acceptodds
Under review as a conference paper at ICLR 2027

Banking Expiring Compute: How Reuse Shapes the Value of Prediction

Abstract

Knowing the expected work of every feasible preparation need not reveal which one is most likely to finish within a fixed budget. We study banking expiring compute: using a temporary allowance to retain intermediate results, reusable while their inputs remain unchanged, under limited storage. For ordered associative computations, both the learner and an informed comparator may choose the evaluation tree and stored results. Under ideal reuse, individual interval-validity probabilities exactly characterize all feasible mean work; joint validity of collections that fit preparation and storage budgets characterizes full work distributions. We construct laws agreeing on every feasible mean, yet even randomized mean-only decisions have exponentially smaller worst-case completion probability than informed decisions with the same resources. On this family, increasing only the execution budget makes a history-free randomized policy exponentially close to optimal in a specified slack range. Logarithmically many complete i.i.d. histories from the same update law recover an optimal preparation with high probability. More generally, physical reuse capacity bounds the sample complexity of near-optimal preparation, with matching worst-case bounds in identified ideal-interface regimes. The upper bound has no additional input-count dependence beyond resource parameters and survives fixed nonnegative checking and restoration costs. Together, these results tie the value of predictive information and the statistical cost of learning a preparation to feasible reuse and execution budgets.

Primary area:
learning theory
Keywords:
statistical learning theory, value of information, sample complexity, data-driven algorithm selection, computation reuse, resource-constrained computation

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_9YZtOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper investigates how limited preparation and storage resources determine the value of predictive information when previously computed results can be reused before becoming invalid. The authors formalize a two-stage preparation problem for ordered associative computations, where an evaluation tree and a set of reusable intermediate results must be chosen under Build and storage budgets. The objective is to maximize the probability of completing future computation within a fixed execution budget. It derives several theoretical results. Theorem 1 characterizes the statistical information required to determine the feasible expected workload and the distribution of completed workloads. Theorem 2 constructs update distributions that agree on the expected workload for each feasible preparation plan but require different decisions when maximizing the completion probability. This separation holds even when facing a randomized mean-only strategy, and the decision values change significantly as the execution margin increases. Experimental evaluations covered precise synthetic constructs, natural revision histories, associative computation benchmarks, as well as caching and expert residency workloads related to LLMs. The results indicate that time-bound optimization yields significant benefits, while in certain scenarios, richer joint information also plays a role.

Critical strengths
  1. Significant theoretical contributions. This paper provides a rigorous characterization of the information required to determine expected work and the completion distribution under physically feasible reuse constraints.

  2. Convincing analysis and interesting time-dependent behavior. The analysis shows that, without changing the preparation resources, increasing the execution margin can significantly reduce the value of missing predictive information.

  3. Meaningful results on sample complexity. An upper bound on the VC dimension links learning complexity to physical reuse capacity rather than directly to the number of inputs, and provides a corresponding lower bound in specific scenarios.

  4. Strong theoretical completeness. This paper provides detailed proofs, optimized algorithms for constrained scenarios, and computational complexity results that elucidate the efficient preparation bounds.

  5. Extensive experimental evaluation. The experiments cover synthetic rules, natural revision trajectories, and several workloads related to large language models (LLMs), including four MoE models, all of which demonstrate consistent performance improvements through the integration of routing information.

Critical weaknesses
  1. There is a gap between theory and applications in LLMs. The strongest MoE results employ different reuse interfaces and a teacher-forced routing replay mechanism, making it impossible to directly verify the core guarantees of ordered tree learning.

  2. Computational scalability issues remain unresolved. Although the upper bound on sample complexity is optimistic, optimizing preparation for general change histories remains computationally challenging, and the NP-hardness of this general problem has been established.

  3. The paper is comprehensive and combines numerous theoretical and experimental directions, making the core contributions difficult to understand.

Questions for authors

Q 1. Practical Implementation.

Can the author identify a representative modern ML or LLM computational scenario in which the exact association reuse assumption holds, and where, given a balanced allocation of storage bytes and execution budget, the resulting preparation yields positive end-to-end savings? I am particularly interested in whether there are any evaluated settings that simultaneously demonstrate useful model quality, improved deadline completion rates, and still yield a positive net benefit after accounting for the costs of preparation, planning, validation, and recovery. A convincing example would significantly enhance my assessment of the practical significance of this theoretical framework.

Q2. The incremental value of joint information under real-world deployment conditions.

Experiments showed almost no improvement compared to paired information models, whereas MoE residency demonstrated significantly greater gains. To what extent can MoE’s improvements be sustained when preparation decisions are evaluated under actual autoregressive inference and realistic expert knowledge transfer behaviors, rather than during teacher-forced, token-by-token route replay?

4 comments
AuthorsOpenReview ↗

Response to Reviewer 9YZt (1/2)

Part 1/2 — Joint information under the models' own decoding and with executed expert transfer (Q2, W1)

Thank you for the careful reading of the theory, including the deadline transition of Theorem 2, one of its most distinctive parts. We begin with Q2: we ran both experiments it describes.

Q2: joint information under deployment conditions. Teacher forcing replays the WildChat responses through each model, so the routes follow those responses rather than the model's own continuations. The first new experiment removes this restriction.

  • Setup. Each held-out prompt is a test conversation up to its first assistant turn. Each model samples its own continuation with a KV cache (temperature 0.7, top-p 0.9, at most 256 tokens), and we record the experts routed at every decode step. Depending on the tokenizer, 1,162–1,170 of the 1,198 prompts fit the context limit.
  • Plans. We evaluate the published Table 2 plans, fitted on teacher-forced training conversations, without refitting.
  • Control. The original first answers to the same prompts pass through the same decoding path.
  • Code. The anonymized package contains the generation and evaluation code and the per-conversation outputs.

Joint minus marginal completion (points; conversation-bootstrap 95% intervals; the Table 2 configurations):

