Optimal Skill Selection for LLM Agents with Provable Bicriteria Guarantees

TL;DR - This paper formulates context-budgeted skill selection for LLM agents as submodular optimization and introduces Best Prefix Selection (BPS), a polynomial-time algorithm with a provably optimal bicriteria approximation. BPS substantially improves task success while using fewer tokens than the strongest released router tested.

• Models skill selection as maximizing monotone submodular benefit minus context penalty under a hard token budget.
• Proves BPS achieves a bicriteria ((1-1/e, 1)) approximation, with a benefit coefficient that is optimal in polynomial time.
• On a contamination-controlled BigCodeBench variant, BPS reaches 0.73 task success versus 0.20–0.52 for skill routers, text retrievers, and executor-based selection.
• BPS uses 28% fewer tokens than the strongest released router.