🤖 machine learning

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

This paper presents a systematic analysis of multiprobe grid-based ANN search, revealing its superior scalability in high dimensions and lower indexing costs compared to graph, tree, and partitioning methods, thereby suggesting its potential for optimizing rebuild-heavy applications and efficient transformer architectures.

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

Published 2026-07-03

📖 5 min read🧠 Deep dive

CC BY 4.0

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

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Finding a Needle in a Growing, Shifting Haystack

Imagine you are looking for a specific needle in a haystack.

The Needle: The exact answer you are looking for (the "nearest neighbor").
The Haystack: A massive collection of data points (like millions of words or images).
The Problem: As the haystack gets bigger (more data) or the needles get more complex (higher dimensions), finding that specific needle becomes incredibly slow and difficult.

This paper introduces a new, old-school way to find needles called "Multiprobe Grid Search." The authors tested this method against the modern, high-tech tools everyone else is using (like graph-based and tree-based systems) and found something surprising: Grid-based methods are actually very strong when the data gets huge or very complex.

The Analogy: The Supermarket vs. The Maze

To understand the difference between the methods, let's use two analogies:

1. The Modern Methods (Graphs and Trees): The Complex Maze
Current popular methods are like a complex, multi-layered maze. To find a needle, you have to follow a winding path through the maze.

The Catch: As the maze gets bigger (more data) or the walls get more confusing (higher dimensions), the path gets longer and more tangled. You spend a lot of time backtracking and getting lost. The paper found that as the data gets more complex, these maze-walkers get significantly slower.

2. The New Method (Multiprobe Grid): The Organized Supermarket
The method in this paper is like a perfectly organized supermarket.

How it works: Instead of a maze, the store is divided into simple, square aisles (a grid).
The Trick: When you want to find an item, you don't just check the one aisle you think it's in. You check that aisle, plus the aisles immediately next to it, and the ones next to those. This is called "multiprobe."
The Secret Sauce: To decide which aisles to check, the system uses a simplified map (a "PCA projection") that ignores some of the confusing details. It only looks at the main layout. Once it picks the right aisles, it does a quick final check in the real, detailed world.

What the Paper Discovered

The authors ran experiments to see how fast these methods get as they change two things: the size of the data and the complexity of the data.

1. The "Size" Test (More Haystacks)

The Setup: They doubled and tripled the amount of data.
The Result: The "Supermarket" (Grid) method slowed down almost perfectly in line with the size. If you double the data, it takes roughly double the time. This is called near-linear scaling.
The Competitors: The "Maze" methods slowed down much less than expected at first, but as the data got huge, they started to struggle more than the Grid method.
Takeaway: The Grid method is very predictable and honest about how much time it needs as data grows.

2. The "Complexity" Test (The Dimension Crossover)

The Setup: They made the data more complex (adding more features, like going from a 2D drawing to a 3D model, then to a 100D model).
The Surprise: This is the paper's biggest discovery.
- The "Maze" methods (Graphs/Trees) got much slower as complexity increased. The more complex the data, the harder it was for them to prune (ignore) the wrong paths.
- The "Supermarket" (Grid) method stayed steady. Because it uses a simplified map to decide which aisles to check, it didn't get confused by the extra complexity.
The Crossover: At a certain point of complexity, the Grid method actually became faster than the modern Maze methods. The paper calls this a "crossover."

3. The Setup Cost (Building the Store)

The Setup: How long does it take to build the index (set up the shelves) before you can start searching?
The Result: The Grid method is incredibly fast to set up. It took the Grid method 4 to 36 seconds to organize a million items. The modern Maze methods took minutes to over 25 minutes.
Why it matters: If you have a system where you constantly throw away old data and build a new index from scratch (like a recommendation system that updates every hour), the Grid method is a winner because it builds so fast.

The "Total Cost" Equation

The paper argues that you shouldn't just look at how fast a search is during the search. You have to look at the Total Cost:

Total Cost = (Time to Build) + (Time to Search × How often you Search)

