Selecting complementary LLM skills improves success while reducing context use

A polynomial-time selection algorithm jointly accounts for skill usefulness, redundancy, and token cost, with a provable approximation guarantee.

PaperTop Universitycs.AIarXiv:2608.19993v1 ↗

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

Tsinghua University

Research Digest·23 August 2026·2 min read

Read the paper →

Thread:Skill Selection for Agents

Chen et al. formulate the choice of reusable skill documents for LLM agents as a budget-constrained optimization problem rather than an independent relevance-ranking task. Their Best Prefix Selection algorithm achieved 0.73 task success on a contamination-controlled BigCodeBench variant, compared with 0.20–0.52 for existing selection methods, while using fewer tokens than the strongest released router.

What they did

The authors model the value of a selected skill set as a monotone submodular function, meaning that skills remain useful but provide diminishing returns when they overlap with already selected material. Selection must fit within a hard context-token budget, and the objective subtracts a penalty for context use.

They develop Best Prefix Selection (BPS), a polynomial-time algorithm for this objective, and evaluate it on a contamination-controlled variant of BigCodeBench. Comparisons include released skill routers, text retrieval systems, and the executor LLM’s own skill-selection strategy.

Key findings

BPS attained 0.73 measured task success, versus 0.20–0.52 across the evaluated baselines.
It used 28% fewer tokens than the strongest released skill router.
The authors prove a bicriteria guarantee of (1−1/e, 1): roughly a 63.2% coefficient on the modeled submodular benefit while retaining the full context-penalty term.
They show that the 1−1/e benefit coefficient is optimal for polynomial-time algorithms under the problem’s stated complexity assumptions.

Why it matters

Skill retrieval is often treated as a ranking problem, even though independently relevant documents can be redundant when combined. This work provides a set-level, cost-aware formulation that can choose complementary capabilities under a fixed context window and offers a formal performance guarantee absent from top-k and greedy packing approaches.

Caveats

The empirical evidence comes from one contamination-controlled coding benchmark, so it is unclear whether the gains extend to other tasks, skill formats, context sizes, or agent architectures. The theorem also depends on benefit being monotone and submodular; real LLM behavior may include harmful interactions or complementarities that violate those assumptions, and measured task success does not by itself establish that the model accurately captures execution outcomes.

Analysis

The paper connects LLM context management with classical submodular optimization, where diminishing returns provide both a natural model of redundant documents and tractable approximation guarantees. Its strongest contribution is the combination of an explicit set-level objective, a token-aware algorithm, and a theorem matching the standard 1−1/e computational barrier.

A central open question is whether useful skill interactions are reliably submodular in practice. If some skills become valuable only when loaded together, future selectors may need models that capture complementarities without losing computational tractability.