OLMoEGraniteQwenDeepSeek
Model's own continuations11.5 [11.1, 12.0]11.7 [11.3, 12.0]12.0 [11.8, 12.3]13.7 [13.2, 14.2]
Original answers, same prompts and decoding9.9 [9.6, 10.2]11.8 [11.4, 12.1]11.7 [11.4, 11.9]13.8 [13.4, 14.2]
Both plans refitted on the sampled routes7.8 [7.5, 8.2]12.7 [12.2, 13.2]10.8 [10.6, 11.0]13.0 [12.5, 13.4]

The gain persists when each model decodes its own continuations. Relative to the original-answer control it changes by −0.1 to +1.6 points, and no 95% interval for the change lies entirely below zero.

  • Self-generated routes shift the expert distribution (per-layer total variation 0.03–0.14). The third row therefore fits both plans on self-generated routes, cross-fitting on two halves of the sampled conversations; joint information still leads by 7.8–13.0 points.

Realistic expert transfer. We also executed the transfers and timed the decoding, under a protocol fixed before the measurement; the package contains it, its recorded deviations, the code and the per-step outputs.

  • Setup. Expert weights stay in pinned host memory. Whenever a decode step routes to a non-resident expert, its weights are copied to the GPU before it is evaluated, and the step is timed from input token to logits. The tokens are the models' own continuations: 150 held-out conversations for OLMoE (12,283 steps), 80 for Granite (11,022) and 60 for Qwen (9,960), each on an RTX 5090, at all 25 Table 2 configurations.
  • Deadline. For a copy cap BB, the latency deadline is the latency fitted on a third plan (frequency caching) at B+12B+\tfrac12 copies.
  • Result. Joint plans meet the deadline more often than marginal plans by 10.0 points [8.5, 11.6] on OLMoE, 10.2 [8.3, 12.1] on Granite and 12.7 [11.9, 13.6] on Qwen, and the joint plan leads wherever the two plans differ. Counting copies on the same steps gives 10.1, 10.6 and 12.8 points.
  • Mean latency. Joint plans do not lower mean latency (26.50 vs 24.99 ms per token on OLMoE, 32.18 vs 31.65 on Granite, 31.75 vs 31.56 on Qwen): they trade mean misses for per-token completion.
  • Scope. The memory limit is emulated: the GPU also holds a full copy of the experts, which only resident experts may read (except in the Qwen comparison with LRU in Part 2, where no full copy is held and each policy reads its own resident experts).

The contrast you note is real. On natural ordered traces, joint information adds at most 1.2 points in the pooled contrasts of Table 3, while in MoE residency the same completion optimizer gains 9.3–13.7 points when it is fitted on the recorded routes rather than on marginal-matched ones, and a layer-shuffle control attributes most of that gain to cross-layer dependence. This is the paper's stated conclusion: the value of richer statistics depends on the workload.

W1: theory–application gap. The formal link is Proposition I.1(2): with unit chunk lengths and no partial reuse, inclusion frequencies determine mean misses but not completion, which is the distinction the MoE experiments measure. They also test the paper's central claim, that the reuse interface decides which statistics suffice, on a second, set-valued interface. As you point out, the ordered-tree learning bounds are specific to ordered computations; Section 6 states this, and the revised discussion now repeats it. The autoregressive experiment above addresses the teacher-forcing part of this concern.

AuthorsOpenReview ↗

Response to Reviewer 9YZt (2/2)

Part 2/2 — An end-to-end example, scalability, presentation (Q1, W2, W3)

Q1: a setting with useful quality, better completion and positive net benefit. Yes. We reran the reader study so that your three criteria are measured on the same requests: with exact associative reuse, it shows all three; among LLM workloads, MoE expert residency comes closest.

Exact associative reuse: SSM-style readers on CPU (Appendix H; code in the package). On SelfRegulationSCP1, trained readers with one complex diagonal affine layer reach 79.9% clean test accuracy at width 128 and 83.4% at width 512 (three seeds; budgeted baselines in Table 10). Each request adds small Gaussian noise to one of 16 segments of a TEST recording and keeps its label. Over all 293 TEST recordings, three seeds and 128 requests each, with four stored records (16.6 kB at width 128, 65.7 kB at width 512):

  • Quality. Accuracy on the edited requests is 79.9% and 83.3%, within 0.1 points of clean; bank outputs equal cold outputs within floating-point tolerance.
  • Completion. A fixed-tree bank answers every request within the median cold latency on training inputs, which cold execution meets on 26.7% and 18.0% of requests.
  • Net benefit. The bank saves 61% and 64% of cold execution time net of planning, Build and serialization, with validity checks and restoration charged; over half for every seed and recording.

MoE expert residency.

  • Model quality. Residency leaves every model output unchanged, because each expert is computed exactly wherever its weights reside.
  • Deadline completion, by measured latency. With expert copies executed and decoding timed (Part 1), joint plans meet the per-token deadline 10.0–12.7 points more often than marginal plans on three models. Against per-layer LRU, the validated pin/LRU policy, whose pinned share is chosen on earlier conversations, is at or above LRU in every measured configuration. With eight conversations decoded in rotation it pins the static joint set and meets the deadline 14.3–27.2 points more often on OLMoE and 16.1–21.0 on Qwen, at mean latency equal to or lower than LRU's on OLMoE and within 0.3 ms of it on Qwen.
  • Deadline completion, in the replays. On all four models the validated policy is at or above LRU in every replayed cell and leads by 19.6–43.0 points with 8 or 32 conversations (Appendix I); joint information adds 9.3–13.7 points over marginal statistics (Part 1).
  • Costs. Planning is offline (under a minute per configuration on one GPU), no validation is needed at run time, and every miss is recovered by an executed copy inside the measured latency.
  • Scope. The interface is set-valued rather than exact associative reuse, and decoding is one token at a time.

Balanced-tree matrix-product chains at dimension 1024 (resident records, 128 reverted-edit rounds, version checks charged) also save net time, with no model-quality dimension: they run 2.63× faster than cold execution at (m,M)=(64,4)(m,M)=(64,4) and 6.36× faster at (1024,32)(1024,32) (Appendix H).

