PaperlayerView exact revision on arXiv

Source-linked AI summary

RaBitQ-SSD: Split Codes and Pipelined I/O for SSD-Resident Vector Search

Yuexuan Xu, Jianyang Gao, Michael Norris, Alibek Zhakubayev, Pankaj Singh, Junjie Qi, Matthijs Douze, Cheng Long

arXiv:2610.02652v1cs.DB

TL;DR

SSD-resident ANN search must address the limits of DRAM and the I/O demands of search. RaBitQ-SSD combines prefix-based candidate pruning with asynchronous SSD reads. The paper reports improved throughput, fewer reads, and smaller, faster-to-build indexes than comparable graph-based systems, and demonstrates search at 10 billion vectors on one server and SSD.

  • Problem

    Graph-based search discovers candidates progressively, while IVF-based approaches read selected lists in full, leaving limited scope for planning reads or pruning within lists.

    Source: §1 · p. 2

  • Method

    RaBitQ-SSD uses a configurable in-memory code prefix with an error-bounded distance estimator and an asynchronous pipeline that coordinates pruning with SSD reads.

    Source: §1 · p. 2

  • Results

    RaBitQ-SSD provides higher throughput, fewer SSD reads, smaller indexes, and faster construction than comparable graph-based systems, and searches 10 billion vectors on one server with one NVMe SSD.

    Source: §7 · p. 12

  • Takeaways & Limitations

    The paper demonstrates that RaBitQ-SSD can search 10 billion vectors using a single server and one NVMe SSD.

    Source: §7 · p. 12

    DiskANN and PipeANN are not evaluated at 10 billion nodes because their 32-bit node IDs cannot represent that scale, and estimated graph-index storage with 64-bit IDs exceeds the SSD capacity.

    Source: §5.4 · p. 10

Abstract

from arXiv · show

SSD-resident approximate nearest-neighbor search is essential when vector collections exceed DRAM capacity. The challenge is to reduce SSD reads and hide I/O latency through concurrent reads and overlap with computation. However, for graph-based search, progressive candidate discovery limits advance I/O planning while IVF search reads inverted lists in full, incurring unnecessary SSD reads. In this paper, we present RaBitQ-SSD, an extension of IVF-RaBitQ for SSD-resident vector search. Specifically, we propose Split-RaBitQ, which retains a configurable prefix of each binary code in DRAM, allowing in-memory code storage below one bit per dimension. Using this partial representation, it provides an unbiased distance estimator with a probabilistic error bound. Once the in-memory coarse quantizer identifies candidate lists, this bound supports pruning individual candidates within them, enabling finer-grained SSD access. We also design an asynchronous search pipeline that coordinates candidate pruning with SSD read scheduling to reduce unnecessary reads while overlapping I/O with computation. On datasets ranging from $5$ million to $1$ billion vectors, RaBitQ-SSD delivers up to $1.74\times$ the throughput of graph-based baselines at $90\%$ recall, while reducing SSD page reads by up to $3.8\times$. Its on-SSD indexes are up to $7.0\times$ smaller and $10.0\times$ faster to build than DiskANN. We also build and search an index of $10$ billion vectors on a single machine with one SSD, achieving over $3{,}000$ queries per second at $90\%$ recall.

1 Introduction

The introduction frames SSD-resident ANN search as a way to store collections that exceed DRAM, while reducing SSD reads and hiding I/O latency. It presents RaBitQ-SSD as an IVF-RaBitQ extension combining prefix-based pruning with asynchronous I/O scheduling.

1 Introduction

  • Graph search discovers candidates progressively, limiting how far SSD accesses can be planned ahead.Expanding an uncached vertex requires reading its on-disk record to obtain neighbors.Source: §1 · pp. 1–2
  • IVF identifies candidate lists in memory, but existing methods read selected lists in full, motivating finer-grained pruning within them.The introduction identifies both fixed one-bit-per-dimension code storage and coordination of pruning with I/O as challenges.Source: §1 · p. 2
  • RaBitQ-SSD uses a configurable binary-code prefix to estimate distances and bound pruning, alongside an asynchronous pipeline that overlaps computation with SSD reads.The pipeline coalesces surviving candidates by page and re-evaluates promising pages before issuing reads.Source: §1 · p. 2
  • The paper evaluates scalability from 100 thousand to 10 billion DINO vectors (1,024 dimensions) on a single server with one SSD.At 10B scale, less than one millionth of the on-SSD data is read to perform the search.Source: Figure 1 · p. 1, §1 · p. 2

