MOCHA: Multi-Objective Chebyshev Annealing for Agent Skill Optimization

summary

The gist

MOCHA introduces Multi-Objective Chebyshev Annealing for Agent Skill Optimization, a framework that addresses the inherent trade-offs between task performance and platform constraints in skill

In short

MOCHA optimizes LLM agent skills by treating them as multi-objective problems, balancing task performance and platform constraints. It uses Multi-Objective Chebyshev Annealing to navigate complex trade-offs, finding superior skill variants that existing single-objective methods fail to discover. This leads to significant accuracy gains across diverse tasks.

Key concepts

Skill Optimization: This is the process of refining the structured natural language specifications (skills) that govern how an LLM agent reasons and responds. It is a multi-objective problem because optimizing for better performance might conflict with platform limits like context window size or description length.
Chebyshev Scalarization: This technique scores a skill by measuring its worst-case weighted shortfall from a perfect skill. By using random weights, it can select any skill on the Pareto front, allowing the optimizer to explore trade-offs that average methods would ignore, effectively covering non-convex regions.
Pareto Front: The Pareto front represents the set of optimal skills where no objective (like accuracy) can be improved without sacrificing another objective (like compliance or economy). MOCHA aims to discover and expand this front, finding multiple skill variants that are all mutually superior in different ways.

Terminology used across episodes

Reinforcement Learning (RL) — explained in 25 episodes
Sample Complexity — explained in 19 episodes
Federated Learning — explained in 17 episodes
Retrieval-Augmented Generation (RAG) — explained in 17 episodes
Quantum Fisher Information (QFI) — explained in 16 episodes
Interpretability — explained in 15 episodes

This episode discusses

The paper

MOCHA: Multi-Objective Chebyshev Annealing for Agent Skill Optimization · Read on arXiv

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

Adobe Research

LLM agents organize behavior through skills -- structured natural-language specifications that govern how an agent reasons, retrieves, and responds. Unlike monolithic prompts, skills are multi-field artifacts with platform limits: descriptions are indexed for routing, instruction bodies are loaded into a shared context window, and every extra line costs the agent context it could spend elsewhere. Skill optimization is therefore inherently multi-objective: a skill should be accurate and economical at once. Existing prompt optimizers collapse these goals into a single score, and we find that this makes them stall: in most of their runs, 1000 rollouts yield zero progress over the seed skill. We introduce MOCHA (Multi-Objective CHebyshev Annealing), which selects skills to improve by Chebyshev scalarization and accepts improvements that expand the Pareto front, annealing from exploration to exploitation. Chebyshev scalarization scores a skill by its largest weighted shortfall from a perfect skill; with random weights, it can select any skill on the Pareto front for improvement, including trade-offs that an average would never favor. Across six diverse skills and two models, MOCHA escapes the seed in nearly every run, achieving 7.9% higher mean accuracy than the strongest baseline (up to 23.7% on DebugBench with GPT 5.5 and 14.9% on FEVER with Claude Haiku 4.5) while discovering Pareto fronts with the highest hypervolume and nearly twice as many Pareto-optimal skills.

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: Today's paper: "MOCHA: Multi-Objective Chebyshev Annealing for Agent Skill Optimization".

Jane: MOCHA introduces Multi-Objective Chebyshev Annealing for Agent Skill Optimization,

Tom: First, who's behind it and why it matters.

Paper summary: Jane: So, wrapping up this discussion on "MOCHA: Multi-Objective Chebyshev Annealing for Agent Skill Optimization," the authors are really saying that skill optimization is fundamentally a structured multi-objective problem that requires principled Pareto front navigation because those objective regions can be non-convex >

Tom: They introduce MOCHA by using Chebyshev scalarization to cover the whole Pareto front, which they claim allows them to select skills in a way that expands the Pareto front >

Lu: The implication is that we should stop looking at single-objective optimization methods for skill refinement and start using techniques like MOCHA that handle trade-offs between accuracy and platform compliance directly >

Meng: From my side, it means we need to think about how to deploy these skills. If you can find twice as many Pareto-optimal variants, that gives you more knobs to tune your agent without worrying about breaking the constraints >

Jane: It’s about moving from finding one "best" skill to discovering a whole set of good trade-offs that fit your specific context >

Tom: The paper shows that MOCHA achieves a seven point five percent relative improvement in mean correctness over the strongest baseline, with gains up to fourteen point nine percent on FEVER and ten point four percent on TheoremQA where objective conflict is strongest >

Lu: The authors point out that their method doesn't provide some kind of magic fix for every problem, they are looking toward adaptive annealing and meta-harness optimization as next steps >

Jane: That's the direction they suggest, moving toward a system that can adapt its skill optimization strategy based on what it’s seeing in real-time >

Conclusion: Tom: So, we’re wrapping up on MOCHA and how it works as a way to improve agent skills >

Jane: Right, so we’ve seen how this method uses Chebyshev scalarization to navigate those multi-objective regions where performance and platform constraints clash >

Tom: Yeah, the authors are showing that most existing optimizers just stall after a thousand runs, meaning they don't actually escape the initial skill choice on four out of six tasks >

Jane: So what does this mean for us listening? It suggests that instead of trying to find one single perfect skill, we should be looking at discovering a whole set of good trade-offs >

Tom: Exactly. The paper claims MOCHA finds twice as many Pareto-optimal skills compared to the previous methods, which is significant because it gives you more options for tuning your agent >

Jane: And the numbers are pretty solid too. They report a seven point five percent relative improvement in mean correctness over the strongest baseline across those six different skills >

Tom: That’s not just some small tweak; that’s a measurable gain on real tasks, especially when things get really tough like on FEVER or TheoremQA where the instruction length pushes against token limits >

Jane: So, it seems like the core idea is using this structured optimization to handle those conflicts directly rather than letting single-objective scores just collapse everything into one narrow path >

More episodes

← Home