Everything K-culture — comebacks to K-beauty, straight to your inboxGet it in your inbox

METAL MEDIA

Optimal Skill Selection for LLM Agents with Provable Bicriteria Guarantees

arXiv:2608.199932026-08-21

A method that picks which 'skill documents' to feed an AI coding agent, with mathematically guaranteed near-optimal results

Coding agents like Codex or Claude Code load reusable 'skill documents' into their limited context window to gain task-specific abilities, but current systems just score each skill independently and pack in the top matches, letting redundant skills waste tokens or even hurt performance. The researchers modeled skill selection as an optimization problem that balances covering needed capabilities against context cost under a token budget, and built a polynomial-time algorithm called Best Prefix Selection (BPS) with the first proven performance guarantee for this task. On a contamination-controlled coding benchmark, BPS reached 0.73 measured task success, beating existing skill routers, text retrievers, and the agent's own selection (0.20-0.52), while using 28% fewer tokens than the strongest existing router.

METAL MEDIA explanatory visual

A method that picks which 'skill documents' to feed an AI coding agent, with mathematically guaranteed near-optimal results

  1. 01Coding agents choose skill documents from a library to load into an LLM's limited context window, but current methods score skills independently and use top-k or greedy packing with no guarantee of quality or cost control
  2. 02The researchers built a structured objective: each skill supplies latent 'capabilities,' each query demands certain capabilities, overlapping supply of the same capability gives diminishing returns, while covering different capabilities complements each other -- and this benefit is offset by a token-length penalty
  3. 03They designed BPS, an algorithm that enumerates small seed sets, greedily grows each into a chain by adding the item with best benefit-per-token, records every intermediate combination along the way, and picks the best one overall
  4. 04They proved a bicriteria approximation guarantee in polynomial time: the algorithm captures at least (1-1/e) of the achievable benefit while paying no more than the full token penalty (a coefficient of 1) -- the best possible benefit ratio achievable in polynomial time
  5. 05Trained only on pass/fail execution outcomes, the fitted model correctly recovered the hidden skill-capability mapping (99.6% accuracy), and on a contamination-controlled BigCodeBench variant, BPS achieved 0.73 success versus 0.20-0.52 for existing baselines
An explanatory diagram made by METAL MEDIA, not a figure supplied by the paper's authors.

What they did

  1. Coding agents choose skill documents from a library to load into an LLM's limited context window, but current methods score skills independently and use top-k or greedy packing with no guarantee of quality or cost control
  2. The researchers built a structured objective: each skill supplies latent 'capabilities,' each query demands certain capabilities, overlapping supply of the same capability gives diminishing returns, while covering different capabilities complements each other -- and this benefit is offset by a token-length penalty
  3. They designed BPS, an algorithm that enumerates small seed sets, greedily grows each into a chain by adding the item with best benefit-per-token, records every intermediate combination along the way, and picks the best one overall
  4. They proved a bicriteria approximation guarantee in polynomial time: the algorithm captures at least (1-1/e) of the achievable benefit while paying no more than the full token penalty (a coefficient of 1) -- the best possible benefit ratio achievable in polynomial time
  5. Trained only on pass/fail execution outcomes, the fitted model correctly recovered the hidden skill-capability mapping (99.6% accuracy), and on a contamination-controlled BigCodeBench variant, BPS achieved 0.73 success versus 0.20-0.52 for existing baselines
Figure 1: Top: The common skill-selection paradigm for coding agents: given a task, the system selects skills from a library and provides them to a frozen LLM executor. Bottom: Effective skill selection depends on capability composition rather than individual relevance. The LLM executor benefits from skill sets that cover the required capabilities, while redundant and irrelevant skills consume context budget with little or negative utility.
Figure 1: Top: The common skill-selection paradigm for coding agents: given a task, the system selects skills from a library and provides them to a frozen LLM executor. Bottom: Effective skill selection depends on capability composition rather than individual relevance. The LLM executor benefits from skill sets that cover the required capabilities, while redundant and irrelevant skills consume context budget with little or negative utility.
tj∈argmaxi∈T∖{t1,⋯,tj−1}G^​(i∣{t1,⋯,tj−1}),(13)
mj:=G^(tj∣{t1,⋯,tj−1}),∀j∈[|T|].
Figure 2: Parameter recovery. Top: the true skill-capability coverage matrix, hidden from the fit. Bottom: the fitted supply u^i,k, learned from pass/fail outcomes alone; its latent dimensions carry no names, so they are matched to the capabilities by the best permutation. Columns are the 31 skills, rows the 5 capabilities. Both panels use the scale on the right, white =0 to dark blue =1; the bottom panel plots u^i,k divided by its largest entry.
Figure 2: Parameter recovery. Top: the true skill-capability coverage matrix, hidden from the fit. Bottom: the fitted supply u^i,k, learned from pass/fail outcomes alone; its latent dimensions carry no names, so they are matched to the capabilities by the best permutation. Columns are the 31 skills, rows the 5 capabilities. Both panels use the scale on the right, white =0 to dark blue =1; the bottom panel plots u^i,k divided by its largest entry.

