acceptodds
Withdrawn from ICLR 2027

When is Multi-Vector, Filtered, and Sparse Nearest Neighbor Meaningful? On the Stability of Modern Vector Retrieval

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Modern vector databases enable efficient retrieval over high-dimensional neural embeddings, powering applications from web search to retrieval-augmented generation. However, classical theory predicts that for many high-dimensional workloads, nearest neighbor search should be inefficient as distances between points become nearly indistinguishable. Prior works have studied the notion of stability in traditional nearest-neighbor search, and identify stable workloads, which are amenable to efficient search. However, no existing research has studied stability in the context of modern formulations of similarity search that have gained traction in practice. Building on foundational results, we extend stability theory to three key retrieval settings: (i) multi-vector search, where we prove that the popular Chamfer distance metric preserves single-vector stability, while average pooling aggregation may destroy it; (ii) filtered vector search, where we show that sufficiently large penalties for mismatched filters can preserve stability; and (iii) sparse vector search, where we formalize and prove novel sufficient stability conditions via the concepts of concentration of importance and overlap of importance. Together, our results extend the classical theory of nearest neighbor meaningfulness to new retrieval settings prevalent in modern practice, offering an explanation for several of the empirically successful design choices behind state-of-the-art vector search systems.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
vector databases, nearest neighbor search, stability, multi-vector search, filtered search, learned sparse retrieval

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_FPzDOpenReview ↗
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
  1. 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?
  2. How do you reconcile the claim that average pooling is unstable with the plateau in Fig. 1?
  3. 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?
  4. 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?
  5. 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?
  6. How do the results change for unnormalized inner-product scoring (SPLADE, MIPS)?
  7. 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?
  8. 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.
Reviewer_CtyMOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper extends the classical stability framework of Beyer et al. (1999) and Durrant–Kabán (2009) to three modern retrieval settings: multi-vector search, filtered vector search, and sparse vector search. It proves stability-preservation theorems, constructs counterexamples, and validates theorem assumptions on real embeddings.

Critical strengths

S1: The paper studies an interesting problem.
S2. The paper provides several new theoretical results.
S3. The theoretical contributions are potentially useful, and some key assumptions have been validated by real-world datasets.

Critical weaknesses

W1. The stability framework is asymptotic in dimension, but the practical claims are finite-dimensional. The impact of dimensionality requires further validation.
W2. For filtered vector search, Theorem 4.3’s penalty bound can be very large in practice.
W3. The sparse-search result relies on relatively stronger assumptions.

Questions for authors

Q1. The empirical validation on dense retrieval often uses embedding datasets with dimensionalities of a few hundreds. The impact of dimensionality should be empirically validated.

Q2. In Theorem 4.3, the value of Δ\Delta depends on the maximum distance, which can be large or unbounded. If the required α\alpha is orders of magnitude larger than typical heuristics, the main result appears to be meaningless.

Q3. Theorem 5.4 assumes concentration of importance, overlap of importance, and a positive-probability event. The theorem’s conclusion is a lower bound on lim inf⁡m→∞RelVarm\liminf_{m\to\infty} \mathrm{RelVar}_m, and the reported empirical bounds (Table 5) are extremely small (e.g., 10−710^{-7}-10−610^{-6}). I wonder whether these bounds are meaningful for stability at finite dimension.

Q4. Although the paper proposes sound theoretical results, it is unclear what practitioners can benefit from them when designing either an index or a search algorithm.

1 comment

We thank the reviewer for their detailed review. Please see our responses to the individual question below:

  1. 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.

  2. 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 Δ\Delta by normalizing the vectors.

  3. 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.

  4. 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.

Reviewer_NdQfOpenReview ↗
Rating
2
Confidence
1
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper investigates a fundamental question in high-dimensional retrieval: when the nearest and farthest documents are almost equally distant from a query, how meaningful is nearest-neighbor search? Building on existing theory linking distance concentration to vanishing relative variance, the authors analyze stability in multi-vector, filtered, and sparse retrieval.

