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

Maximilian Nickel

REVIEW 5 major objections 6 minor 2 references

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

T0 review · 5 major / 6 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Formal proof: train-test evaluation cannot certify models on most social-system data

desk verdict The paper's core impossibility claim is not supported because its key lemma is false, but the framing and the MovieLens underspecification experiment are worth a look. read the letter →

arxiv 2411.13653 v1 pith:HCACXK7X submitted 2024-11-20 cs.AI stat.ML

Maximilian Nickel This is my paper · ORCID

classification cs.AIstat.ML MSC 68Q3268T0568R10

keywords train-testvaliditypassivedatacollectioncomplexsocialsystemsimpossibilitytheoremrecommenderquestionansweringlow-rankmatrixcompletionk-core

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper tries to establish that the standard train-test way of validating machine learning models cannot be trusted when data are passively collected from social systems such as recommender platforms or web corpora. The claim is specifically that, under minimal assumptions about the underlying world (low-rank structure, uniform target distribution, uniform prior over possible worlds), no risk estimator — including counterfactual or causal reweighted estimators — can certify performance on most users, items, or facts. The reason is a combination of biased sampling and heavy-tailed observation graphs: if the observed graph is not sufficiently connected, many different low-rank worlds explain the data equally well and differ wildly elsewhere, so any test-set estimate has probability zero of being close to the true risk. If correct, this means current evaluation practice for large language model reasoning and recommender systems cannot tell us whether models work on the full intended domain, and naive scaling or small benchmarks cannot fix it.

What carries the argument

The central object is the sample graph $G=(X_1,X_2,S)$, the bipartite graph of observed interactions, together with its $k$-core: the maximal subgraph in which every vertex has degree at least $k$, with a graph called $k$-connected when every vertex lies in its $k$-core. The argument represents a possible world as a matrix $\mathbf{F}$, assumes the world has rank at most $k$, and shows (Lemma 1, via matrix-completion results) that when $S$ is not $k$-connected, the set $\mathcal{F}$ of rank-$k$ worlds consistent with the observations is a non-empty vector space. That vector-space structure carries the proof: a volume argument over the uniform distribution on $\mathcal{F}$ shows the probability of small risk tends to zero, and the generalized Pythagorean theorem for Bregman divergences handles hypotheses outside $\mathcal{F}$. The power-law degree assumption then bounds how many nodes can lie in the $k$-core, giving the decay in Theorem 1.

What would settle it

Search for a sample graph and rank bound $k$ where the graph is not $k$-connected yet the feasible set of rank-at-most-$k$ matrices matching the observed entries is not closed under addition and scalar multiplication; finding one refutes Lemma 1 and with it Theorem 1. Alternatively, exhibit a passive sampling scheme with heavy-tailed degrees where a train-test estimator provably bounds true risk on the uniform target despite the graph not being $k$-connected.

Watch

Extended reading notes

Core claim

The paper's central claim is a formal impossibility result: for inference settings where data are passively collected from a complex social system, the train-test paradigm is invalid for essentially the whole system under ontological parsimony. Concretely, when the sample graph is not $k$-connected and the world is modeled as a rank-$k$ matrix, the set of possible worlds consistent with the data is a vector space; drawing a world uniformly from that space, the probability that any test-based risk estimate lies within $\epsilon$ of the true risk is zero for any hypothesis class and any risk estimator. Theorem 1 converts this into a scaling statement: the expected number of nodes for which validity can hold decays like a power law in the rank $k$, i.e. $\mathbb{E}[V_i] \le n_i u(k) k^{-\alpha_i}$. The paper shows this applies to recommender systems and to symbolic reasoning and question answering over factoid triples, and illustrates it empirically on MovieLens, where different rank-50 worlds fit the observed ratings but disagree on most unobserved entries. It also argues that neither scaling data collection nor limited benchmarks can overcome the gap.

Load-bearing premise

