PaperlayerView exact revision on arXiv

Source-linked AI summary

CAPO: Constraint-Aware Prompt Optimization for LLM Agents

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

arXiv:2608.16068v1cs.CLcs.AI

TL;DR

Deploying LLM agents requires satisfying multiple operational thresholds while preserving task performance, but static prompt objectives cannot adapt when constraints change. CAPO and DCAPO use residual-driven prompt rewriting with adaptive constraint weighting, consistently finding empirically feasible prompts across evaluated domains while maintaining or improving accuracy.

  • Problem

    Static weighted objectives and fixed penalties cannot adapt when different operational constraints become active across domains or search trajectories.

  • Method

    CAPO uses pool-based primal–dual prompt rewriting with adaptive constraint weights, while DCAPO learns a feedback- and dual-conditioned rewriter with the task agent frozen.

  • Results

    CAPO satisfies every constraint in all six agentic settings, and DCAPO produces feasible prompts across every evaluated domain while matching or improving baseline accuracy.

  • Takeaways & Limitations

    Measured constraint residuals can guide prompt optimization toward empirically feasible behavior without updating the deployed task agent.

  • Takeaways & Limitations

    The evaluation does not establish generalization to broader domains or cross-domain transfer.

Abstract

from arXiv · show

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.

1 Introduction

CAPO formulates system-prompt optimization as satisfying separate operational thresholds while improving task performance, using feedback-driven primal–dual search with adaptive constraint weighting. Its CAPO and DCAPO variants preserve a frozen task agent, while DCAPO additionally trains a feedback- and dual-conditioned rewriter.

  • Motivation: CAPO targets task performance within deployment-feasible operating regions defined by separate tool-use, escalation, prompt-length, safety, and formatting thresholds [Cui et al., 2025, Barres et al., 2025].These requirements are distinct operating thresholds rather than one undifferentiated quality measure.
  • CAPO framework: CAPO uses signed empirical constraint residuals to increase weights for violations, decrease weights for slack, and preserve strong candidates in a rewrite-enabled prompt pool.Successful rewrites can become parents in later optimization rounds.
  • CAPO and DCAPO: CAPO uses a frozen LLM rewriter, whereas DCAPO learns a feedback- and dual-conditioned rewrite policy while keeping the deployed task agent frozen.DCAPO learns from CAPO edits and online behavior; only DCAPO updates its rewriter through GRPO.
  • Empirical feasibility: All six combinations of three TAU2-BENCH domains and two task models reached every fixed threshold with a CAPO variant, while fixed-score or Pareto baselines did so for at most one combination.This result concerns thresholds fixed before search.

2 Related Work

Prior work optimizes prompts, skills, or constrained generation through textual, evolutionary, reinforcement-learning, and decoding-based methods. CAPO instead optimizes one deployable system prompt for a frozen task model under workload-level thresholds, while DCAPO trains only the rewriter with adaptive Lagrangian scores.

  • Automatic prompt optimization: Automatic prompt optimization spans textual gradients, optimizer LLMs, Bayesian optimization, scalar-reward learning, policy training, reflection, Pareto selection, and evolutionary operators [Pryzant et al., 2023, Yang et al., 2024].Representative methods include APO, OPRO, InstructZero, RLPrompt, StablePrompt, GEPA, MOPO, and EvoPrompt.
  • Context and skill evolution: Context- and skill-evolution methods revise playbooks or structured skills, sometimes jointly with an RL-trained task policy [Zhang et al., 2025, Alzubi et al., 2026, Wang et al., 2026a].ACE targets reusable playbooks for frozen models, whereas INSPO, SkillRL, SAGE, and ReSkill jointly evolve instructions or skills with an RL-trained task policy [Zhou et al., 2026, Xia et al., 2026, Wang et al., 2026b, He et al., 2026].
  • CAPO’s distinction: CAPO optimizes one deployable system prompt for a frozen task model under workload-level thresholds, while DCAPO trains only the rewriter using adaptive Lagrangian scores.
  • Constrained generation and learning: Constrained decoding and controllable generation enforce or steer token-level output properties, whereas CAPO optimizes system prompts against workload metrics that may depend on full agent trajectories [Hokamp and Liu, 2017, Post and Vilar, 2018, Lu et al., 2021, Scholak et al., 2021].CAPO’s dual update follows constrained RL and CMDP methods.

