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

Xingqiao Wang; Zi Wang; Xiaowei Xu

Source-linked AI summary

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

Xingqiao Wang, Zi Wang, Xiaowei Xu

arXiv:2608.15438v1Aug 15, 2026cs.DBcs.IRcs.LG

TL;DR

Billion-scale ANN indexing remains costly because global clustering and graph construction burden construction time and resources. NeuRoute uses logit-guided neural hashing with bucket-local clustering and adaptive centroid routing, achieving 90.3% Recall@10 at 2,414 QPS on BigANN-1B and sub-hour builds.

Problem
Billion-scale ANN indexes face substantial construction, tuning, memory, and preprocessing costs under single-node resource budgets.
Method
NeuRoute learns short balanced binary codes and combines logit-guided bucket probing with bucket-local clustering, centroid gating, and early stopping.
Results
90.3% Recall@10 at 2,414 QPS on BigANN-1B, with sub-hour end-to-end builds on BigANN-1B and Deep1B-1B.
Takeaways & Limitations
NeuRoute makes short-code hashing a competitive lightweight routing framework for billion-scale ANN search with strong accuracy–throughput trade-offs and fast rebuilding.
Takeaways & Limitations
The reported CAGRA GPU baseline is limited by A100 40GB device memory and cannot be compared in the main 100M/1B evaluations.

Abstract

from arXiv · show

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.

1 Introduction

NeuRoute presents short, well-balanced binary codes as a lightweight neural routing mechanism for billion-scale ANN search under strict scan budgets. It combines logit-guided probing, bucket-local centroid filtering, and budget-controlled early stopping, enabling sub-hour end-to-end index rebuilding on 1B-scale benchmarks.

Logit-guided routing: NeuRoute uses encoder-logit deviation-to-threshold scores to prioritize uncertain-bit perturbations for query-adaptive multi-bucket probing.The logits preserve uncertainty information discarded by many binarization pipelines, improving control over where scanning computation is spent.
Construction efficiency: 380 s on BigANN-1B and 614 s on Deep1B-1B are reported for bucket-local clustering during Add/Build.The clustering completes in minutes as part of index construction.
Query-time efficiency: Up to 4.57× higher end-to-end throughput and up to 4.68× fewer refinement candidates are achieved at matched Recall@10.NeuRoute combines calibrated centroid-stage gating with heap-quality-driven early stopping to prune low-value clusters.
Bucket-local clustering: Bucket-local clustering in the learned low-dimensional space provides centroids for compact candidate-cluster generation and centroid-stage filtering.Centroids are ranked by distance to the query before exact scoring is reserved for final top-k refinement.
Billion-scale evaluation: NeuRoute evaluates BigANN-1B and Deep1B-1B, reporting strong Recall@10–throughput trade-offs and sub-hour end-to-end rebuilds on a single node.The end-to-end rebuild includes training plus Add/Build.

2 Related Work

Related work spans clustering-, quantization-, graph-, and hashing-based ANN indexes, each addressing large-scale similarity search but facing persistent build-cost, footprint, or scalability challenges. NeuRoute is positioned as a lightweight learned-hashing approach for billion-scale routing, avoiding complex graph maintenance and global coarse clustering.

ANN indexing paradigms: ANN systems use clustering-, quantization-, graph-, and hashing-based indexing paradigms, but production challenges include high build cost, large footprints, and limited scalability.These paradigms support similarity search across recommendation, multimedia retrieval, biological, and language-modeling applications.
Quantization and IVF-based indexes: FAISS IVF–PQ and IVF–OPQ combine inverted-file partitioning with product quantization, while OPQ learns rotations to reduce quantization distortion at fixed code size.These indexes support SIMD-optimized kernels, runtime tuning such as nprobe, and lookup-table–based asymmetric distance computation.
Graph-based ANN: Graph-based ANN methods such as HNSW use hierarchical routing and small-world connectivity, while DiskANN and SPANN target billion-scale deployment with disk-backed hybrids.Other graph families include Voronoi-style routing structures and degree-reduced traversable graphs designed to reduce traversal cost while maintaining navigability.
Hashing and binary-code retrieval: Hashing methods map vectors to compact binary codes for fast Hamming-space filtering and low-memory indexing, spanning classical LSH, data-dependent hashing, and learned neural encoders.Spectral Hashing and ITQ align codes more closely with local neighborhoods than random projections, whereas FAISS IndexLSH provides training-free SimHash with exact reranking.
Position of NeuRoute: NeuRoute is most closely related to learned hashing and discrete representations, using lightweight training for binary-code routing while reducing dependence on graph maintenance, storage/I/O tuning, and global coarse clustering.Its positioning emphasizes billion-scale routing, Hamming-space navigation, and efficient candidate generation.

