Trustworthy Machine Learning via Memorization and the Granular Long-Tail: A Survey on Interactions, Tradeoffs, and Beyond

Qiongxiu Li, Xiaoyu Luo, Yiyi Chen, Johannes BjervaarXiv 2025 · OpenReview

Introduction

In the pursuit of "Trustworthy AI," researchers often treat privacy, fairness, and robustness as independent, harmonious goals. However, this survey argues that these pillars frequently exist in a state of tension, mediated by a misunderstood phenomenon: memorization. Far from being a mere "bug" or a sign of overfitting, memorization is a fundamental necessity for models to learn from the "long tail" of real-world data. By failing to distinguish between rare, valid data and random noise, current defense mechanisms often act as blunt instruments that inadvertently compromise one aspect of trustworthiness to protect another.

A New Framework for Data Granularity

To navigate these trade-offs, the authors propose a Hierarchical Granularity Framework. This system categorizes data into three distinct levels, moving beyond the simple binary of "clean" versus "noisy" data.

Table mapping data granularity levels to existing literature concepts and memorization perspectives.
  1. Macro-Level (Class): This addresses traditional class imbalance, such as having thousands of images of common cats but only a handful of rare wildcats.
  2. Meso-Level (Sample): This focuses on atypicality within a class. These are valid, correctly labeled samples that possess rare features or high within-class variation.
  3. Micro-Level (Noise): This refers to truly corrupted data, such as mislabeled images or feature corruption.

Distinguishing between the Meso and Micro levels is critical. As shown in the visual benchmarks from CIFAR-10 and CIFAR-100, an atypical sample (like a lobster obscured by background clutter) is still a valid representation of the class, whereas noise (a crab labeled as a lobster) is not.

Visualizing the difference between typical samples, atypical samples, and noise across CIFAR-10 and CIFAR-100 classes.

The Duality of Memorization

The paper posits that memorization is both a "necessity and a liability." Mathematically, memorization is required to achieve near-optimal generalization on long-tailed distributions. If a model does not memorize the rare, atypical samples at the Meso-level, it cannot perform accurately on those minority cases. However, this same memorization becomes a liability for privacy, as it makes those specific, rare individuals identifiable and vulnerable to extraction or membership inference attacks.

The Trustworthiness Paradox: Trade-offs and Interactions

The core of the paper explores how interventions intended to improve one pillar of trustworthiness can degrade others:

  • Privacy vs. Fairness: Differential Privacy (DP) mechanisms are designed to suppress the memorization of individual samples. However, DP often "forgets" high-curvature, atypical samples first. This leads to a "poor become poorer" effect, where the model's accuracy on underrepresented subgroups (fairness) plummets in the name of protecting privacy.
  • Robustness vs. Privacy: Adversarial Training (AT) aims to create smoother decision boundaries to resist attacks. To do this, models are often forced to memorize "harder" samples more deeply. This increased memorization makes robust models significantly more vulnerable to Membership Inference Attacks (MIA), creating a direct conflict between robustness and privacy.
  • Fairness vs. Privacy: Conversely, enhancing fairness often requires the model to memorize more specific details about minority subgroups to ensure they are represented. This increased detail inherently increases the risk of privacy leaks for those specific groups.

Conclusion and Future Directions

The authors conclude that the current "one-size-fits-all" approach to trustworthy ML is insufficient. Because atypical samples act as "memorization amplifiers"—being the most likely to be leaked, poisoned, or exploited—we need more surgical tools.

Future research must focus on developing "granular metrics" that can reliably isolate noise from valid atypicality. By understanding the specific role of memorization at each level of the data hierarchy, researchers can move toward safety interventions that protect privacy without silencing the rare voices necessary for a fair and robust model.

Summary updated

Abstract

The role of memorization in machine learning (ML) has garnered significant attention, particularly as modern models are empirically observed to memorize fragments of training data. Previous theoretical analyses, such as Feldman's seminal work, attribute memorization to the prevalence of long-tail distributions in training data, proving it unavoidable for samples that lie in the tail of the distribution. However, the intersection of memorization and trustworthy ML research reveals critical gaps. While prior research in memorization in trustworthy ML has solely focused on class imbalance, recent work starts to differentiate class-level rarity from atypical samples, which are valid and rare intra-class instances. However, a critical research gap remains: current frameworks conflate atypical samples with noisy and erroneous data, neglecting their divergent impacts on fairness, robustness, and privacy. In this work, we conduct a thorough survey of existing research and their findings on trustworthy ML and the role of memorization. More and beyond, we identify and highlight uncharted gaps and propose new revenues in this research direction. Since existing theoretical and empirical analyses lack the nuances to disentangle memorization's duality as both a necessity and a liability, we formalize three-level long-tail granularity - class imbalance, atypicality, and noise - to reveal how current frameworks misapply these levels, perpetuating flawed solutions. By systematizing this granularity, we draw a roadmap for future research. Trustworthy ML must reconcile the nuanced trade-offs between memorizing atypicality for fairness assurance and suppressing noise for robustness and privacy guarantee. Redefining memorization via this granularity reshapes the theoretical foundation for trustworthy ML, and further affords an empirical prerequisite for models that align performance with societal trust.
BibTeX
@misc{li2025trustworthy,
  author = {Qiongxiu Li and Xiaoyu Luo and Yiyi Chen and Johannes Bjerva},
  title = {{Trustworthy Machine Learning via Memorization and the Granular Long-Tail: A Survey on Interactions, Tradeoffs, and Beyond}},
  year = {2025},
  eprint = {2503.07501},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2503.07501},
}
Figure