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

Grid-based search stays fast in high dimensions while competitors slow down

Approximate nearest neighbor (ANN) search—finding the closest data points to a query in high-dimensional space—is fundamental to modern ML, from recommendation systems to transformer attention mechanisms. The standard wisdom is that graph-based and tree-based methods outperform older grid-based approaches. This paper challenges that assumption by showing that multiprobe grid search exhibits a striking property: as dimensionality increases, its performance degrades far more gracefully than competing methods.

The authors benchmark a multiprobe grid algorithm (dividing space into a grid, then checking multiple cells near the query) against graph-, tree-, and partitioning-based ANN methods on the GloVe embedding family. The key finding is a d-scaling crossover: while graph and tree methods see throughput drop sharply as dimensionality grows, multiprobe grid maintains roughly constant performance scaling with dimension. This advantage persists even though queries scale nearly linearly with dataset size N.

Why this matters and when it's practical

The result has two important implications. First, it identifies a niche where grid-based methods win: scenarios with high indexing costs (frequent index rebuilds) or very high-dimensional data where rebuilding indices is expensive anyway. Second, it connects to a recent theoretical insight—that self-attention in transformers is equivalent to an ANN operation. If attention is ANN, then the scaling laws here help explain and optimize the computational cost of efficient transformer architectures.

The near-linear N-scaling is a cost: as datasets grow, queries get more expensive. But that trade-off is acceptable in many real-world systems where the dataset is fixed or grows slowly, and where the index doesn't need frequent updates. Indexing cost matters because building and maintaining high-dimensional data structures is often a bottleneck in production systems.

The takeaway

The paper's core claim is empirical: grid-based methods don't deserve dismissal from modern scaling analyses. They offer a different curve—flatter in dimensionality, steeper in dataset size—that makes them competitive when dimensions are large or rebuilding is frequent. This is a narrow but genuine advantage, and it suggests that practitioners optimizing for specific hardware or workload constraints should reconsider older methods rather than defaulting to graph-based approaches. For researchers building efficient transformers, the dimensional robustness of grid-based search offers a potential blueprint for cost-aware architectures.