Building approximate nearest neighbor (ANN) indexes at billion scale is often dominated by expensive global clustering or graph construction, making time-to-index a first-order systems concern. We present NeuRoute, a learned hashing index that turns short binary codes into an effective routing primitive for large-scale vector search. NeuRoute trains a lightweight neural network encoder with a selective similarity-preserving objective to produce well-balanced binary addresses. During construction, NeuRoute organizes vectors into buckets by their codes and performs bucket-local clustering in the encoder's low-dimensional space to form centroids. At query time, NeuRoute exploits the encoder logits as an uncertainty signal: it uses deviation-to-threshold scores to prioritize uncertain-bit perturbations for query-adaptive multi-bucket probing, scores bucket-local centroids by their distances to the query to form a compact candidate cluster set, and applies centroid-stage gating with heap-quality-driven early stopping to prune low-value clusters before exact refinement. On billion-scale benchmarks, NeuRoute achieves strong accuracy-throughput trade-offs with fast index construction: on BigANN-1B it reaches 90.3% Recall@10 at 2,414 QPS and is 1.7× faster than OPQ+IVF-PQ (refine) at comparable accuracy, while completing end-to-end training+construction in under an hour on both BigANN-1B and Deep1B-1B. These results show that logit-guided neural routing can make hashing competitive as a lightweight ANN indexing framework at billion scale. Source code and artifacts are available at https://github.com/XingqiaoWang/NeuRoute.
Figures & tables
Figure 1: Overview of the NeuRoute pipeline (Steps 1–5). Steps 1–3: hash learning and index construction; Steps 4–5: logit-guided candidate generation with calibrated gating and early stopping before exact scoring.
Figure 2: Pairwise distances in the base space versus the encoded space for paired vectors (squared for visualization; squaring is monotonic for nonnegative distances and does not change top- k ordering). Left: encoded-sampled pairs. Right: base-sampled pairs.
Dataset
Train (s) [GPU]
Index build (s) [CPU]
CSR build (s) [CPU]
Clustering (s) [CPU]
Other/I/O (s) [CPU]
Add/Build (s) [CPU]
Total (s)
BigANN-100M
1,197.56
49.96
40.78
43.00
53.26
187.00
1,384.56 (0.39 h)
Deep1B-100M
1,176.27
41.85
64.44
69.00
53.71
229.00
1,405.27 (0.39 h)
BigANN-1B
1,183.46
529.29
420.50
380.00
442.21
1,772.00
2,955.47 (0.82 h)
Deep1B-1B
1,124.43
368.00
903.36
614.00
326.64
2,212.00
3,336.43 (0.93 h)
GLDv2
2,471.15
84.78
51.27
44.00
56.96
237.00
2,708.15 (0.75 h)
Table 3: NeuRoute build-time breakdown (seconds). Add/Build = Index build + CSR build + Clustering + Other/I/O, and Total = Train + Add/Build. Index build performs full-base encoding. CSR build constructs CSR files. Clustering is bucket-local clustering. Other/I/O is residual overhead.
Dataset
Method
Train (h)
Add/Build (h)
Total (h)
Serving footprint (GB)
Peak RSS (GB)
GLDv2
IVF-PQ
7.15
3.64
10.80
1.28
18.83
GLDv2
IVF-Flat
9.32
4.32
13.63
58.07
149.21
GLDv2
DiskANN
0.00
1.89
1.89
76.93
107.92
GLDv2
HNSW
0.00
1.79
1.79
56.11
100.84
GLDv2
NeuRoute
0.69
0.07
0.75
0.24 / 53.98
59.38
BigANN-100M
IVF-PQ
1.17
5.96
7.12
4.03
20.54
Table 4: End-to-end build cost breakdown (Train + Add/Build), in hours (h). Serving footprint (GB, bytes/ 109 ) counts the on-disk serving artifacts (index metadata plus any vector payload stored by the method); the original dataset files are not counted. Serving footprint is reported as routing-only / routing+co-located refinement vectors . Peak RSS (GB) is the maximum resident memory during build.
Figure 3: Recall@10–QPS trade-offs on BigANN-1B , Deep1B-1B , BigANN-100M , Deep1B-100M , and GLDv2 . Each curve shows the Pareto frontier obtained by sweeping the main accuracy knob of each baseline (e.g., nprobe for IVF variants, efSearch for HNSW, and the search-budget parameters for DiskANN and rerank/refine variants). Higher is better.
Method (22b)
Recall@10 (%)
QPS
LSH
37.55
82.94
ITQ
57.27
111.17
TBH
74.99
18.52
NeuRoute (no clustering)
93.86
111.40
Table 5: GLDv2 (1536D) comparison under the same evaluation harness ( nq=10,000 ). For fairness, NeuRoute is evaluated using only the learned 22-bit codes (no bucket-local clustering).
Dataset
Method
Recall@10
QPS
Build time (h)
BigANN-1B
DiskANN
0.9040
2,744
17.96
BigANN-1B
OPQ+IVF-PQ (refine)
0.9080
1,406
10.72
BigANN-1B
NeuRoute
0.9030
2,414
0.82
Deep1B-1B
DiskANN
0.8891
914.68
36.47
Deep1B-1B
OPQ+IVF-PQ (refine)
0.9120
3,342
10.51
Deep1B-1B
NeuRoute
0.9010
842
0.93
Table 6: Billion-scale operating points around 90% Recall@10 (single-node). For each method, we report the highest QPS among configurations whose Recall@10 falls in a narrow band around 0.90 (here: [0.88,0.92] ). Build time is end-to-end Train+Add/Build from Table 4 .
Op.
Variant
Recall@10
QPS
Cand./q (k)
A
No early stop
0.90335
1440
249
A
Early stop
0.90260
2414
201
B
No early stop
0.90038
1682
230
B
Early stop
0.89965
2595
194
Table 7: Ablation of heap-quality-driven early stopping on BigANN-1B ( nq=10,000 ).
τemb (%)
Base-sampled pairs
Encoded-sampled pairs
Pearson
Spearman
Pearson
Spearman
0.1
0.8335
0.7722
0.8027
0.7362
0.2
0.8422
0.7789
0.8162
0.7429
0.3
0.8458
0.7813
0.8190
0.7457
0.5
0.8460
0.7800
0.8130
0.7430
0.5 (w/o mask, run-1)
0.8368
0.7535
0.5496
0.5617
Table 8: Sensitivity to the training threshold τemb and the pair-selection mask on Deep1B-100M (database-sampled). Pearson/Spearman correlations are evaluated on a fixed set of 2,096,650 within-batch near-neighbor pairs, sampled as the top 0.5% most similar pairs separately in the base and encoded spaces (thus not necessarily the same pairs).
Dataset
Variant
Recall@10
QPS
Cand./q (k)
BigANN-1B
w/ clustering
0.90260
2414
201
BigANN-1B
no clustering
0.88780
543.6
940
Deep1B-1B
w/ clustering
0.90144
756.9
351
Deep1B-1B
no clustering
0.90007
165.5
1353
Table 9: Ablation of bucket-local clustering on 1B-scale datasets ( nq=10,000 queries). QPS is measured under the same retrieval configuration. Cand./q (k) is the number of vectors routed to exact refinement per query, reported in thousands.
Appendix figures & tables6 assets
Supplementary material from the paper’s appendix.
Appendix
Figure B.1: NeuRoute training/validation loss curves across datasets. Each panel shows the total loss over epochs with an inset zooming into the late-epoch regime to highlight convergence.
Figure C.1: KNN embedding distance versus the proposed bucket score ( L1_sum ). Each point corresponds to a probed bucket; lower scores tend to be associated with closer GT neighbors.
Figure C.2: Distribution of query–candidate Hamming distances observed during probing. Useful candidates concentrate at small Hamming distances, motivating prioritized multi-bucket enumeration under a fixed budget.
Figure C.3: Probability that a KNN flips a bit as a function of the bit’s margin rank (rank 0 = smallest margin / least confident). GT flips concentrate on low-margin bits, validating margin-ranked bit flipping for bucket routing.
Figure D.1: End-to-end index build time (hours, log-scale) for IVF–PQ, IVF–Flat, DiskANN, HNSW, OPQ + IVF–PQ, and NeuRoute.
Figure E.1: CAGRA GPU-only scaling reference at 50M–80M on BigANN and Deep1B. Points are labeled by dataset size (50M/60M/70M/80M).
Approximate Nearest-Neighbor Search (ANNS) pipelines for high-dimensional neural embeddings spend the bulk of their query time in candidate verification, making it the primary bottleneck in the search process. In this paper, we present PANORAMA, a state-of-the-art refinement technique that accelerates verification by exploiting the inherent spectral decay of these embeddings. Using PCA to compact signal energy, PANORAMA evaluates candidate distances incrementally, computing at each step a strict lower bound on the full-vector distance and dynamically pruning candidates the moment this bound exceeds the running k-th nearest neighbor distance. While PCA's concentration of variance facilitates pruning, it breaks the uniform-variance assumption required by Product Quantization (PQ); we resolve this with a variance-shaping step that redistributes energy across subvectors, rendering accretive refinement compatible with quantized indexes. Optimized for modern memory hierarchies via vectorized bulk-pruning and cache-conscious data layouts, PANORAMA has been upstreamed into the FAISS library across major index families (IVFPQ/Flat, HNSW, and Refine). PANORAMA achieves higher QPS at any target recall with a cost that provably scales inversely with dataset spectral decay, delivering end-to-end speedups of up to 28.9x and outperforming probabilistic methods across all recall bands.
Vansh Ramani, Alexis Schlomer, Akash Nayar +3
IIT Delhi & CMU & UCPH · Carnegie Mellon University · Indian Institute of Technology Delhi +1
By introducing RSLM (Rotated Scaled Lloyd-Max), a family of training-free vector quantization codecs compressing embeddings to 1--4 bits per dimension, we reduce memory cost and memory bandwidth of a typical large-scale Approximate Nearest Neighbor (ANN) search system, while reducing its complexity and keeping or improving recall across multiple benchmark datasets. State-of-the-art systems filter candidates using coarse partitions, approximately score them to narrow the set, and then rescore the best with higher precision representations (often >=8 bits per dimension). Our relativized codecs can bring this down to 2--4 bits per dimension. We use the properties of the ANN system to encode residual vectors instead of full vectors, both for the approximate scoring phase and the rescoring phase. Since Maximum Inner Product Search (MIPS) is very sensitive to vector norms, we correct the L2 norms of quantized vectors. Our major innovation is that we correct the L2 norm of the final reconstructed vector rather than just the residual. Our rescaling replaces more complicated schemes, such as Anisotropic loss. The residualization scheme gives us a more favorable quality vs size trade-off than generic quantization methods. Our high-performance implementation leverages a block-wise cascaded Fast Walsh-Hadamard Transform (FWHT) with linear-like complexity, AVX SIMD-optimized codebooks, and a steganographic encoding of scaling factors for perfect cache-line alignment.
Rastislav Lenhardt, Teodora Dobos, Thomas Vecchiato +2
Google Zurich, Switzerland · Technical University of Munich Munich, Germany · University of Copenhagen Copenhagen, Denmark +1
Large-scale Nearest Neighbor (NN) search, though widely utilized in the similarity search field, remains challenged by the computational limitations inherent in processing large scale data. In an effort to decrease the computational expense needed, Approximate Nearest Neighbor (ANN) search is often used in applications that do not require the exact similarity search, but instead can rely on an approximation. Product Quantization (PQ) is a memory-efficient ANN effective for clustering all sizes of datasets. Clustering large-scale, high dimensional data requires a heavy computational expense, in both memory-cost and execution time. This work focuses on a unique way to divide and conquer the large scale data in Python using PQ, Inverted Indexing and Dask, combining the results without compromising the accuracy and reducing computational requirements to the level required when using medium-scale data.
Ashley N. Abraham, Andrew Strelzoff, Haley R. Dozier +2
Information Technology Laboratory, U.S Army Engineer Research and Development Center, Vicksburg, MS, USA · Environmental Laboratory, U.S Army Engineer Research and Development Center,2026 Vicksburg, MS, USA