Prompt Codebooks: Discrete Compositional Optimization for Language Model Instruction Refinement

• URL: http://arxiv.org/abs/2605.28360v1
• Date: Wed, 27 May 2026 11:57:12 GMT
• Title: Prompt Codebooks: Discrete Compositional Optimization for Language Model Instruction Refinement
• Abstract summary: We propose Prompt Codebooks, a novel compositional prompt optimization framework.<n>It recasts APO as discrete learning over a finite vocabulary of natural-language instincts.<n>It improves over zero-shot by up to +30.36 points, surpasses the strongest prior baseline (GEPA) by +3.34 on HotpotQA and +1.11 in aggregate.
• Score: 10.441136483320205
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Automatic prompt optimization (APO) has driven significant gains in LLM-based agentic workflows. However, existing methods treat each task's prompt as a monolithic, instance-blind string optimized through global edits, producing brittle updates and preventing the reuse of learned sub-behaviors. We propose Prompt Codebooks (PCO), a novel compositional prompt optimization framework that recasts APO as discrete learning over a finite vocabulary of natural-language instincts - atomic, reusable instruction units. PCO organizes prompt-construction knowledge in a discrete codebook and routes each input to a small subset of entries via an LLM-based encoder; a generator composes them into a prompt for the frozen target model; a critic emits a structured verdict that decomposes by attribution into per-variable textual gradients, jointly training the encoder, generator, and codebook under a language-valued min-max objective. The resulting routing is per-instance: different inputs in the same task receive different instinct compositions, a regime structurally inexpressible under instance-blind methods. Across six benchmarks on Qwen3-8B and LLaMA-3.1-8B, PCO improves over zero-shot by up to +30.36 points, surpasses the strongest prior baseline (GEPA) by +3.34 on HotpotQA and +1.11 in aggregate, and reduces deployed prompt length by up to 14.1x versus MIPROv2 and 3.0x versus GEPA using only K=16 instincts.

Related papers

• DHRCL:Training Code LLMs with Dense Hierarchical Rewards and Curriculum Learning [15.421698703970167]
  We propose DHRCL, a reinforcement learning framework with Dense Hierarchical Rewards and Curriculum Learning.<n>DHRCL decomposes feedback into syntax validation, execution success, unit-test pass rate, and AST-based structural similarity.<n>We evaluate DHRCL across Qwen3-4B, Qwen3-8B, and Qwen3-14B backbones, showing that its advantage remains consistent as model capacity increases.
  arXiv  Detail & Related papers  (2026-07-29T04:16:33Z)
• Weave of Formal Thought [51.56484100374058]
  We introduce Weave of Formal Thought (WoFT), a paradigm uniting rigorous syntactic validation with learned structural representations.<n>We present a latent-variable fine-tuning method training the language model to interleave non-terminal grammar symbols directly into generation.<n>For Python, fine-tuning StarCoder2-3B with our RWS objective reduces per-token cross-entropy by 14.3% relative to a text-only SFT baseline.
  arXiv  Detail & Related papers  (2026-06-24T15:58:11Z)
• Embedding by Elicitation: Dynamic Representations for Bayesian Optimization of System Prompts [22.060204303535187]
  System prompts are a central control mechanism in modern AI systems, shaping behavior across conversations, tasks, and user populations.<n>We study this aggregate feedback setting as sample-constrained black-box optimization over discrete, variable-length text.<n>We introduce ReElicit, a Bayesian optimization framework based on emphembedding by elicitation.
  arXiv  Detail & Related papers  (2026-05-18T20:28:17Z)
• Compiling Deterministic Structure into SLM Harnesses [0.6117371161379209]
  Small language models (SLMs) are costly and face data sovereignty limits for high-volume use.<n>We propose Semantic Gradient Descent (SGDe), a teacher-student framework that compiles agentic improvement into discrete execution plans.
  arXiv  Detail & Related papers  (2026-04-19T14:04:29Z)
• Prism: Efficient Test-Time Scaling via Hierarchical Search and Self-Verification for Discrete Diffusion Language Models [96.0074341403456]
  Inference-time compute has re-emerged as a practical way to improve LLM reasoning.<n>Most test-time scaling (TTS) algorithms rely on autoregressive decoding.<n>We propose Prism, an efficient TTS framework for dLLMs.
  arXiv  Detail & Related papers  (2026-02-02T09:14:51Z)
• ZERA: Zero-init Instruction Evolving Refinement Agent - From Zero Instructions to Structured Prompts via Principle-based Optimization [6.591649491003996]
  ZERA is a novel framework that jointly optimize both system and user prompts.<n>ZERA scores prompts using eight generalizable criteria with automatically inferred weights, and revises prompts based on structured critiques.<n>We evaluate ZERA across five large language models and nine diverse datasets spanning reasoning, summarization, and code generation tasks.
  arXiv  Detail & Related papers  (2025-09-17T01:47:29Z)
• Automatic Prompt Optimization for Knowledge Graph Construction: Insights from an Empirical Study [8.482898222291206]
  Triple (subject-relationobject) extraction from text is the fundamental building block of KG construction.<n>Recent work in NLP tasks (e.g. autonomy generation) uses automatic prompt optimization/engineering to address this challenge.<n>We evaluate different settings by changing (a) the prompting strategy, (b) the LLM being used for prompt optimization and task execution, (c) the number of canonical relations in the schema, (d) the length and diversity of input text, (e) the metric used to drive the prompt optimization, and (f) the dataset being used for training and testing.
  arXiv  Detail & Related papers  (2025-06-24T16:38:49Z)
• Context-aware Prompt Tuning: Advancing In-Context Learning with Adversarial Methods [69.36397993451742]
  This work introduces Context-aware Prompt Tuning (CPT), a method inspired by ICL, PT, and adversarial attacks. We modify specific context tokens, considering the unique structure of input and output formats. Inspired by adversarial attacks, we adjust the input based on the labels present in the context, focusing on minimizing, rather than maximizing, the loss.
  arXiv  Detail & Related papers  (2024-10-22T17:45:47Z)
• Prompt Optimization via Adversarial In-Context Learning [51.18075178593142]
  adv-ICL is implemented as a two-player game between a generator and a discriminator. The generator tries to generate realistic enough output to fool the discriminator. We show that adv-ICL results in significant improvements over state-of-the-art prompt optimization techniques.
  arXiv  Detail & Related papers  (2023-12-05T09:44:45Z)
• Instruction Position Matters in Sequence Generation with Large Language Models [67.87516654892343]
  Large language models (LLMs) are capable of performing conditional sequence generation tasks, such as translation or summarization. We propose enhancing the instruction-following capability of LLMs by shifting the position of task instructions after the input sentences.
  arXiv  Detail & Related papers  (2023-08-23T12:36:57Z)
• Guiding Large Language Models via Directional Stimulus Prompting [114.84930073977672]
  We introduce Directional Stimulus Prompting, a novel framework for guiding black-box large language models (LLMs) toward specific desired outputs. Instead of directly adjusting LLMs, our method employs a small tunable policy model to generate an auxiliary directional stimulus prompt for each input instance.
  arXiv  Detail & Related papers  (2023-02-22T17:44:15Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.