Optimal Skill Selection for LLM Agents with Provable Bicriteria Guarantees

# Optimal Skill Selection for LLM Agents with Provable Bicriteria Guarantees
Source: [https://arxiv.org/html/2608.19993](https://arxiv.org/html/2608.19993)
Ruishuo ChenAffiliation:Equal contribution, listed in random order\.Xun WangZhuoran LiLongbo Huang\[0\.3em\]Institute for Interdisciplinary Information SciencesTsinghua UniversityCorrespondence: 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\-kkor 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, reaching0\.730\.73measured task success versus0\.200\.20–0\.520\.52for released skill routers, text retrievers, and the executor’s own selection, on28%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](https://arxiv.org/html/2608.19993#bib.bib17), and public skill registries already list tens of thousands of installable skills[4](https://arxiv.org/html/2608.19993#bib.bib5);[11](https://arxiv.org/html/2608.19993#bib.bib13)\. Modern production agents such as Codex[34](https://arxiv.org/html/2608.19993#bib.bib33)and Claude Code[2](https://arxiv.org/html/2608.19993#bib.bib32)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](https://arxiv.org/html/2608.19993#bib.bib5);[57](https://arxiv.org/html/2608.19993#bib.bib6), the metadata alone can exceed the available context budget, making exhaustive LLM\-based selection infeasible[10](https://arxiv.org/html/2608.19993#bib.bib9)\. Furthermore, poor skill selection has measurable consequences for downstream execution: empirical evidence shows that selecting the wrong skills cuts pass rates by up to21%21\\%as libraries grow[40](https://arxiv.org/html/2608.19993#bib.bib12), and selected skills can even push success below the no\-skill baseline on1313of8787benchmark tasks despite curation[28](https://arxiv.org/html/2608.19993#bib.bib18)\.

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](https://arxiv.org/html/2608.19993#bib.bib9);[9](https://arxiv.org/html/2608.19993#bib.bib10);[57](https://arxiv.org/html/2608.19993#bib.bib6);[56](https://arxiv.org/html/2608.19993#bib.bib15);[29](https://arxiv.org/html/2608.19993#bib.bib16)\. 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\-kk[38](https://arxiv.org/html/2608.19993#bib.bib11);[27](https://arxiv.org/html/2608.19993#bib.bib14), truncation[31](https://arxiv.org/html/2608.19993#bib.bib40), or greedy packing[56](https://arxiv.org/html/2608.19993#bib.bib15), 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\.

![Refer to caption](https://arxiv.org/html/2608.19993v1/intro_two.png)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](https://arxiv.org/html/2608.19993#S1.F1)illustrates a common skill\-selection paradigm for coding agents[34](https://arxiv.org/html/2608.19993#bib.bib33);[2](https://arxiv.org/html/2608.19993#bib.bib32): 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](https://arxiv.org/html/2608.19993#bib.bib1)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 a93%93\\%success rate\. After both capabilities are covered, adding a redundant pk64\_snip skill consumes225225additional tokens but improves the success rate by only11percentage point, while adding a semantically related but task\-irrelevant pk64\_extra skill reduces it by2323percentage 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 \([Section3](https://arxiv.org/html/2608.19993#S3)\)\. 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 setSSwithin each capability dimension, capturing diminishing returns from repeatedly covering the same capability, while separate dimensions reward covering all demanded capabilities\. The resulting gross benefitG⁡\(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\)\\ell\(S\), and the total length must not exceed the available budgetBB\. Skill selection therefore becomes maximizing this structured objective subject to the hard token budget with the form:

maxS:ℓ⁡\(S\)≤BF\(S\):=G\(S\)−κℓ\(S\)\.\\max\_\{S:\\ell\(S\)\\leq B\}F\(S\):=G\(S\)\-\\kappa\\ell\(S\)\.\(1\)This problem, formalized in[Section3](https://arxiv.org/html/2608.19993#S3), 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 than1−1/e1\-1/eunlessP=NP\\mathrm\{P\}=\\mathrm\{NP\}[6](https://arxiv.org/html/2608.19993#bib.bib25)\. With the penalty, the objective may be negative, ruling out constant multiplicative approximation and motivating a bicriteria guarantee[33](https://arxiv.org/html/2608.19993#bib.bib27);[18](https://arxiv.org/html/2608.19993#bib.bib26)\. Existing results for solving regularized submodular maximization with a hard budget constraint obtain weaker approximation coefficients[15](https://arxiv.org/html/2608.19993#bib.bib30);[16](https://arxiv.org/html/2608.19993#bib.bib31);[53](https://arxiv.org/html/2608.19993#bib.bib42)or incur an additive precision\-dependent loss[35](https://arxiv.org/html/2608.19993#bib.bib41)\.

Our result attains the best possible coefficient1−1/e1\-1/eon 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](https://arxiv.org/html/2608.19993#S1.E1)\) 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[Section3](https://arxiv.org/html/2608.19993#S3)\. 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[Section5\.2](https://arxiv.org/html/2608.19993#S5.SS2)\.
- •Optimal Bicriteria Guarantee\.We develop Best Prefix Selection \(BPS,[Algorithm1](https://arxiv.org/html/2608.19993#alg1)\), a polynomial\-time algorithm for the skill selection problem, and prove the tight\(1−1/e,1\)\(1\-1/e,\\,1\)bicriteria guarantee \([Theorem1](https://arxiv.org/html/2608.19993#Thmtheorem1)\), 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 coefficient1−1/e1\-1/e\([Section4\.3](https://arxiv.org/html/2608.19993#S4.SS3)\)\.
- •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](https://arxiv.org/html/2608.19993#S1.E1)\) 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 by0\.220\.22–0\.530\.53in measured task success, on28%28\\%fewer tokens than the strongest released router \([Sections3\.3](https://arxiv.org/html/2608.19993#S3.SS3)and[5](https://arxiv.org/html/2608.19993#S5)\)\.

## 2\. Related Work

### 2\.1\. Skill Selection for LLM Agents

Skill retrieval and routing[4](https://arxiv.org/html/2608.19993#bib.bib5);[57](https://arxiv.org/html/2608.19993#bib.bib6);[41](https://arxiv.org/html/2608.19993#bib.bib47);[45](https://arxiv.org/html/2608.19993#bib.bib48);[44](https://arxiv.org/html/2608.19993#bib.bib49)narrow a large skill library to a candidate pool for downstream selection, following a pipeline inherited from tool use[37](https://arxiv.org/html/2608.19993#bib.bib4);[38](https://arxiv.org/html/2608.19993#bib.bib11)\. SkillsInjector[29](https://arxiv.org/html/2608.19993#bib.bib16)learns how many skills to inject and renders them jointly; SkillSelect\-Serve[56](https://arxiv.org/html/2608.19993#bib.bib15)greedily packs itemwise scores under token and deployment constraints; Graph\-of\-Skills[31](https://arxiv.org/html/2608.19993#bib.bib40)expands dependency\-aware bundles under a context cap yet leaves its budgeted objective unsolved; GoSkills[52](https://arxiv.org/html/2608.19993#bib.bib44)and SkillComposer[55](https://arxiv.org/html/2608.19993#bib.bib45)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](https://arxiv.org/html/2608.19993#bib.bib43)applies facility\-location coverage to accumulated session content under a token knapsack, and the knapsack composer of[50](https://arxiv.org/html/2608.19993#bib.bib46)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](https://arxiv.org/html/2608.19993#bib.bib2);[36](https://arxiv.org/html/2608.19993#bib.bib3)\. 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 tight1−1/e1\-1/e[42](https://arxiv.org/html/2608.19993#bib.bib22), and refined analyses shrink the enumerated seeds to size two[24](https://arxiv.org/html/2608.19993#bib.bib23);[7](https://arxiv.org/html/2608.19993#bib.bib29)\. ParetoGreedy[43](https://arxiv.org/html/2608.19993#bib.bib24)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 objectiveG−κ​ℓG\-\\kappa\\ellat a fixedκ\\kappa\. Maximizing this regularized objective, however, changes the problem’s character: it can be negative, which rules out any constant multiplicative approximation[33](https://arxiv.org/html/2608.19993#bib.bib27)\. Distorted greedy[18](https://arxiv.org/html/2608.19993#bib.bib26)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Ψ\\Psi\-greedy of[35](https://arxiv.org/html/2608.19993#bib.bib41)to our aligned objective gives\(1−1/e,1\)\(1\-1/e,1\)up to an additiveκ​ϵ\\kappa\\epsilon, paid withO⁡\(B/ϵ\)O\(B/\\epsilon\)budget levels\. The budgeted\-profit works reach\(1/4,1\)\(1/4,1\)[15](https://arxiv.org/html/2608.19993#bib.bib30)and\(\(1−1/e\)/2,1/2\)\(\(1\-1/e\)/2,1/2\)in near\-linear time[16](https://arxiv.org/html/2608.19993#bib.bib31), and\(1/8−ϵ,1\)\(1/8\-\\epsilon,1\)in one streaming pass[53](https://arxiv.org/html/2608.19993#bib.bib42)\. Our result attains\(1−1/e,1\)\(1\-1/e,1\)exactly, with none of these compromises, and the benefit coefficient1−1/e1\-1/eis optimal for polynomial\-time algorithms \([Section4](https://arxiv.org/html/2608.19993#S4)\)\.

## 3\. Model and Optimization Problem

In this section, we formalize the two\-stage skill\-interaction model in modern LLM agents\. Letℒ=\{s1,⋯,sL\}\{\\mathcal\{L\}\}=\\\{s\_\{1\},\\cdots,s\_\{L\}\\\}denote the skill library, wheresis\_\{i\}is theii\-th skill document\. Given a queryqq, the selection stage chooses a subset of skills, indexed byS⊆\[L\]S\\subseteq\[L\], for a downstream executorEE, held fixed throughout\. With the documents of the selected skills injected into its context window,EEexecutes the queryqqand produces an observable outcomeYE​\(q,S\)Y\_\{E\}\(q,S\)\. We define the execution effect of skill setSSas

FE⋆​\(q,S\):=𝔼⁡\[YE​\(q,S\)−YE​\(q,∅\)\]\.F\_\{E\}^\{\\star\}\(q,S\):=\\mathbb\{E\}\\bigl\[Y\_\{E\}\(q,S\)\-Y\_\{E\}\(q,\\varnothing\)\\bigr\]\.\(2\)FE⋆​\(q,S\)F^\{\\star\}\_\{E\}\(q,S\)measures the performance improvement from injecting skill setSSintoEE’s context window, relative to runningEEwithout any skills\.

A natural formulation of the selection stage is to choose the skill index setSSthat maximizes the execution effectFE⋆​\(q,S\)F\_\{E\}^\{\\star\}\(q,S\)\. However, the execution effectFE⋆​\(q,S\)F\_\{E\}^\{\\star\}\(q,S\)is a black\-box function of the frozen executorEE, the queryqq, and the skill setSS\. Therefore, we need a structured model to approximate the execution effectFE⋆​\(q,S\)F\_\{E\}^\{\\star\}\(q,S\)\.

In the following sections, we model the execution effectFE⋆​\(q,S\)F\_\{E\}^\{\\star\}\(q,S\)in three steps\.[Section3\.1](https://arxiv.org/html/2608.19993#S3.SS1)distills empirical observations into a structured objective, a monotone submodular capability benefit minus a linear degradation penalty;[Section3\.2](https://arxiv.org/html/2608.19993#S3.SS2)casts the selection stage as maximizing this objective under a hard token budget and locates its computational hardness; and[Section3\.3](https://arxiv.org/html/2608.19993#S3.SS3)shows that all latent parameters are learnable from execution records, with fitting error provably transferring to selection regret \([Proposition1](https://arxiv.org/html/2608.19993#Thmproposition1)\)\. We validate the fitted objective on real executions in[Section5\.2](https://arxiv.org/html/2608.19993#S5.SS2)\.

### 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 executorEE, 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 queryqq[5](https://arxiv.org/html/2608.19993#bib.bib55);[1](https://arxiv.org/html/2608.19993#bib.bib56);[46](https://arxiv.org/html/2608.19993#bib.bib57)and complement those already supplied by the selected setSS[17](https://arxiv.org/html/2608.19993#bib.bib19)\.\(ii\)More injected context is not uniformly beneficial: irrelevant content can distract execution[39](https://arxiv.org/html/2608.19993#bib.bib54), redundant items may add little marginal coverage[17](https://arxiv.org/html/2608.19993#bib.bib19);[25](https://arxiv.org/html/2608.19993#bib.bib53), and longer inputs can reduce performance in some settings even when the relevant evidence is retrieved correctly[32](https://arxiv.org/html/2608.19993#bib.bib8)\.\(iii\)For a fixed executor and agent\-framework configuration, the selected skill documents must fit within the residual context budget[49](https://arxiv.org/html/2608.19993#bib.bib20);[25](https://arxiv.org/html/2608.19993#bib.bib53);[38](https://arxiv.org/html/2608.19993#bib.bib11)\.

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 withdddimensions\. For each skillsi∈ℒs\_\{i\}\\in\{\\mathcal\{L\}\}, we assume there exists a latent capability supply vector𝒖i=\(ui,1,⋯,ui,d\)∈ℝ\+d\{\\bm\{u\}\}\_\{i\}=\(u\_\{i,1\},\\cdots,u\_\{i,d\}\)\\in\\mathbb\{R\}\_\{\+\}^\{d\}, whereui,ku\_\{i,k\}quantifies how much capability skillsis\_\{i\}supplies in thekk\-th dimension, e\.g\., operating git or analyzing logs\.

To model the complementarity and redundancy among skills, we introduce a nondecreasing concave functionhkh\_\{k\}withhk​\(0\)=0h\_\{k\}\(0\)=0that captures diminishing returns within the same capability dimension: for a skill setSS, we usehk​\(∑i∈Sui,k\)h\_\{k\}\\left\(\\sum\_\{i\\in S\}u\_\{i,k\}\\right\)to represent the capability coverage ofSSin thekk\-th dimension, so that supplies in the same dimension overlap redundantly while supplies in different dimensions remain complementary\.

For queryqq, we assume there exists a latent capability demand vector𝒘q=\(w1q,⋯,wdq\)∈ℝ\+d\{\\bm\{w\}\}^\{q\}=\(w\_\{1\}^\{q\},\\cdots,w\_\{d\}^\{q\}\)\\in\\mathbb\{R\}\_\{\+\}^\{d\}that encodes the query’s demand for each capability dimension\. We then model the gross benefit of injecting skill setSSinto executorEEas a monotone submodular function

GE​\(q,S\):=∑k=1dηkE​wkq⋅hk​\(λkE​∑i∈Sui,k\),G\_\{E\}\(q,S\):=\\sum\_\{k=1\}^\{d\}\\eta^\{E\}\_\{k\}w\_\{k\}^\{q\}\\cdot h\_\{k\}\\left\(\\lambda^\{E\}\_\{k\}\\sum\_\{i\\in S\}u\_\{i,k\}\\right\),\(3\)whereηkE≥0\\eta^\{E\}\_\{k\}\\geq 0andλkE≥0\\lambda^\{E\}\_\{k\}\\geq 0are executor\-specific parameters that calibrateEE’s sensitivity to thekk\-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](https://arxiv.org/html/2608.19993#bib.bib51);[22](https://arxiv.org/html/2608.19993#bib.bib50), 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 \(ii\), injected documents impose a cost that grows with context length\. Assume each skill documentsis\_\{i\}has a token lengthℓi\\ell\_\{i\}, the number of context\-window tokens it occupies once injected, and writeℓ⁡\(S\):=∑i∈Sℓi\\ell\(S\):=\\sum\_\{i\\in S\}\\ell\_\{i\}for the total token length of skill setSS\. We model the performance degradation caused by injectingSSas a linear penalty

cE​\(S\):=κE⋅ℓ⁡\(S\),c\_\{E\}\(S\):=\\kappa\_\{E\}\\cdot\\ell\(S\),\(4\)whereκE≥0\\kappa\_\{E\}\\geq 0is 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](https://arxiv.org/html/2608.19993#bib.bib13), and focused skills outperform larger, exhaustive ones[28](https://arxiv.org/html/2608.19993#bib.bib18)\.

Moreover, observation \(iii\) imposes a hard feasibility limit on skill selection\. We take the budgetBBto 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\}\.\{\\mathcal\{F\}\}\_\{B\}=\\left\\\{S\\subseteq\[L\]:\\ \\ell\(S\)\\leq B\\right\\\}\.\(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∈ℱB⁡FE​\(q,S\)\.\\max\_\{S\\in\{\\mathcal\{F\}\}\_\{B\}\}\\;F\_\{E\}\(q,S\)\.\(7\)
Problem \([7](https://arxiv.org/html/2608.19993#S3.E7)\) is computationally hard: settingκE=0\\kappa\_\{E\}=0and specializing the responseshkh\_\{k\}to truncated sums recovers budgeted maximum coverage[21](https://arxiv.org/html/2608.19993#bib.bib21), an NP\-hard slice of monotone submodular knapsack maximization[42](https://arxiv.org/html/2608.19993#bib.bib22)\. Moreover, the penalty makesFEF\_\{E\}non\-monotone and possibly negative, ruling out any constant multiplicative approximation in polynomial time[33](https://arxiv.org/html/2608.19993#bib.bib27)\.[Section4](https://arxiv.org/html/2608.19993#S4)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](https://arxiv.org/html/2608.19993#S3.E6)\) is built on latent quantities\. Among its primitives, only the token lengthℓi\\ell\_\{i\}for each skill documentsis\_\{i\}is observable\. The capability supplies𝒖i\{\\bm\{u\}\}\_\{i\}, the query demand𝒘q\{\\bm\{w\}\}^\{q\}, and the executor calibration parametersηkE\\eta^\{E\}\_\{k\},λkE\\lambda^\{E\}\_\{k\},κE\\kappa\_\{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](https://arxiv.org/html/2608.19993#S3.E3)\), the demandwkqw^\{q\}\_\{k\}enters only through the productηkE​wkq\\eta^\{E\}\_\{k\}w^\{q\}\_\{k\}, and the supplyui,ku\_\{i,k\}only throughλkE​ui,k\\lambda^\{E\}\_\{k\}u\_\{i,k\}\. Defining the*effective demand*and*effective supply*

w~kq:=ηkE​wkq,u~i,k:=λkE​ui,k,∀k∈\[d\],\\widetilde\{w\}^\{q\}\_\{k\}:=\\eta^\{E\}\_\{k\}w^\{q\}\_\{k\},\\quad\\widetilde\{u\}\_\{i,k\}:=\\lambda^\{E\}\_\{k\}u\_\{i,k\},\\quad\\forall k\\in\[d\],\(8\)the gross benefit \([3](https://arxiv.org/html/2608.19993#S3.E3)\) rewrites exactly asGE​\(q,S\)=∑k=1dw~kq​hk​\(∑i∈Su~i,k\)G\_\{E\}\(q,S\)=\\sum\_\{k=1\}^\{d\}\\widetilde\{w\}^\{q\}\_\{k\}\\,h\_\{k\}\\bigl\(\\sum\_\{i\\in S\}\\widetilde\{u\}\_\{i,k\}\\bigr\)\. We therefore estimate the effective quantities directly with two*capability encoders*: a demand encoderψ^E:q↦𝒘^q\\widehat\{\\psi\}\_\{E\}:q\\mapsto\\widehat\{\\bm\{w\}\}^\{q\}and a supply encoderϕ^E:si↦𝒖^i\\widehat\{\\phi\}\_\{E\}:s\_\{i\}\\mapsto\\widehat\{\\bm\{u\}\}\_\{i\}, where𝒘^q\\widehat\{\\bm\{w\}\}^\{q\}and𝒖^i\\widehat\{\\bm\{u\}\}\_\{i\}are estimates of the effective demand𝒘~q\\widetilde\{\\bm\{w\}\}^\{q\}and effective supply𝒖~i\\widetilde\{\\bm\{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[Section3\.1](https://arxiv.org/html/2608.19993#S3.SS1)\. The context sensitivity is calibrated asκ^E\\widehat\{\\kappa\}\_\{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](https://arxiv.org/html/2608.19993#bib.bib52), we fix the saturating formhk​\(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\. LetF^E​\(q,S\)\\widehat\{F\}\_\{E\}\(q,S\)denote the fitted objective, obtained by instantiating \([6](https://arxiv.org/html/2608.19993#S3.E6)\) with the encoder outputs and the calibratedκ^E\\widehat\{\\kappa\}\_\{E\}:

F^E​\(q,S\):=⟨ψ^E​\(q\),h⁡\(∑i∈Sϕ^E​\(si\)\)⟩−κ^E⋅ℓ⁡\(S\),\\widehat\{F\}\_\{E\}\(q,S\):=\\left\\langle\\widehat\{\\psi\}\_\{E\}\(q\),h\\left\(\\sum\_\{i\\in S\}\\widehat\{\\phi\}\_\{E\}\(s\_\{i\}\)\\right\)\\right\\rangle\-\\widehat\{\\kappa\}\_\{E\}\\cdot\\ell\(S\),\(9\)whereh⁡\(⋅\)h\(\\cdot\)applies\{hk\}\\\{h\_\{k\}\\\}componentwise\. At decision time, the selection layer solves the*fitted selection problem*, which is the deployable counterpart of \([7](https://arxiv.org/html/2608.19993#S3.E7)\) and is defined by

maxS∈ℱB⁡F^E​\(q,S\)\.\\max\_\{S\\in\{\\mathcal\{F\}\}\_\{B\}\}\\widehat\{F\}\_\{E\}\(q,S\)\.\(10\)Solving \([10](https://arxiv.org/html/2608.19993#S3.E10)\) 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\\varepsilon\\geq 0such that\|FE⋆​\(q,S\)−F^E​\(q,S\)\|≤ε\\bigl\|F\_\{E\}^\{\\star\}\(q,S\)\-\\widehat\{F\}\_\{E\}\(q,S\)\\bigr\|\\leq\\varepsilonfor allS∈ℱBS\\in\{\\mathcal\{F\}\}\_\{B\}\.

The fitting errorε\\varepsilonaggregates two sources: structural mismatch of the objective model in[Section3\.1](https://arxiv.org/html/2608.19993#S3.SS1), and estimation error of the encoders and the calibratedκ^E\\widehat\{\\kappa\}\_\{E\}\.

![Refer to caption](https://arxiv.org/html/2608.19993v1/recovery_matrix.png)Figure 2:Parameter recovery\. Top: the true skill\-capability coverage matrix, hidden from the fit\. Bottom: the fitted supplyu^i,k\\widehat\{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 the3131skills, rows the55capabilities\. Both panels use the scale on the right, white=0=0to dark blue=1=1; the bottom panel plotsu^i,k\\widehat\{u\}\_\{i,k\}divided by its largest entry\.In[Section5\.2](https://arxiv.org/html/2608.19993#S5.SS2)we fit \([9](https://arxiv.org/html/2608.19993#S3.E9)\) 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 with60×60\\timesas many parameters\. Its fitted supplies also recover the true skill\-capability coverage matrix, hidden from the fit: over the155155\(skill, capability\) pairs,u^i,k\\widehat\{u\}\_\{i,k\}ranks a covered pair above an uncovered one99\.6%99\.6\\%of the time \(AUC0\.9960\.996,[Fig\.2](https://arxiv.org/html/2608.19993#S3.F2)\)\.[1](https://arxiv.org/html/2608.19993#Thmassumption1)is therefore attainable on a real executor from pass/fail outcomes alone, with281281parameters and nothing assumed beyond the structured form \([3](https://arxiv.org/html/2608.19993#S3.E3)\)\.

The next proposition bounds the end\-to\-end*selection regret*for any rule that approximately solves \([10](https://arxiv.org/html/2608.19993#S3.E10)\)\.

###### Proposition 1\(Error transfer\)\.

Under[1](https://arxiv.org/html/2608.19993#Thmassumption1), everyS^∈ℱB\\widehat\{S\}\\in\{\\mathcal\{F\}\}\_\{B\}withF^E​\(q,S^\)≥maxS∈ℱB⁡F^E​\(q,S\)−δ\\widehat\{F\}\_\{E\}\(q,\\widehat\{S\}\)\\geq\\max\_\{S\\in\{\\mathcal\{F\}\}\_\{B\}\}\\widehat\{F\}\_\{E\}\(q,S\)\-\\deltasatisfies

maxT∈ℱB⁡FE⋆​\(q,T\)−FE⋆​\(q,S^\)≤2​ε\+δ\.\\max\_\{T\\in\{\\mathcal\{F\}\}\_\{B\}\}F\_\{E\}^\{\\star\}\(q,T\)\-F\_\{E\}^\{\\star\}\(q,\\widehat\{S\}\)\\leq 2\\varepsilon\+\\delta\.\(11\)

###### Proof\.

LetT⋆T^\{\\star\}maximizeFE⋆​\(q,⋅\)F\_\{E\}^\{\\star\}\(q,\\cdot\)overℱB\{\\mathcal\{F\}\}\_\{B\}\. Then we haveFE⋆​\(q,T⋆\)−FE⋆​\(q,S^\)≤F^E​\(q,T⋆\)−F^E​\(q,S^\)\+2​ε≤δ\+2​εF\_\{E\}^\{\\star\}\(q,T^\{\\star\}\)\-F\_\{E\}^\{\\star\}\(q,\\widehat\{S\}\)\\leq\\widehat\{F\}\_\{E\}\(q,T^\{\\star\}\)\-\\widehat\{F\}\_\{E\}\(q,\\widehat\{S\}\)\+2\\varepsilon\\leq\\delta\+2\\varepsilon\. ∎

[Proposition1](https://arxiv.org/html/2608.19993#Thmproposition1)decomposes the selection regret into its two sources: the fitting errorε\\varepsilonof the learned model, whose origins we discussed above, and the optimization errorδ\\deltaof solving the fitted selection problem \([10](https://arxiv.org/html/2608.19993#S3.E10)\), which will be further bounded in[Theorem1](https://arxiv.org/html/2608.19993#Thmtheorem1)\.

## 4\. Skill Selection with Provable Guarantees

We now present the selection algorithm and its per\-instance guarantee for the fitted selection problem \([10](https://arxiv.org/html/2608.19993#S3.E10)\)\. Throughout this section we fix the queryqq, the frozen executorEE, and the budgetBB, and suppress them from the notation, writingG^​\(S\)\\widehat\{G\}\(S\)for the fitted capability benefit,κ^\\widehat\{\\kappa\}for the calibrated context sensitivity, andF^​\(S\)=G^​\(S\)−κ^​ℓ​\(S\)\\widehat\{F\}\(S\)=\\widehat\{G\}\(S\)\-\\widehat\{\\kappa\}\\ell\(S\)for the fitted objective defined in \([9](https://arxiv.org/html/2608.19993#S3.E9)\)\. Our analysis uses only thatG^\\widehat\{G\}is normalized \(G^​\(∅\)=0\\widehat\{G\}\(\\varnothing\)=0\), nondecreasing, and submodular, that all lengthsℓi\\ell\_\{i\}are positive, and thatκ^≥0\\widehat\{\\kappa\}\\geq 0\.

The objectiveF^=G^−κ^​ℓ\\widehat\{F\}=\\widehat\{G\}\-\\widehat\{\\kappa\}\\ellraises three difficulties at once\. First, althoughG^\\widehat\{G\}is monotone,F^\\widehat\{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 toF^\\widehat\{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](https://arxiv.org/html/2608.19993#S3.E10)\) \([Theorem1](https://arxiv.org/html/2608.19993#Thmtheorem1)\)\.

### 4\.1\. The BPS Algorithm

We state*Best Prefix Selection*\(BPS\) in[Algorithm1](https://arxiv.org/html/2608.19993#alg1), 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 objectiveF^\\widehat\{F\}\(Line 11\)\.

Algorithm 1Best Prefix Selection \(BPS\)0:skill library

ℒ\{\\mathcal\{L\}\}, budget

BB, fitted benefit oracle

G^\\widehat\{G\}, fitted context sensitivity

κ^\\widehat\{\\kappa\}\.

0:selected skill set

SBPSS\_\{\\texttt\{BPS\}\}\.

1:Discard every skill

iiwith

ℓi\>B\\ell\_\{i\}\>B; initialize the*prefix pool*

𝒫←∅\\mathcal\{P\}\\leftarrow\\emptyset\.

2:foreach seed

A⊆\[L\]A\\subseteq\[L\]with

\|A\|≤2\|A\|\\leq 2and

ℓ⁡\(A\)≤B\\ell\(A\)\\leq Bdo

3:

S←AS\\leftarrow A
4:Add prefix

SSto

𝒫\\mathcal\{P\}\.// each seed opens a prefix chain

5:whilesome

i∉Si\\notin Sfits, i\.e\.,

ℓ⁡\(S\)\+ℓi≤B\\ell\(S\)\+\\ell\_\{i\}\\leq Bdo

6:

i⋆←argmaxi∉S,ℓ⁡\(S\)\+ℓi≤B\(G^​\(\{i\}∪S\)−G^​\(S\)\)/ℓii^\{\\star\}\\leftarrow\\argmax\_\{i\\notin S,\\,\\ell\(S\)\+\\ell\_\{i\}\\\!\\leq\\\!B\}\\left\(\\widehat\{G\}\(\\\{i\\\}\\\!\\cup\\\!S\)\\\!\-\\\!\\widehat\{G\}\(S\)\\right\)\\\!/\\ell\_\{i\}
7:

S←S∪\{i⋆\}S\\leftarrow S\\cup\\\{i^\{\\star\}\\\}\.

8:Add prefix

SSto

𝒫\\mathcal\{P\}\.// record every prefix in chain

9:endwhile

10:endfor

11:

SBPS←argmaxS∈𝒫F^​\(S\)S\_\{\\texttt\{BPS\}\}\\leftarrow\\argmax\_\{S\\in\\mathcal\{P\}\}\\,\\widehat\{F\}\(S\)\.// choose the best prefix

12:return

SBPSS\_\{\\texttt\{BPS\}\}

[Algorithm1](https://arxiv.org/html/2608.19993#alg1)implements the standard partial\-enumeration density greedy for monotone submodular knapsack[21](https://arxiv.org/html/2608.19993#bib.bib21);[42](https://arxiv.org/html/2608.19993#bib.bib22);[24](https://arxiv.org/html/2608.19993#bib.bib23)\. Under a monotone benefit, the endpoint of each chain dominates all its prefixes, so the known1−1/e1\-1/eanalyses compare only chain endpoints\. Under the non\-monotone fitted objectiveF^\\widehat\{F\}, however, the endpoint need not be the best candidate, since the optimum can sit strictly inside a chain\. Inspired by[43](https://arxiv.org/html/2608.19993#bib.bib24), we record every prefix and select the best one over the full collection byF^\\widehat\{F\}; this best\-prefix selection step gives BPS its name\.

### 4\.2\. Main Result: Bicriteria Approximation Guarantee

Throughout, letα=1−1/e\\alpha=1\-1/e\. The theoretical guarantee for[Algorithm1](https://arxiv.org/html/2608.19993#alg1)is given below\.

###### Theorem 1\(Bicriteria\(1−1/e,1\)\(1\-1/e,\\,1\)\-approximation guarantee\)\.

LetG^\\widehat\{G\}be normalized \(G^​\(∅\)=0\\widehat\{G\}\(\\varnothing\)=0\), nondecreasing, and submodular, letℓi\>0\\ell\_\{i\}\>0for alli∈\[L\]i\\in\[L\], and letκ^≥0\\widehat\{\\kappa\}\\geq 0\. The BPS outputSBPSS\_\{\\texttt\{BPS\}\}of[Algorithm1](https://arxiv.org/html/2608.19993#alg1)satisfiesSBPS∈ℱBS\_\{\\texttt\{BPS\}\}\\in\{\\mathcal\{F\}\}\_\{B\}and

F^​\(SBPS\)≥α​G^​\(T\)−κ^​ℓ​\(T\)∀T∈ℱB\.\\widehat\{F\}\(S\_\{\\texttt\{BPS\}\}\)\\geq\\alpha\\,\\widehat\{G\}\(T\)\-\\widehat\{\\kappa\}\\ell\(T\)\\quad\\forall T\\in\{\\mathcal\{F\}\}\_\{B\}\.\(12\)

The guarantee \([12](https://arxiv.org/html/2608.19993#S4.E12)\) is a*bicriteria approximation*: the two coefficients areα=1−1/e\\alpha=1\-1/eon the benefit and11on 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\\alpha=1\-1/ein \([12](https://arxiv.org/html/2608.19993#S4.E12)\) cannot be improved under standard complexity assumptions \(any\(1−1/e\+ϵ\)\(1\-1/e\+\\epsilon\)\-approximation is NP\-hard[6](https://arxiv.org/html/2608.19993#bib.bib25)\)\.[Theorem1](https://arxiv.org/html/2608.19993#Thmtheorem1)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[Theorem1](https://arxiv.org/html/2608.19993#Thmtheorem1)does not: weaker approximation coefficients[15](https://arxiv.org/html/2608.19993#bib.bib30);[16](https://arxiv.org/html/2608.19993#bib.bib31);[53](https://arxiv.org/html/2608.19993#bib.bib42), an additive precision\-dependent loss[35](https://arxiv.org/html/2608.19993#bib.bib41), or a fractional output[8](https://arxiv.org/html/2608.19993#bib.bib28)\. ParetoGreedy[43](https://arxiv.org/html/2608.19993#bib.bib24), whose candidate generation BPS shares, proves instance\-dependent guarantees on the Pareto frontier, but none for the regularized objective at a fixedκ^\\widehat\{\\kappa\}\.[Theorem1](https://arxiv.org/html/2608.19993#Thmtheorem1)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

LetS⋆=argmaxT∈ℱBFE⋆​\(q,T\)S^\{\\star\}=\\argmax\_\{T\\in\{\\mathcal\{F\}\}\_\{B\}\}F^\{\\star\}\_\{E\}\(q,T\)denote the skill set maximizing the true execution effect\. TakingT=S⋆T=S^\{\\star\}in \([12](https://arxiv.org/html/2608.19993#S4.E12)\) givesF^​\(SBPS\)≥F^​\(S⋆\)−1e​G^​\(S⋆\)\\widehat\{F\}\(S\_\{\\texttt\{BPS\}\}\)\\geq\\widehat\{F\}\(S^\{\\star\}\)\-\\frac\{1\}\{e\}\\widehat\{G\}\(S^\{\\star\}\), so the suboptimality of the BPS output is at most a1/e1/efraction of the optimum’s benefitG^​\(S⋆\)\\widehat\{G\}\(S^\{\\star\}\)\. Combining[Theorem1](https://arxiv.org/html/2608.19993#Thmtheorem1)with the error transfer of[Proposition1](https://arxiv.org/html/2608.19993#Thmproposition1)yields an end\-to\-end bound on the true execution effect\.

###### Corollary 1\(Selection regret of BPS\)\.

Under[1](https://arxiv.org/html/2608.19993#Thmassumption1), the BPS outputSBPSS\_\{\\texttt\{BPS\}\}satisfiesFE⋆​\(q,S⋆\)−FE⋆​\(q,SBPS\)≤1e​G^​\(S⋆\)\+2​ε\.F\_\{E\}^\{\\star\}\(q,S^\{\\star\}\)\-F\_\{E\}^\{\\star\}\(q,S\_\{\\texttt\{BPS\}\}\)\\leq\\frac\{1\}\{e\}\\widehat\{G\}\(S^\{\\star\}\)\+2\\varepsilon\.

##### Time Complexity

[Algorithm1](https://arxiv.org/html/2608.19993#alg1)runs inO⁡\(d​L4\)O\(dL^\{4\}\)time, whereddis the capability dimension andLLthe library size:O⁡\(L2\)O\(L^\{2\}\)seeds each grow a chain of at mostLLdensity steps, and each step scansO⁡\(L\)O\(L\)candidates atO⁡\(d\)O\(d\)cost per marginal evaluation\. In practiceLLis the size of the shortlist left by a high\-recall retrieval stage[4](https://arxiv.org/html/2608.19993#bib.bib5);[57](https://arxiv.org/html/2608.19993#bib.bib6);[10](https://arxiv.org/html/2608.19993#bib.bib9), not of the whole registry\.

### 4\.3\. Proof of[Theorem1](https://arxiv.org/html/2608.19993#Thmtheorem1)

For an arbitrary feasible setTT, the proof proceeds in three steps:\(i\)Construct a seedJJfromTT’s two highest\-marginal items and define a residual benefit functionff\.\(ii\)Lower\-bound the trajectory function \([18](https://arxiv.org/html/2608.19993#S4.E18)\) of the density chain grown fromJJby a piecewise\-exponential bounding functionφ\\varphi, adapting the refined analysis of[24](https://arxiv.org/html/2608.19993#bib.bib23), and establishG^​\(J\)\+V⁡\(r\)≥α​G^​\(T\)\\widehat\{G\}\(J\)\+V\(r\)\\geq\\alpha\\widehat\{G\}\(T\)\.\(iii\)Convert this fractional bound into an actual recorded integral prefix via budget\-aligned interpolation, and conclude via theF^\\widehat\{F\}\-maximization of[Algorithm1](https://arxiv.org/html/2608.19993#alg1)\.

#### 4\.3\.1Seed construction and residual function

We first writeG^​\(i∣S\)=G^​\(S∪\{i\}\)−G^​\(S\)\\widehat\{G\}\(i\\mid S\)=\\widehat\{G\}\(S\\cup\\\{i\\\}\)\-\\widehat\{G\}\(S\)for the marginal benefit\. We order the items ofTTgreedily by nonincreasing marginal benefit with an arbitrary fixed tie\-breaking rule:

tj\\displaystyle t\_\{j\}∈argmaxi∈T∖\{t1,⋯,tj−1\}G^​\(i∣\{t1,⋯,tj−1\}\),\\displaystyle\\in\\argmax\_\{i\\in T\\setminus\\\{t\_\{1\},\\cdots,t\_\{j\-1\}\\\}\}\\widehat\{G\}\\left\(i\\mid\\\{t\_\{1\},\\cdots,t\_\{j\-1\}\\\}\\right\),\(13\)mj\\displaystyle m\_\{j\}:=G^\(tj∣\{t1,⋯,tj−1\}\),∀j∈\[\|T\|\]\.\\displaystyle:=\\widehat\{G\}\\left\(t\_\{j\}\\mid\\\{t\_\{1\},\\cdots,t\_\{j\-1\}\\\}\\right\),\\quad\\forall j\\in\[\|T\|\]\.
If\|T\|≤2\|T\|\\leq 2, then[Algorithm1](https://arxiv.org/html/2608.19993#alg1)enumeratesTTitself as a seed, and we haveF^​\(T\)=G^​\(T\)−κ^​ℓ​\(T\)≥α​G^​\(T\)−κ^​ℓ​\(T\)\.\\widehat\{F\}\(T\)=\\widehat\{G\}\(T\)\-\\widehat\{\\kappa\}\\ell\(T\)\\geq\\alpha\\widehat\{G\}\(T\)\-\\widehat\{\\kappa\}\\ell\(T\)\.

We set the feasible seed setJJwithℓ⁡\(J\)≤B\\ell\(J\)\\leq Bas

J:=\{t1,t2\}\.J:=\\\{t\_\{1\},t\_\{2\}\\\}\.\(14\)Then[Algorithm1](https://arxiv.org/html/2608.19993#alg1)enumerates it in Line 2 and records it in Line 4, soJ∈𝒫J\\in\\mathcal\{P\}\. If\|T\|=3\|T\|=3:G^​\(J\)=m1\+m2≥23​\(m1\+m2\+m3\)=23​G^​\(T\)≥α​G^​\(T\)\\widehat\{G\}\(J\)=m\_\{1\}\+m\_\{2\}\\geq\\frac\{2\}\{3\}\(m\_\{1\}\+m\_\{2\}\+m\_\{3\}\)=\\frac\{2\}\{3\}\\widehat\{G\}\(T\)\\geq\\alpha\\widehat\{G\}\(T\)andℓ⁡\(J\)≤ℓ⁡\(T\)\\ell\(J\)\\leq\\ell\(T\)giveF^​\(J\)≥α​G^​\(T\)−κ^​ℓ​\(T\)\\widehat\{F\}\(J\)\\geq\\alpha\\,\\widehat\{G\}\(T\)\-\\widehat\{\\kappa\}\\,\\ell\(T\)\.

In the following, we assume\|T\|≥4\|T\|\\geq 4\. Our goal is to prove that on the chain grown fromJJ, some recorded prefixSTS\_\{T\}satisfiesF^​\(ST\)≥α​G^​\(T\)−κ^​ℓ​\(T\)\\widehat\{F\}\(S\_\{T\}\)\\geq\\alpha\\widehat\{G\}\(T\)\-\\widehat\{\\kappa\}\\ell\(T\)\.

Inspired by the analysis in[42](https://arxiv.org/html/2608.19993#bib.bib22), we define the residual function

f⁡\(U\):=G^​\(J∪U\)−G^​\(J\),∀U⊆\[L\]\.f\(U\):=\\widehat\{G\}\(J\\cup U\)\-\\widehat\{G\}\(J\),\\quad\\forall U\\subseteq\[L\]\.\(15\)By the properties ofG^\\widehat\{G\},ffis normalized \(f⁡\(∅\)=0f\(\\varnothing\)=0\), nonnegative, nondecreasing, and submodular\. LetP=T∖JP=T\\setminus Jdenote the comparator residual\. For everyv∈Pv\\in P, we havef⁡\(\{v\}\)=G^​\(\{v\}∪J\)−G^​\(J\)=G^​\(v∣J\)≤G^​\(v∣\{t1\}\)≤m2f\(\\\{v\\\}\)=\\widehat\{G\}\(\\\{v\\\}\\cup J\)\-\\widehat\{G\}\(J\)=\\widehat\{G\}\(v\\mid J\)\\leq\\widehat\{G\}\(v\\mid\\\{t\_\{1\}\\\}\)\\leq m\_\{2\}, where the first inequality uses submodularity and the second uses the greedy ordering \([13](https://arxiv.org/html/2608.19993#S4.E13)\)\. Therefore, we have

G^​\(J\)\\displaystyle\\widehat\{G\}\(J\)=G^\(\{t1,t2\}\)−G^\(\{t1\}\)\+G^\(\{t1\}\)=m1\+m2≥2m2≥2f\(\{v\}\),∀v∈P\.\\displaystyle=\\widehat\{G\}\(\\\{t\_\{1\},t\_\{2\}\\\}\)\-\\widehat\{G\}\(\\\{t\_\{1\}\\\}\)\+\\widehat\{G\}\(\\\{t\_\{1\}\\\}\)=m\_\{1\}\+m\_\{2\}\\geq 2m\_\{2\}\\geq 2f\(\\\{v\\\}\),\\quad\\forall v\\in P\.\(16\)
We choosev⋆∈Pv^\{\\star\}\\in Pas the item with maximum token length, i\.e\.,v⋆=argmaxv∈Pℓ​\(\{v\}\)v^\{\\star\}=\\argmax\_\{v\\in P\}\\ell\(\\\{v\\\}\)\. Set

r=ℓ⁡\(P∖\{v⋆\}\)\.r=\\ell\(P\\setminus\\\{v^\{\\star\}\\\}\)\.\(17\)Then we can show that the density chain starting with seedJJmust have total token length larger thanrr\.

#### 4\.3\.2Bounding\-function domination

Run the density chain of[Algorithm1](https://arxiv.org/html/2608.19993#alg1)from seedJJ, and letA0=∅⊊A1⊊⋯⊊AmA\_\{0\}=\\varnothing\\subsetneq A\_\{1\}\\subsetneq\\cdots\\subsetneq A\_\{m\}be its accepted additions, so the actual recorded prefixes areJ∪AjJ\\cup A\_\{j\}\. Writeaj=Aj∖Aj−1a\_\{j\}=A\_\{j\}\\setminus A\_\{j\-1\}for thejj\-th accepted item\. Following[24](https://arxiv.org/html/2608.19993#bib.bib23), we define the piecewise\-affine residual\-benefit trajectoryVVbyV⁡\(0\)=0V\(0\)=0and, forℓ⁡\(Aj−1\)≤u≤ℓ⁡\(Aj\)\\ell\(A\_\{j\-1\}\)\\leq u\\leq\\ell\(A\_\{j\}\),

V⁡\(u\):=f⁡\(Aj−1\)\+\(u−ℓ⁡\(Aj−1\)\)​f⁡\(aj∣Aj−1\)ℓ⁡\(\{aj\}\)\.V\(u\):=f\(A\_\{j\-1\}\)\+\\bigl\(u\-\\ell\(A\_\{j\-1\}\)\\bigr\)\\frac\{f\(a\_\{j\}\\mid A\_\{j\-1\}\)\}\{\\ell\(\\\{a\_\{j\}\\\}\)\}\.\(18\)The functionV:\[0,ℓ⁡\(Am\)\]→ℝ≥0V:\[0,\\ell\(A\_\{m\}\)\]\\to\\mathbb\{R\}\_\{\\geq 0\}traces the residual benefit accumulated by the density chain as a function of the total added lengthu=ℓ⁡\(Aj\)u=\\ell\(A\_\{j\}\)beyond the seedJJ\. At each breakpointu=ℓ⁡\(Aj\)u=\\ell\(A\_\{j\}\), the trajectory evaluates toV⁡\(ℓ⁡\(Aj\)\)=f⁡\(Aj\)V\(\\ell\(A\_\{j\}\)\)=f\(A\_\{j\}\), the exact residual benefit of thejj\-th recorded prefix\. Between consecutive breakpoints,VVinterpolates linearly\. Then we have the following lemmas\.

###### Lemma 1\(Trajectory coverage\)\.

V⁡\(r\)V\(r\)is well\-defined; that is,ℓ⁡\(Am\)≥r\\ell\(A\_\{m\}\)\\geq r\.

###### Proof\.

IfP⊆AmP\\subseteq A\_\{m\}, thenℓ⁡\(Am\)≥ℓ⁡\(P\)\>r\\ell\(A\_\{m\}\)\\geq\\ell\(P\)\>rby definition in \([17](https://arxiv.org/html/2608.19993#S4.E17)\)\. Otherwise pickv∈P∖Amv\\in P\\setminus A\_\{m\}\. When the chain stops, addingvvis infeasible\. Thenℓ⁡\(Am\)\+ℓ⁡\(\{v\}\)\>B−ℓ⁡\(J\)\\ell\(A\_\{m\}\)\+\\ell\(\\\{v\\\}\)\>B\-\\ell\(J\)\. Sinceℓ⁡\(\{v\}\)≤ℓ⁡\(\{v⋆\}\)\\ell\(\\\{v\\\}\)\\leq\\ell\(\\\{v^\{\\star\}\\\}\)andℓ⁡\(T\)≤B\\ell\(T\)\\leq B, we haveℓ⁡\(Am\)\>B−ℓ⁡\(J\)−ℓ⁡\(\{v\}\)≥ℓ⁡\(T\)−ℓ⁡\(J\)−ℓ⁡\(\{v⋆\}\)=r\\ell\(A\_\{m\}\)\>B\-\\ell\(J\)\-\\ell\(\\\{v\\\}\)\\geq\\ell\(T\)\-\\ell\(J\)\-\\ell\(\\\{v^\{\\star\}\\\}\)=r\. ∎

###### Lemma 2\(Residual feasibility beforerr\)\.

Consider an accepted segment whose left endpointu0=ℓ⁡\(Aj−1\)u\_\{0\}=\\ell\(A\_\{j\-1\}\)satisfiesu0<ru\_\{0\}<r\. Then every itemv∈P∖Aj−1v\\in P\\setminus A\_\{j\-1\}is feasible at that point\.

###### Proof\.

By maximality ofℓ⁡\(\{v⋆\}\)\\ell\(\\\{v^\{\\star\}\\\}\), we haveℓ⁡\(Aj−1∪\{v\}\)=u0\+ℓ⁡\(\{v\}\)<r\+ℓ⁡\(\{v⋆\}\)=ℓ⁡\(P\)=ℓ⁡\(T\)−ℓ⁡\(J\)≤B−ℓ⁡\(J\)\\ell\(A\_\{j\-1\}\\cup\\\{v\\\}\)=u\_\{0\}\+\\ell\(\\\{v\\\}\)<r\+\\ell\(\\\{v^\{\\star\}\\\}\)=\\ell\(P\)=\\ell\(T\)\-\\ell\(J\)\\leq B\-\\ell\(J\)\. Therefore,vvis feasible at the selection onaja\_\{j\}\. ∎

[Lemma2](https://arxiv.org/html/2608.19993#Thmlemma2)is where removing the longest residual item pays off\.

We adapt the bounding\-function technique of[24](https://arxiv.org/html/2608.19993#bib.bib23)\. PartitionPPinto two nonempty blocks\{v⋆\}\\\{v^\{\\star\}\\\}andR=P∖\{v⋆\}R=P\\setminus\\\{v^\{\\star\}\\\}, and order them as\(X1,X2\)\(X\_\{1\},X\_\{2\}\)so that

f⁡\(X1\)ℓ⁡\(X1\)≥f⁡\(X2\)ℓ⁡\(X2\)\.\\frac\{f\(X\_\{1\}\)\}\{\\ell\(X\_\{1\}\)\}\\geq\\frac\{f\(X\_\{2\}\)\}\{\\ell\(X\_\{2\}\)\}\.\(19\)Setdj=ℓ⁡\(Xj\)d\_\{j\}=\\ell\(X\_\{j\}\)forj=1,2j=1,2, and define the block densities

ρ1=f⁡\(X1\)d1,ρ2=f⁡\(X2∣X1\)d2,\\rho\_\{1\}=\\frac\{f\(X\_\{1\}\)\}\{d\_\{1\}\},\\quad\\rho\_\{2\}=\\frac\{f\(X\_\{2\}\\mid X\_\{1\}\)\}\{d\_\{2\}\},\(20\)wheref⁡\(X2∣X1\)=f⁡\(X1∪X2\)−f⁡\(X1\)f\(X\_\{2\}\\mid X\_\{1\}\)=f\(X\_\{1\}\\cup X\_\{2\}\)\-f\(X\_\{1\}\)\. Submodularity and \([19](https://arxiv.org/html/2608.19993#S4.E19)\) giveρ1≥ρ2\\rho\_\{1\}\\geq\\rho\_\{2\}\. Write

D=ℓ⁡\(P\)=d1\+d2\.D=\\ell\(P\)=d\_\{1\}\+d\_\{2\}\.\(21\)Ifρ2\>0\\rho\_\{2\}\>0, letD1=d1​ln⁡ρ1ρ2D\_\{1\}=d\_\{1\}\\ln\\frac\{\\rho\_\{1\}\}\{\\rho\_\{2\}\}\. Ifρ2=0\\rho\_\{2\}=0, setD1=\+∞D\_\{1\}=\+\\infty\. Define a continuous functionφ:\[0,∞\)→ℝ≥0\\varphi:\[0,\\infty\)\\to\\mathbb\{R\}\_\{\\geq 0\}by

φ⁡\(u\)=\{f\(X1\)\(1−exp\(−u/d1\)\),0≤u<D1,f⁡\(P\)−ρ2​D​exp⁡\(−u−D1D\),u≥D1\.\\varphi\(u\)=\\begin\{cases\}f\(X\_\{1\}\)\\left\(1\-\\exp\(\{\-u/d\_\{1\}\}\)\\right\),&0\\leq u<D\_\{1\},\\\\ f\(P\)\-\\rho\_\{2\}D\\exp\\left\(\-\\dfrac\{u\-D\_\{1\}\}\{D\}\\right\),&u\\geq D\_\{1\}\.\\end\{cases\}\(22\)
The bounding functionφ\\varphiis constructed so that: on the first branch, it tracks exponential saturation towardf⁡\(X1\)f\(X\_\{1\}\)at rate1/d11/d\_\{1\}; on the second branch, it tracks saturation towardf⁡\(P\)f\(P\)at rate1/D1/D\. The transition atD1D\_\{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φ\\varphibeforerr, and a static half, showing that the seed andφ⁡\(r\)\\varphi\(r\)together already account for anα\\alphafraction ofG^​\(T\)\\widehat\{G\}\(T\)\. And the proofs are computational and deferred to Appendix[A](https://arxiv.org/html/2608.19993#A1)\.

###### Lemma 3\(Trajectory bound\)\.

V⁡\(u\)≥φ⁡\(u\),∀u∈\[0,r\]V\(u\)\\geq\\varphi\(u\),\\forall u\\in\[0,r\]\.

###### Lemma 4\(Static bound atrr\)\.

G^​\(J\)\+φ⁡\(r\)≥α​G^​\(T\)\\widehat\{G\}\(J\)\+\\varphi\(r\)\\geq\\alpha\\widehat\{G\}\(T\)\.

#### 4\.3\.3Budget\-aligned interpolation

[Lemmas3](https://arxiv.org/html/2608.19993#Thmlemma3)and[4](https://arxiv.org/html/2608.19993#Thmlemma4)give

G^​\(J\)\+V⁡\(r\)≥G^​\(J\)\+φ⁡\(r\)≥α​G^​\(T\)\.\\widehat\{G\}\(J\)\+V\(r\)\\geq\\widehat\{G\}\(J\)\+\\varphi\(r\)\\geq\\alpha\\,\\widehat\{G\}\(T\)\.\(23\)Choose consecutive recorded prefixesAj−1,AjA\_\{j\-1\},A\_\{j\}whose segment containsrr\. There existsλ∈\[0,1\]\\lambda\\in\[0,1\]withV⁡\(r\)=\(1−λ\)​f​\(Aj−1\)\+λ​f​\(Aj\),V\(r\)=\(1\-\\lambda\)\\,f\(A\_\{j\-1\}\)\+\\lambda\\,f\(A\_\{j\}\),andr=\(1−λ\)​ℓ​\(Aj−1\)\+λ​ℓ​\(Aj\)r=\(1\-\\lambda\)\\,\\ell\(A\_\{j\-1\}\)\+\\lambda\\,\\ell\(A\_\{j\}\)\. Because the penaltyκ^​ℓ​\(⋅\)\\widehat\{\\kappa\}\\,\\ell\(\\cdot\)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\-\\lambda\)\\widehat\{F\}\(J\\cup A\_\{j\-1\}\)\+\\lambda\\widehat\{F\}\(J\\cup A\_\{j\}\)=\\widehat\{G\}\(J\)\+V\(r\)\-\\widehat\{\\kappa\}\(\\ell\(J\)\+r\)\. Sinceℓ⁡\(J\)\+r=ℓ⁡\(T\)−ℓ⁡\(\{v⋆\}\)≤ℓ⁡\(T\)\\ell\(J\)\+r=\\ell\(T\)\-\\ell\(\\\{v^\{\\star\}\\\}\)\\leq\\ell\(T\), \([23](https://arxiv.org/html/2608.19993#S4.E23)\) gives\(1−λ\)​F^​\(J∪Aj−1\)\+λ​F^​\(J∪Aj\)≥α​G^​\(T\)−κ^​\(ℓ⁡\(T\)−ℓ⁡\(\{v⋆\}\)\)≥α​G^​\(T\)−κ^​ℓ​\(T\)\(1\-\\lambda\)\\widehat\{F\}\(J\\cup A\_\{j\-1\}\)\+\\lambda\\widehat\{F\}\(J\\cup A\_\{j\}\)\\geq\\alpha\\widehat\{G\}\(T\)\-\\widehat\{\\kappa\}\(\\ell\(T\)\-\\ell\(\\\{v^\{\\star\}\\\}\)\)\\geq\\alpha\\widehat\{G\}\(T\)\-\\widehat\{\\kappa\}\\ell\(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\}\.\\widehat\{F\}\(J\\cup A\_\{s\}\)\\geq\\alpha\\widehat\{G\}\(T\)\-\\widehat\{\\kappa\}\\ell\(T\),\\quad s\\in\\\{j\-1,j\\\}\.\(24\)
Therefore, in every case, some recorded candidateST∈𝒫S\_\{T\}\\in\\mathcal\{P\}satisfiesF^​\(ST\)≥α​G^​\(T\)−κ^​ℓ​\(T\)\\widehat\{F\}\(S\_\{T\}\)\\geq\\alpha\\,\\widehat\{G\}\(T\)\-\\widehat\{\\kappa\}\\,\\ell\(T\)\. SinceSBPSS\_\{\\texttt\{BPS\}\}maximizesF^\\widehat\{F\}over𝒫\\mathcal\{P\}\(Line 11 of[Algorithm1](https://arxiv.org/html/2608.19993#alg1)\),F^​\(SBPS\)≥F^​\(ST\)\\widehat\{F\}\(S\_\{\\texttt\{BPS\}\}\)\\geq\\widehat\{F\}\(S\_\{T\}\)\. The seed and witness prefix depend onTT, but every seed of size at most two is enumerated and one selection maximizesF^\\widehat\{F\}over all recorded candidates, so the single outputSBPSS\_\{\\texttt\{BPS\}\}satisfies \([12](https://arxiv.org/html/2608.19993#S4.E12)\) for everyT∈ℱBT\\in\{\\mathcal\{F\}\}\_\{B\}\. This statement finishes the proof of[Theorem1](https://arxiv.org/html/2608.19993#Thmtheorem1)\.■\\blacksquare

## 5\. Evaluation

[Corollary1](https://arxiv.org/html/2608.19993#Thmcorollary1)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\.[Section5\.2](https://arxiv.org/html/2608.19993#S5.SS2)measures the first, how closely the fitted objective tracks those executions, and[Section5\.3](https://arxiv.org/html/2608.19993#S5.SS3)the second, how far the sets BPS returns fall short of the exact optimum of that objective, which[Theorem1](https://arxiv.org/html/2608.19993#Thmtheorem1)bounds only in the worst case\.[Section5\.4](https://arxiv.org/html/2608.19993#S5.SS4)then executes the selected sets and reports the task success they achieve\.

### 5\.1\. Testbed: A Contamination\-Controlled Skill Benchmark

𝟖𝟓%\\mathbf\{85\\%\}𝟎%\\mathbf\{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, passes85%85\\%of runs on the original BigCodeBench[58](https://arxiv.org/html/2608.19993#bib.bib34)tasks from pretraining alone\. We therefore build our own, and everything below rests on63,59663\{,\}596executions of it against real test suites\.

##### Private modules

We fork the benchmark, replacing its standard libraries with sixteen private modules overd=5d=5capability families\. Each module’s call surface is unguessable from the task prose and documented only in the skill library \([Fig\.3](https://arxiv.org/html/2608.19993#S5.F3)\)\.

##### 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 wrote4747skill documents, of whichL=31L=31form 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](https://arxiv.org/html/2608.19993#S3.E9)\) 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[Section3\.3](https://arxiv.org/html/2608.19993#S3.SS3)\.

##### Instantiation and fitting

We setd=5d=5, one dimension per module family, and fixhk​\(x\)=1−e−xh\_\{k\}\(x\)=1\-e^\{\-x\}a priori, as in[Section3\.3](https://arxiv.org/html/2608.19993#S3.SS3)\. The task set and the library are both fixed, so the encoders reduce to lookup tables that assume nothing beyond the structured form \([3](https://arxiv.org/html/2608.19993#S3.E3)\): one supply vector𝒖^i\\widehat\{\\bm\{u\}\}\_\{i\}per skill, one demand vector𝒘^q\\widehat\{\\bm\{w\}\}^\{q\}per task, and one offset per task,281281parameters in total\. These are trained jointly by gradient descent, minimizing the log loss of the measured pass/fail outcomes against the predicted success probabilityexp⁡F^E\\exp\\widehat\{F\}\_\{E\}\([9](https://arxiv.org/html/2608.19993#S3.E9)\)\.

##### 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](https://arxiv.org/html/2608.19993#bib.bib35)do the same with values estimated from measured marginal contributions\. Datamodels[19](https://arxiv.org/html/2608.19993#bib.bib36)regresses the measured rate on the set indicator\. DeepSets[51](https://arxiv.org/html/2608.19993#bib.bib38)and Set Transformer[26](https://arxiv.org/html/2608.19993#bib.bib39)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](https://arxiv.org/html/2608.19993#S5.F4)\(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](https://arxiv.org/html/2608.19993#S5.F4), right\)\. The structured objective reaches95%95\\%of the empirical ceiling, and every interpretable alternative gives up at least0\.370\.37in absolute success\. Only DeepSets remains competitive, at60×60\\timesthe 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δ\\delta, we freeze the objective at the fit of[Section5\.2](https://arxiv.org/html/2608.19993#S5.SS2)and vary only the rule that maximizes it, so that the comparison measures search quality alone\. The8080instances of the fitted selection problem \([10](https://arxiv.org/html/2608.19993#S3.E10)\) span held\-out tasks, token budget levelsBB, 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](https://arxiv.org/html/2608.19993#S3.E9)\) assigns the singleton\{si\}\\\{s\_\{i\}\\\}, and never evaluate the set they assemble or charge for the tokens it costs: top\-kkrelevance fills the budget in that order, while MMR[3](https://arxiv.org/html/2608.19993#bib.bib7)and DPP\-MAP[23](https://arxiv.org/html/2608.19993#bib.bib37)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\-100100random keeps the highest\-scoring of100100random budget\-feasible sets\.

Figure 5:The8080selection 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](https://arxiv.org/html/2608.19993#S3.E10)\) on all8080instances, so the optimization errorδ\\deltaof[Proposition1](https://arxiv.org/html/2608.19993#Thmproposition1)vanishes throughout \([Fig\.5](https://arxiv.org/html/2608.19993#S5.F5), 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 only45%45\\%and44%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 same8080instances, 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](https://arxiv.org/html/2608.19993#bib.bib47), rank the documents by their text against the task prompt and fill the budget in that order\. SkillRouter[57](https://arxiv.org/html/2608.19993#bib.bib6)is a released retrieve\-and\-rerank router, which we run both at its own top\-11operating point and, more generously, in its reranked order up to our full budget; Graph\-of\-Skills[31](https://arxiv.org/html/2608.19993#bib.bib40)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](https://arxiv.org/html/2608.19993#S5.F5), right\)\. The released routers and retrievers reach0\.200\.20–0\.430\.43, between0\.300\.30and0\.530\.53below it, and BPS attains its own result on28%28\\%fewer tokens than the strongest of them; the strongest deployed selector, the executor picking for itself, still gives up0\.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[Section5\.2](https://arxiv.org/html/2608.19993#S5.SS2)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](https://arxiv.org/html/2608.19993#bib.bib58)embeddings of the task prompt and of each skill document into6464latent 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 reach0\.680\.68measured success on716716injected tokens \(red star in[Fig\.5](https://arxiv.org/html/2608.19993#S5.F5)\):0\.050\.05below the lookup\-table instantiation, and0\.170\.17–0\.480\.48above 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

- Anet al\.\(2023\)S\. Anet al\.Skill\-Based Few\-Shot Selection for In\-Context Learning\.InProc\. 2023 Conf\. Empirical Methods Natural Lang\. Process\. \(EMNLP\),pp\. 13472–13492\.Cited by:[§3\.1](https://arxiv.org/html/2608.19993#S3.SS1.p1.1)\.
- Anthropic \(2025\)AnthropicEquipping agents for the real world with agent skills\(Website\)Note:Anthropic Engineering BlogAccessed 2026\-07\-23External Links:[Link](https://www.anthropic.com/engineering/equipping-agents-for-the-real-world-with-agent-skills)Cited by:[§1](https://arxiv.org/html/2608.19993#S1.p1.1),[§1](https://arxiv.org/html/2608.19993#S1.p4.1)\.
- Carbonell and Goldstein \(1998\)J\. Carbonell and J\. GoldsteinThe use of MMR, diversity\-based reranking for reordering documents and producing summaries\.InProc\. 21st Annu\. Int\. ACM SIGIR Conf\. Res\. Develop\. Inf\. Retrieval,pp\. 335–336\.Cited by:[§5\.3](https://arxiv.org/html/2608.19993#S5.SS3.SSS0.Px1.p1.1)\.
- Choet al\.\(2026\)H\. Cho, R\. Kang, and Y\. KimSkillRet: a large\-scale benchmark for skill retrieval in LLM agents\.arXiv preprint arXiv:2605\.05726\.Cited by:[§1](https://arxiv.org/html/2608.19993#S1.p1.1),[§1](https://arxiv.org/html/2608.19993#S1.p2.1),[§2\.1](https://arxiv.org/html/2608.19993#S2.SS1.p1.1),[§4\.2](https://arxiv.org/html/2608.19993#S4.SS2.SSS0.Px4.p1.1)\.
- Didolkaret al\.\(2024\)A\. Didolkaret al\.Metacognitive Capabilities of LLMs: An Exploration in Mathematical Problem Solving\.InAdv\. Neural Inf\. Process\. Syst\. 37 \(NeurIPS 2024\),pp\. 19783–19812\.Cited by:[§3\.1](https://arxiv.org/html/2608.19993#S3.SS1.p1.1)\.
- Feige \(1998\)U\. FeigeA threshold of ln n for approximating set cover\.J\. ACM45\(4\),pp\. 634–652\.Cited by:[§1](https://arxiv.org/html/2608.19993#S1.p6.1),[§4\.2](https://arxiv.org/html/2608.19993#S4.SS2.SSS0.Px1.p1.1)\.
- Feldmanet al\.\(2023\)M\. Feldman, Z\. Nutov, and E\. ShohamPractical budgeted submodular maximization\.Algorithmica85\(5\),pp\. 1332–1371\.Cited by:[§2\.2](https://arxiv.org/html/2608.19993#S2.SS2.p1.1)\.
- Feldman \(2021\)M\. FeldmanGuess free maximization of submodular and linear sums\.Algorithmica83\(3\),pp\. 853–878\.Cited by:[§4\.2](https://arxiv.org/html/2608.19993#S4.SS2.SSS0.Px2.p1.1)\.
- Foreet al\.\(2024\)M\. Fore, S\. Singh, and D\. StamoulisGeckOpt: LLM system efficiency via intent\-based tool selection\.InProc\. Great Lakes Symp\. VLSI \(GLSVLSI\),pp\. 353–354\.Cited by:[§1](https://arxiv.org/html/2608.19993#S1.p3.1)\.
- Gan and Sun \(2025\)T\. Gan and Q\. SunRAG\-MCP: mitigating prompt bloat in LLM tool selection via retrieval\-augmented generation\.arXiv preprint arXiv:2505\.03275\.Cited by:[§1](https://arxiv.org/html/2608.19993#S1.p2.1),[§1](https://arxiv.org/html/2608.19993#S1.p3.1),[§4\.2](https://arxiv.org/html/2608.19993#S4.SS2.SSS0.Px4.p1.1)\.
- Gaoet al\.\(2026\)Y\. Gao, Z\. Li, Y\. Yuan, Z\. Ji, P\. Ma, and S\. WangSkillReducer: optimizing LLM agent skills for token efficiency\.arXiv preprint arXiv:2603\.29919\.Cited by:[§1](https://arxiv.org/html/2608.19993#S1.p1.1),[§3\.1](https://arxiv.org/html/2608.19993#S3.SS1.SSS0.Px2.p1.2)\.
- Ghorbani and Zou \(2019\)A\. Ghorbani and J\. ZouData Shapley: equitable valuation of data for machine learning\.InProc\. 36th Int\. Conf\. Mach\. Learn\. \(ICML\),pp\. 2242–2251\.Cited by:[§5\.2](https://arxiv.org/html/2608.19993#S5.SS2.SSS0.Px2.p1.1)\.
- Ghulyaniet al\.\(2026\)M\. Ghulyani, A\. Singh, K\. Bharadwaj, A\. Nath, and S\. GoswamiPACMS: submodular context selection as a pluggable engine for LLM agents\.arXiv preprint arXiv:2606\.20047\.Cited by:[§2\.1](https://arxiv.org/html/2608.19993#S2.SS1.p1.1)\.
- Golrezaeiet al\.\(2012\)N\. Golrezaei, K\. Shanmugam, A\. G\. Dimakis, A\. F\. Molisch, and G\. CaireFemtoCaching: wireless video content delivery through distributed caching helpers\.InProc\. IEEE INFOCOM,pp\. 1107–1115\.Cited by:[§2\.2](https://arxiv.org/html/2608.19993#S2.SS2.p1.1)\.
- Gonget al\.\(2024\)S\. Gong, Q\. Nong, Y\. Wang, and D\. DuBudget\-constrained profit maximization without non\-negative objective assumption in social networks\.J\. Glob\. Optim\.90\(4\),pp\. 1007–1030\.Cited by:[§1](https://arxiv.org/html/2608.19993#S1.p6.1),[§2\.2](https://arxiv.org/html/2608.19993#S2.SS2.p1.1),[§4\.2](https://arxiv.org/html/2608.19993#S4.SS2.SSS0.Px2.p1.1)\.
- Guoet al\.\(2026\)Q\. Guo, C\. Feng, J\. Shi, J\. Tang, X\. Zhou, and S\. WangEfficient algorithms for budgeted profit maximization with theoretical guarantees\.IEEE Trans\. Knowl\. Data Eng\.38\(4\),pp\. 2234–2248\.Cited by:[§1](https://arxiv.org/html/2608.19993#S1.p6.1),[§2\.2](https://arxiv.org/html/2608.19993#S2.SS2.p1.1),[§4\.2](https://arxiv.org/html/2608.19993#S4.SS2.SSS0.Px2.p1.1)\.
- Guptaet al\.\(2023\)S\. Gupta, M\. Gardner, and S\. SinghCoverage\-based example selection for in\-context learning\.InFindings Assoc\. Comput\. Linguistics: EMNLP 2023,Cited by:[§3\.1](https://arxiv.org/html/2608.19993#S3.SS1.p1.1)\.
- Harshawet al\.\(2019\)C\. Harshaw, M\. Feldman, J\. Ward, and A\. KarbasiSubmodular maximization beyond non\-negativity: guarantees, fast algorithms, and applications\.InProc\. 36th Int\. Conf\. Mach\. Learn\. \(ICML\),pp\. 2634–2643\.Cited by:[§1](https://arxiv.org/html/2608.19993#S1.p6.1),[§2\.2](https://arxiv.org/html/2608.19993#S2.SS2.p1.1)\.
- Ilyaset al\.\(2022\)A\. Ilyas, S\. M\. Park, L\. Engstrom, G\. Leclerc, and A\. MadryDatamodels: understanding predictions with data and data with predictions\.InProc\. 39th Int\. Conf\. Mach\. Learn\. \(ICML\),pp\. 9525–9587\.Cited by:[§5\.2](https://arxiv.org/html/2608.19993#S5.SS2.SSS0.Px2.p1.1)\.
- Iyer and Bilmes \(2015\)R\. Iyer and J\. BilmesSubmodular Point Processes with Applications to Machine learning\.InProc\. 18th Int\. Conf\. Artif\. Intell\. Statist\. \(AISTATS\),pp\. 388–397\.Cited by:[§3\.3](https://arxiv.org/html/2608.19993#S3.SS3.p2.2)\.
- Khulleret al\.\(1999\)S\. Khuller, A\. Moss, and J\. NaorThe budgeted maximum coverage problem\.Inf\. Process\. Lett\.70\(1\),pp\. 39–45\.Cited by:[§3\.2](https://arxiv.org/html/2608.19993#S3.SS2.p2.1),[§4\.1](https://arxiv.org/html/2608.19993#S4.SS1.p2.1)\.
- Kirchhoff and Bilmes \(2014\)K\. Kirchhoff and J\. BilmesSubmodularity for data selection in machine translation\.InProc\. 2014 Conf\. Empirical Methods Natural Lang\. Process\. \(EMNLP\),pp\. 131–141\.Cited by:[§3\.1](https://arxiv.org/html/2608.19993#S3.SS1.SSS0.Px1.p3.2)\.
- Kulesza and Taskar \(2012\)A\. Kulesza and B\. TaskarDeterminantal point processes for machine learning\.Found\. Trends Mach\. Learn\.5\(2–3\),pp\. 123–286\.Cited by:[§5\.3](https://arxiv.org/html/2608.19993#S5.SS3.SSS0.Px1.p1.1)\.
- Kuliket al\.\(2021\)A\. Kulik, R\. Schwartz, and H\. ShachnaiA refined analysis of submodular greedy\.Oper\. Res\. Lett\.49\(4\),pp\. 507–514\.Cited by:[§A\.2](https://arxiv.org/html/2608.19993#A1.SS2.p7.1.1),[§2\.2](https://arxiv.org/html/2608.19993#S2.SS2.p1.1),[§4\.1](https://arxiv.org/html/2608.19993#S4.SS1.p2.1),[§4\.3\.2](https://arxiv.org/html/2608.19993#S4.SS3.SSS2.p1.1),[§4\.3\.2](https://arxiv.org/html/2608.19993#S4.SS3.SSS2.p5.1),[§4\.3](https://arxiv.org/html/2608.19993#S4.SS3.p1.1)\.
- Kumariet al\.\(2024\)L\. Kumari, S\. Wang, A\. Das, T\. Zhou, and J\. BilmesAn end\-to\-end submodular framework for data\-efficient in\-context learning\.InFindings Assoc\. Comput\. Linguistics: NAACL 2024,pp\. 3293–3308\.Cited by:[§3\.1](https://arxiv.org/html/2608.19993#S3.SS1.p1.1)\.
- Leeet al\.\(2019\)J\. Lee, Y\. Lee, J\. Kim, A\. R\. Kosiorek, S\. Choi, and Y\. W\. TehSet transformer: a framework for attention\-based permutation\-invariant neural networks\.InProc\. 36th Int\. Conf\. Mach\. Learn\. \(ICML\),pp\. 3744–3753\.Cited by:[§5\.2](https://arxiv.org/html/2608.19993#S5.SS2.SSS0.Px2.p1.1)\.
- Liet al\.\(2026a\)H\. Liet al\.Organizing, orchestrating, and benchmarking agent skills at ecosystem scale\.arXiv preprint arXiv:2603\.02176\.Cited by:[§1](https://arxiv.org/html/2608.19993#S1.p3.1)\.
- Liet al\.\(2026b\)X\. Liet al\.SkillsBench: benchmarking how well agent skills work across diverse tasks\.arXiv preprint arXiv:2602\.12670\.Cited by:[§1](https://arxiv.org/html/2608.19993#S1.p2.1),[§3\.1](https://arxiv.org/html/2608.19993#S3.SS1.SSS0.Px2.p1.2)\.
- Liet al\.\(2026c\)Y\. Liet al\.SkillsInjector: dynamic skill context construction for LLM agents\.arXiv preprint arXiv:2605\.29794\.Cited by:[§1](https://arxiv.org/html/2608.19993#S1.p3.1),[§2\.1](https://arxiv.org/html/2608.19993#S2.SS1.p1.1)\.
- Lin and Bilmes \(2011\)H\. Lin and J\. BilmesA class of submodular functions for document summarization\.InProc\. 49th Annu\. Meeting Assoc\. Comput\. Linguistics \(ACL\),pp\. 510–520\.Cited by:[§3\.1](https://arxiv.org/html/2608.19993#S3.SS1.SSS0.Px1.p3.2)\.
- Liuet al\.\(2026\)D\. Liuet al\.Graph\-of\-Skills: dependency\-aware structural retrieval for massive agent skills\.arXiv preprint arXiv:2604\.05333\.Cited by:[§1](https://arxiv.org/html/2608.19993#S1.p3.1),[§2\.1](https://arxiv.org/html/2608.19993#S2.SS1.p1.1),[§5\.4](https://arxiv.org/html/2608.19993#S5.SS4.SSS0.Px1.p1.1)\.
- Liuet al\.\(2024\)N\. F\. Liuet al\.Lost in the middle: how language models use long contexts\.Trans\. Assoc\. Comput\. Linguistics12,pp\. 157–173\.Cited by:[§3\.1](https://arxiv.org/html/2608.19993#S3.SS1.p1.1)\.
- Nikolakakiet al\.\(2021\)S\. M\. Nikolakaki, A\. Ene, and E\. TerziAn efficient framework for balancing submodularity and cost\.InProc\. 27th ACM SIGKDD Conf\. Knowl\. Discov\. Data Min\.,pp\. 1256–1266\.Cited by:[§1](https://arxiv.org/html/2608.19993#S1.p6.1),[§2\.2](https://arxiv.org/html/2608.19993#S2.SS2.p1.1),[§3\.2](https://arxiv.org/html/2608.19993#S3.SS2.p2.1)\.
- OpenAI \(2026\)OpenAIBuild skills\(Website\)Note:Codex DocumentationAccessed 2026\-07\-26External Links:[Link](https://developers.openai.com/codex/skills/)Cited by:[§1](https://arxiv.org/html/2608.19993#S1.p1.1),[§1](https://arxiv.org/html/2608.19993#S1.p4.1)\.
- Perraultet al\.\(2021\)P\. Perrault, J\. Healey, Z\. Wen, and M\. ValkoOn the approximation relationship between optimizing ratio of submodular \(RS\) and difference of submodular \(DS\) functions\.arXiv preprint arXiv:2101\.01631\.Cited by:[§1](https://arxiv.org/html/2608.19993#S1.p6.1),[§2\.2](https://arxiv.org/html/2608.19993#S2.SS2.p1.1),[§4\.2](https://arxiv.org/html/2608.19993#S4.SS2.SSS0.Px2.p1.1)\.
- Poularakiset al\.\(2019\)K\. Poularakis, J\. Llorca, A\. M\. Tulino, I\. Taylor, and L\. TassiulasJoint service placement and request routing in multi\-cell mobile edge computing networks\.InProc\. IEEE INFOCOM,pp\. 10–18\.Cited by:[§2\.2](https://arxiv.org/html/2608.19993#S2.SS2.p1.1)\.
- Qinet al\.\(2024\)Y\. Qinet al\.ToolLLM: facilitating large language models to master 16000\+ real\-world APIs\.InProc\. 12th Int\. Conf\. Learn\. Represent\. \(ICLR\),Cited by:[§2\.1](https://arxiv.org/html/2608.19993#S2.SS1.p1.1)\.
- Quet al\.\(2024\)C\. Quet al\.Towards completeness\-oriented tool retrieval for large language models\.InProc\. ACM Int\. Conf\. Inf\. Knowl\. Manage\. \(CIKM\),pp\. 1930–1940\.Cited by:[§1](https://arxiv.org/html/2608.19993#S1.p3.1),[§2\.1](https://arxiv.org/html/2608.19993#S2.SS1.p1.1),[§3\.1](https://arxiv.org/html/2608.19993#S3.SS1.p1.1)\.
- Shiet al\.\(2023\)F\. Shiet al\.Large language models can be easily distracted by irrelevant context\.InProc\. 40th Int\. Conf\. Mach\. Learn\. \(ICML\),pp\. 31210–31227\.Cited by:[§3\.1](https://arxiv.org/html/2608.19993#S3.SS1.p1.1)\.
- Song and Wei \(2026\)H\. Song and S\. WeiMore skills, worse agents? skill shadowing degrades performance when expanding skill libraries\.arXiv preprint arXiv:2605\.24050\.Cited by:[§1](https://arxiv.org/html/2608.19993#S1.p2.1)\.
- Suet al\.\(2026\)W\. Suet al\.Skill retrieval augmentation for agentic AI\.arXiv preprint arXiv:2604\.24594\.Cited by:[§2\.1](https://arxiv.org/html/2608.19993#S2.SS1.p1.1),[§5\.4](https://arxiv.org/html/2608.19993#S5.SS4.SSS0.Px1.p1.1)\.
- Sviridenko \(2004\)M\. SviridenkoA note on maximizing a submodular set function subject to a knapsack constraint\.Oper\. Res\. Lett\.32\(1\),pp\. 41–43\.Cited by:[§2\.2](https://arxiv.org/html/2608.19993#S2.SS2.p1.1),[§3\.2](https://arxiv.org/html/2608.19993#S3.SS2.p2.1),[§4\.1](https://arxiv.org/html/2608.19993#S4.SS1.p2.1),[§4\.3\.1](https://arxiv.org/html/2608.19993#S4.SS3.SSS1.p5.2)\.
- Vombatkere and Terzi \(2026\)K\. Vombatkere and E\. TerziComputing approximate pareto frontiers for submodular utility and cost tradeoffs\.arXiv preprint arXiv:2602\.15964\.Cited by:[§2\.2](https://arxiv.org/html/2608.19993#S2.SS2.p1.1),[§4\.1](https://arxiv.org/html/2608.19993#S4.SS1.p2.1),[§4\.2](https://arxiv.org/html/2608.19993#S4.SS2.SSS0.Px2.p1.1)\.
- Wanget al\.\(2026\)Z\. Wang, W\. Wen, Q\. Ji, R\. Qiao, and X\. SunSkill 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](https://arxiv.org/html/2608.19993#S2.SS1.p1.1)\.
- Xiaoet al\.\(2026\)J\. Xiaoet al\.SkillSight: calibrating generic content bias for skill retrieval\.arXiv preprint arXiv:2607\.18785\.Cited by:[§2\.1](https://arxiv.org/html/2608.19993#S2.SS1.p1.1)\.
- Xuet al\.\(2024\)Z\. Xu, H\. Wang, D\. Bespalov, X\. Wu, P\. Stone, and Y\. QiLaRS: Latent Reasoning Skills for Chain\-of\-Thought Reasoning\.InFindings Assoc\. Comput\. Linguistics: EMNLP 2024,pp\. 3624–3643\.Cited by:[§3\.1](https://arxiv.org/html/2608.19993#S3.SS1.p1.1)\.
- Yanget al\.\(2025\)A\. Yanget al\.Qwen3 technical report\.arXiv preprint arXiv:2505\.09388\.Cited by:[§1](https://arxiv.org/html/2608.19993#S1.p4.1)\.
- Yanget al\.\(2026\)C\. Yanget al\.A survey of agent skills: toward procedural infrastructure for LLM agents\.Preprints\.org preprint\.Note:doi: 10\.20944/preprints202605\.1276\.v1Cited by:[§1](https://arxiv.org/html/2608.19993#S1.p1.1)\.
- Yeet al\.\(2023\)J\. Ye, Z\. Wu, J\. Feng, T\. Yu, and L\. KongCompositional exemplars for in\-context learning\.InProc\. 40th Int\. Conf\. Mach\. Learn\. \(ICML\),pp\. 39818–39833\.Cited by:[§3\.1](https://arxiv.org/html/2608.19993#S3.SS1.p1.1)\.
- Yuanet al\.\(2025\)M\. Yuanet al\.Automated composition of agents: a knapsack approach for agentic component selection\.arXiv preprint arXiv:2510\.16499\.Cited by:[§2\.1](https://arxiv.org/html/2608.19993#S2.SS1.p1.1)\.
- Zaheeret al\.\(2017\)M\. Zaheer, S\. Kottur, S\. Ravanbakhsh, B\. Póczos, R\. Salakhutdinov, and A\. J\. SmolaDeep sets\.InAdv\. Neural Inf\. Process\. Syst\. \(NeurIPS\),pp\. 3391–3401\.Cited by:[§5\.2](https://arxiv.org/html/2608.19993#S5.SS2.SSS0.Px2.p1.1)\.
- Zenget al\.\(2026\)K\. Zenget al\.Group of skills: group\-structured skill retrieval for agent skill libraries\.arXiv preprint arXiv:2605\.06978\.Cited by:[§2\.1](https://arxiv.org/html/2608.19993#S2.SS1.p1.1)\.
- Zhang and Luo \(2026\)H\. Zhang and W\. LuoA streaming algorithm for non\-monotone regularized submodular maximization\.Oper\. Res\. Lett\.67,pp\. 107456\.Cited by:[§1](https://arxiv.org/html/2608.19993#S1.p6.1),[§2\.2](https://arxiv.org/html/2608.19993#S2.SS2.p1.1),[§4\.2](https://arxiv.org/html/2608.19993#S4.SS2.SSS0.Px2.p1.1)\.
- Zhanget al\.\(2025\)Y\. Zhanget al\.Qwen3 embedding: advancing text embedding and reranking through foundation models\.arXiv preprint arXiv:2506\.05176\.Cited by:[§5\.4](https://arxiv.org/html/2608.19993#S5.SS4.SSS0.Px3.p1.1)\.
- Zhaoet al\.\(2026\)X\. Zhaoet al\.Generative skill composition for LLM agents\.arXiv preprint arXiv:2606\.32025\.Cited by:[§2\.1](https://arxiv.org/html/2608.19993#S2.SS1.p1.1)\.
- Zhenget al\.\(2026a\)J\. Zhenget al\.SkillSelect\-Serve: QoS\-aware budgeted skill service recommendation for LLM agents\.arXiv preprint arXiv:2607\.00011\.Cited by:[§1](https://arxiv.org/html/2608.19993#S1.p3.1),[§2\.1](https://arxiv.org/html/2608.19993#S2.SS1.p1.1)\.
- Zhenget al\.\(2026b\)Y\. Zhenget al\.SkillRouter: skill routing for LLM agents at scale\.arXiv preprint arXiv:2603\.22455\.Cited by:[§1](https://arxiv.org/html/2608.19993#S1.p2.1),[§1](https://arxiv.org/html/2608.19993#S1.p3.1),[§2\.1](https://arxiv.org/html/2608.19993#S2.SS1.p1.1),[§4\.2](https://arxiv.org/html/2608.19993#S4.SS2.SSS0.Px4.p1.1),[§5\.4](https://arxiv.org/html/2608.19993#S5.SS4.SSS0.Px1.p1.1)\.
- Zhuoet al\.\(2025\)T\. Y\. Zhuoet al\.BigCodeBench: benchmarking code generation with diverse function calls and complex instructions\.InProc\. 13th Int\. Conf\. Learn\. Represent\. \(ICLR\),Cited by:[§5\.1](https://arxiv.org/html/2608.19993#S5.SS1.p1.1)\.

Appendix

## Appendix AMissing Proof in[Section4\.3](https://arxiv.org/html/2608.19993#S4.SS3)

Throughout the appendices we use the notation of[Section4\.3](https://arxiv.org/html/2608.19993#S4.SS3): the seedJ=\{t1,t2\}J=\\\{t\_\{1\},t\_\{2\}\\\}of \([14](https://arxiv.org/html/2608.19993#S4.E14)\), the residual functionffof \([15](https://arxiv.org/html/2608.19993#S4.E15)\), the comparator residualP=T∖JP=T\\setminus Jwith\|T\|≥4\|T\|\\geq 4, the longest residual itemv⋆v^\{\\star\}, the remainderR=P∖\{v⋆\}R=P\\setminus\\\{v^\{\\star\}\\\}, the lengthsp:=ℓ⁡\(\{v⋆\}\)p:=\\ell\(\\\{v^\{\\star\}\\\}\)andr=ℓ⁡\(R\)r=\\ell\(R\)of \([17](https://arxiv.org/html/2608.19993#S4.E17)\), the block order\(X1,X2\)\(X\_\{1\},X\_\{2\}\)of \([19](https://arxiv.org/html/2608.19993#S4.E19)\) withdj=ℓ⁡\(Xj\)d\_\{j\}=\\ell\(X\_\{j\}\)and densitiesρ1=f⁡\(X1\)/d1\\rho\_\{1\}=f\(X\_\{1\}\)/d\_\{1\},ρ2=f⁡\(X2∣X1\)/d2\\rho\_\{2\}=f\(X\_\{2\}\\mid X\_\{1\}\)/d\_\{2\}, the total residual lengthD=ℓ⁡\(P\)=d1\+d2D=\\ell\(P\)=d\_\{1\}\+d\_\{2\}of \([21](https://arxiv.org/html/2608.19993#S4.E21)\), the crossover pointD1D\_\{1\}, the bounding functionφ\\varphiof \([22](https://arxiv.org/html/2608.19993#S4.E22)\), the trajectoryVVof \([18](https://arxiv.org/html/2608.19993#S4.E18)\), andα=1−1/e\\alpha=1\-1/e\. Since\|T\|≥4\|T\|\\geq 4we have\|P\|≥2\|P\|\\geq 2, so both blocks\{v⋆\}\\\{v^\{\\star\}\\\}andRRare nonempty; all item lengths are positive, hence

p\>0,r\>0,d1\>0,d2\>0,D=p\+r\.p\>0,\\qquad r\>0,\\qquad d\_\{1\}\>0,\\qquad d\_\{2\}\>0,\\qquad D=p\+r\.\(25\)Recall from[Section4\.3](https://arxiv.org/html/2608.19993#S4.SS3)thatffis normalized \(f⁡\(∅\)=0f\(\\varnothing\)=0\), nonnegative, nondecreasing, and submodular, and that submodularity with \([19](https://arxiv.org/html/2608.19993#S4.E19)\) givesρ1≥ρ2≥0\\rho\_\{1\}\\geq\\rho\_\{2\}\\geq 0\.

We first record two auxiliary lemmas whose proofs are elementary computations; both are used repeatedly below\.

###### Lemma 5\(Residual marginals and the trajectory\)\.

1. \(i\)For everyU⊆\[L\]U\\subseteq\[L\]andv∈\[L\]v\\in\[L\],f⁡\(v∣U\)=G^​\(v∣J∪U\)≥0f\(v\\mid U\)=\\widehat\{G\}\(v\\mid J\\cup U\)\\geq 0\.
2. \(ii\)VVis continuous, piecewise affine, and nondecreasing on\[0,ℓ⁡\(Am\)\]\[0,\\ell\(A\_\{m\}\)\]; it satisfiesV⁡\(ℓ⁡\(Aj\)\)=f⁡\(Aj\)V\(\\ell\(A\_\{j\}\)\)=f\(A\_\{j\}\)for everyjj, and it is defined on all of\[0,r\]\[0,r\]\.
3. \(iii\)Consider the chain step that selectsaja\_\{j\}from the stateJ∪Aj−1J\\cup A\_\{j\-1\}, and letσj=f⁡\(aj∣Aj−1\)/ℓaj\\sigma\_\{j\}=f\(a\_\{j\}\\mid A\_\{j\-1\}\)/\\ell\_\{a\_\{j\}\}denote its density\. Thenf⁡\(v∣Aj−1\)/ℓ⁡\(\{v\}\)≤σjf\(v\\mid A\_\{j\-1\}\)/\\ell\(\\\{v\\\}\)\\leq\\sigma\_\{j\}for every itemv∉J∪Aj−1v\\notin J\\cup A\_\{j\-1\}that is feasible at that step\.

###### Proof\.

\(i\) Expanding definition \([15](https://arxiv.org/html/2608.19993#S4.E15)\) 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\\mid U\)=f\(U\\cup\\\{v\\\}\)\-f\(U\)=\\bigl\(\\widehat\{G\}\(J\\cup U\\cup\\\{v\\\}\)\-\\widehat\{G\}\(J\)\\bigr\)\-\\bigl\(\\widehat\{G\}\(J\\cup U\)\-\\widehat\{G\}\(J\)\\bigr\)=\\widehat\{G\}\(v\\mid J\\cup U\),which is nonnegative becauseG^\\widehat\{G\}is nondecreasing\.

\(ii\) By construction \([18](https://arxiv.org/html/2608.19993#S4.E18)\),VVis affine on each segment\[ℓ⁡\(Aj−1\),ℓ⁡\(Aj\)\]\[\\ell\(A\_\{j\-1\}\),\\ell\(A\_\{j\}\)\]with slopeσj=f⁡\(aj∣Aj−1\)/ℓaj\\sigma\_\{j\}=f\(a\_\{j\}\\mid A\_\{j\-1\}\)/\\ell\_\{a\_\{j\}\}, and its value at the right endpoint of segmentjjtelescopes toV⁡\(ℓ⁡\(Aj\)\)=f⁡\(Aj−1\)\+f⁡\(aj∣Aj−1\)=f⁡\(Aj\)V\(\\ell\(A\_\{j\}\)\)=f\(A\_\{j\-1\}\)\+f\(a\_\{j\}\\mid A\_\{j\-1\}\)=f\(A\_\{j\}\), which equals the value used at the left endpoint of segmentj\+1j\+1; henceVVis continuous\. Each slope satisfiesσj≥0\\sigma\_\{j\}\\geq 0by \(i\) andℓaj\>0\\ell\_\{a\_\{j\}\}\>0, soVVis nondecreasing\. Finally,ℓ⁡\(Am\)≥r\\ell\(A\_\{m\}\)\\geq rby[Lemma1](https://arxiv.org/html/2608.19993#Thmlemma1), so\[0,r\]\[0,r\]lies in the domain ofVV\.

\(iii\) Line 6 of[Algorithm1](https://arxiv.org/html/2608.19993#alg1)selects, among all itemsi∉J∪Aj−1i\\notin J\\cup A\_\{j\-1\}that are feasible at the current stateS=J∪Aj−1S=J\\cup A\_\{j\-1\}, one maximizingG^​\(i∣S\)/ℓi\\widehat\{G\}\(i\\mid S\)/\\ell\_\{i\}\. By \(i\),G^​\(v∣J∪Aj−1\)=f⁡\(v∣Aj−1\)\\widehat\{G\}\(v\\mid J\\cup A\_\{j\-1\}\)=f\(v\\mid A\_\{j\-1\}\)for every suchvv, so maximizing the density with respect toG^\\widehat\{G\}is the same as maximizing it with respect toff; in particular the selected itemaja\_\{j\}satisfiesf⁡\(v∣Aj−1\)/ℓ⁡\(\{v\}\)≤f⁡\(aj∣Aj−1\)/ℓaj=σjf\(v\\mid A\_\{j\-1\}\)/\\ell\(\\\{v\\\}\)\\leq f\(a\_\{j\}\\mid A\_\{j\-1\}\)/\\ell\_\{a\_\{j\}\}=\\sigma\_\{j\}for every feasiblevv\. ∎

###### Lemma 6\(Properties of the bounding function\)\.

The functionφ\\varphiof \([22](https://arxiv.org/html/2608.19993#S4.E22)\) satisfies:

1. \(i\)φ⁡\(0\)=0\\varphi\(0\)=0; this holds on the first branch whenD1\>0D\_\{1\}\>0and on the second branch whenD1=0D\_\{1\}=0\.
2. \(ii\)If0<D1<\+∞0<D\_\{1\}<\+\\infty, the two branches agree atu=D1u=D\_\{1\}, soφ\\varphiis continuous on\[0,∞\)\[0,\\infty\)\.
3. \(iii\)On the first branch\(0,D1\)\(0,D\_\{1\}\),φ′​\(u\)=\(f⁡\(X1\)−φ⁡\(u\)\)/d1\\varphi^\{\\prime\}\(u\)=\\bigl\(f\(X\_\{1\}\)\-\\varphi\(u\)\\bigr\)/d\_\{1\}; on the second branch\(D1,∞\)\(D\_\{1\},\\infty\),φ′​\(u\)=\(f⁡\(P\)−φ⁡\(u\)\)/D\\varphi^\{\\prime\}\(u\)=\\bigl\(f\(P\)\-\\varphi\(u\)\\bigr\)/D\.

###### Proof\.

We use throughout the chain\-rule decomposition

f⁡\(P\)=f⁡\(X1\)\+f⁡\(X2∣X1\)=f⁡\(X1\)\+ρ2​d2=ρ1​d1\+ρ2​d2\.f\(P\)=f\(X\_\{1\}\)\+f\(X\_\{2\}\\mid X\_\{1\}\)=f\(X\_\{1\}\)\+\\rho\_\{2\}d\_\{2\}=\\rho\_\{1\}d\_\{1\}\+\\rho\_\{2\}d\_\{2\}\.\(26\)
\(i\) IfD1\>0D\_\{1\}\>0, the first branch givesφ⁡\(0\)=f⁡\(X1\)​\(1−e0\)=0\\varphi\(0\)=f\(X\_\{1\}\)\(1\-e^\{0\}\)=0\. IfD1=0D\_\{1\}=0, then by definition ofD1D\_\{1\}we haveρ2\>0\\rho\_\{2\}\>0andd1​ln⁡\(ρ1/ρ2\)=0d\_\{1\}\\ln\(\\rho\_\{1\}/\\rho\_\{2\}\)=0, henceρ1=ρ2\\rho\_\{1\}=\\rho\_\{2\}; the second branch then gives, using \([26](https://arxiv.org/html/2608.19993#A1.E26)\),φ⁡\(0\)=f⁡\(P\)−ρ2​D​e0=ρ1​d1\+ρ2​d2−ρ2​\(d1\+d2\)=0\\varphi\(0\)=f\(P\)\-\\rho\_\{2\}De^\{0\}=\\rho\_\{1\}d\_\{1\}\+\\rho\_\{2\}d\_\{2\}\-\\rho\_\{2\}\(d\_\{1\}\+d\_\{2\}\)=0\.

\(ii\) Let0<D1<\+∞0<D\_\{1\}<\+\\infty, soρ2\>0\\rho\_\{2\}\>0ande−D1/d1=ρ2/ρ1e^\{\-D\_\{1\}/d\_\{1\}\}=\\rho\_\{2\}/\\rho\_\{1\}\. The left limit atD1D\_\{1\}along the first branch is

f\(X1\)\(1−e−D1/d1\)=f\(X1\)\(1−ρ2ρ1\)=f\(X1\)−ρ2d1,f\(X\_\{1\}\)\\bigl\(1\-e^\{\-D\_\{1\}/d\_\{1\}\}\\bigr\)=f\(X\_\{1\}\)\\Bigl\(1\-\\frac\{\\rho\_\{2\}\}\{\\rho\_\{1\}\}\\Bigr\)=f\(X\_\{1\}\)\-\\rho\_\{2\}d\_\{1\},where the last step usesf⁡\(X1\)=ρ1​d1f\(X\_\{1\}\)=\\rho\_\{1\}d\_\{1\}\. The value atD1D\_\{1\}on the second branch isf⁡\(P\)−ρ2​D​e0=f⁡\(P\)−ρ2​\(d1\+d2\)f\(P\)\-\\rho\_\{2\}De^\{0\}=f\(P\)\-\\rho\_\{2\}\(d\_\{1\}\+d\_\{2\}\), which equalsf⁡\(X1\)−ρ2​d1f\(X\_\{1\}\)\-\\rho\_\{2\}d\_\{1\}by \([26](https://arxiv.org/html/2608.19993#A1.E26)\)\. The two branches agree, and each branch is continuous, soφ\\varphiis continuous\.

\(iii\) On\(0,D1\)\(0,D\_\{1\}\), differentiatingφ\(u\)=f\(X1\)\(1−e−u/d1\)\\varphi\(u\)=f\(X\_\{1\}\)\(1\-e^\{\-u/d\_\{1\}\}\)givesφ′\(u\)=f⁡\(X1\)d1e−u/d1\\varphi^\{\\prime\}\(u\)=\\frac\{f\(X\_\{1\}\)\}\{d\_\{1\}\}e^\{\-u/d\_\{1\}\}, whilef\(X1\)−φ\(u\)=f\(X1\)e−u/d1f\(X\_\{1\}\)\-\\varphi\(u\)=f\(X\_\{1\}\)e^\{\-u/d\_\{1\}\}; dividing byd1d\_\{1\}matches\. On\(D1,∞\)\(D\_\{1\},\\infty\), differentiatingφ⁡\(u\)=f⁡\(P\)−ρ2​D​exp⁡\(−u−D1D\)\\varphi\(u\)=f\(P\)\-\\rho\_\{2\}D\\exp\\bigl\(\-\\frac\{u\-D\_\{1\}\}\{D\}\\bigr\)givesφ′​\(u\)=ρ2​exp⁡\(−u−D1D\)\\varphi^\{\\prime\}\(u\)=\\rho\_\{2\}\\exp\\bigl\(\-\\frac\{u\-D\_\{1\}\}\{D\}\\bigr\), whilef⁡\(P\)−φ⁡\(u\)=ρ2​D​exp⁡\(−u−D1D\)f\(P\)\-\\varphi\(u\)=\\rho\_\{2\}D\\exp\\bigl\(\-\\frac\{u\-D\_\{1\}\}\{D\}\\bigr\); dividing byDDmatches\. ∎

### A\.1\. Proof of[Lemma3](https://arxiv.org/html/2608.19993#Thmlemma3)

###### Proof\.

The proof has three steps: a density lower bound valid on every segment that starts beforerr\(Step 1\), a differential inequality for the differenceW=V−φW=V\-\\varphion each branch \(Step 2\), and a piecewise integrating\-factor argument that propagatesW≥0W\\geq 0across the finitely many breakpoints \(Step 3\)\. Step 4 checks that all placements ofD1D\_\{1\}relative to\[0,r\]\[0,r\]are covered\.

*Step 1 \(density lower bound\)\.*Fix an accepted segment starting atAj−1A\_\{j\-1\}with left endpointu0=ℓ⁡\(Aj−1\)<ru\_\{0\}=\\ell\(A\_\{j\-1\}\)<r, and letσj=f⁡\(aj∣Aj−1\)/ℓaj\\sigma\_\{j\}=f\(a\_\{j\}\\mid A\_\{j\-1\}\)/\\ell\_\{a\_\{j\}\}be the density of the item selected by[Algorithm1](https://arxiv.org/html/2608.19993#alg1)on that segment\. LetQ⊆PQ\\subseteq Pbe any set such that every member ofQ∖Aj−1Q\\setminus A\_\{j\-1\}is feasible at this step; by[Lemma2](https://arxiv.org/html/2608.19993#Thmlemma2), this holds for*every*Q⊆PQ\\subseteq P, sinceu0<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\)\\;\\leq\\;f\(A\_\{j\-1\}\\cup Q\)\\;\\leq\\;f\(A\_\{j\-1\}\)\+\\\!\\\!\\sum\_\{v\\in Q\\setminus A\_\{j\-1\}\}\\\!\\\!f\(v\\mid A\_\{j\-1\}\)\\;\\leq\\;f\(A\_\{j\-1\}\)\+\\sigma\_\{j\}\\,\\ell\(Q\)\.\(27\)The first inequality is monotonicity offf\. For the second, enumerateQ∖Aj−1=\{v1,…,vs\}Q\\setminus A\_\{j\-1\}=\\\{v\_\{1\},\\dots,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\}\\cup Q\)\-f\(A\_\{j\-1\}\)=\\sum\_\{k=1\}^\{s\}f\\bigl\(v\_\{k\}\\mid A\_\{j\-1\}\\cup\\\{v\_\{1\},\\dots,v\_\{k\-1\}\\\}\\bigr\)\\leq\\sum\_\{k=1\}^\{s\}f\(v\_\{k\}\\mid A\_\{j\-1\}\),where each summand is bounded via submodularity offf\(conditioning on a superset ofAj−1A\_\{j\-1\}can only decrease the marginal\)\. For the third inequality, everyv∈Q∖Aj−1v\\in Q\\setminus A\_\{j\-1\}is feasible at this step, so[Lemma5](https://arxiv.org/html/2608.19993#Thmlemma5)\(iii\) givesf⁡\(v∣Aj−1\)≤σj​ℓ​\(\{v\}\)f\(v\\mid A\_\{j\-1\}\)\\leq\\sigma\_\{j\}\\ell\(\\\{v\\\}\); summing overQ∖Aj−1Q\\setminus A\_\{j\-1\}and usingσj≥0\\sigma\_\{j\}\\geq 0together withℓ⁡\(Q∖Aj−1\)≤ℓ⁡\(Q\)\\ell\(Q\\setminus A\_\{j\-1\}\)\\leq\\ell\(Q\)\(lengths are positive\) yields the claim\. Rearranging \([27](https://arxiv.org/html/2608.19993#A1.E27)\) and usingℓ⁡\(Q\)\>0\\ell\(Q\)\>0,

σj≥f⁡\(Q\)−f⁡\(Aj−1\)ℓ⁡\(Q\)≥f⁡\(Q\)−V⁡\(u\)ℓ⁡\(Q\)for every​u∈\[ℓ⁡\(Aj−1\),ℓ⁡\(Aj\)\],\\sigma\_\{j\}\\;\\geq\\;\\frac\{f\(Q\)\-f\(A\_\{j\-1\}\)\}\{\\ell\(Q\)\}\\;\\geq\\;\\frac\{f\(Q\)\-V\(u\)\}\{\\ell\(Q\)\}\\qquad\\text\{for every \}u\\in\[\\ell\(A\_\{j\-1\}\),\\ell\(A\_\{j\}\)\],\(28\)where the second inequality holds becauseVVis nondecreasing \([Lemma5](https://arxiv.org/html/2608.19993#Thmlemma5)\(ii\)\) withV⁡\(ℓ⁡\(Aj−1\)\)=f⁡\(Aj−1\)V\(\\ell\(A\_\{j\-1\}\)\)=f\(A\_\{j\-1\}\), soV⁡\(u\)≥f⁡\(Aj−1\)V\(u\)\\geq f\(A\_\{j\-1\}\)on the whole segment\. SinceX1⊆PX\_\{1\}\\subseteq PandP⊆PP\\subseteq P, inequality \([28](https://arxiv.org/html/2608.19993#A1.E28)\) is available both forQ=X1Q=X\_\{1\}and forQ=PQ=Pon every segment starting beforerr\.

*Step 2 \(differential inequality on each branch\)\.*Consider the differenceW⁡\(u\):=V⁡\(u\)−φ⁡\(u\)W\(u\):=V\(u\)\-\\varphi\(u\)on\[0,r\]\[0,r\]\. BothVVandφ\\varphiare continuous \([Lemma5](https://arxiv.org/html/2608.19993#Thmlemma5)\(ii\) and[Lemma6](https://arxiv.org/html/2608.19993#Thmlemma6)\(ii\)\), soWWis continuous\. Partition\[0,min⁡\(r,D1\)\]\[0,\\min\(r,D\_\{1\}\)\]\(and, whenD1<rD\_\{1\}<r, also\[D1,r\]\[D\_\{1\},r\]\) by the finitely many trajectory breakpointsℓ⁡\(A0\)<ℓ⁡\(A1\)<⋯\\ell\(A\_\{0\}\)<\\ell\(A\_\{1\}\)<\\cdotsfalling in the respective interval\. On the interior of each cell of this partition,VVis affine withV′​\(u\)=σjV^\{\\prime\}\(u\)=\\sigma\_\{j\}for the segment indexjjcontaining the cell, andφ\\varphiis differentiable \([Lemma6](https://arxiv.org/html/2608.19993#Thmlemma6)\(iii\)\)\.

*First branch\.*Letuulie in the interior of a cell of\[0,min⁡\(r,D1\)\]\[0,\\min\(r,D\_\{1\}\)\]\. The segment containinguuhas left endpointu0≤u<ru\_\{0\}\\leq u<r, so \([28](https://arxiv.org/html/2608.19993#A1.E28)\) applies withQ=X1Q=X\_\{1\}, and[Lemma6](https://arxiv.org/html/2608.19993#Thmlemma6)\(iii\) gives the ODE forφ\\varphi\. Subtracting,

W′​\(u\)=V′​\(u\)−φ′​\(u\)≥f⁡\(X1\)−V⁡\(u\)d1−f⁡\(X1\)−φ⁡\(u\)d1=−W⁡\(u\)d1\.W^\{\\prime\}\(u\)=V^\{\\prime\}\(u\)\-\\varphi^\{\\prime\}\(u\)\\;\\geq\\;\\frac\{f\(X\_\{1\}\)\-V\(u\)\}\{d\_\{1\}\}\-\\frac\{f\(X\_\{1\}\)\-\\varphi\(u\)\}\{d\_\{1\}\}\\;=\\;\-\\frac\{W\(u\)\}\{d\_\{1\}\}\.\(29\)
*Second branch\.*LetD1<rD\_\{1\}<rand letuulie in the interior of a cell of\[D1,r\]\[D\_\{1\},r\]\. Again the segment containinguuhas left endpointu0<ru\_\{0\}<r, so \([28](https://arxiv.org/html/2608.19993#A1.E28)\) applies withQ=PQ=P, and the same subtraction gives

W′​\(u\)≥f⁡\(P\)−V⁡\(u\)D−f⁡\(P\)−φ⁡\(u\)D=−W⁡\(u\)D\.W^\{\\prime\}\(u\)\\;\\geq\\;\\frac\{f\(P\)\-V\(u\)\}\{D\}\-\\frac\{f\(P\)\-\\varphi\(u\)\}\{D\}\\;=\\;\-\\frac\{W\(u\)\}\{D\}\.\(30\)
*Step 3 \(integrating factor and propagation across breakpoints\)\.*Fix a branch and writeℓQ\\ell\_\{Q\}for its rate constant \(ℓQ=d1\\ell\_\{Q\}=d\_\{1\}on the first branch,ℓQ=D\\ell\_\{Q\}=Don the second\)\. On the interior of each cell,

dd​u​\(eu/ℓQ​W​\(u\)\)=eu/ℓQ​\(W′​\(u\)\+W⁡\(u\)ℓQ\)≥0\\frac\{\\mathrm\{d\}\}\{\\mathrm\{d\}u\}\\Bigl\(e^\{u/\\ell\_\{Q\}\}\\,W\(u\)\\Bigr\)=e^\{u/\\ell\_\{Q\}\}\\Bigl\(W^\{\\prime\}\(u\)\+\\frac\{W\(u\)\}\{\\ell\_\{Q\}\}\\Bigr\)\\;\\geq\\;0\(31\)by \([29](https://arxiv.org/html/2608.19993#A1.E29)\) or \([30](https://arxiv.org/html/2608.19993#A1.E30)\)\. Henceeu/ℓQ​W​\(u\)e^\{u/\\ell\_\{Q\}\}W\(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, ifW≥0W\\geq 0at the left endpoint of the branch interval, theneu/ℓQ​W​\(u\)≥0e^\{u/\\ell\_\{Q\}\}W\(u\)\\geq 0, henceW⁡\(u\)≥0W\(u\)\\geq 0, throughout that interval\.

It remains to check the left\-endpoint values\. On\[0,min⁡\(r,D1\)\]\[0,\\min\(r,D\_\{1\}\)\]the left endpoint isu=0u=0, whereW⁡\(0\)=V⁡\(0\)−φ⁡\(0\)=0−0=0W\(0\)=V\(0\)\-\\varphi\(0\)=0\-0=0by \([18](https://arxiv.org/html/2608.19993#S4.E18)\) and[Lemma6](https://arxiv.org/html/2608.19993#Thmlemma6)\(i\)\. On\[D1,r\]\[D\_\{1\},r\]\(when0<D1<r0<D\_\{1\}<r\) the left endpoint isu=D1u=D\_\{1\}, where the first\-branch conclusion and continuity ofWWgiveW⁡\(D1\)≥0W\(D\_\{1\}\)\\geq 0\. WhenD1=0D\_\{1\}=0, the left endpoint of the second\-branch interval isu=0u=0, and[Lemma6](https://arxiv.org/html/2608.19993#Thmlemma6)\(i\) again givesW⁡\(0\)=0W\(0\)=0\.

*Step 4\.*IfD1≥rD\_\{1\}\\geq r\(includingD1=\+∞D\_\{1\}=\+\\infty, which occurs whenρ2=0\\rho\_\{2\}=0\), then\[0,r\]⊆\[0,min⁡\(r,D1\)\]\[0,r\]\\subseteq\[0,\\min\(r,D\_\{1\}\)\]and the first\-branch argument alone givesW≥0W\\geq 0on\[0,r\]\[0,r\]\. IfD1=0D\_\{1\}=0, then only the second branch is active on\[0,r\]\[0,r\], with initial valueW⁡\(0\)=0W\(0\)=0\. If0<D1<r0<D\_\{1\}<r, the first\-branch argument givesW≥0W\\geq 0on\[0,D1\]\[0,D\_\{1\}\]and the second\-branch argument extends it to\[D1,r\]\[D\_\{1\},r\]\. In every caseV⁡\(u\)≥φ⁡\(u\)V\(u\)\\geq\\varphi\(u\)for allu∈\[0,r\]u\\in\[0,r\], which is the claim of[Lemma3](https://arxiv.org/html/2608.19993#Thmlemma3)\. ∎

### A\.2\. Proof of Lemma[4](https://arxiv.org/html/2608.19993#Thmlemma4)

We use the following standard inequality; we include its one\-line proof for completeness\.

###### Lemma 7\(Log\-sum inequality\)\.

For positive realsa1,a2,b1,b2a\_\{1\},a\_\{2\},b\_\{1\},b\_\{2\},

a1​ln⁡b1a1\+a2​ln⁡b2a2≤\(a1\+a2\)​ln⁡b1\+b2a1\+a2\.a\_\{1\}\\ln\\frac\{b\_\{1\}\}\{a\_\{1\}\}\+a\_\{2\}\\ln\\frac\{b\_\{2\}\}\{a\_\{2\}\}\\;\\leq\\;\(a\_\{1\}\+a\_\{2\}\)\\ln\\frac\{b\_\{1\}\+b\_\{2\}\}\{a\_\{1\}\+a\_\{2\}\}\.\(32\)

###### Proof\.

Apply Jensen’s inequality to the concave functionln\\lnwith weightsλi=ai/\(a1\+a2\)\\lambda\_\{i\}=a\_\{i\}/\(a\_\{1\}\+a\_\{2\}\)and pointsui=bi/aiu\_\{i\}=b\_\{i\}/a\_\{i\}:

a1a1\+a2​ln⁡b1a1\+a2a1\+a2​ln⁡b2a2≤ln⁡\(a1a1\+a2⋅b1a1\+a2a1\+a2⋅b2a2\)=ln⁡b1\+b2a1\+a2\.\\frac\{a\_\{1\}\}\{a\_\{1\}\+a\_\{2\}\}\\ln\\frac\{b\_\{1\}\}\{a\_\{1\}\}\+\\frac\{a\_\{2\}\}\{a\_\{1\}\+a\_\{2\}\}\\ln\\frac\{b\_\{2\}\}\{a\_\{2\}\}\\;\\leq\\;\\ln\\Bigl\(\\frac\{a\_\{1\}\}\{a\_\{1\}\+a\_\{2\}\}\\cdot\\frac\{b\_\{1\}\}\{a\_\{1\}\}\+\\frac\{a\_\{2\}\}\{a\_\{1\}\+a\_\{2\}\}\\cdot\\frac\{b\_\{2\}\}\{a\_\{2\}\}\\Bigr\)=\\ln\\frac\{b\_\{1\}\+b\_\{2\}\}\{a\_\{1\}\+a\_\{2\}\}\.Multiplying both sides bya1\+a2\>0a\_\{1\}\+a\_\{2\}\>0gives \([32](https://arxiv.org/html/2608.19993#A1.E32)\)\. ∎

###### Proof of Lemma[4](https://arxiv.org/html/2608.19993#Thmlemma4)\.

AbbreviateC:=G^​\(J\)C:=\\widehat\{G\}\(J\)andH:=G^​\(T\)H:=\\widehat\{G\}\(T\)for the duration of this proof\. SinceJ∪P=TJ\\cup P=T, definition \([15](https://arxiv.org/html/2608.19993#S4.E15)\) gives

f⁡\(P\)=G^​\(T\)−G^​\(J\)=H−C\.f\(P\)=\\widehat\{G\}\(T\)\-\\widehat\{G\}\(J\)=H\-C\.\(33\)
*Step 0 \(reduction and common identities\)\.*Iff⁡\(P\)=0f\(P\)=0, thenH=CH=Cby \([33](https://arxiv.org/html/2608.19993#A1.E33)\), and sinceφ≥0\\varphi\\geq 0\(both branches of \([22](https://arxiv.org/html/2608.19993#S4.E22)\) are nonnegative: the first is a nonnegative multiple of1−e−u/d1≥01\-e^\{\-u/d\_\{1\}\}\\geq 0, and the second is bounded below by its value atu=D1u=D\_\{1\}, which equals the first\-branch valuef\(X1\)\(1−e−D1/d1\)≥0f\(X\_\{1\}\)\(1\-e^\{\-D\_\{1\}/d\_\{1\}\}\)\\geq 0by[Lemma6](https://arxiv.org/html/2608.19993#Thmlemma6)\(ii\)\),

C\+φ⁡\(r\)≥C=H≥α​H\.C\+\\varphi\(r\)\\geq C=H\\geq\\alpha H\.Assume from now on thatf⁡\(P\)\>0f\(P\)\>0\. Thenρ1\>0\\rho\_\{1\}\>0: otherwisef⁡\(X1\)=0f\(X\_\{1\}\)=0, and the block order \([19](https://arxiv.org/html/2608.19993#S4.E19)\) forcesf⁡\(X2\)≤d2d1​f​\(X1\)=0f\(X\_\{2\}\)\\leq\\frac\{d\_\{2\}\}\{d\_\{1\}\}f\(X\_\{1\}\)=0, whence by submodularityf⁡\(X2∣X1\)≤f⁡\(X2\)=0f\(X\_\{2\}\\mid X\_\{1\}\)\\leq f\(X\_\{2\}\)=0andf⁡\(P\)=f⁡\(X1\)\+f⁡\(X2∣X1\)≤0f\(P\)=f\(X\_\{1\}\)\+f\(X\_\{2\}\\mid X\_\{1\}\)\\leq 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\)=\\begin\{cases\}\\bigl\(f\(\\\{v^\{\\star\}\\\}\),\\;f\(R\\mid\\\{v^\{\\star\}\\\}\)\\bigr\),&X\_\{1\}=\\\{v^\{\\star\}\\\},\\\\\[3\.00003pt\] \\bigl\(f\(v^\{\\star\}\\mid R\),\\;f\(R\)\\bigr\),&X\_\{1\}=R\.\\end\{cases\}\(34\)In both orders the chain rule givesx\+z=f⁡\(P\)x\+z=f\(P\), so by \([33](https://arxiv.org/html/2608.19993#A1.E33)\),

In both orders we also have

Indeed, ifX1=\{v⋆\}X\_\{1\}=\\\{v^\{\\star\}\\\}thenx=f⁡\(\{v⋆\}\)x=f\(\\\{v^\{\\star\}\\\}\)and \([16](https://arxiv.org/html/2608.19993#S4.E16)\) applies directly withv=v⋆v=v^\{\\star\}; ifX1=RX\_\{1\}=Rthen submodularity givesx=f⁡\(v⋆∣R\)≤f⁡\(\{v⋆\}\)x=f\(v^\{\\star\}\\mid R\)\\leq f\(\\\{v^\{\\star\}\\\}\), and \([16](https://arxiv.org/html/2608.19993#S4.E16)\) givesC≥2​f​\(\{v⋆\}\)≥2​xC\\geq 2f\(\\\{v^\{\\star\}\\\}\)\\geq 2x\.

Finally, recall the block data in the two orders\. IfX1=\{v⋆\}X\_\{1\}=\\\{v^\{\\star\}\\\}:d1=pd\_\{1\}=p,d2=rd\_\{2\}=r,ρ1=x/p\\rho\_\{1\}=x/p,ρ2=z/r\\rho\_\{2\}=z/r\. IfX1=RX\_\{1\}=R:d1=rd\_\{1\}=r,d2=pd\_\{2\}=p,ρ1=z/r\\rho\_\{1\}=z/r,ρ2=x/p\\rho\_\{2\}=x/p\. In both orders, wheneverx,z\>0x,z\>0,

d1​ln​ρ1\+d2​ln​ρ2=p​ln​xp\+r​ln​zr,d\_\{1\}\\ln\\rho\_\{1\}\+d\_\{2\}\\ln\\rho\_\{2\}\\;=\\;p\\ln\\frac\{x\}\{p\}\+r\\ln\\frac\{z\}\{r\},\(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](https://arxiv.org/html/2608.19993#bib.bib23); Step 4 verifies that they are exhaustive\.

*Step 1 \(Case 1:r≥D1r\\geq D\_\{1\}\)\.*Sincer<∞r<\\infty, the case condition forcesD1<∞D\_\{1\}<\\infty, henceρ2\>0\\rho\_\{2\}\>0by the definition ofD1D\_\{1\}, and withρ1≥ρ2\\rho\_\{1\}\\geq\\rho\_\{2\}both block values are positive; reading off the block data above, this means

x\>0andz\>0x\>0\\quad\\text\{and\}\\quad z\>0in both orders, so every logarithm below has a strictly positive argument\. Becauser≥D1r\\geq D\_\{1\}, the second branch of \([22](https://arxiv.org/html/2608.19993#S4.E22)\) evaluatesφ⁡\(r\)\\varphi\(r\), and by \([33](https://arxiv.org/html/2608.19993#A1.E33)\) and \([35](https://arxiv.org/html/2608.19993#A1.E35)\),

C\+φ⁡\(r\)=C\+f⁡\(P\)−ρ2​D​exp⁡\(−r−D1D\)=H−ρ2​D​exp⁡\(−r−D1D\)\.C\+\\varphi\(r\)=C\+f\(P\)\-\\rho\_\{2\}D\\exp\\Bigl\(\-\\frac\{r\-D\_\{1\}\}\{D\}\\Bigr\)=H\-\\rho\_\{2\}D\\exp\\Bigl\(\-\\frac\{r\-D\_\{1\}\}\{D\}\\Bigr\)\.\(38\)It therefore suffices to bound the exponential tail byH/eH/e\.

First, combining \([36](https://arxiv.org/html/2608.19993#A1.E36)\) with \([35](https://arxiv.org/html/2608.19993#A1.E35)\),

H−z=C\+x≥2​x\+x=3​x\.H\-z=C\+x\\geq 2x\+x=3x\.\(39\)Next we bound the weighted\-log expression \([37](https://arxiv.org/html/2608.19993#A1.E37)\)\. Usingx≤\(H−z\)/3x\\leq\(H\-z\)/3from \([39](https://arxiv.org/html/2608.19993#A1.E39)\) and the monotonicity ofln\\ln, then splitting offln⁡3\\ln 3, then applying[Lemma7](https://arxiv.org/html/2608.19993#Thmlemma7)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 usingln⁡3\>1\\ln 3\>1withp\>0p\>0:

p​ln⁡xp\+r​ln⁡zr\\displaystyle p\\ln\\frac\{x\}\{p\}\+r\\ln\\frac\{z\}\{r\}≤p​ln⁡H−z3​p\+r​ln⁡zr\\displaystyle\\leq p\\ln\\frac\{H\-z\}\{3p\}\+r\\ln\\frac\{z\}\{r\}\(40\)=−p​ln⁡3\+p​ln⁡H−zp\+r​ln⁡zr\\displaystyle=\-\\,p\\ln 3\+p\\ln\\frac\{H\-z\}\{p\}\+r\\ln\\frac\{z\}\{r\}≤−p​ln⁡3\+D​ln⁡HD\\displaystyle\\leq\-\\,p\\ln 3\+D\\ln\\frac\{H\}\{D\}≤−p\+D​ln⁡HD\.\\displaystyle\\leq\-\\,p\+D\\ln\\frac\{H\}\{D\}\.Now rewrite the exponential tail\. Usingr=D−pr=D\-p,

ρ2​D​exp⁡\(−r−D1D\)=D​exp⁡\(ln⁡ρ2−D−p−D1D\)=D​exp⁡\(−1\+p\+D1D\+ln⁡ρ2\),\\rho\_\{2\}D\\exp\\Bigl\(\-\\frac\{r\-D\_\{1\}\}\{D\}\\Bigr\)=D\\exp\\Bigl\(\\ln\\rho\_\{2\}\-\\frac\{D\-p\-D\_\{1\}\}\{D\}\\Bigr\)=D\\exp\\Bigl\(\-1\+\\frac\{p\+D\_\{1\}\}\{D\}\+\\ln\\rho\_\{2\}\\Bigr\),and sinceD1=d1​ln⁡\(ρ1/ρ2\)D\_\{1\}=d\_\{1\}\\ln\(\\rho\_\{1\}/\\rho\_\{2\}\)andD=d1\+d2D=d\_\{1\}\+d\_\{2\},

D1D\+ln⁡ρ2=d1​ln⁡ρ1−d1​ln⁡ρ2\+D​ln⁡ρ2D=d1​ln⁡ρ1\+d2​ln⁡ρ2D,\\frac\{D\_\{1\}\}\{D\}\+\\ln\\rho\_\{2\}=\\frac\{d\_\{1\}\\ln\\rho\_\{1\}\-d\_\{1\}\\ln\\rho\_\{2\}\+D\\ln\\rho\_\{2\}\}\{D\}=\\frac\{d\_\{1\}\\ln\\rho\_\{1\}\+d\_\{2\}\\ln\\rho\_\{2\}\}\{D\},so that, by \([37](https://arxiv.org/html/2608.19993#A1.E37)\),

ρ2​D​exp⁡\(−r−D1D\)=D​exp⁡\(−1\+p\+p​ln⁡xp\+r​ln⁡zrD\)\.\\rho\_\{2\}D\\exp\\Bigl\(\-\\frac\{r\-D\_\{1\}\}\{D\}\\Bigr\)=D\\exp\\Bigl\(\-1\+\\frac\{p\+p\\ln\\frac\{x\}\{p\}\+r\\ln\\frac\{z\}\{r\}\}\{D\}\\Bigr\)\.\(41\)Substituting the bound \([40](https://arxiv.org/html/2608.19993#A1.E40)\) into \([41](https://arxiv.org/html/2608.19993#A1.E41)\) and using the monotonicity ofexp\\exp,

ρ2​D​exp⁡\(−r−D1D\)≤D​exp⁡\(−1\+D​ln⁡\(H/D\)D\)=D⋅1e⋅HD=He\.\\rho\_\{2\}D\\exp\\Bigl\(\-\\frac\{r\-D\_\{1\}\}\{D\}\\Bigr\)\\;\\leq\\;D\\exp\\Bigl\(\-1\+\\frac\{D\\ln\(H/D\)\}\{D\}\\Bigr\)=D\\cdot\\frac\{1\}\{e\}\\cdot\\frac\{H\}\{D\}=\\frac\{H\}\{e\}\.\(42\)Combining \([38](https://arxiv.org/html/2608.19993#A1.E38)\) and \([42](https://arxiv.org/html/2608.19993#A1.E42)\),

C\+φ⁡\(r\)≥H−He=α​H\.C\+\\varphi\(r\)\\;\\geq\\;H\-\\frac\{H\}\{e\}\\;=\\;\\alpha H\.The boundary subcases are included:r=D1r=D\_\{1\}uses the second branch of \([22](https://arxiv.org/html/2608.19993#S4.E22)\), which is defined for allu≥D1u\\geq D\_\{1\}, andD1=0D\_\{1\}=0poses no difficulty since only the case conditionr≥D1r\\geq D\_\{1\}was used\.

*Step 2 \(Case 2:r<D1r<D\_\{1\}andX1=\{v⋆\}X\_\{1\}=\\\{v^\{\\star\}\\\}\)\.*Herex=f⁡\(\{v⋆\}\)x=f\(\\\{v^\{\\star\}\\\}\),z=f⁡\(R∣\{v⋆\}\)z=f\(R\\mid\\\{v^\{\\star\}\\\}\),d1=pd\_\{1\}=p, and we write

δ:=rp\>0\.\\delta:=\\frac\{r\}\{p\}\>0\.\(43\)Notex=ρ1​p\>0x=\\rho\_\{1\}p\>0becauseρ1\>0\\rho\_\{1\}\>0\(Step 0\)\. Sincer<D1r<D\_\{1\}, the first branch of \([22](https://arxiv.org/html/2608.19993#S4.E22)\) evaluatesφ⁡\(r\)\\varphi\(r\):

φ\(r\)=x\(1−e−r/p\)=x\(1−e−δ\)\.\\varphi\(r\)=x\\bigl\(1\-e^\{\-r/p\}\\bigr\)=x\\bigl\(1\-e^\{\-\\delta\}\\bigr\)\.\(44\)
Suppose firstz\>0z\>0\. Thenρ2=z/r\>0\\rho\_\{2\}=z/r\>0and the case conditionr<D1=p​ln⁡x/pz/rr<D\_\{1\}=p\\ln\\frac\{x/p\}\{z/r\}can be divided byp\>0p\>0to read

δ<ln⁡\(xp⋅rz\)=ln⁡\(xz​δ\)\.\\delta\\;<\\;\\ln\\Bigl\(\\frac\{x\}\{p\}\\cdot\\frac\{r\}\{z\}\\Bigr\)\\;=\\;\\ln\\Bigl\(\\frac\{x\}\{z\}\\,\\delta\\Bigr\)\.Exponentiating giveseδ<xz​δe^\{\\delta\}<\\frac\{x\}\{z\}\\delta, i\.e\.,

x\>z​eδδ\.x\\;\>\\;z\\,\\frac\{e^\{\\delta\}\}\{\\delta\}\.\(45\)We now chain the estimates; each line is justified below:

C\+φ⁡\(r\)\\displaystyle C\+\\varphi\(r\)=C\+x⁡\(1−e−δ\)\\displaystyle=C\+x\\bigl\(1\-e^\{\-\\delta\}\\bigr\)\(46\)=23​\(C\+x\)\+\[13​\(C\+x\)−x​e−δ\]\\displaystyle=\\tfrac\{2\}\{3\}\(C\+x\)\+\\Bigl\[\\tfrac\{1\}\{3\}\(C\+x\)\-xe^\{\-\\delta\}\\Bigr\]≥23​\(C\+x\)\+x⁡\(1−e−δ\)\\displaystyle\\geq\\tfrac\{2\}\{3\}\(C\+x\)\+x\\bigl\(1\-e^\{\-\\delta\}\\bigr\)\>23​\(C\+x\)\+z​eδ−1δ\\displaystyle\>\\tfrac\{2\}\{3\}\(C\+x\)\+z\\,\\frac\{e^\{\\delta\}\-1\}\{\\delta\}≥23​\(C\+x\)\+z\\displaystyle\\geq\\tfrac\{2\}\{3\}\(C\+x\)\+z≥23​\(C\+x\+z\)=23​H\>α​H\.\\displaystyle\\geq\\tfrac\{2\}\{3\}\(C\+x\+z\)=\\tfrac\{2\}\{3\}H\\;\>\\;\\alpha H\.Line 2 only splitsC\+x=23​\(C\+x\)\+13​\(C\+x\)C\+x=\\tfrac\{2\}\{3\}\(C\+x\)\+\\tfrac\{1\}\{3\}\(C\+x\)and regroups\. Line 3 uses \([36](https://arxiv.org/html/2608.19993#A1.E36)\):C≥2​xC\\geq 2ximplies13​\(C\+x\)≥x\\tfrac\{1\}\{3\}\(C\+x\)\\geq x, so the bracket is at leastx−x​e−δx\-xe^\{\-\\delta\}\. Line 4 uses \([45](https://arxiv.org/html/2608.19993#A1.E45)\) together with1−e−δ=e−δ​\(eδ−1\)\>01\-e^\{\-\\delta\}=e^\{\-\\delta\}\(e^\{\\delta\}\-1\)\>0:

x⁡\(1−e−δ\)\>z​eδδ​e−δ​\(eδ−1\)=z​eδ−1δ\.x\\bigl\(1\-e^\{\-\\delta\}\\bigr\)\\;\>\\;z\\,\\frac\{e^\{\\delta\}\}\{\\delta\}\\,e^\{\-\\delta\}\\bigl\(e^\{\\delta\}\-1\\bigr\)\\;=\\;z\\,\\frac\{e^\{\\delta\}\-1\}\{\\delta\}\.Line 5 uses the elementary inequalityeδ≥1\+δe^\{\\delta\}\\geq 1\+\\delta, which gives\(eδ−1\)/δ≥1\(e^\{\\delta\}\-1\)/\\delta\\geq 1, andz\>0z\>0\. Line 6 usesz≥23​zz\\geq\\tfrac\{2\}\{3\}z, and the final equality is \([35](https://arxiv.org/html/2608.19993#A1.E35)\)\. The last strict comparison usese<3e<3:α=1−1/e<1−1/3=2/3\\alpha=1\-1/e<1\-1/3=2/3\.

If insteadz=0z=0, no logarithm involvingzzis ever formed: lines 1–3 of \([46](https://arxiv.org/html/2608.19993#A1.E46)\) are unchanged and give

C\+φ⁡\(r\)≥23​\(C\+x\)\+x⁡\(1−e−δ\)≥23​\(C\+x\)=23​H\>α​H,C\+\\varphi\(r\)\\;\\geq\\;\\tfrac\{2\}\{3\}\(C\+x\)\+x\\bigl\(1\-e^\{\-\\delta\}\\bigr\)\\;\\geq\\;\\tfrac\{2\}\{3\}\(C\+x\)\\;=\\;\\tfrac\{2\}\{3\}H\\;\>\\;\\alpha H,usingx⁡\(1−e−δ\)≥0x\(1\-e^\{\-\\delta\}\)\\geq 0andH=C\+x\+0H=C\+x\+0from \([35](https://arxiv.org/html/2608.19993#A1.E35)\)\.

*Step 3 \(Case 3:r<D1r<D\_\{1\}andX1=RX\_\{1\}=R\)\.*Herez=f⁡\(R\)z=f\(R\),x=f⁡\(v⋆∣R\)x=f\(v^\{\\star\}\\mid R\), andd1=ℓ⁡\(R\)=rd\_\{1\}=\\ell\(R\)=r\. Sincer<D1r<D\_\{1\}, the first branch of \([22](https://arxiv.org/html/2608.19993#S4.E22)\) evaluatesφ⁡\(r\)\\varphi\(r\), and because the branch rate constant isd1=rd\_\{1\}=r,

φ\(r\)=f\(X1\)\(1−e−r/d1\)=z\(1−e−1\)=αz\.\\varphi\(r\)=f\(X\_\{1\}\)\\bigl\(1\-e^\{\-r/d\_\{1\}\}\\bigr\)=z\\bigl\(1\-e^\{\-1\}\\bigr\)=\\alpha z\.\(47\)From \([36](https://arxiv.org/html/2608.19993#A1.E36)\),C≥2​xC\\geq 2x, hence3​C≥2​C\+2​x3C\\geq 2C\+2x, i\.e\.,

C≥23​\(C\+x\)≥α⁡\(C\+x\),C\\;\\geq\\;\\tfrac\{2\}\{3\}\(C\+x\)\\;\\geq\\;\\alpha\(C\+x\),\(48\)where the second inequality again uses23\>α\\tfrac\{2\}\{3\}\>\\alpha\(frome<3e<3\) andC\+x≥0C\+x\\geq 0\. Adding \([47](https://arxiv.org/html/2608.19993#A1.E47)\) and \([48](https://arxiv.org/html/2608.19993#A1.E48)\) and using \([35](https://arxiv.org/html/2608.19993#A1.E35)\),

C\+φ⁡\(r\)≥α⁡\(C\+x\)\+α​z=α⁡\(C\+x\+z\)=α​H\.C\+\\varphi\(r\)\\;\\geq\\;\\alpha\(C\+x\)\+\\alpha z\\;=\\;\\alpha\(C\+x\+z\)\\;=\\;\\alpha H\.
*Step 4\.*The reductionf⁡\(P\)=0f\(P\)=0was handled in Step 0, so assumef⁡\(P\)\>0f\(P\)\>0\. IfD1≤rD\_\{1\}\\leq r— which includesD1=0D\_\{1\}=0, sincer\>0r\>0by \([25](https://arxiv.org/html/2608.19993#A1.E25)\) — we are in Case 1\. Ifr<D1r<D\_\{1\}— which includesD1=\+∞D\_\{1\}=\+\\infty, i\.e\.,ρ2=0\\rho\_\{2\}=0— we are in Case 2 or Case 3 according to whether the block order puts\{v⋆\}\\\{v^\{\\star\}\\\}orRRfirst; these two options are exhaustive because\(X1,X2\)\(X\_\{1\},X\_\{2\}\)is a permutation of\(\{v⋆\},R\)\\bigl\(\\\{v^\{\\star\}\\\},R\\bigr\)\. In every caseG^​\(J\)\+φ⁡\(r\)≥α​G^​\(T\)\\widehat\{G\}\(J\)\+\\varphi\(r\)\\geq\\alpha\\widehat\{G\}\(T\), which is the claim of[Lemma4](https://arxiv.org/html/2608.19993#Thmlemma4)\. ∎