Pith. sign in

REVIEW 4 major objections 5 minor 1 cited by

The paper claims Jasper, a GPU-native ANNS index, delivers up to 1.93× the query throughput of the leading GPU index while also supporting streaming updates.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-03 11:11 UTC pith:U2UFVBIR

load-bearing objection Solid GPU ANNS paper with real speedups, but the construction average is dominated by one outlier and the visited-set removal needs an ablation. the 4 major comments →

arxiv 2601.07048 v5 pith:U2UFVBIR submitted 2026-01-11 cs.DB cs.AI

GPU-Accelerated ANNS: Quantized for Speed, Built for Change

Hunter McCoy , Zikun Wang , Prashant Pandey This is my paper
classification cs.DB cs.AI
keywords approximate nearest neighbor searchGPU indexingVamana graphRaBitQ quantizationstreaming updatesbeam searchroofline analysisvector search
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper tries to establish that a GPU-native approximate nearest neighbor search index can be both faster than the existing state of the art and genuinely updatable—a combination previous GPU systems forced users to choose between. It argues that three bottlenecks (full rebuilds on update, memory-bound distance computation, and data-dependent memory access) can be removed with a batch-parallel lock-free construction over the Vamana graph, a GPU-friendly quantization scheme called RaBitQ, and a search kernel that dedicates one thread block to each query. If the reported measurements are right, vector search for recommendation, retrieval-augmented generation, and anomaly detection can move to GPUs without giving up incremental ingestion, and high-dimensional data can be searched with up to 8× less memory traffic. The headline numbers are up to 1.93× higher query throughput than the leading GPU index, 2.4× faster construction on average, and 19–131× faster queries than the prior GPU Vamana system.

Core claim

On its own terms, Jasper's central claim is that the Vamana graph—a directed proximity graph with bounded out-degree and greedy beam search—can be the basis of a GPU ANNS system that is faster and updatable at once. Construction is batched: each new vector runs an independent beam search over a read-only snapshot, candidate edges are gathered and sorted by target vertex, and pruning is applied per vertex with no locks. Query time uses a block-per-query kernel with the frontier and distances in shared memory and chunked 16-byte loads for coalesced memory traffic. The paper's first GPU implementation of RaBitQ quantization cuts vector footprint up to 8× with sequential access, making the quant

What carries the argument

The Vamana graph (a directed graph where each point keeps at most R outgoing edges selected so greedy search can navigate toward a query) is the object that carries the argument; its bounded out-degree keeps construction and search costs predictable. Jasper's pipeline rides on three mechanisms: batch-parallel insertion that separates traversal from mutation and applies pruning per vertex without locks; RaBitQ quantization, which uses randomized rotation and scalar quantization so distance estimation becomes a sequential inner-product computation with no codebook lookups; and a block-per-query kernel with chunked 16-byte vector loads that maximizes occupancy and hides memory latency. The roof

Load-bearing premise

The load-bearing premise is the paper's assertion, made from experience rather than an ablation, that removing the 512-slot visited-vertex hash table and deferred merging from the batch beam search leaves index quality and query accuracy essentially unchanged; if that is wrong, the Vamana graph's navigability—and every reported throughput and recall number—degrades.

What would settle it

