Research map / Graph learning / Graph algorithms and clustering
Probabilistic Routing for Graph-Based Approximate Nearest Neighbor Search
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 PEOs, a probabilistic routing test for graph-based ANNS that uses space partitioning, random projections and extreme-order-statistics to decide which neighbors need exact distance computation, with a probabilistic guarantee.
Problem
Graph-based approximate nearest neighbor search spends most time on exact distance computations to neighbors; existing routing heuristics (e.g., FINGER) lack formal guarantees and can cause large estimation errors and recall loss.
Approach
Partition the space into L orthogonal subspaces and aggregate extreme-order-statistic projection data (CEOs-style) across them to reduce the variance of the angle estimator, yielding a (δ, 1-ε) probabilistic routing test with a lookup-table implementation and SIMD.
Key results
- PEOs accelerates HNSW by 1.6 to 2.5 times in QPS across million-scale datasets at matched recall.
- PEOs is 1.1 to 1.4 times faster than the FINGER routing baseline.
- PEOs saves around 75% of exact distance calculations on each dataset; index size is 1.2x to 2.0x that of HNSW on million-scale datasets.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add PEOs routing to HNSW | HNSW · Million-scale datasets | throughput: 1.6 to 2.5 times | Helped |
| Use PEOs routing instead of FINGER routing | HNSW · Million-scale datasets | throughput: 1.1 to 1.4 times | Helped |
| Partition the space with L > 1 instead of L = 1 (ablation) | HNSW+PEOs · SIFT10M, Tiny5M, and GIST | recall-QPS performance | Helped |
| Set L to 32 instead of 8 (ablation) | HNSW+PEOs · SIFT10M | recall-QPS performance | Hurt |
| Set L above 16 (ablation) | HNSW+PEOs · GIST | recall-QPS performance | No clear effect |
| Set error bound epsilon to 0.1 instead of other tested settings (ablation) | PEOs · DEEP10M, GloVe200, and GloVe300 | recall-QPS performance | Hurt |
| Set error bound epsilon to 0.2 (ablation) | PEOs · DEEP10M, GloVe200, and GloVe300 | recall-QPS performance | Helped |
| Use compact PEOs implementation with L=2 and 8-bit scalar compression (ablation) | PEOs · DEEP10M | index size (GB): 12.13 (+0.98x) -> 7.89 (+0.29x) | Helped |
| Use compact PEOs implementation with L=2 and 8-bit scalar compression (ablation) | PEOs · SIFT10M | index size (GB): 14.39 (+0.96x) -> 9.62 (+0.26x) | Helped |
| Add PEOs routing to HNSW | HNSW · DEEP100M | index size (GB): 66.0 -> 67.9 (+0.029x) | Hurt |
Surprising findings
- FINGER and Glass reach under 30% recall on GloVe200, showing heuristic routing can produce unbounded estimation errors.
- Increasing the number of subspaces L beyond a moderate value (e.g., L=32 on SIFT10M) hurts performance because variance grows.
Limitations
- Index size overhead is large for low-dimensional datasets (over 90% extra for d<200 in the standard version).
- Analysis assumes normal approximations and sufficiently large m; the guarantee is for the routing test, not end-to-end recall.
- Extension to MIPS is only sketched in the appendix and not evaluated.
Experimental setup
Datasets: GloVe200 GloVe300 DEEP10M SIFT10M Tiny5M GIST DEEP100M
Benchmarks: GloVe200 GloVe300 DEEP10M SIFT10M Tiny5M GIST DEEP100M
Metrics: recall queries per second number of distance calculations index size indexing time
Baselines: HNSW NSSG Glass ScaNN IVFPQFS FINGER RCEOs
Builds on: HNSW NSSG CEOs SimHash FINGER
Closest papers by meaning
- CSPG: Crossing Sparse Proximity Graphs for Approximate Nearest Neighbor Search (NeurIPS 2024 · similarity 0.87)
- Optimistic Query Routing in Clustering-based Approximate Maximum Inner Product Search (NeurIPS 2025 · similarity 0.86)
- Graph-Based Algorithms for Diverse Similarity Search (ICML 2025 · similarity 0.86)
- Sort Before You Prune: Improved Worst-Case Guarantees of the DiskANN Family of Graphs (ICML 2025 · similarity 0.86)
- Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limits (NeurIPS 2024 · similarity 0.86)
- Prune, Don’t Rebuild: Efficiently Tuning $\alpha$-Reachable Graphs for Nearest Neighbor Search (NeurIPS 2026 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.