{"id":"26f9adff-5f55-403e-9fd9-66a538bd2e9f","arxiv_id":"2411.14754","paper_version":2,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":5,"one_line_summary":"SuCo uses subspace collision counting with inverted multi-indexes to deliver fast and compact approximate nearest neighbor search, though its theoretical guarantees are not rigorously established.","lead":"This paper introduces SuCo, an approximate nearest neighbor search method that splits high-dimensional data into subspaces and counts how often candidate points fall near the query in each subspace. The method shows strong empirical speed and memory results, but the claimed theoretical guarantees rest on faulty probability arguments.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem proofs replace rank-based collision with a threshold on subvector norm; the two events are not equivalent, so the claimed guarantees do not follow.","rationale":"The reader correctly identifies that the independence assumption on subvector norms is unverified and that Theorem 2's proof restricts to the best-case C=N_s scenario. However, the single most load-bearing flaw is more fundamental: the proofs do not analyze the algorithm they claim to analyze. Collision is defined by rank (being among the α·n nearest), but Eq. (2) and Eq. (9) treat collision as an absolute threshold on the subvector norm. No argument connects these events, so the probability bounds derived for Z_j^i do not translate to the SC-score or to query success. This failure is internal to the proof, independent of whether the independence assumption holds. In the ideal i.i.d. Gaussian model, the rank-based probability that a point is in the α·n smallest norms is not controlled by a Paley–Zygmund bound on a single point's norm; the threshold would need to depend on the sample, not just on α, m, and σ. Thus the theoretical guarantee is not rigorous even under the paper's stated assumptions. The empirical results may be valuable and the Dynamic Activation query strategy is a plausible contribution, but the abstract's central claim of rigorous guarantees is unsupported. The reader's REJECT verdict remains appropriate.","tokens_in":43136,"tokens_out":4708,"duration_ms":49085,"concrete_test":"Simulate the actual collision event for i.i.d. Gaussian subvector norms with fixed m, σ, n=10^4, α=0.05. For each point, compute its rank; estimate P(Z_j^i ≤ sqrt((1-α)(σ²+m²)) | point in α·n nearest). If this conditional probability is not close to 1 (or if the unconditional bound Pr(Z_j^i ≤ sqrt(...)) ≤ α fails to match collision probability), then Eq. (2) does not justify the proof. More directly, run the actual SC-Linear algorithm on synthetic i.i.d. Gaussian data and measure the success probability of Theorem 2 for k=1; if it falls below 1/2, the theorem is false in the model it assumes.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim that SuCo provides 'rigorous theoretical guarantees' depends entirely on Theorems 1 and 2. Both proofs model 'collision' as a subvector squared norm Z_j^i falling below a fixed threshold (Eq. (2) and Eq. (9)). But Definition 1 defines collision as being among the α·n nearest points in the subspace, a rank-based event over all n data points. The probability that a point is in the α·n smallest norms is not equal to, or bounded by, the probability that its own Z_j^i is below a threshold; it depends on the whole empirical distribution of distances in that subspace. The proofs never establish an implication either way between the rank event and the threshold event. Consequently, the derived bounds on SC-scores and on query success concern a different procedure than Algorithm 1. This is an internal inconsistency, not merely an unrealistic distributional assumption. Additionally, Theorem 2's 'without loss of generality' restriction to C=N_s (true neighbor collides in every subspace) is not WLOG: the general case is only hand-waved, and the constant 1/2 is never actually verified from the displayed inequalities. Thus the abstract's promise of rigorous guarantees is unsupported even under the paper's independence assumptions.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes Subspace Collision (SC), a framework for high-dimensional approximate nearest neighbor (ANN) search based on counting collisions in randomly sampled subspaces, and SuCo, an efficient implementation using inverted multi-indexes. The paper claims that SC-score acts as a proxy for Euclidean distance, that the framework provides rigorous theoretical guarantees (Theorems 1 and 2), and that SuCo outperforms state-of-the-art ANN methods in both indexing and query performance. The empirical section compares SuCo against LSH-, VQ-, tree-, and graph-based baselines on several standard datasets, reporting large improvements in indexing time and memory footprint with competitive or superior recall.","tokens_in":43468,"tokens_out":7085,"duration_ms":70566,"significance":"If the theoretical guarantees were valid, this would be a notable contribution: an ANN method combining lightweight indexing, fast querying, and formal quality guarantees. The empirical work has independent value: SC-Linear's high recall is a legitimate and interesting observation, SuCo's index is lightweight, and the Dynamic Activation query algorithm offers a measurable speedup over the standard Multi-sequence method. The code is publicly available, and the experiments use standard datasets and careful parameter tuning. However, the paper's central advertised contribution—the 'rigorous theoretical guarantees' of Section 3.4—is not supported. The proofs contain a misapplication of Paley-Zygmund, conflate rank-based collision with a threshold-based event, and rely on an unverified independence assumption. These are load-bearing errors, not presentation issues.","major_comments":[{"comment":"The inequality in Eq. (2), Pr(Z_j^i ≤ sqrt((1−α)(σ^2+m^2))) ≤ α, is not a consequence of the Paley-Zygmund inequality as claimed. Paley-Zygmund states Pr(Z ≥ θE[Z]) ≥ (1−θ)^2 E[Z]^2/E[Z^2] for θ∈[0,1], which yields an upper bound on the lower tail only after complementation and only for θ≤1. For the choice θ = sqrt((1−α)(σ^2+m^2))/m, θ can exceed 1; e.g., with m=σ=1 and α=0.1, θ≈1.34, and the inequality fails for standard distributions (if Z~N(1,1), Pr(Z≤1.34)≈0.63>0.1). Since Eq. (2) and its counterpart Eq. (9) are the starting points of both theorem proofs, the claimed probability bounds in Theorems 1 and 2 do not follow.","section":"Section 3.4, Eq. (2) and Eq. (9)"},{"comment":"The statement 'without loss of generality, we only discuss here the case where the re-rank ratio β is chosen so that C=N_s' is not a genuine WLOG reduction. C is the number of subspaces in which a given data point collides; it is random and depends on the query and the data. The theorem's conclusion requires that appropriate N_s, α, β exist for the actual queries, but no argument shows that one can force C=N_s for the true neighbor, and the sentence 'Other scenarios with C<N_s can be similarly studied by increasing β accordingly' is not a proof. In addition, the proof introduces a normality assumption on squared distances without justification, and the final Chebyshev step only asserts that the success probability is at least 1/2 without verifying that the chosen t simultaneously satisfies t > N_s m sqrt((1−α)(1+σ^2/m^2)) − E_{k,n} and 1 − V_{k,n}/t^2 ≥ 1/2.","section":"Section 3.4, proof of Theorem 2"},{"comment":"The proofs model 'collision' as the event {Z_j^i ≤ sqrt((1−α)(σ^2+m^2))}, where Z_j^i is the squared subvector norm. However, Definition 1 and Definition 2 define collision as membership in the α·n nearest points in a subspace, a rank-based event over the empirical distribution of all n distances. These two events are not equivalent, and neither is implied by the other in general: a point can be among the α·n nearest while its own norm exceeds the threshold (if all other points are even farther), and it can fail to be among the α·n nearest while its norm is below the threshold (if many other points are closer). No lemma connects the rank event to the threshold event, so the derived bounds concern a different procedure from Algorithm 1 and from the SC-score actually computed. This is an internal inconsistency in the theoretical claim.","section":"Section 3.4, proofs of Theorems 1 and 2"},{"comment":"Both theorem proofs assume that the squared subvector norms Z_j^i are independent random variables across all data points i and all subspaces j, with common mean m and variance σ^2. This is a strong i.i.d.-style assumption that is not verified on the real datasets used in Section 5, and it is structurally questionable for fixed data points: the subvector norms of a single vector are generally correlated (for normalized data they even sum to a constant). Because the independence assumption drives the variance computations in Eq. (8) and the subsequent Chebyshev bounds, the claimed guarantees may not apply to the very datasets on which the method is evaluated. The paper should either justify this assumption empirically or explicitly restrict the theoretical claims to distributions satisfying it.","section":"Section 3.4, assumptions before Eq. (1) and Eq. (8)"}],"minor_comments":[{"comment":"Definition 3 describes subspaces formed by uniform random sampling without replacement, while Algorithm 1 and Algorithm 2 use fixed contiguous blocks of dimensions; the paper calls the latter a 'special case,' but the theoretical analysis does not address whether random sampling is required for the guarantees, so the connection between the definition, the implementation, and the theory should be clarified.","section":"Section 3.1, Definition 3 vs. Algorithm 1"},{"comment":"The proof's scenario analysis does not explicitly condition on the theorem's hypothesis that SC-score(o1) > SC-score(o2); the roles of the Δ subspaces and the choice of c1 and c2 are sketched rather than derived, making it difficult to follow how the final probability bound 1/2 − 1/e^2 is obtained.","section":"Section 3.4, proof of Theorem 1"},{"comment":"There is a typo in 'useing OpenMP' near the end of Section 5; it should read 'using OpenMP.'","section":"Section 5, experimental setup"},{"comment":"The claim that SC-score follows the 'Pareto principle' is supported only by a visual inspection of L-shaped scatter plots; a quantitative measure (e.g., the fraction of SC-score mass concentrated in the closest 20% of points) would make the claim more precise and testable.","section":"Section 3.3.1, Figure 2"}],"recommendation":"reject","confidential_remarks":"The paper's theoretical guarantee is its main advertised novelty and the basis for the claimed 'first method that combines performance with rigorous guarantees.' The proof issues identified above—especially the threshold-versus-rank mismatch and the incorrect Paley-Zygmund step—are not local fixable points; they undermine the central claim. The empirical results are interesting and could support a revised, systems-oriented paper that does not assert unsupported guarantees. I would not recommend requiring a major revision of this manuscript in its current form."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: the empirical method is worth a look, but the theoretical guarantee advertised in the abstract does not survive contact with the paper's own definitions. Theorems 1 and 2 are not established, and the claim of 'rigorous theoretical guarantees' is unsupported.\n\nWhat is new: the subspace collision score as a similarity proxy, the SuCo index with a small-K inverted multi-index and the Dynamic Activation query algorithm, and the experimental observation that SC-Linear gets over 0.99 recall on standard 10M-point datasets. The evaluation looks careful: standard benchmarks, relevant baselines, and the code is public. The Dynamic Activation speedup (up to 40% over Multi-sequence) is modest and plausible.\n\nThe soft spot is not a minor gap. Definition 1 defines collision as being among the alpha*n nearest points in the subspace by distance, a rank event over the whole dataset. The proofs of Theorems 1 and 2 replace this with the event that a point's subvector squared norm falls below a fixed threshold (Eqs. (2) and (9)). These are different events: whether a single point's norm is small does not determine whether it ranks in the top alpha fraction of the empirical distribution. So the bounds in the paper concern a different procedure than Algorithm 1. Eq. (2) also misuses Paley-Zygmund, which is an upper-tail bound, not a bound of the form Pr(Z <= c) <= alpha. Theorem 2's 'without loss of generality' restriction to C = N_s is exactly the best-case scenario; the general case is hand-waved, and the constant 1/2 is never shown to follow. The independence assumption on subvector norms is unverified and contradicted by the structure of real embeddings.\n\nNone of this kills the empirical contribution. If the theoretical claims were dropped and the paper repositioned as a heuristic ANN method with a collision-counting index, the experiments would be a solid systems contribution. But as submitted, the headline claim is load-bearing and false. The paper deserves a serious referee so the record is clear, and the authors should be asked to either repair the proofs or formally withdraw the guarantees.\n\nI would bring this to our reading group as an instructive case of separating empirical value from theory.","headline":"Solid empirical ANN paper whose advertised theoretical guarantees do not survive contact with its own definitions; treat the theory as unproven and the method as a heuristic.","tokens_in":43923,"tokens_out":3366,"would_cite":false,"duration_ms":32101,"reading_group":"yes","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proposes that approximate nearest-neighbor search can be reframed as counting collisions across random subspaces, and that this collision count—called SC-score—both tracks Euclidean closeness and supports formal probability…","keywords":["approximate nearest neighbor search","subspace collision","SC-score","inverted multi-index","high-dimensional Euclidean space","Pareto principle","theoretical guarantee","Dynamic Activation"],"falsifier":"Run Algorithm 1 (or SuCo with the same parameters) on a dataset with strongly correlated subvector norms—for example, artificially duplicating or permuting coordinate blocks so that subvector squared norms become dependent—and measure the empirical success rate over many queries. If, with $N_s=8$, $\\alpha=0.05$, and $\\beta=0.005$, the fraction of queries returning the true 50 nearest neighbors falls below $1/2$, or if the measured correlation among subvector norm squares already contradicts the proof's independence assumption on a standard dataset, the central guarantee is falsified.","tokens_in":42949,"feed_emoji":"🔎","tokens_out":6326,"duration_ms":62284,"temperature":0.7,"pith_summary":"The paper is trying to establish that a new similarity metric, SC-score, captures Euclidean closeness well enough to power approximate nearest-neighbor search, and that an ANN method built on it can carry rigorous quality guarantees while staying fast and light. The central claim is that the 20% of points nearest to a query have distinctly high SC-scores, while the rest are indistinguishable, so ranking by SC-score and re-ranking a small candidate pool recovers the true neighbors. If correct, this would close a gap: no existing in-memory ANN method simultaneously gives strong indexing and query performance and formal guarantees. The paper further claims its SuCo index realizes the framework with 1–2 orders of magnitude faster query answering than prior guaranteed methods and roughly one-tenth the index memory.","feed_headline":"Counting subspace collisions yields fast, provable ANN search","feed_subtitle":"A new index, SuCo, answers queries 1–2 orders faster than guaranteed methods with one-tenth the memory.","key_machinery":"The central object is the SC-score and the counting procedure behind it: after dividing the $d$ dimensions into $N_s$ subspaces, a point collides with the query in a subspace when it is among the closest $\\alpha n$ points in that subspace, and its SC-score is the number of such collisions across subspaces. The argument uses the Paley–Zygmund inequality to show that colliding subvectors have small squared norm and Chebyshev's inequality to show that non-colliding subvector norms stay near their common mean, so higher SC-score implies smaller total distance with controlled probability. On the engineering side, SuCo builds the collision counts with a lightweight index: K-means clustering inside an inverted multi-index per subspace, plus a new Dynamic Activation query algorithm that replaces the priority-queue-based Multi-sequence retrieval and returns the same clusters with up to 40% less query time.","core_discovery":"At the center is the SC-score. Given a query $q$, the dimensions are split into $N_s$ subspaces; in each subspace, the $\\alpha n$ points closest to $q$ are counted as \"colliding\"; a point's SC-score is the number of subspaces in which it collides. The paper's Theorem 1 states that if one random point has a higher SC-score than another, it is closer to $q$ with probability at least $1/2 - 1/e^2$, under suitable parameters. Theorem 2 states that the full algorithm answers a $k$-ANN query with probability at least $1/2$. The proofs couple the Paley–Zygmund anti-concentration inequality, which bounds the squared norm of a colliding subvector, with Chebyshev's inequality, which keeps non-colliding subvector norms near their mean. The paper presents experiments showing the SC-score follows a Pareto-like \"L-shape\" on standard datasets and that SuCo outperforms guaranteed baselines and matches or beats non-guaranteed methods on hard datasets.","pith_inferences":["The independence premise is unlikely to hold for real embeddings, so a quantitative version of the guarantee that depends on measured subvector-norm correlations would clarify how much dependence the proof tolerates.","The Pareto-style turning point near $0.2n$ suggests that the collision ratio $\\alpha$ could be chosen adaptively per query or per dataset, potentially lowering cost without losing recall.","The collision-counting view may transfer to other similarity measures and to learned indexes, since the index only needs coarse locality rather than exact distances.","If SC-score is as distribution-insensitive as the paper suggests, it could serve as a cheap pre-filter before a graph-based search, reducing the number of expensive distance evaluations."],"forward_implications":["ANN can be solved by counting coarse subspace collisions rather than summing per-dimension distances, so the index only needs to localize the roughly 3–5% of points that collide.","The index construction runs in $O(n(\\sqrt{K}dt+N_s))$ time and uses $O(\\sqrt{K}d+nN_s)$ memory, which the paper shows scales to 100M-point datasets.","Compared with LSH-based methods that carry theoretical guarantees, SuCo answers queries 1–2 orders of magnitude faster and needs as little as one-tenth of the index memory.","Against methods without guarantees, SuCo is best on hard datasets and competitive with HNSW on easy ones.","Dynamic Activation returns exactly the clusters of Multi-sequence but without priority-queue overhead, giving a free query-speed improvement on the same index."],"supporting_citations":[{"why":"Supplies the inverted multi-index structure that SuCo's index construction builds on, plus the Multi-sequence query baseline that Dynamic Activation replaces.","marker":"[9]"},{"why":"Defines product quantization, the subspace-decomposition idea from which the inverted multi-index derives and which SuCo's two-level clustering instantiates.","marker":"[45]"},{"why":"Provides the optimized product quantization baseline that also uses an inverted multi-index and whose large-K contrast motivates SuCo's coarse clusters.","marker":"[38]"},{"why":"Serves as the primary LSH-based competitor with guarantees, establishing the query-time and memory gap SuCo claims to close.","marker":"[104]"},{"why":"Serves as the strongest non-guaranteed graph-based competitor in the recall-QPS comparisons on easy and hard datasets.","marker":"[67]"},{"why":"Provides the tree-based non-guaranteed baseline used in the indexing and query comparisons and in the complexity table.","marker":"[14]"},{"why":"Supplies the bounds and approximations for moments of order statistics used in the proof of Theorem 2.","marker":"[1]"},{"why":"Supplies the expected-values and moments machinery for order statistics used to control the success probability in Theorem 2.","marker":"[2]"},{"why":"Provides the normal-order-statistic approximation accuracy relied on when Theorem 2 derives its explicit probability bound.","marker":"[16]"}],"fun_headline_variants":["Subspace Collision: provable ANN search that's 100× faster","SC-score: Pareto principle makes ANN search provable","SuCo: 10× faster ANN with guarantees, 10% memory","Provable ANN search via subspace collision counting","Subspace Collision: theoretical guarantees without the usual cost"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the squared Euclidean norms of the subvectors, across all points and subspaces, behave like independent random variables with one common mean and variance; if real data violates this independence, the probability bounds in Theorems 1 and 2 no longer follow from the proof.","fun_headline_variants_meta":{"raw":{"variants":["Subspace Collision: provable ANN search that's 100× faster","SC-score: Pareto principle makes ANN search provable","SuCo: 10× faster ANN with guarantees, 10% memory","Provable ANN search via subspace collision counting","Subspace Collision: theoretical guarantees without the usual cost"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000706,"raw_usage":{"total_tokens":3199,"prompt_tokens":982,"completion_tokens":2217,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":598,"completion_tokens_details":{"reasoning_tokens":2142}},"tokens_in":598,"tokens_out":2217,"duration_ms":27681,"temperature":1.0,"reasoning_tokens":2142,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T14:55:38.800860+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 1 (or SuCo with the same parameters) on a dataset with strongly correlated subvector norms—for example, artificially duplicating or permuting coordinate blocks so that subvector squared norms become dependent—and measure the empirical success rate over many queries. If, with $N_s=8$, $\\alpha=0.05$, and $\\beta=0.005$, the fraction of queries returning the true 50 nearest neighbors falls below $1/2$, or if the measured correlation among subvector norm squares already contradicts the proof's independence assumption on a standard dataset, the central guarantee is falsified.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Serves as the primary LSH-based competitor with guarantees, establishing the query-time and memory gap SuCo claims to close."},{"cited_title":"Expected Values and Moments","cited_arxiv_id":null,"evidence_quote":"Supplies the expected-values and moments machinery for order statistics used to control the success probability in Theorem 2."}],"review_version":1}