The proof hinges on Lemma 1's claim that the set of rank-at-most-$k$ worlds matching the observed data is a non-empty vector space whenever the sample graph is not $k$-connected; if that set is only a union of subspaces, which is typical for low-rank matrix sets, the volume argument collapses.

Editorial extensions

If this is right

Train-test evaluation on passively collected data cannot certify performance on the uniform target distribution for most users, items, or facts, for any risk estimator.
This holds for recommender systems and for reasoning and question answering over factoid triples, independent of whether the reasoning is performed by a large language model.
Naive scaling is prohibitively inefficient: the expected number of draws from the sampling distribution needed to reach a valid test setting scales at least polynomially in the domain size.
Limited benchmarks cannot extrapolate either, since covering the nodes outside sufficiently large $k$-cores requires linearly many additional curated observations.
Because $k$-core membership varies by demographic group, test validity and therefore measured model quality can vary sharply across groups, with fairness consequences.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

One extension I would draw is that benchmark leaderboards for recommender systems and question answering may be reporting fit to the sampling distribution rather than to the intended uniform task, so cross-benchmark comparisons should be treated cautiously.
A testable extension would be to restrict evaluation to the $k$-core of the sample graph and check whether model rankings stabilize there; the paper's theory predicts they should, while full-graph rankings should not.
I would also conjecture that the impossibility result extends qualitatively to feasible sets that are unions of low-dimensional varieties rather than vector spaces, though the volume-based proof would need a different geometric tool; the paper does not establish this.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

First, the punchline: the headline claim—that train-test validation is impossible for passively collected data in complex social systems—is not proven, because the key lemma is false. The underlying concern about heavy-tailed passive data is reasonable, but the formal machinery doesn't deliver what it promises.

What's genuinely new and useful: the paper reframes test validity as an epistemic property. Instead of asking whether a specific estimator generalizes, it asks whether the data plus minimal assumptions (low rank) leave a set of possible worlds on which any estimator's risk is unbounded. That's a nice way to bring NFL-style reasoning into practical evaluation settings. The MovieLens experiment is the most concrete contribution: fitting 100 rank-50 matrices to the observed data and showing large pairwise normalized absolute error on unobserved entries. That's a real illustration of underspecification, and it doesn't depend on the flawed proof. The related work is also fair, connecting to matrix completion, Rashomon sets, and validity theory.

The soft spots are load-bearing. Lemma 1 (Supp. E) asserts that when the sample graph is not k-connected, the set F of rank-≤k matrices consistent with D is a non-empty vector space. That's false. Consider a 3x3 case with observed entries (1,1), (1,2), (2,1) all equal to 1, with k=1. The all-ones matrix and the matrix with a 2x2 block of ones and zeros elsewhere are both rank 1 and consistent with the data, but their sum has rank 2 and is not in F, and scalar multiples leave F. So F is not closed under vector-space operations. Citing Liu et al. doesn't fill that gap. Since Lemma 2's volume argument and Theorem 1's conclusion both rest on Lemma 1, the impossibility result for arbitrary risk estimators is not established.

Additional issues: Theorem 1 moves from a global statement about the whole inference setting to a per-node count of 'users for which test validity holds,' but Definition 4 defines test validity globally; the per-node notion is not defined. Corollary 2's Jensen bound uses E[x]=n/2 for a power-law distribution, which is simply wrong; the mean of a Pareto with tail index α is α x_min/(α−1) for α>1, not n/2. So the scaling-inefficiency bound is also unsupported.

The paper deserves a serious referee because the question matters and the empirical demonstration is worth engaging with, but not in its current form. I'd ask for a revision that either repairs the algebra or honestly weakens the claims to what the experiments show: that many low-rank worlds fit passive data from a heavy-tailed sample graph and disagree strongly on unobserved entries, so any single test-set estimate is fragile. That is a weaker but still interesting result, and the current overclaiming hurts it.

Referee Report

5 major / 6 minor

