Optimal Skill Selection for LLM Agents with Provabl... | AI Research

Optimal Skill Selection for LLM Agents with Provable Bicriteria Guarantees introduces a formal framework to improve how LLM agents choose which external skill documents to load into their limited context windows. By treating skill selection as a mathematical optimization problem rather than a simple ranking task, the researchers provide a way to maximize task performance while minimizing token costs and avoiding redundant information.

The Problem with Current Selection

Modern LLM agents typically select skills by scoring them individually based on semantic relevance and then using heuristics like top-k or greedy packing. The authors, Yu Chen, Ruishuo Chen, Xun Wang, Zhuoran Li, and Longbo Huang, argue that these methods fail because they ignore the "set-level" nature of the problem. Selecting skills is not just about individual relevance; it involves managing capability overlap, complementarity, and the hard constraint of a finite context window. When agents select the wrong combination of skills, they waste tokens and can even degrade performance compared to using no skills at all.

The Best Prefix Selection (BPS) Algorithm

The researchers developed Best Prefix Selection (BPS), a polynomial-time algorithm designed to solve this selection problem. They model the process as a regularized submodular maximization task. In this model:

• Benefit: A monotone submodular function captures how skills provide specific capabilities, accounting for diminishing returns when multiple skills cover the same capability.

• Penalty: A linear penalty accounts for the performance degradation caused by excessive context length.

• Constraint: A hard token budget limits the total size of the selected skill set.
  BPS provides a bicriteria (1-1/e, 1) approximation, which the authors state is the first performance guarantee for skill selection. This means the algorithm achieves an optimal benefit coefficient in polynomial time while strictly adhering to the token budget.

Performance and Results

The authors tested BPS on a contamination-controlled variant of the BigCodeBench benchmark. Their results indicate that BPS outperformed existing methods—including standard skill routers and text retrievers—by achieving a 0.73 task success rate compared to the 0.20–0.52 range of the baselines. Additionally, BPS achieved these results while using 28% fewer tokens than the strongest released router. The researchers also demonstrated that their model could accurately recover latent skill-capability relationships from execution records alone, correctly ranking covered capability pairs over uncovered ones with an AUC of 0.996.

Key Considerations

The effectiveness of this approach relies on the accuracy of the fitted objective function. The authors note that the "fitting error" between their model and the true execution outcomes can impact selection quality. While they provide a proposition showing that this error transfers to selection regret, the practical utility of the system depends on the ability to calibrate the model using execution records. The framework assumes a fixed executor, meaning the parameters must be learned specifically for the model being used to ensure the structured objective remains valid.