acceptodds
Desk rejected at ICLR 2027

Revisability Buys Geometry-Independence: Competitive Analysis of Batched Memory Consolidation

Desk rejected at ICLR 2027, so left out of the paper lists and the map.

Abstract

Moving memory items into network weights, known as consolidation, incurs costs that depend heavily on batching: items consolidated together share a fixed setup price and influence each other's utility based on batch composition. This paper establishes a pricing framework for this consolidation process, yielding a central negative result. The most straightforward consolidation strategy, where each batch fixes its internal alignment, lacks a bounded competitive ratio because an adversary can strategically flood any fixed configuration. Escaping this impossibility requires revisability: the ability to adjust a prior batch's alignment. We analyze two mechanisms for revisability (a lightweight approach of replaying past data during new consolidation steps and a costly joint refitting procedure) and derive their respective prices. Pre-registered experiments on real feature geometry show that while our core theoretical guarantees (the ledger, dominance arithmetic, scheduling reductions, and worst-case bounds) and the separation construction hold on natural data, the exact closed-form quantitative levels do not transfer directly. All pre-registered evaluation criteria are fully detailed in the appendix.

Primary area:
learning theory
Keywords:
continual learning, lifelong learning, memory consolidation, online algorithms, competitive analysis, batching, theory

Reviews

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

As I understand it, the paper studies a setting in which the question is when to write data into a model's weights and which data to combine for such write operations. Different ways to add data to the weights are considered: train on everything from scratch, train only on a batch of the new data, or train the new data together with a few examples of the previous data. Full retrain is the optimal baseline. The paper shows that training only on a batch of the new data fails, but that training together with a few past examples gives a good overall tradeoff.

Critical strengths

The general topic of this paper is interesting even though the precise technical setting is much more narrow.

Critical weaknesses

I struggled a lot with this paper. And maybe that is partly my fault, but I found the paper incredibly difficult to read in a way that is not easy to articulate. Crucial definitions that would belong in the introduction as formally describing the setting, are only found in the appendix. The tone of voice in large sections of the paper feels robot like and it is almost like the text wasn't designed to be a self-contained paper with a nice exposition for a human reader. "Appendices A and B build the world (economics, notation, substrate); C through F prove the economics of frames and schedules (ledger, gauge split, dominance, scheduling)": "build the world"? "substrate"? All over the paper, there is a lot of economic terminology in place of mathematical one ("ledger", "tax", "premium", "currency").

Appendix P really needs to be reformatted.

I wished I could say something more substantive about the content of the work, but, sadly, I am afraid I was unable to get that far despite spending a considerable amount of time on reading the work.

Questions for authors

I did not fully understand the cost measure for W2. Do you not need increasingly many examples in the anchor as the number of classes grow? And doesn't this increase the cost of the anchor over time?

Reviewer_BnibOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This work considers the problem of memory consolidation. It provides theoretical and empirical results characterizing a common problem in continual learning where a model needs to be updated online, but different strategies about when and how to do those updates may incur different costs. The work proposes that revisability or ability to change how older information is represented balances some key trade offs in memory consolidation. To implement this they try replaying data or refitting it later and examine how costly and effective these strategies are on a Pythia model and on vision classification models.

Critical strengths

There are extensive theoretical analyses on memory consolidation updates, particularly around characterizing costs and tradeoffs of update decisions. Overall there is much emphasis on the cost of different strategies. The topic of memory consolidation itself is interesting and relevant to the community.

Critical weaknesses

The work is extremely difficult to follow. It is never clearly stated what is the task being tested (classification?), and thus it is challenging to assess the merit of the work. There are also no baselines of any kind. The writing style introduces many poorly defined terms such as ‘rent’, making it difficult to follow the motivating and theoretical components. I would appreciate it if the work could make it more clear what is the task, what is the method, and how the method compares to or helps us understand current approaches in the field.

Questions for authors

What is the exact task and models that are being tested? What are the existing approaches that are relevant to this work and can a direct comparison be made with your methods and them?

The work has a big emphasis on the cost of memory consolidation. Concisely, how does the work define and measure cost?

Reviewer_M3JHOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

In this work, the authors gave a pricing framework for memory consolidation which combines setup costs, waiting costs, and classification error. It studies joint refitting, anchored replay, and unanchored fitting. Moreover, it also establishes a conditional theoretical separation between fixed-frame and revisable writes. Furthermore. their analysis identifies how mismatched coordinate frames can create persistent errors and how covering replay can remove this obstruction.

Critical strengths
  1. The paper considers both when to consolidate as well as which items to consolidate together, and which fitting procedure to use. It is interesting that connecting these decisions through a common cost framework is an interesting research direction.

  2. The main theorem obtained an useful guarantee, which states that merging batches does not worsen the stated worst-case bound and removes frame mismatch for pairs brought into the same batch. Furthermore the Example 2 also clarifies the scope of this result by showing that merging need not improve every pair on a particular instance.

  3. I liked the transparency of the experimental discussion. The authors reported failures of quantitative transfer and unsuccessful selection rules.

