Optimal Skill Selection for LLM Agents with Provable Bicriteria Guarantees

📄 arXiv: 2608.19993v1 📥 PDF

作者: Yu Chen, Ruishuo Chen, Xun Wang, Zhuoran Li, Longbo Huang

分类: cs.AI

发布日期: 2026-08-20

💡 一句话要点

提出最佳前缀选择算法以优化LLM代理的技能选择

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 技能选择 大型语言模型 优化算法 任务成功率 上下文令牌 子模优化 性能保证

📋 核心要点

  1. 现有的LLM代理在技能选择上存在独立评分和缺乏质量保证的问题，导致冗余或不当选择浪费上下文令牌。
  2. 本文提出将技能选择视为优化问题，设计了最佳前缀选择（BPS）算法，以在令牌预算内最大化效益。
  3. 实验结果显示，BPS在任务成功率和令牌使用效率上均显著优于现有的技能路由器和文本检索器。

📝 摘要（中文）

在当前大型语言模型（LLM）代理中，加载可重用技能文档是获取任务特定能力的主要方式。然而，现有方法仅通过语义相关性独立评分技能，缺乏对所选技能集的质量保证和成本意识。本文将技能选择视为一个优化问题，提出在硬性令牌预算下选择技能集以最大化单调子模益处减去上下文惩罚。我们开发了最佳前缀选择（BPS）算法，并首次证明了技能选择的性能保证，达到了多项式时间内的$(1-1/e,1)$近似。实验结果表明，BPS在控制污染的BigCodeBench变体上超越了所有基线，任务成功率达到$0.73$，使用的令牌比最强的已发布路由器少$28 ext{%}$。

🔬 方法详解

问题定义：本文解决的是在有限的上下文令牌预算下，如何有效选择技能集以优化任务执行结果的问题。现有方法仅依赖语义相关性评分，缺乏对技能选择质量的控制，导致性能下降和资源浪费。

核心思路：论文的核心思路是将技能选择建模为一个优化问题，通过最大化单调子模益处减去上下文惩罚，来确保所选技能集的有效性和经济性。

技术框架：整体架构包括技能评分、技能选择和执行三个主要模块。首先，通过语义相关性对技能进行评分，然后在令牌预算限制下选择最佳技能集，最后执行任务并评估结果。

关键创新：最重要的技术创新在于提出了最佳前缀选择（BPS）算法，并首次提供了技能选择的性能保证，达到了$(1-1/e,1)$的近似效果，这是现有方法所未实现的。

关键设计：BPS算法的设计包括对技能的单调性和子模性进行利用，采用多项式时间复杂度的优化策略，确保在实际应用中能够高效运行。

🖼️ 关键图片

fig_0
fig_1

📊 实验亮点

实验结果表明，BPS算法在控制污染的BigCodeBench变体上实现了$0.73$的任务成功率，相较于其他已发布的技能路由器和文本检索器（成功率为$0.20$至$0.52$）有显著提升，同时使用的令牌数量减少了$28 ext{%}$，展示了其优越的性能。

🎯 应用场景

该研究的潜在应用领域包括智能助手、自动化客服和任务导向的对话系统等。通过优化技能选择，能够显著提升LLM代理在特定任务中的表现，降低资源消耗，具有重要的实际价值和广泛的应用前景。

📄 摘要（原文）

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.