Optimal Skill Selection for LLM Agents with Provable Bicriteria Guarantees
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Reweighted Solutions for Weighted Low Rank Approximation
Weighted low rank approximation (WLRA) is an important yet computationally challenging primitive with applications ranging from statistical analysis, model compression, and signal processing. To cope with the NP-hardness…
feature selectionModel CompressionSimple Heuristics Yield Provable Algorithms for Masked Low-Rank Approximation
In $masked\ low-rank\ approximation$, one is given $A \in \mathbb{R}^{n \times n}$ and binary mask matrix $W \in \{0,1\}^{n \times n}$. The goal is to find a rank-$k$ matrix $L$ for which: $$cost(L) = \sum_{i=1}^{n} \sum…
Low-Rank Matrix CompletionMatrix CompletionTensor DecompositionAlgorithm Selection for Optimal Multi-Agent Path Finding via Graph Embedding
Multi-agent path finding (MAPF) is the problem of finding paths for multiple agents such that they do not collide. This problem manifests in numerous real-world applications such as controlling transportation robots in a…
Graph EmbeddingMulti-Agent Path FindingSelf-Driving CarsReduction of the Pareto Set in Bicriteria Asymmetric Traveling Salesman Problem
We consider the bicriteria asymmetric traveling salesman problem (bi-ATSP). Optimal solution to a multicriteria problem is usually supposed to be the Pareto set, which is rather wide in real-world problems. We apply to t…
Traveling Salesman ProblemSkill-Based Reinforcement Learning with Intrinsic Reward Matching
While unsupervised skill discovery has shown promise in autonomously acquiring behavioral primitives, there is still a large methodological disconnect between task-agnostic skill pretraining and downstream, task-aware fi…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)Robot Manipulation+1