3 Methodology · 3.1 Problem Definition · 3.2 Hash Function

NeuRoute defines ANN retrieval around a learned low-dimensional encoder whose selectively preserved neighborhood structure is binarized into balanced addresses. Its routing pipeline combines logit-guided bucket probing, local centroid filtering, exact refinement, and early stopping for efficient large-scale search.

3 Methodology: NeuRoute’s methodology covers ANN problem definition, learnable hashing, bucketized index construction, retrieval, and time-complexity analysis.The framework is organized around a learnable hash function and an index construction and retrieval mechanism.
3.1 Problem Definition: Given embeddings xi, query q, and Euclidean distance d(u, v) = ∥u −v∥2, ANN search retrieves a subset approximating the true nearest neighbors.The inputs lie in a high-dimensional embedding space of dimension Edim.
3.1 Problem Definition: Short binary codes enable fast multi-bucket probing, centroid-based cluster filtering, and exact refinement in the original embedding space.NeuRoute learns encoder logits that approximately preserve local neighborhood structure for routing-based retrieval.
3.1 Problem Definition: Median thresholding produces balanced binary addresses, while bucket-local latent-space clustering and separate original embeddings support routing followed by exact refinement.At query time, candidate buckets are enumerated around the base address using a logit-guided procedure.
3.1 Problem Definition: NeuRoute’s interleaved routing–refinement pipeline bounds candidate sets and supports early termination when further improvements cease.The pipeline targets a trade-off among retrieval speed, memory efficiency, and search accuracy.
3.2 Hash Function: The hash function maps high-dimensional embeddings to low-dimensional latent representations and then binarizes them into discrete Hamming-space addresses.The encoder compresses inputs while preserving salient similarity information.
3.2 Hash Function: NeuRoute trains with a selective similarity-preservation loss that focuses latent-space consistency on informative nearby pairs rather than the complete global similarity structure.The mask selects the most similar ∼0.5% of pairs, concentrating capacity on relationships that directly determine recall.
3.2 Hash Function: On-the-fly within-batch masking and thresholds eliminate expensive pair-list, hard-negative, and offline-neighbor-graph preparation.This reduces preprocessing overhead and supports the ∼1-hour end-to-end indexing workflow.

3.3 Index Construction · 3.4 Retrieval Process · 3.5 System Complexity and Scalability Analysis

NeuRoute constructs indexes by hashing embeddings into compact binary buckets and clustering each bucket locally in a low-dimensional latent space. Retrieval then uses budgeted bucket enumeration, calibrated centroid gating, and heap-quality-driven early stopping to control exact-refinement work, with costs governed by adaptive query budgets and latent-space processing.

3.3 Index Construction: NeuRoute maps embeddings into compact latent vectors, binarizes them into short addresses, and uses those addresses for bucketized indexing.The encoder produces ℓ = E(X), which is binarized into addresses A for bucket assignment.
3.3 Index Construction: Each vector is appended to the posting list selected by its binary address, while original embeddings remain available for exact top-k refinement.Only non-empty buckets are retained in the directory.
3.3 Index Construction: NeuRoute clusters vectors independently within each non-empty bucket in latent space using bucket-size-aware capacities, sampled k-means initialization, and limited Lloyd refinement.Very small buckets become single clusters, while medium and large buckets use different target capacities.
3.4 Retrieval Process: Calibration uses higher-recall held-out-query runs to supervise bucket-score cutoffs and data-driven centroid-gating margins that preserve top-K coverage while bounding enumeration cost.The margin curve is estimated from query-wise centroid distances and required additional margins, using high quantiles and monotone smoothing.
3.4.1 Bucket Enumeration (Step 4): Bucket enumeration ranks nearby binary addresses around the query hash using bounded exploration and priority bins, enabling termination when further enumeration no longer improves retained candidates.The enumerator derives the base address from query logits and thresholds, then uses deviation-to-threshold scores to prioritize bit selections.
3.4.2 Centroid-Stage Selection with Calibrated Gating and Early Stop (Step 5): Centroid-stage selection evaluates bucket-local centroids with a bounded top-Kc heap and calibrated gate θ = dmin + M(dmin), activating early stopping only after heap and bin-count conditions are met.Singleton buckets bypass centroid selection; retained clusters proceed to candidate formation before exact scoring.
3.5 System Complexity and Scalability Analysis: Hash bucket assignment is linear in database size N, while bucket-local clustering is cheaper in latent dimension Ldim and depends on bucket sizes, cluster budgets, and iteration counts.The complexity discussion is stage-level rather than a tight worst-case bound because runtime follows adaptive budgets.
3.5 System Complexity and Scalability Analysis: NeuRoute combines bucket enumeration, centroid-stage pruning, and early stopping to provide controllable per-query budgets before exact refinement.The dominant query costs are approximately O(Cq · Ldim) for centroid scoring and O(Rq · Edim) for refinement, where Cq and Rq are adaptively determined.

