Building Vector Indices at Billion Scale (Valyu)

Valyu's engineering post, dated 2026-05-22, on rebuilding the initialisation path of its own vector search index. No byline; it is the company speaking. The headline: a build that took 80 minutes at 10M vectors now finishes in about 25 minutes at 100M on one GPU.

It reaches this spoke because of what the speed-up is made of. The index stores 512-bit binary vectors, so its distance function is hamming(a, b) = popcount(a XOR b) — hamming-distance on top of popcount — and the post's own summary of its argument is that "the 5 ns Hamming primitive that drives every decision in this post only exists because the distance primitive is this cheap on our representation."

Why T3. Every number here is Valyu measuring its own closed system. No code, no dataset, no independent replication, and the product being advertised at the bottom of the page is the thing being benchmarked. That is the maker grading its own work, which is what T3 describes. The architecture description is first-party and checkable in principle; the timings are not checkable at all. Compare xor-swap, the spoke's other benchmark-bearing source, where Brumme published the disassembly and the harness with it.

The one number this spoke cares about

A 512-bit Hamming distance costs about 5 nanoseconds on an Intel x86 CPU with AVX-512 and VPOPCNTDQ: one ZMM register, one XOR, one popcount, one horizontal sum. The post adds that floating-point dot products are "an order of magnitude more expensive and don't pin cleanly into registers in the same way."

That 5 ns is load-bearing for the entire system, and the post is explicit about the chain:

1. Because a comparison is that cheap, an exact brute-force sweep over every centroid beats the approximate graph walk the index uses at query time. Their stated crossover: T_brute = C × 5 ns against T_graph = V × 30–100 ns per visit, and the graph walk's per-visit cost itself grows with the centroid count as pointer-chasing goes cache-cold. Measured: per-search graph walk was 35 µs at 1M vectors and 390 µs at 10M — over 10× worse for 10× the corpus.
2. Because brute force is a flat sweep, it vectorizes, tiles, and eventually moves to a GPU.
3. Because the GPU kernel is a wall of popcounts, it ends up bottlenecked on the popcount pipe.

Tiling and pinning: 10 ns → 6.9 ns

The first brute-force kernel cost about 10 ns per Hamming, roughly 80% of it bookkeeping rather than arithmetic. Two changes, both of which are ordinary bit-manipulation discipline applied at industrial volume:

• Query tiling — process 64 queries against the same centroid stripe, so each centroid loads once per tile instead of once per query. At 40K centroids and 10M queries that is a 64× cut in per-centroid bookkeeping.
• Pinned-centroid SIMD — a naive routine feature-detects per call and reloads the centroid inside the SIMD body. "Both are fine when called once; both burn cycles when called 77 billion times." Feature-detect once per batch, load the centroid into a ZMM register, hold it pinned across the whole query batch: 10 ns → 6.9 ns.

Note what these are not. Neither is a clever bit trick in the bit-twiddling-hacks sense; the arithmetic was already at the hardware instruction. The wins came from getting everything that was not the instruction out of the way. At 10M vectors the two changes take assignment from 56.6 min to 8.84 min (6.4×), and total build from 64.3 min to 12.75 min (5.0×).

The post also records where the optimisation regresses: at 1M vectors the centroid array is 64 KB, fits in L1, and per-tile setup shows up as a 5% loss. Tiling only pays at 10M, where the array is 2.5 MB and L2-resident. The technique is scale-conditional, and they say so.

The GPU: pegged on the popcount pipe

A custom CUDA kernel (one thread per query, top-K held in registers via insertion sort). At 30M vectors × 120K centroids, 64-byte binary vectors, K=4, median of five:

8.4× to the GPU, and the kernel runs at about 488 billion 64-bit popcounts per second. Profiling puts it at 93% of compute throughput on the GPU MIO unit, where the CUDA popcll intrinsic shares issue cycles with branches and shared-memory ops. L2 hit rate is 100%. In their words: "The kernel is not memory-bound; it is pegged on the only pipe that can issue its hot instruction."

One detail feeds the spoke's ISA question directly. A single-threaded AVX-512 kernel does 0.32 GH/s per core, and 44 SMT threads reach only 7.25 GH/s — a 22× scale-up on 44 threads, which they attribute to AVX-512's shared 512-bit execution units and turbo throttling under sustained load. Wide-vector popcount does not scale with thread count, because the threads are fighting over the same execution unit.

Confirmed independently, 2026-08-22. uops-info measures VPOPCNTQ zmm at throughput 1.00 per cycle on port 5 alone, on Ice Lake, Tiger Lake, Rocket Lake, Alder Lake-P and Emerald Rapids alike. One issue port per core is exactly the shape this profile inferred: an SMT sibling can use cycles the first thread leaves idle and cannot add popcount throughput, so 44 threads across 22 cores returning 22× is the predicted result rather than an anomaly. The turbo-throttling half of the explanation is untested.

Their next step is not a tweak either: int1 BMMA tensor cores, a separate physical pipeline they expect to be roughly an order of magnitude faster on this work.

Why they wrote their own instead of using FAISS

Two reasons, the first of which belongs to this spoke: "binary vectors are second-class in most of them. These libraries are tuned around float vectors and L2 / inner-product distance; their fastest kernels assume floating-point dot products, not VPOPCNTDQ." The second is architectural — their index is not HNSW or IVF-PQ, and it takes streamed continuous updates rather than one-shot construction.

The thesis, in their words

"Brute force does not always win. The useful habit is to re-evaluate the primitive whenever the scale changes." And: "the fastest path came from treating index construction as a dense batched compute problem rather than as a sequence of approximate searches."

Cross-spoke context

Most of this post is a vector-search systems paper — recursive bisection into balanced buckets, a relative-neighbourhood graph over ~400K centroids at 100M vectors, K-way posting-list replication for recall, a 72-byte fixed-stride disk slab (u32 vector id + u32 doc id + 64-byte vector) so RSS tracks the working set instead of the corpus, and a pipeline overlapping disk reads, PCIe transfers, GPU compute and CPU posting writes. That substance is recorded here and not paged separately: no spoke in the hub owns vector indices or approximate nearest-neighbour search. The _inbox holds one parked source for an eventual information-retrieval cluster (Manning et al.'s Introduction to Information Retrieval), which predicted "embeddings and vector search" as exactly this kind of arrival; if that spoke is ever spun out, this page should be cross-linked from it, and the architecture half re-read there. ../analytical-databases-wiki was the routing runner-up, on index-construction-as-data-infrastructure.

Related

population-count · hamming-distance · valyu · bit-manipulation · swar · bit-twiddling-hacks