提出首个有理论保证的技能选择算法，兼顾任务成功率与上下文开销。
Optimal Skill Selection for LLM Agents with Provable Bicriteria Guarantees
- 将技能选择建模为带约束的优化问题，平衡收益与上下文成本。
- 在少28%令牌下达成0.73成功率，显著优于现有方法（最高0.52）。
- 首次提供可证明的双目标近似保证，适合高精度任务部署场景。
将可复用的技能文档加载到有限上下文窗口，已成为大型语言模型（LLM）代理获取特定能力的主要方式，使技能选择成为任务性能与令牌成本的关键因素。然而，当前代理通过语义相关性独立评分技能，并采用顶-k或贪心打包组合，缺乏对所选集合的质量保障或成本意识。这导致冗余或低效技能浪费珍贵的上下文令牌，甚至降低性能。本文首次建立技能集如何影响执行结果的模型，将技能选择视为优化问题：在硬性令牌预算下，最大化单调子模收益减去上下文惩罚。针对此问题，提出多项式时间算法最佳前缀选择（BPS），并首次证明了技能选择的性能保证：双目标(1-1/e,1)近似，其中收益系数在多项式时间内最优。在受控污染的BigCodeBench变体上，BPS超越所有基线，在仅使用最强释放路由器28%的令牌情况下，达到0.73的任务成功率，而基线表现仅为0.20–0.52。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。