Why it matters

As skill/tool libraries for AI agents keep growing, choosing which items to load into limited context has become a first-order bottleneck for both accuracy and cost, and this work is the first to explain why naive top-k relevance scoring fails and to offer a selection algorithm with a provable guarantee. Anyone building agent frameworks can use this principle to cut wasted context while boosting task success.

Figure 4: Value-model comparison. Left: pairwise ranking accuracy on held-out set pairs, under the extrapolation (filled dots) and unseen-doc (open dots) protocols. Right: measured success of the sets each model selects; the dashed line is the empirical ceiling, the best set per instance in hindsight.
Figure 4: Value-model comparison. Left: pairwise ranking accuracy on held-out set pairs, under the extrapolation (filled dots) and unseen-doc (open dots) protocols. Right: measured success of the sets each model selects; the dashed line is the empirical ceiling, the best set per instance in hindsight.

Terms in this paper

  • skill document · a reusable instruction file that teaches an LLM agent how to perform a specific task
  • context window · the maximum amount of text (tokens) an LLM can process at once
  • submodular function · a function where adding a new item gives diminishing extra benefit as more similar items are already selected
  • bicriteria approximation · a guarantee that bounds two different objectives (here, benefit and cost) with separate approximation ratios
  • knapsack constraint · a limit requiring choices to fit within a fixed budget, like packing a bag with a weight limit
Figure 5: The 80 selection instances. Left: optimization quality. Every rule is given the same fitted objective; bars are the share of instances on which a rule attains the exact optimum, found by exhaustive search over every feasible set, and the right-hand column is its mean shortfall in objective value. Right: end-to-end selection. Each rule is placed by the tokens it injects and the measured success of the sets it chooses; up and to the left is better. Both of our points run BPS and differ only in how the objective’s encoders are instantiated.
Figure 5: The 80 selection instances. Left: optimization quality. Every rule is given the same fitted objective; bars are the share of instances on which a rule attains the exact optimum, found by exhaustive search over every feasible set, and the right-hand column is its mean shortfall in objective value. Right: end-to-end selection. Each rule is placed by the tokens it injects and the measured success of the sets it chooses; up and to the left is better. Both of our points run BPS and differ only in how the objective’s encoders are instantiated.

Original abstract (English)

Loading reusable skill documents into a bounded context window is now the primary way large language model (LLM) agents acquire task-specific capabilities, which makes skill selection a first-order determinant of task performance and token cost. Yet current agents score skills independently by semantic relevance and assemble the set by top-$k$ or greedy packing, with no quality guarantee or cost awareness on the selected set. As a result, redundant or poorly chosen skills waste scarce context tokens and can even degrade performance. We give the first model of how the selected skill set shapes execution outcomes and cast skill selection as an optimization problem: choose a skill set under a hard token budget to maximize a monotone submodular benefit minus context penalty. For this problem, we develop Best Prefix Selection (BPS), a polynomial-time algorithm, and prove, to our knowledge, the first performance guarantee for skill selection: a bicriteria $(1-1/e,1)$ approximation whose benefit coefficient is optimal in polynomial time. On a contamination-controlled BigCodeBench variant, BPS outperforms all the baselines, reaching $0.73$ measured task success versus $0.20$--$0.52$ for released skill routers, text retrievers, and the executor's own selection, on $28\%$ fewer tokens than the strongest released router.

Authors · Yu Chen, Ruishuo Chen, Xun Wang, Zhuoran Li, Longbo Huang

Read on arXiv

Latest papers

All papers →

Latest from METAL MEDIA

Figures: Yu Chen et al., arXiv:2608.19993, cc-by-nc-sa-4.0