- Rating
- 1
- Confidence
- 4
- Informativeness
- 1
- Presentation
- 3
- Soundness
- 1
Read review
Paper summary
The paper extends the stability framework of Beyer et al. (1999) and Durrant & Kabán (2009) to three retrieval settings:
- Multi-vector search with Chamfer aggregation (Thm 3.11). Stability holds if the induced single-vector problem is "c-strongly stable", the document sets are "c-non-degenerate", and the per-token nearest-neighbor distances have non-negative summed covariance. The authors present a synthetic construction that arguably shows that average pooling is unstable.
- Filtered search under an additive mismatch penalty (Thm 4.3). Stability holds if the base problem is stable and the scalar penalty \alpha is sufficiently large. A counterexample shows that small penalties can make the problem unstable.
- Sparse search (Thm 5.4). Two new properties, concentration and overlap of importance, are shown to imply a positive lower bound on the relative variance.
The appendices check the assumptions on ColBERT, SPLADE-v3 and an ArXiv filtered benchmark, and compare HNSW/IVF recall on "stable" and "unstable" synthetic data.
Critical strengths
- The question is relevant and timely. Classical distance-concentration theory has not been revisited for late interaction, filtered search or learned sparse retrieval.
- The paper is clearly written, and the goals/non-goals paragraph sets expectations well.
- The paper engages with real embeddings rather than staying purely synthetic.
- The filtered-search counterexample (App. E.2) is simple and instructive.
Critical weaknesses
W1. The results lack depth: the assumptions carry the content
The proofs are short. That is not a weakness in itself, since simple proofs can mean the formalism is right. Here, however, the brevity reflects that the assumptions are close to restatements of the conclusions, while the substantive question is assumed rather than proved.
- Thm 3.5 restates Beyer et al. and Durrant & Kabán for a non-negative aggregated distance; the authors acknowledge that it "follows directly from the prior proofs".
- Lemma 3.10: it seems like combining c-non-degeneracy with c-strong stability could give the conclusion in one line.
- Thm 3.11 follows from the variance of a sum, Cauchy–Schwarz and the mediant inequality. The covariance condition, where any interaction between query tokens would appear, is simply assumed.
- Thm 4.3 follows from a variance decomposition and the mediant inequality.
- Thm 5.4 is a dimension-free bimodality argument. The proof never uses that m tends to infinity or sparsity; given the objective of the section, I find this strange; all asymptotic content sits in assuming that teh bimodality gap stays constant in m.
- The "reusable decomposition" put forward in the conclusion as a methodological contribution is the mediant inequality.
In my opinion, the key question is under what models of real embeddings these conditions hold as m grows, and it is not addressed. The contribution would be considerably stronger with any of the following: deriving the assumptions from a generative model, giving necessary conditions or showing tightness, or giving non-asymptotic rates in m and n. the current version of the theory is thin.
W2. The asymptotic regime does not match practice, and the empirical checks cannot verify it
- The Beyer framework holds the database size n fixed while m tends to infinity. This is never stated in the paper. Practical retrieval is the opposite regime: m is fixed (128 to 30k) and n is in the millions or more. DMAX/DMIN depends on n even for i.i.d. data, so the empirical ratios depend on a quantity the theory does not model.
- Every condition is a statement about a sequence of problems indexed by m. A trained model is one point in that sequence, and the paper never specifies which m-indexed family a real model belongs to. Tables 1, 3 and 5 therefore check finite-m proxies, not the assumptions themselves. The claim that the assumptions "comfortably hold in practice" is not supported.
- Small or unreported n:
- Fig. 1 uses n = 1000. Table 1 uses about 4000 documents.
- Table 2 does not state n; presumably it is the same as Table 1, i.e., fewer samples than its 15k–19k active dimensions, used to fit a 256–512-factor PPCA. That fit, and therefore the "relevant coordinates" statistic that motivates Section 5, is unreliable.
- Table 3 and Figs. 2–3 do not report n at all.
- The certified bounds do not appear to separate SPLADE from unstable data. The RelVar lower bounds in Table 5 range from 1.2e-7 to 4.3e-6. The paper's own unstable controls in Fig. 3 ("CoI only", "Neither") have relative variance at or above these values at comparable m. For reference, I asked an AI agent to compute RelVar for ℓ2-normalized i.i.d. Gaussian data: it has RelVar \approx 8e-6 at m = 30522. This means that at SPLADE's dimension, the certificate cannot distinguish SPLADE from unstable data. It also seems like the parameters were also tuned to make the theorem applicable; as the authors note, at \alpha = 0.9 the required overlap is essentially never observed.
W3. Stability is conflated with efficient search, and the relevant algorithmic theory is not discussed
The introduction and conclusion repeatedly tie stability to efficient search ("favorable for stability, and thus for efficient search"). Beyer-style stability is a statement about contrast. It gives no algorithmic guarantee.
There is rigorous theory connecting data assumptions to the performance of graph-based indexes: Indyk & Xu (NeurIPS 2023) prove approximation and query-time guarantees for DiskANN on data with bounded doubling dimension, and Gollapudi et al. (ICML 2025) improve the approximation factor and analyse beam search.
These results do not directly cover filtered or Chamfer-based multi-vector search. For the latter, MUVERA (Dhulipala et al., NeurIPS 2024) offers only a reduction-based route. This is exactly where a theoretical contribution would be valuable, but stability does not fill that gap. Shaft & Ramakrishnan (TODS 2006) on indexability is also directly relevant.
Relatedly, App. A.2 argues that intrinsic-dimension measures "only characterize the embedding space geometry, not the aggregation function". Local intrinsic dimensionality is defined from distance distributions for any dissimilarity, so it could be computed on the Chamfer or fused-distance distributions directly.
W4. Filtered search: the fused-distance notion of stability does not measure meaningfulness of the filtered query
The filtered query is argmin \delta(q, d) subject to f = 1 (Def. 4.1). Whether it is meaningful depends on the distribution of \delta among matching documents. However, Thm 4.3 certifies the fused distance over all documents. Once \alpha is large enough, every non-matching document lies above every matching one, so DMAX comes from a filtered-out document. The certified contrast therefore separates filtered-in from filtered-out documents and cannot make a statement about filtered nearest neighbor search.
Methods with hard filtering (ACORN, Filtered-DiskANN, window search) correspond to \alpha = \infty. For these the RelVar machinery is undefined, so the claim that the model "captures nearly all filtered vector search algorithms" needs qualification. I would suggest defining filtered stability on the conditional distribution of \ldeta given f = 1, and discussing how much of the result survives.
W5. Multi-vector search: the average-pooling separation is not supported, and Thm 3.11 has gaps
The abstract states that average pooling "may destroy" stability, citing Fig. 1. But Fig. 1 (right) shows mean-pooling relative variance levelling off just below 1e-3 for m beyond 1000, not converging to zero. Average pooling therefore yields lower contrast but is stable under Def. 3.4. Showing instability would require actually showing convergence to zero in practice.
Lemma 3.10 establishes stability, which yields only that each per-token relative variance does not converge to zero. If I undertand correcly, the proof of Thm 3.11 uses a stronger variant. This looks fixable, but should be inspected carefully.
It seems that Thm 3.11 os missing one hypothesis. The final step (relative variance not converging to 0 implies stability) uses the Durrant–Kabán direction. That requires the bounded-expectation property for the Chamfer distance. It should be added to the theorem's hypotheses.
W6. Sparse search: the stability conclusion needs an unstated hypothesis, and the motivation is not established
The relative variance in Thm 5.4 is taken over random (q, d) pairs, so it includes variation between queries. Events A and B can each have constant probability while being realized by different queries. For example, some queries could overlap with every document and others with none, giving RelVar > 0 with no contrast within any single query. It seems to me that this can be fixed with the current machinery and, maybe, some additional assumptions. The authors should check if a similar pattern happens in Thm 3.11.
Thm C.1 only requires limsup (1/m) Σ_i w_il² > 0, i.e. a positive fraction of signal-carrying coordinates. A fraction of 6–17.5% is consistent with that condition. Moreover, a Gaussian PPCA is misspecified for non-negative, very sparse vectors (and, as discussed in W2, possibly under-sampled).
W7. The analysed scoring functions differ from those used in practice
Def 2.1 assumes a non-negative distance (called a "metric", although the proofs only use non-negativity). Thm 5.4 specifically assumes \ell_p distance between \ell_p-normalized vectors. Neither covers unnormalized inner-product scoring as used by SPLADE, and normalization changes SPLADE's ranking. Late-interaction MaxSim is covered only through an unstated reduction to Chamfer with cosine or squared-L2 distance over normalized vectors; this should be made explicit.
Missing references
- P. Indyk, H. Xu. Worst-case performance of popular approximate nearest neighbor search implementations: guarantees and limitations. NeurIPS 2023.
- S. Gollapudi, R. Krishnaswamy, K. Shiragur, H. Wardhan. Sort before you prune: improved worst-case guarantees of the DiskANN family of graphs. ICML 2025.
- L. Dhulipala, M. Hadian, R. Jayaram, J. Lee, V. Mirrokni. MUVERA: multi-vector retrieval via fixed dimensional encodings. NeurIPS 2024.
- A. Bakshi, P. Indyk, R. Jayaram, S. Silwal, E. Waingarten. A near-linear time algorithm for the Chamfer distance. NeurIPS 2023.
- U. Shaft, R. Ramakrishnan. Theory of nearest neighbors indexability. ACM TODS 31(3), 2006.
- M. Radovanović, A. Nanopoulos, M. Ivanović. Hubs in space: popular nearest neighbors in high-dimensional data. JMLR 11, 2010.
- M. Aumüller, M. Ceccarello. The role of local dimensionality measures in benchmarking nearest neighbor search. Information Systems 101, 2021.
Questions for authors
- For each real-data experiment, which m-indexed family do the asymptotic assumptions refer to? Can you show that the parameters are stable across that family, and as n grows to realistic corpus sizes?
- How do you reconcile the claim that average pooling is unstable with the plateau in Fig. 1?
- Why is stability of the fused distance the right notion for filtered search, rather than stability of \delta conditioned on f = 1? In E.2 the matching documents are equidistant from the query; isn't the filtered problem meaningless there for every \alpha?
- Does Thm 4.3 still hold without base stability when the mismatch probability is bounded below? If so, what role does the base-stability assumption play?
- Thm 5.4 bounds the relative variance over random (q, d) pairs. How do you rule out the case where A and B are realized by different queries? Can the bounded-expectation property be verified here?
- How do the results change for unnormalized inner-product scoring (SPLADE, MIPS)?
- Can you relate your conditions to the doubling-dimension-based guarantees for graph ANN (Indyk & Xu, 2023; Gollapudi et al., 2025)? Does any prediction of your theory translate into measurable recall or latency differences?
- Please report the parameters for the construction in App. D.3, the generator parameters for App. F.3, the database size n for every experiment, and whether code will be released.
We thank the reviewer for their detailed review. Please see our responses to the individual question below:
It is true that we validate these properties on finite-dimensional embeddings while the main theorems are asymptotic. Our goal in the empirical validation is not to argue that the theorem definitively apply but to illustrate that our assumptions are well-founded.
Many filtered algorithms proposed in the literature propose an infinite penalty value. Our bound, in some sense, aligns with this common choice. We can also avoid this concern of an unbounded Δ by normalizing the vectors.
Yes the values are indeed small but still non-zero which is all we need for our theorems. We can also look into these section further and see if we can tighten these assumptions so that the validation is more readily apparent.
Thank you for the question. As we stated in the introduction of the paper, our goal is not necessarily to guide practitioners in designing new algorithms, but to study, from a theoretical perspective, the stability properties of these vector search formulations.