Prompt Codebooks: Discrete Compositional Optimization for Language Model Instruction Refinement¶

🕒 Published (v1): 2026-05-27 11:57 UTC · Source: Arxiv · link

Why this paper was selected

Prompt Codebooks: discrete compositional optimization for LLM instruction refinement

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

TL;DR¶

Prompt Codebook Optimization (PCO) replaces monolithic, instance-blind prompt strings with a discrete codebook of $K$ reusable natural-language "instincts," routing each input to $S \ll K$ entries via an LLM encoder and composing them into a per-instance prompt. Training uses a language-valued min–max objective with per-variable textual gradients that update encoder, generator, and active codebook entries independently. On six benchmarks with 8B models, PCO beats the strongest prior baseline (GEPA) by +1.11 aggregate and reduces deployed prompt length by up to 14.1×.

Problem¶

Existing automatic prompt optimization (APO) methods treat the task prompt as a single monolithic string applied identically to every input (instance-blind) and optimized via global edits (globally entangled). A critique fixing one failure mode rewrites the entire prompt and can disrupt well-tuned behaviors elsewhere; learned sub-behaviors cannot be reused across inputs within the same task.

Method¶

PCO introduces four jointly trained components:

Codebook $\mathcal{C} = \{c_1, \ldots, c_K\}$: $K$ short natural-language directives ("instincts"), each an optimizable string variable.
Encoder $E_\theta : \mathcal{X} \times \mathcal{C}^K \to \{1,\ldots,K\}^S$: an LLM that semantically routes input $x$ to $S$ codebook indices ($S \ll K$), producing $z_q = E_\theta(x, \mathcal{C})$.
Generator $G_\phi : \mathcal{X} \times \mathcal{C}^S \to \mathcal{P}$: an LLM that composes selected instincts conditioned on $x$ into a fluent prompt $p = G_\phi(x, \{c_k : k \in z_q\})$.
Critic $D_\psi$: a frozen LLM that emits a structured natural-language verdict $\ell_\text{text} = D_\psi(y, x, p, y^\star)$.

Training optimizes the language-valued min–max objective: $$\Theta^\star = \arg\max_{\theta,\phi,\mathcal{C}} \min_\psi \; \mathbb{E}\left[r(M(p,x), y^\star) - \rho(D_\psi(y,x,p,y^\star))\right]$$

An LLM attribution operator partitions the penalty additively into per-variable textual gradients $g_\phi, g_\theta, g_{c_k}$, enabling localized updates: only the $S$ active codebook entries are rewritten per step. To prevent codebook collapse (dead entries), routing uses $\epsilon$-greedy exploration with success-weighted sampling $\propto \exp(\bar{r}_k / \tau)$ where $\bar{r}_k$ is the EMA reward for instinct $k$. At inference, only the trained $(\theta^\star, \phi^\star, \mathcal{C}^\star)$ are used; no critic or attribution calls are made.

Key Contributions¶

First APO formulation that constructs prompts compositionally from a shared discrete latent vocabulary ($K=16$ instincts) optimized end-to-end via textual gradients.
Per-instance adaptive prompting: $p_x \neq p_{x'}$ for $x \neq x'$, structurally inexpressible under monolithic methods.
Language-valued min–max training with additive per-variable credit assignment ($\mathcal{L}_\text{fid}$, $\mathcal{L}_\text{cb}$, $\mathcal{L}_\text{route}$), enabling localized codebook entry updates.
$\epsilon$-greedy + success-weighted exploration to prevent codebook collapse (routing entropy collapses from 3.78 to 1.74 bits without it).
Up to 14.1× reduction in deployed prompt token length vs. MIPROv2; 3.0× vs. GEPA.

Results¶

HotpotQA (Qwen3-8B): PCO 65.67 vs. GEPA 62.33 (+3.34), vs. zero-shot 42.33 (+23.34).
HotpotQA (LLaMA-3.1-8B): PCO 51.66 vs. zero-shot 21.30 (+30.36).
IFBench (Qwen3-8B): PCO 41.33 vs. GEPA 38.61 (+2.72).
AIME-25 (Qwen3-8B): PCO 35.67 vs. GEPA 32.00 (+3.67); trails only GRPO (38.00).
Aggregate (Qwen3-8B): PCO 55.96 vs. GEPA 54.85 (+1.11); vs. zero-shot 45.23 (+10.73).
Prompt length: PCO ≤714 tokens on HotpotQA vs. MIPROv2's 10,071 (14.1× reduction); aggregate 9.6× reduction vs. MIPROv2, 2.0× vs. GEPA.
Ablation (IFBench, LLaMA-3.1-8B): removing TextGrad −4.67 acc; removing encoder −2.67 acc; removing $\epsilon$-greedy −6.00 acc (routing entropy 3.78→1.74 bits).
Optimal hyperparameters: $K=16$, $S=4$; $K=32$ dilutes signal, $S=1$ limits composition, $S=6$ introduces noise.

Limitations¶

Evaluated only on locally deployed 8B-parameter models; no results on proprietary or larger models due to resource constraints.
Sensitivity analyses for $K$ and $S$ use only $N=30$ subset examples, limiting statistical confidence.
The min–max inner problem is not actually solved during training; ψ is a fixed frozen adversary, so the distributional-distance interpretation of the GAN analogy does not formally apply.
$K=16$ instincts may be insufficient for highly diverse or domain-shifted tasks; the codebook must be retrained per task.
No evaluation on multi-agent pipeline integration despite the agentic workflow motivation.

Relevance to Harnesses / Meta-Harnesses¶

PCO is directly relevant as an automatic prompt optimization subsystem that could serve as a meta-level controller within agentic harnesses: the codebook functions as a shared, versioned instruction library that any agent node in a pipeline can draw from, making prompt knowledge modular and reusable across calls rather than monolithic per-node strings. The per-instance routing mechanism maps naturally onto harness architectures that dispatch different sub-tasks to different instruction profiles at runtime. The localized credit-assignment mechanism (updating only active codebook entries) is analogous to how meta-harnesses should ideally propagate feedback — targeting the failing sub-behavior without corrupting well-tuned neighbors. Finally, the 14.1× prompt compression directly addresses a practical harness constraint: long system prompts in multi-agent pipelines consume context budget shared across tool calls, retrievals, and intermediate outputs.