CAPO: Constraint-Aware Prompt Optimization for LLM Agents

Victor Ye Dong; Reid Pryzant; Yi Liu; Jian Jiao

cs.CLAug 17, 2026

CAPO: Constraint-Aware Prompt Optimization for LLM Agents

Authors: Victor Ye Dong, Reid Pryzant, Yi Liu, Jian Jiao

Organizations: Microsoft · Independent Researcher

Abstract

Large language models (LLMs) are increasingly deployed as agents that rely on system prompts to use tools and complete tasks. Such deployments impose distinct operational requirements, including appropriate tool use, concise prompts and solution paths, and compliance with safety and formatting policies. For many practitioners, however, assembling domain-specific supervised data to post-train models to meet these requirements is infeasible. We introduce CAPO (Constraint-Aware Prompt Optimization), a primal-dual method that combines pool-based rewrites with adaptive constraint weighting to optimize system prompts under explicit operational constraints. Across agentic benchmarks, CAPO more reliably reaches empirically feasible operating points while improving task performance. CAPO also generalizes beyond agentic settings, achieving strong results on assistant-style evaluations with output-format and safety/privacy constraints. We further introduce DCAPO (Dynamically Trained CAPO), which trains a feedback- and dual-conditioned rewriter with pool-based GRPO while keeping the task agent frozen. Across task agents of different sizes, DCAPO produces a feasible prompt in every evaluated domain and matches or improves the task accuracy achieved by the evaluated baselines. A surrogate analysis characterizes how finite-pool and discrete-rewrite errors enter the inexact primal-dual procedure.

Figures & tables

Figure 1: One round of constraint-aware prompt evolution. The frozen task agent executes a retained prompt, and its behavior supplies reward, constraint costs, and rewrite evidence. Capo uses a frozen LLM as the rewriter, whereas DCAPO uses a trainable rewriter. Both methods evaluate children, update the dual variables from signed threshold residuals, and retain the next prompt pool. Only DCAPO updates the rewriter through GRPO.

Figure 2: Static objectives do not provide reliable constraint control. Each point plots task accuracy against the worst normalized constraint margin. Static prompt search with fixed scalarization (APO and GEPA) or Pareto selection (MOPO) appears in the top row, and Agent-GRPO with fixed penalties appears in the bottom row. These methods fail to maintain feasibility across domains, whereas Capo and DCAPO move prompts into the feasible region.

	GPT-5-mini					GPT-5.1
Method	Acc $\uparrow$	HAR $\downarrow$	ToolEx $\downarrow$	PLen $\downarrow$	AllSat	Acc $\uparrow$	HAR $\downarrow$	ToolEx $\downarrow$	PLen $\downarrow$	AllSat
Airline
Threshold	–	35	105	5.00	–	–	80	80	5.00	–
Initial	25.0	35.0	105.0	0.30	✓	55.0	95.0	91.8	0.30	✗
APO	25.0	10.0	141.0	2.20	✗	45.0	20.0	113.1	3.10	✗
GEPA	30.0	10.0	92.0	4.20	✓	65.0	30.0	152.3	4.72	✗

Table 1: CAPO reaches a feasible operating point in all six evaluated settings. Bold marks the highest feasible accuracy, and underlining marks the next distinct feasible accuracy; ties are included. Per-example standard errors appear in Appendix Tables 14 – 16 .

Table 4

Domain	Method	Acc. $\uparrow$	HAR $\downarrow$	ToolEx $\downarrow$	PLen $\downarrow$	AllSat	Acc. $\uparrow$	HAR $\downarrow$	ToolEx $\downarrow$	PLen $\downarrow$	AllSat
		Qwen3-8B					Qwen3-32B
Airline	Threshold	–	30.0	200.0	5.00	–	–	30.0	200.0	5.00	–
	Initial	0.0	10.0	186.9	0.30	✓	15.0	5.0	232.8	0.30	✗
	Agent-GRPO (loose $\lambda$ )	30.0	20.0	-19.7	0.30	✓	15.0	5.0	144.3	0.30	✓
	Agent-GRPO (strict $\lambda$ )	15.0	60.0	3.3	0.30	✗	0.0	0.0	95.1	0.30	✓
	DCAPO ( $D{=}1$ )	30.0	0.0	-78.7	3.68	✓	20.0	0.0	165.6	3.80	✓