2 Preliminaries

The preliminaries describe IVF routing, RaBitQ distance estimation and pruning, and the limitations of a direct SSD extension. They establish the need for compact in-memory codes and nonblocking I/O.

2.1 ANN Search and IVF

  • IVF partitions vectors into centroid-based inverted lists and scans the n_probe lists nearest the query, trading search efficiency against accuracy.Each probed list still requires distance estimates for its vectors, making compact, fast estimation important.Source: §2.1 · p. 2

2.2 RaBitQ and Its Error Bound

  • RaBitQ quantizes unit residuals relative to a center and estimates their inner product; its unbiased estimate and error bound support candidate pruning.Per-vector factors and batched code lookups support distance estimation and FastScan.Source: §2.2 · pp. 2–3

2.3 In-Memory IVF-RaBitQ and a Naive SSD Extension

  • The direct SSD extension keeps full binary codes in memory and fetches SSD ex-codes for surviving candidates, but has rigid memory use and blocking reads.The in-memory code alone exceeds 1 TB for 10 billion vectors of 1,024 dimensions; asynchronous scanning is proposed to overlap I/O with computation.Source: §2.3 · p. 3

3 Split-RaBitQ

Split-RaBitQ divides each binary code between memory and SSD, using the retained prefix for distance estimation and pruning. Its probabilistic bound enables lower-bound pruning, with prefix length trading memory use against estimation precision.

3.1 The Code Splitting Design

  • Split-RaBitQ retains a build-time-configurable prefix of each binary code in memory and stores the remaining code bits, ex-code, and re-ranking factors on SSD.The prefix and three bound-related factors are packed in batches of 32 for FastScan.Source: §3.1 · p. 3, §3 · p. 3

3.2 A Lower Bound from the Prefix Code

  • The prefix-based inner-product estimate is unbiased, with estimation error O(1/sqrt(D_m)) with high probability, yielding a distance lower bound that holds with high probability.The estimator rescales the prefix contribution by D/D_m to account for omitted coordinates.Source: §3.2 · p. 4
  • Reducing D_m saves memory and pruning computation but widens the error bound, potentially increasing SSD reads and re-ranking work.This makes prefix length a trade-off between memory use and downstream search work.Source: §3.2 · p. 4

4 Search Pipeline

The search pipeline routes queries through IRQ, prunes candidates in probed lists using in-memory bounds, and schedules page reads asynchronously. A tighter drain threshold reduces remaining reads, with a recall guarantee under exact re-ranking and valid lower bounds.

4.1 Overview

  • The query flow probes the nearest clusters, scans batches using prefix-code lower bounds, coalesces surviving points into page candidates, and asynchronously reads and re-ranks surviving pages.The search rechecks candidates against the current dist_k and drains remaining reads after scanning the last cluster.Source: §4.1 · pp. 4–5

4.2 IRQ: In-Memory IVF-RaBitQ as the Coarse Quantizer

  • IRQ reduces average query latency to 2.8 ms, versus 3.9 ms with HNSW and 66 ms with a flat coarse scan, while achieving the best end-to-end performance.Figure 3 compares throughput against recall and splits latency at recall 0.95 into the coarse step and inverted-list work.Source: §4.2 · p. 5, Figure 3 · p. 5

4.3 Pipelining the Inverted-List Search

  • Scheduled queues page candidates by lower bound, caps in-flight reads at Q, and issues a read only while the candidate bound remains below dist_k.At T=1, it reduces reads from 156 to 53 per query compared with Overlapped.Source: §4.3 · pp. 5–6, Table 1 · p. 6
  • At T=64, Scheduled issues 40 reads per query with essentially none wasted and delivers 12× Overlapped’s throughput at k=10 and 5.8× at k=100.Its in-flight count stays at Q rather than rising into the hundreds.Source: §4.3 · p. 6, Table 1 · p. 6, Figure 4 · p. 7