W2: computational scalability. We agree, and the paper keeps statistical and computational resources separate.

  • General planning is NP-hard (Appendix F).
  • Exact planning is polynomial for singleton-or-no-change laws.
  • At fixed MM, all feasible laminar families can be scored in O(M(M+s)m2M)O(M(M+s)m^{2M}) operations.
  • In practice, Tables 1 and 3 (m=8m=8) optimize exactly by enumeration. At 64 regions, local search attains the exact training optimum in 79% of three-record cells, and with four or eight records it stays within 0.1–0.4 held-out points of exact planning wherever a mixed-integer optimum is certified.

W3: presentation. We agree that the breadth of the paper hid its core contributions. In response, the revision adds:

  • a self-contained definition of the setting;
  • a three-sentence summary of the main results;
  • an explicit separation of the three claims: the objective, information sufficiency, and prevalence on natural workloads.

Your questions shaped this revision: Q2 specified the two deployment experiments, and Q1 the test that the reader study now reports. The general response lists what changed for the other reviewers, and we would be glad to answer any further question during the discussion.

Thank you for the clarification. The responses substantially address my concern. I will maintain my score.

Thank you for taking the time to read our responses and for your helpful questions.

Reviewer_npRkOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

Paper consider setting where computation is organized in a binary computational tree, where the leaves correspond to the inputs and the value of each node is computed from the value of its children. The authors consider scenario, where one can store and reuse some values of the internal nodes in the tree in order to reuse the corresponding computational results. There is however uncertainty about what inputs change and possibly invalidate the stored values.

Critical strengths

The model seems potentially interesting

Critical weaknesses
  • I find it very difficult to understand the exact setting of the paper with many terms not properly defined. Let's just look at section 3: "work" after changed J; feasible plan π\pi, virtual component, real size, virtual size. Plan π=(T,A)\pi=(T,A) retains MM complete subtree results -- which ones, those in AA? What is a legal execution?
  • I find it very difficult to understand what is the main contribution of this paper. Did they solve some problem? Did they introduce a novel model? In the abstract, they say that they construct a law with certain properties, where a low (as far as I understood) governs the changes of the inputs. I would rather expect a policy with certain guarantees.

I cannot recommend acceptance of a paper where the studied problem is not clearly stated, it is hard to understand what is the main discovery, and how does it fit to existing knowledge.

Questions for authors
  • Main question: what is the main result in your paper?
  • What aspects of the setting studied in your paper are novel and what were already studied? Are there already results you could compare to? Why have you decided to formulate a different model?
  • What performance measure do you use to evaluate your policies? Is it the probability of completing within a deadline, or the amount of work performed? Are they related?
  • Did you consider a sequence of input updates (possibly coming from the same distribution)? Does your result apply to this setting?
  • I understand that advance preparation makes sense in many scenarios. Can you motivate your particular model that you study and results you have achieved?

I am willing to increase my score if I see that my criticism of the paper's presentation is not justified.

3 comments
AuthorsOpenReview ↗

Response to Reviewer npRk (1/3)

Part 1/3 — The setting

Thank you for the review, and for naming the exact terms that were hard to find in Section 3. In brief:

  • Problem and main result. Before the inputs of an ordered computation change, one chooses an evaluation tree and which intermediate results to store, under preparation and storage budgets, so that a later request finishes within a deadline. The exact mean work of every feasible choice can be insufficient for this choice (Theorem 2); we identify the statistics that suffice (Theorem 1) and how many past observations are needed to learn the choice (Theorems 3–4).
  • A policy with a guarantee. Choose the feasible plan that would have met the deadline for the most past change sets. With probability 1−δ1-\delta, its completion probability is within ϵ\epsilon of the best feasible plan's once the number of observations reaches a bound set by storage, preparation shortfall and deadline slack, with no additional input-count term (Q1 in Part 2). The rule is standard; what is new is this bound, which comes from how much a plan can reuse.

Section 3 was too compressed: it specified every item you list, but through notation and formulas rather than in words, so a reader had to assemble them. The definition below states them explicitly; the revision opens Section 3 with it, and the model is unchanged.

Setting.

  • Computation. There are mm ordered inputs x1,…,xmx_1,\dots,x_m, each carrying a version, and a deterministic, exactly associative operation ⋆\star. The output is x1⋆⋯⋆xmx_1\star\cdots\star x_m, for example a prefix aggregate or a composition of affine state transitions.

  • Evaluation tree. Any full binary tree TT whose leaves are x1,…,xmx_1,\dots,x_m in order. Node vv computes the product of the input interval IvI_v below it. Each leaf read and each combination costs one unit, so computing from scratch costs n=2m−1n=2m-1.

  • Plan. π=(T,A)\pi=(T,A), where AA is the set of nodes of TT whose results are stored. We call AA the bank and its elements records. So yes: the retained subtree results are exactly the nodes in AA.

  • Feasibility. A plan is feasible if ∣A∣≤M|A|\le M (storage) and Build(π)≤b\mathrm{Build}(\pi)\le b (preparation). Here Build(π)\mathrm{Build}(\pi) is the number of unit operations needed to compute all stored results from the current inputs, with shared subtrees counted once. The shortfall is d=n−bd=n-b.

  • Changes. After preparation, an unknown set J⊆[m]J\subseteq[m] of inputs changes version, drawn from an update law PP. Record vv is valid if and only if no input below it changed, i.e. J∩Iv=∅J\cap I_v=\varnothing. A history is the change set of one past period, observed in full.

  • Legal execution. After the changes, TT is evaluated from the root. At node vv:

    • if v∈Av\in A and vv is valid, its stored value is used at no cost;
    • otherwise both children are computed recursively and combined (a leaf is read at cost one).

    Nothing else may be reused: no partial repair, no inverse updates, no newly saved state.

  • Work. Cπ(J)C_\pi(J) is the number of unit operations that this execution performs.

  • Objectives. For an execution budget LL (the deadline, also called the cap), the completion probability is FP(π)=P(Cπ(J)≤L)F_P(\pi)=P(C_\pi(J)\le L), and the slack is Δ=L−d\Delta=L-d. For comparison, the mean work is WP(π)=EP Cπ(J)W_P(\pi)=\mathbb{E}_P\,C_\pi(J).