Table 4: Adaptive rewriting produces feasible prompts across domains and task-agent sizes. For Agent-GRPO, loose and strict

\lambda

denote the fixed penalty vectors

(\lambda_{\mathrm{ToolEx}},\lambda_{\mathrm{HAR}})=(1,2.5)

and

(2,4)

, respectively; Appendix B.2.5 gives the corresponding reward. Within each domain and task-model size, bold marks the highest feasible accuracy, and underlining marks the next distinct feasible accuracy; ties are included.

Figure 5: RL methods with Qwen3-8B. Bars give held-out accuracy; gray hatching and

\times

denote infeasible results.

Appendix figures & tables44 assets

Supplementary material from the paper’s appendix.

Appendix

Type	Name	Description
Agent ( tau2-bench [ Barres et al., 2025 ] )
O	tau2-bench (Acc.)	Tool–agent–user benchmark for policy-governed customer service. We evaluate Airline (94 tasks), Retail (114), and Telecom (114). Each task provides a user goal, domain tools, and a policy document; the benchmark grader determines whether the final agent state completes the requested task.
C	HAR	Mean number of transfer-to-human calls per dialogue, reported as $100$ times the mean. Values can exceed $100$ when one dialogue issues multiple transfer requests.
C	ToolEx	Relative tool-use excess, $(n_{\text{actual}}-n_{\text{reference}})/n_{\text{reference}}\times 100\%$ . Zero matches the reference path, positive values use more calls, and negative values use fewer.
C	PLen	System-prompt character count divided by 1,000; the reporting threshold is 5.0.
Chatbot

Appendix

Table 5: Objectives and constraints by evaluation workload. “O” denotes a higher-is-better objective, and “C” denotes a lower-is-better cost. Thresholds and domain-specific values appear in Tables 1 , 3 , and 10 .

Setting	Dataset	Opt.	Eval.
I (Agent)	Airline	74	20
	Retail	74	40
	Telecom	74	40
II (Chatbot)	GSM8K	7,473	1,319
	AdvBench (safety)	520	128
	Over-Rejection	128	128

Appendix

Table 6: Optimization and evaluation split sizes. Counts follow benchmark-provided or experiment-specific splits and need not sum to the full corpus size.

Parameter	Value
Max optimization rounds	6
Retained beam size ( $k_{1}$ )	6
Parents sampled per round ( $k$ )	4
Children per parent	2
Dual learning rate $\beta$	4
Multiplier cap $\lambda_{\max}$	10

Appendix

Table 7: Representative CAPO configuration on tau2-bench . All settings use a frozen rewriter.

Method	Critique cost / round	Eval cost / round	AllSat (3/3)
APO	$O(nC)$	$O(nE_{\mathrm{tot}})$	1 / 3
MOPO	$O(nbC)$	$O(nbE_{\mathrm{tot}})$	0 / 3
GEPA	$O(kC)$	$O(nE_{\mathrm{tot}})$	1 / 3
Capo	$O(kC)$	$O(nE_{\mathrm{tot}})$	3 / 3

Appendix

Table 8: CAPO matches GEPA’s per-round critique and evaluation complexity while satisfying all three domains. Here

n

is the pool size,

k

