# Optimal Skill Selection for LLM Agents with Provable Bicriteria Guarantees

arXiv: https://arxiv.org/abs/2608.19993 · HTML: https://mlsanity.com/paper/2608.19993/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Placed in Agent skill learning and evolution, one of 16 directions in LLM agents and tool use.
- Builds on 40 of its 65 references that are in the map.
- First posted on arXiv 20 Aug 2026.

## Placed in

- LLM agents and tool use / [Agent skill learning and evolution](https://mlsanity.com/agents/agent-skill-learning-and-evolution/)

## Builds on (most cited first, 30 of 40)

- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [Lost in the Middle: How Language Models Use Long Contexts](https://mlsanity.com/paper/2307.03172/) (2023)
- [ToolLLM: Facilitating Large Language Models to Master 16000+ Real-world APIs](https://mlsanity.com/paper/2307.16789/) (2023)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [Qwen3 Embedding: Advancing Text Embedding and Reranking Through Foundation Models](https://mlsanity.com/paper/2506.05176/) (2025)
- [Large Language Models Can Be Easily Distracted by Irrelevant Context](https://mlsanity.com/paper/2302.00093/) (2023)
- [Data Shapley: Equitable Valuation of Data for Machine Learning](https://mlsanity.com/paper/1904.02868/) (2019)
- [BigCodeBench: Benchmarking Code Generation with Diverse Function Calls and Complex Instructions](https://mlsanity.com/paper/2406.15877/) (2024)
- [SkillsBench: Benchmarking How Well Agent Skills Work Across Diverse Tasks](https://mlsanity.com/paper/2602.12670/) (2026)
- [Compositional Exemplars for In-context Learning](https://mlsanity.com/paper/2302.05698/) (2023)
- [NoLiMa: Long-Context Evaluation Beyond Literal Matching](https://mlsanity.com/paper/2502.05167/) (2025)
- [Metacognitive Capabilities of LLMs: An Exploration in Mathematical Problem Solving](https://mlsanity.com/paper/2405.12205/) (2024)
- [Organizing, Orchestrating, and Benchmarking Agent Skills at Ecosystem Scale](https://mlsanity.com/paper/2603.02176/) (2026)
- [SkillRouter: Skill Routing for LLM Agents at Scale](https://mlsanity.com/paper/2603.22455/) (2026)
- [Coverage-based Example Selection for In-Context Learning](https://mlsanity.com/paper/2305.14907/) (2023)
- [Graph-of-Skills: Dependency-Aware Structural Retrieval for Massive Agent Skills](https://mlsanity.com/paper/2604.05333/) (2026)
- [Skill-Based Few-Shot Selection for In-Context Learning](https://mlsanity.com/paper/2305.14210/) (2023)
- [Skill Retrieval Augmentation for Agentic AI](https://mlsanity.com/paper/2604.24594/) (2026)
- [SkillRet: A Large-Scale Benchmark for Skill Retrieval in LLM Agents](https://mlsanity.com/paper/2605.05726/) (2026)
- [SkillReducer: Optimizing LLM Agent Skills for Token Efficiency](https://mlsanity.com/paper/2603.29919/) (2026)
- [RAG-MCP: Mitigating Prompt Bloat in LLM Tool Selection via Retrieval-Augmented Generation](https://mlsanity.com/paper/2505.03275/) (2025)
- [Towards Completeness-Oriented Tool Retrieval for Large Language Models](https://mlsanity.com/paper/2405.16089/) (2024)
- [Submodular Maximization Beyond Non-negativity: Guarantees, Fast Algorithms, and Applications](https://mlsanity.com/paper/1904.09354/) (2019)
- ["Bring Your Own Greedy"+Max: Near-Optimal 1/2-Approximations for Submodular Knapsack](https://mlsanity.com/paper/1910.05646/) (2019)
- [Guess Free Maximization of Submodular and Linear Sums](https://mlsanity.com/paper/1810.03813/) (2018)
- [GeckOpt: LLM System Efficiency via Intent-Based Tool Selection](https://mlsanity.com/paper/2404.15804/) (2024)
- [More Skills, Worse Agents? Skill Shadowing Degrades Performance When Expanding Skill Libraries](https://mlsanity.com/paper/2605.24050/) (2026)
- [Group of Skills: Group-Structured Skill Retrieval for Agent Skill Libraries](https://mlsanity.com/paper/2605.06978/) (2026)
- [Automated Composition of Agents: A Knapsack Approach for Agentic Component Selection](https://mlsanity.com/paper/2510.16499/) (2025)
- [An Efficient Framework for Balancing Submodularity and Cost](https://mlsanity.com/paper/2002.07782/) (2020)

## Built on by (most cited first, 2 of 2)

- [The Router Within: Eliciting Native Skill Routing from a Frozen LLM](https://mlsanity.com/paper/2609.15982/) (2026)
- [What Can Component-Replacement Evidence Establish? A Critical Scoping Review of Local Decisions in LLM Agents](https://mlsanity.com/paper/2609.39989/) (2026)

## Abstract (arXiv)

Loading reusable skill documents into a bounded context window has become a 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. Redundant or poorly chosen skills then waste scarce context tokens and can even degrade performance. In this paper, we present a theory-grounded and practical framework for budgeted skill selection. We give the first model of how skill sets shape execution outcomes, capturing complementary capability coverage and diminishing returns from redundancy through a monotone submodular benefit, while accounting for context degradation with a linear token penalty under a hard budget. Based on this model, 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. We construct a controlled testbed based on BigCodeBench to isolate the effect of skill selection on execution success. On it, BPS with a learned capability encoder reaches a success rate of 0.65, and the strongest baselines need at least 28% more tokens to reach 0.60.