acceptodds
Under review as a conference paper at ICLR 2027

You Don’t Have to Go the Distance

52 views

Abstract

Neural models use large external memories accessed through learned representations. The cost of inference depends on the length of search for each query. Average recall gives equal weight to all recovered neighbors, while their recovery requires significantly different amounts of computation. We propose a learned search policy, TraCANN, that takes advantage of this asymmetry to reallocate the computation under a shared recall target. TraCANN's training trajectories provide the costs and neighbor recovery statistics used to fit continuation actions jointly, and it selects an action based on one policy evaluation from each query's early search progress. By learning the relative costs of recovery, TraCANN can stop promising searches before exhausting their candidate sets. Compared to eleven baselines, TraCANN's throughput is the highest at all evaluated recall thresholds on four standard ANN benchmarks. Our analysis demonstrates cases when such reallocations reduce computation and bounds the difference between discrete and fractional continuation assignments.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Approximate Nearest Neighbor Search, Similarity Search, Adaptive Precision, Efficient Search

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_v3iSOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper presents TraCANN, a learned adaptive search termination framework for approximate nearest neighbor (ANN) search on proximity graphs. The authors observe that recovering neighbors across different queries exhibits significant cost asymmetries under an aggregate recall target. To exploit this, TraCANN collects early search progress features after a fixed prefix (32 distinct visits) and employs a compact decision tree to dynamically predict both frontier capacity and a total visit budget (w,b)(w, b). The policy optimization is formulated as minimizing total search cost subject to an aggregate miss budget, solved via dynamic programming. The framework is implemented on top of the state of the art RaBitQ/SymphonyQG infrastructure with SIMD acceleration. Extensive benchmarks across four datasets and 11 baselines demonstrate throughput improvements of 1.6x to 2.7x over the strongest competitors at 99% Recall@10.

Critical strengths
  1. Clean and honest core insight: The central premise is grounded and straightforward. The authors recognize that not all queries cost the same to reach a target recall, and they formulate the early termination problem as an explicit resource allocation trade-off across queries without burying the mechanics in overblown theoretical rhetoric.

  2. Rigorous and extensive empirical validation: The experimental evaluation is comprehensive. Benchmarking across 11 competitive baselines under single core and 8 core environments with rigorous warmup and pinning protocols provides solid empirical proof.

  3. Pragmatic systems integration: Building directly on modern graph quantization kernels (RaBitQ and SymphonyQG) ensures that throughput gains are practical wall clock improvements rather than theoretical reductions in simulated distance metrics.

Critical weaknesses
  1. Inaccessible context and positioning for general readers: The paper plunges into traversal mechanics and action spaces assuming deep institutional familiarity with graph-based vector search pipelines. Even for readers with experience in indexing and modern quantization methods like RaBitQ, identifying exactly which component of the standard ANN execution flow is being modified requires multiple passes.

To be honest, it took me a good cup of coffee and a careful re-read to pinpoint exactly which knob in the ANN pipeline the authors are turning here. At first glance, the paper is thick with indexing jargon that might easily lose non-ANN readers. But once you clear the smoke, the core idea is surprisingly neat: instead of forcing every single query to blindly grind through a fixed search budget or frontier width on the proximity graph, the authors essentially let the query 'test the waters' for the first 32 visits, read the local terrain, and then make a fast, learned call via a tiny decision tree on how much further it is actually worth exploring—trading cheap gains on easy queries for hard ones under an aggregate recall target. It is a very clever dynamic resource-allocation trick on top of modern graph quantization (like RaBitQ), and far more nontrivial than it initially appears

As a personal suggestion, I think Section 1 and Section 3 need a clearer high level diagram or schematic contrasting standard fixed-budget graph traversal against this two stage early-decision setup to prevent general ML audiences from getting lost in index specific jargon.

Questions for authors

Curiosity point: The evaluation relies on fixed-length SIMD operations tailored to CPU instructions (AVX-512 VNNI) inside RaBitQ's execution framework. If one wanted to port this dynamic continuation framework to hardware paradigms like GPUs with warp level divergence constraints, or architectures featuring vector length agnostic execution (such as RISC-V Vector extensions, RVV), what bottlenecks or architectural pitfalls would arise from query level early termination and dynamic frontier sizing? This is posed purely out of architectural curiosity and does not impact my evaluation of the paper's core contributions.