3 Threshold-Constrained Prompt Optimization

CAPO formulates prompt optimization as maximizing task quality under explicit population-level cost thresholds, while distinguishing task and constraint workloads. It motivates adaptive constraint feedback because static scalarization, Pareto selection, and fixed penalties can fail when active constraints shift across domains or search trajectories.

  • 3.1 Problem Formulation: CAPO models a frozen task model’s prompt as maximizing expected task reward subject to lower-is-better constraint costs meeting explicit budgets.Costs can represent violation indicators or normalized margins, including excess tool use and prompt length; negative margins denote slack.
  • 3.1 Problem Formulation: Task reward and each constraint may use separate workloads, with higher-is-better compliance scores converted into costs before optimization.This separation supports metrics such as task accuracy, safety, and over-refusal that require different inputs.
  • 3.1 Problem Formulation: A prompt is feasible only when every population cost satisfies its threshold, whereas AllSat measures whether every evaluation-set mean meets its fixed threshold.AllSat is an empirical feasibility criterion, not a finite-sample guarantee of population feasibility.
  • 3.2 Limits of Static Objectives: Prompt edits jointly affect task success, tool use, escalation, response length, and safety, so the active constraint can change across domains and during search.These coupled effects make fixed weighting vulnerable to replacing one violation with another.
  • 3.2 Limits of Static Objectives: Fixed weighted scores assign coefficients before observing the search trajectory, while Pareto selection removes coefficients but cannot ensure the frontier enters the threshold-defined admissible region.An entire Pareto frontier may remain outside the feasible region specified by the constrained objective.
  • 3.2 Limits of Static Objectives: Static prompt search and Agent-GRPO with fixed penalties can improve task accuracy yet fail to remain feasible across domains because they lack feedback that responds to changing active constraints.Agent-GRPO updates reward and all costs simultaneously while its fixed penalty vector cannot adapt when another constraint becomes active.

4 CAPO: Primal–Dual Search with a Frozen Rewriter

CAPO optimizes system prompts with a primal–dual loop while keeping the task model and rewriter frozen. It combines feedback-guided pool search with multiplier updates that emphasize persistent constraint violations and retain feasible progress.

  • CAPO optimization loop: CAPO alternates approximate primal prompt rewrites with dual updates from measured threshold residuals, maintaining only a prompt pool and one multiplier per constraint.The task model is unchanged, and the output remains a text system prompt.
  • Feedback-guided rewriting: The frozen rewriter uses execution trajectories, evaluator outputs, constraint critiques, and the current dual state to prioritize constraints with larger multipliers.Multipliers influence both candidate selection through the Lagrangian and rewrite feedback through constraint-grouped failure evidence.
  • Pool-based search: Each round samples high-scoring parents, expands the pool with rewrites, and retains the top candidates, preserving strong prompts when edits fail and allowing useful children to seed later rounds.Parent sampling can use score-based probabilities and optionally mask all but the highest-scoring candidates.
  • Analysis: CAPO’s finite-pool and discrete-rewrite imperfections are modeled as an inexact primal oracle whose gap propagates into the outer primal–dual bound.The analysis introduces a pool gap and shows how the discrete-rewrite residual enters its recursion.
  • Dual updates: The projected dual update raises λ_i when selected candidates exceed τ_i and lowers it when they have slack, while averaging costs across retained candidates reduces sensitivity to noise.Binary constraints use violation rates, whereas continuous constraints use normalized costs or margins.

5 DCAPO: Learning the Rewriter

