Technical Summary: CAPO – Constraint-Aware Prompt Optimization for LLM Agents

1. Problem Formulation

Large Language Models (LLMs) are increasingly deployed as agents that rely on system prompts to execute tasks using external tools. While these agents may successfully complete tasks, they often fail deployment requirements due to operational constraints such as excessive tool usage, unnecessary human escalation, overly long prompts, or violations of safety and formatting policies.

Existing automatic prompt optimization methods typically fail to address these constraints effectively because they rely on:

• Static Weighted Scores: Assigning fixed coefficients to constraints before search begins, which cannot adapt when the "binding constraint" (the most violated requirement) changes across domains or optimization rounds.
• Pareto Ranking: Identifying Pareto-optimal prompts without ensuring they satisfy specific deployment thresholds, potentially leaving all candidates outside the feasible region.
• Post-Training: Requiring access to model weights and supervised data, which is often infeasible for frozen or API-only models.

The paper formulates the problem as a threshold-constrained optimization:
$$\max_{p \in \mathcal{P}_{text}} R(p) \quad \text{s.t.} \quad C_i(p) \leq \tau_i, \quad i = 1, \dots, m$$
where $R(p)$ is the task reward, $C_i(p)$ is the cost of constraint $i$, and $\tau_i$ is the explicit budget. The goal is to find a prompt that maximizes task performance while satisfying all constraints simultaneously.

2. Methodology

The paper introduces CAPO (Constraint-Aware Prompt Optimization), a primal–dual method that treats prompt optimization as a constrained search problem using adaptive Lagrangian multipliers.

2.1 CAPO: Primal–Dual Search with a Frozen Rewriter

CAPO operates in rounds, alternating between a primal step (rewriting prompts) and a dual step (updating constraint weights).

• Lagrangian Ranking: For a set of multipliers $\lambda_i \geq 0$, the method defines a Lagrangian objective:
  $$J(p, \lambda) = R(p) - \sum_{i=1}^m \lambda_i (C_i(p) - \tau_i)$$
  Prompts are ranked by $J(p, \lambda)$. This ranking guides parent selection for rewriting and determines which prompts are retained in the pool.
• Approximate Primal Rewrites: A frozen "critic" LLM summarizes task failures and constraint violations. A frozen "rewriter" LLM then generates new prompts based on this evidence and the current dual state (multipliers). The rewrite instruction explicitly includes the weights $(1, \lambda_1, \dots, \lambda_m)$ to prioritize constraints with larger multipliers.
• Residual-Driven Dual Updates: After evaluating the expanded pool, the multipliers are updated using a projected subgradient step based on the empirical residual of the top candidates:
  $$\lambda_i \leftarrow \Pi_{[0, \lambda_{max}]} \left[ \lambda_i + \beta \left( \frac{1}{|P_{best}|} \sum_{p_j \in P_{best}} \hat{\rho}_{i,j} - \tau_i \right) \right]$$
  If a constraint is violated ($\hat{\rho} > \tau$), its multiplier increases, increasing its weight in future ranking and rewriting. If there is slack, the multiplier decreases.
• Prompt Pool: A pool of retained prompts preserves strong candidates, allowing successful rewrites to seed future rounds.

2.2 DCAPO: Dynamically Trained CAPO

To improve efficiency and adaptability, the authors introduce DCAPO, which learns a feedback- and dual-conditioned rewriter policy ($\pi_\theta$) instead of relying on a frozen LLM.

• Training: DCAPO uses pool-based GRPO (Group Relative Policy Optimization). It samples parents from the evolving prompt pool, generates groups of child prompts, evaluates them with the frozen task agent, and updates the rewriter policy based on the adaptive Lagrangian scores.
• Conditioning: The rewriter is conditioned on the parent prompt, the previous rewrite in a depth sequence, behavioral trajectories (tool calls, failures), and the current dual state $\lambda_t$.
• Separation of Concerns: The deployed task agent remains frozen; only the rewriter is trained.

2.3 Theoretical Analysis

The paper provides a surrogate analysis characterizing the convergence of the method. It models the discrete text rewrites as an inexact ascent step in a continuous surrogate space. The analysis establishes a primal–dual bound that accounts for:

1. Finite-pool approximation errors.
2. Discrete-rewrite residuals (the gap between the discrete text rewrite and the ideal continuous ascent).
3. Standard dual optimization errors.
   The bound shows that under specific assumptions (strong concavity, bounded gradients), the method converges to a feasible solution as the step sizes vanish.

3. Key Contributions