2 comments
AuthorsOpenReview ↗

Response to Reviewer v3iS (1/2): Presentation Revisions and the New Schematic Figure

Thank you very much for your encouraging review and thoughtful feedback. We really appreciate your recognition of the corpus-level resource-allocation view, the wall-clock evaluations on one and eight CPU cores, and our integration into a modern SIMD-accelerated search engine. Your suggestion to make the paper easier to approach for a broad machine learning readership and to add a direct visual comparison of fixed versus learned allocation made the manuscript much clearer. We feel very fortunate to have the opportunity to exchange ideas with an expert like you through ICLR and to receive such valuable advice.

Revisions for a Broad ML Readership

We revised the abstract, Section 1, and Section 3 so readers outside specialized vector-indexing systems can follow the problem setup and algorithm without extra systems background. Section 1 now motivates cross-query reallocation with a concrete trade-off. If skipping 400 tail visits that would recover one true neighbor on a first query allows 50 visits on a second query to recover two true neighbors, the search spends 350 fewer visits overall for a net gain of one retrieved neighbor. Together with Figure 1 (page 2), which summarizes the online continuation workflow and offline dynamic programming pipeline, Section 3 introduces the shared 32-visit prefix, tree partitioning, and leaf-level width and visit assignment step by step before any low-level kernel details appear.

What Readers Now See in Figure 2

Thanks to your suggestion, Figure 2 (Section 3.1, page 4, also cited in Section 1) gives readers an immediate side-by-side schematic of uniform and learned stopping locations. On the left, two queries start from the same graph entry vertex under a shared frontier width so the stopping rule stands out cleanly. Diamond markers indicate an illustrative fixed limit of 64 visits, and ring markers indicate the learned stopping points, with one query returning at visit 32 and the other continuing past the 64-visit mark. On the right, an accompanying histogram plots the assigned visit budgets for all 475 active SIFT1M training queries assigned width 64 by our 99% Recall@10 policy, showing directly that 152 of them receive b=32b = 32 and return right after the shared prefix.

AuthorsOpenReview ↗

Response to Reviewer v3iS (2/2): Prospective Design Choices for GPU and RISC-V Vector Targets

Thank you as well for asking how query-adaptive frontier widths and visit limits would map onto SIMT GPUs (where lanes in a hardware warp execute instructions in lockstep) and vector-length-agnostic RISC-V (RVV) processors. Your question sparked a really interesting line of thought for us. On a CPU thread, stopping a query early simply frees that core to start the next query, whereas on a GPU a stopping decision that saves work for one query can directly affect how much useful work neighboring lanes get to do unless threads are grouped carefully.

Mapping Adaptive (w,b)(w, b) Execution to SIMT GPUs

Placing a separate query on each SIMT lane would leave lanes idle whenever queries in the same warp choose different visit limits bb. GPU proximity-graph engines such as CAGRA in Ootomo et al. (ICDE 2024) instead assign a cooperative warp or thread block to a single query, parallelizing candidate scoring and coordinate reductions across lanes. Under a warp-per-query layout, halting at a query's assigned bb would be uniform across the entire warp and avoid intra-warp branch divergence. Long continuations could still create batch stragglers, so a GPU port could either refill finished warps dynamically from a work queue or, in large batches, group queries with similar assigned budgets after visit 32 while keeping each query's active frontier, visited filter, and top results in place.

Variable frontier capacity ww affects on-chip memory pressure because GPU graph search stores candidate queues in shared memory or registers, where larger allocations lower streaming multiprocessor occupancy. Bucketing continuations into a few width tiers compiled for matching scratchpad sizes would keep occupancy predictable. Recent GPU graph-search systems such as Jasper in McCoy et al. (PVLDB 2026) and FlowANN in Zhao et al. (OSDI 2026) also show that GPU wall-clock time depends heavily on hiding irregular dependent graph loads and scheduling warps across batches. An offline GPU calibration pass would re-record action times ti(w,b)t_i(w, b) on the target device and validate the dynamic programming policy at the intended serving batch size, where group scheduling directly governs wall time.