4.4 𝛼-Quantile Threshold to Alleviate Drain

  • With exact re-ranking and valid lower bounds, the α-quantile threshold guarantees recall of at least α among points in the probed clusters.At α=0.4, the paper adopts a default for which about 85% of true top-k neighbors fall below the threshold in its stated measurement.Source: §4.4 · p. 6
  • With exact re-ranking and valid lower bounds, I/O completion order can affect Full’s results only at ranks (αk,k], while its reported effect on recall is low.Scheduled (α=1) is unaffected by completion order under those assumptions.Source: §4.4 · p. 6
  • At T=64 and k=100, Full reads 131 pages per query versus Scheduled’s 236, cuts the drain share from 73% to 19%, and raises throughput 1.8×.Reducing drain reads also lowers SSD contention, helping scan-phase reads complete sooner and tightening the scan threshold.Source: Table 1 · p. 6, §4.4 · p. 7

5 Experimental Study

Across matched-memory tests, RaBitQ-SSD has the highest throughput on five datasets at recalls 0.90 and 0.95. The experiments also examine operating conditions, billion-scale search, ablations, additional baselines, and indexing costs.

5.1 Experimental Setup

  • Experiments match per-vector memory budgets against DiskANN, Starling, and PipeANN, measuring recall, QPS, latency, and 4 KB pages per query against exhaustive-search ground truth.The evaluation uses 10,000 queries for the first six datasets; DINO-10B has a separate setup.Source: §5.1 · pp. 7–8

5.2 Main Evaluation

  • At recalls 0.90 and 0.95, RaBitQ-SSD has the highest throughput on all five datasets under both budgets; at Dm=D/2 and recall 0.95, speedup is 1.64–2.52× versus the best baselines.RaBitQ-SSD also reads 1.1–3.8× fewer pages per query than the lowest-reading baseline.Source: Figure 5 · p. 8, §5.2 · p. 8

5.3 Performance under Varying Operating Conditions

  • At recall 0.90, RaBitQ-SSD's advantage over the fastest baseline reaches 1.31–3.31× at k=100 and 1.65–4.01× at k=1000.At T=64 on YFCC-100M, it reaches 12,371 QPS versus baselines' 5,049–5,118; on DPR-100M, Dm=D/2 reaches 8,298 QPS, 24% above Dm=D.Source: Figure 6 · p. 9, §5.3 · pp. 9–10, Figure 7 · p. 10

5.4 Scaling to Billions of Points

  • At recall 0.90 on DataComp-1B, throughput is 1.48×, 2.96×, and 3.9× the fastest baseline at k=10, 100, and 1000; DINO-10B search reaches 3,210 QPS.From 100k to 10B vectors, throughput decreases 4.21× at recall 0.90 and 4.93× at recall 0.95.Source: Figure 8 · p. 10, §5.4 · p. 10, Figure 9 · p. 10

5.5 Ablation Study

  • Replacing PipeANN’s PQ with 1-bit RaBitQ lowers throughput ∼4% on both datasets; compact disk codes improve throughput 60+% over fp32 variants on YFCC-100M, while at recall 0.90, B=5 achieves 1.32×/1.26× SQ4 throughput on YFCC-100M/LAION-100M.SQ4 requires more probing and page reads to reach the same recall.Source: §5.5 · p. 11

5.6 Additional baselines

  • On Wiki-10M at recall 0.90, RaBitQ-SSD delivers 21.3× SPANN's throughput despite unequal memory budgets; at matched memory, it achieves 28,571 QPS versus AlayaLaser's 8,592.SPANN uses 6.6 GB versus RaBitQ-SSD's 1.1 GB; AlayaLaser's matched-memory cache covers about 2.8% of nodes.Source: §5.6 · p. 11, Figure 10 · p. 12

