1
00:00:01,000 --> 00:00:08,383
[Hal Turing] Alrighty! Thanks for tuning in! Hello AI world! I am your host, Hal Turing, and my co-host is Dr. Ada Shannon.

2
00:00:08,383 --> 00:00:53,569
[Hal Turing] Today's paper is RaBitQ-SSD: Split Codes and Pipelined I/O for SSD-Resident Vector Search. Yuexuan Xu is the first author, with Jianyang Gao, Matthijs Douze, Cheng Long and colleagues. They're from Nanyang Technological University, ETH Zurich and Meta, and the paper is from October 2026. The headline claim is that an index of ten billion vectors on a single SSD can answer queries at over 3,000 per second, while reading less than a millionth of the stored data. The core question is whether keeping a partial binary code in memory, and using its error bound to skip individual reads, can beat graph-based SSD systems on page reads and throughput.

3
00:00:53,569 --> 00:01:08,848
[Dr. Ada Shannon] The mechanism is a bound that lets the system prove a disk read is unnecessary before issuing it. The headline fraction deserves scrutiny, and we'll get there. First the foundations, because this is a corner of ML infrastructure many people haven't seen.

4
00:01:08,848 --> 00:01:10,938
[Hal Turing] Start with why the SSD is involved at all.

5
00:01:10,938 --> 00:01:33,972
[Dr. Ada Shannon] Take a billion embeddings at 1024 dimensions in fp32. That's four terabytes. DRAM at that size is expensive, and SSD is roughly ten to fifty times cheaper per byte. One PCIe 4.0 SSD also delivers over a million random 4 KB reads per second. So the design question becomes how to answer a query with as few of those reads as possible.

6
00:01:33,972 --> 00:01:36,851
[Hal Turing] And the task itself is approximate nearest neighbor search?

7
00:01:36,851 --> 00:01:51,619
[Dr. Ada Shannon] Yes. Given a query vector, find vectors close to it without scanning everything. Quality is measured by recall at k: of the true k nearest neighbors, what fraction did you return. Recall at 10 of 0.9 means nine of the true ten on average.

8
00:01:51,619 --> 00:01:53,988
[Hal Turing] Give me the IVF version with a small example.

9
00:01:53,988 --> 00:02:16,790
[Dr. Ada Shannon] Say you have a million vectors. Run k-means to get a thousand centroids, and assign each vector to its nearest one. Each centroid's group is an inverted list, so about a thousand vectors per list. At query time you find the n_probe closest centroids, say eight, and scan only those lists. That's about eight thousand vectors instead of a million. It's a hash table whose buckets are learned from the data.

10
00:02:16,790 --> 00:02:19,483
[Hal Turing] Then graph indexes. DiskANN, Starling, PipeANN.

11
00:02:19,483 --> 00:02:46,790
[Dr. Ada Shannon] DiskANN, from Subramanya and colleagues at Microsoft in 2019, keeps a proximity graph on SSD with compressed codes in memory to guide the search. Starling and PipeANN refine that lineage. PipeANN overlaps compute with speculative reads. The structural limit is that you learn a node's neighbors only by reading the node. Candidates appear progressively, and every uncached hop costs a disk read. You can't plan reads far ahead, and some speculative reads turn out useless.

12
00:02:46,790 --> 00:02:51,434
[Hal Turing] So IVF knows its candidate lists up front. Why not just use IVF on SSD?

13
00:02:51,434 --> 00:03:18,090
[Dr. Ada Shannon] That's SPANN, from Chen and colleagues at Microsoft in 2021. Centroids stay in memory and posting lists sit on disk. But it reads whole lists, and most vectors in a list are nowhere near the query. In this paper's comparison on Wikipedia embeddings, SPANN reads about 870 pages per query where RaBitQ-SSD reads about 38. The caveat is that SPANN isn't memory matched there. It uses more memory.

14
00:03:18,090 --> 00:03:23,152
[Hal Turing] So the missing piece is a way to reject individual vectors safely. Where does RaBitQ come in?

15
00:03:23,152 --> 00:04:06,109
[Dr. Ada Shannon] RaBitQ is from Gao and Long, NTU, in 2024. Subtract the cluster centroid, apply a random orthogonal rotation, and keep only the sign of each coordinate. That's one bit per dimension. Unlike product quantization, whose error is empirical, RaBitQ's distance estimator is unbiased and comes with a probabilistic error bound. So every candidate gets an estimate and a guaranteed lower bound on its true distance. Extended RaBitQ, from Gao and colleagues in 2025, adds extra bits per coordinate. The sign bit plus those extra bits, called the ex-code, gives a sharper distance for re-ranking. The paper's default is nine bits total.

