- 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
-
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.
-
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.
-
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.
-
Strong theoretical completeness. This paper provides detailed proofs, optimized algorithms for constrained scenarios, and computational complexity results that elucidate the efficient preparation bounds.
-
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
-
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.
-
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.
-
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
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 and 6.36× faster at (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 , all feasible laminar families can be scored in operations.
- In practice, Tables 1 and 3 () 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.
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.
Joint minus marginal completion (points; conversation-bootstrap 95% intervals; the Table 2 configurations):
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.
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.
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.