the selected-parent count (

k\leq n

b

the number of MOPO offspring per candidate,

E_{\mathrm{tot}}

the full per-candidate workload, and

C

one optimizer-LLM call. AllSat (3/3) counts the tau2-bench domains in which every metric meets its GPT-5-mini threshold in Table 1 .

Setting / Method	Acc. $\uparrow$	HAR $\downarrow$	ToolEx $\downarrow$	PLen $\downarrow$	AllSat
Airline
Threshold	–	30	200	5.00	–
Initial prompt	15.0	10.0	219.7	0.30	✗
APO	20.0	5.0	188.5	4.24	✓
GEPA	10.0	25.0	239.3	5.54	✗
MOPO	15.0	25.0	237.7	4.72	✗

Appendix

Table 9: Capo is the only method feasible in all three domains with Ministral-8B. Results follow the format of Table 1 . Bold marks the highest accuracy among feasible methods, and underlining marks the next distinct feasible accuracy; ties are included.

Figure 6: Constraint dynamics with nine constraints on Airline. Blue and orange curves show training and evaluation violation rates across optimization rounds. Violations of the turn and latency constraints remain near zero, whereas tool-use and verbosity violations persist and show larger gaps between training and evaluation.

Figure 7: Multiplier trajectories with nine Airline constraints. Constraints with persistent violations accumulate larger multipliers, whereas the multipliers for constraints satisfied early remain stable.

Figure 8: Qwen2.5-7B attains the highest feasible accuracy across the tested model sizes. Held-out accuracy before and after prompt optimization appears on the left, with the corresponding length-violation rates on the right. The dashed line marks the 15% violation threshold; Qwen2.5-7B reaches 81.3% accuracy with no observed violations.

Figure 9: Progressive and simultaneous optimization follow different trajectories. Panels compare held-out accuracy and violation rates for the 12-round progressive run and the six recorded rounds of simultaneous optimization. Progressive optimization uses AdvBench safety and character counting in rounds 1–6 and adds length after round 6; simultaneous optimization activates all three constraints from its first round. Error bars denote one standard deviation, clipped to

[0,1]

. Horizontal dashed lines mark the violation threshold

\tau=0.05

Figure 10: Dual multipliers track active constraint violations. Held-out violation rates appear on the left and the corresponding multiplier trajectories on the right. The vertical line marks the introduction of the length constraint after round 6. Error bars denote one standard deviation, clipped to

[0,1]

Figure 11: Best observed feasible score across editor sizes. Dotted lines compare Qwen3-0.6B, Qwen3-4B, and Qwen3-8B rewriters. All runs use a frozen Qwen3-32B task agent and the same user simulator. The Airline 8B point uses the extended-context configuration. This is a best-observed comparison across settings, not a single-setting size ablation.

Method	Resolve $\uparrow$	Patch $\downarrow$	Tool $\downarrow$	Files $\downarrow$	AllSat
Threshold	–	1.2	0.4	1.7	–
Initial	0.167	1.298	0.423	1.867	✗
MOPO	0.167	1.209	0.393	1.500	✗
Capo	0.167	1.055	0.371	1.300	✓

Appendix

Table 10: CAPO matches the resolve rate while reducing all three coding-agent costs. These values underlie the coding-agent panel in Figure 4 . Bold marks the highest feasible objective, and underlining marks the next distinct feasible objective; ties are included. A row satisfies AllSat only if Patch, Tool, and Files each meet the threshold listed in the first row.

Split	Objective $\uparrow$	ToolEx $\downarrow$	HAR $\downarrow$	PLen $\downarrow$
In-domain	0.450	1.049	0.050	4.98
Shifted	0.400	1.000	0.250	4.91

Appendix

Table 11: CAPO remains feasible under an embedding-defined Airline task-cluster shift. Objective, ToolEx, and HAR are fractions or ratios; PLen is the system-prompt character count divided by 1,000. Bold marks the highest feasible objective, and underlining marks the next distinct feasible objective; ties are included.

Domain	Prompt	Acc $\uparrow$	ToolEx $\downarrow$	HAR $\downarrow$	PLen $\downarrow$	AllSat
Retail	Threshold	–	60.0	30.0	5.00	–
Retail	Initial	27.5	84.0	12.5	0.32	✗
Retail	Frozen Telecom rewrite	32.5	67.0	12.5	1.96	✗
Airline	Threshold	–	200.0	30.0	5.00	–
Airline	Initial	10.0	329.0	15.0	0.32	✗
Airline	Frozen Telecom rewrite	10.0	220.0	10.0	3.04	✗

Appendix

Table 12: Frozen-rewriter transfer lowers ToolEx without reaching target-domain feasibility. A Telecom-trained rewriter is transferred for one inference-only round. No accuracy is bold because no row is feasible.

Domain	Method	Acc $\uparrow$	ToolEx $\downarrow$	HAR $\downarrow$	PLen $\downarrow$	AllSat
Airline	Threshold	–	200.0	30.0	5.00	–
Airline	StablePrompt	15.0	436.4	5.0	0.63	✗
Airline	Agent-GRPO (loose $\lambda$ )	30.0	-19.7	20.0	0.30	✓
Airline	DCAPO	30.0	-78.7	0.0	3.68	✓
Telecom	Threshold	–	40.0	60.0	5.00	–
Telecom	StablePrompt	0.0	81.9	2.5	0.71	✗

Appendix

Table 13: DCAPO is feasible in all three Qwen3-8B domains. StablePrompt and Agent-GRPO provide prompt-policy and task-policy comparisons, respectively; DCAPO uses complete trajectories (

D{=}1

). Agent-GRPO uses the loose fixed penalty vector

(\lambda_{\mathrm{ToolEx}},\lambda_{\mathrm{HAR}})=(1,2.5)

. AllSat holds only when every cost meets its domain threshold. Within each domain, bold marks the highest feasible accuracy, and underlining marks the next distinct feasible accuracy; ties are included.

Figure 12: CAPO reaches chatbot feasibility sooner and finishes with higher task accuracy. The trajectories track constrained prompt optimization across rounds.

Figure 13: DCAPO training dynamics on Airline. Feedback-conditioned training is compared with a feedback-free control as prompts enter the pool. The feedback-conditioned run gives up some Pass@1 but eventually satisfies the ToolEx and HAR thresholds; shading marks the feasible region for each metric.

Method	Acc.	HAR	ToolEx	PLen
Init	0.2500 $\pm$ 0.0793	0.3500 $\pm$ 0.0894	1.0500 $\pm$ 0.2866	0.3060 $\pm$ 0.0000
APO	0.2500 $\pm$ 0.0793	0.1000 $\pm$ 0.0488	1.4100 $\pm$ 0.6521	2.1808 $\pm$ 0.0000
MOPO	0.4500 $\pm$ 0.0941	0.2500 $\pm$ 0.0793	1.5574 $\pm$ 0.0488	4.6780 $\pm$ 0.0000
GEPA	0.3000 $\pm$ 0.0851	0.1000 $\pm$ 0.0488	0.9200 $\pm$ 0.0924	4.2000 $\pm$ 0.0000
Capo (EA)	0.5000 $\pm$ 0.0947	0.2000 $\pm$ 0.0718	1.0000 $\pm$ 0.0851	4.6100 $\pm$ 0.0000
Capo	0.4500 $\pm$ 0.0906	0.0500 $\pm$ 0.0500	1.0492 $\pm$ 0.0918	4.9840 $\pm$ 0.0000

Appendix

Table 14: Per-example uncertainty on Airline with GPT-5-mini. Values are means

\pm

SE for the tau2-bench agent metrics. The accuracy in Table 1 uses a different number of evaluation examples; the denominator here matches the corresponding run.

Method	Acc.	HAR	ToolEx	PLen
Init	0.5000 $\pm$ 0.0601	0.1250 $\pm$ 0.0330	0.5270 $\pm$ 0.0550	0.3040 $\pm$ 0.0000
APO	0.5750 $\pm$ 0.0592	0.0750 $\pm$ 0.0422	0.5750 $\pm$ 0.0564	0.3040 $\pm$ 0.0000
MOPO	0.5500 $\pm$ 0.0597	0.0750 $\pm$ 0.0422	0.5590 $\pm$ 0.0564	5.8680 $\pm$ 0.0000
GEPA	0.5000 $\pm$ 0.0601	0.0500 $\pm$ 0.0349	0.5160 $\pm$ 0.0584	4.5160 $\pm$ 0.0000
Capo (EA)	0.5000 $\pm$ 0.0584	0.1250 $\pm$ 0.0480	0.4950 $\pm$ 0.0534	4.5120 $\pm$ 0.0000
Capo	0.5500 $\pm$ 0.0597	0.1250 $\pm$ 0.0330	0.4409 $\pm$ 0.0592	4.7000 $\pm$ 0.0000

Appendix

Table 15: Per-example uncertainty on Retail with GPT-5-mini. Values are means

\pm