5.7 Indexing Cost and Footprints

  • Build time is at least 5.0× faster than the fastest graph baseline on every dataset; on DataComp-1B, RaBitQ-SSD's on-SSD index is 587 GB versus 4,096 GB for DiskANN and PipeANN.Across datasets, its on-SSD indexes are 4.0–7.0× smaller than the graph baselines' default representations.Source: §5.7 · pp. 11–12, Table 6 · p. 12

6 Related Work

Related work covers graph-based and partitioning-based SSD search, along with vector-quantization methods. RaBitQ-SSD builds on RaBitQ while deriving bounds from a code prefix.

6 Related Work

  • Graph-based SSD search keeps compressed guidance in memory and the graph on SSD; later work improves page locality [30] [34] [42] [68] [75] and overlaps traversal with asynchronous reads [31].DiskANN established this design pattern; AlayaLaser accelerates distance computation [10].Source: §6 · p. 12
  • Partitioning-based SSD methods include SPANN, HELMSMAN, and OrchANN [8], which differ in list selection, I/O paths, and handling of skewed partitions.Other approaches move compressed codes to SSD [54] or prune reads with triangle-inequality bounds [52].Source: §6 · p. 12
  • RaBitQ-SSD builds on RaBitQ's probabilistic error bounds and flexible-bit extension, deriving an unbiased estimator and probabilistic bound from a code prefix.Prior integrations include in-memory graph indexes, GPU systems [48], and an NPU–CPU system [26].Source: §6 · p. 12

7 Conclusion

RaBitQ-SSD combines configurable in-memory code prefixes with an asynchronous search pipeline. The paper reports improved throughput, fewer reads, smaller indexes, faster construction, and search at 10 billion vectors on one server and one NVMe SSD.

7 Conclusion

  • RaBitQ-SSD's configurable Split-RaBitQ prefix supports fine-grained pruning, while its asynchronous pipeline overlaps computation with I/O; experiments report better throughput, fewer reads, smaller indexes, faster builds, and 10-billion-vector search on one server with one NVMe SSD.Source: §7 · p. 12

A Analysis of Split-RaBitQ

The appendix analyzes the Split-RaBitQ prefix through its geometry and component distributions, then proves that its distance estimator is unbiased with a probabilistic error bound.

A Analysis of Split-RaBitQ

  • Only the projection of the prefix vector onto the plane spanned by the data direction and query contributes to their inner product.The component perpendicular to that plane contributes nothing to the query inner product.Source: Figure 11 · p. 14

A.1 Joint Distribution of the Prefix’s Components

  • The prefix’s joint distribution reduces its component orthogonal to the query plane to an independent sphere-distributed coordinate.The lemma expresses this component using X1, independent of the first two components.Source: §A.1 · p. 15

A.2 Concentration of the Prefix’s Share

  • The analysis applies sphere concentration to bound fluctuations in the prefix’s share of the full code.It treats the prefix-share function as Lipschitz and applies a sphere concentration inequality.Source: §A.2 · p. 15

A.3 Proof of Theorem 3.1

  • The estimator is unbiased because the normalized prefix share has expectation one and the orthogonal-component term has mean zero.The proof uses exchangeability for the prefix share and independence for the second term.Source: §A.3 · p. 16
  • The error bound controls the probability that estimation error exceeds ε/√Dm by 2e^-c1ε² for the stated ε range.The proof considers 0 < ε ≤ √Dm/3 before applying the bound.Source: §A.3 · p. 16

A.4 Empirical Error Distribution

Synthetic-vector experiments show errors centered near zero, with broader distributions for half-length prefixes. Lower-bound violation rates are higher for the half-length prefix in the reported cases.

A.4 Empirical Error Distribution

  • Errors are centered near zero, while retaining half the coordinates broadens their distributions.Figure 12 compares Dm=D and Dm=D/2 for D=768.Source: Figure 12 · p. 16, §A.4 · p. 16
  • 0.18% to 2.17%: for β=0.5, the lower-bound violation rate rises from full code to half-length prefix.At β=0.9, no violations were observed for the full code in 10^6 trials, versus 0.21% for the half-length prefix.Source: §A.4 · pp. 16–17

