Research map / Graph learning / Graph algorithms and clustering

MCGI: Manifold-Consistent Graph Indexing for Billion-Scale Disk-Resident Vector Search

NeurIPS 2026 · Graph learning › Graph algorithms and clustering · approach: Graph comparison and random features · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes MCGI, a disk-resident graph index that uses per-node LID estimates (MLE) mapped through a sigmoid to set the Vamana pruning parameter alpha, reporting large throughput and latency gains on GIST1M and SIFT1B.

Problem

Graph-based ANN search on SSD-resident indices degrades in high-dimensional spaces because greedy routing on a Euclidean proximity graph diverges from the data manifold (Euclidean-Geodesic mismatch), hurting recall-throughput at billion scale.

Approach

Use the local intrinsic dimensionality (MLE estimate from k-NN distances), z-score normalized and passed through a logistic function, to assign each node a node-specific pruning parameter alpha during Vamana-style graph construction, so high-LID regions get more conservative pruning; an online variant estimates LID from candidate sets during search-time construction.

Key results

• On GIST1M, MCGI reaches 375.1 QPS at >=95% recall versus 64.7 for DiskANN (5.8x).
• On SIFT1B at 90% recall, MCGI achieves 3,436 QPS and 16.20 ms latency versus DiskANN's 2,597 QPS and 49.06 ms (about 3x lower latency).
• MCGI reaches 96.02% recall at R=32 on GIST1M where PipeANN plateaus near 80%.

Surprising findings

• PipeANN plateaus near 80% recall on GIST1M at R=32 despite I/O pipelining, which the authors attribute to fragmented topology.
• Replacing the sigmoid mapping with a linear mapping causes roughly a 50% QPS drop at R=48 in the authors' ablation.

Limitations

• Theoretical lemma and propositions rely on sketch-level arguments (e.g., uniform-on-sphere assumption, approximations ln(1-x)≈-x), and the fixed-beam corollary is monotone but not tight.
• Calibration on billion-scale data is costly, motivating an online approximation whose quality is not separately characterized.
• Evaluation uses a single hardware setup and compares against mostly disk-based baselines; in-memory graph results are reported only as reference points.

Experimental setup

Datasets: SIFT1M GloVe-100 GIST1M SIFT1B T2I-1B

Benchmarks: SIFT1M GloVe-100 GIST1M SIFT1B T2I-1B

Metrics: QPS at Recall@10 >= 95% latency at 90% recall recall-QPS trade-off

Baselines: PipeANN CSPG DiskANN (Vamana) IVF-Flat (Faiss) HNSW

Builds on: DiskANN Vamana Hill estimator / LID MLE relative neighborhood graph

Closest papers by meaning

• Distance Adaptive Beam Search for Provably Accurate Graph-Based Nearest Neighbor Search (NeurIPS 2025 · similarity 0.85)
• Sort Before You Prune: Improved Worst-Case Guarantees of the DiskANN Family of Graphs (ICML 2025 · similarity 0.84)
• Recovering Manifold Structure Using Ollivier Ricci Curvature (ICLR 2025 · similarity 0.84)
• Graph-Based Algorithms for Diverse Similarity Search (ICML 2025 · similarity 0.83)
• CSPG: Crossing Sparse Proximity Graphs for Approximate Nearest Neighbor Search (NeurIPS 2024 · similarity 0.83)
• Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limits (NeurIPS 2024 · similarity 0.83)