Re-enable the 512-slot visited hash table and deferred merging during Jasper's construction on BigANN and Deep, hold R and beam width fixed, and measure recall@100 of the built graph; if recall moves beyond run-to-run noise, the paper's central simplification is wrong.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • GPU ANNS can exceed 13 million queries per second on BigANN and 3 million on 1,536-dimensional embeddings when RaBitQ is used.
  • Streaming updates become practical on a GPU index: 674K insertions per second peak, and adding a 10% slice of data completes an order of magnitude faster than rebuilding the entire index.
  • Quantization on GPUs does not have to trade away speed: RaBitQ runs up to 3× faster than exact distance computation on high-dimensional data at 90% recall, while product quantization shows no gain over exact search.
  • Construction becomes 2.4× faster on average than the leading GPU index across five standard datasets.
  • Because Jasper reaches 70–80% of the roofline, further gains in GPU ANNS will come mainly from reducing memory traffic rather than from algorithmic tweaks alone.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the claim that dropping the visited-set hash table and deferred merging is harmless generalizes, other graph-based ANNS algorithms ported to GPUs can shed visited-set bookkeeping entirely, simplifying kernels and freeing shared memory—worth testing on hierarchical navigable small world graphs, which currently rely on visited lists.
  • The RaBitQ results imply the GPU bottleneck is bytes moved, not operations; a testable corollary is that pushing quantization below 8 bits per dimension, or combining RaBitQ with scalar quantization of the rotation, should push throughput even closer to the compute roof.
  • The construction batch size is bounded by device memory left after storing the index, so on GPUs with more HBM the same pipeline should sustain higher insertion throughput; varying batch size on a fixed dataset would quantify that scaling, something the paper does not measure.
  • The 1.93× advantage is demonstrated at low-to-moderate recall; the paper's own plots show the leading GPU index retains an accuracy edge at very high recall on some datasets, so the headline claim is best read as winning the throughput–updatability trade-off in the regime most production systems actually use.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The paper presents Jasper, a GPU-native approximate nearest neighbor search (ANNS) system built on the Vamana graph index. It proposes three main techniques: (1) a batch-parallel, lock-free construction algorithm adapted from ParlayANN, (2) a GPU implementation of the RaBitQ quantization scheme, and (3) an optimized block-per-query beam-search kernel with chunked vector loads. Jasper is evaluated on five datasets (BigANN, Deep, Gist, OpenAI, Text2Image) on an NVIDIA A100 against CAGRA, BANG, GANNS, and ParlayANN. The paper claims up to 1.93x higher query throughput than CAGRA while supporting updates, 19–131x faster queries than BANG, 2.4x faster average construction than CAGRA, and 70–80% of peak roofline performance, with the artifact made publicly available.

Significance. If the claims are substantiated, Jasper is a useful systems contribution: it demonstrates that a Vamana-style graph can be built and queried efficiently on GPUs while supporting incremental updates, and it provides the first GPU implementation of RaBitQ with a systematic roofline analysis of GPU ANNS kernels. The artifact is released, which is a concrete strength. However, several load-bearing points are currently unsupported or internally inconsistent, so the headline claims cannot be accepted as written.

major comments (4)
  1. [§4.2] The removal of the 512-slot visited hash table and the deferred-merge optimization is asserted to "materially affect neither index quality or query accuracy," but no ablation is provided. This is load-bearing because the visited set controls duplicate expansions during beam search; changing it can alter the candidate edge set passed to robustPrune and therefore the graph's navigability, which in turn affects every recall/throughput curve in Figure 8. The paper's own observation that Jasper's maximum recall on BigANN 1@1 is 0.9943 versus CAGRA's 0.9999 (§6.3) is consistent with a subtle graph-quality shift. Please add an ablation that compares graph quality (e.g., recall at fixed beam width, edge statistics) and query throughput with and without these two features, at least on BigANN-10M/100M and Deep. Without this, the central claim that Jasper preserves Vamana quality while simplifying
  2. [Abstract vs. §7] The headline results are inconsistent between the abstract and the body. The abstract reports up to 1.84x higher throughput than CAGRA, 7x average construction speedup, and 10–74x faster queries than BANG, while the body and conclusion report 1.93x, 2.4x, and 19–131x respectively. These are materially different numbers. The reader cannot tell which set is authoritative. All instances must be reconciled to a single set of results with a clear mapping to the underlying tables and figures.
  3. [§6.2, Table 2] The construction claims need correction. First, Table 2 gives Jasper 679.8s for BigANN-100M, which is about 147K inserts/s, yet §6.2 states "peak throughput of 674K inserts/secs on BigANN." The origin of 674K must be clarified (e.g., a batch-peak on a smaller dataset or a different measurement window). Second, the claim "2.4x faster on average than CAGRA" is the arithmetic mean of per-dataset speedups 1.95, 1.05, 0.95, 1.06, 6.98; this mean is dominated by Text2Image and Jasper is actually slower on Gist. Please report aggregate construction time over the full benchmark set and/or the geometric mean, and give the per-dataset range. As written, the "average speedup" is not representative.
  4. [§6.2, Figures 6-7] The update evaluation measures only insertion throughput and total update time. It does not verify that the graph produced by incremental construction retains the same search quality as one-shot construction. Since the paper's central positioning is "built for change," the update claim requires evidence that recall and query throughput after incremental insertions do not degrade materially relative to bulk construction. Please add a comparison of recall@k and query throughput for indexes built incrementally versus in one shot, on at least one large dataset (e.g., BigANN-100M) and one high-dimensional dataset (e.g., OpenAI).
