First Provable Skill-Selection Algorithm Hits 0.73 Task Success Against 0.20-0.52 for Released Skill Routers, on 28% Fewer Tokens
Current agents pick which skill documents to load by scoring each one independently for semantic relevance and packing greedily or top-k, which the authors show wastes context on redundant skills and can actively degrade performance. They recast selection as maximizing a monotone submodular benefit minus a context penalty under a hard token budget, and give Best Prefix Selection (BPS), a polynomial-time algorithm with a bicriteria (1-1/e, 1) approximation guarantee, the first performance guarantee for skill selection. On a contamination-controlled BigCodeBench variant BPS reaches 0.73 measured task success versus 0.20-0.52 for released skill routers, text retrievers, and the executor's own selection, while using 28% fewer tokens than the strongest released router.
↳ Follow the thread