PaperlayerView exact revision on arXiv

Source-linked AI summary

MOCHA: Multi-Objective Chebyshev Annealing for Agent Skill Optimization

Md Mehrab Tanjim, Jayakumar Subramanian, Xiang Chen, Branislav Kveton, Subhojyoti Mukherjee, Anlan Zhang, Sungchul Kim, Somdeb Sarkhel, Sunav Choudhury

arXiv:2605.19330v1cs.AIcs.LGcs.SE

TL;DR

Skill optimization must balance task correctness against hard, multi-field platform constraints, a trade-off that existing single-objective optimizers mishandle. MOCHA combines Chebyshev scalarization with annealed exploration and exploitation, improving results across six skills and producing more Pareto-optimal variants.

  • Problem

    Skill optimization is a structured multi-objective problem because correctness competes with description, instruction-body, and shared-context compliance limits that existing optimizers ignore or collapse into one scalar.

  • Method

    MOCHA uses randomized Chebyshev scalarization for parent selection, hypervolume-gated exploration, and annealed acceptance that transitions toward exploitation as optimization progresses.

  • Results

    Across six agent skills, MOCHA improves mean correctness by 7.5% relative to the strongest baseline, breaks through on every task, and discovers twice as many Pareto-optimal variants.

  • Takeaways & Limitations

    MOCHA enables progress where single-objective baselines remain at the seed skill, particularly when correctness and compliance objectives conflict.

  • Takeaways & Limitations

    MOCHA’s compliance metrics are tied to Anthropic’s SKILL.md specification, and its fixed exponential annealing schedule remains a hyperparameter.

Abstract

from arXiv · show

LLM agents organize behavior through skills - structured natural-language specifications governing how an agent reasons, retrieves, and responds. Unlike monolithic prompts, skills are multi-field artifacts subject to hard platform constraints: description fields are truncated for routing, instruction bodies are compacted via progressive disclosure, and co-resident skills compete for limited context windows. These constraints make skill optimization inherently multi-objective: a skill must simultaneously maximize task performance and satisfy platform limits. Yet existing prompt optimizers either ignore these trade-offs or collapse them into a weighted sum, missing Pareto-optimal variants in non-convex objective regions. We introduce MOCHA (Multi-Objective Chebyshev Annealing), which replaces single-objective selection with Chebyshev scalarization - covering the full Pareto front, including non-convex regions - combined with exponential annealing that transitions from exploration to exploitation. In our experiments across six diverse agent skills - where all methods share the same multi-objective mutation operator and baselines receive identical per-objective textual feedback - existing optimizers fail to improve the seed skill on 4 of 6 tasks: 1000 rollouts yield zero progress. MOCHA breaks through on every task, achieving 7.5% relative improvement in mean correctness over the strongest baseline (up to 14.9% on FEVER and 10.4% on TheoremQA) while discovering twice as many more Pareto-optimal skill variants.

1 Introduction

Skills are structured, multi-field behavioral specifications whose correctness objectives conflict with hard platform-compliance limits. MOCHA addresses this structured multi-objective problem with Pareto-front navigation, combining Chebyshev scalarization and exploration-to-exploitation annealing.

  • Motivation: Skills combine descriptions, instruction bodies, and metadata, making them reusable behavioral specifications rather than monolithic prompts.Descriptions support routing and retrieval, instruction bodies govern reasoning and responses, and metadata specifies preconditions and output schemas.
  • Motivation: Platform truncation and shared context budgets create correctness–compliance trade-offs that existing optimizers ignore or collapse into one scalar.Description fields, instruction bodies, and co-resident skills face distinct limits, while compression can sacrifice reasoning structure.
  • MOCHA: MOCHA combines HVC-gated exploration with annealed Chebyshev-consistent exploitation to navigate potentially non-convex Pareto fronts.Exploration broadens the set of trade-off points; exploitation refines the weakest objective as the optimization budget is consumed.
  • MOCHA: MOCHA formalizes skill optimization over multi-field natural-language artifacts with competing task-correctness and platform-compliance objectives.The formulation explicitly accounts for SKILL.md field limits rather than treating the skill as a single text blob.
  • Evaluation: Across six agent skills, MOCHA improves mean correctness by 7.5% relative to the strongest baseline and discovers twice as many Pareto-optimal variants.All methods use the same SKILL.md-aware mutation interface and identical per-objective textual feedback; candidate selection is the independent variable.

2 Related Work