minor comments (5)
  1. [Abstract/Introduction] Typo: "Jasper's has the fastest incremental and batch GPU construction" should be "Jasper has the fastest...".
  2. [§6.1] The description of BANG says "pre-constructed Vamama graph" — typo for "Vamana." Also, BANG is described as not supporting updates, but the paper compares Jasper's update performance only against CAGRA and GANNS; a brief justification for not benchmarking BANG updates would help.
  3. [§5.1] The RaBitQ distance estimator is described in words and with metadata names, but no explicit estimator equation or the associated error bound from [11] is given. For reproducibility, please include the formula for the estimated squared distance in terms of data, data_add, data_rescale, rotated_query_vector, query_add, and query_sumq.
  4. [§6.6 / Table 3] The load microbenchmark and the tile microbenchmark sections describe essentially the same experiment and refer to the same Table 3. Consider merging them to avoid duplication. The figure labels are also small and hard to read in the PDF.
  5. [§6.5] The roofline analysis reports achieved TFLOP/s values, but the paper does not state the theoretical peak compute and memory bandwidth numbers used to draw the roofs. Including these constants would make Figure 9 reproducible.

Circularity Check

0 steps flagged

No significant circularity: Jasper's claims are benchmarked against external systems and algorithms, not derived from its inputs.

full rationale

This is a systems/performance paper rather than a derivation paper, and I find no load-bearing circular step. Jasper's central claims—higher query throughput than CAGRA, faster construction, updatability, and RaBitQ speedups—are established by direct benchmarking against external systems (CAGRA, BANG, GANNS, ParlayANN) on standard datasets. The underlying Vamana graph and RaBitQ quantization methods are cited from prior external work ([15] DiskANN, [20] ParlayANN, [11] RaBitQ), not from the authors' own unpublished claims. There is no fitted parameter that is later renamed as a prediction, no uniqueness theorem imported from the authors' prior work, and no ansatz smuggled in via self-citation. The GPU-specific choices (block-per-query execution, chunked 16-byte loads, removal of the 512-slot hash table and deferred merging) are presented as engineering decisions and are separately microbenchmarked where applicable. The one notable weakness—Section 4.2's assertion that removing the hash table and deferred merging 'materially affects neither index quality or query accuracy' is made without an included ablation—is a missing empirical justification, not a circularity: the claim is not defined in terms of the result it purports to support, and it does not make the later benchmark comparisons equivalent to the paper's own inputs. Accordingly, the honest finding is no significant circularity.

Axiom & Free-Parameter Ledger

6 free parameters · 6 axioms · 0 invented entities

The central performance claims depend on the correctness of imported graph/quantization algorithms and on tuned system parameters. No new theoretical entities are introduced. The free parameters listed above are dataset/implementation choices that materially affect the reported throughput numbers.

free parameters (6)
  • Vamana degree cap R = 64
    Set to 64 for all indices to keep graph size constant; directly controls memory footprint, recall, and traversal cost.
  • Query/insertion beam width = ranges from 1 to 256; per-dataset selection
    Beam width is a core search parameter; peak throughput numbers rely on dataset-specific tuning reported in microbenchmarks.
  • Thread block size = 32 threads for BigANN/Deep; larger for Gist/OpenAI
    Chosen empirically per dataset; the paper's latency-hiding and occupancy claims depend on this tuning (§6.6).
  • Construction batch size = ~1M for BigANN-100M; ~400K for Deep-100M; 2% increments in incremental experiments
    Bounded by GPU memory after index storage; determines construction parallelism and throughput (§4.6).
  • RaBitQ bits per dimension (m) = compression levels 4x and 8x used; exact m not stated
    Quantization error/throughput trade-off is central to the RaBitQ results, but the exact bit settings per dataset are not specified in the evaluation.
  • Vamana pruning factor alpha = not reported
    The robustPrune algorithm's alpha parameter controls graph sparsity vs navigability; the paper does not state the alpha used in its experiments.
