Paper deep dive

Curating Always-Loaded Context for LLM Agents: A Capacitated Assortment Model with Censored Feedback

Zexuan Liu, Yuning Yang, Tiancheng Zhao

Year: 2026Venue: arXiv preprintArea: cs.AIType: PreprintEmbeddings: 138

Intelligence

Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 89%

Last extracted: 10/9/2026, 8:10:57 AM

Summary

This paper formulates the curation of always-loaded context files for LLM agents as a capacitated assortment problem with censored feedback. It demonstrates that appending instructions (accretion) is suboptimal due to attention dilution and setup costs, proving an upper bound on optimal file size. The study analyzes learning from censored session transcripts, showing that deleting ignored instructions is value-blind and establishing evidence thresholds for adding new instructions to minimize regret under limited human review capacity.

Entities (7)

Attention Dilution · concept · 95%LLM Agents · system · 95%Capacitated Assortment Model · methodology · 90%Censored Feedback · concept · 90%Context File · artifact · 90%Accretion Policy · policy · 85%Edit Cap · constraint · 85%

Relation Signals (6)

Context File → isloadedby → LLM Agents

confidence 95% · At the start of every session, LLM agents load a fixed context file

Capacitated Assortment Model → models → Context Curation

confidence 95% · We formulate context curation as a capacitated assortment problem.

Attention Dilution → causes → Reduced Compliance

confidence 90% · Adding an instruction may lower the compliance of every instruction already in the file

Accretion Policy → issuboptimalto → Optimal Subset Selection

confidence 90% · appending every instruction with positive standalone value can be arbitrarily worse in net value than selecting an optimal subset.

Edit Cap → bounds → Regret

confidence 85% · we bound regret when human reviewers can inspect only a limited number of edits per period.

Censored Feedback → complicates → Learning from Transcripts

confidence 85% · Feedback is inherently censored... missing instructions generate feedback only when their absence causes harm.

Cypher Suggestions (0)

No Cypher suggestions yet.

Abstract

Abstract:At the start of every session, LLM agents load a fixed context file, such as $\texttt{this http URL}$. Each loaded token in the file is charged again in every later round of the session, and these files can degrade performance as they grow in size. However, in practice, human or automated curators usually grow these files by appending. We formulate context curation as a capacitated assortment problem. Instructions consume tokens under a finite attention capacity; adding an instruction never raises the compliance of the others, while retained instructions incur a per-session setup cost. We prove an upper bound on the optimal file size, regardless of the number of available candidate instructions, and that appending every instruction with positive standalone value can be arbitrarily worse in net value than selecting an optimal subset. A token budget also limits the loss when the token price is underestimated. We then examine what can be learned from past sessions and how this information can guide decisions to add or remove instructions. Feedback is inherently censored: the benefits and harms of loaded instructions are observable, whereas missing instructions generate feedback only when their absence causes harm. In this setting, we show that deleting instructions ignored by agents can inevitably remove helpful ones. We characterize how much evidence should be collected before adding an instruction. Besides, we bound regret when human reviewers can inspect only a limited number of edits per period. Empirical experiments further show that irrelevant rules drawn from real context files reduce language-model compliance.

PDF

Open source PDF →Open local PDF →

Trouble viewing inline? Open PDF directly →

Full Text

134,303 characters extracted from source content.

Expand or collapse full text

