Paper deep dive
Optimal Skill Selection for LLM Agents with Provable Bicriteria Guarantees
Yu Chen, Ruishuo Chen, Xun Wang, Zhuoran Li, Longbo Huang
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 92%
Last extracted: 8/21/2026, 3:59:37 AM
Summary
This paper introduces Best Prefix Selection (BPS), a polynomial-time algorithm for selecting skill documents for Large Language Model (LLM) agents under a strict token budget. The authors formulate skill selection as a regularized submodular maximization problem, balancing a monotone submodular benefit (based on capability coverage) against a linear context penalty. They prove that BPS achieves a bicriteria (1-1/e, 1) approximation guarantee, which is optimal for polynomial-time algorithms. Experiments on a contamination-controlled BigCodeBench variant show BPS outperforms existing skill routers and retrievers, achieving higher task success rates with 28% fewer tokens.
Entities (6)
Relation Signals (5)
Best Prefix Selection → solves → Skill Selection
confidence 97% · For this problem, we develop Best Prefix Selection (BPS)... cast skill selection as an optimization problem
Best Prefix Selection → achieves → Bicriteria (1-1/e, 1) approximation
confidence 95% · prove... the first performance guarantee for skill selection: a bicriteria (1-1/e,1) approximation
Skill Selection → modeledas → Submodular Maximization
confidence 93% · cast skill selection as an optimization problem... maximize a monotone submodular benefit
Best Prefix Selection → outperforms → Skill Routers
confidence 90% · BPS outperforms all the baselines... versus 0.20--0.52 for released skill routers
Qwen3-32b → usedin → BigCodeBench
confidence 85% · we evaluate Qwen3-32B on tasks... On a contamination-controlled BigCodeBench variant
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2608.19993v1
- Canonical: https://arxiv.org/abs/2608.19993v1
Trouble viewing inline? Open PDF directly →
Full Text
84,482 characters extracted from source content.
Expand or collapse full text
Optimal Skill Selection for LLM Agents with Provable Bicriteria Guarantees Yu Chen Affiliation: Equal contribution, listed in random order. Ruishuo Chen Affiliation: Equal contribution, listed in random order. Xun Wang Zhuoran Li Longbo Huang [0.3em]Institute for Interdisciplinary Information Sciences Tsinghua University Correspondence: longbohuang@tsinghua.edu.cn arXiv preprint, August 20, 2026 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)(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.730.73 measured task success versus 0.200.20–0.520.52 for released skill routers, text retrievers, and the executor’s own selection, on 28%28\% fewer tokens than the strongest released router. 1. Introduction Large language model (LLM) agents increasingly rely on reusable skill documents to acquire task-specific capabilities beyond their parametric knowledge 48, and public skill registries already list tens of thousands of installable skills 4; 11. Modern production agents such as Codex 34 and Claude Code 2 deploy skills through a two-stage mechanism of selection and execution: the LLM reviews each installed skill’s metadata (name and description) and selects skills according to the query, then loads only the selected skill documents into its context window to solve the task. However, both stages are limited by the model’s finite context window: the context cost of selection scales with the size of the installed skill library, whereas execution consumes additional context for the selected skill documents and task input. As skill libraries grow to hundreds or thousands of entries 4; 57, the metadata alone can exceed the available context budget, making exhaustive LLM-based selection infeasible 10. Furthermore, poor skill selection has measurable consequences for downstream execution: empirical evidence shows that selecting the wrong skills cuts pass rates by up to 21%21\% as libraries grow 40, and selected skills can even push success below the no-skill baseline on 1313 of 8787 benchmark tasks despite curation 28. These limitations of modern agent architectures have driven growing interest in dedicated skill-selection mechanisms, ranging from per-skill retrieval and routing to set-aware packing and context construction 10; 9; 57; 56; 29. However, without a principled formulation to guide selection, these methods largely follow a common heuristic template: each skill is scored independently by semantic relevance or a learned preference, and the selected set is then assembled using rules such as top-k 38; 27, truncation 31, or greedy packing 56, ignoring the context cost that loading the selected skill documents imposes at execution time, and leaving capability overlap and complementarity among the selected skills unmodeled. Figure 1: Top: The common skill-selection paradigm for coding agents: given a task, the system selects skills from a library and provides them to a frozen LLM executor. Bottom: Effective skill selection depends on capability composition rather than individual relevance. The LLM executor benefits from skill sets that cover the required capabilities, while redundant and irrelevant skills consume context budget with little or negative utility. Yet these capability relationships are critical to effective skill selection. Fig. 1 illustrates a common skill-selection paradigm for coding agents 34; 2: given a task, the system selects skills from a library and provides them to a frozen LLM executor. Following this paradigm, we evaluate Qwen3-32B 47 on tasks whose required private APIs and semantics are accessible only through the selected skills, making execution performance directly dependent on selection quality. We find that skills covering only one capability achieve zero success, whereas complementary skills covering both reach a 93%93\% success rate. After both capabilities are covered, adding a redundant pk64_snip skill consumes 225225 additional tokens but improves the success rate by only 11 percentage point, while adding a semantically related but task-irrelevant pk64_extra skill reduces it by 2323 percentage points. Together, these results establish skill selection as a budgeted set-level decision rather than a ranking of individual skills. Motivated by these observations, we conduct a principled study on how to formalize and optimize the skill selection stage: given a task query and a bounded token budget, deciding which skill documents to inject into the execution context so that the scarce budget is allocated to the capabilities required by the task (Section 3). Our model takes a capability view of how skills improve performance: each skill document supplies task-relevant capabilities, and the query demands some of them. A concave response aggregates supplies of skill set S within each capability dimension, capturing diminishing returns from repeatedly covering the same capability, while separate dimensions reward covering all demanded capabilities. The resulting gross benefit G(S)G(S) is monotone submodular. To model the performance degradation caused by overlong contexts, the selected skill set is in turn charged a linear context penalty proportional to its token length ℓ(S) (S), and the total length must not exceed the available budget B. Skill selection therefore becomes maximizing this structured objective subject to the hard token budget with the form: maxS:ℓ(S)≤BF(S):=G(S)−κℓ(S). _S: (S)≤ BF(S):=G(S)-κ (S). (1) This problem, formalized in Section 3, is an instance of regularized submodular maximization under a knapsack constraint. Solving this optimization with a provable guarantee, however, faces fundamental barriers. Without the penalty, the problem contains monotone submodular knapsack maximization, which admits no approximation better than 1−1/e1-1/e unless P=NPP=NP 6. With the penalty, the objective may be negative, ruling out constant multiplicative approximation and motivating a bicriteria guarantee 33; 18. Existing results for solving regularized submodular maximization with a hard budget constraint obtain weaker approximation coefficients 15; 16; 53 or incur an additive precision-dependent loss 35. Our result attains the best possible coefficient 1−1/e1-1/e on the submodular benefit while preserving the full penalty, achieving a bicriteria (1−1/e,1)(1-1/e,1)-approximation guarantee for the skill selection problem (1) via a novel budget-aligned interpolation argument that converts a fractional point on a density chain into one of its recorded integral prefixes, exploiting the aligned form of the constraint and the penalty. To our knowledge, this work provides the first structured model of how the selected skill set shapes execution outcomes and the first skill-selection algorithm with a provable performance guarantee. We summarize our main contributions as follows. • New Formulation. We formalize skill selection as a regularized submodular maximization problem under a token budget constraint in Section 3. The structured objective makes redundancy, complementarity, and context cost explicit, and its parameters can be fitted from execution outcomes, with fitting error provably transferring to bounded selection regret. We validate the model on real executions in Section 5.2. • Optimal Bicriteria Guarantee. We develop Best Prefix Selection (BPS, Algorithm 1), a polynomial-time algorithm for the skill selection problem, and prove the tight (1−1/e, 1)(1-1/e,\,1) bicriteria guarantee (Theorem 1), achieving optimality for the benefit approximation coefficient. In the analysis, we propose budget-aligned interpolation, a novel technique exploiting the fact that the budget constraint and the context penalty share the same length coordinate, which yields the tight benefit coefficient 1−1/e1-1/e (Section 4.3). • Real-world Experiments. We construct a contamination-controlled benchmark whose tasks are gated to be unsolvable unless the injected skills supply every capability they require. On it, objective (1) fitted from pass/fail records alone predicts unseen skill sets accurately and recovers their hidden capability coverage; BPS attains its exact optimum on every selection instance; and the sets it selects beat every deployed selector we could run by 0.220.22–0.530.53 in measured task success, on 28%28\% fewer tokens than the strongest released router (Sections 3.3 and 5). 2. Related Work 2.1. Skill Selection for LLM Agents Skill retrieval and routing 4; 57; 41; 45; 44 narrow a large skill library to a candidate pool for downstream selection, following a pipeline inherited from tool use 37; 38. SkillsInjector 29 learns how many skills to inject and renders them jointly; SkillSelect-Serve 56 greedily packs itemwise scores under token and deployment constraints; Graph-of-Skills 31 expands dependency-aware bundles under a context cap yet leaves its budgeted objective unsolved; GoSkills 52 and SkillComposer 55 assemble bounded skill groups and autoregressive subsets. To our knowledge, none of these heuristics states a provable guarantee for the injected set. Guarantee-bearing neighbors decide different objects: PACMS 13 applies facility-location coverage to accumulated session content under a token knapsack, and the knapsack composer of 50 admits agentic components online with a competitive ratio. In contrast, we formulate skill selection for a fixed executor as regularized submodular maximization under a hard knapsack token budget, explicitly modeling set-level redundancy and complementarity. 2.2. Regularized Submodular Maximization Submodular maximization under a knapsack budget is a classical template for placing content and services on constrained resources 14; 36. Skill selection re-instantiates it with the context window as the constraint. For the pure benefit objective, density greedy with size-three seed enumeration attains the tight 1−1/e1-1/e 42, and refined analyses shrink the enumerated seeds to size two 24; 7. ParetoGreedy 43 extends this template toward benefit-cost trade-offs by recording every prefix of each greedy chain, and proves instance-dependent guarantees on the Pareto frontier, but no guarantee for the regularized objective G−κℓG-κ at a fixed κ. Maximizing this regularized objective, however, changes the problem’s character: it can be negative, which rules out any constant multiplicative approximation 33. Distorted greedy 18 achieves a (1−1/e,1)(1-1/e,1) bicriteria guarantee only under a cardinality constraint. Under the hard knapsack constraint, guarantees for the regularized objective come from two sparsely connected lines. Specializing the knapsack Ψ -greedy of 35 to our aligned objective gives (1−1/e,1)(1-1/e,1) up to an additive κϵκε, paid with O(B/ϵ)O(B/ε) budget levels. The budgeted-profit works reach (1/4,1)(1/4,1) 15 and ((1−1/e)/2,1/2)((1-1/e)/2,1/2) in near-linear time 16, and (1/8−ϵ,1)(1/8-ε,1) in one streaming pass 53. Our result attains (1−1/e,1)(1-1/e,1) exactly, with none of these compromises, and the benefit coefficient 1−1/e1-1/e is optimal for polynomial-time algorithms (Section 4). 3. Model and Optimization Problem In this section, we formalize the two-stage skill-interaction model in modern LLM agents. Let ℒ=s1,⋯,sLL=\s_1,·s,s_L\ denote the skill library, where sis_i is the i-th skill document. Given a query q, the selection stage chooses a subset of skills, indexed by S⊆[L]S [L], for a downstream executor E, held fixed throughout. With the documents of the selected skills injected into its context window, E executes the query q and produces an observable outcome YE(q,S)Y_E(q,S). We define the execution effect of skill set S as FE⋆(q,S):=[YE(q,S)−YE(q,∅)].F_E (q,S):=E [Y_E(q,S)-Y_E(q, ) ]. (2) FE⋆(q,S)F _E(q,S) measures the performance improvement from injecting skill set S into E’s context window, relative to running E without any skills. A natural formulation of the selection stage is to choose the skill index set S that maximizes the execution effect FE⋆(q,S)F_E (q,S). However, the execution effect FE⋆(q,S)F_E (q,S) is a black-box function of the frozen executor E, the query q, and the skill set S. Therefore, we need a structured model to approximate the execution effect FE⋆(q,S)F_E (q,S). In the following sections, we model the execution effect FE⋆(q,S)F_E (q,S) in three steps. Section 3.1 distills empirical observations into a structured objective, a monotone submodular capability benefit minus a linear degradation penalty; Section 3.2 casts the selection stage as maximizing this objective under a hard token budget and locates its computational hardness; and Section 3.3 shows that all latent parameters are learnable from execution records, with fitting error provably transferring to selection regret (Proposition 1). We validate the fitted objective on real executions in Section 5.2. 3.1. Key Observations and Structured Objective The structured model is motivated by three recurring observations. (i) Context value is query-dependent and set-level: for the fixed executor E, the positive performance contribution of injecting a skill is not an intrinsic per-skill score. It depends in part on whether the capabilities conveyed by the skill document match those required by query q 5; 1; 46 and complement those already supplied by the selected set S 17. (i) More injected context is not uniformly beneficial: irrelevant content can distract execution 39, redundant items may add little marginal coverage 17; 25, and longer inputs can reduce performance in some settings even when the relevant evidence is retrieved correctly 32. (i) For a fixed executor and agent-framework configuration, the selected skill documents must fit within the residual context budget 49; 25; 38. Guided by these observations, we build the structured model around a latent capability space. Observations (i) and (i) shape the benefit side, while observations (i) and (i) shape the cost side. The following two paragraphs formalize the two sides in turn. Structured Capability Benefit Following observations (i) and (i), we model the positive contribution of skills through a latent capability space with d dimensions. For each skill si∈ℒs_i∈L, we assume there exists a latent capability supply vector i=(ui,1,⋯,ui,d)∈ℝ+d u_i=(u_i,1,·s,u_i,d) _+^d, where ui,ku_i,k quantifies how much capability skill sis_i supplies in the k-th dimension, e.g., operating git or analyzing logs. To model the complementarity and redundancy among skills, we introduce a nondecreasing concave function hkh_k with hk(0)=0h_k(0)=0 that captures diminishing returns within the same capability dimension: for a skill set S, we use hk(∑i∈Sui,k)h_k ( _i∈ Su_i,k ) to represent the capability coverage of S in the k-th dimension, so that supplies in the same dimension overlap redundantly while supplies in different dimensions remain complementary. For query q, we assume there exists a latent capability demand vector q=(w1q,⋯,wdq)∈ℝ+d w^q=(w_1^q,·s,w_d^q) _+^d that encodes the query’s demand for each capability dimension. We then model the gross benefit of injecting skill set S into executor E as a monotone submodular function GE(q,S):=∑k=1dηkEwkq⋅hk(λkE∑i∈Sui,k),G_E(q,S):= _k=1^dη^E_kw_k^q· h_k (λ^E_k _i∈ Su_i,k ), (3) where ηkE≥0η^E_k≥ 0 and λkE≥0λ^E_k≥ 0 are executor-specific parameters that calibrate E’s sensitivity to the k-th capability dimension. GEG_E’s form aligns with the standard model of weighted coverage with diminishing returns in document summarization and data selection 30; 22, with capability dimensions playing the role of features. Intuitively, GEG_E lives on the scale of a log success probability, since success rates across demanded dimensions multiply, so its steepest gains fall on demanded dimensions that remain uncovered. Degradation Penalty and Hard Context Budget Following observation (i), injected documents impose a cost that grows with context length. Assume each skill document sis_i has a token length ℓi _i, the number of context-window tokens it occupies once injected, and write ℓ(S):=∑i∈Sℓi (S):= _i∈ S _i for the total token length of skill set S. We model the performance degradation caused by injecting S as a linear penalty cE(S):=κE⋅ℓ(S),c_E(S):= _E· (S), (4) where κE≥0 _E≥ 0 is the frozen executor’s first-order per-token context sensitivity. This per-token charge is consistent with measurements in the skill setting: compressing skill-document bodies improves execution quality 11, and focused skills outperform larger, exhaustive ones 28. Moreover, observation (i) imposes a hard feasibility limit on skill selection. We take the budget B to be the residual token budget available to skill documents in the agent framework. The hard budget defines the feasible family ℱB=S⊆[L]:ℓ(S)≤B.F_B= \S [L]:\ (S)≤ B \. (5) 3.2. Optimization Problem in Skill Selection Given the structured model above, we formalize the selection stage as a constrained optimization problem. The structured selection objective combines the capability benefit with the degradation penalty, FE(q,S):=GE(q,S)−cE(S),F_E(q,S):=G_E(q,S)-c_E(S), (6) and the selection problem maximizes it over the feasible family: maxS∈ℱBFE(q,S). _S∈F_B\;F_E(q,S). (7) Problem (7) is computationally hard: setting κE=0 _E=0 and specializing the responses hkh_k to truncated sums recovers budgeted maximum coverage 21, an NP-hard slice of monotone submodular knapsack maximization 42. Moreover, the penalty makes FEF_E non-monotone and possibly negative, ruling out any constant multiplicative approximation in polynomial time 33. Section 4 therefore develops an algorithm with a bicriteria guarantee that treats the benefit and the penalty asymmetrically. 3.3. Model Validity and Learnable Parameterization The structured objective (6) is built on latent quantities. Among its primitives, only the token length ℓi _i for each skill document sis_i is observable. The capability supplies i u_i, the query demand q w^q, and the executor calibration parameters ηkEη^E_k, λkEλ^E_k, κE _E admit no direct measurement. Two questions therefore decide whether the model is usable in practice: whether these latent quantities can be estimated from data, and whether an accurately estimated objective leads to a well-chosen skill set. For the first question, the key observation is that the selection objective never requires the latent factors individually. In (3), the demand wkqw^q_k enters only through the product ηkEwkqη^E_kw^q_k, and the supply ui,ku_i,k only through λkEui,kλ^E_ku_i,k. Defining the effective demand and effective supply w~kq:=ηkEwkq,u~i,k:=λkEui,k,∀k∈[d], w^q_k:=η^E_kw^q_k, u_i,k:=λ^E_ku_i,k, ∀ k∈[d], (8) the gross benefit (3) rewrites exactly as GE(q,S)=∑k=1dw~kqhk(∑i∈Su~i,k)G_E(q,S)= _k=1^d w^q_k\,h_k ( _i∈ S u_i,k ). We therefore estimate the effective quantities directly with two capability encoders: a demand encoder ψ^E:q↦^q ψ_E:q w^q and a supply encoder ϕ^E:si↦^i φ_E:s_i u_i, where ^q w^q and ^i u_i are estimates of the effective demand ~q w^q and effective supply ~i u_i, respectively. Each encoder is instantiated as a text encoder with a nonnegative output layer, so that the fitted objective inherits the monotone submodularity established in Section 3.1. The context sensitivity is calibrated as κ^E κ_E jointly with the encoders on execution records (q,S,YE(q,S))(q,S,Y_E(q,S)) of the frozen executor. Inspired by 20, we fix the saturating form hk(x)=1−e−xh_k(x)=1-e^-x, which is nondecreasing, concave, and bounded, thereby assigning diminishing marginal value once a capability dimension is sufficiently covered. For the second question, we give a conditional answer: whenever the fitted objective is uniformly accurate, any near-optimal selection under the fitted objective is provably near-optimal for the true execution effect. Let F^E(q,S) F_E(q,S) denote the fitted objective, obtained by instantiating (6) with the encoder outputs and the calibrated κ^E κ_E: F^E(q,S):=⟨ψ^E(q),h(∑i∈Sϕ^E(si))⟩−κ^E⋅ℓ(S), F_E(q,S):= ψ_E(q),h ( _i∈ S φ_E(s_i) ) - κ_E· (S), (9) where h(⋅)h(·) applies hk\h_k\ componentwise. At decision time, the selection layer solves the fitted selection problem, which is the deployable counterpart of (7) and is defined by maxS∈ℱBF^E(q,S). _S∈F_B F_E(q,S). (10) Solving (10) is worthwhile, however, only insofar as the fitted objective tracks the true execution effect. We formalize this accuracy requirement as a uniform error bound over the feasible family. Assumption 1 (Uniform fitting error). For the fixed instance (q,E,B)(q,E,B), there exists ε≥0 ≥ 0 such that |FE⋆(q,S)−F^E(q,S)|≤ε |F_E (q,S)- F_E(q,S) |≤ for all S∈ℱBS∈F_B. The fitting error ε aggregates two sources: structural mismatch of the objective model in Section 3.1, and estimation error of the encoders and the calibrated κ^E κ_E. Figure 2: Parameter recovery. Top: the true skill-capability coverage matrix, hidden from the fit. Bottom: the fitted supply u^i,k u_i,k, learned from pass/fail outcomes alone; its latent dimensions carry no names, so they are matched to the capabilities by the best permutation. Columns are the 3131 skills, rows the 55 capabilities. Both panels use the scale on the right, white =0=0 to dark blue =1=1; the bottom panel plots u^i,k u_i,k divided by its largest entry. In Section 5.2 we fit (9) on execution records of a frozen Qwen3-32B and evaluate it on skill combinations held out from the fit. It predicts their success to within one percentage point, and orders them by success more accurately than every value model we compare against, including neural set regressors with 60×60× as many parameters. Its fitted supplies also recover the true skill-capability coverage matrix, hidden from the fit: over the 155155 (skill, capability) pairs, u^i,k u_i,k ranks a covered pair above an uncovered one 99.6%99.6\% of the time (AUC 0.9960.996, Fig. 2). 1 is therefore attainable on a real executor from pass/fail outcomes alone, with 281281 parameters and nothing assumed beyond the structured form (3). The next proposition bounds the end-to-end selection regret for any rule that approximately solves (10). Proposition 1 (Error transfer). Under 1, every S^∈ℱB S∈F_B with F^E(q,S^)≥maxS∈ℱBF^E(q,S)−δ F_E(q, S)≥ _S∈F_B F_E(q,S)-δ satisfies maxT∈ℱBFE⋆(q,T)−FE⋆(q,S^)≤2ε+δ. _T∈F_BF_E (q,T)-F_E (q, S)≤ 2 +δ. (11) Proof. Let T⋆T maximize FE⋆(q,⋅)F_E (q,·) over ℱBF_B. Then we have FE⋆(q,T⋆)−FE⋆(q,S^)≤F^E(q,T⋆)−F^E(q,S^)+2ε≤δ+2εF_E (q,T )-F_E (q, S)≤ F_E(q,T )- F_E(q, S)+2 ≤δ+2 . ∎ Proposition 1 decomposes the selection regret into its two sources: the fitting error ε of the learned model, whose origins we discussed above, and the optimization error δ of solving the fitted selection problem (10), which will be further bounded in Theorem 1. 4. Skill Selection with Provable Guarantees We now present the selection algorithm and its per-instance guarantee for the fitted selection problem (10). Throughout this section we fix the query q, the frozen executor E, and the budget B, and suppress them from the notation, writing G^(S) G(S) for the fitted capability benefit, κ κ for the calibrated context sensitivity, and F^(S)=G^(S)−κ^ℓ(S) F(S)= G(S)- κ (S) for the fitted objective defined in (9). Our analysis uses only that G G is normalized (G^(∅)=0 G( )=0), nondecreasing, and submodular, that all lengths ℓi _i are positive, and that κ^≥0 κ≥ 0. The objective F^=G^−κ^ℓ F= G- κ raises three difficulties at once. First, although G G is monotone, F F can be non-monotone and negative, so a selection rule must be allowed to stop early or output the empty set. In particular, the classical greedy analysis for monotone submodular maximization no longer applies to F F. Second, skills have heterogeneous lengths under a single knapsack constraint, so locally dense choices can block valuable combinations. Third, the executor accepts only integral skill sets, so fractional reasoning must eventually land on an integral candidate. In this section, we show that these difficulties call for a new analysis of approximate greedy algorithms. We present our algorithm, Best Prefix Selection (BPS), and prove, to our knowledge, the first per-instance bicriteria approximation guarantee for the fitted selection problem (10) (Theorem 1). 4.1. The BPS Algorithm We state Best Prefix Selection (BPS) in Algorithm 1, a partial-enumeration density-greedy procedure with seed size two. In Lines 2–4, the algorithm enumerates all feasible seeds of size at most two. Then it grows a density-greedy chain from each seed by iteratively adding the skill with the highest marginal benefit per token (Lines 5–9), and records every feasible prefix encountered along each chain. Finally, it returns the single best recorded prefix, the one maximizing the fitted objective F F (Line 11). Algorithm 1 Best Prefix Selection (BPS) 0: skill library ℒL, budget B, fitted benefit oracle G G, fitted context sensitivity κ κ. 0: selected skill set SBPSS_ BPS. 1: Discard every skill i with ℓi>B _i>B; initialize the prefix pool ←∅P← . 2: for each seed A⊆[L]A [L] with |A|≤2|A|≤ 2 and ℓ(A)≤B (A)≤ B do 3: S←AS← A 4: Add prefix S to P. // each seed opens a prefix chain 5: while some i∉Si∉ S fits, i.e., ℓ(S)+ℓi≤B (S)+ _i≤ B do 6: i⋆←argmaxi∉S,ℓ(S)+ℓi≤B(G^(i∪S)−G^(S))/ℓi ← _i∉ S,\, (S)+ _i\!≤\!B ( G(\i\\!∪\!S)\!-\! G(S) )\!/ _i 7: S←S∪i⋆S← S∪\i \. 8: Add prefix S to P. // record every prefix in chain 9: end while 10: end for 11: SBPS←argmaxS∈F^(S)S_ BPS← _S \, F(S). // choose the best prefix 12: return SBPSS_ BPS Algorithm 1 implements the standard partial-enumeration density greedy for monotone submodular knapsack 21; 42; 24. Under a monotone benefit, the endpoint of each chain dominates all its prefixes, so the known 1−1/e1-1/e analyses compare only chain endpoints. Under the non-monotone fitted objective F F, however, the endpoint need not be the best candidate, since the optimum can sit strictly inside a chain. Inspired by 43, we record every prefix and select the best one over the full collection by F F; this best-prefix selection step gives BPS its name. 4.2. Main Result: Bicriteria Approximation Guarantee Throughout, let α=1−1/eα=1-1/e. The theoretical guarantee for Algorithm 1 is given below. Theorem 1 (Bicriteria (1−1/e, 1)(1-1/e,\,1)-approximation guarantee). Let G G be normalized (G^(∅)=0 G( )=0), nondecreasing, and submodular, let ℓi>0 _i>0 for all i∈[L]i∈[L], and let κ^≥0 κ≥ 0. The BPS output SBPSS_ BPS of Algorithm 1 satisfies SBPS∈ℱBS_ BPS∈F_B and F^(SBPS)≥αG^(T)−κ^ℓ(T)∀T∈ℱB. F(S_ BPS)≥α\, G(T)- κ (T) ∀ T∈F_B. (12) The guarantee (12) is a bicriteria approximation: the two coefficients are α=1−1/eα=1-1/e on the benefit and 11 on the penalty, meaning that BPS recovers at least a (1−1/e)(1-1/e) fraction of any feasible set’s capability benefit while incurring its full context-length penalty. Tightness The benefit coefficient α=1−1/eα=1-1/e in (12) cannot be improved under standard complexity assumptions (any (1−1/e+ϵ)(1-1/e+ε)-approximation is NP-hard 6). Theorem 1 provides a tight polynomial-time bicriteria guarantee for maximizing a monotone submodular benefit minus a linear penalty under a knapsack constraint. Comparison to prior work The guarantees closest to our setting address the same regularized objective under the same knapsack constraint, and each concedes what Theorem 1 does not: weaker approximation coefficients 15; 16; 53, an additive precision-dependent loss 35, or a fractional output 8. ParetoGreedy 43, whose candidate generation BPS shares, proves instance-dependent guarantees on the Pareto frontier, but none for the regularized objective at a fixed κ κ. Theorem 1 is, to our knowledge, the first to combine all four properties: a regularized objective, a knapsack constraint with heterogeneous item sizes, an integral output, and zero additive loss. Selection regret Let S⋆=argmaxT∈ℱBFE⋆(q,T)S = _T∈F_BF _E(q,T) denote the skill set maximizing the true execution effect. Taking T=S⋆T=S in (12) gives F^(SBPS)≥F^(S⋆)−1eG^(S⋆) F(S_ BPS)≥ F(S )- 1e G(S ), so the suboptimality of the BPS output is at most a 1/e1/e fraction of the optimum’s benefit G^(S⋆) G(S ). Combining Theorem 1 with the error transfer of Proposition 1 yields an end-to-end bound on the true execution effect. Corollary 1 (Selection regret of BPS). Under 1, the BPS output SBPSS_ BPS satisfies FE⋆(q,S⋆)−FE⋆(q,SBPS)≤1eG^(S⋆)+2ε.F_E (q,S )-F_E (q,S_ BPS)≤ 1e G(S )+2 . Time Complexity Algorithm 1 runs in O(dL4)O(dL^4) time, where d is the capability dimension and L the library size: O(L2)O(L^2) seeds each grow a chain of at most L density steps, and each step scans O(L)O(L) candidates at O(d)O(d) cost per marginal evaluation. In practice L is the size of the shortlist left by a high-recall retrieval stage 4; 57; 10, not of the whole registry. 4.3. Proof of Theorem 1 For an arbitrary feasible set T, the proof proceeds in three steps: (i) Construct a seed J from T’s two highest-marginal items and define a residual benefit function f. (i) Lower-bound the trajectory function (18) of the density chain grown from J by a piecewise-exponential bounding function φ , adapting the refined analysis of 24, and establish G^(J)+V(r)≥αG^(T) G(J)+V(r)≥α G(T). (i) Convert this fractional bound into an actual recorded integral prefix via budget-aligned interpolation, and conclude via the F F-maximization of Algorithm 1. 4.3.1 Seed construction and residual function We first write G^(i∣S)=G^(S∪i)−G^(S) G(i S)= G(S∪\i\)- G(S) for the marginal benefit. We order the items of T greedily by nonincreasing marginal benefit with an arbitrary fixed tie-breaking rule: tj t_j ∈argmaxi∈T∖t1,⋯,tj−1G^(i∣t1,⋯,tj−1), ∈ _i∈ T \t_1,·s,t_j-1\ G (i \t_1,·s,t_j-1\ ), (13) mj m_j :=G^(tj∣t1,⋯,tj−1),∀j∈[|T|]. := G (t_j \t_1,·s,t_j-1\ ), ∀ j∈[|T|]. If |T|≤2|T|≤ 2, then Algorithm 1 enumerates T itself as a seed, and we have F^(T)=G^(T)−κ^ℓ(T)≥αG^(T)−κ^ℓ(T). F(T)= G(T)- κ (T)≥α G(T)- κ (T). We set the feasible seed set J with ℓ(J)≤B (J)≤ B as J:=t1,t2.J:=\t_1,t_2\. (14) Then Algorithm 1 enumerates it in Line 2 and records it in Line 4, so J∈J . If |T|=3|T|=3: G^(J)=m1+m2≥23(m1+m2+m3)=23G^(T)≥αG^(T) G(J)=m_1+m_2≥ 23(m_1+m_2+m_3)= 23 G(T)≥α G(T) and ℓ(J)≤ℓ(T) (J)≤ (T) give F^(J)≥αG^(T)−κ^ℓ(T) F(J)≥α\, G(T)- κ\, (T). In the following, we assume |T|≥4|T|≥ 4. Our goal is to prove that on the chain grown from J, some recorded prefix STS_T satisfies F^(ST)≥αG^(T)−κ^ℓ(T) F(S_T)≥α G(T)- κ (T). Inspired by the analysis in 42, we define the residual function f(U):=G^(J∪U)−G^(J),∀U⊆[L].f(U):= G(J∪ U)- G(J), ∀ U [L]. (15) By the properties of G G, f is normalized (f(∅)=0f( )=0), nonnegative, nondecreasing, and submodular. Let P=T∖JP=T J denote the comparator residual. For every v∈Pv∈ P, we have f(v)=G^(v∪J)−G^(J)=G^(v∣J)≤G^(v∣t1)≤m2f(\v\)= G(\v\∪ J)- G(J)= G(v J)≤ G(v \t_1\)≤ m_2, where the first inequality uses submodularity and the second uses the greedy ordering (13). Therefore, we have G^(J) G(J) =G^(t1,t2)−G^(t1)+G^(t1)=m1+m2≥2m2≥2f(v),∀v∈P. = G(\t_1,t_2\)- G(\t_1\)+ G(\t_1\)=m_1+m_2≥ 2m_2≥ 2f(\v\), ∀ v∈ P. (16) We choose v⋆∈Pv ∈ P as the item with maximum token length, i.e., v⋆=argmaxv∈Pℓ(v)v = _v∈ P (\v\). Set r=ℓ(P∖v⋆).r= (P \v \). (17) Then we can show that the density chain starting with seed J must have total token length larger than r. 4.3.2 Bounding-function domination Run the density chain of Algorithm 1 from seed J, and let A0=∅⊊A1⊊⋯⊊AmA_0= A_1 ·s A_m be its accepted additions, so the actual recorded prefixes are J∪AjJ∪ A_j. Write aj=Aj∖Aj−1a_j=A_j A_j-1 for the j-th accepted item. Following 24, we define the piecewise-affine residual-benefit trajectory V by V(0)=0V(0)=0 and, for ℓ(Aj−1)≤u≤ℓ(Aj) (A_j-1)≤ u≤ (A_j), V(u):=f(Aj−1)+(u−ℓ(Aj−1))f(aj∣Aj−1)ℓ(aj).V(u):=f(A_j-1)+ (u- (A_j-1) ) f(a_j A_j-1) (\a_j\). (18) The function V:[0,ℓ(Am)]→ℝ≥0V:[0, (A_m)] _≥ 0 traces the residual benefit accumulated by the density chain as a function of the total added length u=ℓ(Aj)u= (A_j) beyond the seed J. At each breakpoint u=ℓ(Aj)u= (A_j), the trajectory evaluates to V(ℓ(Aj))=f(Aj)V( (A_j))=f(A_j), the exact residual benefit of the j-th recorded prefix. Between consecutive breakpoints, V interpolates linearly. Then we have the following lemmas. Lemma 1 (Trajectory coverage). V(r)V(r) is well-defined; that is, ℓ(Am)≥r (A_m)≥ r. Proof. If P⊆AmP A_m, then ℓ(Am)≥ℓ(P)>r (A_m)≥ (P)>r by definition in (17). Otherwise pick v∈P∖Amv∈ P A_m. When the chain stops, adding v is infeasible. Then ℓ(Am)+ℓ(v)>B−ℓ(J) (A_m)+ (\v\)>B- (J). Since ℓ(v)≤ℓ(v⋆) (\v\)≤ (\v \) and ℓ(T)≤B (T)≤ B, we have ℓ(Am)>B−ℓ(J)−ℓ(v)≥ℓ(T)−ℓ(J)−ℓ(v⋆)=r (A_m)>B- (J)- (\v\)≥ (T)- (J)- (\v \)=r. ∎ Lemma 2 (Residual feasibility before r). Consider an accepted segment whose left endpoint u0=ℓ(Aj−1)u_0= (A_j-1) satisfies u0<ru_0<r. Then every item v∈P∖Aj−1v∈ P A_j-1 is feasible at that point. Proof. By maximality of ℓ(v⋆) (\v \), we have ℓ(Aj−1∪v)=u0+ℓ(v)<r+ℓ(v⋆)=ℓ(P)=ℓ(T)−ℓ(J)≤B−ℓ(J) (A_j-1∪\v\)=u_0+ (\v\)<r+ (\v \)= (P)= (T)- (J)≤ B- (J). Therefore, v is feasible at the selection on aja_j. ∎ Lemma 2 is where removing the longest residual item pays off. We adapt the bounding-function technique of 24. Partition P into two nonempty blocks v⋆\v \ and R=P∖v⋆R=P \v \, and order them as (X1,X2)(X_1,X_2) so that f(X1)ℓ(X1)≥f(X2)ℓ(X2). f(X_1) (X_1)≥ f(X_2) (X_2). (19) Set dj=ℓ(Xj)d_j= (X_j) for j=1,2j=1,2, and define the block densities ρ1=f(X1)d1,ρ2=f(X2∣X1)d2, _1= f(X_1)d_1, _2= f(X_2 X_1)d_2, (20) where f(X2∣X1)=f(X1∪X2)−f(X1)f(X_2 X_1)=f(X_1∪ X_2)-f(X_1). Submodularity and (19) give ρ1≥ρ2 _1≥ _2. Write D=ℓ(P)=d1+d2.D= (P)=d_1+d_2. (21) If ρ2>0 _2>0, let D1=d1lnρ1ρ2D_1=d_1 _1 _2. If ρ2=0 _2=0, set D1=+∞D_1=+∞. Define a continuous function φ:[0,∞)→ℝ≥0 :[0,∞) _≥ 0 by φ(u)=f(X1)(1−exp(−u/d1)),0≤u<D1,f(P)−ρ2Dexp(−u−D1D),u≥D1. (u)= casesf(X_1) (1- (-u/d_1) ),&0≤ u<D_1,\\ f(P)- _2D (- u-D_1D ),&u≥ D_1. cases (22) The bounding function φ is constructed so that: on the first branch, it tracks exponential saturation toward f(X1)f(X_1) at rate 1/d11/d_1; on the second branch, it tracks saturation toward f(P)f(P) at rate 1/D1/D. The transition at D1D_1 is precisely where the two exponentials meet. The next two lemmas separate the argument into a dynamic half, showing that the trajectory of the density chain never falls below φ before r, and a static half, showing that the seed and φ(r) (r) together already account for an α fraction of G^(T) G(T). And the proofs are computational and deferred to Appendix A. Lemma 3 (Trajectory bound). V(u)≥φ(u),∀u∈[0,r]V(u)≥ (u),∀ u∈[0,r]. Lemma 4 (Static bound at r). G^(J)+φ(r)≥αG^(T) G(J)+ (r)≥α G(T). 4.3.3 Budget-aligned interpolation Lemmas 3 and 4 give G^(J)+V(r)≥G^(J)+φ(r)≥αG^(T). G(J)+V(r)≥ G(J)+ (r)≥α\, G(T). (23) Choose consecutive recorded prefixes Aj−1,AjA_j-1,A_j whose segment contains r. There exists λ∈[0,1]λ∈[0,1] with V(r)=(1−λ)f(Aj−1)+λf(Aj),V(r)=(1-λ)\,f(A_j-1)+λ\,f(A_j), and r=(1−λ)ℓ(Aj−1)+λℓ(Aj)r=(1-λ)\, (A_j-1)+λ\, (A_j). Because the penalty κ^ℓ(⋅) κ\, (·) is the same linear function of the same length coordinate, the two interpolations combine: (1−λ)F^(J∪Aj−1)+λF^(J∪Aj)=G^(J)+V(r)−κ^(ℓ(J)+r)(1-λ) F(J∪ A_j-1)+λ F(J∪ A_j)= G(J)+V(r)- κ( (J)+r). Since ℓ(J)+r=ℓ(T)−ℓ(v⋆)≤ℓ(T) (J)+r= (T)- (\v \)≤ (T), (23) gives (1−λ)F^(J∪Aj−1)+λF^(J∪Aj)≥αG^(T)−κ^(ℓ(T)−ℓ(v⋆))≥αG^(T)−κ^ℓ(T)(1-λ) F(J∪ A_j-1)+λ F(J∪ A_j)≥α G(T)- κ( (T)- (\v \))≥α G(T)- κ (T). A convex combination of two numbers is at most their maximum, so at least one of the two recorded prefixes satisfies F^(J∪As)≥αG^(T)−κ^ℓ(T),s∈j−1,j. F(J∪ A_s)≥α G(T)- κ (T), s∈\j-1,j\. (24) Therefore, in every case, some recorded candidate ST∈S_T satisfies F^(ST)≥αG^(T)−κ^ℓ(T) F(S_T)≥α\, G(T)- κ\, (T). Since SBPSS_ BPS maximizes F F over P (Line 11 of Algorithm 1), F^(SBPS)≥F^(ST) F(S_ BPS)≥ F(S_T). The seed and witness prefix depend on T, but every seed of size at most two is enumerated and one selection maximizes F F over all recorded candidates, so the single output SBPSS_ BPS satisfies (12) for every T∈ℱBT∈F_B. This statement finishes the proof of Theorem 1. ■ 5. Evaluation Corollary 1 bounds the selection regret of BPS by a fitting term and an optimization term, and we measure both on real executions of a frozen executor. Section 5.2 measures the first, how closely the fitted objective tracks those executions, and Section 5.3 the second, how far the sets BPS returns fall short of the exact optimum of that objective, which Theorem 1 bounds only in the worst case. Section 5.4 then executes the selected sets and reports the task success they achieve. 5.1. Testbed: A Contamination-Controlled Skill Benchmark %85\%%0\% Figure 3: Forking a BigCodeBench task. Standard libraries are swapped for private forks with new names and altered constants: pkzip.lade plays the role of zlib.compress but XORs the payload and prepends a private header, and pk64.enrobe base64-encodes under a remapped alphabet. Public code benchmarks cannot measure skill selection, because a capable executor already solves them with no skill at all: Qwen3-32B, the frozen executor throughout, passes 85%85\% of runs on the original BigCodeBench 58 tasks from pretraining alone. We therefore build our own, and everything below rests on 63,59663,596 executions of it against real test suites. Private modules We fork the benchmark, replacing its standard libraries with sixteen private modules over d=5d=5 capability families. Each module’s call surface is unguessable from the task prose and documented only in the skill library (Fig. 3). Task admission A task is admitted only if the private-module solution passes its tests while both the standard-library solution and every one-capability hybrid of the two fail, so that only tasks needing all of their capabilities survive. Fewer than one in three of the tasks we forked cleared this gate, and those that did form the testbed. Skill library We wrote 4747 skill documents, of which L=31L=31 form the library: single-module skills ranging from a short snippet to a full tutorial, two-module handbooks, and distractors covering only look-alike functions no task calls for. 5.2. Validity of the Structured Objective Figure 4: Value-model comparison. Left: pairwise ranking accuracy on held-out set pairs, under the extrapolation (filled dots) and unseen-doc (open dots) protocols. Right: measured success of the sets each model selects; the dashed line is the empirical ceiling, the best set per instance in hindsight. We instantiate the fitted objective (9) on the testbed and evaluate it on two counts, its prediction of held-out executions and the quality of the sets it selects; its recovery of the true coverage matrix was reported in Section 3.3. Instantiation and fitting We set d=5d=5, one dimension per module family, and fix hk(x)=1−e−xh_k(x)=1-e^-x a priori, as in Section 3.3. The task set and the library are both fixed, so the encoders reduce to lookup tables that assume nothing beyond the structured form (3): one supply vector ^i u_i per skill, one demand vector ^q w^q per task, and one offset per task, 281281 parameters in total. These are trained jointly by gradient descent, minimizing the log loss of the measured pass/fail outcomes against the predicted success probability expF^E F_E (9). Baselines We compare against the value models in common use, all fit on the same execution records. Additive fit gives each skill an independent per-task value and sums it over the set; Shapley scores 12 do the same with values estimated from measured marginal contributions. Datamodels 19 regresses the measured rate on the set indicator. DeepSets 51 and Set Transformer 26 are black-box neural set regressors. Linear response is an ablation of our own model, keeping the capability structure but dropping the concave saturation. Prediction Each model scores pairs of sets whose measured success rates differ by a clear margin, and Fig. 4 (left) reports how often it orders the pair correctly. Two protocols probe unseen set compositions. Under extrapolation, a model trains only on sets of at most two skills and must predict sets of three or more; under unseen doc, it sees a skill only on its own, never in combination, and must predict the sets that pair it with others. The structured objective is the most accurate under both, and its predicted rates fall within one percentage point of the measured ones. Selection Prediction accuracy matters only insofar as it changes which set is chosen, so we also let each model choose. Each is refit from a small sample of each test task and returns the set it scores highest, which is then executed (Fig. 4, right). The structured objective reaches 95%95\% of the empirical ceiling, and every interpretable alternative gives up at least 0.370.37 in absolute success. Only DeepSets remains competitive, at 60×60× the parameters and with an advantage that never separates from zero; being a black box, it also exposes no structure for BPS to exploit and can be maximized only by brute force. 5.3. Optimization Quality To isolate the optimization term δ, we freeze the objective at the fit of Section 5.2 and vary only the rule that maximizes it, so that the comparison measures search quality alone. The 8080 instances of the fitted selection problem (10) span held-out tasks, token budget levels B, and settings of the token soft-penalty coefficient. Baselines Five rules receive the same fitted objective but do not maximize it. Three score every skill in isolation, by the benefit (9) assigns the singleton si\s_i\, and never evaluate the set they assemble or charge for the tokens it costs: top-k relevance fills the budget in that order, while MMR 3 and DPP-MAP 23 discount that score by similarity to the fitted supplies already selected. Two do score whole sets but search them heuristically: density greedy adds the skill with the best value per token until the budget closes, and best-of-100100 random keeps the highest-scoring of 100100 random budget-feasible sets. Figure 5: The 8080 selection instances. Left: optimization quality. Every rule is given the same fitted objective; bars are the share of instances on which a rule attains the exact optimum, found by exhaustive search over every feasible set, and the right-hand column is its mean shortfall in objective value. Right: end-to-end selection. Each rule is placed by the tokens it injects and the measured success of the sets it chooses; up and to the left is better. Both of our points run BPS and differ only in how the objective’s encoders are instantiated. Solution quality BPS attains the exact optimum of (10) on all 8080 instances, so the optimization error δ of Proposition 1 vanishes throughout (Fig. 5, left). The three rules that score skills one at a time reach the optimum on fewer than a tenth of them, with a mean shortfall nearly two orders of magnitude larger than that of any rule scoring whole sets; the two set-scoring heuristics come closer, but still reach it on only 45%45\% and 44%44\%. 5.4. End-to-End Selection Quality The end-to-end test executes every rule’s chosen set on the frozen executor over the same 8080 instances, and measures success on executions the fit never saw. Baselines We compare against the skill selection systems in use today. BM25 and a dense bi-encoder, the two retrievers that the skill-retrieval literature defaults to 41, rank the documents by their text against the task prompt and fill the budget in that order. SkillRouter 57 is a released retrieve-and-rerank router, which we run both at its own top-11 operating point and, more generously, in its reranked order up to our full budget; Graph-of-Skills 31 diffuses over an offline skill graph and hydrates under a context cap. Both run from their authors’ released implementations on our library. Finally we let the executor select for itself under the progressive disclosure that deployed systems use, shown every skill’s name, cost and one-line description with the bodies hidden. Measured execution No deployed system we could run matches BPS in measured success (Fig. 5, right). The released routers and retrievers reach 0.200.20–0.430.43, between 0.300.30 and 0.530.53 below it, and BPS attains its own result on 28%28\% fewer tokens than the strongest of them; the strongest deployed selector, the executor picking for itself, still gives up 0.220.22. These systems rarely select distractors. What they select instead are the skills whose text matches the task, and those need not be the skills that cover the capabilities it exercises. A neural capability encoder The encoders of Section 5.2 instantiate the structured objective on the benchmark’s fixed task set and library; deployment beyond them requires encoding tasks and skills from their text. We therefore replace the lookup tables with a neural encoder that projects frozen text-embedding-v4 54 embeddings of the task prompt and of each skill document into 6464 latent capability dimensions, warmed up on annotated examples of covering skill sets and then trained online on pass/fail feedback from the frozen executor; BPS still performs the selection. Its sets reach 0.680.68 measured success on 716716 injected tokens (red star in Fig. 5): 0.050.05 below the lookup-table instantiation, and 0.170.17–0.480.48 above every deployed system, injecting fewer tokens than all of them except the executor’s own selection. 6. Conclusion This paper casts skill selection for LLM agents as regularized submodular maximization under a hard token budget: a submodular capability benefit makes complementarity and redundancy explicit, and a linear penalty charges every injected token. Our polynomial-time selection rule BPS carries a bicriteria (1−1/e, 1)(1-1/e,\,1) guarantee, proved via budget-aligned interpolation and tight in the benefit coefficient. On a contamination-controlled benchmark with real executions, the fitted objective was the most accurate value model, and BPS outperformed every deployed skill selector in measured success while injecting fewer tokens than any released system. Future work includes online selection over streaming queries and degradation models beyond a linear per-token charge. References An et al. (2023) S. An et al. Skill-Based Few-Shot Selection for In-Context Learning. In Proc. 2023 Conf. Empirical Methods Natural Lang. Process. (EMNLP), p. 13472–13492. Cited by: §3.1. Anthropic (2025) AnthropicEquipping agents for the real world with agent skills(Website) Note: Anthropic Engineering BlogAccessed 2026-07-23 External Links: Link Cited by: §1, §1. Carbonell and Goldstein (1998) J. Carbonell and J. Goldstein The use of MMR, diversity-based reranking for reordering documents and producing summaries. In Proc. 21st Annu. Int. ACM SIGIR Conf. Res. Develop. Inf. Retrieval, p. 335–336. Cited by: §5.3. Cho et al. (2026) H. Cho, R. Kang, and Y. Kim SkillRet: a large-scale benchmark for skill retrieval in LLM agents. arXiv preprint arXiv:2605.05726. Cited by: §1, §1, §2.1, §4.2. Didolkar et al. (2024) A. Didolkar et al. Metacognitive Capabilities of LLMs: An Exploration in Mathematical Problem Solving. In Adv. Neural Inf. Process. Syst. 37 (NeurIPS 2024), p. 19783–19812. Cited by: §3.1. Feige (1998) U. Feige A threshold of ln n for approximating set cover. J. ACM 45 (4), p. 634–652. Cited by: §1, §4.2. Feldman et al. (2023) M. Feldman, Z. Nutov, and E. Shoham Practical budgeted submodular maximization. Algorithmica 85 (5), p. 1332–1371. Cited by: §2.2. Feldman (2021) M. Feldman Guess free maximization of submodular and linear sums. Algorithmica 83 (3), p. 853–878. Cited by: §4.2. Fore et al. (2024) M. Fore, S. Singh, and D. Stamoulis GeckOpt: LLM system efficiency via intent-based tool selection. In Proc. Great Lakes Symp. VLSI (GLSVLSI), p. 353–354. Cited by: §1. Gan and Sun (2025) T. Gan and Q. Sun RAG-MCP: mitigating prompt bloat in LLM tool selection via retrieval-augmented generation. arXiv preprint arXiv:2505.03275. Cited by: §1, §1, §4.2. Gao et al. (2026) Y. Gao, Z. Li, Y. Yuan, Z. Ji, P. Ma, and S. Wang SkillReducer: optimizing LLM agent skills for token efficiency. arXiv preprint arXiv:2603.29919. Cited by: §1, §3.1. Ghorbani and Zou (2019) A. Ghorbani and J. Zou Data Shapley: equitable valuation of data for machine learning. In Proc. 36th Int. Conf. Mach. Learn. (ICML), p. 2242–2251. Cited by: §5.2. Ghulyani et al. (2026) M. Ghulyani, A. Singh, K. Bharadwaj, A. Nath, and S. Goswami PACMS: submodular context selection as a pluggable engine for LLM agents. arXiv preprint arXiv:2606.20047. Cited by: §2.1. Golrezaei et al. (2012) N. Golrezaei, K. Shanmugam, A. G. Dimakis, A. F. Molisch, and G. Caire FemtoCaching: wireless video content delivery through distributed caching helpers. In Proc. IEEE INFOCOM, p. 1107–1115. Cited by: §2.2. Gong et al. (2024) S. Gong, Q. Nong, Y. Wang, and D. Du Budget-constrained profit maximization without non-negative objective assumption in social networks. J. Glob. Optim. 90 (4), p. 1007–1030. Cited by: §1, §2.2, §4.2. Guo et al. (2026) Q. Guo, C. Feng, J. Shi, J. Tang, X. Zhou, and S. Wang Efficient algorithms for budgeted profit maximization with theoretical guarantees. IEEE Trans. Knowl. Data Eng. 38 (4), p. 2234–2248. Cited by: §1, §2.2, §4.2. Gupta et al. (2023) S. Gupta, M. Gardner, and S. Singh Coverage-based example selection for in-context learning. In Findings Assoc. Comput. Linguistics: EMNLP 2023, Cited by: §3.1. Harshaw et al. (2019) C. Harshaw, M. Feldman, J. Ward, and A. Karbasi Submodular maximization beyond non-negativity: guarantees, fast algorithms, and applications. In Proc. 36th Int. Conf. Mach. Learn. (ICML), p. 2634–2643. Cited by: §1, §2.2. Ilyas et al. (2022) A. Ilyas, S. M. Park, L. Engstrom, G. Leclerc, and A. Madry Datamodels: understanding predictions with data and data with predictions. In Proc. 39th Int. Conf. Mach. Learn. (ICML), p. 9525–9587. Cited by: §5.2. Iyer and Bilmes (2015) R. Iyer and J. Bilmes Submodular Point Processes with Applications to Machine learning. In Proc. 18th Int. Conf. Artif. Intell. Statist. (AISTATS), p. 388–397. Cited by: §3.3. Khuller et al. (1999) S. Khuller, A. Moss, and J. Naor The budgeted maximum coverage problem. Inf. Process. Lett. 70 (1), p. 39–45. Cited by: §3.2, §4.1. Kirchhoff and Bilmes (2014) K. Kirchhoff and J. Bilmes Submodularity for data selection in machine translation. In Proc. 2014 Conf. Empirical Methods Natural Lang. Process. (EMNLP), p. 131–141. Cited by: §3.1. Kulesza and Taskar (2012) A. Kulesza and B. Taskar Determinantal point processes for machine learning. Found. Trends Mach. Learn. 5 (2–3), p. 123–286. Cited by: §5.3. Kulik et al. (2021) A. Kulik, R. Schwartz, and H. Shachnai A refined analysis of submodular greedy. Oper. Res. Lett. 49 (4), p. 507–514. Cited by: §A.2, §2.2, §4.1, §4.3.2, §4.3.2, §4.3. Kumari et al. (2024) L. Kumari, S. Wang, A. Das, T. Zhou, and J. Bilmes An end-to-end submodular framework for data-efficient in-context learning. In Findings Assoc. Comput. Linguistics: NAACL 2024, p. 3293–3308. Cited by: §3.1. Lee et al. (2019) J. Lee, Y. Lee, J. Kim, A. R. Kosiorek, S. Choi, and Y. W. Teh Set transformer: a framework for attention-based permutation-invariant neural networks. In Proc. 36th Int. Conf. Mach. Learn. (ICML), p. 3744–3753. Cited by: §5.2. Li et al. (2026a) H. Li et al. Organizing, orchestrating, and benchmarking agent skills at ecosystem scale. arXiv preprint arXiv:2603.02176. Cited by: §1. Li et al. (2026b) X. Li et al. SkillsBench: benchmarking how well agent skills work across diverse tasks. arXiv preprint arXiv:2602.12670. Cited by: §1, §3.1. Li et al. (2026c) Y. Li et al. SkillsInjector: dynamic skill context construction for LLM agents. arXiv preprint arXiv:2605.29794. Cited by: §1, §2.1. Lin and Bilmes (2011) H. Lin and J. Bilmes A class of submodular functions for document summarization. In Proc. 49th Annu. Meeting Assoc. Comput. Linguistics (ACL), p. 510–520. Cited by: §3.1. Liu et al. (2026) D. Liu et al. Graph-of-Skills: dependency-aware structural retrieval for massive agent skills. arXiv preprint arXiv:2604.05333. Cited by: §1, §2.1, §5.4. Liu et al. (2024) N. F. Liu et al. Lost in the middle: how language models use long contexts. Trans. Assoc. Comput. Linguistics 12, p. 157–173. Cited by: §3.1. Nikolakaki et al. (2021) S. M. Nikolakaki, A. Ene, and E. Terzi An efficient framework for balancing submodularity and cost. In Proc. 27th ACM SIGKDD Conf. Knowl. Discov. Data Min., p. 1256–1266. Cited by: §1, §2.2, §3.2. OpenAI (2026) OpenAIBuild skills(Website) Note: Codex DocumentationAccessed 2026-07-26 External Links: Link Cited by: §1, §1. Perrault et al. (2021) P. Perrault, J. Healey, Z. Wen, and M. Valko On the approximation relationship between optimizing ratio of submodular (RS) and difference of submodular (DS) functions. arXiv preprint arXiv:2101.01631. Cited by: §1, §2.2, §4.2. Poularakis et al. (2019) K. Poularakis, J. Llorca, A. M. Tulino, I. Taylor, and L. Tassiulas Joint service placement and request routing in multi-cell mobile edge computing networks. In Proc. IEEE INFOCOM, p. 10–18. Cited by: §2.2. Qin et al. (2024) Y. Qin et al. ToolLLM: facilitating large language models to master 16000+ real-world APIs. In Proc. 12th Int. Conf. Learn. Represent. (ICLR), Cited by: §2.1. Qu et al. (2024) C. Qu et al. Towards completeness-oriented tool retrieval for large language models. In Proc. ACM Int. Conf. Inf. Knowl. Manage. (CIKM), p. 1930–1940. Cited by: §1, §2.1, §3.1. Shi et al. (2023) F. Shi et al. Large language models can be easily distracted by irrelevant context. In Proc. 40th Int. Conf. Mach. Learn. (ICML), p. 31210–31227. Cited by: §3.1. Song and Wei (2026) H. Song and S. Wei More skills, worse agents? skill shadowing degrades performance when expanding skill libraries. arXiv preprint arXiv:2605.24050. Cited by: §1. Su et al. (2026) W. Su et al. Skill retrieval augmentation for agentic AI. arXiv preprint arXiv:2604.24594. Cited by: §2.1, §5.4. Sviridenko (2004) M. Sviridenko A note on maximizing a submodular set function subject to a knapsack constraint. Oper. Res. Lett. 32 (1), p. 41–43. Cited by: §2.2, §3.2, §4.1, §4.3.1. Vombatkere and Terzi (2026) K. Vombatkere and E. Terzi Computing approximate pareto frontiers for submodular utility and cost tradeoffs. arXiv preprint arXiv:2602.15964. Cited by: §2.2, §4.1, §4.2. Wang et al. (2026) Z. Wang, W. Wen, Q. Ji, R. Qiao, and X. Sun Skill is not document: a query-conditional benchmark and two-stage retriever for LLM agent skill routing. arXiv preprint arXiv:2606.03565. Cited by: §2.1. Xiao et al. (2026) J. Xiao et al. SkillSight: calibrating generic content bias for skill retrieval. arXiv preprint arXiv:2607.18785. Cited by: §2.1. Xu et al. (2024) Z. Xu, H. Wang, D. Bespalov, X. Wu, P. Stone, and Y. Qi LaRS: Latent Reasoning Skills for Chain-of-Thought Reasoning. In Findings Assoc. Comput. Linguistics: EMNLP 2024, p. 3624–3643. Cited by: §3.1. Yang et al. (2025) A. Yang et al. Qwen3 technical report. arXiv preprint arXiv:2505.09388. Cited by: §1. Yang et al. (2026) C. Yang et al. A survey of agent skills: toward procedural infrastructure for LLM agents. Preprints.org preprint. Note: doi: 10.20944/preprints202605.1276.v1 Cited by: §1. Ye et al. (2023) J. Ye, Z. Wu, J. Feng, T. Yu, and L. Kong Compositional exemplars for in-context learning. In Proc. 40th Int. Conf. Mach. Learn. (ICML), p. 39818–39833. Cited by: §3.1. Yuan et al. (2025) M. Yuan et al. Automated composition of agents: a knapsack approach for agentic component selection. arXiv preprint arXiv:2510.16499. Cited by: §2.1. Zaheer et al. (2017) M. Zaheer, S. Kottur, S. Ravanbakhsh, B. Póczos, R. Salakhutdinov, and A. J. Smola Deep sets. In Adv. Neural Inf. Process. Syst. (NeurIPS), p. 3391–3401. Cited by: §5.2. Zeng et al. (2026) K. Zeng et al. Group of skills: group-structured skill retrieval for agent skill libraries. arXiv preprint arXiv:2605.06978. Cited by: §2.1. Zhang and Luo (2026) H. Zhang and W. Luo A streaming algorithm for non-monotone regularized submodular maximization. Oper. Res. Lett. 67, p. 107456. Cited by: §1, §2.2, §4.2. Zhang et al. (2025) Y. Zhang et al. Qwen3 embedding: advancing text embedding and reranking through foundation models. arXiv preprint arXiv:2506.05176. Cited by: §5.4. Zhao et al. (2026) X. Zhao et al. Generative skill composition for LLM agents. arXiv preprint arXiv:2606.32025. Cited by: §2.1. Zheng et al. (2026a) J. Zheng et al. SkillSelect-Serve: QoS-aware budgeted skill service recommendation for LLM agents. arXiv preprint arXiv:2607.00011. Cited by: §1, §2.1. Zheng et al. (2026b) Y. Zheng et al. SkillRouter: skill routing for LLM agents at scale. arXiv preprint arXiv:2603.22455. Cited by: §1, §1, §2.1, §4.2, §5.4. Zhuo et al. (2025) T. Y. Zhuo et al. BigCodeBench: benchmarking code generation with diverse function calls and complex instructions. In Proc. 13th Int. Conf. Learn. Represent. (ICLR), Cited by: §5.1. Appendix Appendix A Missing Proof in Section 4.3 Throughout the appendices we use the notation of Section 4.3: the seed J=t1,t2J=\t_1,t_2\ of (14), the residual function f of (15), the comparator residual P=T∖JP=T J with |T|≥4|T|≥ 4, the longest residual item v⋆v , the remainder R=P∖v⋆R=P \v \, the lengths p:=ℓ(v⋆)p:= (\v \) and r=ℓ(R)r= (R) of (17), the block order (X1,X2)(X_1,X_2) of (19) with dj=ℓ(Xj)d_j= (X_j) and densities ρ1=f(X1)/d1 _1=f(X_1)/d_1, ρ2=f(X2∣X1)/d2 _2=f(X_2 X_1)/d_2, the total residual length D=ℓ(P)=d1+d2D= (P)=d_1+d_2 of (21), the crossover point D1D_1, the bounding function φ of (22), the trajectory V of (18), and α=1−1/eα=1-1/e. Since |T|≥4|T|≥ 4 we have |P|≥2|P|≥ 2, so both blocks v⋆\v \ and R are nonempty; all item lengths are positive, hence p>0,r>0,d1>0,d2>0,D=p+r.p>0, r>0, d_1>0, d_2>0, D=p+r. (25) Recall from Section 4.3 that f is normalized (f(∅)=0f( )=0), nonnegative, nondecreasing, and submodular, and that submodularity with (19) gives ρ1≥ρ2≥0 _1≥ _2≥ 0. We first record two auxiliary lemmas whose proofs are elementary computations; both are used repeatedly below. Lemma 5 (Residual marginals and the trajectory). (i) For every U⊆[L]U [L] and v∈[L]v∈[L], f(v∣U)=G^(v∣J∪U)≥0f(v U)= G(v J∪ U)≥ 0. (i) V is continuous, piecewise affine, and nondecreasing on [0,ℓ(Am)][0, (A_m)]; it satisfies V(ℓ(Aj))=f(Aj)V( (A_j))=f(A_j) for every j, and it is defined on all of [0,r][0,r]. (i) Consider the chain step that selects aja_j from the state J∪Aj−1J∪ A_j-1, and let σj=f(aj∣Aj−1)/ℓaj _j=f(a_j A_j-1)/ _a_j denote its density. Then f(v∣Aj−1)/ℓ(v)≤σjf(v A_j-1)/ (\v\)≤ _j for every item v∉J∪Aj−1v∉ J∪ A_j-1 that is feasible at that step. Proof. (i) Expanding definition (15) twice, f(v∣U)=f(U∪v)−f(U)=(G^(J∪U∪v)−G^(J))−(G^(J∪U)−G^(J))=G^(v∣J∪U),f(v U)=f(U∪\v\)-f(U)= ( G(J∪ U∪\v\)- G(J) )- ( G(J∪ U)- G(J) )= G(v J∪ U), which is nonnegative because G G is nondecreasing. (i) By construction (18), V is affine on each segment [ℓ(Aj−1),ℓ(Aj)][ (A_j-1), (A_j)] with slope σj=f(aj∣Aj−1)/ℓaj _j=f(a_j A_j-1)/ _a_j, and its value at the right endpoint of segment j telescopes to V(ℓ(Aj))=f(Aj−1)+f(aj∣Aj−1)=f(Aj)V( (A_j))=f(A_j-1)+f(a_j A_j-1)=f(A_j), which equals the value used at the left endpoint of segment j+1j+1; hence V is continuous. Each slope satisfies σj≥0 _j≥ 0 by (i) and ℓaj>0 _a_j>0, so V is nondecreasing. Finally, ℓ(Am)≥r (A_m)≥ r by Lemma 1, so [0,r][0,r] lies in the domain of V. (i) Line 6 of Algorithm 1 selects, among all items i∉J∪Aj−1i∉ J∪ A_j-1 that are feasible at the current state S=J∪Aj−1S=J∪ A_j-1, one maximizing G^(i∣S)/ℓi G(i S)/ _i. By (i), G^(v∣J∪Aj−1)=f(v∣Aj−1) G(v J∪ A_j-1)=f(v A_j-1) for every such v, so maximizing the density with respect to G G is the same as maximizing it with respect to f; in particular the selected item aja_j satisfies f(v∣Aj−1)/ℓ(v)≤f(aj∣Aj−1)/ℓaj=σjf(v A_j-1)/ (\v\)≤ f(a_j A_j-1)/ _a_j= _j for every feasible v. ∎ Lemma 6 (Properties of the bounding function). The function φ of (22) satisfies: (i) φ(0)=0 (0)=0; this holds on the first branch when D1>0D_1>0 and on the second branch when D1=0D_1=0. (i) If 0<D1<+∞0<D_1<+∞, the two branches agree at u=D1u=D_1, so φ is continuous on [0,∞)[0,∞). (i) On the first branch (0,D1)(0,D_1), φ′(u)=(f(X1)−φ(u))/d1 (u)= (f(X_1)- (u) )/d_1; on the second branch (D1,∞)(D_1,∞), φ′(u)=(f(P)−φ(u))/D (u)= (f(P)- (u) )/D. Proof. We use throughout the chain-rule decomposition f(P)=f(X1)+f(X2∣X1)=f(X1)+ρ2d2=ρ1d1+ρ2d2.f(P)=f(X_1)+f(X_2 X_1)=f(X_1)+ _2d_2= _1d_1+ _2d_2. (26) (i) If D1>0D_1>0, the first branch gives φ(0)=f(X1)(1−e0)=0 (0)=f(X_1)(1-e^0)=0. If D1=0D_1=0, then by definition of D1D_1 we have ρ2>0 _2>0 and d1ln(ρ1/ρ2)=0d_1 ( _1/ _2)=0, hence ρ1=ρ2 _1= _2; the second branch then gives, using (26), φ(0)=f(P)−ρ2De0=ρ1d1+ρ2d2−ρ2(d1+d2)=0 (0)=f(P)- _2De^0= _1d_1+ _2d_2- _2(d_1+d_2)=0. (i) Let 0<D1<+∞0<D_1<+∞, so ρ2>0 _2>0 and e−D1/d1=ρ2/ρ1e^-D_1/d_1= _2/ _1. The left limit at D1D_1 along the first branch is f(X1)(1−e−D1/d1)=f(X1)(1−ρ2ρ1)=f(X1)−ρ2d1,f(X_1) (1-e^-D_1/d_1 )=f(X_1) (1- _2 _1 )=f(X_1)- _2d_1, where the last step uses f(X1)=ρ1d1f(X_1)= _1d_1. The value at D1D_1 on the second branch is f(P)−ρ2De0=f(P)−ρ2(d1+d2)f(P)- _2De^0=f(P)- _2(d_1+d_2), which equals f(X1)−ρ2d1f(X_1)- _2d_1 by (26). The two branches agree, and each branch is continuous, so φ is continuous. (i) On (0,D1)(0,D_1), differentiating φ(u)=f(X1)(1−e−u/d1) (u)=f(X_1)(1-e^-u/d_1) gives φ′(u)=f(X1)d1e−u/d1 (u)= f(X_1)d_1e^-u/d_1, while f(X1)−φ(u)=f(X1)e−u/d1f(X_1)- (u)=f(X_1)e^-u/d_1; dividing by d1d_1 matches. On (D1,∞)(D_1,∞), differentiating φ(u)=f(P)−ρ2Dexp(−u−D1D) (u)=f(P)- _2D (- u-D_1D ) gives φ′(u)=ρ2exp(−u−D1D) (u)= _2 (- u-D_1D ), while f(P)−φ(u)=ρ2Dexp(−u−D1D)f(P)- (u)= _2D (- u-D_1D ); dividing by D matches. ∎ A.1. Proof of Lemma 3 Proof. The proof has three steps: a density lower bound valid on every segment that starts before r (Step 1), a differential inequality for the difference W=V−φW=V- on each branch (Step 2), and a piecewise integrating-factor argument that propagates W≥0W≥ 0 across the finitely many breakpoints (Step 3). Step 4 checks that all placements of D1D_1 relative to [0,r][0,r] are covered. Step 1 (density lower bound). Fix an accepted segment starting at Aj−1A_j-1 with left endpoint u0=ℓ(Aj−1)<ru_0= (A_j-1)<r, and let σj=f(aj∣Aj−1)/ℓaj _j=f(a_j A_j-1)/ _a_j be the density of the item selected by Algorithm 1 on that segment. Let Q⊆PQ P be any set such that every member of Q∖Aj−1Q A_j-1 is feasible at this step; by Lemma 2, this holds for every Q⊆PQ P, since u0<ru_0<r. We claim f(Q)≤f(Aj−1∪Q)≤f(Aj−1)+∑v∈Q∖Aj−1f(v∣Aj−1)≤f(Aj−1)+σjℓ(Q).f(Q)\;≤\;f(A_j-1∪ Q)\;≤\;f(A_j-1)+\!\! _v∈ Q A_j-1\!\!f(v A_j-1)\;≤\;f(A_j-1)+ _j\, (Q). (27) The first inequality is monotonicity of f. For the second, enumerate Q∖Aj−1=v1,…,vsQ A_j-1=\v_1,…,v_s\ in an arbitrary order and telescope: f(Aj−1∪Q)−f(Aj−1)=∑k=1sf(vk∣Aj−1∪v1,…,vk−1)≤∑k=1sf(vk∣Aj−1),f(A_j-1∪ Q)-f(A_j-1)= _k=1^sf (v_k A_j-1∪\v_1,…,v_k-1\ )≤ _k=1^sf(v_k A_j-1), where each summand is bounded via submodularity of f (conditioning on a superset of Aj−1A_j-1 can only decrease the marginal). For the third inequality, every v∈Q∖Aj−1v∈ Q A_j-1 is feasible at this step, so Lemma 5(i) gives f(v∣Aj−1)≤σjℓ(v)f(v A_j-1)≤ _j (\v\); summing over Q∖Aj−1Q A_j-1 and using σj≥0 _j≥ 0 together with ℓ(Q∖Aj−1)≤ℓ(Q) (Q A_j-1)≤ (Q) (lengths are positive) yields the claim. Rearranging (27) and using ℓ(Q)>0 (Q)>0, σj≥f(Q)−f(Aj−1)ℓ(Q)≥f(Q)−V(u)ℓ(Q)for every u∈[ℓ(Aj−1),ℓ(Aj)], _j\;≥\; f(Q)-f(A_j-1) (Q)\;≥\; f(Q)-V(u) (Q) every u∈[ (A_j-1), (A_j)], (28) where the second inequality holds because V is nondecreasing (Lemma 5(i)) with V(ℓ(Aj−1))=f(Aj−1)V( (A_j-1))=f(A_j-1), so V(u)≥f(Aj−1)V(u)≥ f(A_j-1) on the whole segment. Since X1⊆PX_1 P and P⊆P P, inequality (28) is available both for Q=X1Q=X_1 and for Q=PQ=P on every segment starting before r. Step 2 (differential inequality on each branch). Consider the difference W(u):=V(u)−φ(u)W(u):=V(u)- (u) on [0,r][0,r]. Both V and φ are continuous (Lemma 5(i) and Lemma 6(i)), so W is continuous. Partition [0,min(r,D1)][0, (r,D_1)] (and, when D1<rD_1<r, also [D1,r][D_1,r]) by the finitely many trajectory breakpoints ℓ(A0)<ℓ(A1)<⋯ (A_0)< (A_1)<·s falling in the respective interval. On the interior of each cell of this partition, V is affine with V′(u)=σjV (u)= _j for the segment index j containing the cell, and φ is differentiable (Lemma 6(i)). First branch. Let u lie in the interior of a cell of [0,min(r,D1)][0, (r,D_1)]. The segment containing u has left endpoint u0≤u<ru_0≤ u<r, so (28) applies with Q=X1Q=X_1, and Lemma 6(i) gives the ODE for φ . Subtracting, W′(u)=V′(u)−φ′(u)≥f(X1)−V(u)d1−f(X1)−φ(u)d1=−W(u)d1.W (u)=V (u)- (u)\;≥\; f(X_1)-V(u)d_1- f(X_1)- (u)d_1\;=\;- W(u)d_1. (29) Second branch. Let D1<rD_1<r and let u lie in the interior of a cell of [D1,r][D_1,r]. Again the segment containing u has left endpoint u0<ru_0<r, so (28) applies with Q=PQ=P, and the same subtraction gives W′(u)≥f(P)−V(u)D−f(P)−φ(u)D=−W(u)D.W (u)\;≥\; f(P)-V(u)D- f(P)- (u)D\;=\;- W(u)D. (30) Step 3 (integrating factor and propagation across breakpoints). Fix a branch and write ℓQ _Q for its rate constant (ℓQ=d1 _Q=d_1 on the first branch, ℓQ=D _Q=D on the second). On the interior of each cell, du(eu/ℓQW(u))=eu/ℓQ(W′(u)+W(u)ℓQ)≥ 0 ddu (e^u/ _Q\,W(u) )=e^u/ _Q (W (u)+ W(u) _Q )\;≥\;0 (31) by (29) or (30). Hence eu/ℓQW(u)e^u/ _QW(u) is nondecreasing on the interior of each cell; since it is continuous on the whole branch interval and the partition has finitely many cells, it is nondecreasing on the entire branch interval. Therefore, if W≥0W≥ 0 at the left endpoint of the branch interval, then eu/ℓQW(u)≥0e^u/ _QW(u)≥ 0, hence W(u)≥0W(u)≥ 0, throughout that interval. It remains to check the left-endpoint values. On [0,min(r,D1)][0, (r,D_1)] the left endpoint is u=0u=0, where W(0)=V(0)−φ(0)=0−0=0W(0)=V(0)- (0)=0-0=0 by (18) and Lemma 6(i). On [D1,r][D_1,r] (when 0<D1<r0<D_1<r) the left endpoint is u=D1u=D_1, where the first-branch conclusion and continuity of W give W(D1)≥0W(D_1)≥ 0. When D1=0D_1=0, the left endpoint of the second-branch interval is u=0u=0, and Lemma 6(i) again gives W(0)=0W(0)=0. Step 4. If D1≥rD_1≥ r (including D1=+∞D_1=+∞, which occurs when ρ2=0 _2=0), then [0,r]⊆[0,min(r,D1)][0,r] [0, (r,D_1)] and the first-branch argument alone gives W≥0W≥ 0 on [0,r][0,r]. If D1=0D_1=0, then only the second branch is active on [0,r][0,r], with initial value W(0)=0W(0)=0. If 0<D1<r0<D_1<r, the first-branch argument gives W≥0W≥ 0 on [0,D1][0,D_1] and the second-branch argument extends it to [D1,r][D_1,r]. In every case V(u)≥φ(u)V(u)≥ (u) for all u∈[0,r]u∈[0,r], which is the claim of Lemma 3. ∎ A.2. Proof of Lemma 4 We use the following standard inequality; we include its one-line proof for completeness. Lemma 7 (Log-sum inequality). For positive reals a1,a2,b1,b2a_1,a_2,b_1,b_2, a1lnb1a1+a2lnb2a2≤(a1+a2)lnb1+b2a1+a2.a_1 b_1a_1+a_2 b_2a_2\;≤\;(a_1+a_2) b_1+b_2a_1+a_2. (32) Proof. Apply Jensen’s inequality to the concave function ln with weights λi=ai/(a1+a2) _i=a_i/(a_1+a_2) and points ui=bi/aiu_i=b_i/a_i: a1a1+a2lnb1a1+a2a1+a2lnb2a2≤ln(a1a1+a2⋅b1a1+a2a1+a2⋅b2a2)=lnb1+b2a1+a2. a_1a_1+a_2 b_1a_1+ a_2a_1+a_2 b_2a_2\;≤\; ( a_1a_1+a_2· b_1a_1+ a_2a_1+a_2· b_2a_2 )= b_1+b_2a_1+a_2. Multiplying both sides by a1+a2>0a_1+a_2>0 gives (32). ∎ Proof of Lemma 4. Abbreviate C:=G^(J)C:= G(J) and H:=G^(T)H:= G(T) for the duration of this proof. Since J∪P=TJ∪ P=T, definition (15) gives f(P)=G^(T)−G^(J)=H−C.f(P)= G(T)- G(J)=H-C. (33) Step 0 (reduction and common identities). If f(P)=0f(P)=0, then H=CH=C by (33), and since φ≥0 ≥ 0 (both branches of (22) are nonnegative: the first is a nonnegative multiple of 1−e−u/d1≥01-e^-u/d_1≥ 0, and the second is bounded below by its value at u=D1u=D_1, which equals the first-branch value f(X1)(1−e−D1/d1)≥0f(X_1)(1-e^-D_1/d_1)≥ 0 by Lemma 6(i)), C+φ(r)≥C=H≥αH.C+ (r)≥ C=H≥α H. Assume from now on that f(P)>0f(P)>0. Then ρ1>0 _1>0: otherwise f(X1)=0f(X_1)=0, and the block order (19) forces f(X2)≤d2d1f(X1)=0f(X_2)≤ d_2d_1f(X_1)=0, whence by submodularity f(X2∣X1)≤f(X2)=0f(X_2 X_1)≤ f(X_2)=0 and f(P)=f(X1)+f(X2∣X1)≤0f(P)=f(X_1)+f(X_2 X_1)≤ 0, a contradiction. Define (x,z)(x,z) according to the block order: (x,z)=(f(v⋆),f(R∣v⋆)),X1=v⋆,(f(v⋆∣R),f(R)),X1=R.(x,z)= cases (f(\v \),\;f(R \v \) ),&X_1=\v \,\\[3.00003pt] (f(v R),\;f(R) ),&X_1=R. cases (34) In both orders the chain rule gives x+z=f(P)x+z=f(P), so by (33), H=C+x+z.H=C+x+z. (35) In both orders we also have C≥2x.C≥ 2x. (36) Indeed, if X1=v⋆X_1=\v \ then x=f(v⋆)x=f(\v \) and (16) applies directly with v=v⋆v=v ; if X1=RX_1=R then submodularity gives x=f(v⋆∣R)≤f(v⋆)x=f(v R)≤ f(\v \), and (16) gives C≥2f(v⋆)≥2xC≥ 2f(\v \)≥ 2x. Finally, recall the block data in the two orders. If X1=v⋆X_1=\v \: d1=pd_1=p, d2=rd_2=r, ρ1=x/p _1=x/p, ρ2=z/r _2=z/r. If X1=RX_1=R: d1=rd_1=r, d2=pd_2=p, ρ1=z/r _1=z/r, ρ2=x/p _2=x/p. In both orders, whenever x,z>0x,z>0, d1lnρ1+d2lnρ2=plnxp+rlnzr,d_1 _1+d_2 _2\;=\;p xp+r zr, (37) because the two summands on the left are exactly the two summands on the right, possibly in the opposite order. We now distinguish the same three structural cases as the refined analysis of 24; Step 4 verifies that they are exhaustive. Step 1 (Case 1: r≥D1r≥ D_1). Since r<∞r<∞, the case condition forces D1<∞D_1<∞, hence ρ2>0 _2>0 by the definition of D1D_1, and with ρ1≥ρ2 _1≥ _2 both block values are positive; reading off the block data above, this means x>0andz>0x>0 z>0 in both orders, so every logarithm below has a strictly positive argument. Because r≥D1r≥ D_1, the second branch of (22) evaluates φ(r) (r), and by (33) and (35), C+φ(r)=C+f(P)−ρ2Dexp(−r−D1D)=H−ρ2Dexp(−r−D1D).C+ (r)=C+f(P)- _2D (- r-D_1D )=H- _2D (- r-D_1D ). (38) It therefore suffices to bound the exponential tail by H/eH/e. First, combining (36) with (35), H−z=C+x≥2x+x=3x.H-z=C+x≥ 2x+x=3x. (39) Next we bound the weighted-log expression (37). Using x≤(H−z)/3x≤(H-z)/3 from (39) and the monotonicity of ln , then splitting off ln3 3, then applying Lemma 7 with (a1,a2)=(p,r)(a_1,a_2)=(p,r) and (b1,b2)=(H−z,z)(b_1,b_2)=(H-z,z) (all four are positive, p+r=Dp+r=D, and (H−z)+z=H(H-z)+z=H), and finally using ln3>1 3>1 with p>0p>0: plnxp+rlnzr p xp+r zr ≤plnH−z3p+rlnzr ≤ p H-z3p+r zr (40) =−pln3+plnH−zp+rlnzr =-\,p 3+p H-zp+r zr ≤−pln3+DlnHD ≤-\,p 3+D HD ≤−p+DlnHD. ≤-\,p+D HD. Now rewrite the exponential tail. Using r=D−pr=D-p, ρ2Dexp(−r−D1D)=Dexp(lnρ2−D−p−D1D)=Dexp(−1+p+D1D+lnρ2), _2D (- r-D_1D )=D ( _2- D-p-D_1D )=D (-1+ p+D_1D+ _2 ), and since D1=d1ln(ρ1/ρ2)D_1=d_1 ( _1/ _2) and D=d1+d2D=d_1+d_2, D1D+lnρ2=d1lnρ1−d1lnρ2+Dlnρ2D=d1lnρ1+d2lnρ2D, D_1D+ _2= d_1 _1-d_1 _2+D _2D= d_1 _1+d_2 _2D, so that, by (37), ρ2Dexp(−r−D1D)=Dexp(−1+p+plnxp+rlnzrD). _2D (- r-D_1D )=D (-1+ p+p xp+r zrD ). (41) Substituting the bound (40) into (41) and using the monotonicity of exp , ρ2Dexp(−r−D1D)≤Dexp(−1+Dln(H/D)D)=D⋅1e⋅HD=He. _2D (- r-D_1D )\;≤\;D (-1+ D (H/D)D )=D· 1e· HD= He. (42) Combining (38) and (42), C+φ(r)≥H−He=αH.C+ (r)\;≥\;H- He\;=\;α H. The boundary subcases are included: r=D1r=D_1 uses the second branch of (22), which is defined for all u≥D1u≥ D_1, and D1=0D_1=0 poses no difficulty since only the case condition r≥D1r≥ D_1 was used. Step 2 (Case 2: r<D1r<D_1 and X1=v⋆X_1=\v \). Here x=f(v⋆)x=f(\v \), z=f(R∣v⋆)z=f(R \v \), d1=pd_1=p, and we write δ:=rp>0.δ:= rp>0. (43) Note x=ρ1p>0x= _1p>0 because ρ1>0 _1>0 (Step 0). Since r<D1r<D_1, the first branch of (22) evaluates φ(r) (r): φ(r)=x(1−e−r/p)=x(1−e−δ). (r)=x (1-e^-r/p )=x (1-e^-δ ). (44) Suppose first z>0z>0. Then ρ2=z/r>0 _2=z/r>0 and the case condition r<D1=plnx/pz/r<D_1=p x/pz/r can be divided by p>0p>0 to read δ<ln(xp⋅rz)=ln(xzδ).δ\;<\; ( xp· rz )\;=\; ( xz\,δ ). Exponentiating gives eδ<xzδe^δ< xzδ, i.e., x>zeδ.x\;>\;z\, e^δ. (45) We now chain the estimates; each line is justified below: C+φ(r) C+ (r) =C+x(1−e−δ) =C+x (1-e^-δ ) (46) =23(C+x)+[13(C+x)−xe−δ] = 23(C+x)+ [ 13(C+x)-xe^-δ ] ≥23(C+x)+x(1−e−δ) ≥ 23(C+x)+x (1-e^-δ ) >23(C+x)+zeδ−1δ > 23(C+x)+z\, e^δ-1δ ≥23(C+x)+z ≥ 23(C+x)+z ≥23(C+x+z)=23H>αH. ≥ 23(C+x+z)= 23H\;>\;α H. Line 2 only splits C+x=23(C+x)+13(C+x)C+x= 23(C+x)+ 13(C+x) and regroups. Line 3 uses (36): C≥2xC≥ 2x implies 13(C+x)≥x 13(C+x)≥ x, so the bracket is at least x−xe−δx-xe^-δ. Line 4 uses (45) together with 1−e−δ=e−δ(eδ−1)>01-e^-δ=e^-δ(e^δ-1)>0: x(1−e−δ)>zeδe−δ(eδ−1)=zeδ−1δ.x (1-e^-δ )\;>\;z\, e^δ\,e^-δ (e^δ-1 )\;=\;z\, e^δ-1δ. Line 5 uses the elementary inequality eδ≥1+δe^δ≥ 1+δ, which gives (eδ−1)/δ≥1(e^δ-1)/δ≥ 1, and z>0z>0. Line 6 uses z≥23z≥ 23z, and the final equality is (35). The last strict comparison uses e<3e<3: α=1−1/e<1−1/3=2/3α=1-1/e<1-1/3=2/3. If instead z=0z=0, no logarithm involving z is ever formed: lines 1–3 of (46) are unchanged and give C+φ(r)≥23(C+x)+x(1−e−δ)≥23(C+x)=23H>αH,C+ (r)\;≥\; 23(C+x)+x (1-e^-δ )\;≥\; 23(C+x)\;=\; 23H\;>\;α H, using x(1−e−δ)≥0x(1-e^-δ)≥ 0 and H=C+x+0H=C+x+0 from (35). Step 3 (Case 3: r<D1r<D_1 and X1=RX_1=R). Here z=f(R)z=f(R), x=f(v⋆∣R)x=f(v R), and d1=ℓ(R)=rd_1= (R)=r. Since r<D1r<D_1, the first branch of (22) evaluates φ(r) (r), and because the branch rate constant is d1=rd_1=r, φ(r)=f(X1)(1−e−r/d1)=z(1−e−1)=αz. (r)=f(X_1) (1-e^-r/d_1 )=z (1-e^-1 )=α z. (47) From (36), C≥2xC≥ 2x, hence 3C≥2C+2x3C≥ 2C+2x, i.e., C≥23(C+x)≥α(C+x),C\;≥\; 23(C+x)\;≥\;α(C+x), (48) where the second inequality again uses 23>α 23>α (from e<3e<3) and C+x≥0C+x≥ 0. Adding (47) and (48) and using (35), C+φ(r)≥α(C+x)+αz=α(C+x+z)=αH.C+ (r)\;≥\;α(C+x)+α z\;=\;α(C+x+z)\;=\;α H. Step 4. The reduction f(P)=0f(P)=0 was handled in Step 0, so assume f(P)>0f(P)>0. If D1≤rD_1≤ r — which includes D1=0D_1=0, since r>0r>0 by (25) — we are in Case 1. If r<D1r<D_1 — which includes D1=+∞D_1=+∞, i.e., ρ2=0 _2=0 — we are in Case 2 or Case 3 according to whether the block order puts v⋆\v \ or R first; these two options are exhaustive because (X1,X2)(X_1,X_2) is a permutation of (v⋆,R) (\v \,R ). In every case G^(J)+φ(r)≥αG^(T) G(J)+ (r)≥α G(T), which is the claim of Lemma 4. ∎