1. Constraint-Aware Prompt Optimization: The development of a pool-based primal–dual procedure that uses signed residuals to adaptively weight constraints, moving beyond static scalarization or Pareto ranking.
2. Consistent Empirical Feasibility: Demonstrating that CAPO reliably reaches operating points where every operational budget is satisfied across diverse domains (Airline, Retail, Telecom) and model sizes, whereas static baselines (APO, GEPA, MOPO) fail to do so in most settings.
3. A Learned Rewriter (DCAPO): Introducing a method to train a rewrite policy using pool-based GRPO. DCAPO produces feasible prompts across domains and matches or exceeds the accuracy of baselines while keeping the task agent frozen.
4. Surrogate Analysis: Providing a theoretical characterization of how finite-pool and discrete-rewrite errors propagate through the inexact primal–dual procedure.

4. Experimental Results

The evaluation spans three main areas: TAU2-BENCH (tool-using agents), Chatbot/Privacy benchmarks, and Coding agents.

4.1 Agentic Tool Use (TAU2-BENCH)

• Feasibility: Across six combinations of three domains (Airline, Retail, Telecom) and two task models (GPT-5-mini, GPT-5.1), CAPO was the only method to satisfy all constraints in every setting.
  • Baselines (Initial, APO, GEPA, MOPO) achieved feasibility in at most one combination.
  • CAPO achieved feasibility in all six combinations while maintaining or improving task accuracy compared to the initial prompt.
  • Note: While CAPO(EA) (a variant using equal eligibility for parents) achieved feasibility in 5 out of 6 settings, the standard CAPO variant was the only method to achieve feasibility in all 6 settings.
• Open-Weight Models: When applied to Ministral-8B, CAPO was the only evaluated method to satisfy all constraints in all three domains, demonstrating robustness even with models that have lower baseline instruction-following capabilities.
  • Note: While APO achieved feasibility in the Airline and Retail domains for Ministral-8B, it failed in the Telecom domain, whereas CAPO succeeded across all three.

4.2 Assistant and Privacy Constraints

• Chatbot Suite: CAPO variants satisfied all four budgets (GSM8K accuracy, response length, safety, over-refusal) and matched the accuracy of infeasible baselines.
• Privacy Delegation (PUPA–IFBench): CAPO achieved the highest objective among all feasible methods, showing the framework extends beyond tool-use costs to safety, formatting, and instruction-following constraints.

4.3 DCAPO Performance

• Feasibility: DCAPO produced feasible prompts in every evaluated domain and task-agent size (Qwen3-8B and Qwen3-32B).
• Comparison with RL: Unlike Agent-GRPO (which updates the task agent with fixed penalties) or StablePrompt, DCAPO consistently satisfied constraints across all domains.
• Ablations:
  • Feedback Source: Online behavioral feedback (using full trajectories) was shown to be critical for feasibility compared to summary-only feedback.
  • Rewrite Depth: Using a second rewrite step (D=2) generally preserved feasibility and improved accuracy.

4.4 Robustness and Transfer

• Noise Sensitivity: CAPO remained feasible under mild noise in dual feedback for the Retail domain, though stricter domains (Airline, Telecom) showed sensitivity, highlighting the importance of accurate cost estimation.
• Task Cluster Shift: CAPO maintained feasibility on an embedding-defined shifted task cluster, demonstrating generalization within a domain.
• Zero-Shot Transfer: A rewriter trained on one domain (Telecom) could reduce tool usage in other domains (Retail, Airline) but did not achieve full feasibility without target-domain adaptation, indicating the need for domain-specific fine-tuning for strict constraints.

5. Significance and Claims

The paper claims that CAPO offers a significant shift in how prompt optimization is approached for deployed agents:

• From Static to Adaptive: It replaces fixed constraint weights with a feedback loop where measured constraint residuals dynamically determine which failures receive attention during search.
• Feasibility as a Primary Goal: The method prioritizes finding prompts that satisfy all deployment thresholds, rather than optimizing a weighted sum that may violate critical constraints.
• Applicability to Frozen Models: By optimizing the system prompt rather than the model weights, CAPO is applicable to API-only and frozen models, a critical requirement for many real-world deployments.
• Learnable Rewriting: DCAPO demonstrates that the rewriting process itself can be learned from behavioral feedback, enabling efficient adaptation without retraining the task agent.

The authors conclude that deployment requirements should serve not just as final evaluation criteria, but as the active feedback signal that guides the search process. This approach provides a more reliable path to deploying LLM agents that are both capable and compliant with operational constraints.