Mapping to Vector-Length-Agnostic RISC-V (RVV)

On an RVV processor, a thread would run decision-tree comparisons and priority-queue management on the scalar unit while vectorizing inner distance calculations across coordinates or neighbor blocks, keeping a query's frontier width ww independent of hardware vector register length. Under the strip-mining model of the RISC-V Vector Extension specification, each iteration requests the remaining element count via vsetvli and advances pointers by the hardware-returned vl, handling arbitrary register widths and short tails without assuming a fixed 512-bit register width. For SIFT1M's full-vector byte distances, widening integer instructions would preserve mixed unsigned-signed byte products without overflow. As shown on Ara2 by Perotti et al. (IEEE TC 2024), short vector loops can expose scalar instruction-issue overhead, and irregular graph fetches remain a separate memory-layout consideration.

Reviewer_PoSAOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper proposes TraCANN, a learned rule for deciding how much work a graph-based nearest-neighbor search should do for each query. After a short initial search, a small decision tree reads features of the search progress and picks how many candidates to keep and how many more vertices to visit. The tree is trained on search trajectories from training queries, and its actions are chosen to minimize search time while keeping average recall above a target. On four standard benchmarks, TraCANN reports substantially higher throughput than the best of baselines at 99% recall on one and many cores.

Critical strengths
  1. The speedups are large and consistent across datasets.
  2. The core idea is simple and useful.
Critical weaknesses
  1. It is unclear how much of the speedup comes from the learned policy. TraCANN runs on its own search code, and the paper never compares it with the same code using one fixed width and budget without learning. This might explain part of the gain, so this comparison is needed to support the main claim.
Questions for authors

None

1 comment
AuthorsOpenReview ↗

Response to Reviewer PoSA

Thank you very much for your warm assessment of our paper and for appreciating how a simple continuation rule delivers consistent gains across benchmarks and core counts. We were especially grateful for your suggestion to compare fixed and learned continuation on the same search engine, an insightful test that shows what adaptive budget allocation contributes in its own right. We added that controlled comparison in Table 2 of the revised manuscript.

Fixed Versus Learned Continuation on the Same Engine

Table 2 (Section 4.2) reports this controlled comparison on SIFT1M at single-core 99% Recall@10. Both configurations run on the same C++ search engine, sharing the proximity graph, quantized neighbor screening, memory layout, and the SIFT AVX-512 VNNI distance kernel.

  • Fixed (w,b)(w, b) continuation on the same backend reaches 12,604 QPS at 99.017% Recall@10.
  • TraCANN learned (w,b)(w, b) continuation on the same backend reaches 16,369 QPS at 99.125% Recall@10, a 1.30× speedup (+29.9% QPS with +0.108 percentage points higher recall).

This 1.30× improvement comes directly from replacing one global (w,b)(w, b) setting with TraCANN's learned 32-visit decision tree on the same engine, whereas Table 3's 1.60× SIFT1M figure compares TraCANN against external SymphonyQG (10,236 QPS).

Why Cross-Query Allocation Improves a Fast Backend

Even on a well-tuned traversal engine, one uniform (w,b)(w, b) pair has to apply the same stopping budget across queries whose remaining neighbors differ sharply in recovery cost. Adaptive HNSW heuristics such as Zhang and Miller (SIGMOD 2026) adjust a single coupled ef parameter per query, whereas TraCANN selects frontier width and total visit limit under an aggregate recall budget and continues directly from the 32-visit state after at most 14 scalar comparisons for an active query. Shortening a query whose next neighbor would take many visits to find frees budget to continue another query where extra visits cheaply recover additional neighbors. On SIFT1M at 99% recall, 12.9% of test queries finish by visit 32 (including early frontier exhaustion and b = 32 assignments) and the median query evaluates 76 full-vector distances.

Reviewer_Z4wsOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper designs a new approximate nearest neighbor search algorithm. It is based on HNSW approach. The new trick is to learn how to adjust the search for a specific query, making it a query-adaptive algorithm.

To do so, the training algorithm takes in a query sample. After 32 steps, properties of the search so far are encoded in "query features". These are used to guide the rest of the search (at inference). The problem is as a joint optimization problem: given a fixed budget of recall, minimize the expected query time. Note that it quantities are average over all queries: hence, on a hard query, the algorithm may bail out early in exchange for better accuracy on an easier query.