Curating Always-Loaded Context for LLM Agents: A Capacitated Assortment Model with Censored Feedback Zexuan Liu Affiliation: University of Illinois at Urbana-Champaign Yuning Yang Affiliation: Georgia Institute of Technology Tiancheng Zhao Affiliation: Saint Louis University Abstract At the start of every session, LLM agents load a fixed context file, such as AGENTS.md. Each loaded token in the file is charged again in every later round of the session, and these files can degrade performance as they grow in size. However, in practice, human or automated curators usually grow these files by appending. We formulate context curation as a capacitated assortment problem. Instructions consume tokens under a finite attention capacity; adding an instruction never raises the compliance of the others, while retained instructions incur a per-session setup cost. We prove an upper bound on the optimal file size, regardless of the number of available candidate instructions, and that appending every instruction with positive standalone value can be arbitrarily worse in net value than selecting an optimal subset. A token budget also limits the loss when the token price is underestimated. We then examine what can be learned from past sessions and how this information can guide decisions to add or remove instructions. Feedback is inherently censored: the benefits and harms of loaded instructions are observable, whereas missing instructions generate feedback only when their absence causes harm. In this setting, we show that deleting instructions ignored by agents can inevitably remove helpful ones. We characterize how much evidence should be collected before adding an instruction. Besides, we bound regret when human reviewers can inspect only a limited number of edits per period. Empirical experiments further show that irrelevant rules drawn from real context files reduce language-model compliance. 1 INTRODUCTION A coding agent that works on a Python package reads the package’s AGENTS.md at the start of every session. The file holds instructions such as “run pytest after every edit”, “add a CHANGELOG.md line”, “use NumPy docstrings”, “never commit to main”, and “always use conda”. The last one breaks the environment in a repository that uses uv. This example illustrates why instructions must be selected carefully: an unsuitable rule can lead the agent to make mistakes. Even instructions that cause no harm incur a setup cost in each session, regardless of their relevance to the current task. Context files can raise inference cost by a fifth or more without a matching gain in task success (Gloaguen et al.,, 2026), since the file remains part of the prompt throughout the session, occupying context space in every model call. As the file grows, the agent may follow its instructions less reliably. At high instruction density the more instructions the file holds, the less reliably the agent follows any one of them (Jaroslawicz et al.,, 2025; Harada et al.,, 2025). However, McMillan, (2026) and Zhang et al., 2026a (), studying real configuration files, observe no drop in adherence as file size grows within the small ranges they test. In practice the file grows by appending. Across 1,867 repositories such files more than double over their life, and deletions become rarer as the file ages (Chakrabarti,, 2026). Tools that write the file from past sessions add to the pressure. Every session is summarized into new candidate instructions, so the pool of candidates grows without bound while the agent’s attention does not. These lead to two questions. What should the file contain? And how can a human or automated curator learn that from the transcripts of past sessions? The second is harder than it looks, because transcripts are censored. For instructions already in the file, transcripts reveal whether the agent complied with them and whether compliance helped or hurt. For instructions not in the file, their value is usually invisible; it becomes observable only when a failure reveals the missing instruction. We answer the first question with an assortment model. Each candidate instruction is an item with a setup cost, a probability of being relevant, and a gain when followed. The gain can be negative as a followed instruction can harm. The agent’s limited attention is shared among all instructions. Adding an instruction may lower the compliance of every instruction already in the file, so the file is an assortment whose items compete for one resource. Every loaded instruction carries a per-session setup cost. This is the fixed-cost assortment problem of operations management (Kunnumkal and Martínez-de Albéniz,, 2019; Feldman and Paul,, 2019) with a capacity constraint (Rusmevichientong et al.,, 2010; Désir et al.,, 2022). Two things are new: the items compete for a shared attention that dilutes as the file grows, and the pool of items grows with time. We answer the second question with an observation model that models the censored feedback. We ask four questions: what censored transcripts identify, when a deletion policy is safe, how much corroboration to require before adding an instruction, and what a cap on human review costs. To our knowledge, no prior work models instruction compliance as choice under a finite attention capacity, and no existing learning result handles censored feedback under an edit cap. Classical assortment models optimize revenue under a fixed choice model (Talluri and van Ryzin,, 2004; Berbeglia and Joret,, 2020); we instead bound the size of the optimal file under a attention-capacity bound. Learning with one-sided feedback (Helmbold et al.,, 2000) and learning under a bounded number of switches (Altschuler and Talwar,, 2021) have each been studied separately. The unique combination with a growing candidate pool and a curator who can review only a limited number of edits has not been studied. Contributions. (i) A model of context curation as capacitated assortment problem with a per-session setup cost, in which compliance is diluted by a shared attention load (Section 2). (i) A structural characterization under finite attention capacity, including a file-size bound independent of the number of candidate instructions and an unbounded accretion loss, which would be optimal without attention dilution (Section 3). (i) What censored feedback identifies: compliance and harm identify different parameters, so deleting on non-compliance is value-blind and can remove the better instruction (Section 4). (iv) An evidence threshold for adding an instruction, and regret when a reviewer accepts at most m edits per period, with the edit-cap term matched above and below (Section 4). (v) Experiments in which the optimal file size stays flat as the candidate pool grows from 200 to 3,200 items for two models, and a simulation matching the edit-cap regret bounds (Section 5). Section 2 defines the model, Section 3 gives the structural results, Section 4 develops the learning results, and Section 5 reports the experiments. Proofs are in the appendix; Appendix A also gives the results on token budgets. The numbered results, except those relying on the smoothness-to-bound step in Assumption C.4, have complete formal proofs in Lean 4 (supplementary material). 2 MODEL The curation workflow. An agent runs sessions. After each session a summarizer, itself a language model, reads the transcript and extracts candidate instructions: things the agent should have known, or mistakes it should not repeat. The candidates join a pool. A curator selects a subset of the pool as the file that the agent loads at the start of every later session. The pool grows with every session; the file should not. Primitives. The pool is [N]=1,…,N[N]=\1,…,N\. We view it as the first N items of an endless list of candidates, so that we can ask what happens as N grows. Every bound below holds for all N. The file is a subset S⊆[N]S [N]. Instruction i has a token cost ci≥cmin>0c_i≥ c_ >0, and C⁡(S)=∑i∈SciC(S)= _i∈ Sc_i is the cost of the file. Instruction i is relevant in a session with probability pip_i. When it is relevant and the agent follows it, the session gains rir_i in expectation. The gain is negative for a harmful instruction. Write wi=piriw_i=p_ir_i for the per-session value of always following i, and w¯=max⁡(0,supiwi)<∞ w= (0, _iw_i)<∞, the supremum over all candidates. Given the file S, the agent follows a relevant instruction i∈Si∈ S with probability qi(S)∈[0,1)q_i(S)∈[0,1), its compliance. Compliance depends on the whole file, not on N. Every loaded instruction is charged once per session, when the session starts and the file enters the prompt. Later turns of the session hit the prompt cache. We call κ>0κ>0 the token price, so the setup cost of instruction i is κciκ c_i per session and the file’s setup cost is κC(S)κ C(S). The per-session value of S is its gross value minus its setup cost, R⁡(S)=R0(S)−κC(S),R0(S)=∑i∈Swiqi(S).R(S)=R_0(S)-κ\,C(S), R_0(S)= _i∈ Sw_i\,q_i(S). (1) The curator solves maxR(S):S⊆[N],C(S)≤B \R(S):S [N],\ C(S)≤ B\ for a budget B≥0B≥ 0. The empty file is feasible and R⁡(∅)=0R( )=0, so an optimum S⋆S exists and R⁡(S⋆)≥0R(S )≥ 0. An instruction with positive standalone value must be followed often enough to pay its tokens. Call ρ=κcmin/w¯ρ=κ c_ / w the break-even compliance (ρ=∞ρ=∞ if w¯=0 w=0). If R⁡(i)>0R(\i\)>0, then qi(i)>ρq_i(\i\)>ρ. General compliance model. The compliance functions qi(S)q_i(S) are otherwise arbitrary, subject to the following structural condition: adding instructions cannot increase the compliance of an instruction already in the file. Assumption 1 (Monotone dilution). qi(S∪T)≤qi(S)q_i(S∪ T)≤ q_i(S) for every finite S, T and every i∈Si∈ S. Shared-dilution subclass. The shared-dilution form is a parametric subclass of the general compliance model. Each instruction has an intrinsic compliance θi>0 _i>0 and an attention load ai>0a_i>0; the file load is A⁡(S)=∑j∈SajA(S)= _j∈ Sa_j. A known dilution curve g:[0,∞)→(0,1]g:[0,∞)→(0,1], nonincreasing with g⁡(0)=1g(0)=1, gives the common discount qi(S)=θig(A⁡(S)),i∈S.q_i(S)= _i\,g (A(S) ), i∈ S. (2) Here θi _i measures how readily the agent follows an instruction, aia_i measures its attention load, and g describes how attention is diluted. We require θig(ai)<1 _ig(a_i)<1 for every i. Since g is nonincreasing, (2) satisfies monotone dilution. It also gives the ratio qi(S)/qj(S)=θi/θjq_i(S)/q_j(S)= _i/ _j, which does not depend on S, and a single-item file has qi(i)=θig(ai)q_i(\i\)= _ig(a_i), which is the compliance a curator observes when testing an instruction on its own. Taking S=iS=\i\, qi(S)≤qi(i)q_i(S)≤ q_i(\i\) for every file that contains i: no instruction is followed more often in company than alone. Under (2), equality is allowed when g is flat on the added-load interval; a strict drop occurs only when g takes a smaller value. Compliance mass and capacity. The total compliance of a file is Q⁡(S)=∑i∈Sqi(S)Q(S)= _i∈ Sq_i(S): the expected number of followed instructions when all are relevant. Its maximum over files of n items is the compliance mass M⁡(n)=supQ⁡(S):|S|=nM(n)= \Q(S):|S|=n\. We use two nested mass conditions. The weaker one controls average compliance: Assumption 2 (Bounded average compliance). lim supn→∞M⁡(n)/n<ρ _n→∞M(n)/n<ρ. The stronger condition is a uniform capacity bound: Assumption 3 (Attention capacity). Q⁡(S)≤Q¯Q(S)≤ Q for every finite S, for a constant Q¯<∞ Q<∞. The agent follows at most Q¯ Q instructions per session on average, however many it is given. Under (2) the capacity is Q¯=χG¯ Q=χ G with χ=supiθi/aiχ= _i _i/a_i and G¯=supx≥0xg(x) G= _x≥ 0x\,g(x), which is finite exactly when g⁡(x)=O⁡(1/x)g(x)=O(1/x). Since M⁡(n)≤Q¯M(n)≤ Q, Assumption 3 implies Assumption 2. The main size bound uses capacity; the appendix also gives the weaker result when capacity fails. Under the shared-dilution form, Assumption 2 holds whenever the loads have a floor ai≥amin>0a_i≥ a_ >0 and supiθi⋅limx→∞g⁡(x)<ρ _i _i· _x→∞g(x)<ρ, in particular whenever g vanishes at infinity. The case Q¯=1 Q=1 is the single-choice case of classical assortment models: the agent follows at most one instruction on average. Appendix B records which classical choice models are instances of (2), and the sharper constants they give. Assumption 3 can fail under (2) while Assumption 2 holds, for example when g decays like a power below one. 3 STRUCTURAL PROPERTIES Each instruction incurs a setup cost, while the agent has a bounded total compliance, so the value of a file cannot keep growing with its size. This section shows that the optimal file size is bounded independently of the candidate pool size. Adding every instruction that has positive standalone value can produce an arbitrarily large accretion loss. Without dilution, however, this policy is optimal whenever the token budget accommodates all such instructions. Proofs are in Appendix A. The size bound. The bound is based on two observations. A file with nonnegative value earns at least its setup cost: R⁡(S)≥0R(S)≥ 0 means κC(S)≤∑i∈Swiqi(S)κ C(S)≤ _i∈ Sw_iq_i(S). And each followed instruction is worth at most w¯ w, while the agent follows at most Q¯ Q instructions per session (Assumption 3). So the setup cost of a file worth keeping is at most w¯Q¯ w Q, whatever the pool holds. Proposition 1 (File size bound). Under Assumption 3, every file with R⁡(S)≥0R(S)≥ 0, and in particular every optimal file S⋆S , satisfies κC(S)≤w¯Q¯and|S|≤w¯Q¯κcmin=Q¯ρ.κ\,C(S)≤ w\, Q |S|≤ w\, Qκ\,c_ = Qρ. Neither bound depends on the pool size N or the budget B. If B≥w¯Q¯/κB≥ w Q/κ, the budget never binds. Under (2) the capacity is Q¯=χG¯ Q=χ G. Appendix A states the full version (Proposition A.1), a bound under Assumption 2 when capacity fails, and a load bound on optima that needs neither condition (Proposition A.5). The bound gives the curator a token budget that does not exclude any optimal file. Suppose the best instruction in the pool is worth w¯/κ=10,000 w/κ=10,000 always-loaded tokens per session, and the agent follows at most χG¯=3χ G=3 instructions per session on average. Then no file worth keeping costs more than 30,00030,000 tokens, and no optimal file has more than 3/ρ3/ρ instructions, however many sessions have been summarized. Accretion. A curator who tests each instruction alone and appends the ones with positive standalone value is running accretion. Write visolo=R⁡(i)=wiqi(i)−κciv_i^solo=R(\i\)=w_iq_i(\i\)-κ c_i for the standalone value of instruction i, which is wiθig(ai)−κciw_i _ig(a_i)-κ c_i under (2). The accretion file is SNacc=i∈[N]:visolo>0S_N^acc=\i∈[N]:v_i^solo>0\ and its closure is S¯Nacc=i∈[N]:visolo≥0 S_N^acc=\i∈[N]:v_i^solo≥ 0\. Every session adds candidates, and every candidate with positive standalone value joins the file. But the file’s gross value is capped at w¯χG¯ wχ G while its setup cost grows with every instruction. Past χG¯/ρχ G/ρ instructions, each addition increase the setup cost by at least κcminκ c_ per session. Corollary 1 (Accretion is unboundedly suboptimal). Assume (2) with χG¯<∞χ G<∞, and let SN⋆S _N be optimal for the pool [N][N]. Every S⊆[N]S [N] satisfies R⁡(S)≤w¯χG¯−κcmin|S|R(S)≤ w\,χ G-κ c_ |S|, hence R⁡(SN⋆)−R⁡(SNacc)≥κcmin|SNacc|−w¯χG¯,R(S _N)-R(S_N^acc)\ ≥\ κ c_ \,|S_N^acc|- w\,χ G, which tends to infinity whenever |SNacc|→∞|S_N^acc|→∞. The loss grows linearly in the size of the accretion file, at rate κcminκ c_ per instruction beyond χG¯/ρχ G/ρ. The hypothesis |SNacc|→∞|S_N^acc|→∞ is met as soon as infinitely many candidates with positive standalone value, which the summarizer of Section 2 supplies. As the pool grows, so does the number of instructions with positive standalone value. Appending all of them leaves an agent that follows about χG¯χ G of them per session while paying for every one. Without dilution. In this case, the token price alone does not make accretion suboptimal. If compliance did not depend on the file, value would be additive and accretion would be optimal whenever the file fits within the token budget. This is the limit aj→0a_j→ 0 of (2), which lies outside the model, and it isolates dilution as the cause of the loss above. Proposition 2 (Without dilution, accretion is optimal). Suppose qi(S)=qiq_i(S)=q_i for every S∋iS i, so that visolo=wiqi−κciv_i^solo=w_iq_i-κ c_i. Then R⁡(S)=∑i∈SvisoloR(S)= _i∈ Sv_i^solo. If B≥C⁡(SNacc)B≥ C(S_N^acc), then SNaccS_N^acc is optimal, and the optimal files are exactly the S with SNacc⊆S⊆S¯NaccS_N^acc S S_N^acc and C⁡(S)≤BC(S)≤ B. Without dilution, accretion is optimal whenever the token budget allows it. Under monotone dilution, every optimal file contains only instructions with nonnegative standalone value. At least one optimal file can be obtained by deleting instructions from the accretion file (Proposition A.2 in the appendix). The next section studies how a curator can use session feedback to identify which instructions to delete. The appendix also gives a tighter size bound for files whose value cannot be increased by deleting one instruction. A token budget set at this bound limits the loss when the curator underestimates the token price (Corollary A.9). 4 LEARNING WITH CENSORED FEEDBACK Section 3 takes the values wiw_i and the compliances qi(S)q_i(S) as known. In this section, we investigate how curators can learn from session transcripts. Transcripts are censored: they show what the loaded file did, not what an absent instruction would have done. Formal assumptions and proofs are in Appendix C. 4.1 Setup Each session t runs with the file StS_t loaded. A reviewer reads the transcript. A curator edits the file. The reviewer approves at most m edits per epoch of L sessions. A transcript carries three kinds of signal. • Loaded i∈Sti∈ S_t: relevant? followed? a harm flag, raised with probability η>0η>0 when following i did harm. • Absent i∉Sti∉ S_t: a gap sighting with probability δipi _ip_i, where δi _i is the reviewer’s detection rate. • Observed gains: the gain Xi,t∈[−1,1]X_i,t∈[-1,1] of a followed instruction, shown only under magnitude feedback. Assumption 4 (Censored feedback). In session t the curator observes the first two signals above. All draws are independent across instructions and sessions, and their law depends on the file only through qi(St)q_i(S_t). The gains rir_i enter no observation. Under magnitude feedback the curator also observes Xi,tX_i,t for each followed i∈Sti∈ S_t. What transcripts identify. Let hih_i be the probability that following i does harm. The typed case is hi∈0,1h_i∈\0,1\: an instruction is always helpful or always harmful. We prove what a fixed sequence of files identifies (Theorem C.5 in Appendix C.2). The compliance qi(S)q_i(S) of a loaded instruction is identified. The harm rate ηhiη h_i is identified, hence whether i ever harms. The sign of the gain rir_i is identified only in the typed case. The size of a gain is never identified without magnitude feedback. An absent instruction is seen only through its gap sightings, which measure a rate, not a value. 4.2 Deletion A natural policy deletes what the agent ignores. We prove that it is blind to value. Proposition 3 (Deleting on non-compliance is value-blind). Suppose Assumption 4 holds, with a fixed file S played in every session. A deletion policy that uses only compliance data has the same law of decisions under every parameter vector with the same (p,q)(p,q). Take an instance of (2) with S=1,2S=\1,2\. Instruction 1 is helpful but often ignored; instruction 2 is mostly followed but worth little or harmful. Deleting the most-ignored instruction removes instruction 1 with probability tending to one as sessions accumulate. In the language of partial monitoring (Bartók et al.,, 2014), the compliance channel is feedback whose law does not separate the hypotheses the curator must tell apart. Here, the compliance observed for an instruction also depends on the other instructions in the file through dilution. The feedback on i is qi(S)q_i(S), which the file S sets through dilution. 4.3 Admission An absent instruction becomes a candidate when reviewers keep sighting its gap. A spurious candidate, one that names no real gap, is also sighted now and then. Sightings are independent across sessions at a fixed sighting rate: ε for a spurious candidate and π=δjpjπ= _jp_j for a real one (Assumption C.2). The curator admits at the first session τk _k by which k sightings fall within a window of W sessions. Over T sessions, a spurious candidate is falsely included with probability PFI(k)=Prε⁡(τk≤T)P_FI(k)= _ ( _k≤ T); a real one waits πτkE_π _k sessions. With NsN_s spurious candidates, a cost cFc_F per false inclusion and cD>0c_D>0 per session of delay, the loss of k is ℒ⁡(k)=ΛFPFI(k)+cDπτkL(k)= _F\,P_FI(k)+c_D\,E_π _k with ΛF=cFNs _F=c_FN_s. Write ΛD=cD/π _D=c_D/π for the the expected delay cost until the first sighting of a real candidate. Let ψW=1−(1−π)W−1 _W=1-(1-π)^W-1 be the chance that two real sightings share a window. Let x=εWx= W and xT=εTx_T= T count the spurious sightings expected per window and per horizon, and let ω=ΛD/(ΛFεT)ω= _D/( _F T). Theorem 1 (How many sightings before adding an instruction). Assumption C.2 with π,ε∈(0,1]π, ∈(0,1], W≥2W≥ 2, ΛF>0 _F>0 and T≥1T≥ 1. If x<ω⁡(2−1/ψW)andω/ψW<1−xT/2−x,x<ω\,(2-1/ _W) ω/ _W<1-x_T/2-x, then k=2k=2 is the unique minimizer of ℒL over k≥1k≥ 1. As ψW→1 _W→ 1 the condition reads x<ω<1−xT/2−x<ω<1-x_T/2-x. Two sightings give the lowest expected loss whenever the price of one wait lies between the false-inclusion costs that a third and a second sighting would prevent. 4.4 Regret under an edit cap Sessions run t=1,…,Tt=1,…,T, with epoch e⁡(t)=⌈t/L⌉e(t)= t/L . The file starts empty, an edit is one addition or one removal, and each epoch has at most m edits. Every played file satisfies C⁡(St)≤BC(S_t)≤ B. A policy maps the history of files and observations to the next file. Its regret against the best fixed feasible file S⋆S is RegT=∑t≤T(R⁡(S⋆)−R(St))Reg_T= _t≤ T(R(S )-E\,R(S_t)), and Δmax=maxC⁡(S)≤B⁡[R⁡(S⋆)−R⁡(S)] _ = _C(S)≤ B[R(S )-R(S)] is the largest per-session loss. Without magnitude feedback every policy has linear regret on some instance (Proposition C.6), so we assume it from here on. We analyze ETC-m (Algorithm 1), an explore-then-commit policy satisfying the edit cap. It tries the candidates in J=⌈N/s⌉J= N/s batches of s=min⁡(⌊m/2⌋,⌊B/cmax⌋)s= ( m/2 , B/c_ ) instructions, where cmax=maxi⁡cic_ = _ic_i, so that one batch can be swapped for the next within one epoch’s cap. Each batch is played for n0n_0 sessions; then it commits to the file with the largest estimated value. The estimator is in Appendix C.5. Algorithm 1 ETC-m: explore-then-commit under an edit cap 1: pool [N][N], cap m, epoch length L, budget B, exploration length n0n_0 2: s←min⁡(⌊m/2⌋,⌊B/cmax⌋)s← ( m/2 , B/c_ ); partition [N][N] into batches 1,…,JJ_1,…,J_J of at most s instructions 3: for j=1,…,Jj=1,…,J do ⊳ explore 4: at the first session of an epoch, replace the loaded batch by jJ_j (at most 2s≤m2s≤ m edits) 5: play jJ_j for ⌈n0/L⌉ n_0/L epochs; record compliance and realized gains 6: end for 7: from the records, estimate the load a^i a_i and the value β^i β_i of every instruction (Appendix C.5) 8: S^←arg⁡max⁡R^(S):C⁡(S)≤B S← \ R(S):C(S)≤ B\ with R^(S)=g⁡(A^(S))∑i∈Sβ^i−κC(S) R(S)=g( A(S)) _i∈ S β_i-κ C(S) ⊳ commit 9: move from JJ_J to S S, removals first, m edits per epoch; then play S S until T Predicting the value of unplayed files needs tied loads (Assumption C.4): θi=λai _i=λ a_i with λ known, and loads bounded by a known amaxa_ . Let nBn_B be the largest number of instructions a feasible file can hold, and pi≥pmin>0p_i≥ p_ >0. Theorem 2 (ETC-m under an edit cap). Assumption 4 with magnitude feedback and compliance (2) under tied loads; m≥2m≥ 2, B≥cmaxB≥ c_ . For every n0≥8ln⁡(6NT)/pminn_0≥ 8 (6NT)/p_ , RegT≤ΔmaxL(J+⌈s+nBm⌉)+ΛT(n0),Reg_T\ ≤\ _ \,L (J+ s+n_Bm )\ +\ _T(n_0), where the learning term ΛT(n0) _T(n_0) is given in Theorem C.12. Theorem 3 (The edit-cap term is unavoidable). Let nm=⌊N/m⌋n_m= N/m , T≥LnmT≥ Ln_m, N,m≥1N,m≥ 1, B>0B>0. There is a family of N instances of Assumption 4 with magnitude feedback and compliance (2). They share c≤Bc≤ B, p, θ and a, with noiseless gains and no harm. Under instance j the optimal file is j\j\, missing j costs at least Δ=pθg(a)−κc>0 =p\,θ\,g(a)-κ c>0 per session, and Δmax≤Δ+κB _ ≤ +κ B. Every policy that adds at most m instructions per epoch from the empty file satisfies maxj⁡RegT(j)≥ΔL2(nm−1)≥ΔLN4m(N≥4m). _jReg_T(j)\ ≥\ L2(n_m-1)\ ≥\ LN4m (N≥ 4m). For N≥4mN≥ 4m, κB≤Δκ B≤ and m≤2B/cmaxm≤ 2B/c_ , the edit-cap terms of the two theorems match up to a constant factor. Both are of order (N/m)LΔ(N/m)L . The learning term ΛT _T is of order T2/3(ln⁡NT)1/3T^2/3( NT)^1/3, the rate of explore-then-commit, and is not claimed tight (Appendix C.5). This is not the switch-budget bound of Simchi-Levi and Xu, (2023), where a global budget leaves regret linear in T. Here the cap renews each epoch, so every candidate is eventually tried. 5 EXPERIMENTS We use three experiments to study instruction files. The first measures how file size affects compliance and value. The second measures compliance in responses from a published benchmark. The third uses simulations to measure the effect of limits on file edits. Appendix D gives the detailed designs, results, and analysis plans. Size sweep. The first experiment tests whether a larger candidate pool requires a larger file. The pool holds 3,200 items from real repository context files. Claude Sonnet 5.5 rewrites 2,560 of them as instructions about the words in a response, so that an automatic checker can score each instruction. Most of these instructions apply only to one response format, such as an email. The other 640 items stay unchanged and have zero value in our score. The tasks are 60 ManyIFEval writing tasks (Harada et al.,, 2025), ten in each of six response formats. The file is the system prompt, and the task is the user prompt. We vary the pool size N∈200,800,3200N∈\200,800,3200\ and the file size b∈5,10,20,40,80,200,400,800,1600,N,b≤N.b∈\5,10,20,40,80,200,400,800,1600,N\, b≤ N. The file SbS_b holds the b instructions that the model receives. Pools and files are nested: each larger pool contains the smaller pools, and each larger file contains the smaller files. Claude Haiku 4.5 and Claude Sonnet 5.5 receive the same files and tasks, for 2,880 runs each. We report three quantities. The gross value R0(Sb)R_0(S_b) is the mean number of relevant instructions that the model follows, minus the number of keyword matches expected by chance. The relevant load ℓ⁡(Sb) (S_b) adds, over the relevant instructions in the file, the compliance of each instruction when it is loaded alone (Appendix D.1). The value subtracts a token penalty from the gross value, Rρexp(Sb)=R0(Sb)−ρexpcmedC(Sb),R_ _exp(S_b)=R_0(S_b)- _expc_med\,C(S_b), where C⁡(Sb)C(S_b) is the token count of the file and cmed≈39c_med≈ 39 tokens is the median instruction length. Here ρexp _exp is a normalized cost per median-length item, distinct from the theoretical break-even compliance ρ. At ρexp=0.1 _exp=0.1, one median-length instruction costs 0.10.1 units of gross value. The measured optimum n⋆(N)n (N) is the size of the highest-value file among the files we test. Figure 1: Gross value against file size for Claude Haiku 4.5 and Claude Sonnet 5.5. Gross value counts relevant instructions that the model follows, after adjustment for chance keyword matches. Each panel uses a different candidate pool. Points show means across 60 tasks. Bars show 95% confidence intervals from a bootstrap that resamples tasks and keeps each task’s runs together. The last point in each panel loads the entire pool. Size sweep: results. Large files reduce gross value in the largest pool (Figure 1). At N=3200N=3200, both models reach their highest gross value at b=200b=200, where Haiku follows 5.05.0 relevant instructions and Sonnet follows 23.823.8. With the entire pool loaded, these values decrease to 0.60.6 and 4.04.0. The marginal relevant compliance, the change in gross value per unit of additional relevant load, is negative at the last step. From b=1600b=1600 to b=3200b=3200, it is −0.007-0.007 [−0.013,−0.002][-0.013,-0.002] for Haiku and −0.037-0.037 [−0.052,−0.023][-0.052,-0.023] for Sonnet (95% intervals). The best tested file stays small as the pool grows. At ρexp=0.1 _exp=0.1 and N=200N=200, 800800, and 32003200, the measured optimum is 1010, 55, and 1010 for Haiku and 4040, 2020, and 4040 for Sonnet. This result is consistent with the size bound of Proposition 1, although it covers only the tested files. The accretion loss, Rρexp(Sn⋆)−Rρexp(SN)R_ _exp(S_n )-R_ _exp(S_N), compares the best tested file with the file that loads the entire pool. From N=200N=200 to N=3200N=3200, it increases from 15.815.8 to 316.7316.7 for Haiku and from 6.06.0 to 320.4320.4 for Sonnet. The loss includes both the compliance effect and the token penalty, as in Corollary 1. Dilution also appears instruction by instruction. At N=3200N=3200, the relevant instructions of the b=40b=40 file have a mean compliance of 0.270.27 for Haiku and 0.910.91 for Sonnet in that file. With the entire pool loaded, both rates decrease to 0.050.05, as Assumption 1 predicts at high load. The score measures instruction compliance and not the overall quality of the response. Dilution on a published benchmark. We re-score 5,993 existing IFScale responses (Jaroslawicz et al.,, 2025) from 24 model configurations. Compliance is 0.920.92–1.001.00 at ten keyword requirements and 0.0670.067–0.6890.689 at 500 requirements. Appendix D.2 gives the fitted curves and the results for each configuration. Regret under an edit cap. The third experiment runs ETC-m (Algorithm 1) on the instances of Theorem 3, where the optimal file is j\j\ and gains have no noise. We vary N∈16,32,64,128,256N∈\16,32,64,128,256\, m∈2,4,8,16m∈\2,4,8,16\, and L∈10,20,40L∈\10,20,40\, which gives 60 settings (Appendix D.3). We report the cap term of the regret: the regret from the first epoch of each test batch and from the transition to the final file. Figure 2: Regret from the edit limit against N/mN/m. Both axes use logarithmic scales. Each panel uses a different epoch length L. Each point combines simulation settings with the same N/mN/m. The lines show the lower bound from Theorem 3 and the cap term of the upper bound from Theorem 2. The variation across settings with the same N/mN/m is smaller than the plotted marker. At each epoch length, the log-log slope of the cap term against N/mN/m is 1.061.06, with a 95% interval of [1.03,1.09][1.03,1.09] (Figure 2). For every setting with N≥4mN≥ 4m, the ratio of the cap term to the lower bound is between 4.14.1 and 5.45.4, and the cap term stays below the upper bound in all 60 settings. The edit-cap term is therefore of order (N/m)L(N/m)L, and the bounds of Theorems 2 and 3 differ by a constant factor. 6 RELATED WORK Assortment with product costs and capacity. The nearest strand of operations management is assortment optimization with a per-item cost (Kunnumkal and Martínez-de Albéniz,, 2019; Feldman and Paul,, 2019) and with a cardinality or space constraint (Rusmevichientong et al.,, 2010; Désir et al.,, 2022). Under the choice model of Appendix B the optimal assortment is revenue-ordered (Talluri and van Ryzin,, 2004); the costed and capped versions are hard, and the papers above give relaxations, approximation schemes, and learning policies. They bound revenue under a fixed choice model and supply algorithms. We bound the size of the optimal file under an attention capacity, with signed gains and a growing pool, and we study structure: the size bound, accretion, and the no-dilution converse. Hardness and approximation carry over from the cited work and are not our subject. Other choice models. Shared dilution (2) contains the general attraction model (Gallego et al.,, 2015), in which an item’s share is its attraction over the sum of attractions plus an outside term. Monotone dilution (Assumption 1) is what the assortment literature calls regularity, which alone gives tight guarantees for revenue-ordered sets (Berbeglia and Joret,, 2020) and places a model among regular, random-utility, and consideration-set classes (Gallego and Iravani,, 2024). In attention models from choice theory the probability that an item is considered does not increase as the menu grows (Lleras et al.,, 2017; Cattaneo et al.,, 2021); the assumption there is per-item, not a cap on the sum. Multipurchase models let the total mass exceed one (Abdallah et al.,, 2026), as ours does, but with additive payoffs. We know of no choice model that takes a capacity on total choice probability as a primitive. Learning with censored feedback and edit budgets. Our observation model descends from apple tasting (Helmbold et al.,, 2000), in which the label is seen only after the positive action, and from partial monitoring (Bartók et al.,, 2014), which classifies such problems by their observation map. What is new here is that the map depends on the file through dilution. Bandits with a global switch budget have a linear regret phase when the budget is below the number of arms (Simchi-Levi and Xu,, 2023; Altschuler and Talwar,, 2021); switch-efficient assortment bandits treat the switch count as an output (Dong et al.,, 2020); batched and streaming bandits limit when a policy may change or how many arms fit in memory (Perchet et al.,, 2016; He et al.,, 2025); apple tasting with a switching cost has regret of order T T (Cesari and Colomboni,, 2026). Our cap differs from all of these: it is a per-period cap on edits that renews, so the untried part of the pool shrinks at a fixed rate, and the resulting edit-cap term is matched above and below. LLM context and memory curation. Several recent systems edit files of the AGENTS.md kind from past sessions: by probing and refining the file (Shepard and Albrecht,, 2026), under an edit budget with a token-cost pruner (Xia et al.,, 2026), by tracking which edit fixed or broke what (Ma et al.,, 2026), by compiling trajectories into instructions behind replay gates (Qiu et al.,, 2026), or by turning user corrections into enforced instructions (Zhou et al.,, 2026). Memory curation has also been posed as optimization: constrained retention (Kang et al.,, 2026), promotion under a token budget (Annapureddy and Thamatani,, 2026), per-task budget allocation (Sharma et al.,, 2026), knapsack prompt compression (Zhang et al., 2026b, ), value-minus-harm scores (Wu et al.,, 2026), and a bandit over memory operations (Jiang et al.,, 2026). All use additive or submodular value, under which appending an item with positive marginal value is safe. Empirical studies document the growth of these files (Chakrabarti,, 2026; Chatlatanagulchai et al.,, 2025), their per-session cost (Gloaguen et al.,, 2026; Lulla et al.,, 2026), and the reduction in compliance as instructions accumulate (Jaroslawicz et al.,, 2025; Harada et al.,, 2025; Vasileva,, 2026), with no size effect at the sizes of real files (McMillan,, 2026; Zhang et al., 2026a, ). None models compliance as choice: no item competes with the others for attention, no signal is censored outside the file, and no result bounds regret under a review cap. 7 CONCLUSION We model context curation as an assortment problem with token costs, attention capacity, and censored feedback. Under our model, the optimal file size has a bound that does not depend on the candidate pool. As the number of instructions with positive standalone value grows without bound, appending all of them can become arbitrarily worse than optimal selection. The learning analysis distinguishes compliance from value. Under our feedback model, compliance and harm observations do not identify gain magnitudes. We establish conditions under which two sightings within a time window minimize the loss from false admissions and delayed admissions. With measured gains and additional identification assumptions, we derive a learning guarantee under limits on file edits. The upper and lower bounds match the edit-related regret term up to constant factors. Experiments with two language models show that large instruction files can reduce gross value, even before the token penalty. The best tested files remain small as the candidate pool grows under the chosen penalty. The published benchmark also shows lower average compliance at high instruction counts. The simulations reproduce the predicted scaling of regret caused by edit limits within our model. An open question is which weaker conditions permit value identification when instructions interact in different ways. Another is whether curation based on measured task gains improves agent performance under actual limits on file edits. References Abdallah et al., (2026) Abdallah, T., Braverman, A., and Gu, W. (2026). Multipurchase assortment optimization under a general random utility model. Operations Research. Altschuler and Talwar, (2021) Altschuler, J. and Talwar, K. (2021). Online learning over a finite action set with limited switching. Mathematics of Operations Research, 46(1):179–203. Annapureddy and Thamatani, (2026) Annapureddy, S. and Thamatani, A. P. (2026). The epistemics of agent memory: Measuring, and governing, the consolidation decision in long-horizon LLM agents. Bartók et al., (2014) Bartók, G., Foster, D. P., Pál, D., Rakhlin, A., and Szepesvári, C. (2014). Partial monitoring—classification, regret bounds, and algorithms. Mathematics of Operations Research, 39(4):967–997. Berbeglia and Joret, (2020) Berbeglia, G. and Joret, G. (2020). Assortment optimisation under a general discrete choice model: A tight analysis of revenue-ordered assortments. Algorithmica, 82(4):681–720. Cattaneo et al., (2021) Cattaneo, M. D., Cheung, P., Ma, X., and Masatlioglu, Y. (2021). Attention overload. Cesari and Colomboni, (2026) Cesari, T. and Colomboni, R. (2026). Two-action apple tasting with switching costs. Chakrabarti, (2026) Chakrabarti, K. (2026). Why does CLAUDE.md keep growing? Catastrophic remembering in agentic coding. arXiv:2608.11095. Chatlatanagulchai et al., (2025) Chatlatanagulchai, W., Li, H., Kashiwa, Y., Reid, B., Thonglek, K., Leelaprute, P., Rungsawang, A., Manaskasemsak, B., Adams, B., Hassan, A. E., and Iida, H. (2025). Agent READMEs: An empirical study of context files for agentic coding. Désir et al., (2022) Désir, A., Goyal, V., and Zhang, J. (2022). Technical note—capacitated assortment optimization: Hardness and approximation. Operations Research, 70(2):893–904. Dong et al., (2020) Dong, K., Li, Y., Zhang, Q., and Zhou, Y. (2020). Multinomial logit bandit with low switching cost. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 2607–2615. Feldman and Paul, (2019) Feldman, J. B. and Paul, A. (2019). Relating the approximability of the fixed cost and space constrained assortment problems. Production and Operations Management. Gallego and Iravani, (2024) Gallego, G. and Iravani, F. (2024). Axioms of rationality for discrete choice models. SSRN. Gallego et al., (2015) Gallego, G., Ratliff, R., and Shebalov, S. (2015). A general attraction model and sales-based linear program for network revenue management under customer choice. Operations Research, 63(1):212–232. Galster et al., (2026) Galster, M., Mohsenimofidi, S., Böhme, L., Lulla, J. L., Abubakar, M. A., Treude, C., and Baltes, S. (2026). A dataset of agentic AI coding tool configurations. Gloaguen et al., (2026) Gloaguen, T., Mündler-Sasahara, N., Müller, M. N., Raychev, V., and Vechev, M. (2026). Evaluating AGENTS.md: Are repository-level context files helpful for coding agents? arXiv:2602.11988. Harada et al., (2025) Harada, K., Yamazaki, Y., Taniguchi, M., Marrese-Taylor, E., Kojima, T., Iwasawa, Y., and Matsuo, Y. (2025). When instructions multiply: Measuring and estimating LLM capabilities of multiple instructions following. In Findings of the Association for Computational Linguistics: EMNLP 2025, pages 16506–16526. He et al., (2025) He, Y., Ye, Z., and Zhang, C. (2025). Understanding memory-regret trade-off for streaming stochastic multi-armed bandits. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). Helmbold et al., (2000) Helmbold, D. P., Littlestone, N., and Long, P. M. (2000). Apple tasting. Information and Computation. Jaroslawicz et al., (2025) Jaroslawicz, D., Whiting, B., Shah, P., and Maamari, K. (2025). How many instructions can LLMs follow at once? arXiv:2507.11538. Jiang et al., (2026) Jiang, E. H., Zhang, Z., Wu, Y., Li, L., Liu, D., Liang, X., Sun, R., Li, Y., Sun, E., Luo, H., Kang, Z., Caliskan, A., Chang, K.-W., and Wu, Y. N. (2026). Memory as a controlled process: Learned adaptive memory management for LLM agents. arXiv:2607.13591. Kang et al., (2026) Kang, Q., Liu, M., Kai, S., Liang, K., Zhong, T., and Yuan, M. (2026). Learning what to remember: Observability-safe memory retention via constrained optimization for long-horizon language agents. Kunnumkal and Martínez-de Albéniz, (2019) Kunnumkal, S. and Martínez-de Albéniz, V. (2019). Tractable approximations for assortment planning with product costs. Operations Research. Lleras et al., (2017) Lleras, J. S., Masatlioglu, Y., Nakajima, D., and Ozbay, E. Y. (2017). When more is less: Limited consideration. Journal of Economic Theory, 170:70–85. Lulla et al., (2026) Lulla, J. L., Mohsenimofidi, S., Galster, M., Zhang, J. M., Baltes, S., and Treude, C. (2026). On the impact of AGENTS.md files on the efficiency of AI coding agents. Ma et al., (2026) Ma, X., Liu, H., Li, Y., Zhu, J., Wang, Z., Chen, Y., and Tang, X. (2026). SEPO: Evidence-grounded prompt optimization via structural editing. McMillan, (2026) McMillan, D. (2026). Instruction adherence in coding agent configuration files: A factorial study of four file-structure variables. arXiv:2605.10039. Perchet et al., (2016) Perchet, V., Rigollet, P., Chassang, S., and Snowberg, E. (2016). Batched bandit problems. The Annals of Statistics, 44(2). Pyatkin et al., (2025) Pyatkin, V., Malik, S., Graf, V., Ivison, H., Huang, S., Dasigi, P., Lambert, N., and Hajishirzi, H. (2025). Generalizing verifiable instruction following. Qiu et al., (2026) Qiu, L., Gao, Z., Chen, J., et al. (2026). AutoRefine: Compiling trajectories into validated typed agent artifacts. Rusmevichientong et al., (2010) Rusmevichientong, P., Shen, Z.-J. M., and Shmoys, D. B. (2010). Dynamic assortment optimization with a multinomial logit choice model and capacity constraint. Operations Research, 58(6):1666–1680. Sharma et al., (2026) Sharma, S., Pandey, N. P., Gungor, O., and Rosing, T. (2026). LIMBO: Lifelong inference-time memory and budget optimization for LLM agents. Shepard and Albrecht, (2026) Shepard, A. and Albrecht, J. (2026). Probe-and-refine tuning of repository guidance for coding agents. Simchi-Levi and Xu, (2023) Simchi-Levi, D. and Xu, Y. (2023). Phase transitions in bandits with switching constraints. Management Science, 69(12):7182–7201. Talluri and van Ryzin, (2004) Talluri, K. and van Ryzin, G. (2004). Revenue management under a general discrete choice model of consumer behavior. Management Science, 50(1):15–33. Vasileva, (2026) Vasileva, M. I. (2026). Large language models can follow instructions, but not many at once: Phase transitions in compositional constraint satisfaction. Wu et al., (2026) Wu, B., Ding, Z., Huang, J., and Zhao, Y. (2026). Forget to improve: On-device LLM-Agent continual learning via budget-curated memory. arXiv:2606.25115. Xia et al., (2026) Xia, P., Han, R., Wang, Z., et al. (2026). RRSI: Regularized recursive self-improvement of agent harnesses. (39) Zhang, X., Wang, G., Cui, Y., Qiu, W., Li, Z., Zhu, B., and He, P. (2026a). Guardrails beat guidance: A large-scale study of rules, skills, and persistent configuration for coding agents. arXiv:2604.11088. (40) Zhang, Z., Cui, S., Zhang, H., and Wang, X. (2026b). PC-SubMax: Efficient prompt compression via regularized submodular maximization. Zhou et al., (2023) Zhou, J., Lu, T., Mishra, S., Brahma, S., Basu, S., Luan, Y., Zhou, D., and Hou, L. (2023). Instruction-following evaluation for large language models. Zhou et al., (2026) Zhou, Y., Guo, K., Zhuang, H., et al. (2026). Getting better at working with you: Compiling user corrections into runtime enforcement for coding agents. Appendix A PROOFS AND FURTHER RESULTS FOR SECTION 3 Throughout this appendix Θ⁡(S)=∑i∈Sθi (S)= _i∈ S _i, θ¯=supiθi θ= _i _i, amin=infiaia_ = _ia_i, g⁡(∞)=limx→∞g⁡(x)g(∞)= _x→∞g(x), and for y∈(0,1]y∈(0,1], g−1(y)=supx≥0:g⁡(x)≥yg^-1(y)= \x≥ 0:g(x)≥ y\, which is finite iff y>g⁡(∞)y>g(∞). Under (2), Q⁡(S)=Θ⁡(S)g(A⁡(S))Q(S)= (S)\,g(A(S)). Section A.1 proves the results of Section 3. Section A.2 shows that optimal files lie inside the accretion closure. Section A.3 gives the size bound under Assumption 2 when capacity fails, and a load bound that needs neither mass condition. Section A.4 sharpens the bound on files that no single deletion improves and shows that a cap at the sharpened bound insures against an underestimated token price. A.1 Proofs for Section 3 Proposition A.1 (File size bound, full version). Assume (2) with χG¯<∞χ G<∞. (i) Every S satisfies R⁡(S)≤w¯Θ(S)g(A⁡(S))−κC(S)≤w¯χG¯−κC(S)R(S)≤ w\, (S)\,g(A(S))-κ C(S)≤ w\,χ G-κ C(S), where Θ⁡(S)=∑i∈Sθi (S)= _i∈ S _i. (i) Every S with R⁡(S)≥0R(S)≥ 0 satisfies κC(S)≤w¯χG¯κ C(S)≤ w\,χ G and |S|≤χG¯/ρ|S|≤χ G/ρ. (i) If B≥w¯χG¯/κB≥ wχ G/κ, the token budget never binds: the capped optima are exactly the uncapped optima. (iv) Every optimum S⋆S has R⁡(S⋆)≥0R(S )≥ 0, so (i) applies to it for every N and every B. (v) In the single-choice case χG¯=1χ G=1, every S with R⁡(S)≥0R(S)≥ 0 has C⁡(S)≤w¯/κC(S)≤ w/κ and |S|≤1/ρ|S|≤ 1/ρ. The proof uses (2) only through Assumption 3 with Q¯=χG¯ Q=χ G; Proposition 1 is (i)-(iv) so stated. Proof of Propositions 1 and A.1. (i) Since wi≤w¯w_i≤ w, qi(S)≥0q_i(S)≥ 0 and w¯≥0 w≥ 0, R0(S)≤w¯Q(S)=w¯Θ(S)g(A⁡(S))R_0(S)≤ w\,Q(S)= w\, (S)\,g(A(S)). As θi≤χai _i≤χ a_i for every i, Θ⁡(S)≤χA(S) (S)≤χ A(S), so Θ⁡(S)g(A⁡(S))≤χA(S)g(A⁡(S))≤χG¯ (S)\,g(A(S))≤χ\,A(S)\,g(A(S))≤χ G. (i) R⁡(S)≥0R(S)≥ 0 and (i) give κC(S)≤w¯χG¯κ C(S)≤ wχ G, and C⁡(S)≥cmin|S|C(S)≥ c_ |S| gives |S|≤w¯χG¯/(κcmin)=χG¯/ρ|S|≤ wχ G/(κ c_ )=χ G/ρ. (If w¯=0 w=0 then R⁡(S)=−κC(S)≥0R(S)=-κ C(S)≥ 0 forces S=∅S= , and χG¯/ρ=0χ G/ρ=0.) (i) Let S∞S_∞ be an uncapped optimum. It has R⁡(S∞)≥R⁡(∅)=0R(S_∞)≥ R( )=0, so C⁡(S∞)≤w¯χG¯/κ≤BC(S_∞)≤ wχ G/κ≤ B by (i): S∞S_∞ is feasible under the cap, hence a capped optimum. Conversely a capped optimum S has R⁡(S)≥R⁡(S∞)R(S)≥ R(S_∞), so it is an uncapped optimum. (iv) ∅ is feasible for every B≥0B≥ 0 and R⁡(∅)=0R( )=0; the constants w¯ w, χ and G¯ G are taken over all candidates. (v) Put χG¯=1χ G=1 in (i). ∎ Proof of Corollary 1. Proposition A.1(i) with C⁡(S)≥cmin|S|C(S)≥ c_ |S| gives the bound on R⁡(S)R(S). Apply it to S=SNaccS=S_N^acc and use R⁡(SN⋆)≥0R(S _N)≥ 0 (Proposition A.1(iv)). ∎ The hypothesis |SNacc|→∞|S_N^acc|→∞ is consistent with (2) and χG¯<∞χ G<∞: any pool with infinitely many candidates satisfying wiθig(ai)>κciw_i _ig(a_i)>κ c_i has it, for example identical candidates with θi=ai=1 _i=a_i=1 and wig(1)>κciw_ig(1)>κ c_i. Proof of Proposition 2. Additivity is immediate from qi(S)=qiq_i(S)=q_i. As visolo>0v_i^solo>0 exactly on SNaccS_N^acc and visolo≤0v_i^solo≤ 0 off it, R⁡(S)≤∑i∈S∩SNaccvisolo≤R⁡(SNacc)R(S)≤ _i∈ S∩ S_N^accv_i^solo≤ R(S_N^acc), with equality iff SNacc⊆S_N^acc S and visolo=0v_i^solo=0 on S∖SNaccS S_N^acc, that is S⊆S¯NaccS S_N^acc; SNaccS_N^acc is feasible because B≥C⁡(SNacc)B≥ C(S_N^acc). ∎ The budget condition is needed: with g=(1,1)g=(1,1), c=(1,1)c=(1,1) and B=1B=1 the optima are the two singletons, and neither contains SNaccS_N^acc. A.2 Optimal files lie inside the accretion closure Under monotone dilution accretion keeps too much but never too little: an instruction with wi≤0w_i≤ 0 is in no optimal file, and one with negative standalone value never appear in optimal file. The statement and its proof hold for any positive price in place of κ and for any budget. Proposition A.2 (Optimal files lie inside the accretion closure). Under Assumption 1, with wiw_i of any sign, every optimal S⋆S satisfies S⋆⊆i:wi>0∩S¯NaccS \i:w_i>0\∩ S_N^acc, and S⋆∩SNaccS ∩ S_N^acc is also optimal. Proof. Let P=i:wi>0P=\i:w_i>0\; subsets of feasible files are feasible. Two inequalities hold for every S under Assumption 1. (L1) R⁡(S∩P)≥R⁡(S)+κC(S∖P)R(S∩ P)≥ R(S)+κ C(S P): indeed R⁡(S∩P)−R⁡(S)=∑j∈S∩Pwj[qj(S∩P)−qj(S)]−∑j∈S∖Pwjqj(S)+κC(S∖P)R(S∩ P)-R(S)= _j∈ S∩ Pw_j[q_j(S∩ P)-q_j(S)]- _j∈ S Pw_jq_j(S)+κ C(S P); the first sum is ≥0≥ 0 by monotone dilution and wj>0w_j>0, the second is ≤0≤ 0 because wj≤0w_j≤ 0. (L2) If wj≥0w_j≥ 0 for all j∈Sj∈ S and i∈Si∈ S, then R⁡(S)−R⁡(S∖i)≤visoloR(S)-R(S \i\)≤ v_i^solo: indeed R⁡(S)−R⁡(S∖i)=wiqi(S)+∑j∈S∖iwj[qj(S)−qj(S∖i)]−κciR(S)-R(S \i\)=w_iq_i(S)+ _j∈ S \i\w_j[q_j(S)-q_j(S \i\)]-κ c_i; each bracket is ≤0≤ 0 and wiqi(S)≤wiqi(i)w_iq_i(S)≤ w_iq_i(\i\). Now let S⋆S be optimal. If S⋆⊈PS P, then C⁡(S⋆∖P)>0C(S P)>0 and (L1) gives R⁡(S⋆∩P)>R⁡(S⋆)R(S ∩ P)>R(S ), a contradiction; so S⋆⊆PS P. If some i∈S⋆i∈ S had visolo<0v_i^solo<0, (L2) would give R⁡(S⋆∖i)>R⁡(S⋆)R(S \i\)>R(S ); so S⋆⊆S¯NaccS S_N^acc. Finally remove the items with visolo=0v_i^solo=0 from S⋆S one at a time; each intermediate set S′S satisfies S′⊆PS P, so (L2) gives R⁡(S′∖i)≥R⁡(S′)R(S \i\)≥ R(S ), the value never drops, and the last set is S⋆∩SNaccS ∩ S_N^acc. ∎ Assumption 1 cannot be weakened to qi(S)≤qi(i)q_i(S)≤ q_i(\i\): take candidates 1,2,31,2,3 with w=(1,10,10)w=(1,10,10), ci=1c_i=1, κ=1κ=1 and B=3B=3, q1=0.1q_1=0.1 in every file, and q2=q3=0.9q_2=q_3=0.9 in every file except 2,3\2,3\, where both are 0.10.1. Then g1=−0.9g_1=-0.9, yet the unique optimum is 1,2,3\1,2,3\ with R=15.1R=15.1: adding instruction 11 raises the compliance of 22 and 33. A.3 Size bounds without capacity Proposition 1 uses (2) only through the capacity Q¯=χG¯ Q=χ G. When G¯=∞ G=∞, for example when g decays like a power below one, two bounds remain. The first uses only Assumption 2 and does not require the shared-dilution parameterization. Let =n≥0:κcminn≤w¯M(n)N=\n≥ 0:κ c_ \,n≤ wM(n)\ be the sizes at which the compliance mass can still pay for the file, and M∗(n)=maxk≤n⁡M⁡(k)M^*(n)= _k≤ nM(k). Proposition A.3 (File size bound under bounded-average compliance). (i) Every S satisfies R⁡(S)≤w¯M(|S|)−κC(S)R(S)≤ wM(|S|)-κ C(S). (i) If R⁡(S)≥0R(S)≥ 0, then κC(S)≤w¯M(|S|)κ C(S)≤ wM(|S|) and |S|∈|S| . (i) Under Assumption 2, N is finite. With n¯=max⁡ n= , every S with R⁡(S)≥0R(S)≥ 0 has |S|≤n¯|S|≤ n and C⁡(S)≤w¯M∗(n¯)/κC(S)≤ wM^*( n)/κ, and a cap B≥w¯M∗(n¯)/κB≥ wM^*( n)/κ never binds. (iv) Every optimal S⋆S has R⁡(S⋆)≥0R(S )≥ 0, so (i) and (i) apply to it, with bounds that depend on neither N nor B. Proof. (i) Since wi≤w¯w_i≤ w, qi(S)≥0q_i(S)≥ 0 and w¯≥0 w≥ 0, R0(S)≤w¯Q(S)≤w¯M(|S|)R_0(S)≤ w\,Q(S)≤ wM(|S|). (i) Combine R⁡(S)≥0R(S)≥ 0 with (i) and C⁡(S)≥cmin|S|C(S)≥ c_ |S|. (i) If w¯=0 w=0, then =0N=\0\. Otherwise Assumption 2 gives M⁡(n)<ρnM(n)<ρ\,n, that is n∉n , for all large n. Then κC(S)≤w¯M(|S|)≤w¯M∗(n¯)κ C(S)≤ wM(|S|)≤ wM^*( n). The cap never binds by the argument of Proposition A.1(i), with w¯M∗(n¯) wM^*( n) in place of w¯χG¯ wχ G. (iv) ∅ is feasible and R⁡(∅)=0R( )=0; w¯ w and M are taken over all candidates. ∎ Lemma A.4. Under Assumption 1, M⁡(n+1)/(n+1)≤M⁡(n)/nM(n+1)/(n+1)≤ M(n)/n for n≥1n≥ 1. Hence Assumption 2 holds iff M⁡(n1)<ρn1M(n_1)<ρ\,n_1 for some n1≥1n_1≥ 1, and N is an initial segment of ℕN. Proof. Fix S′S with |S′|=n+1|S |=n+1 and let j∈S′j∈ S minimize qj(S′)q_j(S ). Removing the smallest of n+1n+1 terms keeps at least a share n/(n+1)n/(n+1) of the sum, and Assumption 1 gives qi(S′∖j)≥qi(S′)q_i(S \j\)≥ q_i(S ), so M⁡(n)≥∑i∈S′∖jqi(S′∖j)≥∑i∈S′∖jqi(S′)≥n+1∑i∈S′qi(S′)M(n)≥ _i∈ S \j\q_i(S \j\)≥ _i∈ S \j\q_i(S )≥ nn+1 _i∈ S q_i(S ). Take the supremum over S′S . A nonincreasing sequence has limit superior equal to its infimum, which is below ρ iff some term is. For n≥1n≥ 1, n∈n iff M⁡(n)/n≥ρM(n)/n≥ρ, which is preserved as n decreases, and 0∈0 . ∎ Remarks. Without Assumption 1, N need not be an interval (Lemma A.4 needs the assumption), which is why n¯ n is defined as a maximum: take identical candidates with wi=ci=1w_i=c_i=1, κ=0.5κ=0.5, and qi(S)=0.1q_i(S)=0.1 if |S|≤2|S|≤ 2, 11 if |S|=3|S|=3, and 00 if |S|≥4|S|≥ 4; then =0,3N=\0,3\ and R⁡(S)=1.5R(S)=1.5 for |S|=3|S|=3. The strict inequality in Assumption 2 cannot be relaxed: for identical instructions with q⁡(n)=ρ+(1−ρ)/n2q(n)=ρ+(1-ρ)/n^2 and 0<ρ<10<ρ<1, Assumption 1 holds, M⁡(n)/n→ρM(n)/n→ρ, every instruction is in SNaccS_N^acc, and R⁡(S)=w¯(1−ρ)/|S|R(S)= w(1-ρ)/|S|, so R⁡(SNacc)→0R(S_N^acc)→ 0 while R⁡(SN⋆)=w¯(1−ρ)R(S _N)= w(1-ρ) for B≥cminB≥ c_ . Examples. Table 1 takes identical instructions (wi=w¯>0w_i= w>0, ci=cminc_i=c_ ) whose compliance q⁡(n)q(n) in a file of n is nonincreasing. Then Assumption 1 holds, M⁡(n)=nq(n)M(n)=nq(n), R(S)=w¯[M(n)−ρn]R(S)= w\,[M(n)-ρ\,n] for |S|=n|S|=n, and n¯=max⁡n:q⁡(n)≥ρ n= \n:q(n)≥ρ\ (00 if q⁡(1)<ρq(1)<ρ). When M is bounded, the cost bound w¯supnM⁡(n)/κ w _nM(n)/κ is linear in w¯/κ w/κ. Under power dilution (0<β<10<β<1), n¯ n grows like (w¯/κ)1/β( w/κ)^1/β and, for α>ρα>ρ, blows up as β↓0β 0, the no-dilution limit. Table 1: Identical instructions with compliance q⁡(n)q(n) in a file of n, where 0<α≤10<α≤ 1, b,u>0b,u>0, 0<β<10<β<1, u=v/v0u=v/v_0 and ⌊y⌋+=max⁡(0,⌊y⌋) y ^+= (0, y ). Assumption 2 holds in the first three rows for every ρ, and in the last iff α<ρα<ρ. The n¯ n column assumes w¯>0 w>0; if w¯=0 w=0, then =0N=\0\ and n¯=0 n=0. Dilution q⁡(n)q(n) M⁡(n)M(n) n¯ n Single choice u1+nu u1+nu <1<1 ⌊1/ρ−1/u⌋+ 1/ρ-1/u ^+ Exponential αe−bnα e^-bn ≤αbe≤ αbe ⌊ln⁡(α/ρ)/b⌋+ (α/ρ)/b ^+ Power (β<1β<1) αn−βα n^-β αn1−βα n^1-β ⌊(α/ρ)1/β⌋ (α/ρ)^1/β None α αnα n ∞ if α≥ρα≥ρ, else 00 If the budget does not bind, the optimal size maximizes M⁡(n)−ρnM(n)-ρ\,n, which is unimodal in each row, so it is ⌊n∗⌋ n^* or ⌈n∗⌉ n^* for the continuous maximizer n∗n^*, clipped at 00: n∗=(u/ρ−1)/un^*=( u/ρ-1)/u (single choice), (1−W0(eρ/α))/b(1-W_0(eρ/α))/b with W0W_0 the principal Lambert branch (exponential), ((1−β)α/ρ)1/β((1-β)α/ρ)^1/β (power), and ∞ if α>ρα>ρ (none). In the power row the optimal size is therefore about a fraction n∗/n¯≈(1−β)1/β<1/en^*/ n≈(1-β)^1/β<1/e of n¯ n as ρ→0ρ→ 0. Power dilution with β≥1β≥ 1 is excluded from the table: then M⁡(n)=αn1−βM(n)=α n^1-β is nonincreasing for n≥1n≥ 1, so the optimal size is 11 if α>ρα>ρ, 00 if α<ρα<ρ, and both 00 and 11 are optimal if α=ρα=ρ. The second bound applies to optima only and uses the form (2) without capacity or bounded average compliance: every instruction in an optimal file is followed often enough to cover its setup cost at the file’s attention load, which bounds the load. Proposition A.5 (Load bound on optima). Assume (2) with w¯>0 w>0 and θ¯<∞ θ<∞, and let S⋆S be a nonempty optimum under any budget. Then wi>0w_i>0 on S⋆S , κci≤wiθig(A⁡(S⋆))κ c_i≤ w_i _i\,g(A(S )) for every i∈S⋆i∈ S , and g⁡(A⁡(S⋆))≥ρ/θ¯g(A(S ))≥ρ/ θ. Hence, if ρ/θ¯>1ρ/ θ>1 the only optimum is ∅ ; and if g⁡(∞)<ρ/θ¯≤1g(∞)<ρ/ θ≤ 1 then A⁡(S⋆)≤g−1(ρ/θ¯)<∞A(S )≤ g^-1(ρ/ θ)<∞ and, when amin>0a_ >0, |S⋆|≤g−1(ρ/θ¯)/amin|S |≤ g^-1(ρ/ θ)/a_ . Proof. By Assumption 1, wi>0w_i>0 on S⋆S by Proposition A.2. Fix i∈S⋆i∈ S ; the file S⋆∖iS \i\ is feasible. By Assumption 1 and wl>0w_l>0 for l≠il≠ i, R⁡(S⋆∖i)≥∑l∈S⋆∖iwlql(S⋆)−κC(S⋆)+κci=R⁡(S⋆)−wiqi(S⋆)+κciR(S \i\)≥ _l∈ S \i\w_lq_l(S )-κ C(S )+κ c_i=R(S )-w_iq_i(S )+κ c_i, and optimality gives wiqi(S⋆)≥κciw_iq_i(S )≥κ c_i, that is κci≤wiθig(A⁡(S⋆))κ c_i≤ w_i _i\,g(A(S )). Since wi≤w¯w_i≤ w, θi≤θ¯ _i≤ θ and ci≥cminc_i≥ c_ , g⁡(A⁡(S⋆))≥κcmin/(w¯θ¯)=ρ/θ¯g(A(S ))≥κ c_ /( w θ)=ρ/ θ. As g≤1g≤ 1, this is impossible when ρ/θ¯>1ρ/ θ>1. When g⁡(∞)<ρ/θ¯≤1g(∞)<ρ/ θ≤ 1, A⁡(S⋆)A(S ) belongs to x:g⁡(x)≥ρ/θ¯\x:g(x)≥ρ/ θ\, whose supremum g−1(ρ/θ¯)g^-1(ρ/ θ) is finite; and |S⋆|amin≤A⁡(S⋆)|S |\,a_ ≤ A(S ). ∎ A.4 Sharpened size bound and cap insurance Proposition 1 bounds every file with R⁡(S)≥0R(S)≥ 0. Files that no single deletion improves obey a sharper bound, because the deletion conditions bound the total setup cost by the file’s own gross value. Throughout this subsection (2) holds. For a price μ≥0μ≥ 0 let Rμ(S)=R0(S)−μC(S)R_μ(S)=R_0(S)-μ C(S), so R=RκR=R_κ, and let Rμ⋆=maxS⊆[N]⁡Rμ(S)R _μ= _S [N]R_μ(S) be the uncapped optimum at price μ. A nonempty file S is deletion-stable at μ if Rμ(S∖i)≤Rμ(S)R_μ(S \i\)≤ R_μ(S) for every i∈Si∈ S. Every nonempty optimum under any budget is deletion-stable at κ, since deleting an item keeps the file feasible, and so is every nonempty file returned by a local search with deletion moves. For a nonempty S write A=A⁡(S)A=A(S), W⁡(S)=∑i∈SwiθiW(S)= _i∈ Sw_i _i, ϕ=R0(S)=g⁡(A)W(S)φ=R_0(S)=g(A)\,W(S), amaxS=maxi∈S⁡aia^S_ = _i∈ Sa_i, and ei(S) e_i(S) =1θi(1g⁡(A)−1g⁡(A−ai))≥0, = 1 _i ( 1g(A)- 1g(A-a_i) )≥ 0, E⁡(S) E(S) =∑i∈Sθiei(S), = _i∈ S _i\,e_i(S), Xg(S) X_g(S) =Θ⁡(S)g(A−amaxS)[1−g⁡(A)E(S)]. = (S)\,g(A-a^S_ )\, [1-g(A)E(S) ]. The quantity ei(S)e_i(S) is nonnegative because g is nonincreasing and ai>0a_i>0. Let X¯g=supXg(S) X_g= X_g(S) over nonempty finite S with wi>0w_i>0 on S (X¯g=0 X_g=0 if there is no such S), and ag=w¯X¯ga_g= w X_g. Lemma A.6 (Single deletion). For nonempty S and i∈Si∈ S, R0(S)−R0(S∖i)=θig(A−ai)[wi−ϕei(S)]R_0(S)-R_0(S \i\)= _i\,g(A-a_i)\,[w_i-φ\,e_i(S)]. Proof. R0(S)−R0(S∖i)=g⁡(A)W(S)−g⁡(A−ai)(W⁡(S)−wiθi)=wiθig(A−ai)−W⁡(S)[g⁡(A−ai)−g⁡(A)]R_0(S)-R_0(S \i\)=g(A)W(S)-g(A-a_i)(W(S)-w_i _i)=w_i _i\,g(A-a_i)-W(S)[g(A-a_i)-g(A)]. By the definition of eie_i, g⁡(A−ai)−g⁡(A)=θiei(S)g(A)g(A−ai)g(A-a_i)-g(A)= _ie_i(S)\,g(A)\,g(A-a_i), so the last term is ϕθiei(S)g(A−ai)φ\, _ie_i(S)\,g(A-a_i). ∎ Proposition A.7 (Sharpened size bound). Assume (2), let wiw_i be of any sign, and let S be deletion-stable at μ>0μ>0. (i) wi>ϕei(S)w_i>φ\,e_i(S) for every i∈Si∈ S, and W⁡(S)[1−g⁡(A)E(S)]>0W(S)\,[1-g(A)E(S)]>0. If g⁡(A)E(S)<1g(A)E(S)<1, in particular if |S|=1|S|=1, then ϕ>0φ>0 and wi>0w_i>0 on S. (i) If ϕ>0φ>0, then wi>0w_i>0 on S and μC(S)≤ϕ⋅g⁡(A−amaxS)g⁡(A)[1−g⁡(A)E(S)]≤ϕ,so Rμ(S)≥0.μ\,C(S)≤φ· g(A-a^S_ )g(A)\, [1-g(A)E(S) ]≤φ, R_μ(S)≥ 0. (i) If ϕ>0φ>0, then μC(S)≤w¯Xg(S)≤agμ\,C(S)≤ w\,X_g(S)≤ a_g, and Xg(S)≤Q(S)X_g(S)≤ Q(S); under χG¯<∞χ G<∞, ag≤w¯χG¯a_g≤ wχ G. Hence every optimum at any price μ>0μ>0 under any budget has μC(S⋆)≤agμ\,C(S )≤ a_g, and a cap B≥ag/κB≥ a_g/κ never binds: its optima are exactly the uncapped optima. Proof. (i) Stability at μ and Lemma A.6 give θig(A−ai)[wi−ϕei(S)]≥μci>0 _i\,g(A-a_i)\,[w_i-φ e_i(S)]≥μ c_i>0, and θig(A−ai)>0 _ig(A-a_i)>0, so wi>ϕei(S)w_i>φ e_i(S). Multiply by θi _i and sum over S: W⁡(S)>ϕE(S)=g⁡(A)W(S)E(S)W(S)>φ E(S)=g(A)W(S)E(S), that is W⁡(S)[1−g⁡(A)E(S)]>0W(S)[1-g(A)E(S)]>0. If 1−g⁡(A)E(S)>01-g(A)E(S)>0 then W⁡(S)>0W(S)>0, so ϕ=g⁡(A)W(S)>0φ=g(A)W(S)>0 and wi>ϕei(S)≥0w_i>φ e_i(S)≥ 0. For S=iS=\i\, E⁡(S)=1/g⁡(ai)−1E(S)=1/g(a_i)-1 and g⁡(A)E(S)=1−g⁡(ai)<1g(A)E(S)=1-g(a_i)<1. (i) If ϕ>0φ>0 then W⁡(S)>0W(S)>0, so 1−g⁡(A)E(S)>01-g(A)E(S)>0 by (i), and then wi>ϕei(S)≥0w_i>φ e_i(S)≥ 0. Sum the stability inequalities over S, using g⁡(A−ai)≤g⁡(A−amaxS)g(A-a_i)≤ g(A-a^S_ ) (as A−ai≥A−amaxSA-a_i≥ A-a^S_ and g is nonincreasing) and the positive brackets: μC(S)≤g⁡(A−amaxS)∑i∈Sθi[wi−ϕei(S)]=g⁡(A−amaxS)[W⁡(S)−ϕE(S)]μ C(S)≤ g(A-a^S_ ) _i∈ S _i[w_i-φ e_i(S)]=g(A-a^S_ )[W(S)-φ E(S)], and W⁡(S)=ϕ/g⁡(A)W(S)=φ/g(A) gives the first bound. For the second, every term of E⁡(S)E(S) is nonnegative, so E⁡(S)≥1/g⁡(A)−1/g⁡(A−amaxS)E(S)≥ 1/g(A)-1/g(A-a^S_ ), hence 1−g⁡(A)E(S)≤g⁡(A)/g⁡(A−amaxS)1-g(A)E(S)≤ g(A)/g(A-a^S_ ) and the first bound is at most ϕφ. (i) W⁡(S)≤w¯Θ(S)W(S)≤ w\, (S) since wi≤w¯w_i≤ w, θi>0 _i>0 and w¯≥0 w≥ 0. Insert this in μC(S)≤g⁡(A−amaxS)[W⁡(S)−ϕE(S)]=g⁡(A−amaxS)W(S)[1−g⁡(A)E(S)]μ C(S)≤ g(A-a^S_ )[W(S)-φ E(S)]=g(A-a^S_ )\,W(S)\,[1-g(A)E(S)], where the bracket is positive by (i), to get μC(S)≤w¯Xg(S)μ C(S)≤ wX_g(S); by (i) wi>0w_i>0 on S, so Xg(S)≤X¯gX_g(S)≤ X_g. The inequality g⁡(A−amaxS)[1−g⁡(A)E(S)]≤g⁡(A)g(A-a^S_ )[1-g(A)E(S)]≤ g(A) of (i) gives Xg(S)≤Θ⁡(S)g(A)=Q⁡(S)X_g(S)≤ (S)g(A)=Q(S), and Q⁡(S)≤χG¯Q(S)≤χ G as in Proposition A.1(i). For the consequences, a nonempty optimum S⋆S at price μ is deletion-stable at μ and has wi>0w_i>0 on S⋆S by Proposition A.2 at price μ, so ϕ>0φ>0 and (i) gives μC(S⋆)≤agμ C(S )≤ a_g; the empty optimum has cost 00. The cap never binds by the argument of Proposition A.1(i), with aga_g in place of w¯χG¯ wχ G. ∎ The case split in (i) is needed. Take g⁡(x)=e−xg(x)=e^-x, two identical instructions with θi=ai=1 _i=a_i=1, wi=−1w_i=-1, ci=1c_i=1, and μ=0.01μ=0.01. Then Rμ(1,2)=−2e−2−0.02≈−0.291R_μ(\1,2\)=-2e^-2-0.02≈-0.291 exceeds Rμ(1)=−e−1−0.01≈−0.378R_μ(\1\)=-e^-1-0.01≈-0.378, so 1,2\1,2\ is deletion-stable with ϕ<0φ<0, both wi<0w_i<0 and Rμ<0R_μ<0; here g⁡(A)E(S)=2(1−e−1)>1g(A)E(S)=2(1-e^-1)>1. Deleting a harmful instruction un-dilutes the other harmful instruction. Optima are unaffected, since they have ϕ>0φ>0. Under the model of Appendix B, g⁡(A)E(S)=Q⁡(S)<1g(A)E(S)=Q(S)<1 for every file, so the sign conclusions of (i) hold for every deletion-stable file, and Xg(S)X_g(S) has the explicit form of Appendix B; a closed form of X¯g X_g for a general g is open, and the bound ag≤w¯χG¯a_g≤ wχ G is what we use. A cap also protects a curator who misestimates the token price. One who treats tokens as free, as an appending tool does, can lose without bound; a cap at ag/κa_g/κ bounds that loss by aga_g, and when the price is overestimated the cap never binds, so it adds no loss of its own. The cap must be set by whoever estimates the token price more accurately than the curator; set with the curator’s own underestimate it protects nothing. Lemma A.8 (Envelope bound). Assume (2). For 0<κ≤μ0<κ≤μ, Rκ⋆−Rμ⋆≤agln⁡(μ/κ)R _κ-R _μ≤ a_g (μ/κ). Proof. For 0<μ1≤μ20< _1≤ _2 let S1S_1 be an uncapped optimum at μ1 _1. Then Rμ1⋆=Rμ2(S1)+(μ2−μ1)C(S1)≤Rμ2⋆+(μ2−μ1)ag/μ1R _ _1=R_ _2(S_1)+( _2- _1)C(S_1)≤ R _ _2+( _2- _1)a_g/ _1, because μ1C(S1)≤ag _1C(S_1)≤ a_g by Proposition A.7 applied at price μ1 _1 (S1S_1 is an optimum at μ1 _1, or empty). Fix n≥1n≥ 1 and put μj=κ(μ/κ)j/n _j=κ(μ/κ)^j/n for j=0,…,nj=0,…,n. Summing the one-step bound over the n steps, Rκ⋆−Rμ⋆≤ag∑j<n(μj+1/μj−1)=agn((μ/κ)1/n−1)R _κ-R _μ≤ a_g _j<n( _j+1/ _j-1)=a_g\,n\,((μ/κ)^1/n-1), which tends to agln⁡(μ/κ)a_g (μ/κ) as n→∞n→∞. ∎ Corollary A.9 (A cap insures against an underestimated token price). Assume (2). Let the curator solve maxR0(S)−κ^C(S):S⊆[N],C(S)≤B \R_0(S)- κC(S):S [N],\ C(S)≤ B\ exactly with an estimate κ^≥0 κ≥ 0 of the true price κ>0κ>0, and call Rκ⋆−R⁡(S)R _κ-R(S) its loss. (i) If κ^≤κ κ≤κ and B≥ag/κB≥ a_g/κ, the loss is at most (κ−κ^)min⁡(B,ag/κ^)(κ- κ) (B,a_g/ κ), with ag/0=∞a_g/0=∞; at B=ag/κB=a_g/κ this is at most ag(1−κ^/κ)≤aga_g(1- κ/κ)≤ a_g. (i) If κ^≥κ κ≥κ and B≥ag/κB≥ a_g/κ, the cap is slack (C⁡(S)≤ag/κ^C(S)≤ a_g/ κ, and S is an uncapped optimum at κ κ), and the loss is at most min⁡agln⁡(κ^/κ),Rκ⋆ \a_g ( κ/κ),\ R _κ\. (i) Without a cap and with 0<κ^≤κ0< κ≤κ, the loss is at most ag(κ/κ^−1)a_g(κ/ κ-1). Proof. Let S be the curator’s file, an optimum of the capped problem at price κ κ, and SκS_κ an uncapped optimum at κ. When κ^>0 κ>0 and S≠∅S≠ , S is deletion-stable at κ κ with wi>0w_i>0 on S (Proposition A.2 at price κ κ), so κ^C(S)≤ag κC(S)≤ a_g by Proposition A.7(i); the same holds for S=∅S= . For every file S′S , R⁡(S′)−R⁡(S)=[Rκ^(S′)−Rκ^(S)]+(κ−κ^)(C⁡(S)−C⁡(S′)).R(S )-R(S)=[R_ κ(S )-R_ κ(S)]+(κ- κ)(C(S)-C(S )). (3) (i) C⁡(Sκ)≤ag/κ≤BC(S_κ)≤ a_g/κ≤ B by Proposition A.7, so SκS_κ is feasible for the curator and Rκ^(Sκ)≤Rκ^(S)R_ κ(S_κ)≤ R_ κ(S). With S′=SκS =S_κ and κ^≤κ κ≤κ, (3) gives Rκ⋆−R⁡(S)≤(κ−κ^)C(S)R _κ-R(S)≤(κ- κ)C(S). Now C⁡(S)≤BC(S)≤ B, and if κ^>0 κ>0 then C⁡(S)≤ag/κ^C(S)≤ a_g/ κ; hence C⁡(S)≤min⁡(B,ag/κ^)C(S)≤ (B,a_g/ κ). At B=ag/κB=a_g/κ the bound is (κ−κ^)ag/κ=ag(1−κ^/κ)(κ- κ)a_g/κ=a_g(1- κ/κ). (i) C⁡(S)≤ag/κ^C(S)≤ a_g/ κ. An uncapped optimum Sκ^S_ κ at κ κ has C⁡(Sκ^)≤ag/κ^≤ag/κ≤BC(S_ κ)≤ a_g/ κ≤ a_g/κ≤ B, so it is feasible for the curator and Rκ^(Sκ^)≤Rκ^(S)R_ κ(S_ κ)≤ R_ κ(S): S is an uncapped optimum at κ κ, that is Rκ^(S)=Rκ^⋆R_ κ(S)=R _ κ. Since κ^≥κ κ≥κ, R⁡(S)=Rκ^(S)+(κ^−κ)C(S)≥Rκ^⋆≥Rκ^(∅)=0R(S)=R_ κ(S)+( κ-κ)C(S)≥ R _ κ≥ R_ κ( )=0, so the loss is at most Rκ⋆R _κ, and it is at most Rκ⋆−Rκ^⋆≤agln⁡(κ^/κ)R _κ-R _ κ≤ a_g ( κ/κ) by Lemma A.8. (i) Without a cap, SκS_κ is feasible, and (3) with S′=SκS =S_κ gives Rκ⋆−R⁡(S)≤(κ−κ^)C(S)≤(κ−κ^)ag/κ^=ag(κ/κ^−1)R _κ-R(S)≤(κ- κ)C(S)≤(κ- κ)a_g/ κ=a_g(κ/ κ-1). ∎ Under the model of Appendix B the bound in (i) is attained for every κ κ, so the uncapped loss is unbounded as κ^→0 κ→ 0; whether it is attained for a general g is open. Appendix B THE MULTINOMIAL LOGIT CASE The multinomial logit model is shared dilution with g⁡(x)=1/(1+x)g(x)=1/(1+x) and θi=ai=ui=vi/v0 _i=a_i=u_i=v_i/v_0. Assumption 1′ (Multinomial logit). Instruction i has weight vi>0v_i>0, the agent’s default behaviour has weight v0>0v_0>0, and qi(S)=vi/(v0+V⁡(S))q_i(S)=v_i/(v_0+V(S)) with V⁡(S)=∑i∈SviV(S)= _i∈ Sv_i. Write U⁡(S)=∑i∈SuiU(S)= _i∈ Su_i and D⁡(S)=1+U⁡(S)D(S)=1+U(S), so that qi(S)=ui/D⁡(S)q_i(S)=u_i/D(S) and Q⁡(S)=U⁡(S)/D⁡(S)=1−1/D⁡(S)<1Q(S)=U(S)/D(S)=1-1/D(S)<1. Every instance satisfies the requirement θig(ai)=ui/(1+ui)<1 _ig(a_i)=u_i/(1+u_i)<1 of Section 2. Here χ=1χ=1 and G¯=supxx/(1+x)=1 G= _xx/(1+x)=1, so the capacity is Q¯=1 Q=1: the agent follows at most one instruction per session on average, which is the single-choice case of Proposition A.1(v). The quantities of Appendix A.4 read, with umax=maxi∈S⁡uiu_ = _i∈ Su_i: W⁡(S)=∑i∈SwiuiW(S)= _i∈ Sw_iu_i, ϕ=R0(S)=W⁡(S)/D⁡(S)φ=R_0(S)=W(S)/D(S), ei(S)=1e_i(S)=1, E⁡(S)=U⁡(S)E(S)=U(S), g⁡(A)E(S)=Q⁡(S)<1g(A)E(S)=Q(S)<1, and R0(S)−R0(S∖i)=ui(wi−ϕ)D⁡(S)−ui,Xg(S)=U⁡(S)D⁡(S)(D⁡(S)−umax).R_0(S)-R_0(S \i\)= u_i(w_i-φ)D(S)-u_i, X_g(S)= U(S)D(S)\,(D(S)-u_ ). Since g⁡(A)E(S)<1g(A)E(S)<1 for every file, Proposition A.7(i) gives wi>ϕ>0w_i>φ>0 on every deletion-stable file, and Proposition A.7(i) reads μC(S)≤ϕ/(D⁡(S)−umax)μ C(S)≤φ/(D(S)-u_ ). The capped problem is capacitated multinomial logit assortment with product costs (Kunnumkal and Martínez-de Albéniz,, 2019), NP-hard in general (Désir et al.,, 2022). Appendix C PROOFS AND FURTHER RESULTS FOR SECTION 4 Section C.1 states the latent-variable model behind Assumption 4 and the tied-loads condition. Section C.2 states and proves Theorem C.5. Section C.3 proves Proposition 3 and gives the result on magnitude feedback. Section C.4 proves Theorem 1. Section C.5 gives the estimator of ETC-m, its error bound, the full regret bound with its tuned form, and the proofs of Theorems 2 and 3. C.1 Formal assumptions Assumption C.1 (Observations). The parameters are ϖ=(p,q,h,r+,r−,η,δ) =(p,q,h,r^+,r^-,η,δ): relevance pi∈[0,1]p_i∈[0,1]; a compliance function q on pairs (S,i)(S,i) with i∈Si∈ S, with values in [0,1][0,1]; harm probability hi∈[0,1]h_i∈[0,1]; gain ri+≥0r_i^+≥ 0 given a helpful outcome and loss ri−≥0r_i^-≥ 0 given a harmful one, so ri=(1−hi)ri+−hiri−r_i=(1-h_i)r_i^+-h_ir_i^-; harm-flag rate η∈(0,1]η∈(0,1]; gap-detection rates δi∈(0,1] _i∈(0,1]. A design is a fixed sequence of files (St)t≥1(S_t)_t≥ 1. In session t each item i has independent latent draws ξi,t∼Bern⁡(pi) _i,t (p_i) (relevance), Fi,t∼Bern⁡(qi(St))F_i,t (q_i(S_t)) (compliance), ζi,t∼Bern⁡(hi) _i,t (h_i) (harmful outcome), ϑi,t∼Bern⁡(η) _i,t (η) (flag) and γi,t∼Bern⁡(δi) _i,t ( _i) (gap detection), independent across items and sessions, and a gain Xi,tX_i,t with ⁡[Xi,t∣ζi,t=0]=ri+E[X_i,t _i,t=0]=r_i^+ and ⁡[Xi,t∣ζi,t=1]=−ri−E[X_i,t _i,t=1]=-r_i^-, independent of the other draws given ζi,t _i,t; the gains are independent across items and sessions and, given ζi,t _i,t, identically distributed. The curator observes, for i∈Sti∈ S_t: ξi,t _i,t; if ξi,t=1 _i,t=1, Fi,tF_i,t; if ξi,tFi,t=1 _i,tF_i,t=1, the harm flag Hi,t=ζi,tϑi,tH_i,t= _i,t _i,t. For i∉Sti∉ S_t it observes only the gap flag Γi,t=ξi,tγi,t _i,t= _i,t _i,t. It never observes Xi,tX_i,t. The expected per-session gain of a loaded item is piqi(S)ri=wiqi(S)p_iq_i(S)r_i=w_iq_i(S), as in (1). Under (2) the compliance function is qi(S)=θig(A⁡(S))q_i(S)= _ig(A(S)) and its parameters are (θ,a)(θ,a). The typed case is hi∈0,1h_i∈\0,1\ with ri±>0r_i^±>0. Assumption C.2 (Sightings). A candidate’s sighting indicators Yt∈0,1Y_t∈\0,1\, t≥1t≥ 1, are i.i.d. Bern⁡(π)Bern(π), with π=επ= for a spurious candidate and π=δjpjπ= _jp_j for a real one. Assumption C.3 (Magnitude feedback). In addition to Assumption C.1: for i∈Sti∈ S_t with ξi,tFi,t=1 _i,tF_i,t=1 the curator observes Xi,t∈[−1,1]X_i,t∈[-1,1], so |wi|≤1|w_i|≤ 1; pi≥pmin>0p_i≥ p_ >0 for all i; and the curator has an exact, measurable oracle for the capped problem with estimated parameters (the maximization in ETC-m below). Assumption C.4 (Tied loads). Compliance follows (2) with θi=λai _i=λ a_i for a known λ>0λ>0, the curve g is known and continuously differentiable, and ai≤amaxa_i≤ a_ for a known amaxa_ . With s the batch size of ETC-m, xs=samaxx_s=sa_ and G⁡(x)=xg(x)G(x)=xg(x), γs=minx∈[0,xs]⁡G′(x)>0. _s= _x∈[0,x_s]G (x)>0. Assumption 4 is Assumption C.1, and with magnitude feedback it is Assumption C.3. Under tied loads Q⁡(S)=λA(S)g(A⁡(S))=λG(A⁡(S))Q(S)=λ A(S)g(A(S))=λ G(A(S)), and γs>0 _s>0 makes G injective on [0,xs][0,x_s], the range of the load of a batch. This is an identification condition, not a regularity condition: for g⁡(x)=e−βxg(x)=e^-β x, G peaks at 1/β1/β, and if xs>1/βx_s>1/β two loads A1<1/β<A2A_1<1/β<A_2 with G⁡(A1)=G⁡(A2)G(A_1)=G(A_2) give a batch the same compliances under a(1)a^(1) and under ai(2)=ai(1)A2/A1a^(2)_i=a^(1)_iA_2/A_1, while the two instances disagree on larger files. Observable rates. Under Assumption C.1 the observations of different items and sessions are independent, so the law of the observation process under a design is the product of the laws of the single observations Oi,tO_i,t. For i∈Sti∈ S_t, Oi,tO_i,t takes the values ξ=0ξ=0, (ξ,F)=(1,0)(ξ,F)=(1,0), (ξ,F,H)=(1,1,0)(ξ,F,H)=(1,1,0) and (1,1,1)(1,1,1) with probabilities 1−pi1-p_i, pi(1−qi(St))p_i(1-q_i(S_t)), piqi(St)(1−ηhi)p_iq_i(S_t)(1-η h_i) and piqi(St)ηhip_iq_i(S_t)\,η h_i. For i∉Sti∉ S_t, Oi,t=Γi,t∼Bern⁡(δipi)O_i,t= _i,t ( _ip_i). Hence two parameter vectors give the same observation law iff, for every (t,i)(t,i) with i∈Sti∈ S_t, they agree on pip_i, piqi(St)p_iq_i(S_t) and piqi(St)ηhip_iq_i(S_t)η h_i, and for every (t,i)(t,i) with i∉Sti∉ S_t they agree on δipi _ip_i. We call these the observable rates. They do not involve (r+,r−)(r^+,r^-), and they involve q only through the values qi(St)q_i(S_t) on played pairs. C.2 Identification A parameter is identified under a design if any two parameter vectors with the same law of the observations agree on it. Theorem C.5 (What censored transcripts identify). Assumption 4 with compliance (2), under a design (St)(S_t). (a) For i∈Sti∈ S_t with pi>0p_i>0, qi(St)q_i(S_t) is identified, and nothing else about compliance is: two compliance functions that agree on the played pairs (St,i)(S_t,i) give the same law. The law of the compliance data depends on the parameters only through (p,q)(p,q), so no test of ri>0r_i>0 against ri<0r_i<0 that uses compliance data alone has power above its size. (b) If i\i\ is played and pi>0p_i>0, then θig(ai) _ig(a_i) is identified. A design of singleton files identifies neither θi _i nor aia_i. Within one played file, θi/θj _i/ _j is identified when pi,pj>0p_i,p_j>0. (c) If S and S∪iS∪\i\ are played, i∉Si∉ S, and some k∈Sk∈ S has pk>0p_k>0, then g⁡(A⁡(S)+ai)/g⁡(A⁡(S))g(A(S)+a_i)/g(A(S)) is identified, and aia_i is identified once A⁡(S)A(S) is, provided the map x↦g⁡(A⁡(S)+x)x g(A(S)+x) is injective on the allowed interval for aia_i. A⁡(S)A(S) is identified when pj>0p_j>0 and θj=λaj _j=λ a_j on S with λ known, and x↦xg(x)x xg(x) is injective on an interval known to contain A⁡(S)A(S). (d) For i∈Sti∈ S_t with piqi(St)>0p_iq_i(S_t)>0, ηhiη h_i is identified, hence whether i ever harms. In the typed case sign⁡(ri) (r_i) is identified; in general it is not, and |ri||r_i| never is. (e) For i never played, the observations involving i are sightings with law Bern⁡(δipi)Bern( _ip_i) per session, and nothing separates δi _i from pip_i. If the sighting rate δ is common and some j0j_0 with pj0>0p_j_0>0 is played in one session and left out in another, then δ and every pip_i are identified. Part (a) is the key fact: compliance carries no information about value, however many sessions are observed. Testing an instruction alone measures θig(ai) _ig(a_i), but not what the instruction takes from the others. Separating the load aia_i from θi _i needs two files that differ in i and a known load for the smaller one; the tied-loads condition supplies that load. Harm flags, unlike compliance, carry the sign of value in the typed case (d). One instruction played both in and out of the file calibrates the sightings of all the others (e). Proof of Theorem C.5. (a) If pi>0p_i>0, the observable rates give qi(St)=piqi(St)/piq_i(S_t)=p_iq_i(S_t)/p_i. Conversely the rates involve q only through the played pairs, so two compliance functions that agree there give the same law. The compliance data (ξi,t,Fi,t)( _i,t,F_i,t) have the product law with parameters (pi,qi(St))(p_i,q_i(S_t)), which depend only on (p,q)(p,q). Given ϖ , let ϖ′ keep (p,q,η,δ)(p,q,η,δ) and set hi′=0h_i =0, ri+⁣′=1r_i^+ =1, ri−⁣′=0r_i^- =0 and, for j≠ij≠ i, hj′=1h_j =1, rj+⁣′=0r_j^+ =0, rj−⁣′=1r_j^- =1; then ri′=1>0>−1=rj′r_i =1>0>-1=r_j , and ϖ,ϖ′ , have the same compliance law; swapping the roles gives a ϖ′ with ri′<0r_i <0. A test based on compliance data has the same rejection probability under ϖ and under a ϖ′ of the opposite sign, so its power equals its size. (b) By (a), qi(i)=θig(ai)q_i(\i\)= _ig(a_i) is identified. If only singleton files are played, item i enters the observable rates only through θig(ai) _ig(a_i); for any a′>0a >0 the pair (θig(ai)/g⁡(a′),a′)( _ig(a_i)/g(a ),\,a ) gives the same value, satisfies the requirement θ′g(a′)=θig(ai)<1θ g(a )= _ig(a_i)<1, and changes no other rate, so neither θi _i nor aia_i is identified. Within a played file S∋i,jS i,j with pi,pj>0p_i,p_j>0, qi(S)/qj(S)=θi/θjq_i(S)/q_j(S)= _i/ _j by (2). (c) By (a), qk(S)q_k(S) and qk(S∪i)q_k(S∪\i\) are identified, and their ratio is g⁡(A⁡(S)+ai)/g⁡(A⁡(S))g(A(S)+a_i)/g(A(S)). Given A⁡(S)A(S), the injectivity condition in (c) makes aia_i the unique solution. Under the stated condition every qj(S)q_j(S), j∈Sj∈ S, is identified, hence Q⁡(S)=∑j∈Sλajg(A⁡(S))=λG(A⁡(S))Q(S)= _j∈ Sλ a_jg(A(S))=λ G(A(S)) with G⁡(x)=xg(x)G(x)=xg(x), and A⁡(S)A(S) is the unique preimage of Q⁡(S)/λQ(S)/λ on the known interval. (d) If piqi(St)>0p_iq_i(S_t)>0, the observable rates give ηhiη h_i, hence hi>01\h_i>0\ as η>0η>0. In the typed case hi∈0,1h_i∈\0,1\ is read off, and sign⁡(ri)=+1 (r_i)=+1 if hi=0h_i=0 and −1-1 if hi=1h_i=1, since ri±>0r_i^±>0. In general, ri=ri+(1−hi(1+λi))r_i=r_i^+(1-h_i(1+ _i)) with λi=ri−/ri+ _i=r_i^-/r_i^+ when ri+>0r_i^+>0; the observation law does not depend on (r+,r−)(r^+,r^-), and for hi∈(0,1)h_i∈(0,1) the map λ↦1−hi(1+λ)λ 1-h_i(1+λ) takes both signs on [0,∞)[0,∞), so choosing ri+=1r_i^+=1 and λi _i on either side of (1−hi)/hi(1-h_i)/h_i gives two parameter vectors with the same law and opposite signs. Since no observable rate involves (r+,r−)(r^+,r^-), |ri||r_i| is not identified. (e) For an item never played, the only observations involving it are the Γi,t _i,t, i.i.d. Bern⁡(δipi)Bern( _ip_i), and no observable rate of another item involves (δi,pi)( _i,p_i); so the law depends on (δi,pi)( _i,p_i) only through the product, and scaling δi _i by c and pip_i by 1/c1/c, for c near 11, leaves it unchanged. With common δ and a bridge item j0j_0, the session with j0∈Stj_0∈ S_t identifies pj0p_j_0 (rate pj0p_j_0), the session with j0∉Stj_0∉ S_t identifies δpj0δ p_j_0, so δ=δpj0/pj0δ=δ p_j_0/p_j_0; then every out-of-file pi=δpi/δp_i=δ p_i/δ, and every in-file pip_i is an observable rate. ∎ C.3 Deletion and the need for magnitudes Proof of Proposition 3. Instance and claims. Take q1(S)=0.1q_1(S)=0.1, q2(S)=0.8q_2(S)=0.8, q1(1)=1/2q_1(\1\)=1/2, q2(2)=8/9q_2(\2\)=8/9, p1=p2=1/2p_1=p_2=1/2, κc1=κc2=0.001κ c_1=κ c_2=0.001, r1=1r_1=1 and r2=±0.05r_2=± 0.05, so that R⁡(1)=0.249>R⁡(2)∈0.021,−0.023R(\1\)=0.249>R(\2\)∈\0.021,-0.023\. We show: with empirical non-compliance over each instruction’s first n relevant sessions, the policy that deletes the most-ignored instruction, and the policy that deletes every instruction above a threshold t0∈(0.2,0.9)t_0∈(0.2,0.9), both delete instruction 1 and keep instruction 2 with probability tending to one as n→∞n→∞; with r2=−0.05r_2=-0.05 they leave a file worth less than the empty one; and in the typed case with r2=−0.05r_2=-0.05, the policy that deletes at the first harm flag never deletes instruction 1 and deletes instruction 2 within n′n sessions with probability 1−(1−0.4η)n′1-(1-0.4η)^n . Law of the decision. By Theorem C.5(a) the compliance data of the first t sessions have the same law under all parameter vectors with the same (p,q)(p,q), so a measurable function of them has the same law. The ϖ′ of that proof has ri′>0r_i >0 and rj′<0r_j <0 for j≠ij≠ i. The instance satisfies (2): with g⁡(x)=1/(1+x)g(x)=1/(1+x) and θ=a=(1,8)θ=a=(1,8), q1(1)=1/2q_1(\1\)=1/2, q2(2)=8/9q_2(\2\)=8/9, q1(S)=1/10q_1(S)=1/10, q2(S)=8/10q_2(S)=8/10, and θ2g(a2)=8/9<1 _2g(a_2)=8/9<1. Its values are R⁡(1,2)=0.05±0.02−0.002R(\1,2\)=0.05± 0.02-0.002, R⁡(1)=0.5⋅0.5−0.001=0.249R(\1\)=0.5· 0.5-0.001=0.249 and R(2)=±0.05⋅0.5⋅8/9−0.001∈0.021,−0.023R(\2\)=± 0.05· 0.5· 8/9-0.001∈\0.021,-0.023\. Under Assumption C.1 the latent compliance draws (Fi,t)t(F_i,t)_t of item i are i.i.d. Bern(qi(S))Bern(q_i(S)) and independent of its relevance draws (ξi,t)t( _i,t)_t, so conditional on the relevance process, the draws at the first n relevant sessions are i.i.d. Bern(qi(S))Bern(q_i(S)) (each item reaches n relevant sessions almost surely since pi>0p_i>0), and Hoeffding’s inequality gives, for the empirical compliance q^i q_i over those sessions, Pr⁡(q^i≥qi(S)+ϵ)≤e−2nϵ2 ( q_i≥ q_i(S)+ε)≤ e^-2nε^2 and Pr⁡(q^i≤qi(S)−ϵ)≤e−2nϵ2 ( q_i≤ q_i(S)-ε)≤ e^-2nε^2. The argmax policy keeps item 1 only if q^1≥q^2 q_1≥ q_2, which requires q^1≥0.45 q_1≥ 0.45 or q^2≤0.45 q_2≤ 0.45, each of probability at most e−2n(0.35)2e^-2n(0.35)^2; so it deletes item 1 and keeps item 2 with probability at least 1−2e−2n(0.35)2→11-2e^-2n(0.35)^2→ 1. The threshold policy keeps item 1 iff q^1≥1−t0=0.1+(0.9−t0) q_1≥ 1-t_0=0.1+(0.9-t_0), of probability at most e−2n(0.9−t0)2e^-2n(0.9-t_0)^2, and deletes item 2 iff q^2<1−t0=0.8−(t0−0.2) q_2<1-t_0=0.8-(t_0-0.2), of probability at most e−2n(t0−0.2)2e^-2n(t_0-0.2)^2; both tend to 00. With r2=−0.05r_2=-0.05 both policies end at 2\2\ with probability tending to 11, and R⁡(2)=−0.023<0=R⁡(∅)R(\2\)=-0.023<0=R( ). For the harm-triggered policy in the typed case with h1=0h_1=0, h2=1h_2=1: item 1 is never flagged, since ζ1,t=0 _1,t=0; item 2 is flagged in a session with S=1,2S=\1,2\ with probability p2q2(S)η=0.4ηp_2q_2(S)η=0.4η, independently across sessions, so it is deleted within n′n sessions with probability 1−(1−0.4η)n′1-(1-0.4η)^n . ∎ The next result is the reason Section 4.4 assumes magnitude feedback. Its setting is that of Section 4.4: a policy is a probability kernel from the history of files and observations to the next file, and given the history through session t−1t-1 and StS_t, the latent draws of session t are independent of the past and follow Assumption C.1 with file StS_t. Proposition C.6 (Magnitudes are necessary). Assumption C.1, one candidate (N=1N=1), κ>0κ>0, c1>0c_1>0, B≥c1B≥ c_1, p1q1(1)>0p_1q_1(\1\)>0. There are parameter vectors ϖ,ϖ′ , with the same observation law such that ∅ is optimal under ϖ with margin Δ=Rϖ(∅)−Rϖ(1)>0 =R_ ( )-R_ (\1\)>0, 1\1\ is optimal under ϖ′ with margin Δ′=Rϖ′(1)−Rϖ′(∅)>0 =R_ (\1\)-R_ ( )>0, and every policy and every horizon T have max⁡(RegT(ϖ),RegT(ϖ′))≥Tmin⁡(Δ,Δ′)/2 (Reg_T( ),Reg_T( ))≥ T ( , )/2. Proof. Take the typed helpful case (h1=0h_1=0) and two gains rlo<κc1/(p1q1(1))<rhir_lo<κ c_1/(p_1q_1(\1\))<r_hi; let ϖ have r1+=rlor_1^+=r_lo and ϖ′ have r1+=rhir_1^+=r_hi, all else equal. No observation depends on r1+r_1^+, so the two observation laws coincide, and a policy induces the same law of (St)t≤T(S_t)_t≤ T under both; in particular T1=∑t≤TSt=1T_1=E _t≤ T1\S_t=\1\\ is the same. Under ϖ , R⁡(1)=−Δ<0=R⁡(∅)R(\1\)=- <0=R( ) with Δ=κc1−p1q1(1)rlo>0 =κ c_1-p_1q_1(\1\)r_lo>0, so S⋆=∅S = and RegT(ϖ)=ΔT1Reg_T( )= T_1. Under ϖ′ , R⁡(1)=Δ′>0R(\1\)= >0 with Δ′=p1q1(1)rhi−κc1 =p_1q_1(\1\)r_hi-κ c_1, so S⋆=1S =\1\ (feasible as B≥c1B≥ c_1) and RegT(ϖ′)=Δ′(T−T1)Reg_T( )= (T-T_1). The larger of the two is at least their average, (ΔT1+Δ′(T−T1))/2≥min⁡(Δ,Δ′)T/2( T_1+ (T-T_1))/2≥ ( , )T/2. ∎ C.4 Admission The admission policy of Section 4.3 admits at τk=inft≥1:∑s=t−W+1tYs≥k _k= \t≥ 1: _s=t-W+1^tY_s≥ k\, with Ys=0Y_s=0 for s≤0s≤ 0. Lemma C.7 (Binomial tail). Pr⁡(Bin⁡(n,y)≥j)≤(nj)yj≤(ny)j/j! (Bin(n,y)≥ j)≤ njy^j≤(ny)^j/j!. Proof. If at least j of n independent trials succeed, some j-subset of the trials succeeds entirely; a union bound over the (nj) nj subsets gives the first inequality, and (nj)≤nj/j! nj≤ n^j/j! the second. ∎ Lemma C.8 (False inclusion). Under Assumption C.2 with rate ε , k≥1k≥ 1, W≥1W≥ 1: (1) PFI(1)=1−(1−ε)TP_FI(1)=1-(1- )^T; (2) PFI(k)≤TεPr⁡(Bin⁡(W−1,ε)≥k−1)≤Tε(W−1k−1)εk−1≤Tε((W−1)ε)k−1/(k−1)!P_FI(k)≤ T (Bin(W-1, )≥ k-1)≤ T W-1k-1 ^k-1≤ T ((W-1) )^k-1/(k-1)!. Proof. (1) τ1 _1 is the first sighting. (2) The event τk=t _k=t requires Yt=1Y_t=1 and at least k−1k-1 sightings among the at most W−1W-1 sessions t−W+1,…,t−1t-W+1,…,t-1, whose count is independent of YtY_t and stochastically at most Bin⁡(W−1,ε)Bin(W-1, ); so Pr⁡(τk=t)≤εPr⁡(Bin⁡(W−1,ε)≥k−1) ( _k=t)≤ (Bin(W-1, )≥ k-1). A union bound over t≤Tt≤ T and Lemma C.7 finish. ∎ Lemma C.9 (Delay). Under Assumption C.2 with rate π∈(0,1]π∈(0,1]: (1) τk≥k/πE _k≥ k/π for all k,Wk,W; (2) for W≥2W≥ 2, τ2=1π(1+1/ψW)E _2= 1π(1+1/ _W) with ψW=1−(1−π)W−1 _W=1-(1-π)^W-1; and τ1=1/πE _1=1/π. Proof. (1) The policy cannot fire before the k-th sighting, whose time is a sum of k i.i.d. Geom⁡(π)Geom(π) waiting times with mean k/πk/π. (2) Let Z1,Z2,…Z_1,Z_2,… be the i.i.d. Geom⁡(π)Geom(π) times between sightings (Z1Z_1 is the first sighting time). The window count changes only at sightings, and at the j-th sighting the window holds two sightings iff Zj≤W−1Z_j≤ W-1. So the policy fires at the j∗j^*-th sighting, j∗=min⁡j≥2:Zj≤W−1j^*= \j≥ 2:Z_j≤ W-1\, and τ2=Z1+⋯+Zj∗ _2=Z_1+…+Z_j^*. Here j∗−1∼Geom⁡(ψW)j^*-1 ( _W) with ψW=Pr⁡(Z≤W−1) _W= (Z≤ W-1), and j∗j^* is a stopping time for (Zj)j≥2(Z_j)_j≥ 2 with finite mean, so Wald’s identity gives τ2=Z1+⁡[j∗−1]Z=1/π+1/(ψWπ)E _2=EZ_1+E[j^*-1]\,EZ=1/π+1/( _Wπ). Finally τ1=Z1 _1=Z_1. ∎ Proof of Theorem 1. Write βε=1−(1−ε)W−1 _ =1-(1- )^W-1 for the chance that a spurious sighting has another inside its window. We first show that k=2k=2 is the unique minimizer under the two conditions (A) ΛF[1−(1−ε)T−Tεβε]>ΛD/ψW, _F [1-(1- )^T-T \, _ ]> _D/ _W, (B) ΛFTεβε<ΛD(2−1/ψW), _F\,T \, _ < _D(2-1/ _W), which need only ε∈[0,1] ∈[0,1] and ΛF≥0 _F≥ 0, and then that the band implies them. By Lemmas C.8(1) and C.9, ℒ⁡(1)=ΛF(1−(1−ε)T)+ΛDL(1)= _F(1-(1- )^T)+ _D. By Lemma C.8(2) with Pr⁡(Bin⁡(W−1,ε)≥1)=βε (Bin(W-1, )≥ 1)= _ and Lemma C.9(2), ℒ⁡(2)≤ΛFTεβε+ΛD(1+1/ψW)L(2)≤ _FT \, _ + _D(1+1/ _W). By Lemma C.9(1), ℒ⁡(k)≥ΛDk≥3ΛDL(k)≥ _Dk≥ 3 _D for k≥3k≥ 3. Condition (A) says exactly that the bound on ℒ⁡(2)L(2) is below ℒ⁡(1)L(1), and (B) that it is below 3ΛD3 _D; so ℒ⁡(2)<ℒ⁡(k)L(2)<L(k) for every k≠2k≠ 2, k≥1k≥ 1. For the band, use (1−ε)T≤e−xT(1- )^T≤ e^-x_T and βε≤(W−1)ε≤x _ ≤(W-1) ≤ x: (A) follows from ΛF(1−e−xT−xTx)>ΛD/ψW _F(1-e^-x_T-x_Tx)> _D/ _W, and (B) from ΛFxTx<ΛD(2−1/ψW) _Fx_Tx< _D(2-1/ _W). Dividing by ΛFεT>0 _F T>0, the second is x<ω⁡(2−1/ψW)x<ω(2-1/ _W), and the first follows from 1−e−xT≥xT−xT2/21-e^-x_T≥ x_T-x_T^2/2 and 1−xT/2−x>ω/ψW1-x_T/2-x>ω/ _W. ∎ In the regime Wπ≫kWπ k the delay is about k/πk/π. When false inclusion is rare, Lemma C.8(2) bounds PFI(k)P_FI(k) by about TWxk(k−1)! TW x^k(k-1)!, and counting only the T/WT/W disjoint windows gives the lower estimate TWxkk! TW x^kk!, a factor k smaller. C.5 Regret under an edit cap Constants. Let cmax=maxi⁡cic_ = _ic_i, s=min⁡(⌊m/2⌋,⌊B/cmax⌋)≥1s= ( m/2 , B/c_ )≥ 1 and J=⌈N/s⌉J= N/s . Let G¯=supx≥0G⁡(x) G= _x≥ 0G(x) and B′=min⁡(B,λG¯/κ)B = (B,λ G/κ), read as B when G¯=∞ G=∞; by Proposition A.1(i), (iv) with χ=λχ=λ and w¯≤1 w≤ 1, some optimal file has C⁡(S⋆)≤B′C(S )≤ B . Let ′=S⊆[N]:C⁡(S)≤B′S =\S [N]:C(S)≤ B \ and nB=max⁡|S|:S∈′n_B= \|S|:S \. With xs=samaxx_s=sa_ and xB=nBamaxx_B=n_Ba_ , put gs=g⁡(xs)g_s=g(x_s), L1/g=maxx∈[0,xs]⁡|g′(x)|g(x)2,Kg=supx≠y∈[0,xB]x|g⁡(x)−g⁡(y)||x−y|≤xBmax[0,xB]|g′|,L_1/g= _x∈[0,x_s] |g (x)|g(x)^2, K_g= _x≠ y∈[0,x_B] x\,|g(x)-g(y)||x-y|\ ≤\ x_B _[0,x_B]|g |, so that 1/g1/g is L1/gL_1/g-Lipschitz on [0,xs][0,x_s]. Finally ϵ0=ln⁡(6NT)/(n0pmin) _0= (6NT)/(n_0p_ ) and εSD(n0)=ϵ0[2+Kggs+(1+Kg)L1/gsλγs]. _SD(n_0)= _0 [ 2+K_gg_s+ (1+K_g)\,L_1/g\,sλ _s ]. ETC-m. Fix an exploration length n0n_0, in sessions per batch. Partition [N][N] into batches 1,…,JJ_1,…,J_J of at most s items. For j=1,…,Jj=1,…,J, play jJ_j for ⌈n0/L⌉ n_0/L epochs, switching at the first session of an epoch (≤2s≤m≤ 2s≤ m edits); let IjI_j be the set of sessions in which jJ_j is played, |Ij|=n≥n0|I_j|=n≥ n_0. For i∈ji _j let q^i q_i be its empirical compliance over its relevant sessions in IjI_j and Y¯i Y_i the mean over IjI_j of Yi,t=ξi,tFi,tXi,tY_i,t= _i,tF_i,tX_i,t. Estimate the batch load and the item parameters by A^j=G−1(clip[0,G⁡(xs)](1λ∑l∈jq^l)),a^i=clip[0,amax](q^iλg(A^j)),β^i=Y¯ig⁡(A^j), A_j=G^-1 (clip_[0,G(x_s)] ( 1λ _l _j q_l ) ), a_i=clip_[0,a_ ] ( q_iλ\,g( A_j) ), β_i= Y_ig( A_j), where G−1G^-1 is the inverse of G on [0,xs][0,x_s]. For S∈′S let A^(S)=∑i∈Sa^i A(S)= _i∈ S a_i and R^(S)=g⁡(A^(S))∑i∈Sβ^i−κC(S). R(S)=g( A(S)) _i∈ S β_i-κ C(S). Let S S maximize R R over ′S . Move from JJ_J to S S, removals first, m edits per epoch at the first session of each epoch, and play S S thereafter. The targets of the estimator are βi=wiθi=λwiai _i=w_i _i=λ w_ia_i and R⁡(S)=g⁡(A⁡(S))∑i∈Sβi−κC(S)R(S)=g(A(S)) _i∈ S _i-κ C(S), which is (1) under (2). Lemma C.10 (Batch errors). Assumptions C.3 and C.4. Let 0G_0 be the event that for every i∈[N]i∈[N], with j the batch of i: (G1) Ni=∑t∈Ijξi,t≥npi/2N_i= _t∈ I_j _i,t≥ np_i/2; (G2) |q^i−qi(j)|≤ϵ0| q_i-q_i(J_j)|≤ _0; (G3) |Y¯i−Yi|≤2ϵ0| Y_i-EY_i|≤ 2 _0, where Yi=wiqi(j)=βig(A⁡(j))EY_i=w_iq_i(J_j)= _ig(A(J_j)). If n0≥8ln⁡(6NT)/pminn_0≥ 8 (6NT)/p_ , then Pr⁡(0c)≤5/(6T) (G_0^c)≤ 5/(6T), and on 0G_0, for every j and i∈ji _j, |A^j−A(j)|≤sϵ0λγs=:ϵA,|a^i−ai|≤ϵ0λgs+L1/gλϵA=:ϵa,|β^i−βi|≤2ϵ0gs+L1/gϵA=:ϵβ.| A_j-A(J_j)|≤ s _0λ _s=: _A, | a_i-a_i|≤ _0λ g_s+ L_1/gλ _A=: _a, | β_i- _i|≤ 2 _0g_s+L_1/g\, _A=: _β. Proof. Probability. The exploration schedule is fixed in advance, so for i∈ji _j the latent draws (ξi,t,Fi,t,Xi,t)t∈Ij( _i,t,F_i,t,X_i,t)_t∈ I_j are i.i.d. across t by Assumption C.1, and Xi,tX_i,t is independent of (ξi,t,Fi,t)( _i,t,F_i,t) because it depends on the other draws only through ζi,t _i,t, which is independent of them; hence Yi=piqi(j)ri=wiqi(j)EY_i=p_iq_i(J_j)r_i=w_iq_i(J_j). By the multiplicative Chernoff bound, Pr(Ni<npi/2)≤e−npi/8≤e−n0pmin/8≤1/(6NT) (N_i<np_i/2)≤ e^-np_i/8≤ e^-n_0p_ /8≤ 1/(6NT). Conditional on the relevance draws, the compliance draws at the relevant sessions are i.i.d. Bern⁡(qi(j))Bern(q_i(J_j)), so on (G1) Hoeffding’s inequality gives Pr⁡(|q^i−qi(j)|>ϵ0∣ξ)≤2e−2Niϵ02≤2e−npiϵ02≤2e−ln⁡(6NT)=1/(3NT) (| q_i-q_i(J_j)|> _0 ξ)≤ 2e^-2N_i _0^2≤ 2e^-np_i _0^2≤ 2e^- (6NT)=1/(3NT). The Yi,tY_i,t are i.i.d. in [−1,1][-1,1], so Hoeffding’s inequality gives Pr⁡(|Y¯i−Yi|>2ϵ0)≤2e−2nϵ02≤1/(3NT) (| Y_i-EY_i|>2 _0)≤ 2e^-2n _0^2≤ 1/(3NT). A union bound over the N items gives Pr⁡(0c)≤N⁡(1/(6NT)+2/(3NT))=5/(6T) (G_0^c)≤ N(1/(6NT)+2/(3NT))=5/(6T). Load. Write Aj=A⁡(j)≤xsA_j=A(J_j)≤ x_s and Qj=Q⁡(j)=λG(Aj)Q_j=Q(J_j)=λ G(A_j), so Qj/λ∈[0,G⁡(xs)]Q_j/λ∈[0,G(x_s)]. By (G2), |∑lq^l/λ−Qj/λ|≤sϵ0/λ| _l q_l/λ-Q_j/λ|≤ s _0/λ, and clipping to [0,G⁡(xs)][0,G(x_s)], which contains Qj/λQ_j/λ, does not increase the distance. On [0,xs][0,x_s], G′≥γs>0G ≥ _s>0, so G is increasing there and G−1G^-1 is 1/γs1/ _s-Lipschitz on [0,G⁡(xs)][0,G(x_s)]; hence |A^j−Aj|≤ϵA| A_j-A_j|≤ _A. Items. Since A^j,Aj∈[0,xs] A_j,A_j∈[0,x_s], g⁡(A^j)≥gsg( A_j)≥ g_s and |1/g⁡(A^j)−1/g⁡(Aj)|≤L1/gϵA|1/g( A_j)-1/g(A_j)|≤ L_1/g _A. With qi=qi(j)=λaig(Aj)≤1q_i=q_i(J_j)=λ a_ig(A_j)≤ 1, q^iλg(A^j)−ai=q^i−qiλg(A^j)+qiλ(1g⁡(A^j)−1g⁡(Aj)), q_iλ g( A_j)-a_i= q_i-q_iλ g( A_j)+ q_iλ ( 1g( A_j)- 1g(A_j) ), of absolute value at most ϵa _a; clipping to [0,amax]∋ai[0,a_ ] a_i does not increase the error. Likewise, with |Yi|≤1|EY_i|≤ 1, β^i−βi=(Y¯i−Yi)/g⁡(A^j)+Yi(1/g⁡(A^j)−1/g⁡(Aj)) β_i- _i=( Y_i-EY_i)/g( A_j)+EY_i\,(1/g( A_j)-1/g(A_j)), of absolute value at most ϵβ _β. ∎ Lemma C.11 (Plug-in stability). Assumptions C.3 and C.4. On 0G_0, every S⊆[N]S [N] with |S|≤nB|S|≤ n_B satisfies |R^(S)−R⁡(S)|≤|S|εSD(n0)| R(S)-R(S)|≤|S|\, _SD(n_0). Proof. Both A⁡(S)=∑SaiA(S)= _Sa_i and A^(S)=∑Sa^i A(S)= _S a_i lie in [0,xB][0,x_B], and |A^(S)−A⁡(S)|≤|S|ϵa| A(S)-A(S)|≤|S| _a by Lemma C.10. Decompose R^(S)−R⁡(S)=g⁡(A^(S))∑i∈S(β^i−βi)+(g⁡(A^(S))−g⁡(A⁡(S)))∑i∈Sβi. R(S)-R(S)=g( A(S)) _i∈ S( β_i- _i)+ (g( A(S))-g(A(S)) ) _i∈ S _i. The first term is at most |S|ϵβ|S| _β in absolute value, as g≤1g≤ 1. For the second, |∑Sβi|≤λ∑S|wi|ai≤λA(S)| _S _i|≤λ _S|w_i|a_i≤λ A(S), and by the definition of KgK_g, A⁡(S)|g⁡(A^(S))−g⁡(A⁡(S))|≤Kg|A^(S)−A⁡(S)|≤Kg|S|ϵaA(S)\,|g( A(S))-g(A(S))|≤ K_g| A(S)-A(S)|≤ K_g|S| _a. So |R^(S)−R⁡(S)|≤|S|(ϵβ+λKgϵa)| R(S)-R(S)|≤|S|( _β+λ K_g _a), and ϵβ+λKgϵa=εSD(n0) _β+λ K_g _a= _SD(n_0) by the definitions of ϵa _a, ϵβ _β and ϵA _A. ∎ The factor A⁡(S)A(S) in front of the difference of g is what keeps the commit error linear in nBn_B: a per-item bound on |q^i(S)−qi(S)|| q_i(S)-q_i(S)| would carry nBn_B once more through A^(S) A(S). Theorem C.12 (ETC-m under an edit cap, full form). Assumptions C.1, C.3 and C.4; m≥2m≥ 2, B≥cmaxB≥ c_ , ci>0c_i>0, κ>0κ>0, N,L,T≥1N,L,T≥ 1. If n0≥8ln⁡(6NT)/pminn_0≥ 8 (6NT)/p_ , then RegT≤ΔmaxL(J+⌈s+nBm⌉)+ΛT(n0),ΛT(n0)=ΔmaxJn0+2nBTεSD(n0)+Δmax.Reg_T≤ _ L (J+ s+n_Bm )+ _T(n_0), _T(n_0)= _ Jn_0+2n_BT\, _SD(n_0)+ _ . Proof. Feasibility. A batch costs at most scmax≤Bsc_ ≤ B, the sets played during the move are subsets of the last batch or of S S, and C⁡(S^)≤B′≤BC( S)≤ B ≤ B; so every played file is feasible and every session’s expected regret is at most Δmax _ . A batch switch uses at most 2s≤m2s≤ m edits and each epoch of the move at most m. Step 1 (decomposition). Exploration lasts JL⌈n0/L⌉<J⁡(n0+L)JL n_0/L <J(n_0+L) sessions and the move L⁡⌈(s+nB)/m⌉L (s+n_B)/m sessions, in all at most Δmax[L⁡(J+⌈(s+nB)/m⌉)+Jn0] _ [L(J+ (s+n_B)/m )+Jn_0] regret. Every later session costs R⁡(S⋆)−R⁡(S^)R(S )-R( S). Step 2 (commit error). Some optimal file lies in ′S and every S∈′S has |S|≤nB|S|≤ n_B. On 0G_0, Lemma C.11 gives |R^(S)−R⁡(S)|≤nBεSD(n0)| R(S)-R(S)|≤ n_B _SD(n_0) for all S∈′S , so R⁡(S⋆)−R⁡(S^)≤[R⁡(S⋆)−R^(S⋆)]+[R^(S⋆)−R^(S^)]+[R^(S^)−R⁡(S^)]≤2nBεSD(n0)R(S )-R( S)≤[R(S )- R(S )]+[ R(S )- R( S)]+[ R( S)-R( S)]≤ 2n_B _SD(n_0), the middle bracket being ≤0≤ 0 by the choice of S S. Step 3 (expectation). The commit phase lasts at most T sessions, so its regret is at most 2nBTεSD(n0)2n_BT _SD(n_0) on 0G_0 and at most TΔmaxT _ off 0G_0, whose probability is at most 5/(6T)≤1/T5/(6T)≤ 1/T by Lemma C.10; in expectation this adds at most Δmax _ . Summing with Step 1 gives the bound. ∎ Corollary C.13 (Tuned exploration). In the setting of Theorem C.12, let nmin=⌈8ln⁡(6NT)/pmin⌉n_ = 8 (6NT)/p_ , C1=2nB[(2+Kg)/gs+(1+Kg)L1/gs/(λγs)]ln⁡(6NT)/pminC_1=2n_B [(2+K_g)/g_s+(1+K_g)L_1/g\,s/(λ _s) ] (6NT)/p_ , so that 2nBεSD(n0)=C1n0−1/22n_B _SD(n_0)=C_1n_0^-1/2, and n0=max⁡nmin,⌈(TC1/(2JΔmax))2/3⌉n_0= \n_ , (TC_1/(2J _ ))^2/3 \, reading y/0=0y/0=0. Then ΛT(n0)≤1.9(JΔmax)1/3(C1T)2/3+JΔmax(nmin+1)+Δmax. _T(n_0)≤ 1.9\,(J _ )^1/3(C_1T)^2/3+J _ (n_ +1)+ _ . Proof. If Δmax=0 _ =0 then RegT≤TΔmax=0Reg_T≤ T _ =0 and there is nothing to prove. Otherwise the first two terms of ΛT(n0) _T(n_0) are n0+n0−1/2 an_0+ bn_0^-1/2 with =JΔmax a=J _ and =C1T b=C_1T; put n∗=(/(2))2/3n^*=( b/(2 a))^2/3, so n∗=2−2/31/32/3 an^*=2^-2/3 a^1/3 b^2/3 and (n∗)−1/2=21/31/32/3 b(n^*)^-1/2=2^1/3 a^1/3 b^2/3. If n0=⌈n∗⌉≥nminn_0= n^* ≥ n_ , then n0+n0−1/2≤(n∗+1)+(n∗)−1/2=3⋅2−2/31/32/3+≤1.91/32/3+ an_0+ bn_0^-1/2≤ a(n^*+1)+ b(n^*)^-1/2=3· 2^-2/3 a^1/3 b^2/3+ a≤ 1.9\, a^1/3 b^2/3+ a. If n0=nmin>n∗n_0=n_ >n^*, then n0=nmin an_0= an_ and n0−1/2<(n∗)−1/2≤1.91/32/3 bn_0^-1/2< b(n^*)^-1/2≤ 1.9\, a^1/3 b^2/3. In both cases the two terms are at most 1.91/32/3+⁡(nmin+1)1.9\, a^1/3 b^2/3+ a(n_ +1). ∎ The tuning uses Δmax _ , which the curator does not know. Tuning with any known Δ¯≥Δmax ≥ _ in its place, for instance Δ¯=nB+κB =n_B+κ B (as |wi|≤1|w_i|≤ 1 and qi≤1q_i≤ 1), gives the same bound with Δ¯ in place of Δmax _ in the first two terms, by the same proof with ≤JΔ¯ a≤ J . Proof of Theorem 2. The hypotheses of Theorem 2 are those of Theorem C.12, with nBn_B the largest size of a file in ′S , so the bound is Theorem C.12. Under the tuning of Corollary C.13, C1C_1 is O⁡(ln⁡(NT))O( (NT)) and nminn_ is O⁡(ln⁡(NT))O( (NT)) with the other parameters fixed, so ΛT=O⁡(T2/3(ln⁡NT)1/3) _T=O(T^2/3( NT)^1/3). For the edit-cap term, if m≤2B/cmaxm≤ 2B/c_ then s=⌊m/2⌋≥m/3s= m/2 ≥ m/3, so J≤3N/m+1J≤ 3N/m+1, and nB≤Nn_B≤ N gives ⌈(s+nB)/m⌉≤N/m+2 (s+n_B)/m ≤ N/m+2; hence the term is at most ΔmaxL(4N/m+3) _ L(4N/m+3). ∎ Proof of Theorem 3. Instance. Fix c∈(0,B]c∈(0,B], p∈(0,1]p∈(0,1], θ>0θ>0 and a>0a>0 with θg(a)<1θ g(a)<1 and κc<pθg(a)κ c<pθ g(a); such values exist since c may be taken small. All items share c, p, θi=θ _i=θ and ai=a_i=a; harm hi=0h_i=0; gap detection δ; under instance j the gains are rj=1r_j=1 and ri=0r_i=0 for i≠ji≠ j, observed without noise (Xi,t≡riX_i,t≡ r_i). Then R(S)=pθg(|S|a) 1j∈S−κc|S|R(S)=p\,θ\,g(|S|a)\,1\j∈ S\-κ c|S|. If j∈Sj∈ S this is at most pθg(a)−κc=R⁡(j)pθ g(a)-κ c=R(\j\), as g is nonincreasing, and if j∉Sj∉ S it is −κc|S|≤0<R⁡(j)-κ c|S|≤ 0<R(\j\). So Sj⋆=jS _j=\j\, and R⁡(Sj⋆)−R⁡(St)≥ΔR(S _j)-R(S_t)≥ whenever j∉Stj∉ S_t; also R⁡(S)≥−κC(S)≥−κBR(S)≥-κ C(S)≥-κ B for feasible S, so Δmax≤Δ+κB _ ≤ +κ B. Reduction. Let instance 00 have ri=0r_i=0 for all i. For a file S∌jS j, the observation law of a session with file S is the same under instance j and instance 00: in-file items have the same compliance θg(|S|a)θ g(|S|a) and the same gain 00 under both, and j contributes only Gj,t∼Bern⁡(δp)G_j,t (δ p). This holds for every joint law of the flags within a session, since the flag laws do not depend on the gains. Let σj=min⁡t:j∈St _j= \t:j∈ S_t\ be the first session that tries j. The law of a history (S1,O1,…,St,Ot)(S_1,O_1,…,S_t,O_t) is the product of the policy kernels ⁡(Ss∣past) P(S_s ) and the session laws ⁡(Os∣Ss) K(O_s S_s); on the event σj>t\ _j>t\ every factor agrees under instances j and 00, so Prj⁡(σj>t)=Pr0⁡(σj>t) _j( _j>t)= _0( _j>t). Counting. From S0=∅S_0= with at most m additions per epoch, |⋃s≤tSs|≤∑s≤t|Ss∖Ss−1|≤me(t)| _s≤ tS_s|≤ _s≤ t|S_s S_s-1|≤ m\,e(t) almost surely, so ∑jPr0⁡(σj≤t)≤0|⋃s≤tSs|≤me(t) _j _0( _j≤ t) _0| _s≤ tS_s|≤ m\,e(t), and ∑jPrj⁡(j∉St)≥∑jPr0⁡(σj>t)≥N−me(t) _j _j(j∉ S_t)≥ _j _0( _j>t)≥ N-m\,e(t). Summing. RegT(j)≥Δ∑t≤TPrj⁡(j∉St)Reg_T(j)≥ _t≤ T _j(j∉ S_t), so, using T≥LnmT≥ Ln_m and N−me≥0N-me≥ 0 for e≤nme≤ n_m, ∑jRegT(j)≥Δ∑e=1nmL⁡(N−me)=ΔL(Nnm−mnm(nm+1)2)≥ΔLN⁡(nm−1)2, _jReg_T(j)≥ _e=1^n_mL(N-me)= L (Nn_m- mn_m(n_m+1)2 )≥ L\, N(n_m-1)2, because mnm≤Nmn_m≤ N. The maximum over j is at least the average, (ΔL/2)(nm−1)( L/2)(n_m-1). For N≥4mN≥ 4m, nm−1>N/m−2≥N/(2m)n_m-1>N/m-2≥ N/(2m). ∎ Appendix D EXPERIMENTAL DETAILS The plan of each experiment is paraphrased below, and every deviation from the plan is listed. Model calls go to hosted Claude models through their command-line client; the context file is the whole system prompt, with no tools and prompt caching off. Intervals are 95% percentile intervals of a task-cluster bootstrap with 2,000 replicates unless stated. D.1 Size sweep Purpose. Proposition 1 bounds the optimal file size independently of the pool, and Corollary 1 says the loss from loading the whole pool grows with the pool. The size sweep grows a pool of real context-file instructions from 200 to 3,200 items and measures value against file size at each pool size, for two models on the same files. Data. Candidates are root context-file list items from a public corpus of coding-agent configuration files (Galster et al.,, 2026) (C BY 4.0 compilation; file contents keep their repository licenses, so only permissive repositories are used and item text stays out of the released data). Tasks are ManyIFEval prompts (Harada et al.,, 2025) (C BY 4.0); verifiers are the IFEval (Zhou et al.,, 2023) and IFBench (Pyatkin et al.,, 2025) checkers (Apache-2.0). The subjects are Claude Haiku 4.5 and Claude Sonnet 5.5. Design. The pool holds 3,200 items drawn from the tier whose verbatim text cannot apply to a reply, in one seeded order: one item per repository for the first 1,901 items and a second item per repository after that. N∈200,800,3200N∈\200,800,3200\ takes prefixes. Every fifth item stays verbatim as a zero-value candidate (640 items). The other 2,560 get a verifier on the item’s rarest word across the corpus (document frequency at most 1%): two thirds use IFEval keywords:existence, one third keywords:frequency with a count of 2 or 3. Every fifth verifiable item is genre-free; the rest carry one of six genre triggers (“When the reply is an email, …”). Claude Sonnet 5.5 rewrites each verifiable item’s body, keeping the original wording; the trigger and the verifier arguments are fixed by code, and a body that lacks the keyword falls back to a template (3 items). Tasks are 60 ManyIFEval prompts that name no genre; the genre is assigned round-robin (ten each) and stated in the user turn with a 900–1,200 word range. The file of size b holds the first b verifiable items of the N pool in a second seeded order, zero-value items last. Files are therefore nested in b, the file b=Nb=N is the whole pool, and n⋆(N)n (N) is the optimum over these nested files. The grid is N∈200,800,3200N∈\200,800,3200\ and b∈5,10,20,40,80,200,400,800,1600,Nb∈\5,10,20,40,80,200,400,800,1600,N\ with b≤Nb≤ N, 60 tasks, 2 replicates that differ in item order: 24 cells and 2,880 runs per model. Both models see the same files. Every run is scored on every verifiable item of its pool that is relevant to its genre, loaded or not. A keyword also appears unprompted. Its chance rate is the share of relevant unloaded verifiers that pass, per model, pool and task, over the files of at most 40 items. It is 0.0450.045, 0.0240.024 and 0.0160.016 at N=200N=200, 800800 and 32003200 for Haiku and within 0.0030.003 of that for Sonnet. Per cell, R0(Sb)R_0(S_b) is the mean number of followed relevant loaded items minus the chance rate times their number. A singleton screen loads an item alone on 6 tasks; qi(i)q_i(\i\) is the mean over them. It covers the 452 items loaded in some file of size at most 200200, once per model (2,712 runs each). The load ℓ⁡(Sb) (S_b) is the sum of the subject’s singleton rates over the relevant loaded items; an unscreened item takes the mean rate of the screened items of its kind and verifier family, which is unbiased because files are seeded prefixes. The mean singleton rate is 0.580.58 for Haiku and 0.800.80 for Sonnet. C⁡(Sb)C(S_b) is the file’s tokens. The marginal relevant compliance between consecutive sizes is MC⁡(b)=[R0(Sb′)−R0(Sb)]/[ℓ⁡(Sb′)−ℓ⁡(Sb)]MC(b)=[R_0(S_b )-R_0(S_b)]/[ (S_b )- (S_b)]. The value at price ρexp _exp is Rρexp(Sb)=R0(Sb)−(ρexp/cmed)C(Sb)R_ _exp(S_b)=R_0(S_b)-( _exp/c_med)C(S_b) with cmed=39c_med=39 tokens, the median verifiable item, so ρexp _exp is the normalized cost per median-length item; it is distinct from the theoretical break-even compliance ρ. From one task-cluster bootstrap we take n⋆(N)=arg⁡maxbRρexp(Sb)n (N)= _bR_ _exp(S_b) and the accretion loss Rρexp(Sn⋆)−Rρexp(SN)R_ _exp(S_n )-R_ _exp(S_N). Details. At b=3200b=3200 the chance hits are about 14 of the 853 relevant loaded items, most of the raw count of followed items (14.3 for Haiku, 18.1 for Sonnet); Tables 2 and 3 give the raw counts next to the corrected ones. The relevant load at b=Nb=N is about 0.27N0.27N items (53, 213, 853). The singleton rate of a genre-free item is pooled over genres. ManyIFEval has too few prompts of each genre, so the genre is assigned and stated in the user turn. The task’s own instruction list is not used. The median item costs 39 tokens after rewriting, against the corpus median of 15. No run was truncated or empty. Results. Tables 2 and 3 give the cells and Table 4 the measured optima. At the top step, b=1600→3200b=1600→ 3200, MCMC is −0.007-0.007 [−0.013,−0.002][-0.013,-0.002] for Haiku and −0.037-0.037 [−0.052,−0.023][-0.052,-0.023] for Sonnet. At N=3200N=3200 gross value peaks at b=200b=200, at 5.05.0 followed instructions for Haiku and 23.823.8 for Sonnet, and falls to 0.60.6 [0.0,1.3][0.0,1.3] and 4.04.0 [0.5,9.5][0.5,9.5] for the whole pool (Figure 1). Without the chance correction the top-step MCMC is 0.0290.029 [0.022,0.035][0.022,0.035] for Haiku and −0.013-0.013 [−0.028,0.001][-0.028,0.001] for Sonnet. Over the three pools the optimum at ρexp=0.1 _exp=0.1 is 1010, 55, 1010 for Haiku and 4040, 2020, 4040 for Sonnet: it does not grow with the pool. From N=800N=800 to N=3200N=3200 the accretion loss grows from 76.276.2 to 316.7316.7 for Haiku and from 75.975.9 to 320.4320.4 for Sonnet, a factor 4.24.2 for each. Sonnet follows about five times as many instructions as Haiku before capacity binds, and its optimal file is four times as large. The curves are not smooth, because unranked files differ in the difficulty of their items. For Sonnet at N=800N=800 gross value is 28.428.4 at b=400b=400 and 3.73.7 for the whole pool, a step of −0.46-0.46 [−0.56,−0.36][-0.56,-0.36]. Loaded items of another genre are followed at 0.020.02–0.050.05. Replies fall inside the word range in 76%76\% of runs for both models. Figure 3 shows the value curves at ρexp=0.1 _exp=0.1 and Figure 4 the marginal compliance against the load. Figures 5 and 6 show the value curves at the other prices: the optimum moves left as ρexp _exp rises, and it sits at b=Nb=N only for Sonnet at N=200N=200 and ρexp=0.05 _exp=0.05. Monotone dilution, item by item. Assumption 1 is a statement about each instruction: its compliance does not rise when the file grows. Files are nested in b within a pool, so every relevant item of SbS_b is in every larger file, and the per-item labels test the assumption directly. For each pool we follow the relevant items of the b=40b=40 file, 12 to 16 per task, through the larger files (Figures 7 and 8). At N=3200N=3200 their compliance falls from 0.270.27 to 0.050.05 for Haiku and from 0.910.91 to 0.050.05 for Sonnet. At N=800N=800 it falls from 0.290.29 to 0.040.04 and from 0.470.47 to 0.070.07, and at N=200N=200 from 0.250.25 to 0.110.11 and from 0.550.55 to 0.310.31. These are raw rates, with the chance rate of 0.020.02–0.050.05 as their floor. Order matters inside large files, which the set-level model does not represent: at b=800b=800 of the largest pool the first fifth of the file is followed about twice as often as the rest by both models (0.050.05 against 0.020.02 for Haiku, 0.140.14 against 0.060.06 for Sonnet). Against their singleton rates, the screened items are followed less often in a file than alone in 23 of the 24 cells for Haiku and 22 for Sonnet, by 0.070.07 to 0.660.66. In the other three cells, all files of at most 40 items, they are followed as often or more often, by at most 0.140.14. Figure 3: Size sweep: value Rρexp(Sb)R_ _exp(S_b) at price ρexp=0.1 _exp=0.1 against file size b for both models, one panel per pool size N. Points are means over the 60 tasks; bars are ±1.96± 1.96 Newey–West standard errors over the task sequence. The stars mark the measured optima n⋆(N)n (N). Figure 4: Size sweep: marginal relevant compliance MC⁡(b)MC(b) against relevant load at N=3200N=3200 for both models, with 95% task-cluster bootstrap bars. Table 2: Size-sweep cells for Claude Haiku 4.5: gross value R0(Sb)R_0(S_b) (followed relevant instructions per task, net of chance), the raw count, the singleton-weighted relevant load ℓ⁡(Sb) (S_b), and the marginal compliance MCMC of the step ending at b with its 95% task-cluster bootstrap interval. N b R0(Sb)R_0(S_b) raw ℓ⁡(Sb) (S_b) MCMC (step to b) 200 5 0.53 0.60 1.33 10 1.19 1.34 1.58 2.67 [1.91, 3.88] 20 2.05 2.35 3.39 0.48 [0.37, 0.57] 40 3.18 3.89 8.69 0.21 [0.13, 0.28] 80 5.11 6.49 14.00 0.36 [0.23, 0.50] 200 3.84 6.25 25.06 −0.11-0.11 [−0.22-0.22, −0.01-0.01] 800 5 1.37 1.43 2.00 10 1.01 1.10 2.53 −0.68-0.68 [−1.49-1.49, −0.14-0.14] 20 2.16 2.30 3.53 1.16 [0.92, 1.41] 40 3.33 3.62 7.03 0.33 [0.21, 0.44] 80 3.65 4.18 13.53 0.05 [−0.03-0.03, 0.14] 200 3.41 4.92 32.50 −0.01-0.01 [−0.06-0.06, 0.05] 400 4.05 7.19 62.93 0.02 [−0.01-0.01, 0.05] 800 2.65 7.69 98.36 −0.04-0.04 [−0.07-0.07, −0.01-0.01] 3200 5 1.55 1.57 1.56 10 2.11 2.17 3.39 0.30 [0.21, 0.40] 20 2.76 2.88 4.28 0.73 [0.33, 1.07] 40 3.65 3.88 6.56 0.39 [0.22, 0.56] 80 4.49 4.95 13.19 0.13 [0.03, 0.23] 200 5.04 6.12 30.86 0.03 [−0.04-0.04, 0.10] 400 4.50 6.63 59.47 −0.02-0.02 [−0.06-0.06, 0.03] 800 3.24 7.51 121.98 −0.02-0.02 [−0.04-0.04, 0.00] 1600 1.67 10.16 240.79 −0.01-0.01 [−0.02-0.02, 0.00] 3200 0.63 14.33 385.89 −0.01-0.01 [−0.01-0.01, 0.00] Table 3: Size-sweep cells for Claude Sonnet 5.5, as in Table 2. N b R0(Sb)R_0(S_b) raw ℓ⁡(Sb) (S_b) MCMC (step to b) 200 5 0.97 1.04 1.56 10 2.25 2.39 3.19 0.78 [0.67, 0.88] 20 2.27 2.56 5.28 0.01 [−0.09-0.09, 0.12] 40 8.07 8.74 11.28 0.97 [0.83, 1.11] 80 10.24 11.55 19.00 0.28 [0.05, 0.51] 200 17.21 19.45 35.22 0.43 [0.25, 0.60] 800 5 1.02 1.08 2.28 10 1.29 1.39 2.78 0.53 [−0.09-0.09, 1.00] 20 3.71 3.87 4.42 1.48 [1.31, 1.66] 40 5.58 5.91 10.61 0.30 [0.13, 0.47] 80 7.07 7.66 18.42 0.19 [0.02, 0.38] 200 11.18 12.85 46.44 0.15 [0.07, 0.23] 400 28.40 31.86 93.65 0.36 [0.26, 0.48] 800 3.72 9.27 147.59 −0.46-0.46 [−0.56-0.56, −0.36-0.36] 3200 5 1.60 1.62 1.50 10 3.31 3.38 3.89 0.71 [0.65, 0.78] 20 5.05 5.17 6.00 0.82 [0.63, 0.99] 40 12.72 12.95 11.03 1.53 [1.42, 1.63] 80 13.48 13.96 21.92 0.07 [−0.15-0.15, 0.28] 200 23.82 24.94 49.42 0.38 [0.20, 0.56] 400 15.88 18.07 94.43 −0.18-0.18 [−0.29-0.29, −0.06-0.06] 800 15.90 20.28 186.93 0.00 [−0.04-0.04, 0.04] 1600 12.32 21.05 369.21 −0.02-0.02 [−0.04-0.04, 0.00] 3200 4.01 18.09 591.98 −0.04-0.04 [−0.05-0.05, −0.02-0.02] Table 4: Size sweep: measured optimum n⋆(N)n (N) and accretion loss Rρexp(Sn⋆)−Rρexp(SN)R_ _exp(S_n )-R_ _exp(S_N) with 95% task-cluster bootstrap interval, per model, pool size and price ρexp _exp. N ρexp=0.05 _exp=0.05 ρexp=0.1 _exp=0.1 ρexp=0.2 _exp=0.2 ρexp=0.4 _exp=0.4 Haiku 200 40; 6.9 [5.9, 8.0] 10; 15.8 [14.6, 16.8] 5; 34.5 [33.3, 35.5] 5; 72.3 [71.1, 73.3] 800 40; 37.5 [36.4, 38.7] 5; 76.2 [74.9, 77.3] 5; 153.7 [152.4, 154.8] 5; 308.7 [307.4, 309.8] 3200 20; 159.1 [158.4, 159.9] 10; 316.7 [316.0, 317.4] 5; 632.2 [631.5, 632.9] 5; 1263.5 [1262.8, 1264.1] Sonnet 200 200; 0.0 [0.0, 1.3] 40; 6.0 [3.7, 8.3] 10; 21.9 [19.3, 24.5] 5; 59.3 [56.7, 62.0] 800 400; 41.9 [37.9, 47.6] 20; 75.9 [73.1, 78.4] 5; 152.3 [149.5, 154.6] 5; 307.3 [304.4, 309.6] 3200 200; 166.9 [161.3, 173.0] 40; 320.4 [315.1, 324.2] 40; 632.1 [626.7, 635.9] 5; 1260.2 [1254.7, 1263.7] Figure 5: Size sweep, Claude Haiku 4.5: value Rρexp(Sb)R_ _exp(S_b) against file size at each price ρexp _exp, one series per pool size N, with Newey–West error bars and stars at n⋆(N)n (N) as in Figure 3. Figure 6: Size sweep, Claude Sonnet 5.5: value Rρexp(Sb)R_ _exp(S_b) against file size at each price ρexp _exp, as in Figure 5. Figure 7: Monotone dilution, item by item, Claude Haiku 4.5: compliance of the relevant items of the b=40b=40 file in that file and in every larger file of the same pool, with 95% task-cluster bootstrap bars. Figure 8: Monotone dilution, item by item, Claude Sonnet 5.5, as in Figure 7. D.2 Dilution Purpose. Assumption 1 says that compliance with one instruction does not increase as the file grows. The dilution experiment measures the compliance curve q⁡(n)q(n) of 24 model configurations on a published instruction-density benchmark, with no model calls of our own. Data. The IFScale generations (Jaroslawicz et al.,, 2025): 5,993 reports from 24 model configurations with n∈10,…,500n∈\10,…,500\ keyword instructions and 5 seeds. The repository has no license and the paper is C BY-NC-SA 4.0, so the raw generations stay local and only aggregates are reported. Design. Every generation is re-scored with our labels; 52 generations that paste the keyword list are dropped. Per configuration we fit M⁡(n)=nq(n)M(n)=n\,q(n), the number of followed instructions, and report M⁡(500)/500M(500)/500, the compliance at n=500n=500. The fitted capacity K of the corrected curve fit sets the class: weak K<100K<100, mid 100100–350350, strong K>350K>350. Preregistered call. Descriptive only: M⁡(500)/500M(500)/500 is expected between 0.070.07 and 0.690.69 in all 24 configurations, with the late/early slope ratio of M⁡(n)M(n) below 0.10.1 in the four weak configurations and the hyperbola g⁡(x)=1/(1+x)g(x)=1/(1+x) the AIC-best form only in the weak class. Deviations. The fitted K places 6 configurations in the weak class, 5 in the mid class and 13 in the strong class; the plan projected 4, 8 and 12. The slope ratio is below 0.10.1 in 2 of the 6 weak configurations, and the hyperbola is AIC-best in 4 of the 6 weak configurations and in none of the others. One configuration, llama-4-scout, falls just below the planned 0.070.07 floor at 0.0670.067. Results. Compliance at n=10n=10 is 0.920.92–1.001.00 in every configuration. M⁡(500)/500M(500)/500 lies in [0.067,0.689][0.067,0.689] and is below 11 in 24 of 24 configurations (Table 5): no configuration follows its instructions in proportion to their number at n=500n=500, and the strongest configuration follows fewer than 0.70.7 of them. The curve q⁡(n)q(n) is nonincreasing for every class (Figure 9). The hyperbola of the logit case fits only the weak configurations; the monotone dilution Assumption 1 needs no particular curve and holds throughout. Table 5: Dilution: fitted capacity K, class, AIC-best curve form and compliance M⁡(500)/500M(500)/500 at n=500n=500, per configuration. configuration K class best form M⁡(500)/500M(500)/500 llama-4-scout 34 weak power 0.067 claude-3.5-haiku 52 weak hyperbola 0.085 gpt-4o-mini 61 weak hyperbola 0.104 gpt-4o 81 weak hyperbola 0.154 llama-4-maverick 87 weak power 0.096 gpt-4.1-nano 99 weak hyperbola 0.162 qwen3-235b-a22b 161 mid exponential 0.209 gpt-4.1-mini 202 mid exponential 0.272 deepseek-r1-0528 229 mid exponential 0.309 gemini-2.5-flash-preview 281 mid exponential 0.342 grok-3-mini-beta 329 mid exponential 0.364 gpt-4.5-preview 376 strong exponential 0.430 claude-opus-4 428 strong linear 0.446 claude-sonnet-4 504 strong linear 0.429 gpt-4.1 526 strong linear 0.489 claude-opus-4 (high reasoning) 602 strong exponential 0.521 o4-mini 611 strong logistic 0.344 claude-3.7-sonnet 613 strong linear 0.527 claude-sonnet-4 (high reasoning) 648 strong logistic 0.399 o3 845 strong logistic 0.516 grok-3-beta 1012 strong linear 0.619 gemini-2.5-pro-preview 1274 strong linear 0.666 gemini-2.5-pro-preview (high reasoning) 1333 strong linear 0.689 o3 (high reasoning) 1607 strong logistic 0.628 Figure 9: Dilution: q⁡(n)=M⁡(n)/nq(n)=M(n)/n against n for the lowest-, median- and highest-K configuration of each class (three left panels), and the 24 late/early slope ratios sorted, with 95% seed-bootstrap bars and the 0.10.1 reference line (right). D.3 Regret Purpose. Theorem 2 bounds the edit-cap term of ETC-m from above and Theorem 3 bounds every policy from below, both of order (N/m)L(N/m)L. The regret experiment runs ETC-m on the instances of Theorem 3 and checks both bounds and the order. It is a verification of the theorems, not an empirical test; no dataset has an edit cap. No data and no model calls. Design. The instances are those of Theorem 3: N identical items, a=0.02a=0.02, θg(a)=0.9θ g(a)=0.9, p=0.3p=0.3, c=1c=1, κ=0.004κ=0.004, B=10B=10, r1=1r_1=1, noiseless gains, with g⁡(x)=1/(1+x)g(x)=1/(1+x) of Appendix B; S⋆=1S =\1\ and every cell is exact. Grid: N∈16,32,64,128,256N∈\16,32,64,128,256\, m∈2,4,8,16m∈\2,4,8,16\, L∈10,20,40L∈\10,20,40\, 60 cells. ETC-m is Algorithm 1 with the estimator of Appendix C.5, under tied loads θi=λai _i=λ a_i. Regret is exact wherever the schedule fixes the file, so the only random element is the committed file. The cap term is the regret of the first epoch of every exploration batch plus the transition; the learning term is the later exploration epochs plus the commit phase. n0=⌈8ln⁡(6NT)/pmin⌉n_0= 8 (6NT)/p_ and T=L⁡(2J+⌈(s+nB)/m⌉)+4n0JT=L(2J+ (s+n_B)/m )+4n_0J are solved as a fixed point. The lower bound is (ΔL/2)(nm−1)( L/2)(n_m-1) with nm=⌊N/m⌋n_m= N/m and Δ=R⁡(S⋆) =R(S ). Preregistered call. The ratio of the cap term to the lower bound lies in [1,4(Δmax/Δ)(1+m⁡(1+nB/s)/(2N))][1,4( _ / )(1+m(1+n_B/s)/(2N))] in every cell with N≥4mN≥ 4m, and the log-log slope of the cap term on N/mN/m is 1.0±0.11.0± 0.1 at each L. A ratio below 11 refutes the bound or the simulator; a slope outside the band refutes the order N/mN/m. Deviations. None. Gains are observed without noise and η=1η=1; the pool has no spurious candidates, so ε is unused. Results. Both calls pass. Over the 51 cells with N≥4mN≥ 4m the ratio to the lower bound is 4.084.08–5.385.38, inside the interval in every cell (Table 6); the cap term is under the upper bound in all 60 cells, and ETC-m committed to S⋆S in every cell. The log-log slope of the cap term on N/mN/m is 1.0581.058 [1.029,1.088][1.029,1.088] with R2=0.997R^2=0.997 at each L, over a span of a factor 192192 in the cap term (Figure 2). The ratio does not depend on L and falls toward 44 as N grows, the constant of Theorem 2. The three parameters move the cap term as the bounds predict. More candidates increase the cost, because the policy must test more instructions. A larger edit cap decreases the cost. Longer epochs increase the time that the policy must keep each test batch. Table 6: Regret experiment: cap-term regret of ETC-m over the lower bound (ΔL/2)(nm−1)( L/2)(n_m-1), with the plan’s upper limit 4(Δmax/Δ)(1+m⁡(1+nB/s)/(2N))4( _ / )(1+m(1+n_B/s)/(2N)) in parentheses. The ratio does not depend on L. Cells with N<4mN<4m are outside the call. N m=2m=2 m=4m=4 m=8m=8 m=16m=16 16 4.35 (7.77) 4.83 (8.05) N<4mN<4m N<4mN<4m 32 4.20 (6.18) 4.42 (6.33) 5.02 (6.61) N<4mN<4m 64 4.13 (5.39) 4.26 (5.46) 4.57 (5.61) 5.38 (5.90) 128 4.09 (5.00) 4.19 (5.03) 4.40 (5.10) 4.87 (5.25) 256 4.08 (4.80) 4.15 (4.82) 4.32 (4.85) 4.66 (4.93)

Instant research discovery