A Power Law in Logarithm's Clothing: On the Scalability of Graph-Based Vector Search

arXiv:2609.02143 · cs.DB, cs.AI, cs.IR, cs.LG · Submitted 2026-09-02 · Read on arXiv

cs.DB, cs.AI, cs.IR, cs.LG

Submitted: 2026-09-02

Updated: 2026-09-02

Comments: 17 pages, 10 figures

Code: https://github.com/pgvector/pgvector

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Terminology

• Pruning — 12× in this paper · explained in 4 episodes
• Accuracy — 8× in this paper · explained in 1 episode
• Benchmark — 7× in this paper · explained in 2 episodes
• Core — 6× in this paper · explained in 2 episodes
• Embeddings — 6× in this paper · explained in 2 episodes
• Graph Construction — 4× in this paper · explained in 3 episodes
• Curse of Dimensionality — 3× in this paper · explained in 6 episodes
• Benchmarking — 2× in this paper · explained in 4 episodes
• Intrinsic Dimension — 2× in this paper · explained in 2 episodes
• Quantization — 2× in this paper · explained in 12 episodes
• Semantic Similarity — 2× in this paper · explained in 2 episodes
• Sparse Neighborhood Graph — 2× in this paper
• APEX — 1× in this paper · explained in 1 episode
• Adam — 1× in this paper · explained in 2 episodes
• Adaptation — 1× in this paper · explained in 1 episode
• Elias — 1× in this paper · explained in 2 episodes
• Generalization — 1× in this paper · explained in 13 episodes
• Generative AI — 1× in this paper · explained in 2 episodes
• Hierarchical Navigable Small Worlds — 1× in this paper
• Hilbert Space — 1× in this paper · explained in 2 episodes
• In Empirical Methods in Natural Language Processing — 1× in this paper
• RAG — 1× in this paper · explained in 3 episodes
• Retrieval-Augmented Generation (RAG) — 1× in this paper · explained in 16 episodes
• Self-Supervised Learning — 1× in this paper · explained in 8 episodes
• Vector Representations — 1× in this paper · explained in 2 episodes

Sources

• wav2vec 2.0: A Framework for Self-Supervised Learning of Speech Representations
• Verifying the Union of Manifolds Hypothesis for Image Data
• The Faiss library
• Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph
• Retrieval-Augmented Generation for Large Language Models: A Survey
• On the Difficulty of Nearest Neighbor Search
• VIBE: Vector Index Benchmark for Embeddings
• Graph-based time-space trade-offs for approximate near neighbors
• Graph based Nearest Neighbor Search: Promises and Failures
• Sparse Neighborhood Graph-Based Approximate Nearest Neighbor Search Revisited: Theoretical Analysis and Optimization
• Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs
• UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction
• Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks
• Results of the Big ANN: NeurIPS'23 competition
• FreshDiskANN: A Fast and Accurate Graph-Based ANN Index for Streaming Similarity Search
• A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search
• GRAB-ANNS: High-Throughput Indexing and Hybrid Search via GPU-Native Bucketing

Related papers

• Vibe Coding on Trial: Operating Characteristics of Unanimous LLM Juries
• Human-Level Text-to-SQL via Reinforcement Learning on Verified Data, Without Pipeline Engineering
• Bridging Business Intent and Data: A Benchmark for Automatic Relational Data Product Generation
• DexterSQL: Deep Schema Exploration and Rule-based Correction for Text-to-SQL Generation
• MaDI-Bench: An End-to-End Data Integration Benchmark
• Eigenius: A Typed Knowledge-Graph DBMS with Epistemic Stratification and Institution-Mediated Reasoning