Optimal Skill Selection for LLM Agents with Provable Bicriteria Guarantees

arXiv preprint, August 21, 2026

Optimal Skill Selection for LLM Agents with Provable Bicriteria Guarantees

arXiv:2608.19993v1 [cs.AI] 20 Aug 2026

Yu Chen1,★, Ruishuo Chen1,★, Xun Wang1 , Zhuoran Li1 , and Longbo Huang1 # 1 Institute for Interdisciplinary Information Sciences, Tsinghua University # Correspondence: longbohuang@tsinghua.edu.cn ★ Equal contribution, listed in random order. 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-𝑘 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/𝑒, 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.

1. Introduction Large language model (LLM) agents increasingly rely on reusable skill documents to acquire task-specific capabilities beyond their parametric knowledge (Yang et al., 2026), and public skill registries already list tens of thousands of installable skills (Cho et al., 2026; Gao et al., 2026). Modern production agents such as Codex (OpenAI, 2026) and Claude Code (Anthropic, 2025) 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 (Cho et al., 2026; Zheng et al., 2026b), the metadata alone can exceed the available context budget, making exhaustive LLM-based selection infeasible (Gan & Sun, 2025). 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% as libraries grow (Song & Wei, 2026), and selected skills can even push success below the no-skill baseline on 13 of 87 benchmark tasks despite curation (Li et al., 2026b). 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 (Gan & Sun, 2025; Fore et al., 2024; Zheng et al., 2026b,a; Li et al., 2026c). 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-𝑘 (Qu et al., 2024; Li et al., 2026a), truncation (Liu et al., 2026), or greedy packing (Zheng

1

Optimal Skill Selection for LLM Agents

Skill Selection Paradigm

Skill Library pkzip_core

pk64_core

Zip API and semantics

Encode API and semantics

~210 Tokens

~240 Tokens

pk64_snip

pk64_extra

Encode API and similar semantics ~225 Tokens

Irrelevant API and similar semantics ~385 Tokens

Task: Complete a zip-then-encode pipeline. Zip

Encode

Input Select a set of skill

Skill Selection

0101 1010

Output

① Frozen Model

Skill 1

② Context Budget Skill 2

One Capability

Success Rate

Skill Selection Effect

Tokens

0%

pkzip_core

Redundant

210

pkzip_core

Complementary Success Rate pkzip_core

240

0%

pk64_core

pk64_core

pk64_core

Irrelevant pkzip_core

450

pk64_extra

Success Rate

+1pp

Tokens 675

94%

pk64_snip

Tokens

93%

LLM Executor

pk64_core

Success Rate 56%

-23pp

Tokens 835

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.

et al., 2026a), 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. Yet these capability relationships are critical to effective skill selection. Fig. 1 illustrates a common skill-selection paradigm for coding agents (OpenAI, 2026; Anthropic, 2025): 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 (Yang et al., 2025) 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% success rate. After both capabilities are covered, adding a redundant pk64_snip skill consumes 225 additional tokens but improves the success rate by only 1 percentage point, while adding a semantically related but task-irrelevant pk64_extra skill reduces it by 23 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 𝑆 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 𝐺 (𝑆) 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 ℓ ( 𝑆), and the total length must not exceed the available budget 𝐵. Skill selection therefore becomes maximizing this structured objective subject to the hard token budget with the form: max 𝐹 ( 𝑆) := 𝐺 (𝑆) − 𝜅ℓ ( 𝑆) .

𝑆:ℓ ( 𝑆 ) ≤ 𝐵

(1)

This problem, formalized in Section 3, is an instance of regularized submodular maximization under a knapsack constraint. 2