16
00:04:06,109 --> 00:04:08,431
[Hal Turing] And the lower bound is what lets you skip a read.

17
00:04:08,431 --> 00:04:26,775
[Dr. Ada Shannon] Right. Keep the current k-th best distance found so far. If a candidate's lower bound already exceeds it, that candidate can't enter the top k, so its data is never fetched. It's branch-and-bound at the level of single vectors. The guarantee is probabilistic, so recall stays approximate.

18
00:04:26,775 --> 00:04:29,329
[Hal Turing] Why can't you just port that straight to an SSD?

19
00:04:29,329 --> 00:04:50,320
[Dr. Ada Shannon] The paper names two problems with the naive port. First, memory is rigid. At ten billion vectors of 1024 dimensions, the binary codes alone exceed a terabyte of DRAM. Second, blocking I/O. One thread that issues a read and waits manages roughly ten thousand reads per second, against over a million that the device can serve.

20
00:04:50,320 --> 00:04:52,689
[Hal Turing] So a lot of the engineering is closing that gap.

21
00:04:52,689 --> 00:05:17,813
[Dr. Ada Shannon] And it gives us the frame for judging every result. Call r_max the measured random-read ceiling of the SSD, which is 1.63 million reads per second here. Read rate is queries per second times pages per query. Once the device saturates, QPS is roughly r_max divided by pages per query. If everyone is pinned at the same ceiling, the winner is whoever needs fewer pages.

22
00:05:17,813 --> 00:05:20,088
[Hal Turing] I'll hold you to that when the big numbers show up.

23
00:05:20,088 --> 00:05:33,649
[Dr. Ada Shannon] Start with the memory problem. Split-RaBitQ keeps only the first D_m bits of each binary code in DRAM, plus three small per-vector factors. The sign bits that aren't in memory, the ex-code and the re-ranking factors all go on the SSD.

24
00:05:33,649 --> 00:05:37,875
[Hal Turing] Dropping bits sounds like it would break the bound. Why does the lower bound survive?

25
00:05:37,875 --> 00:06:05,413
[Dr. Ada Shannon] The estimate is rescaled by D over D_m to make up for the missing coordinates. After the random rotation, each coordinate carries about an equal share of the signal, so the rescaled prefix estimate is still unbiased. The error width scales as one over the square root of D_m. Fewer bits give a looser bound, so more candidates survive pruning and more pages get read. D_m is therefore a memory dial, and the price of turning it down is SSD reads.

26
00:06:05,413 --> 00:06:09,918
[Hal Turing] So where does a record live on disk? The page has to be found without a lookup.

27
00:06:09,918 --> 00:06:32,302
[Dr. Ada Shannon] Each cluster is packed into contiguous 4 KB pages. Every vector gets one fixed-size record holding its suffix bits, ex-code and two factors, padded so none crosses a page boundary. The records sit in the same order in RAM and on SSD, sorted by distance to the centroid. A vector's position in memory therefore tells you which page holds it, and no index is needed.

28
00:06:32,302 --> 00:06:37,736
[Hal Turing] Before any of that, something has to pick the clusters. Isn't that scan expensive at 100 million vectors?

29
00:06:37,736 --> 00:07:06,761
[Dr. Ada Shannon] On YFCC-100M it was the dominant cost. With about 96,000 centroids, a flat scan took 95% of query latency, roughly 62 of 66 milliseconds. A graph over the centroids brought a query to 3.9 milliseconds. Their choice, called IRQ, is a small in-memory RaBitQ index over the centroids themselves. It gets a query to 2.8 milliseconds, so the same prune-then-rerank idea also does the routing.

30
00:07:06,761 --> 00:07:09,361
[Hal Turing] Now the pipeline. I take it there's a progression.

31
00:07:09,361 --> 00:07:29,284
[Dr. Ada Shannon] Yes, and it works as a causal chain. Naive reads each surviving candidate and blocks, so the thread spends over 90% of its time waiting. Coalesced lets survivors on the same page share one read, which gives 1.3 times the speed. Overlapped stops blocking, and with one thread it's a big win, about 6.7 times Naive.

32
00:07:29,284 --> 00:07:30,352
[Hal Turing] And at full load?

33
00:07:30,352 --> 00:07:58,262
[Dr. Ada Shannon] It collapses. With 64 threads the SSD saturates and completions slow down. dist_k, the current k-th best distance, stops tightening, so more candidates survive pruning. That triggers more reads, which slow completions further. The loop feeds itself. A query issues 483 pages and 400 are wasted. It ends up slower than the plain blocking version, at 0.58 times Naive.