The authors runs extensive experiments on a number of benchmarks, against a number of SOTA algorithms. They obtain 1.6x or more speedup (single thread, on SIFT1M like datasets).

Critical strengths
  • The top-line improvement is solid and credible. The experiments give good evidence for the efficiency of the designed algorithm.
  • the formulation of the problem is interesting and novel (to the best of my knowledge), leading to concrete algorithmic questions, that the authors address (combination of greedy and dynamic programming).
Critical weaknesses

The main weakness is that it is not immediately clear that the improvement comes precisely from the special query-adaptive part (as opposed to other algorithm implementation details, like using AVX-512 VNNI dot products). Since this is the central innovation, it would be great to see ablations isolating which parts are most important to the reported improvement.

Minor:

  • the query features are designed and feel a bit ad hoc.
Questions for authors
2 comments
AuthorsOpenReview ↗

Response to Reviewer Z4ws (1/2): Policy Attribution and Prefix Feature Signals

Thank you so much for your generous review and for recognizing the novelty of optimizing over average recall, the decision tree and dynamic programming algorithm that follows from it, and the strength of our experimental evidence. It is a real pleasure to discuss these design questions with someone who shares our interest in how adaptive graph search actually behaves. Your questions also led us to report the controlled policy comparison in Table 2 and the offline costs in Table 14 of the revised paper, and we really appreciate how much clearer those additions make our evaluation.

Same-Backend Comparison Against Fixed Continuation

Table 2 (Section 4.2) compares a single fixed (w,b)(w, b) continuation against TraCANN's learned (w,b)(w, b) policy on the same C++ graph-search engine on SIFT1M at single-core 99% Recall@10. Both runs share the proximity graph, quantized neighbor screening, memory layout, and the SIFT AVX-512 VNNI distance kernel. Fixed continuation reaches 12,604 QPS at 99.017% Recall@10, and TraCANN's learned policy reaches 16,369 QPS at 99.125% Recall@10, giving a 1.30× throughput gain (+29.9% QPS and +0.108 percentage points higher recall) from adaptive allocation on the same codebase. Table 3's 1.60× ratio on SIFT1M compares TraCANN against external SymphonyQG (10,236 QPS). Signed-byte VNNI arithmetic is used only on SIFT1M (Appendix C.10). DEEP-1M, GIST1M, and GloVe100 compute standard FP32 full-vector distances, and TraCANN reaches 1.72×, 2.30×, and 2.72× single-core throughput over the fastest qualifying external baselines at 99% recall in Table 3. Within proximity-graph traversal, Lu et al. (ICML 2024) show how per-neighbor probabilistic filtering reduces individual edge-evaluation work, and holding our inner-loop screening and distance kernels fixed in Table 2 verifies the throughput gain from cross-query budget allocation itself.

Prefix Features and Data-Driven Tree Splits

After visit 32, an active query computes 20 inexpensive prefix statistics from the visited candidates, priority queue, and precomputed per-vertex neighborhood scales (Appendix A, Table 6, and Appendix C.8). These statistics describe local geometry through scale-free distance ratios, comparisons against outgoing neighbor spacing, and log-ratio summaries based on Levina and Bickel (NeurIPS 2004) that reflect the spacing of the closest visited vectors around the query. They also track recent progress since visits 16 and 24 alongside remaining frontier competitiveness. In recent work on learned query-cost estimation, Wang et al. (PVLDB 2026) likewise find that early traversal distance profiles and local graph spacing predict downstream graph search cost well.

During offline training, greedy splitting chooses candidate thresholds directly by how much assigning separate continuations to the child groups reduces measured search time plus a miss penalty (Section 3.3). Different vector modalities naturally select different signals. In the fitted 99% Recall@10 trees, SIFT1M splits first by comparing the tenth-closest squared distance at visit 16 against visit 32, and DEEP-1M splits first by comparing the next unprocessed frontier score with the current tenth-closest squared distance. Dynamic programming then assigns one (w,b)(w, b) pair per leaf under a shared corpus miss budget, so an active query selects its continuation in at most 14 scalar threshold comparisons at serving time.

