PaperlayerView exact revision on arXiv

Source-linked AI summary

Scaling Laws for Grid-Based Approximate Nearest Neighbor Search in High Dimensions

Matthew J Liu, Wei Hang Zheng, Vidhan Purohit, Siqi Xie, Chieh-En Li, Jerry Li, Noah Flynn

arXiv:2607.01283v1cs.LGcs.AI

TL;DR

Modern scaling analyses have undercharacterized grid-based approximate nearest neighbor search despite the importance of dataset-size and dimensionality scaling. This paper characterizes a multiprobe grid algorithm and finds favorable dimensional scaling alongside near-linear query scaling with dataset size.

  • Problem

    Grid-based ANN methods remain undercharacterized in modern scaling analyses, where existing approaches show regime-dependent trade-offs across dataset size and dimensionality.

  • Method

    The paper theoretically and empirically characterizes multiprobe grid scaling in N and d, selecting cells in a PCA-reduced subspace and reranking candidates in the full space.

  • Results

    Multiprobe grid maintains relatively flat dimensional scaling while other evaluated methods steepen at higher recall, despite near-linear query degradation with dataset size.

  • Takeaways & Limitations

    Grid-based ANN methods may be competitive in rebuild-heavy or high-dimensional settings where indexing cost and dimensional robustness matter.

  • Takeaways & Limitations

    The dimensional-scaling analysis is bounded at d = 200, leaving regimes such as d ≥512 for future work.

Abstract

from arXiv · show

Grid-based approaches to approximate nearest neighbor (ANN) search have been absent from modern scaling analyses. We present a systematic characterization of a multiprobe grid algorithm with respect to dataset size $N$ and dimensionality $d$. Our experiments reveal a previously unreported $d$-scaling crossover on the GloVe embedding family, in which multiprobe grid search maintains an approximately constant dimensional scaling exponent while other graph-, tree-, and partitioning-based methods exhibit degrading throughput. The advantage comes with near-linear query scaling in $N$, but also with lower indexing cost than competing ANN methods. Our results suggest that grid-based methods such as multiprobe grid may be competitive in rebuild-heavy or high-dimensional settings where indexing cost and dimensional robustness dictate performance. More broadly, recent work has formalized self-attention as an ANN operation. Thus, the $N$- and $d$-scaling properties of ANN algorithms may guide cost analysis of efficient transformer architectures. Code is available at: https://github.com/weiz345/MultiProbeANN.

1. Introduction

The introduction frames ANN search as a central operation for large, high-dimensional machine learning systems and transformer architectures. It motivates analyzing multiprobe grid search because dataset size and dimensionality create distinct challenges, while existing ANN families have regime-dependent trade-offs.

  • Motivation: ANN search supports large, high-dimensional machine learning systems and has become a computational primitive in transformer architectures.Recent studies formalize self-attention as an ANN operation over token embeddings, enabling sub-quadratic approximations to full attention.
  • Problem: Scaling N stresses candidate filtering and indexing efficiency, while scaling d worsens the curse of dimensionality and geometric pruning.These pressures contribute to regime-dependent trade-offs among graph-, tree-, and partitioning-based ANN methods.
  • Contribution: This work characterizes N- and d-scaling relationships for a multiprobe grid algorithm that decouples cell selection from d.Grid-based methods were foundational in early ANN theory but remain undercharacterized in modern scaling analyses relative to graph- and tree-based methods.

2. Theoretical scaling model for multiprobe grid search

The section develops a theoretical scaling model for multiprobe grid search by relating query cost to recall. Under its cell-partitioning and recall assumptions, the framework predicts a log-linear QPS–recall relationship driven by exponential probability decay and linear candidate growth.

  • Closed form and log-linearity: The framework predicts log QPS(R) ≈ log(const′) − log R, yielding a log-linear relationship between QPS and recall.The relationship arises from exponential decay of nearest-neighbor membership probability across probed cells and linear candidate-set growth with nprobe.
  • Cost model: The model partitions PCA-projected R^m space into G^m cells, each containing N/G^m points on average.This establishes the per-cell candidate-cost basis for multiprobe search.
  • Cost model: A query probes 1 ≤ nprobe ≤ 2^m cells, including its home cell and neighboring cells ordered by ascending wall distance.The probed-cell range defines the algorithm’s query budget.
  • Recall model: The recall model defines P_i as the probability that the true nearest neighbor lies in the i-th probed cell and assumes P_i decreases monotonically with wall distance.The model uses a uniform-distribution assumption and an exponential approximation for this decay.

