The Lie of the Average: How Class Incremental Learning Evaluation Deceives You?

This paper argues that mainstream Class Incremental Learning evaluation protocols are biased due to insufficient sequence sampling, and proposes EDGE, a new protocol that leverages inter-task similarity to identify extreme sequences for accurately characterizing the full performance distribution.

The Gist

🚗 The Problem: The "Average" Driver is a Lie

Imagine you are hiring a driver for a very important job: navigating a city where the traffic rules change every day. Sometimes the streets are wide and empty; other times, they are narrow, filled with construction, and confusing.

In the world of Class Incremental Learning (CIL), the "driver" is an AI model, and the "traffic rules" are new categories of things it needs to learn (like recognizing a new type of animal or a new brand of car). The AI must learn these new things without forgetting the old ones.

The Current Mistake (The RS Protocol):
Right now, scientists test these AI drivers by asking them to drive on just three random routes.

• Route A: Easy, sunny day.
• Route B: A bit rainy.
• Route C: Some traffic.

They then calculate the average speed of the driver across these three trips and say, "Great! This driver is safe and fast!"

The Paper's Warning:
The authors say this is a lie.
Just because a driver is good on three random routes doesn't mean they can handle every route. There might be a specific, nightmare route (a "Hard Sequence") where the driver gets completely lost and crashes. Conversely, there might be a "Dream Route" where they drive perfectly.

If you only look at the average, you might hire a driver who looks great on paper but fails catastrophically in a real-world emergency. The current method hides the worst-case scenarios and underestimates how much the driver's performance can swing.

🔍 The Solution: EDGE (The "Extreme" Test)

The authors propose a new way to test drivers called EDGE. Instead of picking three random routes, EDGE uses a smart strategy to find the three most important routes:

1. The Nightmare Route (Hard Sequence): A route designed to be as confusing as possible. It forces the driver to make the hardest possible turns between similar-looking streets.
2. The Dream Route (Easy Sequence): A route designed to be as smooth as possible, grouping similar streets together so the driver never gets confused.
3. The Normal Route (Medium Sequence): A standard, random route.

How does it find these routes?
The AI uses a "semantic map" (like a GPS that understands the meaning of street names).

• To make a Hard Route, it groups similar-looking things together in the same task (e.g., teaching the AI to distinguish between an Apple and a Pear in the same lesson). This is hard because they look alike.
• To make an Easy Route, it separates similar things into different lessons (e.g., teaching Apples in Lesson 1 and Pears in Lesson 10). This is easy because the AI has time to reset.

📊 The Results: Why It Matters

When the authors tested this new method, they found shocking differences:

• The "Average" Lie: A model might have an "Average Score" of 85%. The old method (Random Sampling) would say, "This model is safe!"
• The EDGE Reality: The EDGE method reveals that on the "Nightmare Route," that same model drops to 70%. On the "Dream Route," it hits 95%.

Why is this a big deal?
If you are building a self-driving car, you don't care about the average performance. You care about the worst-case scenario. If the car crashes 10% of the time because it got confused by a specific sequence of events, an "average" score of 85% is dangerous.

🧠 The Big Takeaway

This paper argues that we need to stop judging AI models based on a few lucky random tests. Instead, we should stress-test them with the hardest possible scenarios and the easiest possible scenarios to get a true picture of their reliability.

Think of it like this:

• Old Way: Testing a parachute by jumping out of a plane three times on a calm day and saying, "It works 100% of the time!"
• EDGE Way: Testing the parachute by simulating a calm day, a stormy day, and a day with a broken parachute, just to see if it really saves you when things go wrong.

By using EDGE, researchers can finally see the full range of an AI's abilities, ensuring that the models we deploy in the real world are truly robust and safe.

Technical Summary

1. Problem Statement

Class Incremental Learning (CIL) requires models to learn new classes sequentially without forgetting previous ones. A critical challenge in CIL is that model performance is highly sensitive to the order in which classes arrive.

• The Issue: The number of possible class sequences grows factorially ($O(N!)$), making exhaustive evaluation impossible.
• Current Practice: Mainstream evaluation protocols use Random Sampling (RS), typically testing only 3–5 randomly generated class sequences and reporting the mean and standard deviation.
• The Flaw: The authors argue that RS fails to capture the true performance distribution. It systematically overestimates the mean and severely underestimates the variance, leading to biased conclusions. A model might appear robust based on an average score but fail catastrophically in specific "extreme" sequences (e.g., dropping from 85% to 70% accuracy), posing risks for real-world deployment (e.g., autonomous driving).

2. Methodology: EDGE Protocol