34
00:07:58,262 --> 00:07:59,888
[Hal Turing] So the fix is to decide later.

35
00:07:59,888 --> 00:08:23,944
[Dr. Ada Shannon] Right. Scheduled puts page candidates in a priority set ordered by page lower bound. At most Q reads are in flight, and each candidate is re-checked against the latest dist_k just before its read goes out. Most are dropped while they wait. That's about 40 reads per query, near 7 times Naive. Replacing the lower-bound ordering with FIFO issues roughly twice the reads and cuts throughput to under half.

36
00:08:23,944 --> 00:08:25,290
[Hal Turing] What does Full add, then?

37
00:08:25,290 --> 00:08:55,709
[Dr. Ada Shannon] It targets the drain, the tail after the last cluster when only outstanding I/O remains. There it issues a pending read only if the page could place in the top alpha times k results, with alpha at 0.4. At k equals 100 and 64 threads, pages drop from 236 to 131 and throughput rises about 1.8 times. One catch: with alpha below one, the returned neighbors can depend on the order reads complete. The authors say the effect is low.

38
00:08:55,709 --> 00:08:59,331
[Hal Turing] Does that same pages-per-query story hold against the graph systems?

39
00:08:59,331 --> 00:09:40,244
[Dr. Ada Shannon] Yes, it's the central result. This was one Threadripper box with 768 GB of DRAM and one PCIe 4.0 Samsung SSD. At recall 0.90 and k equals 10, the best graph baseline reads about 1.1 to 3.8 times RaBitQ-SSD's pages. Every method sits near the SSD ceiling, so the throughput gap follows the page gap. On YFCC it's about 62 pages for PipeANN against 38 here, which accounts for about 1.6 times the QPS. The gap widens with k, reaching 2.86 times at k equals 1000. The limits: memory is matched per point, not in total, and they report no error bars.

40
00:09:40,244 --> 00:09:42,799
[Hal Turing] Could the win just be the bound, or is it something else?

41
00:09:42,799 --> 00:10:17,118
[Dr. Ada Shannon] The ablation says it's the bound. Swapping PipeANN's product-quantization codes for one-bit RaBitQ codes made it about 4% slower, so the code type alone buys nothing. But the compact on-disk record matters too. Storing fp32 vectors in RaBitQ-SSD's own layout was 15% slower on LAION. On YFCC, giving DiskANN compressed on-disk codes closed the gap to 12%, and DiskANN then read slightly fewer pages, 36.5 against 37.8. So part of the win is the compact record, not only the pruning.

42
00:10:17,118 --> 00:10:18,465
[Hal Turing] Any cost on the build side?

43
00:10:18,465 --> 00:10:42,845
[Dr. Ada Shannon] A real saving. The indexes are up to 7 times smaller on SSD and build at least 5 times faster. On the one-billion-vector set, 9.2 hours and 587 GB compared with 45.6 hours and 4,096 GB for DiskANN. Part of that is no per-vector adjacency lists. Part is cheap assignment and encoding instead of graph construction.

44
00:10:42,845 --> 00:10:51,855
[Hal Turing] Let's take the headline. At ten billion vectors, less than one-millionth of the on-SSD data is read. That sounds like an efficiency miracle. Is it?

45
00:10:51,855 --> 00:11:07,784
[Dr. Ada Shannon] It's a ratio against a 10.24 terabyte store, so it mostly measures how big the corpus is. The real cost is about 509 random 4 KB pages per query, roughly 2 megabytes. Any index that touches a few hundred pages looks tiny against 10 terabytes.

46
00:11:07,784 --> 00:11:10,199
[Hal Turing] And 3,210 queries per second at that scale?

47
00:11:10,199 --> 00:11:35,323
[Dr. Ada Shannon] Multiply it out. 3,210 times 509.4 is about 1.63 million pages per second, which is the measured device ceiling. The read rate sits between 1.55 and 1.64 million at every size from 100 thousand to 10 billion. So the 10B throughput is the SSD's page budget divided by pages per query. It isn't a separate discovery.

48
00:11:35,323 --> 00:11:38,016
[Hal Turing] Then what does the 10B run show beyond that division?

49
00:11:38,016 --> 00:12:01,700
[Dr. Ada Shannon] The denominator stayed small. Pages per query grew only about 4.25 times, from 120 to 509, over 100,000 times more data. QPS fell 4.21 times. Also, a 545 GB resident index and a single SSD sustaining over 3,000 QPS at recall 0.90 is a feasibility result, and a real one.

