{"id":"5240586b-9e15-490d-90f9-3bf1a782b9c7","arxiv_id":"2411.13653","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":3,"one_line_summary":"For passively collected data from heavy-tailed social systems, train-test validation cannot be trusted for most of the system under a low-rank, uniform-prior model.","lead":"This paper argues that when data is collected passively from social systems, like movie ratings or web text, no test set can certify how well an AI model works on the full task. The author proves a formal limit: for low-rank tasks with heavy-tailed sampling, most of the system is too sparsely observed for any validation method to bound the true error.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 1's vector-space claim is false: low-rank completion sets are not generally vector spaces, so the volume argument behind Theorem 1 collapses.","rationale":"The paper's informal question—whether train-test evaluation can be valid when validation data are passively sampled from a heavy-tailed social system—is well motivated, and the MovieLens experiment showing many low-rank completions with very different unobserved values is a genuine illustration of underspecification. But the formal route from that intuition to the theorem requires: (i) F is a vector space; (ii) a uniform/limiting measure on F has the volume scaling used in Lemma 2; (iii) a node-level notion of test validity that matches Definition 4; and (iv) a correct expectation bound in Corollary 2. The reader's weakest assumption identifies (i). My small counterexample shows (i) is not merely unproven but false in the paper's own setting. Because Lemma 2's conclusion is exactly the 'for all H and all h, probability equals zero' statement that Definition 4 requires for test-invalidity, and Theorem 1's degree-count bound is derived from Lemma 2, the central theorem is unsupported. I do not claim the high-level phenomenon is silly; I claim this manuscript does not establish the impossibility. The empirical evidence does not close the proof gap because it fits possible worlds within one subspace and does not compute the probability over all possible worlds or test any estimator. For these reasons the reader's REJECT is appropriate and no verdict change is needed.","tokens_in":23744,"tokens_out":7644,"duration_ms":951590,"concrete_test":"Verify Lemma 1 on the 3x3 counterexample: A=[[1,1,0],[1,1,0],[0,0,0]] and B=[[1,1,1],[1,1,1],[1,1,1]] are both rank-1 completions of S={(1,1),(1,2),(2,1)} with values 1; compute A+B and 2A to show F is not closed under vector-space operations. This directly falsifies Lemma 1 as stated and removes the foundation of Lemma 2 and Theorem 1. As an additional check, attempt to prove Theorem 1 without the vector-space assumption: if no measure-zero bound can be derived on the actual non-linear rank variety, the theorem should be revised or restricted to settings where a subspace structure is explicitly assumed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 1 (main text; proof in Supp. E) asserts that when the sample graph S is not k-connected, the set F={f: rank(f)<=k, f(x)=y on D} is a non-empty vector space, and Lemma 2 (Supp. F) then uses balls and dimension ratios in that vector space to conclude P_{f~F}(|theta - L^T_{fh}| <= epsilon)=0 for every h. The assertion is false as stated. Low-rank matrices satisfying fixed observed entries generally form an affine variety, not a linear subspace. Minimal check: take X1=X2={1,2,3}, S={(1,1),(1,2),(2,1)} with observed values 1, and k=1. F contains A=[[1,1,0],[1,1,0],[0,0,0]] and B=all-ones, both rank 1 and consistent with S, but A+B has rank 2 and is not in F; scalar multiples also violate the fixed entries. S is not 2-connected, so this is exactly the Lemma 1 setting. Therefore the volume argument supporting Lemma 2, and with it Theorem 1's claim that no risk estimator can be valid, is not established. Even weakening 'vector space' to 'affine subspace' does not repair the argument, because F is not affine.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":23985,"tokens_out":7834,"duration_ms":79378,"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":[{"comment":"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":"Section 4, Lemma 1 (proof in Supp. E)"},{"comment":"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.","section":"Section 4, Theorem 1 (proof sketch)"},{"comment":"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.","section":"Supp. F, proof of Lemma 2"},{"comment":"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":"Corollary 2 and Supp. G.2"},{"comment":"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.","section":"Section 4, Definition 4 and choice of F"}],"minor_comments":[{"comment":"There is a typo in the first paragraph: 'wether' should be 'whether.'","section":"Section 1"},{"comment":"The word 'lineraly' should be 'linearly' in the sentence 'N_j scales lineraly in the size of the domain |X|.'","section":"Corollary 2 statement"},{"comment":"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.","section":"Section 4 (Lemma 2) and Supp. F"},{"comment":"In Definition 2, the phrase 'nodes in X1 and X, respectively' contains a typo; it should be 'X1 and X2.'","section":"Definition 2"},{"comment":"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.","section":"Table 2"},{"comment":"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.","section":"References"}],"recommendation":"reject","confidential_remarks":"The central mathematical claim of the paper, Lemma 1, is demonstrably false, and the subsequent impossibility results depend on it. Even substantial revision would require replacing the core proof mechanism with a correct treatment of low-rank completion sets and a well-defined prior; the current manuscript does not meet the bar for publication as a formal impossibility result. The paper might be more appropriately framed as a position or perspective piece highlighting challenges of passive data collection, rather than as a theorem-driven contribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nWhat'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.\n\nThe 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.\n\nAdditional 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.\n\nThe 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.","headline":"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.","tokens_in":24517,"tokens_out":4508,"would_cite":false,"duration_ms":43778,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","68T05","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"Formal proof: train-test evaluation cannot certify models on most social-system data","keywords":["train-test validity","passive data collection","complex social systems","impossibility theorem","recommender systems","question answering","low-rank matrix completion","k-core"],"falsifier":"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.","tokens_in":1829,"feed_emoji":"📉","tokens_out":7855,"duration_ms":133866,"temperature":0.7,"pith_summary":"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.","feed_headline":"Train-test evaluation fails for most social-system data","feed_subtitle":"Passively collected ratings and web text cannot certify performance on the full intended domain, a new proof shows.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Establishes the no-free-lunch baseline this paper strengthens, showing that inductive inference requires assumptions.","marker":"Wolpert, 1996"},{"why":"Supplies the algebraic result that the set of low-rank matrices matching the observed entries forms a non-empty vector space when the sample graph is not k-connected; this is the load-bearing step in Lemma 1.","marker":"G. Liu et al., 2019"},{"why":"Provides the generalized Pythagorean theorem for Bregman divergences used to extend Lemma 2 to hypotheses outside the feasible set.","marker":"Dhillon et al., 2008"},{"why":"Prior power-law matrix completion work showing that at least k samples per row and column are needed, supporting the k-core necessary condition.","marker":"Meka et al., 2009"},{"why":"The MovieLens 100k dataset used for the empirical illustration of widely different possible worlds that fit the observed data.","marker":"Harper et al., 2015"},{"why":"Defines regularly-varying power-law distributions and tail-index methodology used to formalize passive data in complex systems.","marker":"Voitalov et al., 2018"},{"why":"Classic generative model connecting preferential attachment to power-law degree distributions, supporting the heavy-tail assumption.","marker":"Barabási et al., 1999"},{"why":"Coupon-collector bounds used in Corollary 2 to lower-bound the number of samples needed for scaling to a valid test setting.","marker":"Flajolet et al., 1992"}],"fun_headline_variants":["Passive data can't validate AI for social systems","Proof: train-test invalid for social-system data","Scaling won't fix train-test flaws in social AI","No free delivery: passive data limits model validity","Impossibility: test risk unknowable in social systems"],"cache_read_input_tokens":26624,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Passive data can't validate AI for social systems","Proof: train-test invalid for social-system data","Scaling won't fix train-test flaws in social AI","No free delivery: passive data limits model validity","Impossibility: test risk unknowable in social systems"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000241,"raw_usage":{"total_tokens":1540,"prompt_tokens":984,"completion_tokens":556,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":600,"completion_tokens_details":{"reasoning_tokens":480}},"tokens_in":600,"tokens_out":556,"duration_ms":6504,"temperature":1.0,"reasoning_tokens":480,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T16:01:08.703327+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}