Related work spans prompt optimization, agent skill refinement, and classical multi-objective optimization. MOCHA targets the gap between these areas: gradient-free, discrete, sample-expensive optimization of existing natural-language skills under competing objectives.

  • Prompt and instruction optimization: Prompt optimizers include gradient-dependent methods and gradient-free propose-and-rank or feedback-driven approaches, but skill optimization must operate through black-box language-model evaluations.Gradient-dependent methods require differentiable traces or policy-gradient signals, while gradient-free methods use LLM calls.
  • Agent skill discovery and refinement: Skill refinement updates existing natural-language definitions, unlike skill discovery methods that extract reusable skills through many trajectories and depend on costly underlying tools.This focus also suits closed-source API models, where fine-tuning is unavailable and prompt optimization is the remaining lever.
  • Multi-objective optimization: Classical multi-objective methods assume continuous decision spaces and cheap evaluations, whereas skill search uses discrete natural language and expensive LLM calls.MOCHA addresses this mismatch by adapting multi-objective mechanisms to natural-language skill optimization.
  • Multi-objective optimization: Linear scalarization can miss Pareto-optimal points in non-convex regions, while Chebyshev scalarization can access the full Pareto front.MOCHA combines Chebyshev scalarization with hypervolume-based exploration and annealed mode switching in the discrete setting.

3 Method

MOCHA formulates skill optimization as multi-objective search over correctness and platform compliance, returning Pareto-optimal variants rather than a single scalar-selected skill. It combines randomized Chebyshev parent selection with threshold-annealed exploration and exploitation, using hypervolume contribution to expand the front before refining it.

  • Problem formulation: Skill optimization seeks Pareto-optimal definitions across multiple normalized metrics, allowing practitioners to choose correctness, compliance, or a balance after optimization.The pool represents correctness, description compliance, and body compliance as objective-space points.
  • Parent selection: MOCHA selects mutation parents by drawing weights from a Dirichlet distribution and minimizing weighted worst-case deviation from the ideal point.Chebyshev scalarization can access Pareto-optimal solutions in non-convex regions, unlike linear scalarization.
  • Acceptance modes: Exploration accepts candidates that improve the Pareto front in any direction, whereas exploitation accepts candidates that improve the Chebyshev objective in the parent’s selected direction.This separates direction-agnostic front expansion from later scalarized refinement.
  • Hypervolume contribution: Hypervolume contribution measures the exclusive objective-space volume added by a candidate and is positive exactly when the candidate is non-dominated by the current pool.With three objectives, exact computation is tractable in O(n^2 log n).
  • Final selection: MOCHA grows a validated pool of distinct skill variants and returns the full pool for practitioner selection according to deployment priorities.The algorithm initializes with the seed, repeatedly mutates selected parents, evaluates candidates, and commits accepted variants within the budget.
  • Threshold annealing: The acceptance threshold decays exponentially with consumed budget, shifting from HVC-based exploration early to Chebyshev-based exploitation later.The threshold is set to approach zero around the budget midpoint; a size-5 HVC priority queue delays expensive validation until a promising candidate exceeds the threshold.
  • Mutation: Skill-aware mutation preserves the multi-field structure of the natural-language artifact during candidate generation.The framework uses skill-aware mutation strategies within the LLM-based mutation step.

4 Experiments

The experiments evaluate SKILL.md optimization across six skills under matched budgets, measuring correctness, compliance, and Pareto-front quality. MOCHA consistently improves beyond seed skills and balances correctness with diversity through its exploration–exploitation design.

  • Experimental setup: Six skills span reasoning, multi-hop, and code categories, with 100 train, validation, and test examples sampled per benchmark.
  • Experimental setup: The evaluation reports correctness, description compliance, body compliance, and 3D hypervolume under a 1,000-rollout budget with five seeds.All methods use the same SKILL.md-aware mutation interface and matched evaluation protocol.
  • Main results: On 4 of 6 tasks, all three baselines return the seed skill unchanged after 1,000 rollouts, producing zero improvement.MOCHA improves on every task and achieves 7.5% relative improvement in mean correctness over ProTeGi.
  • Main results: MOCHA discovers 2× more Pareto-optimal variants than competing methods, with 3.6 versus 1.6 variants and 3.1% higher 3D hypervolume.Its variants span the correctness–compliance frontier while baselines cluster at a single operating point.
  • Ablation study: Removing HVC gating increases correctness to .687 but reduces diversity, whereas removing annealing increases Pareto size to 3.8 but lowers correctness to .671.MOCHA balances these forces with correctness .675, 3.6 Pareto points, and .531 HV.
  • Qualitative comparison: The FEVER comparison shows baselines retaining the seed template while MOCHA produces structured rules and explicit reasoning.The figure uses grey for shared YAML fields, red for the baseline, and green for the MOCHA-optimized skill.

