NeuRoute: Logit-Guided Neural Routing for Billion-Scale Vector Search with Sub-Hour Index Construction

Xingqiao Wang; Zi Wang; Xiaowei Xu

cs.DBAug 15, 2026

NeuRoute: Logit-Guided Neural Routing for Billion-Scale Vector Search with Sub-Hour Index Construction

Authors: Xingqiao Wang, Zi Wang, Xiaowei Xu

Organizations: University of Arkansas at Little Rock

Abstract

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\times$ 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/

10^{9}

) 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 (

n_{q}{=}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 (

n_{q}=10{,}000

$\tau_{\text{emb}}$ (%)	Base-sampled pairs		Encoded-sampled pairs
$\tau_{\text{emb}}$ (%)	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

\tau_{\text{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 (

n_{q}{=}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

Approximate nearest neighbor search finds close vectors without exhaustive comparisons, enabling scalable retrieval in high-dimensional datasets.

See all 43 papers

Panorama: Fast-Track Nearest Neighbors
Oct 1, 2025Vansh Ramani, Alexis Schlomer, Akash Nayar +3Product Quantization Approximate Nearest Neighbor Search
IIT Delhi & CMU & UCPH · Carnegie Mellon University · Indian Institute of Technology Delhi +1
RSLM: Training-Free Vector Quantization for Approximate Nearest Neighbor Search
Aug 31, 2026Rastislav Lenhardt, Teodora Dobos, Thomas Vecchiato +2Rotation-Based Quantization Vector Quantization
Google Zurich, Switzerland · Technical University of Munich Munich, Germany · University of Copenhagen Copenhagen, Denmark +1
Large-Scale Data Parallelization of Product Quantization and Inverted Indexing Using Dask
Apr 23, 2026Ashley N. Abraham, Andrew Strelzoff, Haley R. Dozier +2Information Retrieval Product Quantization
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

Oct 1, 2025J/K move · Enter open · S save

Panorama: Fast-Track Nearest Neighbors

Vansh Ramani, Alexis Schlomer, Akash Nayar, Sayan Ranu+2

IIT Delhi & CMU & UCPH · Carnegie Mellon University · Indian Institute of Technology Delhi+1

Product Quantization Approximate Nearest Neighbor Search

Open paper AskPDF arXiv

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.

Abstract

Approximate Nearest Neighbor Search

Explore similar work

Panorama: Fast-Track Nearest Neighbors

RSLM: Training-Free Vector Quantization for Approximate Nearest Neighbor Search

Large-Scale Data Parallelization of Product Quantization and Inverted Indexing Using Dask