Summary. The paper formalizes the question of whether the train-test paradigm can validate models when data are passively collected from complex social systems. It models possible worlds as low-rank matrices, defines test validity relative to a prior distribution over worlds consistent with the observed data, and claims that for heavy-tailed sample graphs the paradigm is invalid for any risk estimator for most of the system. The paper further claims that scaling data collection or using limited benchmarks is prohibitively inefficient, and illustrates the non-identifiability of possible worlds on MovieLens and Cora. The intended contribution is a set of impossibility results strengthening no-free-lunch theorems for social systems.

Significance. The question attacked by the paper is important and timely: whether current evaluation practices can certify performance on the target distribution when data are collected passively. The formal framework—sample graphs, k-connectivity, possible worlds, and validity relative to a prior—is a useful way to structure the problem, and the experiments on MovieLens and Cora provide a clear falsifiable demonstration that many low-rank completions can fit observed data while disagreeing on unobserved entries. If the central theorem were correct, it would be a notable result with implications for recommender systems, question answering, and benchmarking practice. However, the paper's central proof relies on a mathematically false lemma, and several other load-bearing steps are not justified; in its current form the impossibility claim is not established.

major comments (5)

[Section 4, Lemma 1 (proof in Supp. E)] The assertion that the set F of rank-≤k matrices consistent with observed entries is a non-empty vector space is false. For X1=X2={1,2,3}, S={(1,1),(1,2),(2,1)} with observed value 1, and k=1, both the all-ones matrix and the matrix with ones at the observed positions and zeros elsewhere belong to F, but their sum has rank 2 and does not match the observed entries at (1,1); scalar multiples also violate the fixed values. Thus F is not closed under addition or scalar multiplication. Because Lemma 2's volume argument in Supp. F requires F to be a vector space with a well-defined dimension, the proof of Lemma 2 collapses, and with it Theorem 1, which depends on Lemma 2. The cited result (G. Liu et al., 2019, Lemma 5.1) does not establish the stated claim, and low-rank completion sets are generally affine varieties rather than linear subspaces.
[Section 4, Theorem 1 (proof sketch)] Theorem 1 states that the number V_i of nodes in X_i for which test validity holds decays as a power law, but Definition 4 defines test validity only for an entire inference setting (A,D,T,F), not for individual nodes. The proof sketch moves from global non-k-connectivity to a per-node degree bound without introducing a formal per-node validity notion. Moreover, k-connectivity is a global graph property, and membership in the k-core is strictly stronger than having degree at least k, as the paper itself notes in the footnote to Definition 6. The bound E[V_i] ≤ n_i u(k)k^{-α_i} is derived from the number of nodes with degree at least k, which is only an upper bound on any k-core-based quantity; it therefore does not establish that validity fails for the vast majority of nodes.
[Supp. F, proof of Lemma 2] The proof defines a limit of uniform distributions on balls of radius r in F, but there is no uniform distribution on an infinite-dimensional (or unbounded finite-dimensional) vector space, and the limit r→∞ does not converge to a countably additive probability measure. The statement P_{f∼F}(|θ−L^T_{fh}|≤ε)=0 is therefore not a well-defined probability statement. The volume-ratio argument also depends on the specific metric used to define balls (a Bregman divergence) and on the choice of limiting procedure, so it cannot support the claimed universality over all risk estimators. The proof needs a rigorous treatment of the prior over F, or the theorem must be restated in terms of an improper prior with explicit caveats.
[Corollary 2 and Supp. G.2] The derivation of the scaling lower bound misapplies the expectation under a power-law distribution. The text computes E_{i∼U{1,n}}[T_i] by treating x_i as if it were drawn uniformly from {1,...,n}, giving E[x]=(n/2), but the paper's model assumes degrees follow a regularly-varying power-law; under a Pareto distribution with tail index α, the mean degree is α x_min/(α−1) for α>1, not n/2. The displayed formula T_i = x_i^{α+1}/(α x_min^α) further conflates the node's degree with the node index. Consequently, the quantitative claims in Corollary 2 about samples needed for scaling and the number of nodes needing additional observations are not supported. Since Corollary 2 is presented as a main contribution (informal Corollary 2 in the introduction), this is a load-bearing issue for the paper's secondary thesis.
[Section 4, Definition 4 and choice of F] The impossibility result is conditional on taking F to be the uniform distribution over possible worlds, which the paper justifies by 'ontological parsimony.' However, a uniform distribution over an unbounded completion set is itself a substantive and arguably non-minimal assumption; priors favoring low-rank or smooth completions—the same structure used in the paper's own experiments to construct possible worlds—would lead to bounded risk. The paper's categorical phrasing ('cannot be valid,' 'no free delivery service') overstates the conditional nature of the result. To support the epistemic conclusion, the paper would need either a justification of uniformity as the uniquely parsimonious prior or a sensitivity analysis showing the conclusion is robust to reasonable prior choices.

