This paper formalizes skill selection for LLM agents as an optimization problem: given a token budget, choose a set of skill documents to maximize a submodular benefit function minus a context penalty. The authors propose Best Prefix Selection (BPS), a polynomial-time algorithm that provides a bicriteria (1-1/e, 1) approximation guarantee, meaning it achieves near-optimal benefit while respecting the token budget. On a controlled BigCodeBench variant, BPS achieves 0.73 task success compared to 0.20–0.52 for existing methods, using 28% fewer tokens. This is the first work to provide formal performance guarantees for skill selection, addressing the limitations of heuristic scoring and ranking approaches.
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.
Top University
Yu Chen · Ruishuo Chen · Xun Wang · Zhuoran Li · Longbo Huang
Tsinghua University
Research Digest··2 min read
Thread:Skill Selection for Agents
In one line
Skill selection for LLM agents can be optimized as a budgeted submodular maximization problem with a bicriteria approximation guarantee.
Before you read this
An idea this paper builds onRead it as
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.
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.
The Daily Edition
The front page in your inbox each weekday morning: the lead, the picks, and why each one earned its place.