DCAPO learns the prompt rewriter rather than repeatedly querying a frozen optimizer, conditioning edits on prompt behavior, critic feedback, and the current constraint dual state. It initializes through supervised learning from successful CAPO edits, then applies pool-based GRPO while keeping the deployed task agent frozen.

  • 5 DCAPO: Learning the Rewriter: DCAPO learns a depth-indexed rewriter policy conditioned on the parent prompt, preceding prompt behavior, optional critic summaries, and dual state λ_t, while updating only π_θ.The deployed task policy never receives GRPO updates.
  • 5 DCAPO: Learning the Rewriter: Training first fine-tunes a base model on successful CAPO parent–child pairs, then uses online pool-based GRPO initialized from the same SFT checkpoint across domains.The supervised stage teaches structural preservation and plausible prompt edits; the online stage combines group-relative updates with CAPO’s selection–rewrite process.
  • 5 DCAPO: Learning the Rewriter: The algorithm retains top-scoring children in the prompt pool, updates dual variables from constrained-search scores, and returns both the learned rewriter and the best final prompt.The frozen task model generates behavior, the rewriter receives policy updates, and the pool and dual variables store search state.

6 Surrogate Analysis of Discrete Rewrites

The analysis models discrete text rewrites in a continuous surrogate space and applies inexact primal–dual analysis to separate optimization, finite-pool, and rewrite-mismatch errors. It also distinguishes this surrogate bound from empirical AllSat feasibility and reports positive alignment measurements for one trained rewriter.

  • Surrogate formulation: Both algorithms approximately maximize the current Lagrangian over prompts before taking a projected dual step in a continuous surrogate space for text rewrites.The analysis uses standard inexact primal–dual analysis [Nedi´c and Ozdaglar, 2009], while the surrogate map is analogous to continuous prompt relaxations [Jang et al., 2017, Maddison et al., 2017, Li and Liang, 2021].
  • Theorem 6.1: Under the stated appendix assumptions, Theorem 6.1 analyzes the rewrite-and-retain loop using a contraction parameter ρ = 2µ(κ −Lν/2) ∈(0, 1].The theorem is framed as a rewrite-oracle reduction under Assumptions A1–A2, A4–A7, and B1–B2.
  • Rewrite errors: Rewrite error enters the pool recursion additively, with pruning and noisy extraction measured by πt and ζt.The analysis defines these quantities as components of the rewrite process affecting the recursion.
  • Error decomposition: The surrogate analysis separates ordinary dual optimization, finite-pool error, and mismatch between a text rewrite and ideal ascent.The bound characterizes the surrogate population problem under the stated conditions.
  • Empirical interpretation: The surrogate bound is distinct from empirical AllSat feasibility, which records whether the returned text prompt satisfies every threshold in Section 7.For one trained rewriter, hidden-state alignment, parameter-update alignment, and parent–child ∆J are all positive.

7 Experiments

Across tool-using, assistant-style, privacy, and coding-agent evaluations, CAPO reliably finds feasible prompts while preserving or improving task performance. DCAPO extends this result through learned rewriting, achieving feasibility across domains and matching or exceeding evaluated baselines.

  • Agentic tool use: CAPO satisfies every constraint in all six TAU2-BENCH settings, while the initial prompt, APO, and GEPA are feasible in only one and MOPO in none.The best feasible CAPO prompt exceeds the initial prompt’s accuracy in five settings and matches it in the sixth.
  • Chatbot and privacy delegation: Beyond tool use, both CAPO variants satisfy all chatbot budgets, while CAPO(EA) achieves the highest feasible objective on PUPA–IFBench.These studies cover response length, safety, over-refusal, character-counting, privacy, and instruction-following constraints.
  • Coding agent and ablations: On SWE-BENCH Lite, all methods resolve 5 of 30 issues, while CAPO yields the lowest patch size, tool-action count, and number of files touched.A second rewrite preserves feasibility and usually matches or improves accuracy; online training reduces ToolEx and restores feasibility without reducing accuracy.
  • Robustness and sensitivity: CAPO remains feasible under an embedding-defined task-cluster shift, but mild Gaussian noise preserves feasibility only for Retail, with Airline and Telecom violating at least one threshold.The shifted Airline split produces a modest objective decrease; noisy feedback affects feasibility gating and dual updates, not continuous candidate-ranking scores.
  • Learned rewriter: DCAPO satisfies every constraint across domains and task-agent sizes, and on Qwen3-32B achieves the highest accuracy in each domain where all optimized methods are feasible.Against RL-based prompt-learning baselines, DCAPO is feasible in all three domains, versus StablePrompt on Retail and Agent-GRPO with loose λ on Airline.