Scenario A: You build the index once and search a million times. The slow-to-build Maze methods might win because they are fast to search.
Scenario B: You build the index often (rebuild-heavy) or search only a few times. The Grid method wins because it is so cheap and fast to build.

Why This Matters for AI (The "Attention" Connection)

The paper mentions that modern AI (Transformers) works by doing "Approximate Nearest Neighbor" searches to decide which words to pay attention to.

If an AI model needs to constantly update its memory (index) as new words come in, the Grid method's low setup cost and ability to handle complex data without slowing down could make AI faster and cheaper to run.

Summary

The paper says: "Don't ignore the simple grid."
While everyone has been obsessed with complex, maze-like search methods, the simple, organized "Supermarket" approach (Multiprobe Grid) is actually better at handling:

Huge datasets (predictable speed).
Very complex data (it doesn't get confused by high dimensions).
Frequent rebuilding (it sets up in seconds, not minutes).

It's a reminder that sometimes the "old school" way, when tweaked correctly, is the most efficient tool for the job.

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

Problem Statement

Approximate Nearest Neighbor (ANN) search is a fundamental primitive in modern machine learning, serving both traditional retrieval tasks and emerging roles as a computational building block for transformer architectures (where self-attention is formalized as an ANN operation). While empirical scaling laws guide the design of large-scale models, the scaling behavior of ANN algorithms with respect to dataset size ( $N$ ) and dimensionality ( $d$ ) remains a critical, yet under-characterized, area of study.

Existing literature has extensively analyzed graph-based (e.g., HNSW), tree-based, and partitioning-based methods. However, grid-based approaches, despite their foundational role in early ANN theory, have been largely absent from modern scaling analyses. This paper addresses the gap by systematically characterizing the scaling dynamics of a multiprobe grid algorithm, specifically investigating how its performance scales with $N$ and $d$ compared to state-of-the-art competitors.

Methodology

The Multiprobe Grid Algorithm

The authors propose a multiprobe grid algorithm that decouples cell selection from the full dimensionality $d$ . The workflow involves:

PCA Projection: Data points are projected from $\mathbb{R}^d$ to a lower-dimensional subspace $\mathbb{R}^m$ ( $m \ll d$ ).
Grid Partitioning: The subspace is partitioned into a uniform grid of $G^m$ cells.
Multiprobe Selection: At query time, the algorithm identifies the "home" cell and probes up to $2^m - 1$ neighboring cells, ordered by their squared wall distance ( $w_i^2$ ) from the query.
Re-ranking: Candidates collected from probed cells are re-ranked in the original high-dimensional space $\mathbb{R}^d$ .

Theoretical Model

The authors derive a closed-form relationship between query cost (Queries Per Second, QPS) and recall ( $R$ ).

Cost Model: Query cost is linear in the number of probed cells ( $n_{probe}$ ) and the number of points per cell ( $N/G^m$ ).
Recall Model: Assuming a uniform distribution, the probability of the true nearest neighbor lying in a probed cell decays exponentially with the wall distance.
Resulting Relationship: The model predicts a log-linear relationship between QPS and recall: $\log(\text{QPS}) \approx \log(\text{const}) - \log(R)$ . This arises from the exponential decay of membership probability across cells and the linear growth of the candidate set size.

Empirical Evaluation

The study evaluates the multiprobe grid against four baselines representing major ANN families:

Graph-based: Voyager, PyNNDescent.
Tree-based: Annoy.
Partitioning/Quantization: FAISS-IVF.

Experiments were conducted using the ann-benchmarks framework on two datasets:

GloVe-200-angular (Word embeddings, $d=200$ , $N \approx 1.18 \times 10^6$ ).
SIFT-128-euclidean (Image descriptors, $d=128$ ).

The evaluation focused on scaling exponents for $N$ ( $\alpha_N$ ) and $d$ ( $\alpha_d$ ), Pareto fronts (throughput vs. recall), and total cost analysis (indexing + query time).

Key Results

1. Log-Linear Throughput-Recall Relationship

Pareto front analysis on GloVe-200 confirms the theoretical prediction: the multiprobe grid exhibits a log-linear decrease in throughput as recall increases. This behavior is distinct from the baselines and is driven by the grid geometry and the exponential decay of nearest-neighbor membership probability.

2. $N$ -Scaling: Near-Linear Degradation

The multiprobe grid scales near-linearly with dataset size ( $N$ ).

At recall@10 = 0.80, the scaling exponent is $\alpha_N \approx -0.94$ (GloVe) and $-0.83$ (SIFT).
In contrast, graph-based and tree-based baselines exhibit sub-linear scaling ( $\alpha_N$ ranging from $-0.44$ to $-0.59$).
Implication: While multiprobe grid throughput degrades faster as $N$ grows compared to graph methods, this is a mechanistic consequence of the algorithm's design (candidate count grows linearly with $N$ ).

3. $d$ -Scaling: A Critical Crossover

A previously unreported $d$ -scaling crossover is observed on the GloVe embedding family.

Baselines: As dimensionality $d$ increases, the throughput of graph, tree, and partitioning methods degrades significantly (steep $\alpha_d$ ), reflecting the "curse of dimensionality" and the failure of geometric pruning in high dimensions.
Multiprobe Grid: The scaling exponent $\alpha_d$ remains relatively flat and favorable as $d$ increases.
Mechanism: By performing cell selection in a low-dimensional PCA subspace ( $m \ll d$ ) and adapting the grid parameters ( $m, G$ ) based on $d$ and target recall, the algorithm avoids traversing the full high-dimensional space. Re-ranking costs grow only linearly with the candidate count, which is less aggressive than the cost growth of methods traversing the full $d$ -dimensional space.

4. Total Cost and Indexing Efficiency

The paper analyzes total cost $J(N) = f_I \cdot I(N) + f_C \cdot C(N) + M(N)$ , where $I$ is indexing cost, $C$ is compute cost, and $M$ is memory footprint.

Indexing Speed: Multiprobe grid is significantly faster to build than baselines. At $N = 1.18 \times 10^6$ , it builds an index in 4–36 seconds, compared to 1,569 seconds for Voyager.
Query Latency: The multiprobe grid has higher per-query latency (approx. 120 $\times$ slower than Voyager at high recall).
Competitive Regime: The method becomes competitive when the rebuild-to-query ratio ( $f_I/f_C$ ) is high. Specifically, if an index is rebuilt roughly once per 2,600–20,400 queries, the multiprobe grid offers a lower total cost. This makes it suitable for "rebuild-heavy" scenarios.

Significance and Claims

The paper claims that grid-based methods, often overlooked in modern scaling analyses, offer a distinct and competitive set of trade-offs in specific regimes:

Dimensional Robustness: The multiprobe grid is uniquely robust to increasing dimensionality ( $d$ ), outperforming graph and tree methods in high-dimensional settings where geometric pruning fails.
Low Indexing Overhead: The algorithm offers near-instant indexing compared to graph-based methods that require complex, data-dependent graph construction.
Relevance to Transformers: Given the formalization of self-attention as an ANN operation, the $N$ $N$ - and $d$ $d$ -scaling properties of ANN algorithms are directly relevant to transformer efficiency. The authors suggest that multiprobe grid may be advantageous in transformer architectures where:
- The context length ( $N$ ) or head dimension ( $d$ ) varies.
- Incremental updates are frequent (e.g., extending the KV-cache), as appending a token to a grid requires only a single cell assignment rather than a full graph rebuild.
Total Cost Perspective: The paper argues that ANN method selection should not rely solely on query latency but must consider the total cost function, including indexing frequency and rebuild costs. In high-rebuild scenarios, the low indexing cost of grid methods can outweigh their higher query latency.

In summary, the work re-establishes grid-based methods as a viable option for high-dimensional learning systems, particularly where indexing cost, rebuild frequency, and dimensional robustness are the primary constraints.