每天早上一封邮件，把昨天的 AI 梳理好订阅邮件

METAL LAB

Optimal Skill Selection for LLM Agents with Provable Bicriteria Guarantees

arXiv:2608.199932026-08-21

让AI编程智能体挑选该装入哪些技能文档,并从数学上保证接近最优的方法

像Codex或Claude Code这样的编程智能体在执行任务时,会把预先写好的技能文档装入容量有限的上下文窗口来获得特定能力,但现有做法只是给每个技能单独打相关性分数、取前几名塞进去,导致重复或无关的技能白白占用宝贵的token空间,甚至拖累表现。研究团队把技能选择重新定义为一个优化问题:在固定的token预算内,最大化覆盖任务所需能力带来的收益,同时扣除上下文长度的代价,并提出了一个多项式时间算法Best Prefix Selection(BPS),首次给出了这类问题可证明的性能保证。在一个经过污染控制的编程基准测试中,BPS的任务成功率达到0.73,超过了现有的技能路由器、文本检索器和智能体自身选择方式(0.20到0.52),同时比表现最强的现有路由器少用28%的token。

他们做了什么

  1. 编程智能体需要从技能库中挑选文档装入LLM有限的上下文窗口,但现有方法对每个技能独立打分、用取前几名或贪心打包的方式组合,无法保证选出的集合质量或控制成本
  2. 研究团队构建了一个结构化目标函数:每个技能在若干潜在能力维度上提供供给,每个查询在这些维度上有需求,同一能力维度的重复供给收益递减,而覆盖不同能力维度则互补增益,这个收益再减去与token长度成正比的代价
  3. 他们设计了BPS算法,先枚举少量种子组合,再按每token收益最高的贪心方式逐步扩展成链条,并记录链条上出现过的每一个可行子集,最后从中选出目标函数值最高的那个
  4. 研究证明了该算法在多项式时间内达到一种双准则近似保证:收益方面至少达到最优解的(1-1/e)比例,而代价方面完全不打折扣(系数为1),其中收益系数(1-1/e)已是多项式时间算法能达到的最优水平
  5. 仅用任务成功与否的执行记录拟合模型,就能以99.6%的准确率还原出隐藏的技能-能力对应关系;在污染控制的BigCodeBench变体测试中,BPS取得0.73的成功率,远超现有基线方法的0.20至0.52
Figure 1: Top: The common skill-selection paradigm for coding agents: given a task, the system selects skills from a library and provides them to a frozen LLM executor. Bottom: Effective skill selection depends on capability composition rather than individual relevance. The LLM executor benefits from skill sets that cover the required capabilities, while redundant and irrelevant skills consume context budget with little or negative utility.
Figure 1: Top: The common skill-selection paradigm for coding agents: given a task, the system selects skills from a library and provides them to a frozen LLM executor. Bottom: Effective skill selection depends on capability composition rather than individual relevance. The LLM executor benefits from skill sets that cover the required capabilities, while redundant and irrelevant skills consume context budget with little or negative utility.
tj∈argmaxi∈T∖{t1,⋯,tj−1}G^​(i∣{t1,⋯,tj−1}),(13)
mj:=G^(tj∣{t1,⋯,tj−1}),∀j∈[|T|].
Figure 2: Parameter recovery. Top: the true skill-capability coverage matrix, hidden from the fit. Bottom: the fitted supply u^i,k, learned from pass/fail outcomes alone; its latent dimensions carry no names, so they are matched to the capabilities by the best permutation. Columns are the 31 skills, rows the 5 capabilities. Both panels use the scale on the right, white =0 to dark blue =1; the bottom panel plots u^i,k divided by its largest entry.
Figure 2: Parameter recovery. Top: the true skill-capability coverage matrix, hidden from the fit. Bottom: the fitted supply u^i,k, learned from pass/fail outcomes alone; its latent dimensions carry no names, so they are matched to the capabilities by the best permutation. Columns are the 31 skills, rows the 5 capabilities. Both panels use the scale on the right, white =0 to dark blue =1; the bottom panel plots u^i,k divided by its largest entry.

为什么重要

随着AI智能体所用的技能库/工具库越来越庞大,该往有限上下文里装什么已成为决定任务表现和成本的关键瓶颈,这项研究首次解释了简单的相关性排序为何会失败,并给出了首个有理论保证的选择算法。对于开发智能体框架的人来说,这一原理可以在减少上下文浪费的同时提高任务成功率。

Figure 4: Value-model comparison. Left: pairwise ranking accuracy on held-out set pairs, under the extrapolation (filled dots) and unseen-doc (open dots) protocols. Right: measured success of the sets each model selects; the dashed line is the empirical ceiling, the best set per instance in hindsight.
Figure 4: Value-model comparison. Left: pairwise ranking accuracy on held-out set pairs, under the extrapolation (filled dots) and unseen-doc (open dots) protocols. Right: measured success of the sets each model selects; the dashed line is the empirical ceiling, the best set per instance in hindsight.

本文术语

  • 技能文档(skill document) · 教会LLM智能体如何完成特定任务的可复用说明文件
  • 上下文窗口(context window) · LLM一次能处理的最大文本量,以token计量
  • 次模函数(submodular function) · 已选项目越多,新增项目带来的边际收益就越小的一类函数
  • 双准则近似(bicriteria approximation) · 同时对两个不同目标(这里是收益和成本)分别给出近似比例保证的方法
  • 背包约束(knapsack constraint) · 要求所选内容总量不超过固定预算的限制,类似往有限承重的背包里装东西
Figure 5: The 80 selection instances. Left: optimization quality. Every rule is given the same fitted objective; bars are the share of instances on which a rule attains the exact optimum, found by exhaustive search over every feasible set, and the right-hand column is its mean shortfall in objective value. Right: end-to-end selection. Each rule is placed by the tokens it injects and the measured success of the sets it chooses; up and to the left is better. Both of our points run BPS and differ only in how the objective’s encoders are instantiated.
Figure 5: The 80 selection instances. Left: optimization quality. Every rule is given the same fitted objective; bars are the share of instances on which a rule attains the exact optimum, found by exhaustive search over every feasible set, and the right-hand column is its mean shortfall in objective value. Right: end-to-end selection. Each rule is placed by the tokens it injects and the measured success of the sets it chooses; up and to the left is better. Both of our points run BPS and differ only in how the objective’s encoders are instantiated.

论文原文摘要（英文）

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.

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

在 arXiv 阅读

最新论文

全部论文 →

METAL LAB 最新报道

图片来源： Yu Chen et al., arXiv:2608.19993, cc-by-nc-sa-4.0