CAPO - Constraint-Aware Prompt Optimization for LLM Agents

Sep 15, 2026

Large language models are increasingly used as agents driven by system prompts, which must satisfy distinct requirements such as correct tool use, concise prompts and solution paths, and strict safety or formatting policies. CAPO (Constraint-Aware Prompt Optimization) introduces a primal–dual approach that optimizes system prompts under explicit operational constraints using pool-based rewrites and adaptive constraint weighting. Experiments on agentic benchmarks show more reliable feasibility and improved task performance, while DCAPO extends the method with a dynamically trained, dual-conditioned rewriter for consistent prompt feasibility across domains.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages47

Reading Time1 h 58 min

AccessFree to download

Abstract

Introduction

Operational thresholds for agent deployment

Threshold-constrained prompt optimization

Related Work

Automatic prompt optimization

Context and skill evolution

arXiv :2608 . 16068v1 [ cs .CL] 17 Aug 2026 CAPO: Constraint-Aware Prompt Optimization for LLM Agents Victor Ye Dong1 , Reid Pryzant2 , Yi Liu1 , Jian Jiao1 1Microsoft 2Independent Researcher [victordong@microsoft.com](victordong@microsoft.com) 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 (ConstraintAware 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 assistantstyle 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 An LLM agent can solve its assigned task and still be unsuitable for deployment. It may invoke too many tools, escalate requests unnecessarily, produce an overlong system prompt, or violate safety and formatting policies. These requirements define separate operating thresholds, not one undifferentiated notion of quality [Cui et al., 2025, Barres et al., 2025] . A useful optimizer must therefore improve task performance within the region in which every operational budget is satisfied. Most automatic prompt optimizers do not let users enforce separate thresholds. A fixed weighted score assigns each requirement a coefficient before search, although the binding constraint can change across models, domains, and optimization rounds. Pareto ranking avoids choosing coefficients, but a Pareto-optimal prompt can still violate every deployment threshold. Post-training can help the task model internalize some requirements, but doing so requires access to model weights and suitable training data. By contrast, prompt optimization applies to frozen and API-only models without changing their weights. It does not replace hard safeguards for irreversible or high-stakes actions. We formulate system-prompt optimization as an explicit threshold-constrained problem and solve it with feedback-driven primal–dual search. Each constraint has a nonnegative multiplier that is updated from its signed empirical residual. Violations increase the corresponding weight in later ranking and rewriting; slack decreases it. A prompt pool preserves strong candidates and allows successful rewrites to become parents in later rounds. Figure 1 illustrates how agent behavior drives rewriting, dual updates, and pool retention in one round. Preprint. 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. The framework has two forms. CAPO uses a frozen LLM as its rewriter and stores optimization state in the prompt pool and dual variable

FAQs

What problems does CAPO address when deploying LLM agents?

CAPO targets deployment issues where agents can overuse tools, escalate unnecessarily, produce overly long prompts, or violate safety and formatting policies. It formulates these as separate operational thresholds that must all be satisfied.

How does CAPO optimize system prompts under constraints?

CAPO uses a pool-based primal–dual procedure with feedback-driven search. Each constraint has a nonnegative multiplier updated from signed empirical residuals, increasing weights on violations and decreasing them on slack while retaining promising prompt candidates.

What is DCAPO and how is it different from CAPO?

DCAPO trains a feedback- and dual-conditioned rewriter using CAPO-derived edits and pool-based GRPO, while keeping the task agent frozen. It aims to produce feasible prompts across evaluated domains and match or improve baseline task accuracy.

Sep 15, 2026

Uploaded by Olivia Brown

CAPO - Constraint-Aware Prompt Optimization for LLM Agents_Page 1

Open in WPS to view all 47 pages