The paper proposes EDGE (Extreme case–based Distribution & Generalization Evaluation), a protocol designed to approximate the ground-truth performance distribution by explicitly sampling extreme cases.

A. Theoretical Foundation

• Combinatorial Explosion: The authors prove that the space of possible sequences is too vast for random sampling to be representative (Lemma 1).
• Extreme Sequence Importance: Theoretical analysis (Theorem 2) demonstrates that incorporating known extreme sequences (hardest and easiest) significantly reduces the sample complexity required to estimate the true distribution mean and variance compared to uniform random sampling.
• Similarity-Performance Correlation: The paper establishes a theoretical link (Theorem 3) between inter-task similarity and generalization error.
  • Low Inter-Task Similarity: Adjacent tasks are dissimilar, causing large parameter shifts and high forgetting (Hard Sequence).
  • High Inter-Task Similarity: Adjacent tasks are similar, facilitating transfer and reducing forgetting (Easy Sequence).
  • Empirical results confirm a strong positive correlation between inter-task similarity and model accuracy.

B. The EDGE Algorithm

EDGE constructs three representative sequences to approximate the distribution:

1. Hard Sequence (Minimizing Similarity):
   • Uses a pre-trained CLIP text encoder to embed class labels into semantic vectors.
   • Constructs a similarity matrix between all classes.
   • Uses hierarchical clustering to group semantically similar classes into the same task (maximizing intra-task similarity, minimizing inter-task similarity).
   • Greedily orders tasks to maximize the dissimilarity between consecutive tasks.
2. Easy Sequence (Maximizing Similarity):
   • Inversely groups semantically similar classes into different tasks.
   • Orders tasks to maximize the similarity between consecutive tasks.
3. Medium Sequence:
   • A randomly sampled sequence to represent the central tendency.

The final evaluation aggregates the performance on these three sequences to estimate the distribution's boundaries (min/max) and variance more accurately than RS.

3. Key Contributions

1. Critical Analysis of RS: The paper provides both theoretical proofs and empirical evidence that the standard Random Sampling protocol yields biased estimates, failing to capture the true upper and lower bounds of CIL performance.
2. EDGE Framework: Introduction of a novel evaluation protocol that adaptively identifies extreme sequences based on inter-task semantic similarity, offering a sample-efficient approximation of the ground-truth distribution.
3. Theoretical Insight: Formalization of the relationship between inter-task similarity and generalization error, proving that extreme sequences are crucial for reliable evaluation.
4. Actionable Insights: Demonstration that different CIL methods may converge to similar worst-case performance under difficult sequences, suggesting that task difficulty is often a larger bottleneck than architectural differences.

4. Experimental Results

The authors conducted extensive experiments on CIFAR-100, ImageNet-R, and CUB-200, comparing EDGE against the standard RS protocol.

• Enumerable Experiments (Ground Truth): On a subset of 6 classes (90 possible sequences), the authors exhaustively evaluated all permutations to establish the "True Distribution."
  • Accuracy of Bounds: EDGE's estimated min/max bounds were significantly closer to the ground truth than RS. RS often overestimated the lower bound (hiding poor performance) and underestimated the variance.
  • Distribution Distance: EDGE achieved lower Jensen-Shannon Divergence (JSD) and Wasserstein Distance compared to RS, indicating a better fit to the true distribution.
• Large-Scale Benchmarks:
  • EDGE consistently identified performance extremes that RS missed. For example, on ImageNet-R, RS estimated a lower bound of ~39% for CODA-Prompt, while EDGE revealed a true lower bound of ~21%.
  • Model Selection: Rankings of models changed significantly when evaluated with EDGE. Methods that appeared stable under RS showed high variance under EDGE, revealing hidden fragility.
• Robustness: EDGE remained effective across different backbones (ResNet, ViT) and CLIP encoder sizes.

5. Significance and Impact

• Paradigm Shift: The paper argues that CIL evaluation should move from "point estimates" (average accuracy) to "distributional characterization" (capturing the full range of performance).
• Safety and Reliability: By exposing the "worst-case" scenarios, EDGE prevents the deployment of models that might fail in specific, real-world class arrival orders, which is critical for safety-critical applications like autonomous driving.
• Efficiency: EDGE achieves better distribution estimation with fewer samples (3 sequences) compared to the massive number of random samples required to theoretically approximate the same distribution.
• Open Source: The authors released the code and integrated the protocol into popular CIL toolboxes (PILOT and PyCIL), facilitating immediate adoption by the community.

In summary, EDGE exposes the "lie of the average" in CIL research, providing a rigorous, theoretically grounded, and empirically validated framework to evaluate model robustness against the inherent unpredictability of class arrival orders.