3. Empirical scaling laws

Across five ANN algorithms, multiprobe grid shows near-linear query degradation with dataset size but a relatively flat dimensionality exponent, producing a crossover in d-scaling at higher recall. It also offers fast indexing, while the d-scaling characterization is limited to d = 200.

  • Experimental setup: The evaluation compares multiprobe grid with Voyager, PyNNDescent, Annoy, and FAISS-IVF under single-CPU isolation using ann-benchmarks.The baselines represent graph-, tree-, and quantization-based partitioning ANN families.
  • Pareto fronts: At recall@k=10 > 0.9, multiprobe throughput converges toward brute-force as higher recall requires densely populated cells or more probes.Figure 1 reports log(QPS) decreasing linearly with increasing recall, consistent with performance being determined by grid geometry.
  • N-scaling: At recall@k=10 = 0.80, multiprobe grid has αN = −0.94 (R2 = 1.00), versus baseline exponents from −0.44 to −0.59.The result indicates near-linear degradation of QPS with dataset size, while baseline scaling is sublinear.
  • N-scaling: At recall@k=10 = 0.80 on SIFT-128-euclidean, multiprobe grid has αN = −0.83 (R2 = 1.00), versus baseline exponents between −0.27 and −0.39.The log-linear Pareto behavior and relative αN trends are preserved beyond word embeddings.
  • d-scaling: Beyond recall 0.7, αd steepens dramatically for every method except multiprobe grid, whose αd remains relatively flat, creating a d-scaling crossover.The crossover reverses the usual pattern: the method with the least favorable N-scaling has the most favorable d-scaling at high recall.
  • Limitations: The d-scaling characterization is bounded by d = 200 because GloVe is the only d-varying dataset family available in ann-benchmarks.The observed crossover is therefore demonstrated only across the available GloVe dimensionality range.
  • Indexing cost: At N = 1.18 × 10^6, multiprobe grid builds in 4–36 sec, compared with 206 sec for FAISS-IVF, 333 sec for Annoy, 500 sec for PyNNDescent, and 1,569 sec for Voyager.Multiprobe grid and FAISS-IVF are fastest across all N; multiprobe uses PCA fitting, cell assignment, and BFS precomputation.

Appendix A. Related work

ANN methods trade exactness for speed through indexing strategies including tree-, hash-, quantization-, graph-, and partitioning-based approaches. Grid-based methods remain comparatively underexplored despite their structural simplicity, low indexing cost, and predictable query behavior.

  • ANN method landscape: ANN search retrieves high-quality candidate sets that approximate true nearest neighbors while trading exactness for speed.
  • ANN method landscape: Indexing strategies include tree-based, hash-based, quantization-based, and graph-based methods, with hashing and quantization often grouped as partitioning-based methods.Partitioning-based methods divide the search space into discrete regions to prune candidates.
  • Grid-based methods: Early grid-based ANN studies used translated grids to mitigate exponential dimensional dependence and remove logarithmic factors in batched queries.The bucketing method subsequently achieved constant-time hash evaluations independent of dataset size.
  • Graph-based methods: Modern ANN systems frequently use graph-based indices such as HNSW, whose multi-layer proximity-graph traversal can face capacity-limited failure when exploration is insufficient.Insufficient exploration can cause abrupt degradation in neighbor quality.
  • Research gap: Grid-based approaches remain comparatively underexplored in benchmarking and scaling studies despite structural simplicity, low indexing cost, and predictable query behavior.Existing studies primarily focus on graph-based, tree-based, and adaptive partitioning methods.

Appendix B. Derivation of the Multiprobe Grid Scaling Model … B.5. Geometric closed form

