An arXiv preprint reports that Best Prefix Selection (BPS), a method for choosing bundles of skills for a language-model agent, reached a measured task-success rate of 0.73 on its benchmark. The compared released routers, text retrievers and executor self-selection scored between 0.20 and 0.52, while BPS used 28% fewer tokens than the strongest released router.
The problem is the set
The paper frames skill selection as a set-level optimization problem: choose a group of skills under a hard token budget, balancing the group’s capability benefit against a linear penalty for the context it consumes.
Its benefit function is monotone submodular — a mathematical form that can value new capability coverage while giving overlapping additions less incremental weight. BPS partially enumerates feasible starting sets of up to two skills, extends each with density-greedy additions and records every feasible prefix.
A controlled benchmark
The evaluation used a contamination-controlled benchmark derived from BigCodeBench and 63,596 executions against real test suites. The executor was frozen Qwen3-32B, which passed 85% of original BigCodeBench runs without skills.
The constructed library held 47 skill documents; 31 of them formed the library used in evaluation. Tasks were admitted only when the private-module solution passed while the standard-library solution and every one-capability hybrid failed.
With the task set and library fixed, the fitted capability encoders were lookup tables with 281 total parameters, trained jointly by gradient descent using log loss on pass/fail outcomes.
The fitted model held up on its own test
On held-out data, the fitted objective predicted success within one percentage point. It ranked covered capability pairs above uncovered pairs 99.6% of the time, with an AUC, a measure of ranking performance, of 0.996 across 155 pairs.
Across 80 fitted selection instances, BPS reached the exact optimum of the fitted objective in all 80. Two set-scoring heuristics reached that optimum in 45% and 44% of instances.
When the selected sets were taken into execution, the structured objective reached 95% of the empirical ceiling. Interpretable alternatives were at least 0.37 lower in absolute success, while a DeepSets model used 60 times as many parameters.
What the guarantee means
The authors also give BPS a bicriteria approximation guarantee. Under the stated assumptions, its benefit coefficient is 1 − 1/e and its modeled penalty coefficient is 1, meaning the full penalty is retained in the guarantee.
That result applies to the stated mathematical objective and its assumptions; it is not a measured guarantee that every real execution will show the same success.
A second version used a neural capability encoder. Paired with BPS, it reached 0.68 measured success on 716 injected tokens — 0.05 below the lookup-table version and 0.17 to 0.48 above deployed systems.
A result tied to one testbed
These are benchmark comparisons rather than a randomized test, so they show how the systems performed in this setup, not that BPS caused a universal improvement.
The empirical case rests on the frozen Qwen3-32B executor and the 31-skill evaluation library, with an admission rule that kept tasks where the private-module solution passed but the standard-library solution and every one-capability hybrid failed.
BPS’s guarantee likewise depends on modeling capability benefit as monotone submodular and token cost as a linear penalty under a hard budget. Those choices define what the mathematical result can guarantee.
Paper data and sources
Original title: Optimal Skill Selection for LLM Agents with Provable Bicriteria Guarantees
Authors: Yu Chen, Ruishuo Chen, Xun Wang et al.
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-20
DOI: Not available
Original paper · Full text