Example (m=4m=4). Take the tree (x1⋆x2)⋆(x3⋆x4)(x_1\star x_2)\star(x_3\star x_4), so n=7n=7, and store only x1⋆x2x_1\star x_2 (one record, Build 3). If x1x_1 and x2x_2 are unchanged, the record is valid and the work is 4: read x3x_3 and x4x_4, combine them, and combine the result with the record. If x1x_1 or x2x_2 changes, the record is invalid and the work is 7. With deadline L=4L=4, this plan completes exactly when x1x_1 and x2x_2 are unchanged.

The three remaining terms belong to a closed form for the work. Assign each operation to the nearest stored node at or above it.

  • The real size wvw_v of record vv is the number of operations assigned to it.
  • The virtual component consists of the operations with no stored node at or above them. They are always executed, and their number is the virtual size aa.

Then Cπ(J)=a+∑v∈Awv 1{J∩Iv≠∅}C_\pi(J)=a+\sum_{v\in A}w_v\,\mathbf 1\{J\cap I_v\ne\varnothing\}. In the example, a=4a=4 and wv=3w_v=3. In the revision these terms appear after the definitions.

Where the submitted Section 3 states each item. For reference:

  • work after changes JJ: the closed form above, under "One execution identity";
  • feasible plan: at most MM stored results, and the Build constraint under "Execution and budgets";
  • which results are stored: the nodes in AA, the set over which Build is taken;
  • legal execution: "A record skips its subtree exactly when J∩Iv=∅J\cap I_v=\varnothing; otherwise execution recurses below it";
  • virtual component and sizes: "Assign each operation to its nearest retained ancestor, or a virtual component if none exists", with aa and wvw_v given by formulas.
AuthorsOpenReview ↗

Response to Reviewer npRk (2/3)

Part 2/3 — Main result and what is new (Q1, Q2)

Q1. What is the main result? In one sentence: knowing the exact mean work of every feasible plan does not suffice to choose the plan most likely to finish within the deadline, and we characterize which statistics do suffice and how many past observations are needed to learn such a plan. There are three results.

  1. Theorem 1 identifies the statistics that matter:
    • the mean work of every feasible plan is determined by the validity probabilities of individual intervals that fit the Build budget;
    • the full work distribution of every feasible plan is determined by the joint validity probabilities of unions of at most MM intervals that fit the Build budget together.
  2. Theorem 2 shows that the gap between these two levels matters for decisions. It constructs laws that agree on the mean work of every feasible plan. At small slack, any procedure that sees only these means, even a randomized one, has exponentially small worst-case completion probability, while a planner that knows the law, but not the future change set, reaches 1/21/2 with the same resources. Increasing only the deadline makes a history-free randomized policy exponentially close to optimal.
  3. Theorems 3–4 address learning. Given ss histories, choose the feasible plan that completes the largest number of them. With probability at least 1−δ1-\delta, its completion probability is within ϵ\epsilon of the best feasible plan once s≥c0 [Mlog⁡2(2+d/M+Δ)+log⁡(1/δ)]/ϵ2s\ge c_0\,[M\log_2(2+d/M+\Delta)+\log(1/\delta)]/\epsilon^2, for an absolute constant c0c_0. The bound depends on storage, shortfall and slack, with no additional dependence on the input count mm, and matching worst-case lower bounds hold in identified regimes.

On "a law rather than a policy": a law is the probability distribution of the set of inputs that change, as you understood. The law in the abstract is a lower-bound construction: the laws in Theorem 2 exhibit a limit that every policy restricted to mean information faces. The policies with guarantees are:

  • the learner of Theorem 3, with the sample bound above;
  • recovery of an optimal plan from O(log⁡(g/δ))O(\log(g/\delta)) histories on the family of Theorem 2;
  • exact planning algorithms (Section 4).

Q2. What is new, and why a different model? What is new is the pair of questions and their answers. We are not aware of prior work that characterizes which statistics of the change distribution suffice for such preparation decisions (Theorems 1–2), or that bounds the number of histories needed to learn them by physical reuse capacity (Theorems 3–4).

The ingredients of the model are classical: associative incremental aggregation, caching and checkpointing, chance-constrained optimization, and PAC algorithm selection. The questions require four features of the setting to be explicit:

  • (a) the preparation (a tree plus stored results) is fixed before the inputs change;
  • (b) validity is version-based on intervals;
  • (c) Build and storage budgets restrict what can be prepared;
  • (d) the objective is deadline completion, not mean recomputation.

Under a pure prefix interface, for instance, node-visit frequencies already determine every work distribution (Proposition I.1(1)), so the information question does not arise there.

The closest existing results are:

  • decision-focused learning, where exact target means can still yield poor decisions under a nonlinear objective (Cameron et al., 2022); our gap holds against any randomized rule that knows the mean work of every feasible plan, over all legal trees and banks, and becomes exponentially small when only the deadline increases (Theorem 2);
  • moment bounds and correlation-gap analysis (Bertsimas & Popescu, 2005; Agrawal et al., 2012), which already show that dependence beyond given summaries can matter; we identify which summaries legal reuse distinguishes, even when the exact mean work of every feasible plan is known;
  • sparse prefix caching for recurrent models (Shirokikh & Nikolenko, 2026), which minimizes expected recomputation under a prefix interface and learns from overlap depths;
  • tail-optimized caching (Zhang et al., 2025), which makes online cache decisions for a threshold-referenced excess latency;
  • sample approximation of chance constraints (Luedtke & Ahmed, 2008), whose direct-counting rate Mlog⁡(2+m/M)M\log(2+m/M) Theorem 3 replaces by Mlog⁡(2+d/M+Δ)M\log(2+d/M+\Delta) (Section 4).

A full comparison table is in the new Appendix J and in our response to Reviewer 1N37.

AuthorsOpenReview ↗

Response to Reviewer npRk (3/3)

Part 3/3 — Performance measure, update sequences, motivation (Q3–Q5)

Q3. Which performance measure? The objective throughout is the completion probability FP(π)=P(Cπ(J)≤L)F_P(\pi)=P(C_\pi(J)\le L); mean work is the comparison objective. Mean work bounds completion but does not determine it; for instance, for integer work and integer LL, Markov's inequality gives FP(π)≥1−WP(π)/(L+1)F_P(\pi)\ge 1-W_P(\pi)/(L+1). Equal means do not imply equal completion. In Theorem 2, every feasible plan has the same mean under all the laws, yet completion differs by an exponential factor. Empirically, training for completion rather than mean work raises held-out completion by 7.4–8.4 points on natural revision traces (Table 3).