50
00:12:01,700 --> 00:12:04,905
[Hal Turing] What produced the slow growth? Is it the pruning bound?

51
00:12:04,905 --> 00:12:28,032
[Dr. Ada Shannon] Several candidates, and the paper doesn't separate them. Cluster size is fixed, with about N over 4096 clusters. Probe counts grow slowly. The lower-bound pruning keeps working. But there's no cluster-size ablation. The subsets are also the first N vectors of one DINO dataset, which may be an easy distribution. So I wouldn't claim it holds for hard, high-intrinsic-dimension data.

52
00:12:28,032 --> 00:12:29,472
[Hal Turing] And nobody else ran at 10B.

53
00:12:29,472 --> 00:12:58,822
[Dr. Ada Shannon] DiskANN and PipeANN use 32-bit node IDs, and the authors estimate a 64-bit extension at 20.48 terabytes. So there's no head-to-head. The closest evidence is the 1B comparison, 1.48 times faster at k=10, rising to 3.9 times at k=1000. But the 10B run keeps raw uint8 vectors on SSD, while 1B uses 8-bit ex-codes on a different dataset. Those two points don't form a clean scaling curve.

54
00:12:58,822 --> 00:13:02,630
[Hal Turing] The 10B run also uses a quarter of the prefix. Was that a free choice?

55
00:13:02,630 --> 00:13:31,422
[Dr. Ada Shannon] It was forced by memory. A full prefix would need 1.48 terabytes against 768 of DRAM. The authors say themselves that D/4 makes the run I/O-bound. The opposite regime matters too. At recall 0.98 with the full prefix, the fastest graph baseline wins on four of five datasets. Probing more clusters makes CPU scanning the limit. Memory is a real dial, and the paper offers no rule for setting it.

56
00:13:31,422 --> 00:13:33,466
[Hal Turing] What about the 16x number on DPR?

57
00:13:33,466 --> 00:14:02,026
[Dr. Ada Shannon] Treat that with suspicion. The baselines get memory matched per vector, which leaves them roughly 60-byte PQ codes at half prefix. On DPR that makes their page reads balloon. That's PQ failing at a small byte budget. The ablation agrees: swapping PQ for 1-bit RaBitQ codes in PipeANN changes little, about 4% slower. And a compact on-disk record explains a lot of the win. DiskANN with disk-PQ nearly closes the gap on YFCC.

58
00:14:02,026 --> 00:14:03,884
[Hal Turing] So the bound isn't the whole story.

59
00:14:03,884 --> 00:14:12,011
[Dr. Ada Shannon] It's part of it. The pipeline ablations show scheduling by lower bound matters. But the speedups bundle compact records, the bound and scheduling together.

60
00:14:12,011 --> 00:14:12,986
[Hal Turing] Other soft spots?

61
00:14:12,986 --> 00:14:49,349
[Dr. Ada Shannon] Matching is per-point bytes, not total memory. SPANN isn't memory matched. There are no error bars, one machine, one fast PCIe 4.0 SSD. The drain threshold at alpha 0.4 can make returned results depend on I/O completion order, which matters for reproducibility. And the index is static. Inserts mean rewriting pages and repacking batches, and the only update story is a nine-hour rebuild at 1B. Graph systems have FreshDiskANN and Filtered-DiskANN for that, and filtered search could break page coalescing.

62
00:14:49,349 --> 00:14:51,392
[Hal Turing] Practically, what should someone take from this?

63
00:14:51,392 --> 00:15:17,909
[Dr. Ada Shannon] On a saturated SSD, watch pages per query, not bytes read as a fraction. Ask any such claim what the denominator is. Ask what memory and on-disk format the baselines got. And check recall at your target, because 0.98 behaves differently from 0.90. On a slower SSD the page gap should matter more, but that wasn't tested. A faster one pushes you toward the CPU limit.

64
00:15:17,909 --> 00:15:19,209
[Hal Turing] So what's established?

65
00:15:19,209 --> 00:15:44,148
[Dr. Ada Shannon] A partial-code bound plus scheduled async I/O cuts pages per query and beats graph baselines on one SSD at 100M to 1B scale, with compact records doing part of the work. A 10B index is feasible on one box. The boundary is that the 10B number is the SSD ceiling divided by about 500 pages. It's not a comparison, and high-recall CPU limits remain.

66
00:15:44,148 --> 00:15:46,748
[Hal Turing] Thanks for listening, everyone. See you next time.