Optimal Skill Selection for LLM Agents with Provable Bicriteria Guarantees

LLM agent 从技能库加载文档到有限 context：独立语义评分 + top-k 贪婪装填，无质量保证也无成本控制

将技能选择形式化为有上下文约束的双目标优化，给出可证 bicriteria 近似保证的选择算法

在性能保证和 token 成本双指标上严格优于贪婪 top-k；理论保证在实验中得到验证

大型技能库的实时 agent 中，技能选择效率直接影响响应延迟和可靠性

Loading reusable skill documents into a bounded context window is now the primary way large language model (LLM) agents acquire task-specific capabilities, which makes skill selection a first-order determinant of task performance and token cost. Yet current agents score skills independently by semantic relevance and assemble the set by top-$k$ or greedy packing, with no quality guarantee or cost awareness on the selected set. As a result, redundant or poorly chosen skills waste scarce context tokens and can even degrade performance. We give the first model of how the selected skill set shapes execution outcomes and cast skill selection as an optimization problem: choose a skill set under a hard token budget to maximize a monotone submodular benefit minus context penalty. For this problem, we develop Best Prefix Selection (BPS), a polynomial-time algorithm, and prove, to our knowledge, the first performance guarantee for skill selection: a bicriteria $(1-1/e,1)$ approximation whose benefit coefficient is optimal in polynomial time. On a contamination-controlled BigCodeBench variant, BPS outperforms all the baselines, reaching $0.73$ measured task success versus $0.20$--$0.52$ for released skill routers, text retrievers, and the executor's own selection, on $28\%$ fewer tokens than the strongest released router.