Q4. Sequences of updates. Yes, in two senses.

  • Within one period, any sequence of updates may arrive before the request. Because reuse is version-based, only the set JJ of inputs whose version changed matters: repeated edits of one input count as one change, and an edit that restores an old value still invalidates.
  • Across periods, the change sets form a sequence drawn from the same law. This is the setting of Theorems 3–4: from ss past change sets, independent of each other and each observed in full, the learner chooses the plan for the next period. Dependence within a change set is arbitrary.
  • Scope. The guarantee assumes independent periods. Updating the stored results while changes arrive is outside the model.

Q5. Motivation. The common pattern is preparation before demand under a latency budget. Examples:

  • idle-time precomputation (continual computation, Horvitz, 2001; sleep-time compute, Lin et al., 2025);
  • incremental aggregation over changing inputs (sliding-window aggregation, Tangwongsan et al., 2015, 2017; Slider, Bhatotia et al., 2014);
  • composition of affine state transitions in linear state-space layers (Smith et al., 2023);
  • choosing which KV prefixes, retrieved chunks or experts to keep resident before requests arrive in LLM serving (Appendix I).

In each case, one must decide in advance what to keep under storage and preparation limits, the inputs may change, and what matters is whether the remaining work fits a deadline. Ordered associative computation is the simplest exact instance in which this information question can be answered completely.

The results answer two design questions for such systems.

  • What to record about past changes. How often each single interval stays unchanged is enough to predict expected work. It need not be enough to predict whether a deadline is met; how often stored intervals stay unchanged together is enough (Theorems 1–2).
  • How long to observe before trusting a learned plan. The number of periods needed scales with storage, shortfall and slack, with no additional input-count term (Theorems 3–4).

The revised PDF says all of this in the paper itself: Section 3 opens with the definition and the example of Part 1, the three remaining terms follow them, and the introduction states the three results of Part 2. These are changes of presentation; the model and Theorems 1–4 are as submitted. If a definition, the main result or its relation to prior work remains unclear, we would be glad to expand it during the discussion.

Reviewer_1N37OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

The paper studies anticipatory caching for computations whose inputs may change before the computation is needed.

One can spend time in advance calculating and storing intermediate results, then reuse the results that remain valid after the inputs change. The goal is to finish within a future deadline, under limited preparation time and storage. The main claim is that expected recomputation cost is not always enough to choose a good cache. Two possible patterns of future changes may give the same expected cost for every available preparation, while differing in which preparation is most likely to meet the deadline. The missing information concerns dependencies between changes: it matters which cached results become invalid together, not only how often each one fails individually.

The paper develops a theory of which information can be distinguished by the reuse mechanism and how many past observations are needed to learn a good preparation. It proves strong separations using synthetic update laws, together with statistical learning bounds. The experiments support the claim in selected synthetic and mixture-of-experts settings, but show much smaller benefits from richer joint information on natural revision traces, and do not establish general net wall-clock savings for the main ordered-computation model.

Critical strengths

The strongest aspect of the paper is its theoretical characterization of the information that can matter for reuse decisions. The paper makes the useful distinction between expected recomputation cost and the probability of completing before a deadline, and shows that the former does not always determine the latter. The constructions and learning bounds give this distinction a precise form, while the dependence of the result on the available reuse and execution capacity provides a coherent conceptual thread.

Critical weaknesses
  1. The central claim (joint predictive information matters when reuse is physically limited) is established only on purpose-built laws. The natural-workload evidence mostly does not support its practical relevance, and the positive evidence is not an instance of the theory.

  2. Presentation and verifiability: the 9-page main text is a compression of a 55-page document and cannot stand alone.

  3. The authors disclose extensive AI assistance in designing the experiments, suggesting parameters, implementing methods, generating synthetic laws and edits, cleaning data, coding, and interpreting results. This disclosure does not by itself undermine the work, but it makes reproducibility especially important: several numerical claims could in principle be produced by relatively short bespoke scripts, while the paper currently provides no code or raw outputs for independent checking during review. The submission should provide exact generation/enumeration scripts, preprocessing code, configurations, seeds, per-run outputs, and a minimal runnable reproduction of the main tables, or explain why these cannot be provided.

  4. Many proofs are very terse (e.g. the laminar-structure counting inside the VC bound, Lemma A.1, Appendices D-E). The authors disclose heavy AI assistance for framework, claims and proof ingredients, with checking by derivation and exhaustive finite computation rather than formal verification. That is acceptable, but it raises the burden to make the proofs checkable by a human reader. I could follow the main arguments and my spot-checks agree, but I cannot vouch for every step of the roughly 17 pages of proofs (A-G). Code is promised only on acceptance, so the many experiments cannot be checked.

Questions for authors
  1. In which realistic regime does Thm 3 improve on direct counting O(M log(2 + m/M))? Since d = n-b, bounded d/M requires an almost full Build. What are (m, M, b, L) for a realistic ML setting (SSM state, prefix aggregates) in which the bound is both non-vacuous and better than direct counting?

  2. Can the exponential separation be obtained for laws that agree on all pairwise (or bounded-order) statistics? The matched pair of Sec. 6 has equal first/second moments but only a 9-point gap at m = 8. If not, the claim that "joint" information matters should be limited to the combinatorial family.

  3. Is there any workload in the ordered-associative model where banking gives net wall-clock savings and where joint (rather than pairwise/marginal) information pays for its planning cost? If not, how should the "expiring compute" motivation be read?

  4. MoE residency: how does it relate to the theory beyond Prop. I.1(2)? Please compare with at least one trace-driven expert caching/prefetching baseline, report miss volume or latency, and give intervals that resample conversations rather than configurations.

  5. The learner analysed (ERM over feasible plans) is NP-hard in general (App. F) and exponential in s for general masks; the experiments use greedy/local search (greedy loses even on TRAIN in 63/72 RAGPulse runs). Do the guarantees apply to anything that is run? Please state in the abstract that the learning result is information-theoretic.

  6. The empirical section relies on purpose-built synthetic laws, exhaustive finite enumeration, bespoke dataset extraction, and learned or approximate optimizers. Please provide, during review if possible, the exact law-generation and enumeration code, preprocessing scripts, all seeds and hyperparameters, raw per-run results, and a clear separation between exact calculations, Monte Carlo estimates, bootstrap intervals, and approximate optimization. At minimum, can the authors provide an anonymised, independently runnable reproduction of the matched-law results and Tables 1--3?

  7. The paper claims a new framework, but the novelty relative to predictive caching, continual/incremental computation, checkpointing/rematerialisation, learned caching, algorithm selection, and expert-offloading systems is difficult to assess. Please add a comparison table covering the execution model, whether preparation is fixed before updates, the invalidation/reuse model, resource constraints, and the objective (expected work versus deadline completion). Where prior methods can be instantiated, please compare against them empirically rather than only against statistics and plan classes introduced in this paper.

