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

# Scaling Laws for Grid-Based Approximate Nearest Neighbor Search in High Dimensions
Source: [https://arxiv.org/html/2607.01283](https://arxiv.org/html/2607.01283)
\\hldauthor\\Name

Matthew J\. Liu\\Emailmatthewliu@berkeley\.edu \\addrUniversity of California, Berkeley and\\NameWei Hang Zheng\\Emailweihang\_zheng@berkeley\.edu \\addrUniversity of California, Berkeley and\\NameVidhan Purohit\\Emailviddyp1804@gmail\.com \\addrUniversity of Toronto, St\. George and\\NameSiqi Xie\\Emailsiqixie@alumni\.cmu\.edu \\addrIndependent Researcher and\\NameChieh\-En Li\\Emailchiehenli@gmail\.com \\addrIndependent Researcher and\\NameJerry Li\\Emailli\.zhiyi\.jerry@gmail\.com \\addrUniversity of Waterloo and\\NameNoah Flynn\\Emailnoahflynn@berkeley\.edu \\addrUniversity of California, Berkeley

###### Abstract

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 sizeNNand dimensionalitydd\. Our experiments reveal a previously unreporteddd\-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 inNN, 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, theNN\- anddd\-scaling properties of ANN algorithms may guide cost analysis of efficient transformer architectures\. Code is available at:\\urlhttps://github\.com/weiz345/MultiProbeANN\.

## 1Introduction

Approximate nearest neighbor \(ANN\) search is central to modern machine learning systems operating on large, high\-dimensional datasets\[darrell\_nearest\-neighbor\_2005\]\. Beyond its classical role in retrieval, ANN has emerged as 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\[haris\_knn\_2025,liu\_fast\_2025,kang\_attention\_2025\]\. As empirical scaling laws guide transformer design\[kaplan\_scaling\_2020\], the scaling behavior of ANN algorithms is increasingly relevant to the development of more efficient transformer architectures\. In particular, scaling dataset sizeNNstresses candidate filtering and indexing efficiency, while scaling dimensionalityddexacerbates the curse of dimensionality and degrades the effectiveness of geometric pruning\. As a result, ANN methods including graph\-, tree\-, and partitioning\-based approaches exhibit regime\-dependent trade\-offs in which no method dominates universally\[xiao\_enhancing\_2024,iff\_benchmarking\_2026\]\.

Grid\-based methods \(a variant of partitioning approaches\) played a foundational role in early ANN theory\[indyk\_approximate\_1998,chan\_approximate\_1997\], but remain undercharacterized relative to graph\- and tree\-based methods in modern scaling analyses \(see Appendix[A](https://arxiv.org/html/2607.01283#A1)for Related Work\)\. In this work, we characterizeNNandddscaling relationships for a multiprobe grid algorithm \(overview in Section[2](https://arxiv.org/html/2607.01283#S2)\) that decouples cell selection fromdd, where cell selection denotes the query\-time procedure that identifies which grid cells supply candidate vectors\. This decoupling is achieved by performing cell selection in a PCA\-reduced subspaceℝm\\mathbb\{R\}^\{m\}while re\-ranking candidates inℝd\\mathbb\{R\}^\{d\}\. We show that while multiprobe grid exhibits near\-linear scaling withNN, itsdd\-scaling behavior remains favorable as dimensionality increases\. This work situates grid\-based methods within the broader ANN design space and highlights regimes in which they offer competitive trade\-offs\.

## 2Theoretical scaling model for multiprobe grid search

We provide a theoretical overview for the multiprobe grid algorithm, deriving a closed\-form relationship between query cost and recall\. Appendix[B](https://arxiv.org/html/2607.01283#A2)contains the full discussion and Figure[D1](https://arxiv.org/html/2607.01283#A4.F1)provides an overview schematic for the algorithm\.

##### Cost model\.

After PCA projection toℝm\\mathbb\{R\}^\{m\}, the space is partitioned intoGmG^\{m\}cells withN/GmN/G^\{m\}points each\. A queryqqprobes a total of1≤nprobe≤2m1\\leq n\_\{\\mathrm\{probe\}\}\\leq 2^\{m\}cells, consisting of the home cellchc\_\{h\}\(defined in Appendix[B\.1](https://arxiv.org/html/2607.01283#A2.SS1)\) and up to2m−12^\{m\}\-1neighboring cells ordered ascending by wall distancewi2w\_\{i\}^\{2\}\(Appendix[B\.2](https://arxiv.org/html/2607.01283#A2.SS2)\)\. Each probed cell contributes, on average,N/GmN/G^\{m\}candidates to the cost:

cost=1/QPS=K⋅nprobe⋅NGm\.\\mathrm\{cost\}\\;=\\;1/\\mathrm\{QPS\}\\;=\\;K\\cdot n\_\{\\mathrm\{probe\}\}\\cdot\\frac\{N\}\{G^\{m\}\}\.\(1\)

##### Recall model\.

LetPi=Pr⁡\[x∗∈ci\]P\_\{i\}=\\Pr\[x^\{\*\}\\in c\_\{i\}\]be the probability that the true nearest neighbor lies in theii\-th probed cell\. Under the uniform distribution assumption,PiP\_\{i\}decreases monotonically inwi2w\_\{i\}^\{2\}, and we adopt the exponential approximation \(Appendices[B\.3](https://arxiv.org/html/2607.01283#A2.SS3)and[B\.6](https://arxiv.org/html/2607.01283#A2.SS6)\)\.

Pi≈Ph​e−μ​wi2,Ph:=P0,μ\>0P\_\{i\}\\;\\approx\\;P\_\{h\}\\,e^\{\-\\mu w\_\{i\}^\{2\}\},\\qquad P\_\{h\}:=P\_\{0\},\\ \\mu\>0\(2\)

##### Closed form\.

Using a linear approximation𝔼​\[wi2\]≈θ​i\\mathbb\{E\}\[w\_\{i\}^\{2\}\]\\approx\\theta i\(Appendix[B\.4](https://arxiv.org/html/2607.01283#A2.SS4)\) on the mean gap yields

R​\(nprobe\)=Ph​∑i=0nprobe−1Δi=Ph⋅1−Δnprobe1−Δ,Δ:=e−μ​θ∈\(0,1\)R\(n\_\{\\mathrm\{probe\}\}\)\\;=\\;P\_\{h\}\\sum\_\{i=0\}^\{n\_\{\\mathrm\{probe\}\}\-1\}\\Delta^\{i\}\\;=\\;P\_\{h\}\\cdot\\frac\{1\-\\Delta^\{n\_\{\\mathrm\{probe\}\}\}\}\{1\-\\Delta\},\\Delta:=e^\{\-\\mu\\theta\}\\in\(0,1\)\(3\)

##### Log\-linearity\.

Solving equation[3](https://arxiv.org/html/2607.01283#S2.E3)fornproben\_\{\\mathrm\{probe\}\}, substituting into equation[1](https://arxiv.org/html/2607.01283#S2.E1), and inverting gives

QPS​\(R\)=GmK​N⋅\|ln⁡Δ\|−ln⁡\(1−R/Rmax\)\.\\mathrm\{QPS\}\(R\)\\;=\\;\\frac\{G^\{m\}\}\{KN\}\\cdot\\frac\{\|\\ln\\Delta\|\}\{\-\\ln\(1\-R/R\_\{\\max\}\)\}\.\(4\)Taking logs, we arrive atlog⁡QPS​\(R\)≈log⁡\(const′\)−log⁡R\\log\\mathrm\{QPS\}\(R\)\\approx\\log\(\\mathrm\{const\}^\{\\prime\}\)\-\\log R\. Thus, our framework predicts a log\-linear relationship between QPS and recall, arising from the exponential decay of nearest\-neighbor membership probability across probed cells and the linear growth of candidate set size withnproben\_\{\\mathrm\{probe\}\}\.

## 3Empirical scaling laws

We evaluate our multiprobe grid algorithm against four baselines representing major ANN families: Voyager \(graph\-based\)\[noauthor\_spotifyvoyager\_2026\], PyNNDescent \(graph\-based\)\[mcinnes\_lmcinnespynndescent\_2026\], Annoy \(tree\-based\)\[noauthor\_spotifyannoy\_2026\], and FAISS\-IVF \(quantization\-based partitioning\)\[noauthor\_facebookresearchfaiss\_2026\]\. Algorithms are evaluated using theann\-benchmarksframework\[aumuller\_ann\-benchmarks\_2020,aumuller\_reproducibility\_2021\], executing each method in a dedicated Docker container to enforce single\-CPU isolation\. The baseline implementations use highly optimized C\+\+ implementations, while our multiprobe grid implementation is a Python\-based proof\-of\-concept\. Consequently, the measured QPS for multiprobe grid likely understates the throughput attainable with a comparably optimized implementation\. Nonetheless, we expect that the relative scaling trends reported here remain informative, given that multiprobe grid’s per\-query time is primarily spent in NumPy/BLAS \(see profiling study in Appendix[C](https://arxiv.org/html/2607.01283#A3)\)\. Baseline algorithms use their establishedann\-benchmarksparameter sweeps, which represent well\-explored, community\-validated search spaces; the multiprobe grid algorithm required bespoke NSGA\-II tuning to identify competitive configurations \(Appendix[C](https://arxiv.org/html/2607.01283#A3)for implementation details\)\.

### 3\.1Pareto fronts reveal a log\-linear throughput\-recall relationship for multiprobe grid

Figure[1](https://arxiv.org/html/2607.01283#S3.F1)shows Pareto fronts on GloVe\-200\-angular \(N=1\.18×106N=1\.18\\times 10^\{6\}points\)\[pennington\_glove\_2014,aumuller\_ann\-benchmarks\_2020,aumuller\_reproducibility\_2021\]for all five algorithms\. Consistent with Section[2](https://arxiv.org/html/2607.01283#S2), multiprobe grid shows thatlog⁡\(QPS\)\\log\(\\mathrm\{QPS\}\)decreases linearly with increasing recall, indicating that performance is determined by grid geometry\. At recall@kk=10\>0\.9\>0\.9, multiprobe’s throughput converges toward brute\-force: achieving high recall requires either coarse PCA projections \(m=2m\{=\}2\) that produce densely\-populated cells, or exhaustive multiprobing at highermm, resulting in ranking a large fraction of the dataset\. We show individual Pareto fronts at each subsampledNNfor GloVe\-200 anddd\(GloVe\-25, 50, 100, 200\) in Figures[D2](https://arxiv.org/html/2607.01283#A4.F2)–[D3](https://arxiv.org/html/2607.01283#A4.F3)\.

![Refer to caption](https://arxiv.org/html/2607.01283v1/x1.png)Figure 1:Pareto fronts for GloVe\-200\-angular \(d=200d=200,N=1\.18×106N=1\.18\\times 10^\{6\}\)\.
### 3\.2NN\-scaling: multiprobe grid scales near\-linearly with dataset size

#### 3\.2\.1GloVe dataset \(angular\)

Figure[2](https://arxiv.org/html/2607.01283#S3.F2)a shows how theNN\-scaling exponentαN\\alpha\_\{N\}varies with recall across all five ANN algorithms\. At recall@kk=10=0\.80=0\.80, multiprobe grid exhibitsαN=−0\.94\\alpha\_\{N\}=\-0\.94\(R2=1\.00R^\{2\}=1\.00\), indicating near\-linear degradation of QPS with dataset size\. In contrast, we observe sublinear scaling for the baselines, ranging fromαN=−0\.44\\alpha\_\{N\}=\-0\.44to−0\.59\-0\.59\. Figure[D4](https://arxiv.org/html/2607.01283#A4.F4)shows thelog10⁡\(QPS\)\\log\_\{10\}\(\\mathrm\{QPS\}\)vs\.log⁡\(N\)\\log\(N\)plots at each target recall@kk=10 used to derive the exponents in Figure[2](https://arxiv.org/html/2607.01283#S3.F2)a\.

The near\-linearNN\-scaling of multiprobe is mechanistically expected: for fixed grid parameters\(m,G\)\(m,G\), the candidate count per cell grows asN/GmN/G^\{m\}, and re\-ranking cost is linear in candidate count\. As recall targets increase, all algorithms’ exponents trend towardαN=−1\\alpha\_\{N\}=\-1, reflecting how perfect recall requires exhaustive search\. Multiprobe’s exponent is already near its asymptotic value across the full recall range, while baseline methods degrade more rapidly at higher recalls\.

#### 3\.2\.2SIFT\-128 dataset \(Euclidean\)

To investigate whether the observedNN\-scaling relationships generalize beyond word embeddings, we repeat the analysis on SIFT\-128\-euclidean \(image descriptors,d=128d=128\)\[jegou\_product\_2011\]\. The log\-linear Pareto behavior of multiprobe grid \(Figure[D5](https://arxiv.org/html/2607.01283#A4.F5)\) and relative trends inαN\\alpha\_\{N\}are preserved \(Figures[D6](https://arxiv.org/html/2607.01283#A4.F6)–[D7](https://arxiv.org/html/2607.01283#A4.F7)\)\. At recall@kk=10=0\.80=0\.80, multiprobe grid exhibits a scaling exponentαN=−0\.83\\alpha\_\{N\}=\-0\.83\(R2=1\.00R^\{2\}=1\.00\), while baseline algorithms fall between−0\.27\-0\.27and−0\.39\-0\.39\. The consistency across data modality \(images vs\. words\) and similarity metric \(Euclidean vs\. angular\) suggests thatNN\-scaling in multiprobe grid is intrinsic to the algorithm rather than dataset\-specific\.

![Refer to caption](https://arxiv.org/html/2607.01283v1/x2.png)Figure 2:Scaling exponents vs\. recall@kk=10 for all five algorithms\.\(a\)NN\-scaling exponentαN\\alpha\_\{N\}\. Datasets: GloVe\-200\-angular \(d=200\)d=200\)subsampled at varyingNN\.\(b\)dd\-scaling exponentαd\\alpha\_\{d\}\. Datasets: GloVe\-25\-, 50\-, 100\-, and 200\-angular \(N=1\.18×106N=1\.18\\times 10^\{6\}\)\.

### 3\.3dd\-scaling: multiprobe grid is increasingly competitive for higher dimensional data

Figure[2](https://arxiv.org/html/2607.01283#S3.F2)b shows how thedd\-scaling exponentαd\\alpha\_\{d\}varies with recall, revealing a non\-monotonic crossover between multiprobe grid and the other four algorithms\. As recall increases beyond 0\.7,αd\\alpha\_\{d\}of all algorithms besides multiprobe grid steepen dramatically, reflecting lower throughput with increasing dimensionality\. Meanwhile,αd\\alpha\_\{d\}for multiprobe grid remains relatively flat\. The contrast is notable given that prior empirical studies, including our own in Figure[2](https://arxiv.org/html/2607.01283#S3.F2)a, typically findNN\-scaling exponents to be remarkably consistent across algorithm families\(sun\_scaling\_2025\)\. Thedd\-scaling crossover subverts this universality \- the same algorithm that exhibits the least favorableNN\-scaling simultaneously exhibits the most favorabledd\-scaling at high recall\. Figure[D8](https://arxiv.org/html/2607.01283#A4.F8)shows thelog10⁡\(QPS\)\\log\_\{10\}\(\\mathrm\{QPS\}\)vs\.log⁡\(d\)\\log\(d\)plots at each target recall@kk=10 used to derive the exponents in Figure[2](https://arxiv.org/html/2607.01283#S3.F2)b\.

The crossover inαd\\alpha\_\{d\}arises from how each algorithm interacts withdd\. Graph\-based methods \(Voyager, PyNNDescent\) construct and traverse proximity graphs in the fulldd\-dimensional space\. At high recall, accurate retrieval requires exploring larger neighborhoods and more backtracking\. Similarly, tree\-based \(Annoy\) and quantization\-based partitioning \(FAISS\-IVF\) methods operate on the rawdd\-dimensional vectors, where pruning effectiveness degrades asddgrows\. In contrast, multiprobe grid performs cell selection in a PCA subspace of dimensionalitym≪dm\\ll d\. Although PCA retains a smaller fraction of total variance asddincreases \(Figure[D9](https://arxiv.org/html/2607.01283#A4.F9)\), the Pareto\-optimal\(m,G\)\(m,G\)adapts with bothddand the target recall rather than remaining fixed \(Appendix Table[E1](https://arxiv.org/html/2607.01283#A5.T1)\)\. At higherdd, fewer total cellsGmG^\{m\}are favored, concentrating more candidates per probed cell to preserve recall\. Because re\-ranking grows only linearly in candidate count, the query cost scales less aggressively withddthan for methods that traverse the fulldd\-dimensional space\. We note that ourdd\-scaling characterization is bounded byd=200d=200, the maximum dimensionality available in the GloVe family \(the onlydd\-varying dataset family provided inann\-benchmarks\)\. While this range demonstrates theαd\\alpha\_\{d\}crossover, extending our analysis to higher\-ddregimes \(e\.g\.,d≥512d\\geq 512for modern transformer embeddings\) is a key direction for future work \(Section[3\.5](https://arxiv.org/html/2607.01283#S3.SS5)\)\.

### 3\.4Total cost analysis reveals competitive regimes for multiprobe grid

Figure[D10](https://arxiv.org/html/2607.01283#A4.F10)shows build time scaling withNNfor the Pareto\-optimal configuration achieving recall@kk= 10≈0\.80\\approx 0\.80\. Multiprobe grid and FAISS\-IVF are fastest across allNN\. AtN=1\.18×106N=1\.18\\times 10^\{6\}, multiprobe grid builds its index in 4–36 sec depending on the selected hyperparameter configuration \(4 sec for the smallest config,m=2,G=4m\{=\}2,G\{=\}4; 36 sec for the largest,m=7,G=7m\{=\}7,G\{=\}7\)\. We measure 206 sec for FAISS\-IVF, 333 sec for Annoy, 500 sec for PyNNDescent, and 1,569 sec for Voyager\. Multiprobe grid indexing requires only PCA fitting, cell assignment, and BFS precomputation, whereas baselines rely on data\-dependent operations such as graph insertion by repeated nearest\-neighbor queries \(Voyager, PyNNDescent\)\.

Recent work by Sun et al\. established power\-law scaling relationships for different ANN methods like brute\-force, partitioning\-based, and graph\-basedsun\_scaling\_2025\. The study proposed a framework for the total costJJof ANN search that is a function of query\-time compute, indexing, and storage costs:J​\(N\)=fI⋅I​\(N\)\+fC⋅C​\(N\)\+S​\(N\)J\(N\)=f\_\{I\}\\cdot I\(N\)\+f\_\{C\}\\cdot C\(N\)\+S\(N\), whereII,CC, andSSdenote indexing, compute, and storage costs, andfIf\_\{I\},fCf\_\{C\}their respective frequency of occurrence\. We adapt the cost framework with one substitution, reporting memory footprintM​\(N\)M\(N\)in place ofS​\(N\)S\(N\), becauseann\-benchmarksmeasures process RSS during indexing rather than on\-disk storage size\. Table[1](https://arxiv.org/html/2607.01283#S3.T1)shows empirical scaling exponents at recall@kk=10=0\.80=0\.80on GloVe\-200\-angular\.C​\(N\)C\(N\)corresponds directly to the values shown in Figure[2](https://arxiv.org/html/2607.01283#S3.F2)a for recall@kk=10=0\.80=0\.80\.I​\(N\)I\(N\)andM​\(N\)M\(N\)are measured directly from the Pareto\-optimal configuration at eachNN\(Figures[D10](https://arxiv.org/html/2607.01283#A4.F10)and[D11](https://arxiv.org/html/2607.01283#A4.F11)\)\. AtN=1\.18×106N=1\.18\\times 10^\{6\}, multiprobe grid builds its recall@kk=10=0\.80=0\.80index∼\\sim190×\\timesfaster than Voyager \(8\.4 sec vs\. 1,569 sec\), but exhibits per\-query latency approximately 120×\\timesslower\. Thus, multiprobe grid achieves lower total cost when the rebuild\-to\-query ratiofI/fCf\_\{I\}/f\_\{C\}is sufficiently high: approximately one index rebuild per 2,600–20,400 queries depending on the baseline algorithm \(see Appendix[C\.4](https://arxiv.org/html/2607.01283#A3.SS4)\)\. This regime may include applications in recommendation systems and retrieval\-augmented generation\.

Table 1:Scaling exponents at recall@kk=10=0\.80=0\.80\(GloVe\-200, angular;R2R^\{2\}in parentheses\)\.
### 3\.5Implications for high\-dimensional learning systems

Building on the formalization of attention as ANN searchliu\_fast\_2025;haris\_knn\_2025;kang\_attention\_2025, our scaling characterization maps dataset sizeNNto context length, native dimensionalityddto the attention head dimension \(dheadd\_\{\\text\{head\}\}, typically6464to128128, within the range characterized here\), and indexing cost to the incremental updates as new tokens extend the KV\-cache\. In particular, low\-cost indexing methods are favored when the ratio of index updates to queries is high \(e\.g\., during incremental KV\-cache growth\)\. This regime may favor multiprobe grid, as appending a token to the grid requires only a single cell assignment rather than a full rebuild\. Thus, the nominal rebuild costI​\(N\)I\(N\)is a substantially cheaper per\-insert cost; characterizing this per\-insert cost and its interaction with the precomputed BFS fallback is left to future work\. An additional, empirical question for future work is whether theαd\\alpha\_\{d\}crossover persists for Key vector distributions in transformers, which we anticipate exhibit greater non\-uniformity and heavier\-tailed structures than GloVe\. More broadly, our results underscore that ANN method selection should considerNN\- anddd\-scaling relationships, total costJJ, and operational frequencies such as rebuild rate\.

## References

## Appendix ARelated work

Approximate nearest neighbor \(ANN\) search retrieves high\-quality candidate sets approximating true nearest neighbors, trading exactness for speedindyk\_approximate\_1998;jayaram\_subramanya\_diskann\_2019\. Indexing strategies include tree\-based, hash\-based, quantization\-based, and graph\-based methodsxiao\_enhancing\_2024\. Among these, hashing and quantization are often grouped under a broader partitioning\-based framework, as both divide the search space into discrete regions to prune candidatessun\_scaling\_2025\. We adopt this framing in our work\.

Grid\-based methods, a variant of partitioning\-based methods, were explored in early theoretical studies on ANN\. For example, translated grids were used to mitigate exponential dependence on dimensionality and remove logarithmic factors in batched query settingschan\_approximate\_1997\. Subsequent work, such as the bucketing method, achieved constant\-time hash evaluations independent of dataset sizeindyk\_approximate\_1998\. These approaches are notable for their conceptual simplicity and minimal indexing overhead\. As ANN research shifted toward large\-scale, high\-dimensional datasets, practical focus moved toward more flexible methods, including Locality\-Sensitive Hashing \(LSH\)gionis\_similarity\_1999;datar\_locality\-sensitive\_2004;jafari\_experimental\_2021, k\-d treesbentley\_multidimensional\_1975;arya\_optimal\_1998;silpa\-anan\_optimised\_2008, and Production Quantizationjegou\_product\_2011\. As a result, grid\-based methods became relatively underexplored in modern ANN systems, despite offering a distinct set of structural and theoretical properties\.

In addition to partitioning\-based methods, modern ANN systems frequently rely on graph\-based indices, particularly Hierarchical Navigable Small World \(HNSW\), which achieve strong empirical performance by traversing multi\-layer proximity graphsmalkov\_efficient\_2020\. However, graph\-based methods introduce distinct operational challenges\. For example, they can exhibit capacity\-limited failure, where insufficient exploration leads to abrupt degradation in neighbor qualitycooper\_capacity\-limited\_2026\. They are also sensitive to dynamic updates, as repeated insertions and deletions can produce unreachable nodes and degrade recall over timexiao\_enhancing\_2024\. More broadly, these limitations highlight the complex trade\-offs between query efficiency, index construction, and robustness that characterize modern ANN methods\.

Beyond algorithmic design, recent work has emphasized empirical evaluation and scaling behavior as the primary lens for understanding ANN performance\. Standardized benchmarks such asann\-benchmarksevaluate methods across datasets, reporting recall–latency tradeoffs under fixed resource budgetsaumuller\_ann\-benchmarks\_2020;aumuller\_reproducibility\_2021\. Benchmarking studies have helped establish empirical baselines across a wide range of regimes, with HNSW and Facebook AI Similarity Search \(FAISS\) often exhibiting state\-of\-the\-art performance\. To better generalize benchmarks, studies also seek to evaluate how performance scales with dataset sizeNNand search budget\. For example, Sun et al\. established power\-law scaling relationships for partitioning\- and graph\-based methodssun\_scaling\_2025\. The study proposed a framework for the total costJJof ANN search that is a function of query\-time compute, indexing, and storage costs:J​\(N\)=fI⋅I​\(N\)\+fC⋅C​\(N\)\+S​\(N\)J\(N\)=f\_\{I\}\\cdot I\(N\)\+f\_\{C\}\\cdot C\(N\)\+S\(N\), whereII,CC, andSSdenote indexing, compute, and storage costs, andfIf\_\{I\},fCf\_\{C\}their respective frequency of occurrence\. We adapt this cost framework in Section[3\.4](https://arxiv.org/html/2607.01283#S3.SS4)\.

While benchmarking and scaling studies have significantly improved our understanding of ANN performance, they primarily focus on graph\-based, tree\-based, and adaptive partitioning methods\. Grid\-based approaches have remained comparatively underexplored despite their unique properties in the ANN design space, such as structural simplicity, low indexing cost, and predictable query behavior\. We anticipated that grid\-based methods may therefore exhibit different performance trade\-offs from the other, more characterized methods \- particularly in regimes where indexing cost, rebuild frequency, or robustness to dimensionality are dominant concerns\. Thus, we revisit grid\-based ANN methods in this work, aiming to expand understanding of how different ANN design principles translate into distinct scaling behaviors\.

## Appendix BDerivation of the Multiprobe Grid Scaling Model

We derive a probabilistic upper\-bound approximation for the query cost–recall relationship of multiprobe grid search, averaged over many queries\. The derivation assumes uniform query and data distribution at the cell scale and does not account for rank distortion introduced by the PCA projection; extending to PCA\-induced distortion is left for future work\. Throughout, we use the same notation as the main text:NNdata points inℝd\\mathbb\{R\}^\{d\}, projected via PCA toℝm\\mathbb\{R\}^\{m\}and partitioned into a uniformGmG^\{m\}grid with cell side lengthCC\.

### B\.1Probe Setup and Cell Offsets

Given a query𝒒∈ℝd\{\\bm\{q\}\}\\in\\mathbb\{R\}^\{d\}and its PCA projection𝒒′=\(q1′,…,qm′\)\{\\bm\{q\}\}^\{\\prime\}=\(q^\{\\prime\}\_\{1\},\\ldots,q^\{\\prime\}\_\{m\}\), letchc\_\{h\}denote the home cell\. For each dimensionjj, define the binary offset

oj=\{\+1qj′≥midpoint of​ch​in dim\.​j,−1otherwise\.o\_\{j\}\\;=\\;\\begin\{cases\}\+1&q^\{\\prime\}\_\{j\}\\geq\\text\{midpoint of \}c\_\{h\}\\text\{ in dim\. \}j,\\\\ \-1&\\text\{otherwise\.\}\\end\{cases\}Because the position of𝒒′\{\\bm\{q\}\}^\{\\prime\}withinchc\_\{h\}determines the sign per dimension, the set of candidate cell displacements is the Cartesian product of themmbinary choices, giving2m2^\{m\}offset vectors\. Removing the all\-zero vector \(the home cell\) leaves2m−12^\{m\}\-1neighboring cells, rather than the3m−13^\{m\}\-1full\-neighborhood count\. This orthant pruning is employed to prune the number of cells checked asmmincreases\.

##### Two\-dimensional example\.

Form=2m=2withq′q^\{\\prime\}above the midpoint in both dimensions \(o=\(\+1,\+1\)o=\(\+1,\+1\)\), the non\-home offset vectors are\{\(0,1\),\(1,0\),\(1,1\)\}\\\{\(0,1\),\(1,0\),\(1,1\)\\\}in Cartesian choice notation, corresponding to the horizontal, vertical, and diagonal neighbors in the upper\-right orthant\.

### B\.2Wall distance ordering and cost model

For each candidate cell, define the squared wall distance

wi2=∑j:oj≠0\(qj′−wallj\)2,w\_\{i\}^\{2\}\\;=\\;\\sum\_\{j\\,:\\,o\_\{j\}\\neq 0\}\(q^\{\\prime\}\_\{j\}\-\\mathrm\{wall\}\_\{j\}\)^\{2\},\(5\)wherewallj\\mathrm\{wall\}\_\{j\}is the boundary ofchc\_\{h\}shared with the candidate cell in dimensionjj\. The2m−12^\{m\}\-1values are sorted ascending as\(w02,…,w2m−22\)\(w\_\{0\}^\{2\},\\ldots,w\_\{2^\{m\}\-2\}^\{2\}\), and at query time only the firstnprobe≤2m−1n\_\{\\mathrm\{probe\}\}\\leq 2^\{m\}\-1cells in this order are probed\. Candidates from all probed cells are re\-ranked in the nativedd\-space\.

Each probed cell contributes on averageN/GmN/G^\{m\}points to the candidate set, and ranking is linear in the candidate count\. Thus

cost=1/QPS=K⋅nprobe⋅NGm,\\mathrm\{cost\}\\;=\\;1/\\mathrm\{QPS\}\\;=\\;K\\cdot n\_\{\\mathrm\{probe\}\}\\cdot\\frac\{N\}\{G^\{m\}\},\(6\)whereK\>0K\>0absorbs per\-candidate constants \(distance computations, comparisons, bookkeeping\)\.

### B\.3Recall as a sum of cell\-membership probabilities

Letx∗x^\{\*\}denote the true nearest neighbor ofqqand define the cell\-membership probabilityPi=Pr⁡\[x∗∈ci\]P\_\{i\}=\\Pr\[x^\{\*\}\\in c\_\{i\}\]\. Because probed cells are disjoint,

R​\(nprobe\)=∑i=0nprobe−1Pi\.R\(n\_\{\\mathrm\{probe\}\}\)\\;=\\;\\sum\_\{i=0\}^\{n\_\{\\mathrm\{probe\}\}\-1\}P\_\{i\}\.Under uniform query/data distribution at the cell scale,PiP\_\{i\}decreases monotonically withwi2w\_\{i\}^\{2\}; since thewi2w\_\{i\}^\{2\}are sorted ascending,P0≥P1≥⋯≥PnprobeP\_\{0\}\\geq P\_\{1\}\\geq\\cdots\\geq P\_\{n\_\{\\mathrm\{probe\}\}\}\. We adopt the exponential fall\-off

Pi≈Ph​e−μ​wi2,Ph:=P0,μ\>0,P\_\{i\}\\;\\approx\\;P\_\{h\}\\,e^\{\-\\mu w\_\{i\}^\{2\}\},\\qquad P\_\{h\}:=P\_\{0\},\\ \\mu\>0,\(7\)as a mean\-field approximation\.

### B\.4Expected wall distance via offset geometry

To obtain an analytical form, we replace the cell\-specificwi2w\_\{i\}^\{2\}with its expected value under uniform queries\. From equation[5](https://arxiv.org/html/2607.01283#A2.E5),wi2=∑j:oj≠0εj2w\_\{i\}^\{2\}=\\sum\_\{j:o\_\{j\}\\neq 0\}\\varepsilon\_\{j\}^\{2\}whereεj:=qj′−wallj\\varepsilon\_\{j\}:=q^\{\\prime\}\_\{j\}\-\\mathrm\{wall\}\_\{j\}\. Under the uniform\-distribution assumption,εj∼U​\(0,C/2\)\\varepsilon\_\{j\}\\sim U\(0,C/2\)\(the query sits in a given half ofchc\_\{h\}per dimension\), giving

𝔼\[εj2\]=∫0C/2x2⋅2Cdx=\(C/2\)23=:L\.\\mathbb\{E\}\[\\varepsilon\_\{j\}^\{2\}\]\\;=\\;\\int\_\{0\}^\{C/2\}x^\{2\}\\cdot\\frac\{2\}\{C\}\\,dx\\;=\\;\\frac\{\(C/2\)^\{2\}\}\{3\}\\;=:\\;L\.LetAiA\_\{i\}denote the set of nonzero offset coordinates of theii\-th cell\. By linearity,

𝔼​\[wi2\]=\|Ai\|⋅L\.\\mathbb\{E\}\[w\_\{i\}^\{2\}\]\\;=\\;\|A\_\{i\}\|\\cdot L\.\(8\)For eachj∈\{1,…,m\}j\\in\\\{1,\\ldots,m\\\}, there are\(mj\)\\binom\{m\}\{j\}offset vectors with exactlyjjnonzero entries, all sharing𝔼​\[wi2\]=j​L\\mathbb\{E\}\[w\_\{i\}^\{2\}\]=jL\. Sorting the2m−12^\{m\}\-1cells in ascending order of expected wall distance produces a step function that takes valuej​LjLon a plateau of length\(mj\)\\binom\{m\}\{j\}, forj=1,…,mj=1,\\ldots,m\.

##### Example:m=3m=3\.

There are\(31\)=3\\binom\{3\}\{1\}=3face\-adjacent cells, reachable by the offset vectors \(0,0,1\), \(0,1,0\) and \(1,0,0\) with𝔼​\[w2\]=L\\mathbb\{E\}\[w^\{2\}\]=L,\(32\)=3\\binom\{3\}\{2\}=3edge\-adjacent cells with offset vectors \(0,1,1\), \(1,0,1\) and, \(1,1,0\) with𝔼​\[w2\]=2​L\\mathbb\{E\}\[w^\{2\}\]=2L, and\(33\)=1\\binom\{3\}\{3\}=1corner cell with offset vector \(1,1,1\) with𝔼​\[w2\]=3​L\\mathbb\{E\}\[w^\{2\}\]=3L, totaling23−1=72^\{3\}\-1=7\.

##### Arithmetic mean gap \(telescoping\)\.

Define𝔼​\[w−12\]:=0\\mathbb\{E\}\[w\_\{\-1\}^\{2\}\]:=0for the home cell\. The arithmetic mean of first differences is

θ=12m−1​∑i=02m−2\(𝔼​\[wi2\]−𝔼​\[wi−12\]\)\.\\theta\\;=\\;\\frac\{1\}\{2^\{m\}\-1\}\\sum\_\{i=0\}^\{2^\{m\}\-2\}\\bigl\(\\mathbb\{E\}\[w\_\{i\}^\{2\}\]\-\\mathbb\{E\}\[w\_\{i\-1\}^\{2\}\]\\bigr\)\.The sum telescopes: within each plateau the increment is0, and at each of themmtransitions between consecutive plateaus the increment isLL\. Therefore

θ=m⋅L2m−1=m​\(C/2\)23​\(2m−1\)\.\\theta\\;=\\;\\frac\{m\\cdot L\}\{2^\{m\}\-1\}\\;=\\;\\frac\{m\\,\(C/2\)^\{2\}\}\{3\\,\(2^\{m\}\-1\)\}\.\(9\)Form=3m=3,θ=3​L/7=\(C/2\)2/7\\theta=3L/7=\(C/2\)^\{2\}/7\. We approximate the step function linearly as

𝔼​\[wi2\]≈θ​i\.\\mathbb\{E\}\[w\_\{i\}^\{2\}\]\\;\\approx\\;\\theta\\,i\.\(10\)

### B\.5Geometric closed form

Substituting𝔼​\[wi2\]≈θ​i\\mathbb\{E\}\[w\_\{i\}^\{2\}\]\\approx\\theta iinto equation[7](https://arxiv.org/html/2607.01283#A2.E7)withΔ:=e−μ​θ∈\(0,1\)\\Delta:=e^\{\-\\mu\\theta\}\\in\(0,1\), we obtainPi≈Ph​ΔiP\_\{i\}\\approx P\_\{h\}\\Delta^\{i\}, and the recall becomes a geometric series:

R​\(nprobe\)=Ph​∑i=0nprobe−1Δi=Ph⋅1−Δnprobe1−Δ\.R\(n\_\{\\mathrm\{probe\}\}\)\\;=\\;P\_\{h\}\\sum\_\{i=0\}^\{n\_\{\\mathrm\{probe\}\}\-1\}\\Delta^\{i\}\\;=\\;P\_\{h\}\\cdot\\frac\{1\-\\Delta^\{n\_\{\\mathrm\{probe\}\}\}\}\{1\-\\Delta\}\.\(11\)The achievable recall range is bounded by

Rmin=Ph\(nprobe=1\),Rmax=Ph⋅1−Δ2m1−Δ\(nprobe=2m\)\.R\_\{\\min\}\\;=\\;P\_\{h\}\\quad\(n\_\{\\mathrm\{probe\}\}=1\),\\qquad R\_\{\\max\}\\;=\\;P\_\{h\}\\cdot\\frac\{1\-\\Delta^\{2^\{m\}\}\}\{1\-\\Delta\}\\quad\(n\_\{\\mathrm\{probe\}\}=2^\{m\}\)\.ForΔ∈\(0,1\)\\Delta\\in\(0,1\)and moderately largemm,Δ2m→0\\Delta^\{2^\{m\}\}\\to 0very rapidly, so

Rmax≈Ph1−Δ⟺1Rmax≈1−ΔPh\.R\_\{\\max\}\\;\\approx\\;\\frac\{P\_\{h\}\}\{1\-\\Delta\}\\qquad\\Longleftrightarrow\\qquad\\frac\{1\}\{R\_\{\\max\}\}\\;\\approx\\;\\frac\{1\-\\Delta\}\{P\_\{h\}\}\.\(12\)

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

Starting from the geometric closed form equation[11](https://arxiv.org/html/2607.01283#A2.E11)and solving fornproben\_\{\\mathrm\{probe\}\},

Δnprobe=1−R​\(1−Δ\)Ph,nprobe​\(R\)=ln⁡\(1−R/Rmax\)ln⁡Δ\.\\Delta^\{n\_\{\\mathrm\{probe\}\}\}\\;=\\;1\-\\frac\{R\(1\-\\Delta\)\}\{P\_\{h\}\},\\qquad n\_\{\\mathrm\{probe\}\}\(R\)\\;=\\;\\frac\{\\ln\(1\-R/R\_\{\\max\}\)\}\{\\ln\\Delta\}\.Using the approximation\(1−Δ\)/Ph≈1/Rmax\(1\-\\Delta\)/P\_\{h\}\\approx 1/R\_\{\\max\}from equation[12](https://arxiv.org/html/2607.01283#A2.E12),

nprobe​\(R\)=ln⁡\(1−R/Rmax\)ln⁡Δ−1\.n\_\{\\mathrm\{probe\}\}\(R\)\\;=\\;\\frac\{\\ln\(1\-R/R\_\{\\max\}\)\}\{\\ln\\Delta\}\-1\.\(13\)Substituting equation[13](https://arxiv.org/html/2607.01283#A2.E13)into the cost formula equation[6](https://arxiv.org/html/2607.01283#A2.E6)and factoring outln⁡Δ\\ln\\Deltafrom the numerator,

1QPS=K​NGm⋅ln⁡\(1−R/Rmax\)−ln⁡Δln⁡Δ\.\\frac\{1\}\{\\mathrm\{QPS\}\}\\;=\\;\\frac\{KN\}\{G^\{m\}\}\\cdot\\frac\{\\ln\(1\-R/R\_\{\\max\}\)\-\\ln\\Delta\}\{\\ln\\Delta\}\.\(14\)Bothln⁡\(1−R/Rmax\)\\ln\(1\-R/R\_\{\\max\}\)andln⁡Δ\\ln\\Deltaare negative \(sinceR/Rmax,Δ∈\(0,1\)R/R\_\{\\max\},\\Delta\\in\(0,1\)\), so we may rewrite equation[14](https://arxiv.org/html/2607.01283#A2.E14)with all signs made explicit:

QPS​\(R\)=\|ln⁡Δ\|K​N/Gm⋅1−ln⁡\(1−R/Rmax\)\+ln⁡Δ\.\\mathrm\{QPS\}\(R\)\\;=\\;\\frac\{\|\\ln\\Delta\|\}\{KN/G^\{m\}\}\\cdot\\frac\{1\}\{\-\\ln\(1\-R/R\_\{\\max\}\)\+\\ln\\Delta\}\.\(15\)
##### Taking the log\.

To expose the exponential structure, we take the logarithm of both sides of equation[15](https://arxiv.org/html/2607.01283#A2.E15):

log⁡QPS​\(R\)=log⁡\(\|ln⁡Δ\|​GmK​N\)−log⁡\(−ln⁡\(1−R/Rmax\)\+ln⁡Δ\)\.\\log\\mathrm\{QPS\}\(R\)\\;=\\;\\log\\\!\\Big\(\\tfrac\{\|\\ln\\Delta\|G^\{m\}\}\{KN\}\\Big\)\\;\-\\;\\log\\\!\\Big\(\-\\ln\(1\-R/R\_\{\\max\}\)\+\\ln\\Delta\\Big\)\.\(16\)The first term is constant inRR; all theRR\-dependence lives in the second term\.

##### Taylor expansion of the inner log\.

Letu:=R/Rmax∈\(0,1\)u:=R/R\_\{\\max\}\\in\(0,1\)\. The function−ln⁡\(1−u\)=ln⁡\(1/\(1−u\)\)\-\\ln\(1\-u\)=\\ln\\\!\\bigl\(1/\(1\-u\)\\bigr\)admits the convergent Taylor series

−ln⁡\(1−u\)=u\+u22\+u33\+⋯\-\\ln\(1\-u\)\\;=\\;u\+\\tfrac\{u^\{2\}\}\{2\}\+\\tfrac\{u^\{3\}\}\{3\}\+\\cdotson\(0,1\)\(0,1\)\. Becauseu<1u<1, the higher\-order terms are dominated by the linear term, and we truncate at first order:

−ln⁡\(1−R/Rmax\)≈RRmax\.\-\\ln\(1\-R/R\_\{\\max\}\)\\;\\approx\\;\\frac\{R\}\{R\_\{\\max\}\}\.\(17\)
The first\-order truncation in equation[17](https://arxiv.org/html/2607.01283#A2.E17)has relative error1−u/\[−ln⁡\(1−u\)\]1\-u/\[\-\\ln\(1\-u\)\], which is approximately28%28\\%atu=0\.5u=0\.5,50%50\\%atu≈0\.8u\\approx 0\.8, and diverges asu→1u\\to 1\. The closed form derived below is therefore a local approximation, accurate foruubounded away from11\. As we discuss in Appendix[B\.7](https://arxiv.org/html/2607.01283#A2.SS7), this is one of two approximations whose validity degrades in the high\-recall regime; the empirical Pareto front in Figure[1](https://arxiv.org/html/2607.01283#S3.F1)nonetheless follows the predicted log\-linear shape over most of the operating range, suggesting that the structural prediction survives quantitative slack in the underlying assumptions\. Substituting equation[17](https://arxiv.org/html/2607.01283#A2.E17)into equation[16](https://arxiv.org/html/2607.01283#A2.E16),

log⁡QPS​\(R\)≈log⁡\(const\)−log⁡\(R/Rmax\+ln⁡Δ\)\.\\log\\mathrm\{QPS\}\(R\)\\;\\approx\\;\\log\(\\mathrm\{const\}\)\\;\-\\;\\log\\\!\\Big\(R/R\_\{\\max\}\+\\ln\\Delta\\Big\)\.\(18\)

##### Mean\-field approximation\.

We now make the mean\-field argument rigorous\. The derivation rests on the following assumption:

> Assumption \(mean\-field\)\.The query points are uniformly distributed within the home cell, and the dataset points are drawn from a distribution that is approximately uniform at the scale of a single grid cell\.

Three consequences follow\. First, the wall distanceswi2w\_\{i\}^\{2\}are expectations taken over the uniform query position distribution within the cell, soθ\\thetais the mean inter\-neighbor gap averaged over all possible query locations \(Appendix[B\.4](https://arxiv.org/html/2607.01283#A2.SS4)\)\. Second, the decay parameterμ\\mucharacterizes the rate at which the NN\-membership probability falls off with wall distance, and is itself determined by the local point density at the cell scale\. Lastly, since the point distribution is approximately uniform at the cell scale, the cell\-membership probability massPi=Ph​e−μ​wi2P\_\{i\}=P\_\{h\}e^\{\-\\mu w\_\{i\}^\{2\}\}does not vary sharply between adjacent cells\. That is, neighboring cells have similar density to the home cell, so the decay is gradual\. This implies

μ​θ≪1⟺Δ=e−μ​θ≈1⟺\|ln⁡Δ\|≪1\.\\mu\\theta\\;\\ll\\;1\\qquad\\Longleftrightarrow\\qquad\\Delta=e^\{\-\\mu\\theta\}\\approx 1\\qquad\\Longleftrightarrow\\qquad\|\\ln\\Delta\|\\;\\ll\\;1\.\(19\)
This assumption is equivalent to requiring that the grid cell size be small relative to the scale at which the data distribution varies, which is the standard regime underlying any local approximation in partition\-based ANN\. It is also the regime in which the grid index is well\-calibrated: if cells were so large that density varied significantly within them, the grid partition itself would be a poor indexing structure regardless of multiprobe\.

##### Practical domain of the mean\-field assumption\.

Real embedding distributions such as GloVe and SIFT exhibit substantial non\-uniformity, with cluster structure, manifold geometry, and density variations corresponding to semantic structure\. The assumption is therefore not literally satisfied by any of the datasets we evaluate\. What the assumption requires*in practice*is that the optimizer selects\(m,G\)\(m,G\)such that adjacent cells have similar local density on average, a weaker condition than global uniformity, and one that is implicitly enforced, since configurations straddling severe density gradients incur recall penalties and are filtered from the Pareto front\. The assumption nevertheless degrades asnproben\_\{\\mathrm\{probe\}\}grows, because probing further from the home cell increases the likelihood of crossing a density gradient\. High recall therefore corresponds to the regime where mean\-field is most strained, by the same mechanism that makes the Taylor truncation in equation[17](https://arxiv.org/html/2607.01283#A2.E17)least accurate\. The two limitations are not independent, both reflecting the algorithm operating outside the local neighborhood of the home cell \(where the mean\-field description applies\)\. The predicted log\-linear form nevertheless holds empirically over most of the operating range in Figure[1](https://arxiv.org/html/2607.01283#S3.F1), which we discuss further in Appendix[B\.7](https://arxiv.org/html/2607.01283#A2.SS7)\.

##### Droppingln⁡Δ\\ln\\Delta\.

Under equation[19](https://arxiv.org/html/2607.01283#A2.E19), we dropln⁡Δ\\ln\\Deltafrom the argument of the outer log in equation[18](https://arxiv.org/html/2607.01283#A2.E18)\. To confirm this is a well\-controlled approximation: becauseln⁡Δ<0\\ln\\Delta<0,

RRmax\+ln⁡Δ<RRmax,\\frac\{R\}\{R\_\{\\max\}\}\+\\ln\\Delta\\;<\\;\\frac\{R\}\{R\_\{\\max\}\},and monotonicity oflog\\loggives

log⁡\(R/Rmax\+ln⁡Δ\)<log⁡\(R/Rmax\),\\log\\\!\\Big\(R/R\_\{\\max\}\+\\ln\\Delta\\Big\)\\;<\\;\\log\(R/R\_\{\\max\}\),solog⁡\(R/Rmax\)\\log\(R/R\_\{\\max\}\)is a valid upper bound, with the gap shrinking to zero asμ​θ→0\\mu\\theta\\to 0\. Applying this approximation to equation[18](https://arxiv.org/html/2607.01283#A2.E18),

log⁡QPS​\(R\)≈log⁡\(const\)−log⁡\(R/Rmax\)\.\\log\\mathrm\{QPS\}\(R\)\\;\\approx\\;\\log\(\\mathrm\{const\}\)\\;\-\\;\\log\(R/R\_\{\\max\}\)\.\(20\)

##### Expanding the log\-ratio\.

Expandinglog⁡\(R/Rmax\)=log⁡R−log⁡Rmax\\log\(R/R\_\{\\max\}\)=\\log R\-\\log R\_\{\\max\}and substituting into equation[20](https://arxiv.org/html/2607.01283#A2.E20),

log⁡QPS​\(R\)≈log⁡\(const\)−log⁡R\+log⁡Rmax=log⁡\(const⋅Rmax\)−log⁡R\.\\log\\mathrm\{QPS\}\(R\)\\;\\approx\\;\\log\(\\mathrm\{const\}\)\-\\log R\+\\log R\_\{\\max\}\\;=\\;\\log\(\\mathrm\{const\}\\cdot R\_\{\\max\}\)\-\\log R\.\(21\)Absorbinglog⁡Rmax\\log R\_\{\\max\}into the constant, we defineconst′:=const⋅Rmax\\mathrm\{const\}^\{\\prime\}:=\\mathrm\{const\}\\cdot R\_\{\\max\}and obtain

log⁡QPS​\(R\)≈log⁡\(const′\)−log⁡R\.\\log\\mathrm\{QPS\}\(R\)\\;\\approx\\;\\log\(\\mathrm\{const\}^\{\\prime\}\)\-\\log R\.\(22\)Equation equation[22](https://arxiv.org/html/2607.01283#A2.E22)is a power\-law relationship,QPS∝1/R\\mathrm\{QPS\}\\propto 1/R\.

##### Local linearization oflog⁡R\\log R\.

To recover the exponential form observed empirically, we exploit the fact thatRRis confined to a bounded interval\[Rmin,Rmax\]\[R\_\{\\min\},R\_\{\\max\}\]and linearize:

log⁡R≈a\+b​R,R∈\[Rmin,Rmax\],\\log R\\;\\approx\\;a\+b\\,R,\\qquad R\\in\[R\_\{\\min\},R\_\{\\max\}\],\(23\)withb\>0b\>0becauselog\\logis increasing\. Geometrically, this replaces the concavelog⁡R\\log Rcurve with a tangent line over the achievable recall range, as shown in Figure[A1](https://arxiv.org/html/2607.01283#A2.F1)\. Substituting equation[23](https://arxiv.org/html/2607.01283#A2.E23)into equation[22](https://arxiv.org/html/2607.01283#A2.E22),

log⁡QPS​\(R\)≈log⁡\(const′\)−a−b​R\.\\log\\mathrm\{QPS\}\(R\)\\;\\approx\\;\\log\(\\mathrm\{const\}^\{\\prime\}\)\-a\-b\\,R\.\(24\)

##### Exponentiating\.

Sincelog=log10\\log=\\log\_\{10\}throughout, exponentiating equation[24](https://arxiv.org/html/2607.01283#A2.E24)in base 10 yields

QPS​\(R\)≈10log⁡\(const′\)−a−b​R=const′⋅10−a⋅10−b​R\.\\mathrm\{QPS\}\(R\)\\;\\approx\\;10^\{\\log\(\\mathrm\{const\}^\{\\prime\}\)\-a\-bR\}\\;=\\;\\mathrm\{const\}^\{\\prime\}\\cdot 10^\{\-a\}\\cdot 10^\{\-bR\}\.\(25\)Absorbing the twoRR\-independent factors into a single constantA′:=const′⋅10−aA^\{\\prime\}:=\\mathrm\{const\}^\{\\prime\}\\cdot 10^\{\-a\}and settingB:=bB:=b, we obtain the log\-linear throughput–recall relation:

QPS\(R\)≈A′⋅10−B​R,A′\>0,B\>0\.\\boxed\{\\;\\mathrm\{QPS\}\(R\)\\;\\approx\\;A^\{\\prime\}\\cdot 10^\{\-BR\},\\qquad A^\{\\prime\}\>0,\\ B\>0\.\\;\}\(26\)Equivalently,QPS​\(R\)≈A′​e−B′​R\\mathrm\{QPS\}\(R\)\\approx A^\{\\prime\}e^\{\-B^\{\\prime\}R\}withB′=B​ln⁡10B^\{\\prime\}=B\\ln 10, confirming the log\-linear relationship observed empirically in Section[3\.1](https://arxiv.org/html/2607.01283#S3.SS1)\. We note that the slopeBBis set by the local derivative oflog⁡R\\log Ron\[Rmin,Rmax\]\[R\_\{\\min\},R\_\{\\max\}\], which scales inversely withRmaxR\_\{\\max\}\.

RRlog⁡R\\log Rlog⁡R\\log Ra\+b​Ra\+b\\,RRminR\_\{\\min\}RmaxR\_\{\\max\}achievable recall rangeFigure A1:Local linearization oflog⁡R\\log Ron the achievable recall interval\[Rmin,Rmax\]\[R\_\{\\min\},R\_\{\\max\}\]\. The concavelog⁡R\\log Rcurve \(blue, solid\) is approximated by a tangent linea\+b​Ra\+b\\,R\(red, dashed\) over the narrow operating range of the algorithm\. Substituting this linear approximation intolog⁡QPS≈log⁡\(const⋅Rmax\)−log⁡R\\log\\mathrm\{QPS\}\\approx\\log\(\\mathrm\{const\}\\cdot R\_\{\\max\}\)\-\\log Rconverts the power\-law dependence into an exponential one, yieldingQPS​\(R\)≈A′​e−B′​R\\mathrm\{QPS\}\(R\)\\approx A^\{\\prime\}e^\{\-B^\{\\prime\}R\}\.

### B\.7Validity, robustness, and empirical correspondence

The closed form equation[26](https://arxiv.org/html/2607.01283#A2.E26)relies on multiple approximations: a Taylor truncation equation[17](https://arxiv.org/html/2607.01283#A2.E17), a mean\-field assumption equation[19](https://arxiv.org/html/2607.01283#A2.E19)that real embedding distributions do not fully satisfy, and a local linearization oflog⁡R\\log R\(equation[23](https://arxiv.org/html/2607.01283#A2.E23)\)\. Taylor truncation and mean\-field degrade in the high\-recall regime, which is also the regime where the empiricaldd\-scaling crossover reported in the main text emerges\. Here, we argue that the qualitative log\-linear form is structural and robust to its underlying assumptions, with Figure[1](https://arxiv.org/html/2607.01283#S3.F1)corroborating our reasoning\. In addition, the empiricaldd\-scaling characterization in the main text is methodologically independent of the closed\-form model\.

##### Robustness of the log\-linear form\.

It is not obvious*a priori*that equation[26](https://arxiv.org/html/2607.01283#A2.E26)should describe the empirical Pareto front at all, given that the mean\-field assumption is not fully satisfied by the non\-uniform embedding distributions on which we evaluate the algorithm\. We argue that the qualitative log\-linear shape is structural rather than approximation\-dependent\. Two mechanical features of the algorithm produce the log\-linear shape: \(i\) recall is a saturating, monotonically increasing function ofnproben\_\{\\mathrm\{probe\}\}, because cells are probed in order of decreasing membership probabilityPiP\_\{i\}; and \(ii\) cost is linear innproben\_\{\\mathrm\{probe\}\}, because each probed cell contributes a fixed expected candidate countN/GmN/G^\{m\}\. Combining a saturating\-concave recall function with a linear cost function yields cost growing faster than linearly in recall as recall approaches its ceiling, which on log\-y vs\. linear\-recall axes traces out a near\-straight line over the operating range with downward curvature near the ceiling\. Importantly, neither \(i\) nor \(ii\) requires the mean\-field assumption\. \(i\) requires only that cells can be ordered by membership probability, which the algorithm enforces by construction, and \(ii\) follows from each probed cell contributing a fixed expected candidate count\. Thus, the approximations affect the predicted slopeBBand ceilingRmaxR\_\{\\max\}, but not the functional form itself, which we observe on real, non\-uniform embedding data\.

##### Relevance to thedd\-scaling crossover\.

The closed form and thedd\-scaling characterization reported in Figure[2](https://arxiv.org/html/2607.01283#S3.F2)b answer fundamentally different questions\. While equation[26](https://arxiv.org/html/2607.01283#A2.E26)models the shape of the QPS–recall Pareto front for a fixed dataset,αd\\alpha\_\{d\}characterizes how QPS \(at fixed recall\) scales across datasets of different dimensionality\. The closed form contains nodd\-dependence in its functional form\. Rather,ddmanifests empirically by influencing the Pareto\-optimal\(m,G,nprobe\)\(m,G,n\_\{\\mathrm\{probe\}\}\)configuration\. Thus, the absence of explicitdd\-dependence in equation[26](https://arxiv.org/html/2607.01283#A2.E26)underscores that thedd\-scaling crossover is an authentic, empirical finding that reflects the algorithm’s ability to adapt to dataset dimensionality\.

## Appendix CImplementation and Experimental Details

### C\.1Multiprobe grid search

#### C\.1\.1Index construction

We employ PCA to project each point in𝔻\{\\mathbb\{D\}\}fromℝd\\mathbb\{R\}^\{d\}toℝm\\mathbb\{R\}^\{m\}, where the grid dimensionalitym≪dm\\ll dis a hyperparameter\. The projected space is partitioned into a uniform grid ofGmG^\{m\}cells, whereGGis the number of splits per dimension\. Each cell stores the indices of points whose projections fall within its boundaries\. To handle empty cells encountered during querying, we precompute a multi\-source breadth\-first search \(BFS\) over the grid graph in which every occupied cell is seeded simultaneously as a source\. The BFS expands outward through cell neighbors, recording for each cell the identity of its nearest occupied cell\. This process is easy to parallelize and each non\-empty cell only needs to be updated once\. The result is a static lookup table mapping every grid cell to the nearest occupied cell by Manhattan distance\. Insertion and deletion of new points are also efficient under this regime\. Figure[D12](https://arxiv.org/html/2607.01283#A4.F12)shows examples of how often the BFS fallback is triggered as a function of dataset characteristics \(i\.e\.,NNanddd\) and hyperparameters \(GGandnproben\_\{\\text\{probe\}\}\)\.

#### C\.1\.2Query processing

Given a query vector𝒒∈ℝd\{\\bm\{q\}\}\\in\\mathbb\{R\}^\{d\}and a probe countnprobe≥1n\_\{\\text\{probe\}\}\\geq 1, we project𝒒\{\\bm\{q\}\}to themm\-dimensional PCA space and identify the cell containing the projected vector𝒒′\{\\bm\{q\}\}^\{\\prime\}\. Whennprobe=1n\_\{\\text\{probe\}\}=1, only the primary cell is searched\. Whennprobe\>1n\_\{\\text\{probe\}\}\>1, we additionally probe thenprobe−1n\_\{\\text\{probe\}\}\-1nearest neighboring cells ranked by wall distance \(the squared Euclidean distance from𝒒′\{\\bm\{q\}\}^\{\\prime\}to the shared boundary of each neighboring cell\)\. To bound the search space, we consider only the2m2^\{m\}cells in the geometric orthant \(themm\-dimensional generalization of a quadrant\) toward which𝒒′\{\\bm\{q\}\}^\{\\prime\}is displaced from the primary cell’s midpoint\. Candidates from all probed cells are gathered and ranked using the fulldd\-dimensional metric \(cosine similarity for angular datasets, Euclidean distance forL2L\_\{2\}datasets\) to return the top\-kkresults\. If all probed cells are empty, the precomputed BFS fallback is triggered to return the nearest occupied cell\.

### C\.2Experimental setup

All experiments use theann\-benchmarksframeworkaumuller\_ann\-benchmarks\_2020;aumuller\_reproducibility\_2021, which provides standardized evaluation with Docker containers enforcing single\-CPU execution per algorithm\. We report recall@k=10k=10as the accuracy metric and queries per second \(QPS\) as the throughput metric\.

#### C\.2\.1Baselines

We compare the multiprobe grid search with the following algorithms: Voyager \(a HNSW variant, graph\-based\)noauthor\_spotifyvoyager\_2026, PyNNDescent \(graph\-based\)mcinnes\_lmcinnespynndescent\_2026, Annoy \(tree\-based\)noauthor\_spotifyannoy\_2026, and FAISS\-IVF \(quantization\-based partitioning\)noauthor\_facebookresearchfaiss\_2026\. We selected these state\-of\-the\-art algorithms to represent the major ANN algorithm families\. Brute\-force search serves as a reference for several performance metrics \(e\.g\., queries per second\) and to identify ground truth nearest neighbors\.

#### C\.2\.2Hyperparameter tuning for multiprobe grid

The multiprobe grid algorithm has three hyperparameters: grid dimensionalitymm, grid splitsGG, and probe countnproben\_\{\\text\{probe\}\}\. The pair\(m,G\)\(m,G\)determines the index structure, whilenproben\_\{\\text\{probe\}\}impacts the recall\-latency tradeoff at query time\. We run NSGA\-II multi\-objective optimization \(200 trials\) using the Optuna package to identify Pareto\-optimal\(m,G\)\(m,G\)pairs for the GloVe\-200\-angular dataset; the same configurations are applied to subsampled GloVe\-200 and to GloVe\-25, \-50, and \-100\-angular\. A separate optimization was performed on SIFT\-128\-euclidean because of the distinct data modality\. From each Optuna study, representative\(m,G\)\(m,G\)pairs spanning recall\>\>0\.10 to 0\.98 are selected for all subsequent experiments\. For each pair,nproben\_\{\\text\{probe\}\}is swept across a range of values up to2m2^\{m\}to trace the recall\-QPS frontier\. Baseline algorithms use their respectiveann\-benchmarksdefault parameter sweeps\.

#### C\.2\.3Scaling analysis

We characterize scaling behavior by fittinglog⁡\(QPS\)=αx​log⁡\(x\)\+b\\log\(\\text\{QPS\}\)=\\alpha\_\{x\}\\log\(x\)\+b, wherexxcorresponds to either dataset size \(NN\) or dataset dimensionality \(dd\)\. The exponentαx\\alpha\_\{x\}captures how query throughput changes withxx\. For each algorithm, dataset, and recall target, we construct the Pareto front over all benchmarked configurations and interpolate QPS to the target recall by linear interpolation inlog10⁡\(QPS\)\\log\_\{10\}\(\\mathrm\{QPS\}\)between the two Pareto\-optimal configurations whose measured recalls bracket the target\. If the target recall falls outside the Pareto front’s recall range for a given dataset, that point is omitted from the fit\.

- •ForNN\-scaling studies, GloVe\-200\-angular is sampled atN∈\{104,2\.0×104,4\.0×104,7\.5×104,1\.5×105,3\.0×105,6\.0×105,1\.18×106\}N\\in\\\{10^\{4\},2\.0\\times 10^\{4\},4\.0\\times 10^\{4\},7\.5\\times 10^\{4\},1\.5\\times 10^\{5\},3\.0\\times 10^\{5\},6\.0\\times 10^\{5\},1\.18\\times 10^\{6\}\\\}points\. SIFT\-128\-euclidean is sampled atN∈\{104,5×104,105,5×105,106\}N\\in\\\{10^\{4\},5\\times 10^\{4\},10^\{5\},5\\times 10^\{5\},10^\{6\}\\\}points\. Ground truth \(k=10k=10nearest neighbors\) is recomputed for each subsample via brute\-force\.
- •dd\-scaling uses the GloVe word embedding familypennington\_glove\_2014\(GloVe\-25, 50, 100, 200\), which provides four datasets of identical size \(N=1\.18×106N=1\.18\\times 10^\{6\}\) and source distribution with varying native dimensionalityd∈\{25,50,100,200\}d\\in\\\{25,50,100,200\\\}\.

### C\.3Profiling analysis of multiprobe grid

Our multiprobe grid implementation is in Python, while baseline algorithms \(Voyager, PyNNDescent, Annoy, FAISS\-IVF\) use highly optimized C\+\+\. Here, we investigate whether Python interpreter overhead, memory allocation, and orchestration loops have significant impact on our reported scaling exponents\.

##### First\-principles reasoning\.

The per\-query cost primarily decomposes into two components: an algorithmic component involving calls into NumPy/BLAS C kernels \(e\.g\., PCA projection, candidate gathering via concatenation and fancy indexing, re\-ranking\), and an overhead component involving interpreter\-bound orchestration \(e\.g\., primary cell lookup, neighbor cell enumeration, candidate\-list assembly\)\. The interpreter\-bound operations operate on a fixed number of cells \(at most2m2^\{m\}\) and are therefore independent ofNN, contributing a constant, additive term to the per\-query cost\. In the regime where the algorithmic term dominates, which we expect for any modern dataset of appreciableNN, this additive overhead becomes negligible and does not affect the slope of a log–log fit\. The reported scaling exponents therefore reflect algorithmic complexity, not implementation language\.

##### Empirical profiling\.

We profiled the multiprobe query path withcProfileon GloVe\-200\-angular across threeNNscales spanning two orders of magnitude, at a representative configuration \(m=6m\{=\}6,G=5G\{=\}5,nprobe=16n\_\{\\text\{probe\}\}\{=\}16, 1,000 queries perNN\)\. The query was decomposed into named phase functions socProfile’s per\-function attribution gives per\-phase timings \(Table[C1](https://arxiv.org/html/2607.01283#A3.T1)\)\. Phases dominated by NumPy/BLAS calls \(PCA projection, candidate gathering vianp\.concatenateand fancy indexing, and re\-ranking via norm/matmul/argpartition\) scale near\-linearly with candidate count\. In contrast, phases that are pure Python orchestration \(cell index lookup, neighbor enumeration, list assembly\) remain atO​\(1​μ​s\)O\(1\\mu s\)cost across the entire range ofNN\. Altogether, we observe a factor of∼2\.6\\sim 2\.6increase fromN=104N\{=\}10^\{4\}toN=1\.18×106N\{=\}1\.18\\times 10^\{6\}in the Python overhead and a factor of∼865×\\sim 865\\timesgrowth of the NumPy/BLAS\-backed phases\. AtN=1\.18×106N\{=\}1\.18\\times 10^\{6\}, Python orchestration accounts for under 0\.01% of total query time\. The reported scaling exponents in the main text should therefore hold whether multiprobe grid is implemented in Python or C\+\+\.

Table C1:Per\-query phase times \(µs\) for multiprobe grid on GloVe\-200\-angular \(m=6m\{=\}6,G=5G\{=\}5,nprobe=16n\_\{\\text\{probe\}\}\{=\}16\), profiled withcProfileover 1,000 queries perNN\.

### C\.4Derivation of the rebuild\-to\-query crossover

Section[3\.4](https://arxiv.org/html/2607.01283#S3.SS4)reports a rebuild\-to\-query crossover threshold for GloVe\-200 of approximately one rebuild per 2,600–20,400 queries depending on the baseline\. Here, we derive that range from the cost\-framework from Sun et alsun\_scaling\_2025\.

##### Crossover condition\.

The total cost is

J​\(N\)=fI⋅I​\(N\)\+fC⋅C​\(N\)\+M​\(N\),J\(N\)=f\_\{I\}\\cdot I\(N\)\+f\_\{C\}\\cdot C\(N\)\+M\(N\),\(27\)wherefIf\_\{I\}andfCf\_\{C\}denote the frequencies of index rebuild and query, respectively\. Multiprobe grid achieves lower total cost than a given baseline whenJgrid<JbaselineJ\_\{\\text\{grid\}\}<J\_\{\\text\{baseline\}\}\. Because the memory termM​\(N\)M\(N\)enters identically on both sides, it cancels and the inequality reduces to

fI⋅Igrid\+fC⋅Cgrid<fI⋅Ibaseline\+fC⋅Cbaseline\.f\_\{I\}\\cdot I\_\{\\text\{grid\}\}\+f\_\{C\}\\cdot C\_\{\\text\{grid\}\}\\;<\\;f\_\{I\}\\cdot I\_\{\\text\{baseline\}\}\+f\_\{C\}\\cdot C\_\{\\text\{baseline\}\}\.\(28\)Collecting thefIf\_\{I\}terms on the right and thefCf\_\{C\}terms on the left,

fC⋅\(Cgrid−Cbaseline\)<fI⋅\(Ibaseline−Igrid\)\.f\_\{C\}\\cdot\\bigl\(C\_\{\\text\{grid\}\}\-C\_\{\\text\{baseline\}\}\\bigr\)\\;<\\;f\_\{I\}\\cdot\\bigl\(I\_\{\\text\{baseline\}\}\-I\_\{\\text\{grid\}\}\\bigr\)\.\(29\)Multiprobe has lower indexing cost \(Igrid<IbaselineI\_\{\\text\{grid\}\}<I\_\{\\text\{baseline\}\}\) and higher per\-query latency \(Cgrid\>CbaselineC\_\{\\text\{grid\}\}\>C\_\{\\text\{baseline\}\}\), so we defineΔ​I:=Ibaseline−Igrid\>0\\Delta I:=I\_\{\\text\{baseline\}\}\-I\_\{\\text\{grid\}\}\>0andΔ​C:=Cgrid−Cbaseline\>0\\Delta C:=C\_\{\\text\{grid\}\}\-C\_\{\\text\{baseline\}\}\>0\. Both sides of the inequality are positive\. Dividing both sides byfI⋅Δ​C\>0f\_\{I\}\\cdot\\Delta C\>0\(which preserves the inequality direction\),

fCfI<Δ​IΔ​C=:Ncross\.\\frac\{f\_\{C\}\}\{f\_\{I\}\}\\;<\\;\\frac\{\\Delta I\}\{\\Delta C\}\\;=:\\;N\_\{\\text\{cross\}\}\.\(30\)The ratiofC/fIf\_\{C\}/f\_\{I\}is the expected number of queries per index rebuild; multiprobe wins on total cost whenever this ratio falls below the crossoverNcrossN\_\{\\text\{cross\}\}\.

##### Empirical crossovers for GloVe\-200 \(N=1\.18×106N=1\.18\\times 10^\{6\}\)\.

For each algorithm we use the Pareto\-optimal configuration nearest to recall@kk=10=0\.80\{=\}0\.80\. Multiprobe’s anchor is\(m=6,G=5\)\(m\{=\}6,G\{=\}5\)\. Per\-algorithm values and the resulting crossovers are reported in Table[C2](https://arxiv.org/html/2607.01283#A3.T2);Δ​I\\Delta IandΔ​C\\Delta Care converted to a common time unit \(seconds\) before computing the ratio\. The 2,600–20,400 range cited in Section[3\.4](https://arxiv.org/html/2607.01283#S3.SS4)is set by the FAISS\-IVF crossover \(2,591\) and the Voyager crossover \(20,432\), the two extremes among the four baselines\.

Table C2:Rebuild\-to\-query crossover thresholdNcrossN\_\{\\text\{cross\}\}for multiprobe grid against each baseline atN=1\.18×106N=1\.18\\times 10^\{6\}, recall@kk=10=0\.80\{=\}0\.80\. Multiprobe achieves lower total cost whenfC/fI<Ncrossf\_\{C\}/f\_\{I\}<N\_\{\\text\{cross\}\}\(i\.e\., when index rebuilds happen at least once perNcrossN\_\{\\text\{cross\}\}queries\)\.

## Appendix DSupplementary Figures

![Refer to caption](https://arxiv.org/html/2607.01283v1/x3.png)Figure D1:Overview of the multiprobe grid algorithm\.Initialization:dataset points are projected fromℝd\\mathbb\{R\}^\{d\}toℝm\\mathbb\{R\}^\{m\}\(m≪dm\\ll d\) via principal component analysis and assigned to cells in a uniformGmG^\{m\}grid\. Empty cells store a pointer to the nearest occupied cell, as computed by multisource breadth\-first\-search\.Similarity search:the query𝐪\\mathbf\{q\}is projected to𝐪′\\mathbf\{q\}^\{\\prime\}, which identifies a primary cell\. Fornprobe\>1n\_\{\\text\{probe\}\}\>1, additional cells in the orthant toward which𝐪′\\mathbf\{q\}^\{\\prime\}is displaced are probed in order of wall distance\. Candidates from all probed cells are gathered and re\-ranked in the nativedd\-dimensional space to return the top\-kkneighbors\.![Refer to caption](https://arxiv.org/html/2607.01283v1/x4.png)Figure D2:Pareto fronts across subsampledNNon GloVe\-200\-angular \(d=200d=200\), where each panel shows all five algorithms \+ brute\-force \(which appears as a single point at recall=1\.0\)\. Note that panel \(h\) corresponds to Figure[1](https://arxiv.org/html/2607.01283#S3.F1)in the main text\.![Refer to caption](https://arxiv.org/html/2607.01283v1/x5.png)Figure D3:Pareto fronts across the GloVe\-25\-, 50\-, 100\-, and 200\-angular datasets \(N=1\.18×106N=1\.18\\times 10^\{6\}\), where each panel shows all five algorithms \+ brute\-force \(which appears as a single point at recall=1\.0\)\. Note that panel \(d\) corresponds to panel \(h\) in Figure[D2](https://arxiv.org/html/2607.01283#A4.F2)and Figure[1](https://arxiv.org/html/2607.01283#S3.F1)in the main text\.![Refer to caption](https://arxiv.org/html/2607.01283v1/x6.png)Figure D4:log10⁡\(QPS\)\\log\_\{10\}\(\\mathrm\{QPS\}\)vs\.log⁡\(N\)\\log\(N\)plots at each target recall@kk=10 used to derive the exponents in Figure[2](https://arxiv.org/html/2607.01283#S3.F2)a\. Datasets: GloVe\-200\-angular \(d=200\)d=200\)subsampled atN=104N=10^\{4\},2\.0×1042\.0\\times 10^\{4\},4\.0×1044\.0\\times 10^\{4\},7\.5×1047\.5\\times 10^\{4\},1\.5×1051\.5\\times 10^\{5\},3\.0×1053\.0\\times 10^\{5\},6\.0×1056\.0\\times 10^\{5\}, and the full1\.18×1061\.18\\times 10^\{6\}points\. The slope of each curve gives anαN\\alpha\_\{N\}value for the respective algorithm and target recall \(one data point in Figure[2](https://arxiv.org/html/2607.01283#S3.F2)a\)\. Note that QPS values are interpolated along the Pareto front for eachNNand target recall\. Points are omitted where no configuration in the benchmark sweep achieved the target recall\.![Refer to caption](https://arxiv.org/html/2607.01283v1/x7.png)Figure D5:Pareto fronts across subsampledNNon SIFT\-128\-euclidean \(d=128d=128\), where each panel shows all five algorithms \+ brute\-force \(which appears as a single point at recall=1\.0\)\.![Refer to caption](https://arxiv.org/html/2607.01283v1/x8.png)Figure D6:NN\-scaling exponentαN\\alpha\_\{N\}vs\. recall@kk=10 target on SIFT\-128\-euclidean\. Datasets: SIFT\-128\-euclidean subsampled atN∈\{104,5×104,105,5×105,106\}N\\in\\\{10^\{4\},5\\times 10^\{4\},10^\{5\},5\\times 10^\{5\},10^\{6\}\\\}\.![Refer to caption](https://arxiv.org/html/2607.01283v1/x9.png)Figure D7:log10⁡\(QPS\)\\log\_\{10\}\(\\mathrm\{QPS\}\)vs\.log10⁡\(N\)\\log\_\{10\}\(N\)plots at each target recall@kk=10\. Datasets: SIFT\-128\-euclidean \(d=128d=128\) subsampled atN∈\{104,5×104,105,5×105,106\}N\\in\\\{10^\{4\},5\\times 10^\{4\},10^\{5\},5\\times 10^\{5\},10^\{6\}\\\}\. The slope of each curve gives anαN\\alpha\_\{N\}value for the respective algorithm and target recall \(one data point in Figure[D6](https://arxiv.org/html/2607.01283#A4.F6)\)\. Note that QPS values are interpolated along the Pareto front for eachNNand target recall\. Points are omitted where no configuration in the benchmark sweep achieved the target recall![Refer to caption](https://arxiv.org/html/2607.01283v1/x10.png)Figure D8:log10⁡\(QPS\)\\log\_\{10\}\(\\mathrm\{QPS\}\)vs\.log⁡\(d\)\\log\(d\)plots at each target recall@kk=10 used to derive the exponents in Figure[2](https://arxiv.org/html/2607.01283#S3.F2)b\. Datasets: GloVe\-25, \-50, \-100, and \-200\-angular \(N=1\.18×106N=1\.18\\times 10^\{6\}\)\. The slope of each curve gives anαd\\alpha\_\{d\}value for the respective algorithm and target recall \(one data point in Figure[2](https://arxiv.org/html/2607.01283#S3.F2)b\)\. Note that QPS values are interpolated along the Pareto front for eachddand target recall\. Points are omitted where no configuration in the benchmark sweep achieved the target recall\.![Refer to caption](https://arxiv.org/html/2607.01283v1/x11.png)Figure D9:Variance retained by PCA projection as a function of the number of PCA componentsmmand native dimensionality of the datasetdd\.\(a\)Cumulative variance vs\.mmfor the GloVe\-25, \-50, \-100, and \-200\-angular datasets \(N=1\.18×106N=1\.18\\times 10^\{6\}\)\. Dotted vertical lines denote the minimum and maximum PCA components explored during hyperparameter optimization of multiprobe grid\.\(b\)Variance explained at fixedm∈\{2,4,6,8\}m\\in\\\{2,4,6,8\\\}as a function of native dimensionalitydd\. Although the absolute variance explained withmmcomponents decreases withdd, the grid algorithm compensates by adapting its projection depth at query time \(Table[E1](https://arxiv.org/html/2607.01283#A5.T1)\)\.![Refer to caption](https://arxiv.org/html/2607.01283v1/x12.png)Figure D10:Build time scaling withNNacross all five algorithms\. Datasets: GloVe\-200\-angular \(d=200\)d=200\)subsampled atN=104N=10^\{4\},2\.0×1042\.0\\times 10^\{4\},4\.0×1044\.0\\times 10^\{4\},7\.5×1047\.5\\times 10^\{4\},1\.5×1051\.5\\times 10^\{5\},3\.0×1053\.0\\times 10^\{5\},6\.0×1056\.0\\times 10^\{5\}, and the full1\.18×1061\.18\\times 10^\{6\}points\. For each algorithm andNN, we report the build time of the Pareto\-optimal configuration nearest to recall@kk=10=0\.80=0\.80; because this configuration can vary acrossNN, fit quality \(reported asR2R^\{2\}\) differs across algorithms\. The slope of each fit gives the indexing scaling exponentηI\\eta\_\{I\}, as reported in Table[1](https://arxiv.org/html/2607.01283#S3.T1)\(the exponent forI​\(N\)I\(N\)entries\)\.![Refer to caption](https://arxiv.org/html/2607.01283v1/x13.png)Figure D11:Memory footprint scaling withNNacross all five algorithms\. Datasets: GloVe\-200\-angular \(d=200\)d=200\)subsampled atN=104N=10^\{4\},2\.0×1042\.0\\times 10^\{4\},4\.0×1044\.0\\times 10^\{4\},7\.5×1047\.5\\times 10^\{4\},1\.5×1051\.5\\times 10^\{5\},3\.0×1053\.0\\times 10^\{5\},6\.0×1056\.0\\times 10^\{5\}, and the full1\.18×1061\.18\\times 10^\{6\}points\. Followingann\-benchmarksaumuller\_ann\-benchmarks\_2020, memory footprint is measured as the difference in process resident set size \(RSS\) before and after index construction\. We plot values for the Pareto\-optimal configuration nearest to recall@kk=10=0\.80=0\.80at eachNN\. The slope of each fit gives the memory scaling exponentηM\\eta\_\{M\}, as reported in Table[1](https://arxiv.org/html/2607.01283#S3.T1)\(the exponent forM​\(N\)M\(N\)entries\)\. Because memory footprint is measured via process RSS rather than on\-disk index size, it may include differences in Python runtime and loaded data overhead in addition to the index itself\.![Refer to caption](https://arxiv.org/html/2607.01283v1/x14.png)Figure D12:BFS fallback frequency with grid splits \(GG\), probe budget \(nproben\_\{\\text\{probe\}\}\), dataset size \(NN\), and dataset dimensionality \(dd\)\. Each panel varies one of the variables while holding the other three constant\. Hyperparameter configurations are representative of the range explored during Optuna hyperparameter optimization \(Table[E1](https://arxiv.org/html/2607.01283#A5.T1)\)\.\(a\)BFS fallback count vs\. grid splitsGGon GloVe\-200\-angular \(N=1\.18×106N=1\.18\\times 10^\{6\}\), withm=6m=6andnprobe=1n\_\{\\text\{probe\}\}=1held fixed\.\(b\)BFS fallback count vs\. probe budgetnproben\_\{\\text\{probe\}\}on GloVe\-200\-angular \(N=1\.18×106N=1\.18\\times 10^\{6\}\), withm=6m=6andG=12G=12held fixed\.\(c\)BFS fallback count vs\. dataset sizeNNon GloVe\-200\-angular subsampled atN∈\{104,1\.5×105,1\.18×106\}N\\in\\\{10^\{4\},1\.5\\times 10^\{5\},1\.18\\times 10^\{6\}\\\}, withm=6m=6,G=10G=10, andnprobe=4n\_\{\\text\{probe\}\}=4held fixed\.\(d\)BFS fallback count vs\. dataset dimensionalityddacross the GloVe\-25, \-50, \-100, and \-200\-angular datasets \(N=1\.18×106N=1\.18\\times 10^\{6\}each\), withm=6m=6,G=10G=10, andnprobe=4n\_\{\\text\{probe\}\}=4held fixed\.
## Appendix ESupplementary Tables

Table E1:Pareto\-optimal multiprobe grid configurations\(m,G,nprobe\)\(m,G,n\_\{\\text\{probe\}\}\)from benchmark sweeps at each target recall\. Dataset: GloVe\-25, \-50, \-100, and \-200\-angular \(N=1\.18×106N=1\.18\\times 10^\{6\}\)\. Each table entry represents the Pareto\-optimal configuration whose measured recall is closest to the target recall\. Parenthetical values indicate the actual measured recall@kk=10\. Note that the entry fordd=200 at a target recall of 0\.95 matches the entry fordd=200 at a target recall of 0\.90, reflecting the algorithm’s recall ceiling at that dimensionality\.