4 Experiment

NeuRoute is evaluated under practical vector-search conditions spanning high-dimensional multi-million-scale data and billion-scale benchmarks. The experiments measure Recall@10 against query throughput and candidate-processing cost using consistent single-node protocols.

Benchmarks: The evaluation covers GLDv2 with 1536D embeddings and billion-scale BigANN-1B and Deep1B-1B datasets.GLDv2 tests high-dimensional robustness, while BigANN-1B and Deep1B-1B use 128-D and 96-D vectors, respectively, with 1B entries.
Baselines: Baseline comparisons sweep one primary query-time knob per index family, including nprobe, efSearch, search depth L, and a 22-bit hashing probing budget.The evaluation selects reproducible methods feasible on a single node up to 1B scale.
Evaluation metrics: Recall@10 is evaluated against queries per second and average candidates per query to expose quality–throughput and refinement-cost trade-offs.Average candidates counts database vectors receiving exact distance computations during refinement.
Experimental setup: Experiments use Euclidean distance with k=10 on large corpora under strict runtime budgets in a single-node setup.The host includes 64 physical CPU cores, 1007 GiB RAM, and one NVIDIA A100 GPU; the GPU is used only to train learned hashing models.
Benchmarks: The broader benchmark suite also includes BigANN-100M, Deep1B-100M, and GLDv2 with 10M 1536-dimensional vectors.Unless otherwise stated, each dataset uses 10,000 queries in the same batched evaluation setting.

5 Results and Discussion

NeuRoute is evaluated under Euclidean distance using Recall@10, QPS, search effort, and end-to-end index build cost. It delivers sub-hour billion-scale construction while reaching a competitive serving point near 90% Recall@10 on BigANN-1B.

Build-time advantage: 0.82 h and 0.93 h are NeuRoute’s end-to-end build times on BigANN-1B and Deep1B-1B, respectively.These times include training and index construction.
Retrieval quality and throughput: 90.3% Recall@10 at 2,414 QPS is NeuRoute’s BigANN-1B serving point, compared with DiskANN’s 90.4% at 2,744 QPS.The comparison is presented as a competitive serving point near 90% Recall@10.
Build-time advantage: 0.75 h is NeuRoute’s GLDv2 build time under the same 2M-vector training budget, including the 1536D dataset.The matched 2M training budget applies across trainable methods for GLDv2.
Build-time decomposition: Refinement-cache construction and bucket-local clustering account for roughly 40–69% of Add/Build across datasets, while calibration/evaluation is lightweight.Add/Build also includes full-base encoding, CSR construction, and residual I/O.

6 Retrieval Results

NeuRoute delivers competitive mid-to-high recall with fast construction across 100M- and billion-scale datasets, including high-dimensional GLDv2. At approximately 90% recall on BigANN-1B and Deep1B-1B, it matches strong baselines’ throughput while substantially reducing build time.

100M-scale results: 88.6% Recall@10 is achieved at 7,565 QPS on BigANN-100M and 2,559 QPS on Deep1B-100M, with 0.39-hour end-to-end builds on both datasets.NeuRoute extends to 95.9% recall at 2,665 QPS on BigANN-100M and 94.0% at 1,054 QPS on Deep1B-100M.
High-dimensional GLDv2: 72.4% Recall@10 at 4,251 QPS and 88.1% at 814 QPS demonstrate usable performance on 1536D GLDv2, with a 0.75-hour end-to-end build.Pushing recall to 92.7% yields 425 QPS, while graph-based baselines reach higher near-saturated recall.
Billion-scale comparisons: 90.3% recall at 2,414 QPS on BigANN-1B is comparable to DiskANN’s 90.4% at 2,744 QPS and faster than OPQ+IVF-PQ (refine) at 90.8% and 1,406 QPS.IVF-PQ tops out at 63.9% recall in the reported BigANN-1B sweep.
Billion-scale comparisons: 90.1% Recall@10 at 842 QPS on Deep1B-1B is achieved with a 0.93-hour build, versus DiskANN’s 88.9% at 915 QPS and 36.47-hour build.OPQ+IVF-PQ (refine) reaches 91.2% recall at 3,342 QPS and extends to 99.4% recall at 248 QPS.
Ablations: 1.5×–1.7× QPS improvements from centroid-stage early stopping reduce refinement candidates by ∼16–19% with a Recall@10 drop below 10−3.Bucket-local clustering improves Deep1B-1B throughput by 4.57× and reduces candidates/query by 3.86×, with a +0.14-point Recall@10 gain.