5 comments
AuthorsOpenReview ↗

Response to Reviewer 1N37 (1/5)

Part 1/5 — What the evidence supports (W1, Q2)

Thank you for the detailed review and for spot-checking the arguments. You ask for code and raw outputs, checkable proofs and claims scoped to the evidence; the revision and the supplement now provide each, and answer Q1–Q7:

  • Code and raw outputs (W3, Q6). An anonymized, runnable package: an exact verifier for the matched pair (about 4 s), and code, seeds and per-run outputs for Tables 1–3 (Part 3).
  • Checkable proofs (W4). The counting step of the VC bound is written out in six steps, and Lemma A.1 and Appendices D–E are expanded into numbered steps. Scripts check Theorems 1–3, Lemma A.1 and two of these steps exhaustively on small instances (Part 3).
  • Scoped claims (W1). The revised introduction separates what is proved for every update law, what is a worst-case construction and what the traces show. New evidence on a natural workload: in MoE expert residency, joint information adds 9.3–13.7 points on four models, also under their own decoding, with measured latency and on a second corpus (this part).
  • Bounded-order statistics (Q2). Yes: a new proposition keeps an exponential separation at zero slack for laws that also agree on all pairwise statistics, or on all moments up to any fixed order (this part).
  • Net savings with joint information (Q3). Yes, in a new timed test on a trained reader, with edits from the matched laws of Section 6 (Part 2).
  • Your other requests. The abstract now says that the learning guarantee is statistical (Q5). We also give a numerical regime for Theorem 3 (Q1), a caching baseline, miss volume, measured latency and conversation-level intervals for MoE (Q4), and the comparison table with three prior methods run on the natural histories (Q7); see Parts 4 and 5.

W1: scope of the evidence. Constructed laws enter only where a worst-case statement needs them. Theorem 1 and Theorem 3 hold for every update law; Theorem 2 and the lower bounds of Theorem 4 are worst-case results, which is why they are proved by construction. How often the extra information matters is an empirical question, so the paper makes three separate claims.

  1. Objective. Minimizing mean work need not maximize completion. On natural traces, completion training gains 7.4–8.4 points over mean-work training (Table 3).
  2. Information sufficiency. Even the exact mean work of every feasible plan can be insufficient (Theorem 2). This is a worst-case existence result on constructed laws.
  3. Value of richer joint statistics. For MoE expert residency, a natural workload, joint information adds 9.3–13.7 points on four model families, 11.5–13.7 under the models' own decoding, and 9.7–10.2 on a second corpus (three models); for this set-valued interface, Proposition I.1(2) shows that frequencies fix mean misses but not completion (Part 4). On our natural ordered-computation traces we agree with your reading: interval, pairwise and marginal models come within 1.2 points of full history when pooled as in Table 3, and within two points on every row.

Q2: bounded-order statistics. Yes: at zero slack, an exponential separation survives matching of all pairwise statistics, and of all moments up to any fixed order kk. The revision adds this as Proposition A.4 (Appendix A.2). In Theorem 2 the gg hidden candidates share one fair change bit, which pairwise covariances reveal; the new laws hide that bit inside blocks.

  • Blocks. Each candidate becomes a block of 4t−24t-2 inputs, followed by an always-changing input. In state 1 the block stays unchanged with probability α=1−1/t\alpha=1-1/t; otherwise 2t2t random inputs change. In state 0 one random input changes with probability (4t−4)/(4t−3)(4t-4)/(4t-3); otherwise all do. Both states give the block the same first and second moments.
  • Laws. The gg blocks in HH share one fair state bit; the other gg have independent fair state bits. All (2gg)\binom{2g}{g} laws therefore agree on every feasible mean and on all moments of the change mask up to order five.
  • Separation. With M=gM=g and the Build of gg whole blocks, at zero slack a plan completes only by saving gg whole blocks that all stay unchanged. Knowing HH gives αg/2\alpha^g/2. Any procedure that sees only the feasible means and these moments, even a randomized one, completes with probability at most (3α/4)g(3\alpha/4)^g under some law. With t=4gt=4g this is at least 3/83/8 against at most (3/4)g(3/4)^g; at g=8g=8 (m=2,032m=2{,}032), 0.388 against 0.031.
  • Any fixed order. Size laws with equal moments up to order kk exist for every kk (Lemma A.5), with block size polynomial in gg.
  • Learning. O(log⁡(g/δ))O(\log(g/\delta)) complete histories identify HH from how often pairs of blocks stay unchanged together, which these moments do not determine.
  • Check. A standard-library script in the package verifies these moments exactly and, at g=2g=2, enumerates all 20,417 feasible banks under all six laws; it repeats the bank check at g=3g=3.
AuthorsOpenReview ↗

Response to Reviewer 1N37 (2/5)

Part 2/5 — Net wall-clock savings and joint information (Q3)