Critical weaknesses
  1. The central separation depends strongly on the operator restrictions as well as error objective.

  2. The positive guarantee leaves the practical cost of replay unresolved. For instance, the covering replay must include all previously written classes, but the scheduling guarantee assumes a setup cost independent of the store size.

  3. The framework does not yet provide a policy for the full decision problem, as suggested in the motivation.

Questions for authors
  1. Can you bound the residual excess error and incorporate it into the competitive analysis?

  2. Can partial coverage provide a useful tradeoff between replay cost and residual error?

  3. Can an analogous separation be established when errors are charged according to the actual query distribution or multiclass prediction loss?

1 comment
AuthorsOpenReview ↗

the paper answers Questions 1 and 2 and half of Question 3. the population ledger is exact, the middle is measured and negative, and the separation depends on the charge.

Dear Reviewer M3JH,

You asked three questions and raised three concerns. The paper answers Questions 1 and 2 in full, and half of Question 3. Your first two concerns are fair, and the paper acknowledges both; the third is right too, and we name that gap openly.

Question 1: the residual excess error. At the population level the answer is exact, not a bound. The Section 4 ledger prices every cross-batch pair in closed form, and Proposition 13 splits that price in two: a per-class shift, which a single offset removes completely, and a misalignment of direction, which no constant can fix, because constants move thresholds, not directions.

The residual is already inside the competitive analysis: its floor is integral to Theorem 4's separation. Under every composition and correction the flooded pair's residual stays above that floor, and Proposition 33 caps it at 0.5807 (Appendix P.2). This exactness holds in the ideal case, but it stops on finite data. The proof of the anchored escape leaves anchor noise outside its scope by design, and Section 10 says plainly that the ledger's level does not carry over to learned features. A distribution-free finite-sample bound is still open problem; we do not know one yet.

Your second concern and Question 2: how expensive replay really is. You are right, and the paper says so. The scheduling guarantee treats setup as a fixed price, but a covering anchor must store examples of every class written so far, so its cost grows with the store. The registered cost model charges a write by the classes it serves, which makes full coverage grow with the square of the store-to-batch ratio (E-L2-11); the experiments therefore ran both arms (E-L2-12).

The measurements agree with the model. A covering anchor's setup price came in at 147.1 times the plain write's (152.2 and 155.8 on other seeds), growing with the store as predicted. On 15 adversarial streams built to make undoing as costly as possible, the covering policy never once beat the break-even rule; its cost ratio, 47.19, stayed within the 156.84 the theory allows. Section 9 reaches the same conclusion: at prices that high, the promised improvement has no practical use.

Nor does partial coverage rescue it. At the two extremes the theory is settled: an anchor covering every class restores the classical guarantees at no extra cost (Proposition 5), and writing with no anchor at all has no bounded ratio (Theorem 4). Between them there is no theorem, only measurement, and the measurement is negative.

Before any run, E-L2-11 registered the prediction that below break-even coverage a covering write leaves pairs worse off than no write at all, and that is what happened: at coverage depth 64 the covering write left 0.0020 excess over the joint refit, while the unanchored baseline sat at 0.00026, indistinguishable from zero at a hundred classes (t = 0.56). Break-even coverage measured 128 per class, 1.28 times the store; the grid never reached that high, so 128 is a floor. Where coverage applies, it does beat size: a one-exemplar covering anchor left 0.0079 where an equal-sized non-covering anchor left 0.0440 (paired z = -7.7 over 75 rows). We also tried ranking which classes to cover; the rule performed at chance (Spearman 0.0058) and lost its registered bars. The middle is unresolved, and the submission says so directly.

Your first concern and Question 3: what the separation depends on. It depends on what a query is charged, and the submission states this beside the theorem. Theorem 4 charges the balanced-prior bill, and under it the separation holds. Under a one-sided charge the flood is free: a policy can steer the batch composition until the balanced error reaches 1/2 while every flooded-class query stays correct, and the ratio is bounded (Remark 9).

On the operator side, the separation binds the unanchored writer; anchoring and refitting are the escapes, and the paper prices both. For a general query weighting we have a sketch but no theorem, and we will not promise one in this window; for multiclass loss we have nothing yet. The experiments do carry the unarranged flood, in which classes arrive with heavy-tailed popularity and are queried in proportion: no policy exceeded its proved bound on those 15 streams, and on CIFAR-100 class means the unanchored ratio grows to 775.2 against the anchored 2.0.

Your third concern is correct. The paper prices the pieces separately: the anchored arm reduces to classical scheduling (Proposition 5), the mixed-operator bounds price mixing (Theorem 31 and Corollary 32), and the ledger prices which items belong together. A single policy that decides when to write, which items to combine, and which operator to use is an open problem.

Thank you very much for working through the merge theorem and Example 2, and for crediting the failure reports. If these answers change your view of the paper and your assessment, we would be very grateful.

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

Related papers

Discussion (0)

Sign in to comment.