Optimal Skill Selection for LLM Agents 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/𝑒 unless P = NP (Feige, 1998). With the penalty, the objective may be negative, ruling out constant multiplicative approximation and motivating a bicriteria guarantee (Nikolakaki et al., 2021; Harshaw et al., 2019). Existing results for solving regularized submodular maximization with a hard budget constraint obtain weaker approximation coefficients (Gong et al., 2024; Guo et al., 2026; Zhang & Luo, 2026) or incur an additive precision-dependent loss (Perrault et al., 2021). Our result attains the best possible coefficient 1 − 1/𝑒 on the submodular benefit while preserving the full penalty, achieving a bicriteria (1 − 1/𝑒, 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/𝑒, 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/𝑒 (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.22–0.53 in measured task success, on 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 (Cho et al., 2026; Zheng et al., 2026b; Su et al., 2026; Xiao et al., 2026; Wang et al., 2026) narrow a large skill library to a candidate pool for downstream selection, following a pipeline inherited from tool use (Qin et al., 2024; Qu et al., 2024). SkillsInjector (Li et al., 2026c) learns how many skills to inject and renders them jointly; SkillSelect-Serve (Zheng et al., 2026a) greedily packs itemwise scores under token and deployment constraints; Graph-of-Skills (Liu et al., 2026) expands dependency-aware bundles under a context cap yet leaves its budgeted objective unsolved; GoSkills (Zeng et al., 2026) and SkillComposer (Zhao et al., 2026) 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 (Ghulyani et al., 2026) applies facility-location coverage to accumulated session content under a token knapsack, and the knapsack composer of (Yuan et al., 2025) 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 (Golrezaei et al., 2012; Poularakis et al., 2019). Skill selection re-instantiates it with the context window as the constraint. For the pure benefit objective, density greedy with size-three 3

Optimal Skill Selection for LLM Agents seed enumeration attains the tight 1 − 1/𝑒 (Sviridenko, 2004), and refined analyses shrink the enumerated seeds to size two (Kulik et al., 2021; Feldman et al., 2023). ParetoGreedy (Vombatkere & Terzi, 2026) 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 𝐺 − 𝜅ℓ at a fixed 𝜅. Maximizing this regularized objective, however, changes the problem’s character: it can be negative, which rules out any constant multiplicative approximation (Nikolakaki et al., 2021). Distorted greedy (Harshaw et al., 2019) achieves a (1 − 1/𝑒, 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 (Perrault et al., 2021) to our aligned objective gives (1 − 1/𝑒, 1) up to an additive 𝜅𝜖, paid with 𝑂 ( 𝐵/𝜖) budget levels. The budgeted-profit works reach (1/4, 1) (Gong et al., 2024) and ((1 − 1/𝑒)/2, 1/2) in near-linear time (Guo et al., 2026), and (1/8 − 𝜖, 1) in one streaming pass (Zhang & Luo, 2026). Our result attains (1 − 1/𝑒, 1) exactly, with none of these compromises, and the benefit coefficient 1 − 1/𝑒 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 L = { 𝑠1 , · · · , 𝑠𝐿 } denote the skill library, where 𝑠𝑖 is the 𝑖-th skill document. Given a query 𝑞, the selection stage chooses a subset of skills, indexed by 𝑆 ⊆ [ 𝐿], for a downstream executor 𝐸, held fixed throughout. With the documents of the selected skills injected into its context window, 𝐸 executes the query 𝑞 and produces an observable outcome 𝑌𝐸 ( 𝑞, 𝑆). We define the execution effect of skill set 𝑆 as   𝐹★𝐸 ( 𝑞, 𝑆) := 𝔼 𝑌𝐸 ( 𝑞, 𝑆) − 𝑌𝐸 ( 𝑞, ∅) . (2) 𝐹★𝐸 ( 𝑞, 𝑆) measures the performance improvement from injecting skill set 𝑆 into 𝐸’s context window, relative to running 𝐸 without any skills.

A natural formulation of the selection stage is to choose the skill index set 𝑆 that maximizes the execution effect 𝐹★𝐸 ( 𝑞, 𝑆). However, the execution effect 𝐹★𝐸 ( 𝑞, 𝑆) is a black-box function of the frozen executor 𝐸, the query 𝑞, and the skill set 𝑆. Therefore, we need a structured model to approximate the execution effect 𝐹★𝐸 ( 𝑞, 𝑆). In the following sections, we model the execution effect 𝐹★𝐸 ( 𝑞, 𝑆) 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 𝐸, 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 𝑞 (Didolkar et al., 2024; An et al., 2023; Xu et al., 2024) and complement those already supplied by the selected set 𝑆 (Gupta et al., 2023). (ii) More injected context is not uniformly beneficial: irrelevant content can distract execution (Shi et al., 2023), redundant items may add little marginal coverage (Gupta et al., 2023; Kumari et al., 2024), and longer inputs can reduce performance in some settings even when the relevant evidence is retrieved correctly (Liu et al., 2024). (iii) For a fixed executor and agent-framework configuration, the selected skill documents must fit within the residual context budget (Ye et al., 2023; Kumari et al., 2024; Qu et al., 2024). Guided by these observations, we build the structured model around a latent capability space. Observations (i) and (ii) shape the benefit side, while observations (ii) and (iii) shape the cost side. The following two paragraphs formalize the two sides in turn. Structured Capability Benefit Following observations (i) and (ii), we model the positive contribution of skills through a latent capability space with 𝑑 dimensions. For each skill 𝑠𝑖 ∈ L, we assume there exists a latent 4

Optimal Skill Selection for LLM Agents capability supply vector 𝒖𝑖 = (𝑢𝑖,1 , · · · , 𝑢𝑖,𝑑 ) ∈ ℝ+𝑑 , where 𝑢𝑖,𝑘 quantifies how much capability skill 𝑠𝑖 supplies in the 𝑘-th dimension, e.g., operating git or analyzing logs. To model the complementarity and redundancy among skills, we introduce a nondecreasing concave function ℎ𝑘 with ℎ𝑘 (0) =
0 that captures diminishing returns within the same capability dimension: for a skill set 𝑆, we Í use ℎ𝑘 𝑖 ∈ 𝑆 𝑢𝑖,𝑘 to represent the capability coverage of 𝑆 in the 𝑘-th dimension, so that supplies in the same dimension overlap redundantly while supplies in different dimensions remain complementary. For query 𝑞, we assume there exists a latent capability demand vector 𝒘𝑞 = ( 𝑤1𝑞 , · · · , 𝑤𝑑𝑞 ) ∈ ℝ+𝑑 that encodes the query’s demand for each capability dimension. We then model the gross benefit of injecting skill set 𝑆 into executor 𝐸 as a monotone submodular function ! 𝑑 ∑︁ ∑︁ 𝐸 𝑞 𝐸 𝐺 𝐸 ( 𝑞, 𝑆) := 𝜂𝑘 𝑤𝑘 · ℎ𝑘 𝜆 𝑘 𝑢𝑖,𝑘 , (3) 𝑖 ∈𝑆

𝑘=1

where 𝜂𝑘𝐸 ≥ 0 and 𝜆 𝑘𝐸 ≥ 0 are executor-specific parameters that calibrate 𝐸’s sensitivity to the 𝑘-th capability dimension. 𝐺 𝐸 ’s form aligns with the standard model of weighted coverage with diminishing returns in document summarization and data selection (Lin & Bilmes, 2011; Kirchhoff & Bilmes, 2014), with capability dimensions playing the role of features. Intuitively, 𝐺 𝐸 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 (ii), injected documents impose a cost that grows with context length. Assume each skill document 𝑠𝑖 has a token length ℓ𝑖 , the number of Í context-window tokens it occupies once injected, and write ℓ ( 𝑆) := 𝑖 ∈ 𝑆 ℓ𝑖 for the total token length of skill set 𝑆. We model the performance degradation caused by injecting 𝑆 as a linear penalty 𝑐 𝐸 ( 𝑆) := 𝜅 𝐸 · ℓ ( 𝑆) ,

(4)

where 𝜅𝐸 ≥ 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 (Gao et al., 2026), and focused skills outperform larger, exhaustive ones (Li et al., 2026b). Moreover, observation (iii) imposes a hard feasibility limit on skill selection. We take the budget 𝐵 to be the residual token budget available to skill documents in the agent framework. The hard budget defines the feasible family F𝐵 = {𝑆 ⊆ [ 𝐿] : ℓ ( 𝑆) ≤ 𝐵 } . (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, 𝐹 𝐸 ( 𝑞, 𝑆) := 𝐺 𝐸 ( 𝑞, 𝑆) − 𝑐 𝐸 ( 𝑆) ,

(6)

and the selection problem maximizes it over the feasible family: max 𝐹 𝐸 ( 𝑞, 𝑆) . 𝑆 ∈ F𝐵

(7)

Problem (7) is computationally hard: setting 𝜅𝐸 = 0 and specializing the responses ℎ𝑘 to truncated sums recovers budgeted maximum coverage (Khuller et al., 1999), an NP-hard slice of monotone submodular knapsack maximization (Sviridenko, 2004). Moreover, the penalty makes 𝐹 𝐸 non-monotone and possibly negative, ruling out any constant multiplicative approximation in polynomial time (Nikolakaki et al., 2021). Section 4 therefore develops an algorithm with a bicriteria guarantee that treats the benefit and the penalty asymmetrically.

5

Optimal Skill Selection for LLM Agents 3.3. Model Validity and Learnable Parameterization The structured objective (6) is built on latent quantities. Among its primitives, only the token length ℓ𝑖 for each skill document 𝑠𝑖 is observable. The capability supplies 𝒖𝑖 , the query demand 𝒘𝑞 , and the executor calibration parameters 𝜂𝑘𝐸 , 𝜆 𝑘𝐸 , 𝜅𝐸 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 𝑤𝑘𝑞 enters only through the product 𝜂𝑘𝐸 𝑤𝑘𝑞 , and the supply 𝑢𝑖,𝑘 only through 𝜆 𝑘𝐸 𝑢𝑖,𝑘 . Defining the effective demand and effective supply 𝑤 e𝑘 := 𝜂𝑘𝐸 𝑤𝑘 , 𝑞

𝑞

e 𝑢𝑖,𝑘 := 𝜆 𝑘𝐸 𝑢𝑖,𝑘 ,

∀𝑘 ∈ [ 𝑑 ] ,

(8)

Í Í the gross benefit (3) rewrites exactly as 𝐺 𝐸 ( 𝑞, 𝑆) = 𝑑𝑘=1 𝑤 e𝑘𝑞 ℎ𝑘 𝑖 ∈ 𝑆 e 𝑢𝑖,𝑘 . We therefore estimate the effective b𝐸 : 𝑞 ↦→ 𝒘 b𝑞 and a supply encoder quantities directly with two capability encoders: a demand encoder 𝜓 𝑞 𝑞 b𝐸 : 𝑠𝑖 ↦→ b b and b e and effective supply e 𝒖𝑖 are estimates of the effective demand 𝒘 𝒖𝑖 , respectively. 𝜙 𝒖𝑖 , where 𝒘 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 b 𝜅𝐸 jointly with the encoders on execution records ( 𝑞, 𝑆, 𝑌𝐸 ( 𝑞, 𝑆)) of the frozen executor. Inspired by (Iyer & Bilmes, 2015), we fix the saturating form ℎ𝑘 ( 𝑥 ) = 1 − 𝑒− 𝑥 , 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 b 𝐹 𝐸 ( 𝑞, 𝑆) denote the fitted objective, obtained by instantiating (6) with the encoder outputs and the calibrated b 𝜅𝐸 : * !+ ∑︁ b𝐸 ( 𝑞) , ℎ b𝐸 ( 𝑠𝑖 ) − b b 𝐹 𝐸 ( 𝑞, 𝑆) := 𝜓 𝜙 𝜅 𝐸 · ℓ ( 𝑆) , (9) 𝑖 ∈𝑆

where ℎ (·) applies { ℎ𝑘 } componentwise. At decision time, the selection layer solves the fitted selection problem, which is the deployable counterpart of (7) and is defined by 𝐹 𝐸 ( 𝑞, 𝑆) . max b 𝑆 ∈ F𝐵

(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 ( 𝑞, 𝐸, 𝐵), there exists 𝜀 ≥ 0 such that 𝐹★𝐸 ( 𝑞, 𝑆) − b 𝐹 𝐸 ( 𝑞, 𝑆) ≤ 𝜀 for all 𝑆 ∈ F𝐵 . 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 b 𝜅𝐸 . 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× as many parameters. Its fitted supplies also recover the true skill-capability coverage matrix, hidden from the fit: over the 155 (skill, capability) pairs, b 𝑢𝑖,𝑘 ranks a covered pair above an uncovered one 99.6% of the time (AUC 0.996, Fig. 2). Assumption 1 is therefore attainable on a real executor from pass/fail outcomes alone, with 281 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 Assumption 1, every b 𝑆 ∈ F𝐵 with b 𝐹 𝐸 ( 𝑞, b 𝑆) ≥ max𝑆 ∈ F𝐵 b 𝐹 𝐸 ( 𝑞, 𝑆) − 𝛿 satisfies max 𝐹★𝐸 ( 𝑞, 𝑇 ) − 𝐹★𝐸 ( 𝑞, b 𝑆) ≤ 2𝜀 + 𝛿. 𝑇 ∈ F𝐵

6

(11)

Optimal Skill Selection for LLM Agents

true coverage (hidden from the fit) pk64 pkbin pkzip pkdigest pkmac

1.0

fitted supply ui, k pk64 pkbin pkzip pkdigest pkmac

single-module docs

0.5

handbooks

distractors

0.0

Figure 2 | Parameter recovery. Top: the true skill-capability coverage matrix, hidden from the fit. Bottom: the fitted supply b 𝑢𝑖,𝑘 , 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 31 skills, rows the 5 capabilities. Both panels use the scale on the right, white = 0 to dark blue = 1; the bottom panel plots b 𝑢𝑖,𝑘 divided by its largest entry.

Proof. Let 𝑇 ★ maximize 𝐹★𝐸 ( 𝑞, ·) over F𝐵 . Then we have 𝐹★𝐸 ( 𝑞, 𝑇 ★) − 𝐹★𝐸 ( 𝑞, b 𝑆) ≤ b 𝐹 𝐸 ( 𝑞, 𝑇 ★) − b 𝐹 𝐸 ( 𝑞, b 𝑆) +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 𝑞, the frozen executor 𝐸, and the budget 𝐵, and suppress them b(𝑆) for the fitted capability benefit, b from the notation, writing 𝐺 𝜅 for the calibrated context sensitivity, and b b b is normalized (𝐺 b(∅) = 0), 𝐹 ( 𝑆) = 𝐺 ( 𝑆) −b 𝜅ℓ ( 𝑆) for the fitted objective defined in (9). Our analysis uses only that 𝐺 nondecreasing, and submodular, that all lengths ℓ𝑖 are positive, and that b 𝜅 ≥ 0. b−b b is monotone, b 𝐹 =𝐺 𝜅ℓ raises three difficulties at once. First, although 𝐺 𝐹 can be non-monotone The objective b 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 b 𝐹 . 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 b 𝐹 (Line 11). Algorithm 1 implements the standard partial-enumeration density greedy for monotone submodular knapsack (Khuller et al., 1999; Sviridenko, 2004; Kulik et al., 2021). Under a monotone benefit, the endpoint of each chain dominates all its prefixes, so the known 1 − 1/𝑒 analyses compare only chain endpoints. Under the

7

Optimal Skill Selection for LLM Agents Algorithm 1 Best Prefix Selection (BPS) b, fitted context sensitivity b Require: skill library L, budget 𝐵, fitted benefit oracle 𝐺 𝜅. Ensure: selected skill set 𝑆BPS . 1: Discard every skill 𝑖 with ℓ𝑖 > 𝐵; initialize the prefix pool P ← ∅. 2: for each seed 𝐴 ⊆ [ 𝐿] with | 𝐴 | ≤ 2 and ℓ ( 𝐴) ≤ 𝐵 do 3: 𝑆←𝐴 4: Add prefix 𝑆 to P. // each seed opens a prefix chain 5: while some 𝑖 ∉ 𝑆 fits, i.e., ℓ (𝑆) + ℓ𝑖 ≤ 𝐵 do  b({ 𝑖 }∪ 𝑆) − 𝐺 b(𝑆) /ℓ𝑖 6: 𝑖★ ← argmax𝑖∉𝑆, ℓ ( 𝑆 )+ℓ𝑖≤𝐵 𝐺 ★ 7: 𝑆 ← 𝑆 ∪ { 𝑖 }. 8: Add prefix 𝑆 to P. // record every prefix in chain 9: end while 10: end for 11: 𝑆BPS ← argmax𝑆 ∈ P b 𝐹 ( 𝑆). // choose the best prefix 12: return 𝑆BPS non-monotone fitted objective b 𝐹 , however, the endpoint need not be the best candidate, since the optimum can sit strictly inside a chain. Inspired by (Vombatkere & Terzi, 2026), we record every prefix and select the best one over the full collection by b 𝐹 ; this best-prefix selection step gives BPS its name. 4.2. Main Result: Bicriteria Approximation Guarantee Throughout, let 𝛼 = 1 − 1/𝑒. The theoretical guarantee for Algorithm 1 is given below. b be normalized (𝐺 b(∅) = 0), nondecreasing, Theorem 1 (Bicriteria (1 − 1/𝑒, 1)-approximation guarantee). Let 𝐺 and submodular, let ℓ𝑖 > 0 for all 𝑖 ∈ [ 𝐿], and let b 𝜅 ≥ 0. The BPS output 𝑆BPS of Algorithm 1 satisfies 𝑆BPS ∈ F𝐵 and b b(𝑇 ) − b 𝐹 ( 𝑆BPS ) ≥ 𝛼 𝐺 𝜅 ℓ (𝑇 )

∀𝑇 ∈ F𝐵 .

(12)

The guarantee (12) is a bicriteria approximation: the two coefficients are 𝛼 = 1 − 1/𝑒 on the benefit and 1 on the penalty, meaning that BPS recovers at least a (1 − 1/𝑒) fraction of any feasible set’s capability benefit while incurring its full context-length penalty. Tightness The benefit coefficient 𝛼 = 1 − 1/𝑒 in (12) cannot be improved under standard complexity assumptions (any (1 − 1/𝑒 + 𝜖)-approximation is NP-hard (Feige, 1998)). Theorem 1 provides a tight polynomialtime 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 (Gong et al., 2024; Guo et al., 2026; Zhang & Luo, 2026), an additive precision-dependent loss (Perrault et al., 2021), or a fractional output (Feldman, 2021). ParetoGreedy (Vombatkere & Terzi, 2026), whose candidate generation BPS shares, proves instance-dependent guarantees on the Pareto frontier, but none for the regularized objective at a fixed b 𝜅. 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 𝑆★ = argmax𝑇 ∈ F𝐵 𝐹★𝐸 ( 𝑞, 𝑇 ) denote the skill set maximizing the true execution effect. b(𝑆★), so the suboptimality of the BPS output is at most a 1/𝑒 Taking 𝑇 = 𝑆★ in (12) gives b 𝐹 ( 𝑆BPS ) ≥ b 𝐹 ( 𝑆★) − 1𝑒 𝐺 b(𝑆★). Combining Theorem 1 with the error transfer of Proposition 1 yields fraction of the optimum’s benefit 𝐺 an end-to-end bound on the true execution effect.

8

Optimal Skill Selection for LLM Agents Corollary 1 (Selection regret of BPS). Under Assumption 1, the BPS output 𝑆BPS satisfies 𝐹★𝐸 ( 𝑞, 𝑆★) − 𝐹★𝐸 ( 𝑞, 𝑆BPS ) ≤ 1b ★ 𝐺 ( 𝑆 ) + 2𝜀. 𝑒 Time Complexity Algorithm 1 runs in 𝑂 ( 𝑑𝐿4 ) time, where 𝑑 is the capability dimension and 𝐿 the library size: 𝑂 ( 𝐿2 ) seeds each grow a chain of at most 𝐿 density steps, and each step scans 𝑂 ( 𝐿) candidates at 𝑂 ( 𝑑 ) cost per marginal evaluation. In practice 𝐿 is the size of the shortlist left by a high-recall retrieval stage (Cho et al., 2026; Zheng et al., 2026b; Gan & Sun, 2025), not of the whole registry. 4.3. Proof of Theorem 1 For an arbitrary feasible set 𝑇 , the proof proceeds in three steps: (i) Construct a seed 𝐽 from 𝑇 ’s two highestmarginal items and define a residual benefit function 𝑓 . (ii) Lower-bound the trajectory function (18) of the density chain grown from 𝐽 by a piecewise-exponential bounding function 𝜑, adapting the refined analysis b( 𝐽 ) + 𝑉 ( 𝑟 ) ≥ 𝛼𝐺 b(𝑇 ). (iii) Convert this fractional bound into an actual of (Kulik et al., 2021), and establish 𝐺 recorded integral prefix via budget-aligned interpolation, and conclude via the b 𝐹 -maximization of Algorithm 1. 4.3.1

Seed construction and residual function

b( 𝑖 | 𝑆) = 𝐺 b(𝑆 ∪ { 𝑖 }) − 𝐺 b(𝑆) for the marginal benefit. We order the items of 𝑇 greedily by We first write 𝐺 nonincreasing marginal benefit with an arbitrary fixed tie-breaking rule:
b 𝑖 | {𝑡1 , · · · , 𝑡 𝑗 −1 } , 𝑡 𝑗 ∈ argmax 𝐺 𝑖 ∈ 𝑇 \{ 𝑡1 , ··· ,𝑡 𝑗 −1 } (13)
b 𝑚 𝑗 := 𝐺 𝑡 𝑗 | {𝑡1 , · · · , 𝑡 𝑗 −1 } , ∀ 𝑗 ∈ [|𝑇 |] . b(𝑇 ) − b b(𝑇 ) − b If |𝑇 | ≤ 2, then Algorithm 1 enumerates 𝑇 itself as a seed, and we have b 𝐹 (𝑇 ) = 𝐺 𝜅ℓ (𝑇 ) ≥ 𝛼𝐺 𝜅 ℓ (𝑇 ) . We set the feasible seed set 𝐽 with ℓ ( 𝐽 ) ≤ 𝐵 as 𝐽 := {𝑡1 , 𝑡2 } .

(14)

b( 𝐽 ) = 𝑚1 + 𝑚2 ≥ Then Algorithm 1 enumerates it in Line 2 and records it in Line 4, so 𝐽 ∈ P. If |𝑇 | = 3: 𝐺 2b 2 b b b ( 𝑚 + 𝑚 + 𝑚 ) = 𝐺 ( 𝑇 ) ≥ 𝛼 𝐺 ( 𝑇 ) and ℓ ( 𝐽 ) ≤ ℓ ( 𝑇 ) give 𝐹 ( 𝐽 ) ≥ 𝛼 𝐺 ( 𝑇 ) − b 𝜅 ℓ ( 𝑇 ). 1 2 3 3 3 In the following, we assume |𝑇 | ≥ 4. Our goal is to prove that on the chain grown from 𝐽 , some recorded prefix b(𝑇 ) − b 𝑆𝑇 satisfies b 𝐹 ( 𝑆𝑇 ) ≥ 𝛼𝐺 𝜅ℓ (𝑇 ). Inspired by the analysis in (Sviridenko, 2004), we define the residual function b( 𝐽 ∪ 𝑈 ) − 𝐺 b( 𝐽 ) , 𝑓 (𝑈 ) := 𝐺

∀𝑈 ⊆ [ 𝐿] .

(15)

b, 𝑓 is normalized ( 𝑓 (∅) = 0), nonnegative, nondecreasing, and submodular. Let 𝑃 = 𝑇 \ 𝐽 By the properties of 𝐺 b({ 𝑣} ∪ 𝐽 ) − 𝐺 b( 𝐽 ) = 𝐺 b( 𝑣 | 𝐽 ) ≤ 𝐺 b( 𝑣 | {𝑡1 }) ≤ denote the comparator residual. For every 𝑣 ∈ 𝑃 , we have 𝑓 ({ 𝑣}) = 𝐺 𝑚2 , where the first inequality uses submodularity and the second uses the greedy ordering (13). Therefore, we have b( 𝐽 ) = 𝐺 b({𝑡1 , 𝑡2 }) − 𝐺 b({𝑡1 }) + 𝐺 b({𝑡1 }) = 𝑚1 + 𝑚2 ≥ 2𝑚2 ≥ 2 𝑓 ({ 𝑣}) , ∀𝑣 ∈ 𝑃. (16) 𝐺 We choose 𝑣★ ∈ 𝑃 as the item with maximum token length, i.e., 𝑣★ = argmax𝑣 ∈ 𝑃 ℓ ({ 𝑣}). Set 𝑟 = ℓ ( 𝑃 \ { 𝑣★ }) .

(17)

Then we can show that the density chain starting with seed 𝐽 must have total token length larger than 𝑟 .

9

Optimal Skill Selection for LLM Agents 4.3.2

Bounding-function domination

Run the density chain of Algorithm 1 from seed 𝐽 , and let 𝐴0 = ∅ ⊊ 𝐴1 ⊊ · · · ⊊ 𝐴𝑚 be its accepted additions, so the actual recorded prefixes are 𝐽 ∪ 𝐴 𝑗 . Write 𝑎 𝑗 = 𝐴 𝑗 \ 𝐴 𝑗 −1 for the 𝑗-th accepted item. Following (Kulik et al., 2021), we define the piecewise-affine residual-benefit trajectory 𝑉 by 𝑉 (0) = 0 and, for ℓ ( 𝐴 𝑗 −1 ) ≤ 𝑢 ≤ ℓ ( 𝐴 𝑗 ), 𝑉 ( 𝑢) := 𝑓 ( 𝐴 𝑗 −1 ) + 𝑢 − ℓ ( 𝐴 𝑗 −1 )

𝑓 ( 𝑎 𝑗 | 𝐴 𝑗 −1 ) . ℓ ({ 𝑎 𝑗 })

(18)

The function 𝑉 : [0, ℓ ( 𝐴𝑚 )] → ℝ ≥0 traces the residual benefit accumulated by the density chain as a function of the total added length 𝑢 = ℓ ( 𝐴 𝑗 ) beyond the seed 𝐽 . At each breakpoint 𝑢 = ℓ ( 𝐴 𝑗 ), the trajectory evaluates to 𝑉 ( ℓ ( 𝐴 𝑗 )) = 𝑓 ( 𝐴 𝑗 ), the exact residual benefit of the 𝑗-th recorded prefix. Between consecutive breakpoints, 𝑉 interpolates linearly. Then we have the following lemmas. Lemma 1 (Trajectory coverage). 𝑉 ( 𝑟 ) is well-defined; that is, ℓ ( 𝐴𝑚 ) ≥ 𝑟 . Proof. If 𝑃 ⊆ 𝐴𝑚 , then ℓ ( 𝐴𝑚 ) ≥ ℓ ( 𝑃 ) > 𝑟 by definition in (17). Otherwise pick 𝑣 ∈ 𝑃 \ 𝐴𝑚 . When the chain stops, adding 𝑣 is infeasible. Then ℓ ( 𝐴𝑚 ) + ℓ ({ 𝑣}) > 𝐵 − ℓ ( 𝐽 ). Since ℓ ({ 𝑣}) ≤ ℓ ({ 𝑣★ }) and ℓ (𝑇 ) ≤ 𝐵, we have ℓ ( 𝐴𝑚 ) > 𝐵 − ℓ ( 𝐽 ) − ℓ ({ 𝑣}) ≥ ℓ (𝑇 ) − ℓ ( 𝐽 ) − ℓ ({ 𝑣★ }) = 𝑟 . □ Lemma 2 (Residual feasibility before 𝑟 ). Consider an accepted segment whose left endpoint 𝑢0 = ℓ ( 𝐴 𝑗 −1 ) satisfies 𝑢0 < 𝑟 . Then every item 𝑣 ∈ 𝑃 \ 𝐴 𝑗 −1 is feasible at that point. Proof. By maximality of ℓ ({ 𝑣★ }), we have ℓ ( 𝐴 𝑗 −1 ∪{ 𝑣}) = 𝑢0 + ℓ ({ 𝑣}) < 𝑟 + ℓ ({ 𝑣★ }) = ℓ ( 𝑃 ) = ℓ (𝑇 ) − ℓ ( 𝐽 ) ≤ 𝐵 − ℓ ( 𝐽 ). Therefore, 𝑣 is feasible at the selection on 𝑎 𝑗 . □ Lemma 2 is where removing the longest residual item pays off. We adapt the bounding-function technique of (Kulik et al., 2021). Partition 𝑃 into two nonempty blocks { 𝑣★ } and 𝑅 = 𝑃 \ { 𝑣★ }, and order them as ( 𝑋1 , 𝑋2 ) so that 𝑓 ( 𝑋1 ) 𝑓 ( 𝑋2 ) ≥ . ℓ ( 𝑋1 ) ℓ ( 𝑋2 )

(19)

Set 𝑑 𝑗 = ℓ ( 𝑋 𝑗 ) for 𝑗 = 1, 2, and define the block densities 𝜌1 =

𝑓 ( 𝑋1 ) , 𝑑1

𝜌2 =

𝑓 ( 𝑋2 | 𝑋1 ) , 𝑑2

(20)

where 𝑓 ( 𝑋2 | 𝑋1 ) = 𝑓 ( 𝑋1 ∪ 𝑋2 ) − 𝑓 ( 𝑋1 ). Submodularity and (19) give 𝜌1 ≥ 𝜌2 . Write (21)

𝐷 = ℓ ( 𝑃 ) = 𝑑1 + 𝑑2 .

If 𝜌2 > 0, let 𝐷1 = 𝑑1 ln 𝜌𝜌12 . If 𝜌2 = 0, set 𝐷1 = +∞. Define a continuous function 𝜑 : [0, ∞) → ℝ ≥0 by 𝜑 ( 𝑢) =

   𝑓 ( 𝑋1 ) (1 − exp(−   𝑢/𝑑1 )) ,  𝑢 − 𝐷1  ,  𝑓 ( 𝑃 ) − 𝜌2 𝐷 exp − 𝐷 

0 ≤ 𝑢 < 𝐷1 , 𝑢 ≥ 𝐷1 .

(22)

The bounding function 𝜑 is constructed so that: on the first branch, it tracks exponential saturation toward 𝑓 ( 𝑋1 ) at rate 1/𝑑1 ; on the second branch, it tracks saturation toward 𝑓 ( 𝑃 ) at rate 1/ 𝐷. The transition at 𝐷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 𝑟 , and a static half, showing that b(𝑇 ). And the proofs are computational and the seed and 𝜑 ( 𝑟 ) together already account for an 𝛼 fraction of 𝐺 deferred to Appendix A. Lemma 3 (Trajectory bound). 𝑉 ( 𝑢) ≥ 𝜑 ( 𝑢) , ∀𝑢 ∈ [0, 𝑟 ]. b( 𝐽 ) + 𝜑 ( 𝑟 ) ≥ 𝛼𝐺 b(𝑇 ). Lemma 4 (Static bound at 𝑟 ). 𝐺 10

Optimal Skill Selection for LLM Agents 4.3.3

Budget-aligned interpolation

Lemmas 3 and 4 give

(23)

b( 𝐽 ) + 𝑉 ( 𝑟 ) ≥ 𝐺 b( 𝐽 ) + 𝜑 ( 𝑟 ) ≥ 𝛼 𝐺 b(𝑇 ) . 𝐺

Choose consecutive recorded prefixes 𝐴 𝑗 −1 , 𝐴 𝑗 whose segment contains 𝑟 . There exists 𝜆 ∈ [0, 1] with 𝑉 ( 𝑟 ) = (1− 𝜆 ) 𝑓 ( 𝐴 𝑗 −1 ) + 𝜆 𝑓 ( 𝐴 𝑗 ) , and 𝑟 = (1− 𝜆 ) ℓ ( 𝐴 𝑗 −1 ) + 𝜆 ℓ ( 𝐴 𝑗 ). Because the penalty b 𝜅 ℓ (·) is the same linear function of the b( 𝐽 ) +𝑉 ( 𝑟 ) −b same length coordinate, the two interpolations combine: (1− 𝜆 ) b 𝐹 ( 𝐽 ∪ 𝐴 𝑗 −1 ) + 𝜆 b 𝐹 ( 𝐽 ∪ 𝐴 𝑗) = 𝐺 𝜅 ( ℓ ( 𝐽 ) + 𝑟 ). ★ b b b Since ℓ ( 𝐽 ) + 𝑟 = ℓ (𝑇 ) − ℓ ({ 𝑣 }) ≤ ℓ (𝑇 ), (23) gives (1 − 𝜆 ) 𝐹 ( 𝐽 ∪ 𝐴 𝑗 −1 ) + 𝜆 𝐹 ( 𝐽 ∪ 𝐴 𝑗 ) ≥ 𝛼𝐺 (𝑇 ) − b 𝜅 ( ℓ (𝑇 ) − ℓ ({ 𝑣★ })) ≥ b(𝑇 ) − b 𝛼𝐺 𝜅ℓ (𝑇 ). A convex combination of two numbers is at most their maximum, so at least one of the two recorded prefixes satisfies b b(𝑇 ) − b 𝐹 ( 𝐽 ∪ 𝐴𝑠 ) ≥ 𝛼𝐺 𝜅ℓ (𝑇 ) , 𝑠 ∈ { 𝑗 − 1, 𝑗 } . (24) b(𝑇 ) −b Therefore, in every case, some recorded candidate 𝑆𝑇 ∈ P satisfies b 𝐹 ( 𝑆𝑇 ) ≥ 𝛼 𝐺 𝜅 ℓ (𝑇 ). Since 𝑆BPS maximizes b b b 𝐹 over P (Line 11 of Algorithm 1), 𝐹 ( 𝑆BPS ) ≥ 𝐹 ( 𝑆𝑇 ). The seed and witness prefix depend on 𝑇 , but every seed of size at most two is enumerated and one selection maximizes b 𝐹 over all recorded candidates, so the single output 𝑆BPS satisfies (12) for every 𝑇 ∈ F𝐵 . 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 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% of runs on the original BigCodeBench (Zhuo et al., 2025) tasks from pretraining alone. We therefore build our own, and everything below rests on 63,596 executions of it against real test suites. Private modules We fork the benchmark, replacing its standard libraries with sixteen private modules over 𝑑 = 5 capability families. Each module’s call surface is unguessable from the task prose and documented only in the skill library (Fig. 3).

pretraining alone: 85% pass

Original task

dict

zlib.compress

b64encode

POST

swap libraries for private forks no skills injected: 0% pass

Forked task

dict

pkzip.lade

pk64.enrobe

POST

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.

Task admission A task is admitted only if the private-module solution passes its tests while both the standardlibrary 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 47 skill documents, of which 𝐿 = 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 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. 11

Optimal Skill Selection for LLM Agents

Prediction params chance

unseen doc

Selection

extrapolation

empirical ceiling

Ours 281

DeepSets 16.9k Datamodels 672 Additive fit 672 Shapley 651 Linear response 281 Set Transformer 16.6k

0.279 0.202 0.156 0.144 0.049

0.5

0.6

0.7

0.8

0.9

held-out ranking accuracy

0.0

0.2

0.4

0.674 0.640

0.6

0.8

success of selected sets

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.

Instantiation and fitting We set 𝑑 = 5, one dimension per module family, and fix ℎ𝑘 ( 𝑥 ) = 1 − 𝑒− 𝑥 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 b𝑞 per task, and nothing beyond the structured form (3): one supply vector b 𝒖𝑖 per skill, one demand vector 𝒘 one offset per task, 281 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 exp b 𝐹 𝐸 (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 (Ghorbani & Zou, 2019) do the same with values estimated from measured marginal contributions. Datamodels (Ilyas et al., 2022) regresses the measured rate on the set indicator. DeepSets (Zaheer et al., 2017) and Set Transformer (Lee et al., 2019) 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% of the empirical ceiling, and every interpretable alternative gives up at least 0.37 in absolute success. Only DeepSets remains competitive, at 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 80 instances of the fitted selection problem (10) span held-out tasks, token budget levels 𝐵, 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 { 𝑠𝑖 }, and never evaluate the set they assemble or charge for the tokens it costs: top-𝑘 relevance fills the budget in that order, while MMR (Carbonell & Goldstein, 1998) 12

Optimal Skill Selection for LLM Agents

100%

Best-of-100 Density greedy DPP-MAP MMR Top-k

45% 44% 7.5% 7.5% 7.5% 0

25

50

75

mean gap 0 0.03 0.05 3.51 3.69 4.36

0.8

measured success

BPS (ours)

100

0.6 Ours (lookup tables) Ours (neural encoder)

0.4

Executor self-select SkillRouter BM25 SkillRouter top-1 Dense retrieval Graph-of-Skills

0.2 0

instances solved to the exact optimum

300

600

tokens injected

900

1200

Figure 5 | The 80 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.

and DPP-MAP (Kulesza & Taskar, 2012) 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-100 random keeps the highest-scoring of 100 random budget-feasible sets. Solution quality BPS attains the exact optimum of (10) on all 80 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% and 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 80 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 (Su et al., 2026), rank the documents by their text against the task prompt and fill the budget in that order. SkillRouter (Zheng et al., 2026b) is a released retrieve-and-rerank router, which we run both at its own top-1 operating point and, more generously, in its reranked order up to our full budget; Graph-of-Skills (Liu et al., 2026) 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.20–0.43, between 0.30 and 0.53 below it, and BPS attains its own result on 28% fewer tokens than the strongest of them; the strongest deployed selector, the executor picking for itself, still gives up 0.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 (Zhang

13

Optimal Skill Selection for LLM Agents et al., 2025) embeddings of the task prompt and of each skill document into 64 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.68 measured success on 716 injected tokens (red star in Fig. 5): 0.05 below the lookup-table instantiation, and 0.17–0.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/𝑒, 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, S. et al. Skill-Based Few-Shot Selection for In-Context Learning. In Proc. 2023 Conf. Empirical Methods Natural Lang. Process. (EMNLP), pp. 13472–13492, 2023. Anthropic. Engineering

Equipping agents Blog, 2025.

for

the

real URL

world

with agent skills. Anthropic https://www.anthropic.com/engineering/ equipping-agents-for-the-real-world-with-agent-skills. Accessed 2026-07-23.

Carbonell, J. and Goldstein, J. 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, pp. 335–336, 1998. Cho, H., Kang, R., and Kim, Y. SkillRet: A large-scale benchmark for skill retrieval in LLM agents. arXiv preprint arXiv:2605.05726, 2026. Didolkar, A. et al. Metacognitive Capabilities of LLMs: An Exploration in Mathematical Problem Solving. In Adv. Neural Inf. Process. Syst. 37 (NeurIPS 2024), pp. 19783–19812, 2024. Feige, U. A threshold of ln n for approximating set cover. J. ACM, 45(4):634–652, 1998. Feldman, M. Guess free maximization of submodular and linear sums. Algorithmica, 83(3):853–878, 2021. Feldman, M., Nutov, Z., and Shoham, E. Practical budgeted submodular maximization. Algorithmica, 85(5): 1332–1371, 2023. Fore, M., Singh, S., and Stamoulis, D. GeckOpt: LLM system efficiency via intent-based tool selection. In Proc. Great Lakes Symp. VLSI (GLSVLSI), pp. 353–354, 2024. Gan, T. and Sun, Q. RAG-MCP: Mitigating prompt bloat in LLM tool selection via retrieval-augmented generation. arXiv preprint arXiv:2505.03275, 2025. Gao, Y., Li, Z., Yuan, Y., Ji, Z., Ma, P., and Wang, S. SkillReducer: Optimizing LLM agent skills for token efficiency. arXiv preprint arXiv:2603.29919, 2026. Ghorbani, A. and Zou, J. Data Shapley: Equitable valuation of data for machine learning. In Proc. 36th Int. Conf. Mach. Learn. (ICML), pp. 2242–2251, 2019. Ghulyani, M., Singh, A., Bharadwaj, K., Nath, A., and Goswami, S. PACMS: Submodular context selection as a pluggable engine for LLM agents. arXiv preprint arXiv:2606.20047, 2026. Golrezaei, N., Shanmugam, K., Dimakis, A. G., Molisch, A. F., and Caire, G. FemtoCaching: Wireless video content delivery through distributed caching helpers. In Proc. IEEE INFOCOM, pp. 1107–1115, 2012.

14

Optimal Skill Selection for LLM Agents Gong, S., Nong, Q., Wang, Y., and Du, D. Budget-constrained profit maximization without non-negative objective assumption in social networks. J. Glob. Optim., 90(4):1007–1030, 2024. Guo, Q., Feng, C., Shi, J., Tang, J., Zhou, X., and Wang, S. Efficient algorithms for budgeted profit maximization with theoretical guarantees. IEEE Trans. Knowl. Data Eng., 38(4):2234–2248, 2026. Gupta, S., Gardner, M., and Singh, S. Coverage-based example selection for in-context learning. In Findings Assoc. Comput. Linguistics: EMNLP 2023, 2023. Harshaw, C., Feldman, M., Ward, J., and Karbasi, A. Submodular maximization beyond non-negativity: Guarantees, fast algorithms, and applications. In Proc. 36th Int. Conf. Mach. Learn. (ICML), pp. 2634–2643, 2019. Ilyas, A., Park, S. M., Engstrom, L., Leclerc, G., and Madry, A. Datamodels: Understanding predictions with data and data with predictions. In Proc. 39th Int. Conf. Mach. Learn. (ICML), pp. 9525–9587, 2022. Iyer, R. and Bilmes, J. Submodular Point Processes with Applications to Machine learning. In Proc. 18th Int. Conf. Artif. Intell. Statist. (AISTATS), pp. 388–397, 2015. Khuller, S., Moss, A., and Naor, J. The budgeted maximum coverage problem. Inf. Process. Lett., 70(1):39–45, 1999. Kirchhoff, K. and Bilmes, J. Submodularity for data selection in machine translation. In Proc. 2014 Conf. Empirical Methods Natural Lang. Process. (EMNLP), pp. 131–141, 2014. Kulesza, A. and Taskar, B. Determinantal point processes for machine learning. Found. Trends Mach. Learn., 5 (2–3):123–286, 2012. Kulik, A., Schwartz, R., and Shachnai, H. A refined analysis of submodular greedy. Oper. Res. Lett., 49(4): 507–514, 2021. Kumari, L., Wang, S., Das, A., Zhou, T., and Bilmes, J. An end-to-end submodular framework for data-efficient in-context learning. In Findings Assoc. Comput. Linguistics: NAACL 2024, pp. 3293–3308, 2024. Lee, J., Lee, Y., Kim, J., Kosiorek, A. R., Choi, S., and Teh, Y. W. Set transformer: A framework for attentionbased permutation-invariant neural networks. In Proc. 36th Int. Conf. Mach. Learn. (ICML), pp. 3744–3753, 2019. Li, H. et al. Organizing, orchestrating, and benchmarking agent skills at ecosystem scale. arXiv preprint arXiv:2603.02176, 2026a. Li, X. et al. SkillsBench: Benchmarking how well agent skills work across diverse tasks. arXiv preprint arXiv:2602.12670, 2026b. Li, Y. et al. SkillsInjector: Dynamic skill context construction for LLM agents. arXiv preprint arXiv:2605.29794, 2026c. Lin, H. and Bilmes, J. A class of submodular functions for document summarization. In Proc. 49th Annu. Meeting Assoc. Comput. Linguistics (ACL), pp. 510–520, 2011. Liu, D. et al. Graph-of-Skills: Dependency-aware structural retrieval for massive agent skills. arXiv preprint arXiv:2604.05333, 2026. Liu, N. F. et al. Lost in the middle: How language models use long contexts. Trans. Assoc. Comput. Linguistics, 12:157–173, 2024. Nikolakaki, S. M., Ene, A., and Terzi, E. An efficient framework for balancing submodularity and cost. In Proc. 27th ACM SIGKDD Conf. Knowl. Discov. Data Min., pp. 1256–1266, 2021. OpenAI. Build skills. Codex Documentation, 2026. URL https://developers.openai.com/codex/ skills/. Accessed 2026-07-26. Perrault, P., Healey, J., Wen, Z., and Valko, M. On the approximation relationship between optimizing ratio of submodular (RS) and difference of submodular (DS) functions. arXiv preprint arXiv:2101.01631, 2021. 15

Optimal Skill Selection for LLM Agents Poularakis, K., Llorca, J., Tulino, A. M., Taylor, I., and Tassiulas, L. Joint service placement and request routing in multi-cell mobile edge computing networks. In Proc. IEEE INFOCOM, pp. 10–18, 2019. Qin, Y. et al. ToolLLM: Facilitating large language models to master 16000+ real-world APIs. In Proc. 12th Int. Conf. Learn. Represent. (ICLR), 2024. Qu, C. et al. Towards completeness-oriented tool retrieval for large language models. In Proc. ACM Int. Conf. Inf. Knowl. Manage. (CIKM), pp. 1930–1940, 2024. Shi, F. et al. Large language models can be easily distracted by irrelevant context. In Proc. 40th Int. Conf. Mach. Learn. (ICML), pp. 31210–31227, 2023. Song, H. and Wei, S. More skills, worse agents? skill shadowing degrades performance when expanding skill libraries. arXiv preprint arXiv:2605.24050, 2026. Su, W. et al. Skill retrieval augmentation for agentic AI. arXiv preprint arXiv:2604.24594, 2026. Sviridenko, M. A note on maximizing a submodular set function subject to a knapsack constraint. Oper. Res. Lett., 32(1):41–43, 2004. Vombatkere, K. and Terzi, E. Computing approximate pareto frontiers for submodular utility and cost tradeoffs. arXiv preprint arXiv:2602.15964, 2026. Wang, Z., Wen, W., Ji, Q., Qiao, R., and Sun, X. Skill is not document: A query-conditional benchmark and two-stage retriever for LLM agent skill routing. arXiv preprint arXiv:2606.03565, 2026. Xiao, J. et al. SkillSight: Calibrating generic content bias for skill retrieval. arXiv preprint arXiv:2607.18785, 2026. Xu, Z., Wang, H., Bespalov, D., Wu, X., Stone, P., and Qi, Y. LaRS: Latent Reasoning Skills for Chain-of-Thought Reasoning. In Findings Assoc. Comput. Linguistics: EMNLP 2024, pp. 3624–3643, 2024. Yang, A. et al. Qwen3 technical report. arXiv preprint arXiv:2505.09388, 2025. Yang, C. et al. A survey of agent skills: Toward procedural infrastructure for LLM agents. Preprints.org preprint, 2026. doi: 10.20944/preprints202605.1276.v1. Ye, J., Wu, Z., Feng, J., Yu, T., and Kong, L. Compositional exemplars for in-context learning. In Proc. 40th Int. Conf. Mach. Learn. (ICML), pp. 39818–39833, 2023. Yuan, M. et al. Automated composition of agents: A knapsack approach for agentic component selection. arXiv preprint arXiv:2510.16499, 2025. Zaheer, M., Kottur, S., Ravanbakhsh, S., Póczos, B., Salakhutdinov, R., and Smola, A. J. Deep sets. In Adv. Neural Inf. Process. Syst. (NeurIPS), pp. 3391–3401, 2017. Zeng, K. et al. Group of skills: Group-structured skill retrieval for agent skill libraries. arXiv preprint arXiv:2605.06978, 2026. Zhang, H. and Luo, W. A streaming algorithm for non-monotone regularized submodular maximization. Oper. Res. Lett., 67:107456, 2026. Zhang, Y. et al. Qwen3 embedding: Advancing text embedding and reranking through foundation models. arXiv preprint arXiv:2506.05176, 2025. Zhao, X. et al. Generative skill composition for LLM agents. arXiv preprint arXiv:2606.32025, 2026. Zheng, J. et al. SkillSelect-Serve: QoS-aware budgeted skill service recommendation for LLM agents. arXiv preprint arXiv:2607.00011, 2026a. Zheng, Y. et al. SkillRouter: Skill routing for LLM agents at scale. arXiv preprint arXiv:2603.22455, 2026b. Zhuo, T. Y. et al. BigCodeBench: Benchmarking code generation with diverse function calls and complex instructions. In Proc. 13th Int. Conf. Learn. Represent. (ICLR), 2025.

16

Optimal Skill Selection for LLM Agents

Appendix A Missing Proof in Section 4.3

18

A.1 Proof of Lemma 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 A.2 Proof of Lemma 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

17

Optimal Skill Selection for LLM Agents

A. Missing Proof in Section 4.3 Throughout the appendices we use the notation of Section 4.3: the seed 𝐽 = {𝑡1 , 𝑡2 } of (14), the residual function 𝑓 of (15), the comparator residual 𝑃 = 𝑇 \ 𝐽 with |𝑇 | ≥ 4, the longest residual item 𝑣★, the remainder 𝑅 = 𝑃 \ { 𝑣★ }, the lengths 𝑝 := ℓ ({ 𝑣★ }) and 𝑟 = ℓ ( 𝑅) of (17), the block order ( 𝑋1 , 𝑋2 ) of (19) with 𝑑 𝑗 = ℓ ( 𝑋 𝑗 ) and densities 𝜌1 = 𝑓 ( 𝑋1 )/𝑑1 , 𝜌2 = 𝑓 ( 𝑋2 | 𝑋1 )/𝑑2 , the total residual length 𝐷 = ℓ ( 𝑃 ) = 𝑑1 + 𝑑2 of (21), the crossover point 𝐷1 , the bounding function 𝜑 of (22), the trajectory 𝑉 of (18), and 𝛼 = 1 − 1/𝑒. Since |𝑇 | ≥ 4 we have | 𝑃 | ≥ 2, so both blocks { 𝑣★ } and 𝑅 are nonempty; all item lengths are positive, hence 𝑝 > 0,

𝑟 > 0,

𝑑1 > 0,

𝑑2 > 0,

(25)

𝐷 = 𝑝 + 𝑟.

Recall from Section 4.3 that 𝑓 is normalized ( 𝑓 (∅) = 0), nonnegative, nondecreasing, and submodular, and that submodularity with (19) gives 𝜌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). b( 𝑣 | 𝐽 ∪ 𝑈 ) ≥ 0. (i) For every 𝑈 ⊆ [ 𝐿] and 𝑣 ∈ [ 𝐿], 𝑓 ( 𝑣 | 𝑈 ) = 𝐺 (ii) 𝑉 is continuous, piecewise affine, and nondecreasing on [0, ℓ ( 𝐴𝑚 )]; it satisfies 𝑉 ( ℓ ( 𝐴 𝑗 )) = 𝑓 ( 𝐴 𝑗 ) for every 𝑗, and it is defined on all of [0, 𝑟 ]. (iii) Consider the chain step that selects 𝑎 𝑗 from the state 𝐽 ∪ 𝐴 𝑗 −1 , and let 𝜎 𝑗 = 𝑓 ( 𝑎 𝑗 | 𝐴 𝑗 −1 )/ℓ𝑎 𝑗 denote its density. Then 𝑓 ( 𝑣 | 𝐴 𝑗 −1 )/ℓ ({ 𝑣}) ≤ 𝜎 𝑗 for every item 𝑣 ∉ 𝐽 ∪ 𝐴 𝑗 −1 that is feasible at that step. Proof. (i) Expanding definition (15) twice,

b( 𝐽 ∪ 𝑈 ∪ { 𝑣}) − 𝐺 b( 𝐽 ) − 𝐺 b( 𝐽 ∪ 𝑈 ) − 𝐺 b( 𝐽 ) = 𝐺 b( 𝑣 | 𝐽 ∪ 𝑈 ) , 𝑓 ( 𝑣 | 𝑈 ) = 𝑓 (𝑈 ∪ { 𝑣}) − 𝑓 (𝑈 ) = 𝐺 b is nondecreasing. which is nonnegative because 𝐺 (ii) By construction (18), 𝑉 is affine on each segment [ ℓ ( 𝐴 𝑗 −1 ) , ℓ ( 𝐴 𝑗 )] with slope 𝜎 𝑗 = 𝑓 ( 𝑎 𝑗 | 𝐴 𝑗 −1 )/ℓ𝑎 𝑗 , and its value at the right endpoint of segment 𝑗 telescopes to 𝑉 ( ℓ ( 𝐴 𝑗 )) = 𝑓 ( 𝐴 𝑗 −1 ) + 𝑓 ( 𝑎 𝑗 | 𝐴 𝑗 −1 ) = 𝑓 ( 𝐴 𝑗 ), which equals the value used at the left endpoint of segment 𝑗 + 1; hence 𝑉 is continuous. Each slope satisfies 𝜎 𝑗 ≥ 0 by (i) and ℓ𝑎 𝑗 > 0, so 𝑉 is nondecreasing. Finally, ℓ ( 𝐴𝑚 ) ≥ 𝑟 by Lemma 1, so [0, 𝑟 ] lies in the domain of 𝑉 . (iii) Line 6 of Algorithm 1 selects, among all items 𝑖 ∉ 𝐽 ∪ 𝐴 𝑗 −1 that are feasible at the current state 𝑆 = 𝐽 ∪ 𝐴 𝑗 −1 , b( 𝑖 | 𝑆)/ℓ𝑖 . By (i), 𝐺 b( 𝑣 | 𝐽 ∪ 𝐴 𝑗 −1 ) = 𝑓 ( 𝑣 | 𝐴 𝑗 −1 ) for every such 𝑣, so maximizing the density one maximizing 𝐺 b is the same as maximizing it with respect to 𝑓 ; in particular the selected item 𝑎 𝑗 satisfies with respect to 𝐺 𝑓 ( 𝑣 | 𝐴 𝑗 −1 )/ℓ ({ 𝑣}) ≤ 𝑓 ( 𝑎 𝑗 | 𝐴 𝑗 −1 )/ℓ𝑎 𝑗 = 𝜎 𝑗 for every feasible 𝑣. □ Lemma 6 (Properties of the bounding function). The function 𝜑 of (22) satisfies: (i) 𝜑 (0) = 0; this holds on the first branch when 𝐷1 > 0 and on the second branch when 𝐷1 = 0. (ii) If 0 < 𝐷1 < +∞, the two branches agree at 𝑢 = 𝐷1 , so 𝜑 is continuous on [0, ∞).
′ ′ (iii) On the
first branch (0, 𝐷1 ), 𝜑 ( 𝑢) = 𝑓 ( 𝑋1 ) − 𝜑 ( 𝑢) /𝑑1 ; on the second branch ( 𝐷1 , ∞), 𝜑 ( 𝑢) = 𝑓 ( 𝑃 ) − 𝜑 ( 𝑢) / 𝐷. Proof. We use throughout the chain-rule decomposition 𝑓 ( 𝑃 ) = 𝑓 ( 𝑋1 ) + 𝑓 ( 𝑋2 | 𝑋1 ) = 𝑓 ( 𝑋1 ) + 𝜌2 𝑑2 = 𝜌1 𝑑1 + 𝜌2 𝑑2 .

(26)

(i) If 𝐷1 > 0, the first branch gives 𝜑 (0) = 𝑓 ( 𝑋1 ) (1 − 𝑒0 ) = 0. If 𝐷1 = 0, then by definition of 𝐷1 we have 𝜌2 > 0 and 𝑑1 ln( 𝜌1 / 𝜌2 ) = 0, hence 𝜌1 = 𝜌2 ; the second branch then gives, using (26), 𝜑 (0) = 𝑓 ( 𝑃 ) − 𝜌2 𝐷𝑒0 = 𝜌1 𝑑1 + 𝜌2 𝑑2 − 𝜌2 ( 𝑑1 + 𝑑2 ) = 0.

18

Optimal Skill Selection for LLM Agents (ii) Let 0 < 𝐷1 < +∞, so 𝜌2 > 0 and 𝑒− 𝐷1 /𝑑1 = 𝜌2 / 𝜌1 . The left limit at 𝐷1 along the first branch is 
𝜌2  𝑓 ( 𝑋1 ) 1 − 𝑒 − 𝐷1 /𝑑1 = 𝑓 ( 𝑋1 ) 1 − = 𝑓 ( 𝑋1 ) − 𝜌2 𝑑1 , 𝜌1

where the last step uses 𝑓 ( 𝑋1 ) = 𝜌1 𝑑1 . The value at 𝐷1 on the second branch is 𝑓 ( 𝑃 ) − 𝜌2 𝐷𝑒0 = 𝑓 ( 𝑃 ) − 𝜌2 ( 𝑑1 + 𝑑2 ), which equals 𝑓 ( 𝑋1 ) − 𝜌2 𝑑1 by (26). The two branches agree, and each branch is continuous, so 𝜑 is continuous. (iii) On (0, 𝐷1 ), differentiating 𝜑 ( 𝑢) = 𝑓 ( 𝑋1 ) (1 − 𝑒−𝑢/𝑑1 ) gives 𝜑′ ( 𝑢) = 𝑓 (𝑑𝑋11 ) 𝑒−𝑢/𝑑1 , while 𝑓 ( 𝑋1 ) − 𝜑 ( 𝑢) = 𝑢− 𝐷
𝑓 ( 𝑋1 ) 𝑒 −𝑢/𝑑1 ; dividing by 𝑑1 matches. On ( 𝐷1 , ∞), differentiating 𝜑 ( 𝑢) = 𝑓 ( 𝑃 ) − 𝜌2 𝐷 exp − 𝐷 1 gives 𝜑′ ( 𝑢) =

𝑢− 𝐷 𝑢− 𝐷 𝜌2 exp − 𝐷 1 , while 𝑓 ( 𝑃 ) − 𝜑 ( 𝑢) = 𝜌2 𝐷 exp − 𝐷 1 ; dividing by 𝐷 matches. □ A.1. Proof of Lemma 3 Proof. The proof has three steps: a density lower bound valid on every segment that starts before 𝑟 (Step 1), a differential inequality for the difference 𝑊 = 𝑉 − 𝜑 on each branch (Step 2), and a piecewise integratingfactor argument that propagates 𝑊 ≥ 0 across the finitely many breakpoints (Step 3). Step 4 checks that all placements of 𝐷1 relative to [0, 𝑟 ] are covered. Step 1 (density lower bound). Fix an accepted segment starting at 𝐴 𝑗 −1 with left endpoint 𝑢0 = ℓ ( 𝐴 𝑗 −1 ) < 𝑟 , and let 𝜎 𝑗 = 𝑓 ( 𝑎 𝑗 | 𝐴 𝑗 −1 )/ℓ𝑎 𝑗 be the density of the item selected by Algorithm 1 on that segment. Let 𝑄 ⊆ 𝑃 be any set such that every member of 𝑄 \ 𝐴 𝑗 −1 is feasible at this step; by Lemma 2, this holds for every 𝑄 ⊆ 𝑃 , since 𝑢0 < 𝑟 . We claim ∑︁ 𝑓 ( 𝑄 ) ≤ 𝑓 ( 𝐴 𝑗 −1 ∪ 𝑄 ) ≤ 𝑓 ( 𝐴 𝑗 −1 ) + 𝑓 ( 𝑣 | 𝐴 𝑗 −1 ) ≤ 𝑓 ( 𝐴 𝑗 −1 ) + 𝜎 𝑗 ℓ ( 𝑄 ) . (27) 𝑣 ∈ 𝑄 \ 𝐴 𝑗 −1

The first inequality is monotonicity of 𝑓 . For the second, enumerate 𝑄 \ 𝐴 𝑗 −1 = { 𝑣1 , . . . , 𝑣𝑠 } in an arbitrary order and telescope: 𝑓 ( 𝐴 𝑗 −1 ∪ 𝑄 ) − 𝑓 ( 𝐴 𝑗 −1 ) =

𝑠 ∑︁

𝑓 𝑣𝑘 | 𝐴 𝑗 −1 ∪ { 𝑣1 , . . . , 𝑣𝑘 −1 } ≤

𝑘=1

𝑠 ∑︁

𝑓 ( 𝑣𝑘 | 𝐴 𝑗 −1 ) ,

𝑘=1

where each summand is bounded via submodularity of 𝑓 (conditioning on a superset of 𝐴 𝑗 −1 can only decrease the marginal). For the third inequality, every 𝑣 ∈ 𝑄 \ 𝐴 𝑗 −1 is feasible at this step, so Lemma 5(iii) gives 𝑓 ( 𝑣 | 𝐴 𝑗 −1 ) ≤ 𝜎 𝑗 ℓ ({ 𝑣}); summing over 𝑄 \ 𝐴 𝑗 −1 and using 𝜎 𝑗 ≥ 0 together with ℓ ( 𝑄 \ 𝐴 𝑗 −1 ) ≤ ℓ ( 𝑄 ) (lengths are positive) yields the claim. Rearranging (27) and using ℓ ( 𝑄 ) > 0, 𝜎𝑗 ≥

𝑓 ( 𝑄 ) − 𝑓 ( 𝐴 𝑗 −1 ) ℓ (𝑄)

≥

𝑓 ( 𝑄 ) − 𝑉 ( 𝑢) ℓ (𝑄)

for every 𝑢 ∈ [ ℓ ( 𝐴 𝑗 −1 ) , ℓ ( 𝐴 𝑗 )] ,

(28)

where the second inequality holds because 𝑉 is nondecreasing (Lemma 5(ii)) with 𝑉 ( ℓ ( 𝐴 𝑗 −1 )) = 𝑓 ( 𝐴 𝑗 −1 ), so 𝑉 ( 𝑢) ≥ 𝑓 ( 𝐴 𝑗 −1 ) on the whole segment. Since 𝑋1 ⊆ 𝑃 and 𝑃 ⊆ 𝑃 , inequality (28) is available both for 𝑄 = 𝑋1 and for 𝑄 = 𝑃 on every segment starting before 𝑟 . Step 2 (differential inequality on each branch). Consider the difference 𝑊 (𝑢) := 𝑉 (𝑢) − 𝜑 ( 𝑢) on [0, 𝑟 ]. Both 𝑉 and 𝜑 are continuous (Lemma 5(ii) and Lemma 6(ii)), so 𝑊 is continuous. Partition [0, min( 𝑟, 𝐷1 )] (and, when 𝐷1 < 𝑟 , also [ 𝐷1 , 𝑟 ]) by the finitely many trajectory breakpoints ℓ ( 𝐴0 ) < ℓ ( 𝐴1 ) < · · · falling in the respective interval. On the interior of each cell of this partition, 𝑉 is affine with 𝑉 ′ ( 𝑢) = 𝜎 𝑗 for the segment index 𝑗 containing the cell, and 𝜑 is differentiable (Lemma 6(iii)). First branch. Let 𝑢 lie in the interior of a cell of [0, min( 𝑟, 𝐷1 )]. The segment containing 𝑢 has left endpoint 𝑢0 ≤ 𝑢 < 𝑟 , so (28) applies with 𝑄 = 𝑋1 , and Lemma 6(iii) gives the ODE for 𝜑. Subtracting, 𝑊 ′ ( 𝑢) = 𝑉 ′ ( 𝑢) − 𝜑′ ( 𝑢) ≥

𝑓 ( 𝑋1 ) − 𝑉 ( 𝑢) 𝑓 ( 𝑋1 ) − 𝜑 ( 𝑢) 𝑊 ( 𝑢) − = − . 𝑑1 𝑑1 𝑑1

19

(29)

Optimal Skill Selection for LLM Agents Second branch. Let 𝐷1 < 𝑟 and let 𝑢 lie in the interior of a cell of [ 𝐷1 , 𝑟 ]. Again the segment containing 𝑢 has left endpoint 𝑢0 < 𝑟 , so (28) applies with 𝑄 = 𝑃 , and the same subtraction gives 𝑊 ′ ( 𝑢) ≥

𝑓 ( 𝑃 ) − 𝑉 ( 𝑢) 𝑓 ( 𝑃 ) − 𝜑 ( 𝑢) 𝑊 ( 𝑢) − = − . 𝐷 𝐷 𝐷

(30)

Step 3 (integrating factor and propagation across breakpoints). Fix a branch and write ℓ𝑄 for its rate constant (ℓ𝑄 = 𝑑1 on the first branch, ℓ𝑄 = 𝐷 on the second). On the interior of each cell,   d  𝑢/ℓ𝑄 𝑊 ( 𝑢)  𝑒 𝑊 ( 𝑢) = 𝑒𝑢/ℓ𝑄 𝑊 ′ ( 𝑢) + ≥ 0 d𝑢 ℓ𝑄

(31)

by (29) or (30). Hence 𝑒𝑢/ℓ𝑄 𝑊 (𝑢) 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 𝑊 ≥ 0 at the left endpoint of the branch interval, then 𝑒𝑢/ℓ𝑄 𝑊 (𝑢) ≥ 0, hence 𝑊 (𝑢) ≥ 0, throughout that interval. It remains to check the left-endpoint values. On [0, min( 𝑟, 𝐷1 )] the left endpoint is 𝑢 = 0, where 𝑊 (0) = 𝑉 (0) − 𝜑 (0) = 0 − 0 = 0 by (18) and Lemma 6(i). On [ 𝐷1 , 𝑟 ] (when 0 < 𝐷1 < 𝑟 ) the left endpoint is 𝑢 = 𝐷1 , where the first-branch conclusion and continuity of 𝑊 give 𝑊 ( 𝐷1 ) ≥ 0. When 𝐷1 = 0, the left endpoint of the second-branch interval is 𝑢 = 0, and Lemma 6(i) again gives 𝑊 (0) = 0. Step 4. If 𝐷1 ≥ 𝑟 (including 𝐷1 = +∞, which occurs when 𝜌2 = 0), then [0, 𝑟 ] ⊆ [0, min( 𝑟, 𝐷1 )] and the firstbranch argument alone gives 𝑊 ≥ 0 on [0, 𝑟 ]. If 𝐷1 = 0, then only the second branch is active on [0, 𝑟 ], with initial value 𝑊 (0) = 0. If 0 < 𝐷1 < 𝑟 , the first-branch argument gives 𝑊 ≥ 0 on [0, 𝐷1 ] and the second-branch argument extends it to [ 𝐷1 , 𝑟 ]. In every case 𝑉 ( 𝑢) ≥ 𝜑 (𝑢) for all 𝑢 ∈ [0, 𝑟 ], 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 𝑎1 , 𝑎2 , 𝑏1 , 𝑏2 , 𝑎1 ln

𝑏2 𝑏1 + 𝑏2 𝑏1 + 𝑎2 ln ≤ ( 𝑎1 + 𝑎2 ) ln . 𝑎1 𝑎2 𝑎1 + 𝑎 2

(32)

Proof. Apply Jensen’s inequality to the concave function ln with weights 𝜆 𝑖 = 𝑎𝑖 /( 𝑎1 + 𝑎2 ) and points 𝑢𝑖 = 𝑏𝑖 /𝑎𝑖 : 𝑎1 𝑎1 + 𝑎 2

ln

 𝑎 𝑏1 𝑎2 𝑏2 𝑏1 𝑎2 𝑏2  𝑏1 + 𝑏2 1 + ln ≤ ln · + · = ln . 𝑎1 𝑎1 + 𝑎 2 𝑎2 𝑎1 + 𝑎 2 𝑎1 𝑎1 + 𝑎 2 𝑎2 𝑎1 + 𝑎 2

Multiplying both sides by 𝑎1 + 𝑎2 > 0 gives (32).

□

b( 𝐽 ) and 𝐻 := 𝐺 b(𝑇 ) for the duration of this proof. Since 𝐽 ∪ 𝑃 = 𝑇 , definition Proof of Lemma 4. Abbreviate 𝐶 := 𝐺 (15) gives b(𝑇 ) − 𝐺 b( 𝐽 ) = 𝐻 − 𝐶. 𝑓 ( 𝑃) = 𝐺 (33) Step 0 (reduction and common identities). If 𝑓 ( 𝑃 ) = 0, then 𝐻 = 𝐶 by (33), and since 𝜑 ≥ 0 (both branches of (22) are nonnegative: the first is a nonnegative multiple of 1 − 𝑒−𝑢/𝑑1 ≥ 0, and the second is bounded below by its value at 𝑢 = 𝐷1 , which equals the first-branch value 𝑓 ( 𝑋1 ) (1 − 𝑒− 𝐷1 /𝑑1 ) ≥ 0 by Lemma 6(ii)), 𝐶 + 𝜑 ( 𝑟 ) ≥ 𝐶 = 𝐻 ≥ 𝛼𝐻.

Assume from now on that 𝑓 ( 𝑃 ) > 0. Then 𝜌1 > 0: otherwise 𝑓 ( 𝑋1 ) = 0, and the block order (19) forces 𝑑 𝑓 ( 𝑋2 ) ≤ 𝑑2 𝑓 ( 𝑋1 ) = 0, whence by submodularity 𝑓 ( 𝑋2 | 𝑋1 ) ≤ 𝑓 ( 𝑋2 ) = 0 and 𝑓 ( 𝑃 ) = 𝑓 ( 𝑋1 ) + 𝑓 ( 𝑋2 | 𝑋1 ) ≤ 0, a 1 contradiction.

20

Optimal Skill Selection for LLM Agents Define ( 𝑥, 𝑧 ) according to the block order: ( ( 𝑥, 𝑧 ) =

𝑓 ({ 𝑣★ }) , 𝑓 ( 𝑅 | { 𝑣★ }) ,

𝑓 ( 𝑣★ | 𝑅) , 𝑓 ( 𝑅) ,

𝑋1 = { 𝑣★ },

(34)

𝑋1 = 𝑅.

In both orders the chain rule gives 𝑥 + 𝑧 = 𝑓 ( 𝑃 ), so by (33), (35)

𝐻 = 𝐶 + 𝑥 + 𝑧.

In both orders we also have

𝐶 ≥ 2 𝑥.

(36)

Indeed, if 𝑋1 = { 𝑣 } then 𝑥 = 𝑓 ({ 𝑣 }) and (16) applies directly with 𝑣 = 𝑣 ; if 𝑋1 = 𝑅 then submodularity gives 𝑥 = 𝑓 ( 𝑣★ | 𝑅) ≤ 𝑓 ({ 𝑣★ }), and (16) gives 𝐶 ≥ 2 𝑓 ({ 𝑣★ }) ≥ 2 𝑥 . ★

★

★

Finally, recall the block data in the two orders. If 𝑋1 = { 𝑣★ }: 𝑑1 = 𝑝, 𝑑2 = 𝑟 , 𝜌1 = 𝑥 / 𝑝, 𝜌2 = 𝑧 /𝑟 . If 𝑋1 = 𝑅: 𝑑1 = 𝑟 , 𝑑2 = 𝑝, 𝜌1 = 𝑧 /𝑟 , 𝜌2 = 𝑥 / 𝑝. In both orders, whenever 𝑥, 𝑧 > 0, 𝑑1 ln 𝜌1 + 𝑑2 ln 𝜌2 = 𝑝 ln

𝑥 𝑧 + 𝑟 ln , 𝑝 𝑟

(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 (Kulik et al., 2021); Step 4 verifies that they are exhaustive. Step 1 (Case 1: 𝑟 ≥ 𝐷1 ). Since 𝑟 < ∞, the case condition forces 𝐷1 < ∞, hence 𝜌2 > 0 by the definition of 𝐷1 , and with 𝜌1 ≥ 𝜌2 both block values are positive; reading off the block data above, this means 𝑥>0

and

𝑧>0

in both orders, so every logarithm below has a strictly positive argument. Because 𝑟 ≥ 𝐷1 , the second branch of (22) evaluates 𝜑 ( 𝑟 ), and by (33) and (35),  𝑟−𝐷  1

𝐶 + 𝜑 ( 𝑟 ) = 𝐶 + 𝑓 ( 𝑃 ) − 𝜌2 𝐷 exp −

𝐷

 𝑟−𝐷  1 = 𝐻 − 𝜌2 𝐷 exp − . 𝐷

(38)

It therefore suffices to bound the exponential tail by 𝐻 /𝑒. First, combining (36) with (35),

𝐻 − 𝑧 = 𝐶 + 𝑥 ≥ 2 𝑥 + 𝑥 = 3 𝑥.

(39)

Next we bound the weighted-log expression (37). Using 𝑥 ≤ ( 𝐻 − 𝑧 )/3 from (39) and the monotonicity of ln, then splitting off ln 3, then applying Lemma 7 with ( 𝑎1 , 𝑎2 ) = ( 𝑝, 𝑟 ) and ( 𝑏1 , 𝑏2 ) = ( 𝐻 − 𝑧, 𝑧 ) (all four are positive, 𝑝 + 𝑟 = 𝐷, and ( 𝐻 − 𝑧 ) + 𝑧 = 𝐻 ), and finally using ln 3 > 1 with 𝑝 > 0: 𝑝 ln

𝑥 𝑧 𝐻−𝑧 𝑧 + 𝑟 ln ≤ 𝑝 ln + 𝑟 ln 𝑝 𝑟 3𝑝 𝑟 𝐻−𝑧 𝑧 = − 𝑝 ln 3 + 𝑝 ln + 𝑟 ln 𝑝 𝑟 𝐻 ≤ − 𝑝 ln 3 + 𝐷 ln 𝐷 𝐻 ≤ − 𝑝 + 𝐷 ln . 𝐷

(40)

Now rewrite the exponential tail. Using 𝑟 = 𝐷 − 𝑝,  𝑟−𝐷  1

𝜌2 𝐷 exp −

𝐷

   𝐷 − 𝑝 − 𝐷1  𝑝 + 𝐷1 = 𝐷 exp ln 𝜌2 − = 𝐷 exp −1 + + ln 𝜌2 , 𝐷

21

𝐷

Optimal Skill Selection for LLM Agents and since 𝐷1 = 𝑑1 ln( 𝜌1 / 𝜌2 ) and 𝐷 = 𝑑1 + 𝑑2 , 𝐷1 𝑑1 ln 𝜌1 − 𝑑1 ln 𝜌2 + 𝐷 ln 𝜌2 𝑑1 ln 𝜌1 + 𝑑2 ln 𝜌2 + ln 𝜌2 = = , 𝐷 𝐷 𝐷

so that, by (37),  𝑟−𝐷  1

𝜌2 𝐷 exp −

𝐷

 𝑝 + 𝑝 ln 𝑥𝑝 + 𝑟 ln 𝑧𝑟  = 𝐷 exp −1 + .

(41)

𝐷

Substituting the bound (40) into (41) and using the monotonicity of exp,  𝑟−𝐷  1

𝜌2 𝐷 exp −

𝐷

 𝐷 ln( 𝐻 / 𝐷)  1 𝐻 𝐻 ≤ 𝐷 exp −1 + =𝐷· · = . 𝐷

𝑒

𝐷

𝑒

(42)

Combining (38) and (42), 𝐶 + 𝜑 ( 𝑟) ≥ 𝐻 −

𝐻 = 𝛼𝐻. 𝑒

The boundary subcases are included: 𝑟 = 𝐷1 uses the second branch of (22), which is defined for all 𝑢 ≥ 𝐷1 , and 𝐷1 = 0 poses no difficulty since only the case condition 𝑟 ≥ 𝐷1 was used. Step 2 (Case 2: 𝑟 < 𝐷1 and 𝑋1 = { 𝑣★ }). Here 𝑥 = 𝑓 ({ 𝑣★ }), 𝑧 = 𝑓 ( 𝑅 | { 𝑣★ }), 𝑑1 = 𝑝, and we write 𝛿 :=

𝑟 > 0. 𝑝

(43)

Note 𝑥 = 𝜌1 𝑝 > 0 because 𝜌1 > 0 (Step 0). Since 𝑟 < 𝐷1 , the first branch of (22) evaluates 𝜑 ( 𝑟 ):

𝜑 ( 𝑟 ) = 𝑥 1 − 𝑒− 𝑟/ 𝑝 = 𝑥 1 − 𝑒− 𝛿 .

(44)

Suppose first 𝑧 > 0. Then 𝜌2 = 𝑧/𝑟 > 0 and the case condition 𝑟 < 𝐷1 = 𝑝 ln 𝑥𝑧//𝑟𝑝 can be divided by 𝑝 > 0 to read 𝛿 < ln

𝑥 𝑝

·

𝑥  𝑟 = ln 𝛿 . 𝑧 𝑧

Exponentiating gives 𝑒𝛿 < 𝑥𝑧 𝛿, i.e., 𝑥 > 𝑧

𝑒𝛿 . 𝛿

(45)

We now chain the estimates; each line is justified below: 𝐶 + 𝜑 ( 𝑟) = 𝐶 + 𝑥 1 − 𝑒−𝛿

= 23 ( 𝐶 + 𝑥 ) +

h

−𝛿 1 3 ( 𝐶 + 𝑥 ) − 𝑥𝑒

≥ 23 ( 𝐶 + 𝑥 ) + 𝑥 1 − 𝑒−𝛿 > 32 ( 𝐶 + 𝑥 ) + 𝑧

i

𝑒𝛿 − 1 𝛿

(46)

≥ 23 ( 𝐶 + 𝑥 ) + 𝑧

≥ 23 ( 𝐶 + 𝑥 + 𝑧 ) = 23 𝐻 > 𝛼𝐻.

Line 2 only splits 𝐶 + 𝑥 = 32 ( 𝐶 + 𝑥 ) + 13 ( 𝐶 + 𝑥 ) and regroups. Line 3 uses (36): 𝐶 ≥ 2 𝑥 implies 13 ( 𝐶 + 𝑥 ) ≥ 𝑥 , so the bracket is at least 𝑥 − 𝑥𝑒−𝛿 . Line 4 uses (45) together with 1 − 𝑒−𝛿 = 𝑒−𝛿 ( 𝑒𝛿 − 1) > 0: 𝑥 1 − 𝑒−𝛿

> 𝑧

𝑒𝛿 − 𝛿 𝛿 𝑒𝛿 − 1 𝑒 𝑒 −1 = 𝑧 . 𝛿 𝛿

Line 5 uses the elementary inequality 𝑒𝛿 ≥ 1 + 𝛿, which gives ( 𝑒𝛿 − 1)/𝛿 ≥ 1, and 𝑧 > 0. Line 6 uses 𝑧 ≥ 23 𝑧, and the final equality is (35). The last strict comparison uses 𝑒 < 3: 𝛼 = 1 − 1/𝑒 < 1 − 1/3 = 2/3. 22

Optimal Skill Selection for LLM Agents If instead 𝑧 = 0, no logarithm involving 𝑧 is ever formed: lines 1–3 of (46) are unchanged and give
𝐶 + 𝜑 ( 𝑟 ) ≥ 32 ( 𝐶 + 𝑥 ) + 𝑥 1 − 𝑒 − 𝛿 ≥ 23 ( 𝐶 + 𝑥 ) = 23 𝐻 > 𝛼𝐻, using 𝑥 (1 − 𝑒−𝛿 ) ≥ 0 and 𝐻 = 𝐶 + 𝑥 + 0 from (35). Step 3 (Case 3: 𝑟 < 𝐷1 and 𝑋1 = 𝑅). Here 𝑧 = 𝑓 ( 𝑅), 𝑥 = 𝑓 ( 𝑣★ | 𝑅), and 𝑑1 = ℓ ( 𝑅) = 𝑟 . Since 𝑟 < 𝐷1 , the first branch of (22) evaluates 𝜑 ( 𝑟 ), and because the branch rate constant is 𝑑1 = 𝑟 ,

𝜑 ( 𝑟 ) = 𝑓 ( 𝑋1 ) 1 − 𝑒 − 𝑟/𝑑1 = 𝑧 1 − 𝑒 −1 = 𝛼𝑧. (47) From (36), 𝐶 ≥ 2𝑥 , hence 3𝐶 ≥ 2𝐶 + 2 𝑥 , i.e., 𝐶 ≥

2 3 (𝐶 + 𝑥 )

≥ 𝛼 (𝐶 + 𝑥 ) ,

(48)

where the second inequality again uses 23 > 𝛼 (from 𝑒 < 3) and 𝐶 + 𝑥 ≥ 0. Adding (47) and (48) and using (35), 𝐶 + 𝜑 ( 𝑟 ) ≥ 𝛼 ( 𝐶 + 𝑥 ) + 𝛼𝑧 = 𝛼 ( 𝐶 + 𝑥 + 𝑧 ) = 𝛼𝐻. Step 4. The reduction 𝑓 ( 𝑃 ) = 0 was handled in Step 0, so assume 𝑓 ( 𝑃 ) > 0. If 𝐷1 ≤ 𝑟 — which includes 𝐷1 = 0, since 𝑟 > 0 by (25) — we are in Case 1. If 𝑟 < 𝐷1 — which includes 𝐷1 = +∞, i.e., 𝜌2 = 0 — we are in Case 2 or Case 3 according to whether the
block order puts { 𝑣★ } or 𝑅 first; these two options are exhaustive because b( 𝐽 ) + 𝜑 ( 𝑟 ) ≥ 𝛼𝐺 b(𝑇 ), which is the claim of Lemma 4. □ ( 𝑋1 , 𝑋2 ) is a permutation of { 𝑣★ }, 𝑅 . In every case 𝐺

23

Related documents

• MOCHA: Multi-Objective Chebyshev Annealing for Agent Skill Optimization#204853
• Skill Self-Play: Pushing the Frontier of LLM Capability with Co-Evolving Skills#406537
• A Deterministic Control Plane for LLM Coding Agents#310744
• Probabilistic promotion and ability#727463
• HyperSkill: Self-Evolving LLM Agents via Hypergraph-Structured Skill Memory#620528