Optimal Skill Selection for LLM Agents with Provable Bicriteria Guarantees

Yu Chen; Ruishuo Chen; Xun Wang; Zhuoran Li; Longbo Huang

cs.AIAug 20, 2026

Optimal Skill Selection for LLM Agents with Provable Bicriteria Guarantees

Authors: Yu Chen, Ruishuo Chen, Xun Wang, Zhuoran Li, Longbo Huang

Organizations: Institute for Interdisciplinary Information Sciences, Tsinghua University

Abstract

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.

Figures & tables

Figure 1: Top: skill selection in coding agents: a selector picks skills from a library and injects them into a frozen LLM executor. Bottom: selection is set-level: sets covering the required capabilities succeed, while redundant and irrelevant skills spend context budget for little or negative return.

Figure 2: Parameter recovery. Columns are the $31$ skill documents, grouped by the private modules they document: one, two, or none (distractors, which document look-alike APIs the tasks never use). Rows are the five capabilities, one per private module. Top: the true coverage from human labels. Bottom: the supply $\widehat{u}_{i,k}$ fitted from pass/fail outcomes alone, scaled by its largest entry, with latent dimensions matched to capabilities by the best permutation. Both panels share the $0$ – $1$ scale.

Panel of Figure 3 — Figure 3: Forking a BigCodeBench task: standard libraries are replaced by private forks.

Figure 4: Value-model comparison, parameter counts in parentheses. Left: pairwise ranking accuracy on the held-out sets of the test tasks. Right: mean success rate of the selected sets on executions held out from fitting, with the empirical ceiling dashed.

Figure 5: End-to-end skill selection: injected tokens versus measured execution success, averaged over the eight test tasks and three token budgets. From left to right, the stars show BPS with the neural capability encoder at

\rho=2,1,0

, and each top-

k

curve shows

k=1,2,3

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 6: Supplementary prediction experiments for Section 5.2 , reporting pairwise ranking accuracy with parameter counts in parentheses. Left (extrapolation): training uses sets of one or two documents; testing uses sets of three or more. Right (unseen doc): each fold withholds all combinations containing one target document, retains its singleton records in training, and tests on the withheld combinations.

Figure 7: A tiled library with three families. Left: the supply matrix, $15$ capabilities by $93$ skills; each family is a perturbed copy of the fitted library in Fig. 2 over its own five capability dimensions. Right: one task’s demand, one fitted task per family.

Figure 8: Optimization quality as the library grows. Each point is the share of instances on which a method’s selected set reaches the best value found by any method, over

300

instances per library size.

Rule	$B=500$	$B=750$	$B=1{,}000$	Mean
BPS, $\rho=0$	0.66 / 464	0.65 / 686	0.70 / 927	0.67 / 693
BPS, $\rho=1$	0.62 / 456	0.66 / 513	0.66 / 550	0.65 / 506
BPS, $\rho=2$	0.49 / 370	0.52 / 410	0.62 / 456	0.55 / 412
Executor self-select	0.51 / 530	0.57 / 660	0.71 / 753	0.60 / 647
Fine-tuned retriever, $k=1$	0.00 / 222	0.00 / 222	0.04 / 302	0.01 / 249
Fine-tuned retriever, $k=2$	0.66 / 464	0.48 / 523	0.44 / 565	0.53 / 518

Appendix

Table 1: Every point of Fig. 5 : measured success and injected tokens per budget, and their mean over the three budgets. Each cell reads success / tokens; the self-selecting executor’s tokens include the catalogue lines it reads.

Explore similar work

SkillSelect-Serve: QoS-Aware Budgeted Skill Service Recommendation for LLM Agents
May 8, 2026Jingyuan Zheng, Dongjing Wang, Xin Zhang +7LLM Agent Skill Retrieval LLM Agents
School of Computer Science and Technology, Hangzhou Dianzi University, Hangzhou, 310018, China · Sanya Traditional Chinese Medicine Hospital, Sanya, 572000, China · HDU-ITMO Joint Institute, Hangzhou Dianzi University +3
SkillsInjector: Dynamic Skill Context Construction for LLM Agents
May 28, 2026Yanchao Li, Wanhao Liu, Ben Gao +5Tool-Augmented Language Model Agents LLM Agent Skill Learning
1Nanjing University · 2Shanghai AI Lab
SkillFocus: Evolving Agent Skills via Capability Decomposition
Sep 28, 2026Ning Wang, Zhiren Gong, Bingdong Li +2LLM Agent Skill Learning Task Decomposition
East China Normal University · Nanyang Technological University · Southern University of Science and Technology +1

May 8, 2026, cs.IRJ/K move · Enter open · S save

SkillSelect-Serve: QoS-Aware Budgeted Skill Service Recommendation for LLM Agents

Jingyuan Zheng, Dongjing Wang, Xin Zhang, Hao Chen+6

School of Computer Science and Technology, Hangzhou Dianzi University, Hangzhou, 310018, China · Sanya Traditional Chinese Medicine Hospital, Sanya, 572000, China · HDU-ITMO Joint Institute, Hangzhou Dianzi University+3

LLM Agent Skill Retrieval LLM Agents Constrained Optimization Recommender Systems Large Language Model-Based Recommendation

Open paper AskPDF arXiv

Reusable agent skills are emerging as a service-oriented capability layer for Large Language Model (LLM) agents. Unlike plain retrieval items, a skill exposes functional capabilities, input-output assumptions, tool dependencies, context cost, and risk metadata. Selecting skills is particularly challenging for small LLM agents, which can load only a few capability units under restricted context, tool availability, and risk tolerance. Existing fixed Top-k methods rank skills by textual relevance and overlook requirement satisfaction, deliverability, and operational constraints. We present SkillSelect-Serve, a QoS-aware, budget-constrained Skill Service recommendation framework. Raw skills are profiled as structured Skill Services, the task is converted into a structured requirement object, and candidates discovered from a large-scale registry are ranked by a calibrated task-conditioned suitability estimator and packed by a constrained projection enforcing token-budget, aggregated-risk, and tool-availability constraints, using only deployment-observable features. On a registry of 35,353 skills with pooled multi-positive relevance judgments verified by two independent assessors, the unconstrained top-5 recommendation fits a realistic 4,000-token context for only 9.1% of tasks; the constrained projection restores 100% deliverability at a cost of only 1.14 points of hit rate, outperforming retrieve-and-rerank, budget truncation, and diversity-based selection under identical budgets. The same mechanism halves delivered risk exposure and eliminates the 44-81% tool-violation rates of tool-agnostic recommendation. At an identical three-service budget, hit rate improves from 0.8864 to 0.9091 over fixed Top-3 retrieval. The results support managing reusable agent skills as discoverable, comparable, and constraint-aware service units instead of plain retrievable documents.

Abstract

Explore similar work

SkillSelect-Serve: QoS-Aware Budgeted Skill Service Recommendation for LLM Agents

SkillsInjector: Dynamic Skill Context Construction for LLM Agents

SkillFocus: Evolving Agent Skills via Capability Decomposition