8 Limitations

The evaluation isolates prompt rewriting with fixed task agents, so its findings do not characterize joint agent–prompt training or optimization of other deployment artifacts. Results also include infeasible operating points, which are explicitly marked in the RL comparison.

  • Feasibility: Figure 5 marks infeasible RL results alongside held-out accuracy, indicating that some evaluated methods do not reach feasible operating points.Gray hatching and × identify infeasible results.
  • Experimental scope: The experiments modify only the system prompt while keeping the task agent fixed, excluding joint agent–prompt training and optimization of skills or execution harnesses.These alternatives may exhibit different optimization dynamics.
  • Evaluation scope: The evaluation spans multiple agent and assistant tasks, models, and constraint families, but the supplied limitation passage is truncated before specifying the full domain scope.The reported scope is therefore broader than a single task or model, while its complete coverage cannot be determined here.

9 Conclusion … A.3 Algorithmic Definitions

CAPO uses constraint-residual feedback to optimize system prompts without updating task agents, while DCAPO trains a feedback- and dual-conditioned rewriter that achieves feasible performance across evaluated domains. The appendix formalizes the method as an inexact primal–dual procedure connecting discrete rewrites, pool search, and convergence analysis.

  • 9 Conclusion: CAPO uses measured constraint residuals to prioritize failures during system-prompt search, more consistently finding empirically feasible prompts across tool-using agents and assistant-style tasks without updating the task agent.DCAPO extends this approach by training the rewriting process while keeping the task agent frozen.
  • B.2 Training and related appendices: The appendices describe CAPO and DCAPO training, baseline setup, runtime and complexity, open-weight targets, additional experiments, analyses, prompt mechanisms, prompt listings, and broader impacts.The supplied appendix material identifies these topics but does not provide their substantive results here.
  • A Surrogate Primal–Dual Analysis: The surrogate primal–dual analysis treats pool-based prompt search as an inexact primal oracle and connects discrete LLM rewrites to a continuous surrogate model.This appendix analyzes CAPO with projected dual updates.
  • A.1 Setup and Assumptions: The formal setup assumes compact convex primal and dual domains, strong duality, uniform strong concavity and smoothness, bounded constraints, stochastic-gradient noise, bounded pruning loss, parent-selection probability, and extraction noise.These assumptions define the conditions under which the surrogate primal–dual analysis is developed.
  • A.2 Discrete Rewrites and Surrogate Gradients: CAPO’s discrete prompt rewrites are mapped into surrogate space, where the rewriter is assumed to align with the surrogate gradient in expectation rather than requiring token-level gradients.This view parallels continuous relaxations and soft prompt parameterizations [Jang et al., 2017, Maddison et al., 2017, Li and Liang, 2021, Liu et al., 2021, Pryzant et al., 2023, Deng et al., 2022].
  • A.2 Discrete Rewrites and Surrogate Gradients: A discrete rewrite therefore acts as an inexact ascent oracle with a per-step residual, and that residual enters the pool-gap recursion before the outer primal–dual convergence bound.The analysis uses the actual gap of the prompt selected from the pool, avoiding double-counting rewrite error.
  • A.3 Algorithmic Definitions: At each iteration, CAPO samples and mutates pool parents, merges and prunes candidates, extracts a deployed prompt under noisy evaluation, and updates the dual variable.The algorithm also defines an exact best response, primal inexactness, and a primal–dual gap.