minor comments (6)

[Section 1] There is a typo in the first paragraph: 'wether' should be 'whether.'
[Corollary 2 statement] The word 'lineraly' should be 'linearly' in the sentence 'N_j scales lineraly in the size of the domain |X|.'
[Section 4 (Lemma 2) and Supp. F] The main text says 'See supp. B.2 for proof details' after Lemma 2, but the proof is actually in Supp. F; the cross-reference should be corrected.
[Definition 2] In Definition 2, the phrase 'nodes in X1 and X, respectively' contains a typo; it should be 'X1 and X2.'
[Table 2] The Book Crossing row describes the fraction of users with sufficiently large degrees, but the validity conditions elsewhere require k-core membership, which is stronger than degree; the table should clarify whether degree or k-core is being used.
[References] The reference to Abebe (2022) lacks a publication venue or preprint identifier, and the Anderson (2008) reference is an undated web source; full citation details should be provided.

Circularity Check

1 steps flagged · score 5.0 of 10

The impossibility result is largely an unpacking of the paper's own uniform prior over possible worlds; no load-bearing self-citation.

self definitional [Supplementary F, proof of Lemma 2 (main text Section 4, Lemma 2)]
"Since the standard uniform distribution is not defined on an entire vector space, I will instead consider the limit of the class of uniform distributions of balls of radius r. ... Next, let U_r denote the uniform distribution over B(f, r·epsilon). Then, the probability ... is given by forall f in F: P_{f'~U_r}(L^T_{ff'} <= epsilon) = Vol B(f,epsilon)/Vol B(f,r·epsilon) = 1/r^{dim V}."

Lemma 2's conclusion (universal test-invalidity, P=0 for every hypothesis and every epsilon) is derived immediately from this volume ratio. The ratio 1/r^{dim V} is not an empirical or data-dependent quantity: it is the measure-theoretic consequence of choosing the uniform prior over an unbounded vector space F. Section 4 selects this prior as 'ontological parsimony', and Definition 4 defines test validity as a probability over F. The zero probability is therefore built into the prior by construction; the k-connectivity condition only decides whether Lemma 1 makes F a vector space. The paper presents this as an impossibility result for passive data in social systems, but the result is equivalent to the stipulated uniform prior over underdetermined possible worlds.

full rationale

The paper is not circular through self-citation: Lemma 1 relies on G. Liu et al. (2019) and the Bregman argument on Dhillon et al. (2008), both external to this paper, and no fitted parameter is relabeled as a prediction. The MovieLens experiments are illustrative rather than an independent validation of the theorem. The circularity is conceptual: the headline negative result is loaded into the 'ontological parsimony' prior (uniform over F). Once F is a vector space, Lemma 2's zero-probability conclusion is just the volume ratio of that prior, so the central claim reduces to the chosen prior plus the power-law degree assumption in Theorem 1. This is a partial, definitional circularity rather than a fitted-parameter one. Whether Lemma 1's vector-space claim is mathematically correct (the skeptical counterexample in the review) is a separate correctness issue and is not counted here as circularity.