Q3: net savings with joint information. Yes: a new controlled test shows both; how often this happens on natural workloads is not shown. It helps to separate banking itself from joint information.

  • Where banking itself saves time. Balanced-tree matrix-product chains at dimension 1024 (resident records, 128 reverted-edit rounds, version checks charged) run 2.63× faster at (m,M)=(64,4)(m,M)=(64,4) and 6.36× faster at (1024,32)(1024,32). On SCP1 under independent edits on CPU, fixed-tree banks of trained affine readers meet the deadline on every request, against 26.7% and 18.0% for cold execution at widths 128 and 512, and save 61% and 64% of cold execution time net of planning, Build and serialization; accuracy on these requests stays within 0.1 points of clean (293 test recordings, three seeds; Appendix H).
  • Joint information with measured costs (new test). The reader study above plans from single-input edit histories, for which per-input change rates determine every work distribution, so it cannot test joint information. The new test draws edits from the matched pair of Section 6 (Q2 in Part 1), whose two laws agree on all first and second moments, and applies them to SCP1 recordings read by the trained width-512 reader, with the bank class of Tables 1 and 3, (m,M,b)=(8,3,10)(m,M,b)=(8,3,10).
    • Planning. Full history, the pairwise model (maximum entropy given all first and second moments) and marginal statistics are fitted to the same 32 independent samples of 1,024 training histories. Each picks the bank with the highest predicted completion under one latency model fitted on training recordings, so no test timing enters planning.
    • Measurement. Every chosen bank is built on each of two test recordings and timed on all 256 change masks in two passes; reading the bank, validity checks and restoration are inside the timed requests. Completion integrates each law over these masks.
    • Completion. At the median cold latency on training recordings (8.73 ms), full history meets the deadline on 99.5% of requests under both laws, against 98.3% and 98.1% for the pairwise model: +1.2 [1.1, 1.4] and +1.4 [1.3, 1.6] points (intervals resample the 32 training samples), so misses fall from 1.7% and 1.9% to 0.5%. Over marginal statistics the gains are +1.0 [0.8, 1.1] and +1.1 [0.9, 1.2] points. With 256 histories the gains over the pairwise model are +0.8 points under both laws, and a law with independent changes shows no gain.
    • Cost. At this deadline the full-history, pairwise and marginal banks save the same time relative to cold execution, to within 2 ms: about 0.39 s per 128 requests, about 30% of cold execution time, net of history fitting, planning, Build and serialization. The completion gain therefore costs essentially no net time. The one-time setup, 16 s mostly spent profiling the hardware for the latency model, is shared by all banks and recovered after about 43 of them.
    • Package. The code, every timing, and a script that rebuilds every bank choice from the training inputs alone.

The "expiring compute" motivation is best read as a decision problem: what to keep, and which statistics suffice to choose it. Net runtime benefit depends on the implementation, and our timing studies identify the costs that decide it: per-request overhead, validation and host transfer.

AuthorsOpenReview ↗

Response to Reviewer 1N37 (3/5)

Part 3/5 — Checking the experiments and the proofs; presentation (W3/Q6, W4, W2)

W3 and Q6: reproducibility. We agree that the disclosed AI assistance raises the bar for checkability; the package and the expanded proofs answer it. The package covers the matched-law results and Tables 1–3, the minimum you name, and the seven new studies, but not every appendix experiment. The code is the code that produced the reported numbers; the only edits remove names and paths. The package contains the items you list:

  • Matched laws and enumeration. An independent verifier rebuilds the matched pair from the 256 printed integers and checks its moments, interval statistics, all 2,236 banks, the three optima and 7419/819207419/81920. It was written from the paper's definitions, separately from the experiment code, with exact rationals and only the standard library. It runs in 4 seconds (command in the README).
  • Theorems on small instances. Written for the review: exhaustive checks over all feasible plans of Theorem 1 (m≤5m\le5), Lemma A.1 and Theorem 2 at g=2g=2, and of the closed form for work against direct execution (m≤6m\le6). For Theorem 3, on all 1,693 instances with m≤6m\le6 (and m=7m=7, M≤3M\le3), every plan meets the capacity bound and the exact VC dimension never exceeds Mlog⁡2(2+d/M+Δ)M\log_2(2+d/M+\Delta). Each check has a control showing that it can fail.
  • Tables 1–3. Code, seeds, settings and per-run outputs, and the inputs of Tables 1 and 3; Table 1 reruns bit-identically in 35 s on a laptop CPU. Table 2 recomputes from per-conversation outputs; the README rebuilds its router traces (1.7 GB) from public models and data and a bit-identical copy of all 3,991 conversations.
  • Preprocessing. The scripts that built the change masks from public git histories and Wikipedia revisions. They need network access, so the outputs are shipped.
  • Kinds of numbers. A table classifying each covered result as exact calculation, Monte Carlo estimate, bootstrap interval or approximate optimization.
  • New studies. Code and per-item outputs for the seven new studies: self-generated routing, measured expert offloading, shorter MoE histories, a second corpus, the prior methods of Q7, reader quality and timing on the same edited requests, and the timing test of Q3.

W4: proof detail. The revised Appendix G spells out the counting step of the VC bound:

  1. Witness. If masks J1,…,JvJ_1,\dots,J_v are shattered, some feasible π+\pi_+ completes all of them. Ideal work is monotone in the change set, so Cπ+({j})≤LC_{\pi_+}(\{j\})\le L for every j∈Z:=⋃iJij\in Z:=\bigcup_iJ_i. Hence ∣Z∣≤G|Z|\le G by the capacity bound of Section 4.
  2. Projection. Every Ji⊆ZJ_i\subseteq Z. So for any plan and stored interval II, 1{Ji∩I≠∅}=1{Ji∩(I∩Z)≠∅}\mathbf 1\{J_i\cap I\ne\varnothing\}=\mathbf 1\{J_i\cap(I\cap Z)\ne\varnothing\}, and on these masks a plan acts only through its projected intervals I∩ZI\cap Z. Empty projections give constant features, which the threshold absorbs.
  3. Laminarity. A plan's stored intervals are nodes of one tree, so any two are nested or disjoint. Intersecting with ZZ preserves both relations. The projections therefore form a laminar multiset of r≤Mr\le M intervals of the ordered set ZZ; duplicates are allowed.
  4. Counting structures.
    • Read the 2r2r endpoints left to right, writing "(" for left and ")" for right endpoints, and break ties at a shared position by nesting. This gives a balanced word, so there are at most Catalan(r)≤4r\mathrm{Catalan}(r)\le4^r shapes.
    • The endpoint positions form a weakly increasing sequence of length 2r2r in ZZ, so there are at most (G+2r−12r)≤(G+2r2r)\binom{G+2r-1}{2r}\le\binom{G+2r}{2r} placements.
    • Ties occur only between nested intervals, so every laminar multiset arises from some shape and placement. There are thus at most ∑r≤M4r(G+2r2r)\sum_{r\le M}4^r\binom{G+2r}{2r} structures.
  5. Halfspaces. For a fixed structure, the closed form for work in Section 3, or its fee version in Appendix G, makes every completion indicator an affine threshold of the rr binary hit features, with arbitrary real coefficients. Halfspaces on rr features have VC dimension r+1≤M+1r+1\le M+1, so by Sauer's lemma they induce at most (ev/(M+1))M+1(ev/(M+1))^{M+1} labelings of v≥M+1v\ge M+1 points.
  6. Conclusion. Shattering requires 2v≤[∑r≤M4r(G+2r2r)] (ev/(M+1))M+12^v\le\big[\sum_{r\le M}4^r\binom{G+2r}{2r}\big]\,(ev/(M+1))^{M+1}, which gives v=O(Mlog⁡(2+G/M))v=O(M\log(2+G/M)). Combined with G/M≤(d+1)/(2M)+ΔG/M\le(d+1)/(2M)+\Delta, this yields the bound of Theorem 3.

