매일 아침, 어제의 AI를 한 통으로 정리해 보내드립니다메일로 받아보기

METAL LAB

Optimal Skill Selection for LLM Agents with Provable Bicriteria Guarantees

arXiv:2608.199932026-08-21

AI 에이전트에게 어떤 '스킬 문서'를 몇 개나 줘야 잘 작동하는지, 수학적으로 최적해를 보장하며 골라주는 방법

Codex나 Claude Code 같은 코딩 에이전트는 작업을 시킬 때 미리 만들어둔 '스킬 문서'(사용법 설명서 같은 것)를 한정된 컨텍스트 창에 넣어주는데, 지금까지는 각 스킬을 개별적으로 관련성 점수 매겨서 상위 몇 개만 넣는 식이라 겹치는 스킬이 토큰만 낭비하거나 오히려 성능을 떨어뜨리는 문제가 있었다. 연구팀은 스킬 선택을 '토큰 예산 안에서 필요한 능력을 최대한 커버하되 겹치는 건 줄이고 문맥 비용은 빼는' 최적화 문제로 정식화하고, 이를 다항시간 안에 푸는 Best Prefix Selection(BPS) 알고리즘을 제시해 이론적으로 증명된 근사 보장을 처음 확보했다. 오염 통제된 코딩 벤치마크 실험에서 BPS는 성공률 0.73을 기록해 기존 스킬 라우터·검색기·에이전트 자체 선택(0.20~0.52)을 앞섰고, 토큰도 가장 강력한 기존 라우터보다 28% 적게 썼다.

무엇을 했나

  1. 코딩 에이전트가 작업을 풀 때 라이브러리에서 필요한 스킬 문서를 골라 LLM의 제한된 컨텍스트 창에 넣는데, 기존 방식은 스킬을 하나씩 독립적으로 점수 매겨 상위 k개나 그리디 방식으로 채워 넣어 품질이나 비용을 보장하지 못했다
  2. 연구팀은 각 스킬이 잠재적인 '능력(capability)'을 얼마나 공급하는지, 쿼리가 어떤 능력을 요구하는지를 모델링해 겹치는 능력은 체감 효과가 줄고 서로 다른 능력을 보완하면 이득이 커지는 구조로 '이득에서 토큰 비용을 뺀' 목적함수를 만들었다
  3. 이 목적함수를 정해진 토큰 예산 안에서 최대화하는 문제로 정식화하고, 후보 조합을 부분적으로만 탐색하면서 밀도(토큰당 이득) 기준으로 그리디하게 확장한 뒤 지나온 모든 중간 조합 중 최선을 고르는 BPS 알고리즘을 설계했다
  4. 이론적으로 이득 측면에서 최적 근사 비율인 (1-1/e)를, 비용 측면에서는 손실 없는 근사(1)를 동시에 만족하는 바이크라이테리아(두 기준) 근사 보장을 다항시간 안에 증명했으며, 이는 이 종류의 문제에서 알려진 것 중 가장 강력한 보장이다
  5. 실제 실행 결과만으로 잠재 파라미터를 학습시켜 검증한 결과, 숨겨진 능력-스킬 대응관계를 정확히 복원했고(정확도 0.996), 오염 통제된 BigCodeBench 변형 벤치마크에서 성공률 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이 한 번에 읽어들일 수 있는 텍스트(토큰)의 최대 분량
  • 서브모듈러 함수(submodular function) · 이미 선택된 항목이 많을수록 새 항목을 추가했을 때 얻는 이득이 점점 줄어드는 성질을 가진 함수
  • 바이크라이테리아 근사(bicriteria approximation) · 두 가지 기준(이득과 비용)에 대해 각각 다른 비율로 최적해에 가까움을 보장하는 근사 방식
  • 니거색(knapsack) 제약 · 정해진 무게나 비용 한도 안에서 항목을 골라야 하는 배낭 문제 형태의 제약
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