Replay Methods › Experience Replay

Experience replay is the most direct response to catastrophic forgetting: save some examples from each task, and include them in the training batches for all future tasks. When the model trains on task $T_k$, it does not just minimize loss on the current task's data; it also minimizes loss on a small replay sample from every previous task.

The simplicity of this approach belies how much engineering goes into making it work well. The key design decisions revolve around three questions: which examples to store, how many to store, and how to integrate them into training. Each of these decisions has non-trivial consequences for forgetting, plasticity, and computational overhead. A buffer that is too small provides insufficient coverage; a buffer that stores unrepresentative examples may fail to anchor the critical regions of each task's decision boundary; a replay ratio that is too high slows learning on new tasks while one that is too low provides insufficient protection against forgetting.

The replay buffer is a data structure that stores a subset of training examples from past tasks. Its design involves three fundamental questions:

• What to store: Which examples should be retained from each task?
• How much to store: What is the total buffer capacity, and how is it divided across tasks?
• How to use it: When and how should stored examples be mixed into training?

The simplest design answers all three questions with uniform choices: store random examples, divide capacity equally across tasks, and mix replay examples with current task examples in each training batch. This baseline is surprisingly effective and provides a clear point of comparison for more sophisticated approaches.

Formally, let $\mathcal{M}$ denote the replay buffer with total capacity $C$. After observing $k$ tasks, the buffer holds at most $\lfloor C/k \rfloor$ examples from each task. When training on task $T_{k+1}$, each mini-batch contains both examples from the current task and examples randomly sampled from $\mathcal{M}$.

The capacity constraint creates a real tension as the number of tasks grows. With 10 tasks and a buffer of 500 examples, each task gets 50 examples on average. If each task originally had 5,000 training examples, the buffer retains only 1% of each task's information. This compression is not free: the fewer examples the buffer holds for a given task, the less accurately it represents that task's distribution, and the less effective replay becomes at preventing forgetting. The relationship between buffer size and forgetting prevention is roughly logarithmic: doubling the buffer from 50 to 100 examples per task has a larger effect than doubling it from 500 to 1000.

The buffer retains 150 examples total after task 2 has been added. Because each task contributes 150 examples and the buffer evicts the oldest on overflow, the earlier task is gradually replaced. This naive eviction strategy highlights a real problem: with many tasks and a fixed buffer, each individual task is represented by increasingly few examples.

This behavior reflects a fundamental tension between breadth and depth of memory, rather than a software bug. A buffer that tries to remember everything retains so few examples per task that each task's distribution is poorly approximated. A buffer that retains many examples per task quickly runs out of capacity as tasks accumulate. There is no free lunch: you must decide how to allocate a fixed memory budget across a potentially unbounded task sequence.

The naive buffer above overwrites old examples when new ones arrive, which biases the buffer toward recently seen tasks. A better approach is reservoir sampling, which ensures that every example from the entire task sequence has an equal probability of being retained in the buffer at any point.

The algorithm maintains the invariant that after observing $n$ total examples, each one is in the buffer with probability $C/n$, where $C$ is the buffer capacity. When a new example arrives, it replaces a randomly selected existing buffer slot with probability $C/n$:

$$P(\text{new example is stored}) = \frac{C}{n}$$ $$P(\text{specific buffer slot is replaced} \mid \text{new example is stored}) = \frac{1}{C}$$

where:

• $C$: the total buffer capacity
• $n$: the number of examples seen so far (across all tasks)
• $C/n$: the probability that any individual example survives to the current point, which decreases as more examples are seen

The key insight is that this probability decreases over time in a principled way. Early examples are retained with high initial probability but face a growing risk of displacement. Later examples enter with lower probability but are at lower risk of subsequent eviction. The result is a statistically unbiased sample of the entire training history.

To see why the invariant holds, consider what happens when example number $n+1$ arrives. Each of the $n$ previously seen examples currently has probability $C/n$ of being in the buffer (by the invariant). After processing the new example:

• With probability $C/(n+1)$, the new example is stored and replaces one of the $C$ buffer slots uniformly at random.
• Each existing buffer example is evicted with probability $(C/(n+1)) \times (1/C) = 1/(n+1)$.
• Each existing buffer example survives the step with probability $1 - 1/(n+1) = n/(n+1)$.
• The probability that any previously seen example is in the buffer after the update is $(C/n) \times (n/(n+1)) = C/(n+1)$.