The appendix derives a probabilistic query-cost–recall approximation for multiprobe grid search under uniform cell-scale distributions, using orthant-pruned probes, wall-distance ordering, and a geometric recall model. It yields an analytical recall range bounded by the home-cell probability and the maximum geometric-series sum.

  • Appendix B. Derivation of the Multiprobe Grid Scaling Model: The model approximates average query cost versus recall under uniform query and data distributions at the cell scale, excluding PCA-induced rank distortion.Extending the derivation to PCA-induced distortion is left for future work.
  • B.1. Probe Setup and Cell Offsets: Orthant pruning generates 2^m −1 non-home neighboring cells instead of 3^m −1 full-neighborhood cells.The candidate displacements arise from the Cartesian product of m binary offset choices.
  • B.2. Wall distance ordering and cost model: Probes are sorted by ascending squared wall distance, and only the first nprobe ≤2^m −1 cells are searched before native d-space reranking.This ordering defines which candidate cells contribute to the approximate search.
  • B.2. Wall distance ordering and cost model: Each probed cell contributes N/G^m points on average, so candidate ranking is linear in the resulting candidate count.The constant K > 0 absorbs per-candidate distance computations, comparisons, and bookkeeping.
  • B.3. Recall as a sum of cell-membership probabilities: Under uniform cell-scale distributions, nearest-neighbor membership probabilities decrease with sorted wall distance and are modeled using an exponential fall-off.The resulting probabilities satisfy P0 ≥P1 ≥· · · ≥Pnprobe under the adopted mean-field approximation.
  • B.4. Expected wall distance via offset geometry: Replacing cell-specific wall distances by uniform-query expectations produces plateaus at jL for offset vectors with j nonzero coordinates.The expected wall-distance ordering groups cells by offset Hamming weight.
  • B.4. Expected wall distance via offset geometry: The arithmetic mean gap equals the telescoping transition contribution across the m plateaus, yielding θ = 3L/7 for m = 3.The m transitions each contribute L while within-plateau increments are zero.
  • B.5. Geometric closed form: Approximating expected wall distances linearly gives Pi ≈Ph∆i and expresses recall as a geometric series with bounds Rmin = Ph and Rmax = Ph · 1 −∆2^m.The stated lower bound corresponds to nprobe = 1; the displayed upper-bound expression is the maximum achievable recall range in the closed form.

B.6. Log-QPS derivation: from geometric closed form to exponential

The derivation transforms a geometric closed form into an approximate power-law QPS ∝ 1/R, then uses local linearization of log R to recover the empirical exponential throughput–recall relation. Its validity depends on low µθ, locally similar cell densities, and recall bounded away from Rmax.

  • Geometric-to-log derivation: Solving the geometric closed form for nprobe and substituting it into the cost formula yields an explicit QPS expression with signs clarified for ln(1−R/Rmax) and ln ∆.Both logarithms are negative because R/Rmax and ∆ lie in (0, 1).
  • Taylor approximation: First-order Taylor expansion of −ln(1−u), where u = R/Rmax, is local: relative error is approximately 28% at u = 0.5 and 50% at u ≈ 0.8, diverging as u → 1.The resulting closed form is accurate when u is bounded away from 1.
  • Mean-field approximation: Under the mean-field assumption, µθ ≪ 1 implies ∆ = e−µθ ≈ 1 and |ln ∆| ≪ 1, reflecting gradual decay across adjacent cells.This assumes queries are uniform within the home cell and data are approximately uniform at single-cell scale.
  • Mean-field approximation: The mean-field regime requires grid cells small relative to the scale of density variation, although real GloVe and SIFT distributions violate literal uniformity and require locally similar adjacent-cell densities in practice.The assumption also corresponds to a well-calibrated grid index.
  • Power-law intermediate form: Dropping ln ∆ and expanding log(R/Rmax) gives log QPS(R) ≈ log(const · Rmax) − log R, hence QPS ∝ 1/R.The bound gap from dropping ln ∆ shrinks to zero as µθ → 0.
  • Exponential form: Linearizing log R over [Rmin, Rmax] and exponentiating yields QPS(R) ≈ A′e−B′R, with B′ = B ln 10 and B scaling inversely with Rmax.This converts the power-law dependence into the log-linear throughput–recall relation observed empirically.

B.7. Validity, robustness, and empirical correspondence