AuthorsOpenReview ↗

Response to Reviewer Z4ws (2/2): Offline Resource Footprint and Adaptive Baselines

Offline Index Build, Policy Fitting, and Peak Training Memory

Table 14 (Appendix F.1) reports offline graph construction time in seconds, complete policy preparation and fitting time in seconds (covering trajectory collection, tree construction, dense refinement, and dynamic programming), and peak training resident memory (RSS) in GiB for the 99% Recall@10 policies.

  • SIFT1M takes 52.84 s for index build, 271.46 s for policy fit, and 2.684 GiB peak training RSS.
  • DEEP-1M takes 198.63 s for index build, 386.27 s for policy fit, and 4.287 GiB peak training RSS.
  • GIST1M takes 632.47 s for index build, 894.73 s for policy fit, and 12.731 GiB peak training RSS.
  • GloVe100 takes 186.91 s for index build, 1,426.58 s for policy fit, and 3.742 GiB peak training RSS.

Evaluating thousands of candidate actions remains fast offline because Lemma 1 lets a single continuation run per candidate width record elapsed time and neighbor hits across all stopping budgets (Appendix B.1). Online serving adds only 11.35 to 16.00 KiB for the decision tree and 3.81 to 4.51 MiB for precomputed FP32 local scales (Table 13).

Comparison with AdaptNN and Ada-ef

Both adaptive methods you mentioned are evaluated in our experiments at matched single-core 99% Recall@10 targets, showing end-to-end serving throughput alongside Table 2's same-code SIFT1M control.

  • AdaptNN (Li et al., SIGMOD 2020) observes query coordinates, candidate distances, and progress at an HNSW checkpoint and uses gradient-boosted trees to predict a distance-evaluation count for each query. In Table 3, AdaptNN achieves 674 QPS on SIFT1M and 223 QPS on DEEP-1M, and TraCANN achieves 16,369 QPS and 12,056 QPS (AdaptNN did not reach the 99% target on GIST1M or GloVe100 within our parameter sweeps in Appendix D.4).
  • Ada-ef (Zhang and Miller, SIGMOD 2026) estimates the query-to-database similarity distribution to pick a query-specific HNSW exploration factor ef. On unit-normalized GloVe100 at 99% recall (Table 2), Ada-ef reaches 414 QPS at 99.025% recall, and TraCANN reaches 1,846 QPS at 99.008% recall, a 4.46× speedup.

Alongside our SymphonyQG/RaBitQ-Library quantized-edge backend, two algorithmic choices explain this performance. Per-query stopping predictors like AdaptNN, query-specific ef selectors like Ada-ef, and geometric stopping rules such as Al-Jazzazi et al. (NeurIPS 2025) calibrate stopping or breadth per query. TraCANN pools missed neighbors across query groups under one dataset-wide recall target, spending visits where additional true neighbors are cheapest to recover per unit time. In addition, choosing frontier capacity ww and total visit limit bb jointly lets TraCANN keep alternative routing paths in a wide queue and still stop full-vector evaluations early without resetting the search state (Figure 5).

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Author Responses and Manuscript Updates

We warmly thank Reviewers Z4ws, PoSA, and v3iS for their supportive reviews and thoughtful questions. Addressing the policy-attribution question raised by Reviewers Z4ws and PoSA, Table 2 (Section 4.2) evaluates fixed versus learned (w,b)(w, b) continuation on the same C++ search engine on SIFT1M at single-core 99% Recall@10. Fixed continuation reaches 12,604 QPS at 99.017% recall, and TraCANN's learned policy reaches 16,369 QPS at 99.125% recall, delivering a 1.30× speedup on the shared codebase.

We are especially grateful to Reviewer v3iS for suggesting a direct visual comparison and broader introductory framing, which guided our revisions to the abstract, Section 1, and Section 3 as well as the new schematic of uniform versus learned stopping in Figure 2. Our individual replies also cover Reviewer Z4ws's questions on prefix features, offline training times and memory footprints in Table 14, and empirical comparisons against AdaptNN and Ada-ef, along with Reviewer v3iS's prospective design questions for SIMT GPUs and RVV processors. Thank you all again for helping us strengthen the work.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.