A.4 Prompt-Pool Approximation Error … B Experiment Details

The appendix formalizes how pool approximation, extraction, pruning, gradient, dual-drift, and rewrite errors propagate through CAPO’s inexact primal–dual procedure. Under constant-step conditions the method reaches an error neighborhood, while diminishing steps and vanishing residual errors yield convergence in expectation.

  • A.4 Prompt-Pool Approximation Error: One-step stochastic ascent contracts the function gap under L-smoothness, strong concavity, and step size α ≤ 1/L.This contraction is the optimization component used in the pool recursion.
  • A.4 Prompt-Pool Approximation Error: Pool quality is affected by extraction noise, pruning, and dual drift: the pool gap is Lipschitz in λ, while projected dual updates move by at most β_tG_g.Pruning can lose the true best merged-set element by at most B_max.
  • A.4 Prompt-Pool Approximation Error: Lemma A.6 gives a pool recursion contracting the pool gap at rate 1 − ρp_t while adding rewrite error p_tη_t and pruning loss π_tB_max.The bound also accounts for dual-state movement and extraction noise through additional terms.
  • A.4 Prompt-Pool Approximation Error: Proposition A.7 shows that with a positive selection probability, bounded constant-step errors yield bounded expected oracle quality, while diminishing residuals make E[δ_t] converge to zero.The diminishing-step result requires vanishing pruning, dual-drift, and extraction contributions relative to the optimization steps.
  • A.5 Inexact Primal–Dual Bound: Theorem A.8 bounds the pooled inexact primal–dual procedure using the actual primal gap, with separate constant-step and diminishing-step convergence regimes.The constant-step regime supports neighborhood convergence in expectation, whereas diminishing steps provide sufficient conditions for the gap to vanish asymptotically.
  • A.5 Inexact Primal–Dual Bound: In the implemented finite-round experiments, the dual step β is fixed; diminishing-step assumptions are sufficient for asymptotic convergence but are not algorithm requirements.All experiments use a finite number of optimization rounds.
  • A.6 Rewrite Error Propagation: Corollary A.9 shows that rewrite residuals enter the pool recursion additively, and vanishing rewrite, pruning, and extraction errors imply E[δ_t] → 0.The result combines the contractive pool recursion with the outer inexact primal–dual bound.

B.1 Dataset Details … B.3.1 Constraint-Set Scaling

The appendix defines the evaluation workloads, training procedures, baselines, complexity accounting, and extended experiments used to assess CAPO and DCAPO. Across these settings, CAPO remains feasible with an open-weight target and adaptively prioritizes persistent violations as constraint sets grow.

  • B.1 Dataset Details: Each candidate is evaluated on task-specific objective and constraint workloads, with objectives kept higher-is-better and constraints converted to lower-is-better costs.Objective and constraint examples may come from different datasets, but competitors use the same task-specific workloads.
  • B.1 Dataset Details: Results report PLen = L/1,000 with a threshold of 5.0, equivalent to the optimizer’s relative-excess cost threshold of 0.25, preserving feasibility and AllSat labels.Thresholds are anchored to the initial prompt’s training-split mean cost and evaluated on a separate evaluation split.
  • B.2.1 CAPO Training: CAPO iteratively evaluates the retained and expanded pools, updates multipliers from selected residuals, and retains the next beam using round-t scores.Frozen-rewriter CAPO uses up to six rounds; the coding-agent study uses four rounds, and thresholds are fixed before optimization and baseline tuning.
  • B.2.2 Baseline Setup: Baselines receive objective and constraint measurements but generally use fixed multipliers or native Pareto ranking rather than adaptive dual updates.Multi-task APO, GEPA, and EvoPrompt–GA fix constraint coefficients, while MOPO preserves NSGA-II non-dominated sorting and crowding-distance selection.
  • B.2.3 Complexity and Runtime: CAPO matches GEPA’s per-round critique complexity, while its dual update is negligible relative to rollout calls and optimizer-side critique cost is O(kC).Candidate count, rather than workload per candidate, drives cost differences: MOPO evaluates b offspring per candidate, whereas CAPO and GEPA rewrite k selected parents.
  • B.2.4 Open-Weight Targets: CAPO is the only evaluated method satisfying all constraints in all three domains with Ministral-8B, although absolute accuracy decreases across methods.The open-weight target has lower baseline instruction-following accuracy than GPT-5-mini.
  • B.2.5 DCAPO Training: DCAPO trains a feedback- and dual-conditioned rewriter while keeping the task agent frozen, using signed residual rewards and projected multipliers; Agent-GRPO instead holds penalty coefficients fixed.DCAPO uses off-policy prompt-pool parents and group-relative advantages, whereas Agent-GRPO does not update coefficients from observed residuals.
  • B.3.1 Constraint-Set Scaling: With nine Airline constraints, easier constraints remain satisfied with near-zero multipliers, while persistently violated constraints receive larger multipliers without manual weight tuning.The experiment spans resource use, reliability, user experience, and safety; turn and latency violations remain near zero, whereas tool-use and verbosity violations persist.