B Search-Result Determinism

Search-result variation differs between Scheduled and Full: Scheduled is nearly deterministic, while Full’s changes concentrate in the tail and depend on I/O completion order.

B Search-Result Determinism

  • Scheduled changes only 5 top-10 and 4 top-100 results among 10,000 queries across eight runs, with recall varying by at most 0.003 percentage points.The passage attributes remaining changes to the probabilistic nature of the lower bound.Source: B Search-Result Determinism · p. 17
  • 35.85%: at k=100, Full’s unchanged-query fraction is the same for the entire top-k and ranks (0.4k,k], versus 99.66% for the first 40 positions.Across eight runs, recall at k=100 ranged from 0.9005 to 0.9069; the passage links tail sensitivity to I/O completion order.Source: B Search-Result Determinism · p. 17

C.1 Main Evaluation

The passage identifies Table 8 as the throughput comparison for the five-dataset main evaluation at two recall targets.

C.1 Main Evaluation

  • Table 8 reports throughput for all five main-evaluation datasets at recall 0.90 and 0.95.The supplied passage does not state the table’s throughput values or comparison outcome.Source: §C.1 · p. 17

C.2 Ablation Study

The ablations show that RaBitQ-SSD’s throughput advantage depends on recall and representation: it can lead DiskANN at lower recall, while SQ4 falls behind as recall rises. More probing can make in-memory code scanning the bottleneck.

Ablation Study

  • At recall 0.90, RaBitQ-SSD (B=9) is faster than DiskANN (disk-PQ) on YFCC-100M, but DiskANN is faster at recall 0.95.At the higher recall, additional probing increases full-dimensional code-scanning work, making FastScan RaBitQ-SSD’s main bottleneck and limiting the benefit of fewer SSD reads.Source: §C.2 · p. 17
  • Across the ablations, higher recall can narrow throughput advantages as extra probing increases the work of scanning full-dimensional codes.RaBitQ-SSD’s advantage over DiskANN reverses at recall 0.95 on YFCC-100M, while SQ4’s throughput gap from B=5 grows at higher recall on both datasets.Source: §C.2 · p. 17
  • The throughput gap between B=5 and SQ4 grows at higher recall on both YFCC-100M and LAION-100M.SQ4 needs substantially more probing to reach higher recall; it reaches recall 0.95 on YFCC-100M at much lower throughput than B=5 and does not reach 0.95 on LAION-100M.Source: §C.2 · p. 17

C.3 Parameter Study

The parameter study shows that the useful in-flight read budget depends on query size and thread count, while the default settings remain close to their measured throughput optima. Tightening the drain threshold reduces page reads, with the default remaining close to the best measured throughput.

In-flight budget Q

  • At recall 0.90 and k=1000, reducing Q from 16 to 4 cuts T=1 throughput to about a third, while the same change barely affects k=10.Too-small Q limits SSD internal parallelism when many reads are issued; the study reports that the best Q rises with k and falls with T.Source: §C.3 · p. 17
  • The deployed rule, Q=16 for T≤16 and Q=8 above, stays within 3.7% of the best measured throughput across T and k.Excessively large Q can commit candidates that a later threshold would prune, causing unnecessary page reads and longer completion latency under heavy I/O.Source: §C.3 · p. 17, Figure 14 · p. 18

Drain threshold α

  • At recall 0.90, the default α=0.4 reads 132 pages per query at k=100 and 957 at k=1000, versus 236 and 1,699 at α=1.A tighter threshold prunes more pages left pending when the scan ends; α=1 recovers Scheduled.Source: §C.3 · p. 17, Figure 15 · p. 18
  • At recall 0.90, the default α stays within 6.6% of the best measured throughput at every k.Below the default, the page count barely moves; above it, the count nearly doubles.Source: §C.3 · p. 17

Parameter Study

  • Table 8 reports throughput at recall 0.90 and 0.95 across five datasets, k=10, T=64, and both memory budgets.Its caption says bold marks the highest QPS for each dataset, memory budget, and recall.Source: Table 8 · p. 18
Loading 2610.02652v1…