5 Discussion and Conclusion

MOCHA combines Chebyshev scalarization with annealed exploration and exploitation to navigate non-convex skill trade-offs, while its limitations include low-conflict tasks, fixed scheduling, and platform-specific compliance.

  • Discussion: 2× more non-dominated skill variants were discovered by MOCHA than by baselines, with 3.6 Pareto points versus 1.6.Removing HVC gating favored highest correctness, removing annealing favored richest Pareto fronts, and full MOCHA balanced both.
  • Future directions: Applying the multi-objective machinery to meta-harness optimization is presented as a natural extension beyond skill specifications.In that setting, the pipeline structure itself becomes the search target while the execution pipeline is no longer fixed.
  • Limitations: MOCHA is less advantageous on low-conflict tasks, uses a fixed annealing schedule, and measures compliance against one platform’s SKILL.md specification.The paper identifies automatic conflict detection, adaptive schedules, and broader constraint schemas as open directions.
  • Conclusion: 7.5% relative improvement in mean correctness over the strongest baseline was achieved by MOCHA, with gains up to 14.9% on FEVER and 10.4% on TheoremQA.The largest gains occurred where improving correctness conflicted with instruction-body token limits.
  • Multi-objective foundations: Chebyshev scalarization can reach every Pareto-optimal solution, unlike linear scalarization, which can miss non-convex Pareto-front regions.Chebyshev targets a direction-specific solution, while hypervolume contribution rewards candidates expanding under-covered regions.
  • Multi-objective foundations: Hypervolume measures the region of objective space weakly dominated by a solution set and bounded by a reference point.In MOCHA, correctness, description compliance, and body compliance are non-negative maximized objectives with reference point r = 0.
  • Discussion: MOCHA retains GEPA’s mutation and evaluation infrastructure while replacing heuristic candidate selection with principled multi-objective mechanisms.The framework combines Chebyshev exploitation with HVC exploration in an annealed two-phase strategy.

B Implementation Details

MOCHA gates candidates cheaply on minibatches, scores accepted candidates on validation data, and combines HVC exploration with annealed Chebyshev selection under a shared evaluation framework.

  • Two-stage evaluation: MOCHA evaluates parent and candidate on a training minibatch before committing accepted candidates after full validation scoring.Minibatch acceptance filters poor candidates cheaply; validation scores support subsequent parent selection.
  • Hypervolume computation: M = 3 metrics are used throughout: correctness, description compliance, and body compliance.HVC is computed with the exact HSO algorithm in O(n^2 log n).
  • Exploration: During exploration, a capacity-5 priority queue stores non-dominated candidates ranked by HVC until a candidate exceeds the annealing threshold.The highest-impact buffered candidate is then committed, reducing premature commitment to marginal discoveries.
  • Annealing: τ0 = 0.1, τend = 0.0, and λ = 10 define the exponential annealing schedule, making τ(B/2) approximately 0.0007.The threshold is effectively zero by mid-budget.
  • Unified comparison: The unified framework gives all methods identical prompts, evaluation harnesses, and rollout budgets, varying only candidate selection strategy.TextGrad uses greedy acceptance, ProTeGi UCB beam search, GEPA stochastic Pareto selection, and MOCHA Chebyshev scalarization with threshold annealing.

C Additional Experimental Results

All optimizers receive the same SKILL.md mutation interface, compliance constraints, and task feedback; the proposer prioritizes accuracy while preserving field validity and limits.

  • Shared optimization interface: All methods share the same mutation interface, including the complete SkillMdProposer prompt.This design isolates candidate selection rather than mutation feedback as the source of performance differences.
  • Format constraints: The proposer optimizes description length, body length, and valid YAML frontmatter as SKILL.md field constraints.The stated limits are description ≤1,024 characters and body ≤5,000 characters.
  • Mutation inputs: The proposer receives the current skill, compliance status, task-example feedback, and sections flagged for improvement.These inputs are supplied through the current skill, compliance report, feedback text, and components-to-update variables.
  • Mutation objective: The rewrite instruction prioritizes improving task accuracy while respecting field constraints and maintaining valid YAML and section headers.Any field, including the description and body sections, may be modified.
  • Experimental control: Baselines receive the same compliance constraints and per-example correctness signals as MOCHA during mutation.MOCHA’s gains are attributed to candidate selection rather than privileged mutation feedback.

C.2 Per-Task Compliance Analysis

