A decades-old grid search technique for finding similar data points outperforms newer methods when the number of dimensions gets large, according to new research posted to arXiv.
Researchers ran systematic benchmarks of a multiprobe grid algorithm against graph-, tree-, and partitioning-based approximate nearest neighbor (ANN) methods — the workhorses of modern vector search. On the GloVe embedding family, the grid method held a roughly constant performance exponent as dimensionality scaled up, while competing approaches degraded. Query time scales near-linearly with dataset size, and indexing — the upfront cost of building the search structure — came in cheaper than rivals.
That indexing cost matters more than it might seem. Systems that rebuild their search indexes frequently, or that need to stay fast across very high-dimensional data, pay a tax every time they reconstruct. A method that is cheaper to rebuild and more dimensionally stable is a genuine operational advantage, not just a benchmark footnote. The researchers also flag a connection to transformer efficiency: recent work treats self-attention as an ANN operation, meaning ANN scaling properties could inform cost models for large language models.
Grid-based ANN has mostly sat out the vector-database arms race that accompanied the AI boom — libraries like FAISS and HNSW have dominated production deployments. Whether that changes depends on whether "competitive in rebuild-heavy or high-dimensional settings" translates to real workloads, which these benchmarks, run on GloVe embeddings alone, do not fully answer.