axioms (6)
  • domain assumption Vamana/robustPrune preserves navigability of greedy search
    Adopted from DiskANN [15] without re-derivation; central to using the graph for queries and incremental updates (§3).
  • domain assumption ParlayANN batch-parallel construction (search, semisort, prune) is correct and lock-free
    CPU algorithm imported to GPU; correctness relies on read-only snapshots during search and per-vertex pruning after edge sorting (§3.3, §4.5).
  • standard math Random rotation makes each coordinate tightly concentrated around 0 (Johnson–Lindenstrauss)
    Invoked in §5.1 to justify scalar quantization of rotated vectors; standard lemma.
  • domain assumption RaBitQ distance estimator is unbiased with a theoretical error bound
    Jasper adopts RaBitQ's estimator and metadata formulas from [11] without re-derivation; load-bearing for the quantization accuracy claims (§5.1).
  • domain assumption GPU weak memory model and per-SM non-coherent L1 require shared-memory cooperative state
    Hardware model assumed in §2.2; motivates the block-per-query design and shared-memory placement of per-query state.
  • standard math Roofline model bounds attainable performance using peak compute and memory bandwidth
    Used to claim 70–80% peak utilization and to argue ANNS is memory-bound (§2.3, §6.5).

pith-pipeline@v1.3.0-alltime-deepseek · 20889 in / 14486 out tokens · 143853 ms · 2026-08-03T11:11:09.612356+00:00 · methodology

0 comments
read the original abstract

Approximate nearest neighbor search (ANNS) is a core problem in machine learning and information retrieval applications. GPUs offer a promising path to high-performance ANNS: they provide massive parallelism for distance computations, are readily available, and can co-locate with downstream applications. Despite these advantages, current GPU-accelerated ANNS systems face three key limitations. First, real-world applications operate on evolving datasets that require fast batch updates, yet most GPU indices must be rebuilt from scratch when new data arrives. Second, high-dimensional vectors strain memory bandwidth, but current GPU systems lack efficient quantization techniques that reduce data movement without introducing costly random memory accesses. Third, the data-dependent memory accesses inherent to greedy search make overlapping compute and memory difficult, leading to reduced performance. We present Jasper, a GPU-native ANNS system with both high query throughput and updatability. Jasper builds on the Vamana graph index and overcomes existing bottlenecks via three contributions: (1) a CUDA batch-parallel construction algorithm that enables lock-free streaming insertions, (2) a GPU-efficient implementation of RaBitQ quantization that reduces memory footprint up to 8x without the random access penalties, and (3) an optimized greedy search kernel that increases compute utilization, resulting in better latency hiding and higher throughput. Our evaluation across five datasets shows that Jasper achieves up to 1.84x higher query throughput than CAGRA and achieves up to 80% peak utilization as measured by the roofline model. Jasper's construction scales efficiently and constructs indices an average of 7x faster than CAGRA while providing updatability that CAGRA lacks. Compared to BANG, the previous fastest GPU Vamana implementation, Jasper delivers 10-74x faster queries.

Figures

Figures reproduced from arXiv: 2601.07048 by Hunter McCoy, Prashant Pandey, Zikun Wang.