B.3.2 Model-Scale Ablation … B.4 Analysis

Across ablations and analysis, CAPO’s feasibility depends on model scale, constraint scheduling, and editor capacity, while its generalization studies show strong transfer in coding and shifted-task settings but limited zero-shot cross-domain feasibility. DCAPO remains feasible across all three Qwen3-8B domains and matches or improves feasible accuracy against RL-based baselines.

  • B.3.2 Model-Scale Ablation: Qwen2.5-7B achieves the highest feasible accuracy across tested model sizes at 81.3% with no observed length violations.The accuracy–constraint trade-off is non-monotonic: smaller models have lower accuracy, while larger variants exceed the length budget.
  • B.3.3 Progressive Constraint Addition: Progressive constraint addition recovers accuracy after introducing length while its violation falls, whereas simultaneous optimization activates all three constraints from the first round.AdvBench’s multiplier grows as its violation falls; after length is added, its multiplier rises until length violations reach zero, while character counting remains near zero.
  • B.3.4 Editor-Size Ablation: Best observed feasible score generally improves with editor size across Qwen3-0.6B, Qwen3-4B, and Qwen3-8B, although Retail is non-monotonic.All runs use a frozen Qwen3-32B task agent, the same user simulator, seed, 30-step online budget, and domain thresholds.
  • B.3.5 Generalization and Transfer: CAPO matches the coding-agent resolve rate while recording the smallest patch, fewest tool actions, and fewest files touched among the compared methods.The study optimizes a GPT-5-mini SWE-agent prompt on SWE-BENCH Lite using normalized patch, tool-action, and file-touch costs.
  • B.3.5 Generalization and Transfer: CAPO remains feasible under an embedding-defined Airline task-cluster shift by meeting all three listed thresholds.The evaluation cluster is selected as farthest from the evaluation-set centroid in embedding space.
  • B.3.5 Generalization and Transfer: A Telecom-trained frozen rewriter lowers ToolEx in Retail and Airline without reducing accuracy or violating other cost thresholds, but remains above the ToolEx threshold.One inference-only round therefore produces useful edits without achieving target-domain feasibility absent target-domain adaptation.
  • B.3.6 RL-Based Baselines: DCAPO satisfies all constraints in all three domains, ties the highest feasible accuracy on Airline and Retail, and is the only feasible method on Telecom.This contrasts adaptive, constraint-aware rewriter learning with RL prompt generation and direct task-policy training under fixed weighted objectives.
  • B.4 Analysis: The B.4 analysis examines optimization dynamics, robustness, sensitivity, and alignment between learned rewrites and estimated ascent directions.These analyses complement the empirical ablations and transfer studies without introducing an additional reported result here.

B.4.1 Training Dynamics

