Optimal Skill Selection for LLM Agents with Provable Bicriteria Guarantees
- URL: http://arxiv.org/abs/2608.19993v1
- Date: Thu, 20 Aug 2026 13:08:17 GMT
- Title: Optimal Skill Selection for LLM Agents with Provable Bicriteria Guarantees
- Abstract summary: Current agents score skills independently and assemble the set by top-$k or greedy packing.<n>We give the first model of how selected skill set execution outcomes and cast skill selection as an optimization problem.<n>We develop Best Prefix Selection (BPS), a monotone-time algorithm, and prove to our knowledge, the first performance guarantee for skill selection.
- Score: 36.31894794808421
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: 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.
Related papers
- COBRA-Skills: Contextual Bandit-Guided Evolution for Agent Skill Optimization [55.60171725587438]
Large language model (LLM) agents can benefit from reusable skills distilled from prior task experience.<n>Existing skill optimization methods often rely on costly execution-based evaluation and substantial task data.<n>We introduce textbfCOBRA-Skills, an efficient framework that formulates skill optimization as budgeted sequential optimization over a dynamically evolving candidate space.
arXiv Detail & Related papers (2026-09-10T15:12:24Z) - SkillSelect-Serve: QoS-Aware Budgeted Skill Service Recommendation for LLM Agents [22.742669807735254]
Reusable agent skills are emerging as a service-oriented capability layer for Large Language Model (LLM) agents.<n>Existing fixed Top-k methods rank skills by textual relevance and overlook requirement satisfaction, deliverability, and operational constraints.<n>We present SkillSelect-Serve, a budget-constrained Skill Service recommendation framework.
arXiv Detail & Related papers (2026-05-08T09:36:14Z) - SkillMOO: Multi-Objective Optimization of Agent Skills for Software Engineering [9.008257157319271]
SkillMOO improves pass rate by up to 131% while reducing cost up to 32% relative to the best baseline per task at low optimization overhead.<n>We present SkillMOO, a multi-objective optimization framework that automatically evolves skill bundles using LLM-proposed edits and NSGA-II survivor selection.<n>On three SkillsBench software engineering tasks, SkillMOO improves pass rate by up to 131% while reducing cost up to 32% relative to the best baseline per task at low optimization overhead.
arXiv Detail & Related papers (2026-04-10T13:08:01Z) - Multiple-play Stochastic Bandits with Prioritized Arm Capacity Sharing [52.124267908936396]
The model is composed of $M$ arms and $K$ plays.<n>Each arm has a number of capacities, and each unit of capacity is associated with a reward function.<n>When multiple plays compete for the arm capacity, the arm capacity is allocated in a larger priority weight first manner.
arXiv Detail & Related papers (2025-12-25T11:19:09Z) - One-Stage Top-$k$ Learning-to-Defer: Score-Based Surrogates with Theoretical Guarantees [6.792743621449621]
We introduce the first one-stage Top-$k$ Learning-to-Defer framework.<n>We learn a shared score-based model that selects the $k$ most cost-effective entities-labels or experts-per input.<n>Experiments on CIFAR-10 and SVHN confirm that our one-stage Top-$k$ method strictly outperforms Top-1 deferral.
arXiv Detail & Related papers (2025-05-15T10:41:16Z) - Efficient Prompt Optimization Through the Lens of Best Arm Identification [50.56113809171805]
This work provides a principled framework, TRIPLE, to efficiently perform prompt selection under an explicit budget constraint.
It is built on a novel connection established between prompt optimization and fixed-budget best arm identification (BAI-FB) in multi-armed bandits (MAB)
arXiv Detail & Related papers (2024-02-15T05:31:13Z) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
We propose a novelgreedy bandit (SGB) algorithm for multi-armed bandit problems when no extra information other than the joint reward of the selected set of $n$ arms at each time $tin [T]$ is observed.
SGB adopts an optimized-explore-then-commit approach and is specifically designed for scenarios with a large set of base arms.
arXiv Detail & Related papers (2023-12-13T11:08:25Z) - Skill-Based Reinforcement Learning with Intrinsic Reward Matching [77.34726150561087]
We present Intrinsic Reward Matching (IRM), which unifies task-agnostic skill pretraining and task-aware finetuning.
IRM enables us to utilize pretrained skills far more effectively than previous skill selection methods.
arXiv Detail & Related papers (2022-10-14T00:04:49Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.