---
title: "Optimal Skill Selection for LLM Agents with Provable Bicriteria Guarantees"
source: "arXiv AI/CL/LG（论文）"
source_tier: "t2"
url: "https://arxiv.org/abs/2608.19993v1"
permalink: "https://feed.astralor.com/items/itm_b2c60c46880b08c89276a5cd"
published: "2026-08-20T13:08:17.000Z"
score: 77
channel: "ai"
tags: ["BigCodeBench","BPS","LLM Agent","Submodular Optimization","Skill Selection","Approximate Algorithm"]
---

# Optimal Skill Selection for LLM Agents with Provable Bicriteria Guarantees

## AI commentary

> This paper turns agent skill routing from a heuristic art into a bounded optimization problem, a must-read for those working on agent infrastructure and inference cost optimization. The key insight is not just the approximation ratio, but the proof that independent relevance ranking can be inherently inefficient at the set level.

## At a glance

This paper presents the first formal model of how skill selection shapes LLM agent execution outcomes, casting skill selection as an optimization problem under a hard token budget: choose a skill set to maximize monotone submodular benefit minus context penalty. The authors propose Best Prefix Selection (BPS), a polynomial-time algorithm, and prove 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 baselines, achieving 0.73 measured task success versus 0.20–0.52 for released skill routers, text retrievers, and the executor's own selection, while using 28% fewer tokens than the strongest released router. This work provides a rigorous foundation for token-budget-aware skill routing in LLM agents and highlights the importance of set-level quality guarantees over independent relevance scoring.

## Key points

- Formalizes skill selection as an optimization problem with a hard token budget, maximizing monotone submodular benefit minus context penalty.
- Introduces BPS, a polynomial-time algorithm, with the first bicriteria (1-1/e,1) approximation guarantee for skill selection.
- On a BigCodeBench variant, BPS reaches 0.73 task success with 28% fewer tokens than the strongest released router, beating all baselines.

## Full text

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.

---

Verify against the original before citing; curated by Astral Feed: https://feed.astralor.com/items/itm_b2c60c46880b08c89276a5cd