Three skill optimizers stall at zero on 4 of 6 tasks — Chebyshev scalarization unsticks them

Notes on MOCHA: Multi-Objective Chebyshev Annealing for Agent Skill Optimization (arXiv:2605.19330) — Mahmud Tanjim, Jayakumar Subramanian, Xiang Chen, B. Kveton, Subhojyoti Mukherjee, Anlan Zhang, Sungchul Kim, Somdeb Sarkhel, S. Choudhury · May 2026

Note published July 25, 2026 · written by SkillFed’s research pipeline from the paper above · how these notes are made

Agent skills aren't single prompts — they're multi-field specs bound by hard platform limits: a description field truncated at 1,024 characters for routing, an instruction body capped at 5,000 characters and chopped down further via progressive disclosure, and a context budget shared with whatever other skills are co-resident. Optimizing a skill means hitting several of these targets at once, not just raising one accuracy score. Prior prompt optimizers dodge that reality — they either ignore the constraints outright or collapse performance and compliance into a single weighted number, which throws away any solution sitting in a non-convex fold of the trade-off surface. MOCHA replaces that weighted sum with Chebyshev scalarization: minimize the worst weighted gap to an ideal point, a formulation that reaches every point on the Pareto front, non-convex regions included. An exponential annealing schedule rides on top, letting the search roam broadly early and lock onto a specific trade-off direction as the budget runs out.

Across six skills — GPQA and TheoremQA for reasoning, HoVer, HotpotQA and FEVER for multi-hop QA and fact verification, and DebugBench for code debugging — three established optimizers (TextGrad, ProTeGi, GEPA) burned 1,000 rollouts each and handed back the untouched seed skill on 4 of the 6 tasks. Zero measurable progress. MOCHA improved every task: a mean correctness of .675 against .628 for the strongest baseline (ProTeGi), a 7.5% relative gain that reached 14.9% on FEVER and 10.4% over the runner-up on TheoremQA. It also surfaced roughly twice as many Pareto-optimal skill variants on average — 3.6 versus 1.6 — with a higher 3-D hypervolume, meaning it hands back more usable trade-off points, not just one better one.