Table 4 reports mean description and body compliance across five seeds, while the accompanying analysis characterizes a correctness–compliance trade-off for MOCHA.

  • Compliance metrics: Mean description and body compliance are reported across 5 seeds for all methods and six skills.Desc. denotes description ≤1,024 characters; Body denotes instruction body ≤5,000 characters.
  • Per-task analysis: MOCHA trades some compliance for correctness, making the multi-objective trade-off explicit and navigable.Baselines maintain high compliance because their selection strategies rarely accept candidates that deviate from the initial SKILL.md template.

C.3 Full Pareto Front Visualization

Across all six skills, MOCHA explores multiple non-dominated correctness–compliance trade-offs, whereas baselines generally remain near one operating point. Its variants span an exploration–exploitation spectrum, with full MOCHA balancing candidate diversity and correctness.

  • Without annealing, MOCHA produces the most candidates; without HVC, it pushes furthest on correctness; full MOCHA balances both.Baselines generally cluster at a single operating point.
  • MOCHA variants consistently explore multiple non-dominated operating points across correctness and body compliance, while baselines remain near the initial prompt.
  • MOCHA explores multiple mutation branches, with best-performing variants often emerging from non-obvious lineages rather than greedy refinement.Evolution trees mark committed skill variants, parent–child mutation paths, and best test correctness.

C.6 Per-Task Qualitative Analysis

MOCHA’s qualitative gains arise from more structured, domain-specific skills that add reasoning protocols, error avoidance, and strict output formatting. Across tasks, these changes range from expert verification procedures to minimal-answer constraints, although HotpotQA shows no meaningful advantage.

  • GPQA: On GPQA, MOCHA replaces GEPA’s 57-token template with a 3,418-token six-step expert verification protocol and domain-specific error checks.MOCHA reaches .636 versus GEPA’s .592, a +4.4pp difference.
  • TheoremQA: On TheoremQA, MOCHA produces a leaner 2,517-token skill with explicit theorem naming, term-by-term matrix operations, and alternative-method verification.Test correctness is .762 versus GEPA’s .656 (+10.6pp).
  • HoVer: On HoVer, MOCHA adds atomic claim decomposition, explicit evidence quoting, an all-or-nothing verdict rule, and checks for entity swaps.
  • HotpotQA: On HotpotQA, MOCHA enforces stricter minimalism, but its .600 versus .602 result is within standard deviation.
  • DebugBench: On DebugBench, MOCHA enumerates bug patterns and mandates surgical fixes that change only buggy lines.
  • MOCHA skills contain domain-specific reasoning protocols, explicit error avoidance, and structured output formatting absent from baseline skills.

C.7 Per-Task Ablation Detail

The ablation results place MOCHA variants on a clear exploration–exploitation spectrum. Pure exploitation often maximizes correctness, while full MOCHA is especially effective where premature convergence is problematic.

  • The w/o HVC variant achieves the highest correctness on 4/6 tasks, consistent with its exploitation-oriented position.
  • Full MOCHA achieves the best or near-best result on HoVer, where annealing avoids the premature convergence observed in w/o Annealing (−4.6pp).
  • HotpotQA remains challenging for all MOCHA variants; ProTeGi’s UCB beam search reaches .622 and outperforms every MOCHA variant.The result suggests this task’s flat objective landscape favors single-objective exploitation.
  • All MOCHA variants substantially outperform all baselines on GPQA, FEVER, and DebugBench, where baselines return the seed unchanged.
  • MOCHA’s evolution trees show committed candidate variants, mutation relationships, and metric breakdowns between root and best nodes.

C.8 Ablation: Hypervolume Heatmap

The task-level comparisons show MOCHA replacing sparse or weak seed templates with structured skills tailored to each benchmark. Its gains are visible across reasoning, verification, question answering, and debugging tasks, while the ablation heatmap separates correctness from Pareto diversity.

  • GPQA: On GPQA, MOCHA replaces a single-line seed template with a six-step expert verification protocol for STEM reasoning.The seed correctness is 0.59; the optimized skill adds domain-specific checks.
  • TheoremQA: On TheoremQA, MOCHA improves correctness from .53 to .82 while producing a lean skill with theorem identification, sign/unit tracking, templates, and strict formatting.
  • HoVer: On HoVer, MOCHA replaces the unchanged seed with a seven-step verification procedure using a SUPPORTED bias and retriever-augmented gap filling.
  • HotpotQA: On HotpotQA, MOCHA improves correctness from .34 to .66 through verbatim extraction rules and explicit formatting examples.
  • DebugBench: On DebugBench, MOCHA develops category-aware bug heuristics and conservative fixing to prevent over-correction on multi-bug inputs.
  • Ablation heatmap: Removing HVC gating shifts toward exploitation, whereas removing annealing shifts toward exploration and produces the highest Pareto diversity.
Loading 2605.19330v1…