Assumptions & free parameters 3 free parameters · 6 assumptions · 0 invented entities

The central claim rests on four main pillars: the low-rank possible-world model, the uniform prior over F, the power-law sampling assumption, and the cited vector-space lemma. The first three are explicitly assumed; the fourth is imported from the literature and is the most fragile.

free parameters (3)

power-law tail index alpha_i = alpha=2.5 (Table 2), 2.38 for Book Crossing illustration
The quantitative form of Theorem 1 and Corollary 2 depends on the tail exponent of the degree distribution, which is assumed from the literature rather than estimated.
Pareto scale x_min = 5 or 8 in Table 2
Used in numerical illustrations of the scaling and benchmark costs; the bound scales with this quantity.
rank k of the possible world = k=50 in experiments; rank 8-100 in Table 2
The theorem parametrizes validity by the assumed complexity rank; the paper does not estimate k from data.

assumptions (6)

standard math The set F of rank-k matrices consistent with observations forms a non-empty vector space (G. Liu et al. 2019, Lemma 5.1).
This is the load-bearing technical lemma for Lemma 2 and Theorem 1; it is cited, not proven, and the algebraic structure of low-rank sets makes the claim questionable.
ad hoc to paper F is equipped with a uniform distribution (or limit of uniform distributions on balls), used for 'ontological parsimony'.
The uniform prior over an unbounded vector space is improper and drives the zero-probability conclusion.
domain assumption Node degrees in the sample graph are i.i.d. regularly-varying power-law random variables.
Definition 2; needed for the tail bound in Theorem 1. The paper acknowledges this is a disputed but common model.
domain assumption The loss is a scalar Bregman divergence and the target distribution is uniform over X.
Assumed in Lemma 2; covers squared loss, log loss, KL. Uniform target models 'all possible interactions'.
domain assumption The true world and hypotheses are noise-free (f,h: X -> Y).
Stated in Section 3 for clarity; the paper does not analyze noisy observations.
standard math Test validity is defined via existence of some hypothesis class H (Definition 4).
The definition itself, not proved; reasonable but the negation in test-invalidity is strong.

how reviews work

0 comments

Cite this review

Pith. "Pith review of No Free Delivery Service: Epistemic limits of passive data collection in complex social systems." pith.science (2026). https://pith.science/paper/HCACXK7X

@misc{pith2026241113653,
  author       = {Pith},
  title        = {Pith review of: No Free Delivery Service: Epistemic limits of passive data collection in complex social systems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HCACXK7X}},
  note         = {Machine review of arXiv:2411.13653}
}

read the original 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\"ive 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.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

2 extracted references · 2 canonical work pages

[1]

Start with a small connected graph 𝐺0 with𝑚 nodes

work page
[2]

the full procedure followed to train and validate a predictor

At each time step𝑡 >0, add a new node𝑥 to𝐺 and connect it to𝑚 existing nodes in𝐺 with a probability proportional to their degree, i.e., ℙ(𝑖 ∼𝑡 𝑣)= 𝜅𝑖∑ 𝑗∈X𝜅𝑗 It is then well known that definition 10 leads to a power-law degree distribution in𝐺, i.e., a distribution where the probability of a node having 𝑘 connections is proportional to 𝑘−𝛼 for some𝛼 >0. D ...

work page 2018

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.

[1] [1]

Start with a small connected graph 𝐺0 with𝑚 nodes

work page

[2] [2]

the full procedure followed to train and validate a predictor

At each time step𝑡 >0, add a new node𝑥 to𝐺 and connect it to𝑚 existing nodes in𝐺 with a probability proportional to their degree, i.e., ℙ(𝑖 ∼𝑡 𝑣)= 𝜅𝑖∑ 𝑗∈X𝜅𝑗 It is then well known that definition 10 leads to a power-law degree distribution in𝐺, i.e., a distribution where the probability of a node having 𝑘 connections is proportional to 𝑘−𝛼 for some𝛼 >0. D ...

work page 2018