The log-linear QPS–recall form is structurally robust despite approximations that degrade at high recall, while dimensionality affects Pareto-optimal configurations rather than the closed form’s functional shape.

  • Validity and limitations: The closed form relies on Taylor truncation, a mean-field assumption, and local linearization of log R, with Taylor and mean-field errors worsening at high recall.The high-recall regime also contains the empirical d-scaling crossover.
  • Robustness of the log-linear form: The qualitative log-linear shape is structural rather than approximation-dependent, despite non-uniform embedding distributions violating the mean-field assumption.The shape follows from combining saturating-concave recall with linear cost.
  • Robustness of the log-linear form: Recall increases monotonically but saturates with nprobe, while cost grows linearly because each probed cell contributes a fixed expected candidate count N/Gm.Together, these mechanics produce cost that grows faster than linearly as recall approaches its ceiling, yielding a near-straight line on log-y versus linear-recall axes.
  • Relevance to the d-scaling crossover: The closed form describes the QPS–recall Pareto-front shape for a fixed dataset, whereas αd describes fixed-recall QPS scaling across datasets with different dimensionality.The closed form has no d-dependence; dimensionality instead influences the Pareto-optimal (m, G, nprobe) configuration empirically.

Appendix C. Implementation and Experimental Details … C.1.2. Query processing

The multiprobe grid implementation projects data and queries into a lower-dimensional PCA space partitioned into uniform cells. Query processing searches the primary cell and, when requested, nearby cells selected by wall distance within a bounded geometric orthant.

  • C.1.1. Index construction: PCA projects each data point from R^d to R^m, with grid dimensionality m ≪ d treated as a hyperparameter.The projection reduces the dimensionality before grid indexing.
  • C.1.1. Index construction: The projected space is partitioned into G^m uniform grid cells, where G denotes the number of splits per dimension.Cells are defined uniformly across the m-dimensional projected space.
  • C.1.1. Index construction: Each grid cell stores the indices of data points whose projections fall within that cell’s boundaries.The index associates projected points with their containing cells.
  • C.1.2. Query processing: For a query q ∈ R^d, the method projects q into PCA space and identifies the cell containing the projected vector q′.Query processing applies the same projection used for data points.
  • C.1.2. Query processing: When nprobe = 1, query processing searches only the primary cell; when nprobe > 1, it also probes nprobe − 1 nearest neighboring cells.The probe count controls whether neighboring cells are searched.
  • C.1.2. Query processing: Neighboring cells are ranked by wall distance, defined as the squared Euclidean distance from q′ to each shared cell boundary.The ranking uses distance to cell boundaries rather than cell centers.
  • C.1.2. Query processing: To bound the search space, the query considers only the 2^m cells in the geometric orthant.The orthant restriction limits which cells can be probed.

C.2. Experimental setup · C.2.1. Baselines · C.2.2. Hyperparameter tuning for multiprobe grid

The experiments use standardized single-CPU ann-benchmarks evaluations, measuring recall@k = 10 and queries per second (QPS). They compare multiprobe grid against representative ANN families and tune its three hyperparameters through multi-objective optimization.

  • C.2. Experimental setup: All experiments use the ann-benchmarks framework with Docker containers enforcing single-CPU execution per algorithm.
  • C.2. Experimental setup: Recall@k = 10 is the accuracy metric, while queries per second (QPS) is the throughput metric.
  • C.2.1. Baselines: Multiprobe grid search is compared with Voyager, PyNNDescent, Annoy, and FAISS-IVF.These baselines represent graph-based, tree-based, and quantization-based partitioning ANN families.
  • C.2.1. Baselines: Brute-force search provides a reference for performance metrics such as queries per second (QPS) and identifies ground truth nearest neighbors.
  • C.2.2. Hyperparameter tuning for multiprobe grid: Multiprobe grid has three hyperparameters: grid dimensionality m, grid splits G, and probe count nprobe.The pair (m, G) determines the index structure, while nprobe affects the recall-latency tradeoff at query time.
  • C.2.2. Hyperparameter tuning for multiprobe grid: 200 trials of NSGA-II multi-objective optimization identify Pareto-optimal (m, G) pairs on the GloVe-200-angular dataset.The same configurations are applied to subsampled GloVe-200 and to GloVe-25, -50, and -100-angular.

C.2.3. Scaling analysis

The scaling analysis fits log(QPS) against dataset size or dimensionality, using the exponent α_x to quantify throughput changes and Pareto-front interpolation at target recall. It evaluates N-scaling on subsampled GloVe-200 and SIFT-128 datasets and d-scaling across equal-sized GloVe embeddings with varying native dimensionality.

  • Method: Scaling exponents α_x are estimated by fitting log(QPS) = α_x log(x)+b, with x equal to N or d.For each algorithm, dataset, and recall target, QPS is interpolated in log10(QPS) between Pareto-optimal configurations bracketing the target recall.
  • N-scaling: N-scaling uses GloVe-200-angular samples from 104 to 1.18 × 106 points and SIFT-128-euclidean samples from 104 to 106 points.Ground truth for k = 10 nearest neighbors is recomputed for each subsample via brute-force.
  • d-scaling: d-scaling compares GloVe-25, GloVe-50, GloVe-100, and GloVe-200, each with N = 1.18 × 106 and native d ∈{25, 50, 100, 200}.The four datasets share the same source distribution while varying native dimensionality.