7 Conclusion

NeuRoute is an encoder-based hashing framework that combines compact binary codes, logit-guided routing, calibrated gating, and heap-quality-driven early stopping for scalable billion-scale vector search. It achieves 90%+ Recall@10 with sub-hour end-to-end builds, while leaving room for quantization extensions and production hardening.

Conclusion: NeuRoute combines compact binary codes with logit-guided routing, calibrated gating, and heap-quality-driven early stopping for scalable k-nearest-neighbor search.The framework targets fast, memory-efficient candidate generation in large vector databases.
Conclusion: 90%+ Recall@10 is achieved on 1B-vector benchmarks while enabling sub-hour end-to-end builds.
Future work: PQ-based reranking is an orthogonal extension that may further improve the tradeoff curve.Future work will study additional quantization variants, including OPQ+PQ, within the same refinement interface.
Future work: The authors plan to harden NeuRoute for production deployment, with implementation and evaluation artifacts publicly available for reproducibility.

A NeuRoute model configurations

NeuRoute uses lightweight MLP encoders that compress input embeddings into compact latent logit vectors for binarization and routing. The architecture combines Linear–BatchNorm–ReLU hidden layers with a final linear layer that preserves latent logits.

Encoder architecture: NeuRoute progressively compresses input embeddings from E_dim to compact latent logit vectors of dimension L_dim.These logits support binary-code generation and routing.
Encoder architecture: Each hidden layer applies Linear, BatchNorm, and ReLU operations.This configuration is used across the encoder instantiations evaluated in the paper.
Encoder architecture: The final encoder layer is linear without BatchNorm or activation to preserve latent logits for binarization and routing.The linear output retains the logits used by NeuRoute’s downstream hashing and routing procedures.

B Training stability and convergence

NeuRoute exhibits consistent convergence across evaluated datasets: loss drops rapidly early in training and then stabilizes under the fixed default schedule. The same schedule is used throughout for simplicity and reproducibility.

Training protocol: Under the default protocol, NeuRoute trains for 500 epochs on a 2M training subset with batch size 4096.The protocol is applied across all evaluated datasets.
Convergence: Across datasets, training and validation loss decrease rapidly during early epochs before stabilizing.This pattern indicates consistent convergence behavior under the fixed schedule.
Training protocol: All experiments use the fixed training schedule to simplify execution and improve reproducibility.

C Empirical evidence for logit-guided bucket routing

NeuRoute uses pre-binarization logit margins to prioritize query-adaptive bucket probing under fixed codes and a limited budget. Evidence links its routing signals to neighbor distance, Hamming proximity, low-margin bit flips, and budget-controlled retrieval with lightweight index construction.

The proposed bucket score correlates with KNN distance, with lower scores tending to identify buckets containing closer ground-truth neighbors.This supports ranking buckets by the L1_sum score during probing.
Useful candidates concentrate at small Hamming distances, motivating prioritized multi-bucket enumeration under a fixed probing budget.
KNN ground-truth bit flips concentrate on low-margin, uncertain bits, validating margin-ranked bit flipping for bucket routing.Margin rank 0 denotes the smallest margin and least-confident bit.
At operating points with Recall@10 closest to 0.90, NeuRoute decomposes query work into bucket enumeration, routing, refinement, total time, throughput, recall, and refined candidates per query.The breakdown is reported per dataset, alongside an end-to-end build-time comparison across ANN index families.

E GPU-only reference (CAGRA)

CAGRA serves as a GPU-only throughput reference, but GPU memory limits construction to 80M vectors on an A100 40GB. At 80M, it delivers very high throughput with strong recall on both BigANN and Deep1B.

Scaling constraint: CAGRA construction is limited to 80M vectors on an A100 40GB, excluding it from the main 100M/1B-scale Recall@10–QPS comparisons.The limitation is attributed to GPU memory.
Throughput reference: 0.918 Recall@10 at ∼1.13 × 10^6 QPS is achieved on Deep1B-80M.The result likewise shows strong recall and throughput under sufficient device memory.