Figure 1
Figure 1. Figure 1: GPU memory hierarchy and roofline model. [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: ANNS query pipeline in Jasper. between vectors is embarrassingly parallel and occupies the full block, while irregular phases such as candidate expansion and graph traversal are partially serialized to reduce control-flow divergence. The size of the thread block controls a trade-off between per￾query compute throughput and the number of memory requests issued. Larger blocks increase arithmetic throughput, … view at source ↗
Figure 3
Figure 3. Figure 3: Comparison of the two different load strategies [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Batch graph construction pipeline in Jasper. [PITH_FULL_IMAGE:figures/full_fig_p007_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: During L2 distance calculation, RaBitQ loads query [PITH_FULL_IMAGE:figures/full_fig_p008_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Jasper incremental construction throughput. X-axis [PITH_FULL_IMAGE:figures/full_fig_p009_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Incremental vs non-incremental construction [PITH_FULL_IMAGE:figures/full_fig_p009_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Query recall/throughput curves for various ANNS indexes across five datasets on Nvidia A100 GPU. We report recall [PITH_FULL_IMAGE:figures/full_fig_p010_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Roofline analysis of the Deep and Gist search [PITH_FULL_IMAGE:figures/full_fig_p011_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Varying Tile size for BigANN and Gist. Throughput [PITH_FULL_IMAGE:figures/full_fig_p012_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Varying Block size for BigANN and Gist. Through [PITH_FULL_IMAGE:figures/full_fig_p012_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: Different quantization method’s query perfor [PITH_FULL_IMAGE:figures/full_fig_p013_12.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. InferScale: GPU-Native KV Injection for Personalized LLM Serving

    cs.DC 2026-07 accept novelty 6.0

    GPU-resident precomputed KV injection with Chunked RoPE and context-window encoding makes personalized LLM memory latency nearly independent of retrieval budget while nearly matching prompt-injection accuracy.

Reference graph

Works this paper leans on

47 extracted references · 6 canonical work pages · cited by 1 Pith paper

  1. [1]

    Philip Adams, Menghao Li, Shi Zhang, Li Tan, Qi Chen, Mingqin Li, Zengzhong Li, Knut Magne Risvik, and Harsha Vardhan simhadri. 2025. DistributedANN: Effi- cient Scaling of a Single DiskANN Graph Across Thousands of Computers. InThe 1st Workshop on Vector Databases. https://openreview.net/forum?id=6AEsfCLRm3

    2025

  2. [2]

    Donaldson, Ganesh Gopalakrishnan, Jeroen Ketema, Daniel Poetzl, Tyler Sorensen, and John Wickerson

    Jade Alglave, Mark Batty, Alastair F. Donaldson, Ganesh Gopalakrishnan, Jeroen Ketema, Daniel Poetzl, Tyler Sorensen, and John Wickerson. 2015. GPU Concurrency: Weak Behaviours and Programming Assumptions. In Proceedings of the Twentieth International Conference on Architectural Support for Programming Languages and Operating Systems(Istanbul, Turkey)(ASP...

    arXiv 2015

  3. [3]

    Artem Babenko and Victor Lempitsky. 2015. The Inverted Multi-Index.IEEE Transactions on Pattern Analysis and Machine Intelligence37, 6 (June 2015), 1247–1260. doi:10.1109/tpami.2014.2361319

    arXiv 2015

  4. [4]

    Imane Belahyane, Mouad Mammass, Hasna Abioui, and Ali Idarrou. 2020. Graph-Based Image Retrieval: State of the Art. Springer International Publishing, 299–307. doi:10.1007/978-3-030-51935-3_32

    work page doi:10.1007/978-3-030-51935-3_32 2020

  5. [5]

    Jon Louis Bentley. 1975. Multidimensional binary search trees used for associative searching.Commun. ACM18, 9 (Sept. 1975), 509–517. doi:10.1145/361002.361007

    arXiv 1975

  6. [6]

    Blelloch, Daniel Anderson, and Laxman Dhulipala

    Guy E. Blelloch, Daniel Anderson, and Laxman Dhulipala. 2020. ParlayLib - A Toolkit for Parallel Algorithms on Shared-Memory Multicore Machines. InProceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA ’20). ACM, 507–509. doi:10.1145/3350755.3400254

    arXiv 2020

  7. [7]

    Mirrokni

    Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S. Mirrokni. 2004. Locality-sensitive hashing scheme based on p-stable distributions. InProceedings of the twentieth annual symposium on Computational geometry (SoCG04). ACM, 253–262. doi:10.1145/997817.997857

    arXiv 2004

  8. [8]

    Wei Dong, Charikar Moses, and Kai Li. 2011. Efficient k-nearest neigh- bor graph construction for generic similarity measures. InProceedings of the 20th international conference on World wide web (WWW ’11). ACM. doi:10.1145/1963405.1963487

    arXiv 2011

  9. [9]

    Matthijs Douze, Alexandr Guzhva, Chengqi Deng, Jeff Johnson, Gergely Szilvasy, Pierre-Emmanuel Mazaré, Maria Lomeli, Lucas Hosseini, and Hervé Jégou. 2024. The Faiss library. doi:10.48550/ARXIV.2401.08281

    Pith/arXiv arXiv doi:10.48550/arxiv.2401.08281 2024

  10. [10]

    R. A. Finkel and J. L. Bentley. 1974. Quad trees a data structure for retrieval on composite keys.Acta Informatica4, 1 (1974), 1–9. doi:10.1007/bf00288933

    doi:10.1007/bf00288933 1974

  11. [11]

    Jianyang Gao and Cheng Long. 2024. RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search.Proceedings of the ACM on Management of Data2, 3 (May 2024), 1–27. doi:10.1145/3654970

    doi:10.1145/3654970 2024

  12. [12]

    Siddharth Gollapudi, Neel Karia, Varun Sivashankar, Ravishankar Krishnaswamy, Nikit Begwani, Swapnil Raz, Yiyong Lin, Yin Zhang, Neelam Mahapatro, Premkumar Srinivasan, Amit Singh, and Harsha Vardhan Simhadri. 2023. Filtered-DiskANN: Graph Algorithms for Approximate Nearest Neighbor Search with Filters. InProceedings of the ACM Web Conference 2023 (WWW ’2...

    arXiv 2023

  13. [13]

    Xiaoyi Gu, Leman Akoglu, and Alessandro Rinaldo. 2019. Statistical Analysis of Nearest Neighbor Methods for Anomaly Detection. InAd- vances in Neural Information Processing Systems, H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (Eds.), Vol. 32. Curran Associates, Inc. https://proceedings.neurips.cc/paper_files/paper/201...

    2019

  14. [14]

    Piotr Indyk and Rajeev Motwani. 1998. Approximate nearest neighbors: towards removing the curse of dimensionality. InProceedings of the thirtieth annual ACM symposium on Theory of computing - STOC ’98 (STOC ’98). ACM Press, 604–613. doi:10.1145/276698.276876

    arXiv 1998

  15. [15]

    Suhas Jayaram Subramanya, Fnu Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnawamy, and Rohan Kadekodi. 2019. DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node. InAdvances in Neural Information Pro- cessing Systems, H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (Eds.), Vol. 32. Curran As...

    2019

  16. [16]

    Johnson and Joram Lindenstrauss

    William B. Johnson and Joram Lindenstrauss. 1984. Extensions of Lipschitz mappings into a Hilbert space. 189–206 pages. doi:10.1090/conm/026/737400

    doi:10.1090/conm/026/737400 1984

  17. [17]

    H Jégou, M Douze, and C Schmid. 2011. Product Quantization for Nearest Neighbor Search.IEEE Transactions on Pattern Analysis and Machine Intelligence 33, 1 (Jan. 2011), 117–128. doi:10.1109/tpami.2010.57

    doi:10.1109/tpami.2010.57 2011

  18. [18]

    Yury Malkov, Alexander Ponomarenko, Andrey Logvinov, and Vladimir Krylov

  19. [19]

    Malkov and D

    Yu A. Malkov and D. A. Yashunin. 2020. Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence42, 4 (April 2020), 824–836. doi:10.1109/tpami.2018.2889473

    arXiv 2020

  20. [20]

    Magdalen Dobson Manohar, Zheqi Shen, Guy Blelloch, Laxman Dhulipala, Yan Gu, Harsha Vardhan Simhadri, and Yihan Sun. 2024. ParlayANN: Scalable and Deterministic Parallel Graph-Based Approximate Nearest Neighbor Search Algorithms. InProceedings of the 29th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming (PPoPP ’24). ACM, 270...

    arXiv 2024

  21. [21]

    Marvin Minsky and Seymour A. Papert. 2017.Perceptrons: An Introduction to Computational Geometry. The MIT Press. doi:10.7551/mitpress/11301.001.0001

    doi:10.7551/mitpress/11301.001.0001 2017

  22. [22]

    Rajeev Motwani, Assaf Naor, and Rina Panigrahy. 2008. Lower Bounds on Locality Sensitive Hashing.SIAM Journal on Discrete Mathematics21, 4 (Jan. 2008), 930–935. doi:10.1137/050646858

    work page doi:10.1137/050646858 2008

  23. [23]

    NVIDIA. 2020. Nvidia A100 tensor core GPU | Data sheet | 1. https://www.nvidia.com/content/dam/en-zz/Solutions/Data-Center/a100/ pdf/nvidia-a100-datasheet-nvidia-us-2188504-web.pdf

    2020

  24. [24]

    2024.On the Design of Scalable Outlier Detection Methods Using Approximate Nearest Neighbor Graphs

    Camilla Birch Okkels, Martin Aumüller, and Arthur Zimek. 2024.On the Design of Scalable Outlier Detection Methods Using Approximate Nearest Neighbor Graphs. Springer Nature Switzerland, 170–184. doi:10.1007/978-3-031-75823-2_14

    work page doi:10.1007/978-3-031-75823-2_14 2024

  25. [25]

    Hiroyuki Ootomo, Akira Naruse, Corey Nolet, Ray Wang, Tamas Feher, and Yong Wang. 2024. CAGRA: Highly Parallel Graph Construction and Approximate Nearest Neighbor Search for GPUs. arXiv:2308.15136 [cs.DS] https://arxiv.org/abs/2308.15136

    Pith/arXiv arXiv 2024

  26. [26]

    Derrick Quinn, Mohammad Nouri, Neel Patel, John Salihu, Alireza Salemi, Sukhan Lee, Hamed Zamani, and Mohammad Alian. 2025. Accelerating Retrieval-Augmented Generation. InProceedings of the 30th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 1(Rotterdam, Netherlands)(ASPLOS ’25). Association f...

    2025

  27. [27]

    MD Shaikh Rahman, Syed Maudud E Rabbi, and Muhammad Mahbubur Rashid. 2024. Optimizing Domain-Specific Image Retrieval: A Benchmark of FAISS and Annoy with Fine-Tuned Features.ArXivabs/2412.01555 (2024). https://api.semanticscholar.org/CorpusID:274437371

    Pith/arXiv arXiv 2024

  28. [28]

    Deepjyoti Roy and Mala Dutta. 2022. A systematic review and research perspective on recommender systems.Journal of Big Data9, 1 (May 2022). doi:10.1186/s40537-022-00592-5

    doi:10.1186/s40537-022-00592-5 2022

  29. [29]

    2015.Fast and Scalable Outlier Detection with Approximate Nearest Neighbor Ensembles

    Erich Schubert, Arthur Zimek, and Hans-Peter Kriegel. 2015.Fast and Scalable Outlier Detection with Approximate Nearest Neighbor Ensembles. Springer International Publishing, 19–36. doi:10.1007/978-3-319-18123-3_2

    work page doi:10.1007/978-3-319-18123-3_2 2015

  30. [30]

    Harsha Vardhan Simhadri, George Williams, Martin Aumüller, Matthijs Douze, Artem Babenko, Dmitry Baranchuk, Qi Chen, Lucas Hosseini, Ravishankar Krishnaswamy, Gopal Srinivasa, Suhas Jayaram Subramanya, and Jingdong Wang

  31. [31]

    Aditi Singh, Suhas Jayaram Subramanya, Ravishankar Krishnaswamy, and Har- sha Vardhan Simhadri. 2021. FreshDiskANN: A Fast and Accurate Graph-Based ANN Index for Streaming Similarity Search. doi:10.48550/ARXIV.2105.09613

    Pith/arXiv arXiv doi:10.48550/arxiv.2105.09613 2021

  32. [32]

    Pradeep Kumar Singh, Pijush Kanti Dutta Pramanik, Avick Kumar Dey, and Prasenjit Choudhury. 2021. Recommender systems: an overview, research trends, and future directions.International Journal of Business and Systems Research15, 1 (2021), 14. doi:10.1504/ijbsr.2021.111753

    arXiv 2021

  33. [33]

    Sivic and Zisserman. 2003. Video Google: a text retrieval approach to object matching in videos. InProceedings Ninth IEEE International Conference on Computer Vision. IEEE, 1470–1477 vol.2. doi:10.1109/iccv.2003.1238663

    Pith/arXiv arXiv 2003

  34. [34]

    Yiping Sun, Yang Shi, and Jiaolong Du. 2024. A Real-Time Adaptive Multi-Stream GPU System For Online Approximate Nearest Neighborhood Search. InPro- ceedings of the 33rd ACM International Conference on Information and Knowledge Management (CIKM ’24). ACM, 4906–4913. doi:10.1145/3627673.3680054

    arXiv 2024

  35. [35]

    Karthik Venkatasubba, Saim Khan, Somesh Singh, Harsha Vardhan Simhadri, and Jyothi Vedurada. 2025. BANG: Billion-Scale Approximate Nearest Neighbour Search Using a Single GPU.IEEE Transactions on Big Data11, 6 (Dec. 2025), 3142–3157. doi:10.1109/tbdata.2025.3581085

    arXiv 2025

  36. [36]

    Hui Wang, Wan-Lei Zhao, Xiangxiang Zeng, and Jianye Yang. 2021. Fast k-NN Graph Construction by GPU based NN-Descent. InProceedings of the 30th ACM International Conference on Information & Knowledge Management (CIKM ’21). ACM, 1929–1938. doi:10.1145/3459637.3482344

    arXiv 2021

  37. [37]

    Shijie Wang, Wenqi Fan, Yue Feng, Lin Shanru, Xinyu Ma, Shuaiqiang Wang, and Dawei Yin. 2025. Knowledge Graph Retrieval-Augmented Generation for LLM-based Recommendation. InProceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). Association for Computational Linguistics, 27152–27168. doi:10.18653/v1...

    doi:10.18653/v1/2025.acl-long.1317 2025

  38. [38]

    Tevin Wang, Jingyuan He, and Chenyan Xiong. 2024. RAGViz: Diag- nose and Visualize Retrieval-Augmented Generation. InProceedings of the 2024 Conference on Empirical Methods in Natural Language Processing: Sys- tem Demonstrations. Association for Computational Linguistics, 320–327. doi:10.18653/v1/2024.emnlp-demo.33

    work page doi:10.18653/v1/2024.emnlp-demo.33 2024

  39. [39]

    Samuel Williams, Andrew Waterman, and David Patterson. 2009. Roofline: an insightful visual performance model for multicore architectures.Commun. ACM 52, 4 (April 2009), 65–76. doi:10.1145/1498765.1498785

    arXiv 2009

  40. [40]

    Yan Xia, Kaiming He, Fang Wen, and Jian Sun. 2013. Joint Inverted Indexing. In2013 IEEE International Conference on Computer Vision. IEEE, 3416–3423. doi:10.1109/iccv.2013.424 GPU-Accelerated ANNS: Quantized for Speed, Built for Change

    work page doi:10.1109/iccv.2013.424 2013

  41. [41]

    Yuanhang Yu, Dong Wen, Ying Zhang, Lu Qin, Wenjie Zhang, and Xuemin Lin

  42. [42]

    Weijie Zhao, Shulong Tan, and Ping Li. 2020. SONG: Approximate Nearest Neighbor Search on GPU. In2020 IEEE 36th International Conference on Data Engineering (ICDE). IEEE. doi:10.1109/icde48307.2020.00094

    arXiv 2020

  43. [43]

    Yifan Zhu, Ruiyao Ma, Baihua Zheng, Xiangyu Ke, Lu Chen, and Yunjun Gao

  44. [44]

    In2022 IEEE 38th International Conference on Data Engineering (ICDE)

    GPU-accelerated Proximity Graph Approximate Nearest Neighbor Search and Construction. In2022 IEEE 38th International Conference on Data Engineering (ICDE). IEEE, 552–564. doi:10.1109/icde53745.2022.00046

    arXiv 2022

  45. [2014]

    2014), 61–68

    Approximate nearest neighbor algorithm based on navigable small world graphs.Information Systems45 (Sept. 2014), 61–68. doi:10.1016/j.is.2013.10.006

    doi:10.1016/j.is.2013.10.006 2014

  46. [2022]

    arXiv:2205.03763 [cs.LG] https://arxiv.org/abs/2205.03763

    Results of the NeurIPS’21 Challenge on Billion-Scale Approximate Nearest Neighbor Search. arXiv:2205.03763 [cs.LG] https://arxiv.org/abs/2205.03763

    Pith/arXiv arXiv

  47. [2024]

    doi:10.1145/3654945

    GTS: GPU-based Tree Index for Fast Similarity Search.Proceedings of the ACM on Management of Data2, 3 (May 2024), 1–27. doi:10.1145/3654945

    doi:10.1145/3654945 2024