C.3. Profiling analysis of multiprobe grid

The profiling analysis tests whether Python-specific overhead distorts multiprobe grid scaling, separating algorithmic NumPy/BLAS work from interpreter-bound orchestration. It concludes that, for datasets with appreciable N, algorithmic cost dominates, so reported exponents reflect algorithmic complexity rather than implementation language.

  • Motivation: Multiprobe grid is implemented in Python, whereas Voyager, PyNNDescent, Annoy, and FAISS-IVF use highly optimized C++ baselines.The analysis specifically examines interpreter overhead, memory allocation, and orchestration loops as possible influences on scaling exponents.
  • First-principles reasoning: Per-query cost decomposes into algorithmic NumPy/BLAS kernel work and interpreter-bound orchestration overhead.Examples include PCA projection, candidate gathering, re-ranking, primary-cell lookup, and neighbor-cell enumeration.
  • Empirical profiling: Profiling used cProfile on GloVe-200-angular across three N scales spanning two orders of magnitude, with m=6, G=5, nprobe=16, and 1,000 queries per N.The query path was decomposed into named phase functions for per-phase timing attribution.
  • First-principles reasoning: For modern datasets of appreciable N, algorithmic cost dominates, making overhead negligible and leaving scaling exponents representative of algorithmic complexity.The additive overhead does not affect the slope of a log–log fit in this regime.

C.4. Derivation of the rebuild-to-query crossover · Appendix D. Supplementary Figures · Appendix E. Supplementary Tables

The appendices derive when multiprobe grid’s lower indexing cost offsets its higher query latency and document supplementary scaling, algorithmic, and configuration analyses. For GloVe-200, the rebuild-to-query crossover spans approximately 2,600–20,400 queries depending on the baseline.

  • C.4. Derivation of the rebuild-to-query crossover: Multiprobe grid beats a baseline when its total cost satisfies Jgrid < Jbaseline, with the identical memory term canceling from the comparison.The reduced condition compares rebuild and query costs only.
  • C.4. Derivation of the rebuild-to-query crossover: Multiprobe’s lower indexing cost and higher per-query latency define a crossover ratio fC/fI, below which multiprobe has lower total cost.Here, fC/fI is the expected number of queries per index rebuild.
  • C.4. Derivation of the rebuild-to-query crossover: 2,600–20,400 queries is the GloVe-200 rebuild-to-query crossover range, bounded by FAISS-IVF at 2,591 and Voyager at 20,432.The comparison uses N = 1.18 × 10^6 and Pareto-optimal configurations nearest to recall@k=10 =0.80; multiprobe’s anchor is (m=6, G=5).
  • Appendix D. Supplementary Figures: Supplementary figures visualize the multiprobe grid pipeline, Pareto fronts, N- and d-scaling exponents, PCA variance retention, build-time and memory scaling, and BFS fallback frequency.The figures cover GloVe, SIFT-128-euclidean, and varying dataset size, dimensionality, recall targets, and grid-search parameters.
  • Appendix D. Supplementary Figures: Supplementary scaling plots derive αN and αd from slopes of interpolated log10(QPS) relationships at each target recall.Points are omitted when no benchmark configuration achieves the target recall.
  • Appendix D. Supplementary Figures: The supplementary figures also examine PCA variance as a function of projection components and native dimensionality, plus indexing memory, build time, and BFS fallback behavior.BFS fallback analyses vary grid splits G, probe budget nprobe, dataset size N, and dimensionality d while holding the other variables constant.
  • Appendix E. Supplementary Tables: Table E1 lists Pareto-optimal multiprobe grid configurations (m, G, nprobe) for GloVe-25, -50, -100, and -200-angular at each target recall.Parenthetical values give measured recall@k=10, and the d=200 entries at target recalls 0.95 and 0.90 match.
Loading 2607.01283v1…