CAPO reaches feasibility quickly by amplifying persistent constraint violations, then improves accuracy while preserving feasibility. DCAPO’s feedback-conditioned rewriter sacrifices some task reward to satisfy ToolEx and HAR thresholds, unlike a feedback-free control.

  • B.4.1 Training Dynamics: CAPO reaches chatbot feasibility sooner and finishes with higher task accuracy by increasing multipliers for persistent violations before stabilizing feasibility.After all constraints are satisfied, stable or decreasing multipliers let later prompt updates improve accuracy without losing feasibility.
  • B.4.1 Training Dynamics: DCAPO’s feedback-conditioned rewriter trades some Pass@1 for lower ToolEx and HAR, satisfying both thresholds after roughly 80 accepted prompts.The feedback-free control achieves higher Pass@1 in this run but later violates the HAR threshold.

B.4.2 Robustness and Sensitivity … D Broader Impact

CAPO’s robustness depends on residual-based dual updates: noise and alternative search mechanisms can break feasibility, while tuned dual learning and multiplier scaling preserve it under some tighter budgets. Rewrite-alignment evidence, recurring prompt tactics, prompt listings, and broader-impact analysis further characterize the method’s behavior, scope, and risks.

  • B.4.2 Robustness and Sensitivity: Residual-based iterative feedback is necessary for feasibility: one-shot sampling, static budget injection, and EvoPrompt-GA [Guo et al., 2024] each violate at least one threshold.Sampling finds strong prompts without correcting binding constraints, static injection can shift violations, and generic evolutionary search does not reproduce CAPO’s feasibility.
  • B.4.2 Robustness and Sensitivity: Only β=4 is feasible in both Airline and Telecom and achieves the best feasible objective in each sweep, whereas noisy feedback can break Airline and Telecom feasibility.Mild noise preserves Retail feasibility but breaks Airline and Telecom; noise affects feasibility gating and dual updates, while ranking and final evaluation remain unperturbed.
  • B.4.2 Robustness and Sensitivity: Tightening ToolEx budgets increases final multipliers, but at Airline’s strictest budget of 0.5 the multiplier reaches its cap without producing a feasible prompt.On Telecom, only CAPO satisfies all constraints under the stricter ToolEx ≤70 threshold, consistent with multipliers scaled by violation size.
  • B.4.3 Rewrite Alignment: DCAPO rewrites align with estimated ascent directions: hidden-state displacements align with gradients, parameter updates with policy gradients, and child prompts improve Lagrangian scores on average.The analysis compares sampled parent–child displacements and parameter updates with REINFORCE score-function surrogates under a shared multiplier vector.
  • C.1 Prompt-Level Mechanisms: Representative CAPO and DCAPO prompts exhibit recurring tactics including numbered verification, preconditions before tool calls, autonomous resolution before transfer, and concise response rules.These tactics also appear in baseline prompts, so the listings support qualitative interpretation rather than establishing aggregate method effects.
  • C.2 Agent (TAU2-BENCH) System Prompts: TAU2-BENCH prompt listings compare CAPO, DCAPO, and APO, MOPO, and GEPA baselines, emphasizing policy adherence, verification, confirmation before irreversible actions, efficient tool use, and valid JSON.The prompts commonly require gathering information, checking eligibility, presenting options, obtaining approval, and avoiding redundant tool calls.
  • C.3 Chatbot System Prompts: Chatbot and PUPA–IFBench prompt listings encode concise, stepwise, safe responses alongside privacy-preserving rewriting and strict content, formatting, linguistic, structural, and keyword constraints.The chatbot prompts include character limits, explicit final-answer highlighting, and safety handling; PUPA–IFBench prompts require removing PII while preserving intent.
  • D Broader Impact: CAPO’s explicit constraints can improve accountability but also risk encoding unfair or overly conservative behavior, overfitting narrow test suites, or rewarding superficial compliance while remaining brittle.These risks accompany its intended deployment under behavioral, safety, privacy, and resource constraints.
Loading 2608.16068v1…