No Free Delivery Service: Epistemic limits of passive data collection in complex social systems

Maximilian Nickel

Introduction

The rapid advancement of modern Artificial Intelligence relies heavily on the "train-test" paradigm: models are trained on a large dataset and validated on a held-out test set. If the test error is low, we assume the model will perform well in the real world. However, this foundational assumption is mathematically invalid when applied to data passively collected from complex social systems, such as the internet or recommender platforms. Because these systems naturally produce heavy-tailed distributions, we often lack the structural "connectivity" in our data required to bound a model's true error. Consequently, we cannot truly know if our deployed models are reliable, safe, or fair.

The Core Problem: Active vs. Passive Data Collection

In traditional machine learning and statistics, data is often assumed to be "actively" sampled—like a scientist carefully selecting independent and identically distributed (i.i.d.) subjects for a clinical trial. Under these conditions, the laws of statistics guarantee that test error closely approximates true real-world error.

Modern AI, including Large Language Models (LLMs) and recommender systems, operates differently. It relies on passive data collection, scraping whatever data naturally occurs. This data is generated by complex social systems governed by popularity bias, feedback loops, and network effects. The fundamental epistemic question is: Given how we currently collect data, can we actually know whether a model performs well? For many critical tasks, the answer is a resounding "no."

The epistemic framework of model validation, illustrating how assumptions and sample locations determine whether true risk can be bounded across possible worlds.

The Mathematical Limit: K-Cores and Impossibility

To understand why validation fails, the paper utilizes matrix completion theory and the concept of k-connectivity.

Imagine a graph of interactions, such as users rating movies. A "k-core" is a subset of this graph where every member has at least k interactions. The paper introduces a formal Impossibility Theorem: if the complexity of the underlying system (represented by the mathematical rank of the "true world" matrix) exceeds the k-connectivity of the sample data, validation is impossible.

In these scenarios, there are infinitely many "possible worlds" that perfectly fit the observed training and test data but behave wildly differently on unseen data. If your data isn't sufficiently connected (low k-core), you literally cannot distinguish between a model that has learned underlying rules and one that has merely memorized a specific, narrow path through the dataset.

The Scaling Myth and Heavy-Tailed Reality

A common assumption in modern AI is that simply scaling up—collecting more data—will eventually solve generalization issues. However, passive data collection in social systems almost always results in heavy-tailed (e.g., Pareto) distributions. A few items or users get massive attention, while the vast majority reside in the "long tail" with almost no interactions.

Heavy-tailed observation distributions in the MovieLens 100k recommender dataset and the FB15k-237 knowledge graph dataset.

Because of these power-law dynamics, the amount of data needed to reach a "valid" k-core state for the long tail grows polynomially or even linearly with the size of the domain. The paper demonstrates this inefficiency mathematically: to ensure a valid test setting for a random node in a large system (e.g., 10^7 entities), the lower bound for required samples is roughly 2 × 10^21. This number is far beyond any current or foreseeable dataset, making it practically impossible to "catch up" via passive scraping alone.

Hidden Unfairness in Validation

This epistemic limit also introduces severe, hidden fairness issues. Validation validity is not distributed equally across demographics.

Using the classic MovieLens 100k benchmark, the author demonstrates how this plays out empirically. For a model of moderate complexity (rank 60), the mathematical requirements for test validity held for 67% of "technicians" but only 14% of "homemakers."

This creates a dangerous illusion: an AI system might boast a high average test score, leading developers to believe it works for everyone. In reality, the system's performance for specific marginalized or less-active groups remains mathematically unknowable. The test set is effectively lying by omission.

Conclusion and Future Directions

The title "No Free Delivery" is a nod to the famous "No Free Lunch" theorems. It emphasizes that social systems do not automatically deliver valid validation data for free. The structural holes created by passive data collection cannot be bridged by math or massive scaling without introducing strong, often unverified assumptions.

To build truly reliable and fair AI, the field must move beyond passive scraping. The paper advocates for a shift toward participatory data curation and open science. Instead of hoping that more data will magically fill the gaps, we must actively and intentionally sample the "long tail" to build the k-cores necessary for rigorous, mathematically sound model validation.

Summary updated

Abstract

Rapid model validation via the train-test paradigm has been a key driver for the breathtaking progress in machine learning and AI. However, modern AI systems often depend on a combination of tasks and data collection practices that violate all assumptions ensuring test validity. Yet, without rigorous model validation we cannot ensure the intended outcomes of deployed AI systems, including positive social impact, nor continue to advance AI research in a scientifically sound way. In this paper, I will show that for widely considered inference settings in complex social systems the train-test paradigm does not only lack a justification but is indeed invalid for any risk estimator, including counterfactual and causal estimators, with high probability. These formal impossibility results highlight a fundamental epistemic issue, i.e., that for key tasks in modern AI we cannot know whether models are valid under current data collection practices. Importantly, this includes variants of both recommender systems and reasoning via large language models, and neither naïve scaling nor limited benchmarks are suited to address this issue. I am illustrating these results via the widely used MovieLens benchmark and conclude by discussing the implications of these results for AI in social systems, including possible remedies such as participatory data curation and open science.
BibTeX
@inproceedings{nickel2024no,
  author = {Maximilian Nickel},
  title = {{No Free Delivery Service: Epistemic limits of passive data collection in complex social systems}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2024},
  url = {https://openreview.net/forum?id=XZ0fpoAKEB},
}
Figure