Critical strengths
  1. Relevant problem formulation. The paper extends the study of nearest-neighbor meaningfulness to multi-vector, filtered, and sparse retrieval, addressing settings that are important in modern retrieval systems.

  2. Interpretable theoretical conditions. The analysis identifies concrete properties—such as document-set non-degeneracy, covariance between token-level distances, and concentration and overlap of sparse-vector mass—that offer useful perspectives on when retrieval may retain distance contrast.

Critical weaknesses

The authors treat distance concentration in probability as equivalent to concentration in the second-moment sense, without establishing sufficient regularity conditions for this equivalence. This gap affects subsequent theorems that rely on the criterion.

Counterexample to Theorem 3.5

For m≥2m\ge2, let the query distribution and Chamfer distances be:

QueryProbabilityDistance to D1D_1Distance to D2D_2
Q0Q_01−m−21-m^{-2}111+m−11+m^{-1}
Q1Q_1m−2m^{-2}11mm

This is realizable using Euclidean distance on the first coordinate axis of Rm\mathbb R^m:

D_1=\{1,m+2+1/m\},\quad D_2=\{1+1/m\}.$$ Sample $D$ uniformly and independently of $Q$, and write $X_m=\operatorname{Chamfer}(Q,D)$. - **Instability:** The maximum-to-minimum distance ratio is $1+1/m$ with probability $1-m^{-2}$ and $m$ otherwise. Hence it converges to $1$ in probability. - **Bounded expectation:** The mean is $$\mu_m=1+\frac1m-\frac1{2m^2}-\frac1{2m^3}\in[1,1+1/m],$$ so $D_{\min}(Q)\le\mu_m\le D_{\max}(Q)$ for both queries. - **Nonvanishing relative variance:** Since $\mu_m\to1$ and $\mathbb E[X_m^2]\to3/2$, $$\operatorname{RelVar}(X_m)\to\frac12>0.$$ Thus the problem is **unstable despite nonvanishing relative variance**, contradicting Theorem 3.5 as stated. The proof incorrectly infers variance convergence from convergence in probability. Additional moment control, such as uniform integrability of $(X_m/\mu_m)^2$, is needed.
Questions for authors
  1. Probability space and assumptions. Are expectations, variances, and covariances computed over documents conditional on a fixed query, or jointly over queries and documents? Is the database size fixed as the dimension grows? Please clarify these choices in Theorems 3.5 and 3.11, since they affect the validity of the arguments.

  2. Validity of the relative-variance criterion. The proof of Theorem 3.5 infers convergence of variance from convergence in probability, which generally requires additional moment control. What assumptions justify this step, and do they hold in the settings considered by the subsequent theorems?

  3. Applicability to ColBERT. How do the finite-dimensional measurements in Table 3 support the dimension-independent assumptions of Theorem 3.11? In particular, can the authors report a common choice of cc that satisfies non-degeneracy while leaving a strictly positive strong-stability margin γ\gamma?

1 comment

We thank the reviewer for their thorough feedback, especially taking the time to write out a detailed counter example to Theorem 3.5. We reviewed the proposed counterexample carefully and it is correct. This counterexample applies not only to our Theorem 3.5 but also to the original theorem of Durrant and Kaban which we carried over directly for our theorem 3.5.

Response to Questions

  1. All quantities are over the joint distribution of queries and documents. We will make this more clear in the paper. The database sized is fixed as the dimension grows (this is a critical assumption as well)

  2. Yes, as we mentioned above, we believe Theorem 3.5 (as well as the original Theorem published by Durrant and Kaban) require an additional moment control assumption to be correct. Fortunately, after looking at the problem again, we believe that we can prove this stability result without Theorem 3.5 and instead directly from the definition of relative variance, so we may not need Theorem 3.5 at all.

  3. Thank you for raising this point. We use the same c for both conditions, but we picked the largest c possible, which leaves no margin, so we’ll check whether a slightly smaller c still passes non-degeneracy and report that, and we’ll say plainly that Table 3 only covers the dimensions we measured.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.