This is exactly the target probability for $n+1$ total examples seen. The invariant is maintained inductively. No explicit knowledge of task boundaries is needed, and no task receives preferential treatment regardless of the order examples arrive.

Reservoir sampling achieves a roughly equal distribution across all three tasks despite the buffer capacity being half the size of each individual task's dataset. The slight imbalance is expected statistical noise. No example stream has preferential treatment regardless of the order tasks were encountered.

Reservoir sampling is most appropriate when tasks contribute roughly equal numbers of training examples and when unbiased coverage of all historical data is the goal. In practice, task sizes often differ substantially. If task 1 has 10,000 examples and task 2 has only 100, reservoir sampling will allocate buffer slots proportionally to task size, meaning task 2 receives very few examples. For such imbalanced settings, task-aware allocation strategies that explicitly balance the number of stored examples per task often work better.

Random reservoir sampling provides an unbiased estimate of the task distribution, but it may not be the most effective use of limited buffer capacity. The buffer contains only a small fraction of each task's examples, and which examples are retained can significantly affect learning efficiency. Two tasks with identical class distributions but different example choices can show dramatically different forgetting rates.

The core question is: given a budget of $k$ examples to store from a task with $N$ training examples, which $k$ should you keep? The answer depends on what you believe replay is protecting against. If replay protects the model's overall accuracy on a task, representative examples covering the full class distribution are ideal. If replay protects the model's decision boundary, examples near the boundary are most critical. If replay protects the model's feature representations, examples that activate diverse feature patterns are most valuable.

Several principled selection strategies have been proposed, each encoding different assumptions about what makes an example valuable to replay:

Herding (Prototype-based selection) selects examples whose mean feature vector best approximates the true class mean. After computing embeddings for all examples in a task, the algorithm greedily adds examples that minimize the distance between the selected subset's mean and the full dataset's mean. This ensures the stored examples are representative of each class's central tendency. Herding was introduced in the context of iCaRL, an early and influential class-incremental learning system, where maintaining accurate class means was critical for the nearest-class-mean classifier used at inference time. The greedy algorithm is computationally cheap: it requires one pass to compute the class mean, and then $k$ greedy steps each requiring a single distance computation per candidate.

The greedy herding procedure can be written out explicitly. Let $\mu$ be the true mean embedding of class $c$ across all $N$ training examples. Let $\mathcal{S}$ be the set of selected examples (initially empty) and $P$ be the pool of candidates. At each step:

$$p^* = \arg\min_{p \in P} \left\| \frac{1}{|\mathcal{S}| + 1} \left( \sum_{x \in \mathcal{S}} \phi(x) + \phi(p) \right) - \mu \right\|_2$$

where $\phi(x)$ is the embedding of example $x$. After selecting $p^*$, it is moved from $P$ to $\mathcal{S}$ and the process repeats. After $k$ steps, $\mathcal{S}$ contains the $k$ examples whose collective mean is closest to $\mu$.

Gradient-based selection keeps examples whose gradients are most aligned with the average gradient of the full task dataset. The idea is that these examples carry the most informative training signal, so replaying them exerts a force similar to training on the full dataset. Computing gradients for every candidate example is expensive, but approximate methods exist. One practical approximation computes a small representative subset of the full-data gradient and selects examples whose individual gradients have the highest cosine similarity to it. Gradient-based selection is conceptually more expensive than herding but can outperform it when class distributions are complex or multi-modal.

Uncertainty-based selection keeps examples the model is currently most uncertain about, often measured by prediction entropy or margin. High-uncertainty examples are close to the decision boundary and most likely to be forgotten or misclassified under parameter drift. The intuition is that the boundary is the most fragile part of the classifier: small parameter changes can flip predictions for examples near the boundary, while interior examples (far from any boundary) resist moderate perturbations. By concentrating the buffer on boundary examples, uncertainty selection maximizes replay's protective effect on classification accuracy.

A practical consideration: uncertainty-based selection measures uncertainty at the time of selection, using the model's current parameters. As the model continues training on new tasks, the decision boundary shifts, and examples that were uncertain during selection may no longer be boundary-proximal. This temporal mismatch limits the effectiveness of uncertainty selection in long task sequences. Some methods address this by periodically re-evaluating and replacing buffer contents.

