Continual learning systems keep a small replay buffer, a memory of past training examples that is mixed back into training so the model does not overwrite what it learned before. Compressing that memory lets the buffer hold more examples, and it helps. But every existing method chooses how hard to compress each example by asking how good the picture looks after decompression. The model never looks at the picture. It only uses the gradient the example produces during replay. This proposal allocates buffer bytes the way cost-aware caches allocate memory: by value per byte. Here "value" means how faithfully a compressed example reproduces the training signal (the gradient) of the original.
The intuition is simple. Take two stored images that decompress with the same pixel error. One sits far from any decision boundary, so its gradient hardly changes under compression. The other sits on a fragile boundary between classes, and blurring it flips its gradient direction. A byte spent on the second image protects the model. The same byte spent on the first mostly buys cosmetics. We propose to measure this per example, cheaply. Examples then receive more bits, fewer bits, or none, and they are progressively demoted to lower bitrates instead of evicted outright. We test whether this beats reconstruction-driven compression under identical byte budgets.
Core Claim
Under a fixed buffer size in bytes, examples should be ranked by how well their compressed form preserves the model's replay gradient, per byte of storage, rather than by reconstruction error. Examples should also move down a ladder of bitrates as their marginal value per byte falls, rather than being deleted wholesale. We expect this to raise final accuracy over reconstruction-thresholded compression and over the best single global compression quality at the same storage.
This claim is falsifiable at its root. If reconstruction error already predicts gradient distortion almost perfectly across examples, the idea adds nothing. We measure that correlation first.
Where This Sits
The caching literature supplies the allocation principle. Towards Optimal Caching and Model Selection for Large Model Inference caches LLM queries by expected cost saved rather than frequency. It reports a 4.3× FLOPs reduction on Lambada, which shows that heterogeneous miss costs make hit-rate policies wasteful. Linear Elastic Caching via Ski Rental separates how much memory an item may occupy from how long it is kept. Cost-aware caching: optimizing cache provisioning and object placement in ICN shows that minimizing real cost means accepting a lower hit ratio. None of these touch learning systems. We reuse their central move: score each item by value per byte, and let items shrink or leave based on that score.
The continual-learning compression line motivates the gap and constrains the design. Scalable Recollections for Continual Lifelong Learning stores examples as fixed-length discrete codes from a categorical autoencoder. Every example gets the same bit budget. Memory Replay with Data Compression for Continual Learning (MRDC) trades JPEG quality against the number of stored examples. It tunes one quality level by feature-space coverage and warns of an "out-of-distribution cliff," where heavy compression suddenly wrecks accuracy. We take that cliff as a warning: per-example allocation must never push fragile examples over it. The closest prior work is Online Learned Continual Compression with Adaptive Quantization Modules (AQM). It stores each example at the lowest level of a hierarchical vector-quantized autoencoder whose reconstruction error stays under a threshold, and it evicts by reservoir sampling. AQM already has per-example variable bitrate. What differs here is the criterion (gradient fidelity rather than pixel fidelity), the joint byte-budget allocation across examples, and demotion in place of uniform eviction.
The gradient-centric line supplies the scoring signal. Learning to Learn without Forgetting by Maximizing Transfer and Minimizing Interference frames forgetting as conflicting gradients between new and replayed data. GCR: Gradient Coreset Based Replay Buffer Selection For Continual Learning selects buffer subsets whose gradients match the history's. Gradient-based Editing of Memory Examples for Online Task-free Continual Learning edits stored examples toward high-interference regions. All three treat each stored example as costing the same memory. We carry their gradient view into the storage-size decision. We also note their warning that inner-loop gradient computations are expensive, which is why our score is designed to be cheap.
Research Program
Each incoming example is compressed at insertion into a ladder of levels $l = 1, \dots, L$ with byte sizes $b_1 > \dots > b_L$. The ladder is built from JPEG qualities in the simple variant and from AQM's hierarchical codebook levels in the learned variant; level $0$ means not stored.
While the raw example $x$ is still available, we compute its last-layer gradient $g(x)$. For softmax cross-entropy this has a closed form: the outer product of the predicted-minus-true label vector with the penultimate features. It costs one forward pass per level. We then define the gradient distortion at level $l$ as
$$d(l) = \min\left(1, \frac{\lVert g(\hat{x}_l) - g(x) \rVert}{\lVert g(x) \rVert}\right),$$
where $\hat{x}_l$ is the decoded example and $d(0) = 1$.
The buffer then solves, approximately and online,
$$\max_{\{l_i\}} \sum_i w_i \,\big(1 - d_i(l_i)\big) \quad \text{subject to} \quad \sum_i b_{l_i} \le B,$$
where $B$ is the byte budget. The weight $w_i$ is $1$ in the base method, and in a variant it is the example's interference with the current stream, meaning the negative part of its gradient inner product with the incoming batch.
The solver is the greedy rule caches use for variable-size items. When space is needed, the system takes the single step down some example's ladder that loses the least weighted value per byte freed. That step may be a demotion to the next level or a final eviction.
Once the raw example is gone, distortions are re-estimated relative to the currently stored version. JPEG re-encoding and dropping levels of a hierarchical codebook both allow this. Scores are refreshed lazily on a random fraction of the buffer each step, which bounds overhead.
We will also check, on a held-out subset where raw data is kept, whether the last-layer proxy tracks full-network gradient distortion. Everything is task-free: nothing uses task boundaries.
Baselines
The naive reference is plain experience replay (ER) with raw images and reservoir sampling at the same byte budget, which therefore holds far fewer examples. Reported ER numbers vary with setup: 27.5% on disjoint CIFAR-10 in the AQM paper and 33.30% on Split CIFAR-10 in Gradient-based Editing of Memory Examples for Online Task-free Continual Learning. We therefore rerun ER in our own pipeline rather than quote it.
The strongest existing competitor for the online setting is AQM, because it already uses learned, per-example adaptive bitrate in a single-pass stream. It reports 43.5% accuracy on disjoint CIFAR-10, against 33.9% for JPEG compression, at equal storage. We run AQM's released design with our backbone, stream, and byte budget. We give its reconstruction threshold the same tuning budget as our method's hyperparameters, a matched number of validation-stream trials. Beating it means higher final average accuracy with lower forgetting, over at least five seeds and across a range of byte budgets, not just one.
For the offline class-incremental setting the strongest competitor is MRDC on top of LUCIR. It reports 70.53% average accuracy on ImageNet-sub with 25 phases, against 61.44% for LUCIR alone. We run it at identical storage.
A third baseline is the best single global JPEG quality chosen by oracle search on the test sequence. It is an upper bound on any uniform-quality policy.
Two ablations isolate the key ingredient. The first swaps our gradient-distortion score for reconstruction error while keeping the byte-budget greedy allocation and demotion. This shows whether the criterion or the allocation machinery carries the gain. The second keeps the gradient score but replaces demotion with direct eviction.
Why not just…?
Why not just use AQM's reconstruction threshold, since pixel error probably tracks gradient error anyway? This is the central threat, and we test it directly rather than argue it. Before any continual-learning run, we compute the per-example rank correlation between reconstruction error and gradient distortion at each ladder level on CIFAR-10 and mini-ImageNet. We report it separately for examples near and far from the model's decision boundary. If the correlation is uniformly very high, the proposal reduces to AQM plus a knapsack, and we would report that as the finding. The reconstruction-score ablation provides the end-to-end version of the same test.
Why not just tune one good global quality, as MRDC does? Per-example allocation could be a small refinement over a well-chosen single quality. The oracle global-quality baseline bounds what any uniform policy can reach. If our method cannot beat that oracle, per-example allocation is not worth its bookkeeping. MRDC's own out-of-distribution cliff suggests it should beat it: a global setting must stay conservative enough for the most fragile examples, which wastes bytes on robust ones.
Why not just give more bits to high-loss examples? Loss is cheaper than a gradient difference and may capture most of the "fragile boundary" signal. We include loss-proportional allocation under the same greedy solver as a baseline. Our score differs because it measures what compression destroys, not how hard an example is. A hard example whose gradient survives heavy compression should still be stored cheaply. If loss-based allocation matches ours, we would adopt it as the simpler method.
Why not just skip compression and train from scratch on a balanced raw buffer (GDumb), or fine-tune on the buffer at the end? Online Continual Learning in Image Classification: An Empirical Survey shows that GDumb is strong in class-incremental settings with large memory. The same survey shows that a final balanced fine-tuning pass (the "review trick") boosts replay methods substantially. Both are compatible with our buffer, so we will report GDumb with raw storage, and GDumb and review applied on top of each compressed buffer. This checks whether our gains survive those tricks. At small byte budgets, raw storage simply holds too few examples, which is where compression should matter most.
Proposed Experiments
The online, task-free evaluations use disjoint Split CIFAR-10, Split CIFAR-100 with 20 tasks, and Split mini-ImageNet in single-pass streams. The offline class-incremental evaluation uses ImageNet-sub with 25 phases and LUCIR, following MRDC. For each, we sweep the byte budget from the equivalent of 20 raw images per class down to 1 and plot final average accuracy and forgetting against bytes. The area under that curve is the headline metric. We also report wall-clock time and extra forward passes per stream step, so that any accuracy gain is weighed against the insertion-time scoring cost that GCR and GMED warn about.
Three checks decide the question. The first is the correlation study above, run before everything else. The second is the reconstruction-score ablation under identical allocation. If gradient scoring does not beat it by more than seed variance at small budgets, the core claim fails. The third is a diagnostic: counting how often the reconstruction-based policy stores examples below the level where their gradient flips sign. This quantifies the per-example version of MRDC's cliff and explains any gain we find.
A secondary check compares the last-layer proxy against full-network gradient distortion on the raw-kept subset. It tells us whether the cheap score is trustworthy enough to recommend.
References
- Towards Optimal Caching and Model Selection for Large Model Inference
- Linear Elastic Caching via Ski Rental
- Cost-aware caching: Optimizing cache provisioning and object placement in ICN
- Scalable Recollections for Continual Lifelong Learning
- Memory Replay with Data Compression for Continual Learning
- Online Learned Continual Compression with Adaptive Quantization Modules
- Learning to Learn without Forgetting by Maximizing Transfer and Minimizing Interference
- GCR: Gradient Coreset based Replay Buffer Selection for Continual Learning
- Gradient-based Editing of Memory Examples for Online Task-free Continual Learning
- Online continual learning in image classification: An empirical survey