The revision also writes out in numbered steps the domination step of Lemma A.1, the case analysis of Appendix D and the testing arguments of Appendix E. The package checks the first two, the encoding of step 4 and Theorem 3 itself by enumeration.

W2: a main text that stands alone. We agree that the main text was too compressed. The revision opens Section 3 with a self-contained definition of the setting (reproduced in our response to npRk), ends the introduction with a three-sentence statement of the main results, and separates the three claims of Part 1.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response to all reviewers

General response: main results, scope of the evidence, code

We thank the reviewers for their careful reading.

Main results in brief. Before the inputs of an ordered computation change, one chooses which intermediate results to store, under preparation and storage budgets, so that a later request finishes within a deadline.

  1. For every update law, the validity probabilities of single intervals determine the mean work of every feasible choice, and joint validities of budget-feasible unions determine its work distribution (Theorem 1).
  2. Laws can agree on every feasible mean and still require different choices. Even randomized mean-only decisions then have exponentially smaller worst-case completion probability than informed ones, while increasing only the deadline makes this gap exponentially small (Theorem 2).
  3. Learning a near-optimal choice needs a number of past observations governed by storage, preparation shortfall and deadline slack, with no additional input-count term and matching lower bounds in identified regimes (Theorems 3–4).

1. Presentation (all reviewers). Section 3 now opens with a self-contained definition of the setting, reproduced in our response to Reviewer npRk, and the introduction ends with the three results above.

2. Scope of the claims and the evidence (Reviewers 9YZt and 1N37). The revision keeps three claims apart.

  • Objective. Minimizing mean work need not maximize completion. On 80 natural revision histories, training for completion instead of mean work gains 7.4–8.4 points of held-out completion (Table 3).
  • Information sufficiency (theory). Theorems 1 and 3 hold for every update law. Theorem 2 and the lower bounds of Theorem 4 are worst-case results on constructed laws: they show existence, not prevalence.
  • Whether natural workloads need more than simple statistics. On our natural ordered-computation traces, interval, pairwise and marginal models come within 1.2 points of full history when pooled as in Table 3. Joint histories pay off for MoE expert residency: with the same completion optimizer and budgets, plans fitted on recorded routes beat those fitted on marginal-matched routes by 9.3–13.7 points on four models. The gain persists under each model's own decoding (11.5–13.7 points), with expert copies executed and latency measured (10.0–12.7 points on three models; see our response to Reviewer 9YZt) and on a second corpus (9.7–10.2 points, three models). Expert residency is a set-valued interface: Proposition I.1(2) shows that there, too, frequencies fix mean misses but not completion; the ordered-tree learning bounds do not apply.

On SCP1, banking meets Reviewer 9YZt's three criteria on the same synthetically edited requests: fixed-tree banks of trained CPU readers keep accuracy, meet the deadline on every request (cold: 18–27%) and save 61–64% of cold execution time over 128 requests, net of planning, Build and serialization (Appendix H.4).

3. Verifiability (Reviewer 1N37). The supplement now links to an anonymized, runnable package:

  • an independent exact verifier for the matched pair;
  • exhaustive checks of Theorems 1–3 and Lemma A.1 on small instances;
  • code, seeds and per-run outputs for Tables 1–3 and the seven new studies, with the inputs of Tables 1 and 3;
  • a table separating exact computations, Monte Carlo estimates, bootstrap intervals and approximate optimization.

4. Positioning (Reviewers npRk and 1N37). Our response to Reviewer 1N37 includes a comparison table, added to the revision as Appendix J.

The plan trained for completion also leads three prior preparation methods on the 80 natural histories of Table 3; the strongest, greedy view materialization, trails by 9.6 points.

5. Computation (Reviewers 9YZt and 1N37). The learning guarantee is statistical, not computational, as the revised abstract now states. In Tables 1 and 3, plans are optimized exactly over all 2,236 feasible banks, so the full-history learner is the empirical completion maximizer of Theorem 3. General planning is NP-hard (Appendix F).

Summary of changes in the revised PDF (marked in blue).

  • Abstract, and Section 4 after Theorem 3: the learning guarantees are statistical, not computational.
  • Sections 1 and 3: the three claims, stated separately with the natural-trace and MoE findings; a summary of the main results; a self-contained definition of the setting.
  • Section 4: a numerical comparison with direct counting.
  • Section 6, Appendix A.2: the matched-pair gap is finite; exponential gaps survive bounded-order matching.
  • Section 7: the scope of each claim: expert residency and the ordered-tree learning bounds, and the timing evidence.
  • Appendices A, D, E and G: proof steps written out in numbered form.
  • Section 6, Appendix I: expert residency with own decoding, measured latency, less history and a second corpus.
  • New Appendix J: comparison table with related work, and three prior methods on the natural histories.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.