Each strategy captures a different aspect of the task distribution. Random selection treats all examples equally, producing a buffer that mirrors the overall class proportions but may under-represent the decision boundary. Herding selection clusters around class centroids, giving the replay buffer a strong signal about each class's core characteristics. Uncertainty selection concentrates entirely on the decision boundary region, making it aggressive at preventing boundary drift but at the cost of losing information about the broader class structure.

Which strategy wins depends on the task. For class-incremental learning, where the model must distinguish between all classes seen so far using a single classifier, herding tends to work best because accurate class mean representations are critical. For domain-incremental learning, where the output structure remains fixed but the input distribution shifts, uncertainty-based selection often provides better protection for the classifier boundary. Random selection is a reliable baseline that avoids the overhead of embedding computation or gradient evaluation.

How replay examples are combined with current task data during training affects both the efficiency and stability of continual learning. The two main strategies are interleaved training and alternating batches.

In interleaved training, each mini-batch contains a mix of current task examples and replay samples. If the current task batch size is $B$ and the replay sample size is $R$, then each gradient update uses $B + R$ examples drawn from both distributions simultaneously:

$$\mathcal{L}_{\text{total}} = \frac{1}{B + R} \left( \sum_{(x, y) \in \mathcal{B}_{\text{current}}} \ell(f_\theta(x), y) + \sum_{(x, y) \in \mathcal{B}_{\text{replay}}} \ell(f_\theta(x), y) \right)$$

where:

• $\mathcal{B}_{\text{current}}$: the mini-batch of current task examples
• $\mathcal{B}_{\text{replay}}$: the mini-batch sampled from the replay buffer
• $\ell$: the per-example task loss (cross-entropy for classification)
• $\theta$: the model parameters being updated

This uniform weighting treats replay examples the same as current examples. Some variants apply a separate weight $\lambda$ to the replay loss, allowing you to control how aggressively the model is pulled back toward past tasks. Higher $\lambda$ prioritizes stability; lower $\lambda$ allows more plasticity for the new task.

In alternating batches, the training loop alternates between steps on the current task and steps on the replay buffer. This can be useful when the current task and past tasks have very different data modalities or loss scales, and blending them into a single batch would produce unstable gradients. Alternating steps decouple the two optimization signals, which can stabilize training at the cost of slightly slower convergence on each individual task.

The replay_ratio parameter controls the balance between stability and plasticity. A ratio of 0 means pure gradient descent on the current task (maximum plasticity, maximum forgetting). A ratio approaching 1 means the model spends most of its capacity on replayed past tasks (maximum stability, slow learning on new tasks). In practice, ratios between 0.25 and 0.5 work well, though the optimal value depends on task difficulty and the degree of task similarity.

One practical refinement is to use class-balanced sampling from the buffer rather than uniform sampling. If the buffer contains 80 examples from task 1 (class 0 and 1) and 20 from task 2, uniform sampling will over-represent task 1 in each replay batch. Class-balanced sampling ensures each class seen so far contributes an equal number of examples per batch, which is particularly important for class-incremental settings where the classification head must distinguish between a growing set of classes.

A notable variant of experience replay is Dark Experience Replay (DER), which augments the stored examples with the model's logit outputs at the time the examples were added to the buffer. Rather than training on hard labels from the buffer, the model is trained to reproduce its own previous logit distributions on replayed inputs. This is a form of self-distillation: the current model is regularized to maintain consistent output distributions on past examples, not just correct predictions.

The DER loss for a replayed example $(x, z_{\text{stored}})$ where $z_{\text{stored}}$ are the logits stored at insertion time is:

$$\mathcal{L}_{\text{DER}} = \frac{1}{|\mathcal{B}_{\text{replay}}|} \sum_{(x, z_{\text{stored}}) \in \mathcal{B}_{\text{replay}}} \| f_\theta(x) - z_{\text{stored}} \|_2^2$$

The key insight is that stored logits carry more information than hard labels. A logit vector $[2.3, -1.1, 0.4]$ tells you that the model predicted class 0, how confident it was, and which alternatives it considered plausible. Matching the full logit distribution preserves the final prediction and the internal representation structure of the model at the time of storage. This soft constraint is more forgiving of small parameter changes (the model can drift slightly without penalty) while still preventing large representation shifts.