TurboQuant can reduce vector index size by 10x at 100M Row Scale

Background

Since the publication of TurboQuant (tq) on April 28, 2025, and Google's larger announcement on March 24, 2026, a few open-source implementations have appeared: turbovec, a Rust/Python vector index, and 0xSero/turboquant, a PyTorch implementation aimed at LLM KV-cache compression. After reflecting on the algorithm, I thought it would be most useful at the database layer, and pgvector seemed like a good home for it. I've spent the last several weeks on this PR. And while working on it, a TurboQuant-based index type was requested for pgvector itself (#984)!

Note: I used Claude Code, Codex, and other AI tools extensively in this work.

For testing I used a large dataset I built alongside the usual open-source datasets. I'm' happy to share it if it's useful; it's unwieldy but could be hosted on HuggingFace or similar. I also gave a talk about this work recently while preparing the PR.

---

This PR adds three index access methods built on tq, a data-oblivious 4-bit vector quantization. The pipeline is a random orthonormal rotation (dense, or a structured randomized Hadamard transform) followed by per-coordinate Lloyd-Max quantization against the analytic coordinate distribution of rotated unit vectors. Because the codebook is data-independent, indexes need no training on the data so tqflat/tqhnsw build on empty tables just like hnsw. Queries score codes with an asymmetric-distance LUT, vectorized with a runtime-dispatched AVX-512 kernel (NEON on AArch64, scalar fallback), then rerank the top candidates with exact distances from the heap.

The key advantage of tq is that the index shrinks 2–8x versus the corresponding full-precision index, with equal or better recall after rerank at identical graph parameters, and the advantage grows with dimension. We pay for it with slower build times and slightly slower queries.

What's new

AM	Analogue	What it is	Types	Metrics
tqflat	(exact scan)	flat scan over the 4-bit code plane + rerank	vector, halfvec, sparsevec	L2, IP, cosine
tqivf	ivfflat	k-means inverted lists over codes (reuses ivfflat's k-means/sampling)	vector, halfvec	L2, IP, cosine
tqhnsw	hnsw	HNSW graph over codes (mirrors hnsw's architecture)	vector, halfvec, sparsevec	L2, IP, cosine

Feature parity with the existing AMs:

• WAL throughout (GenericXLog; builds replay on standbys, covered by WAL TAP tests)

• Concurrent insert (aminsert; tqhnsw mirrors hnswinsert's locking protocol)

• Vacuum: tqhnsw mirrors hnsw's four passes (tombstone → graph-repair → confirm-repaired → mark-deleted) with slot reuse, including 0.8.3's entry-point corruption fix and post-repair confirmation pass; tqivf/tqflat use ivfflat-style list/page vacuum

• Parallel build (tqivf, tqhnsw): tqhnsw ports hnsw's shared-memory graph build (relative pointers, two-lock insert protocol, flush-to-disk OOM fallback); near-linear scaling, 5.3–6.0× at 8 workers

• Iterative scans: tqivf.iterative_scan = relaxed_order and tqivf.max_probes (mirrors ivfflat)

• Build progress reporting, cost estimation, and amoptions

• Dimensions: 4-bit codes keep tuples small, so tqflat/tqhnsw reach 16,000 with fast_rotation = false, or 8,192 with the default fast_rotation (which pads codes to the next power of two); tqivf stores a full-precision centroid per list, so it inherits ivfflat's limits (2,000 vector, 4,000 halfvec); sparsevec is densified before encoding. Each AM raises a clear error past its limit.

New SQL surface: 24 operator classes ((vector|halfvec|sparsevec) × (l2|ip|cosine) × 3 AMs, minus tqivf sparsevec), 3 AM handlers, 21 opclass support functions; migration vector--0.8.3--0.8.4.sql (the branch is rebased on the current 0.8.3 release). The version number is a placeholder; happy to have you change that or anything else.

How this diverges from the paper and reference implementations

The paper and the two reference implementations target different settings than Postgres. turbovec is a standalone vector index, and 0xSero/turboquant is a KV-cache compressor for LLM inference. Putting the index inside Postgres shifts several of the key trade-offs. The deliberate divergences:

1. Structured rotation by default, dense rotation available. The paper specifies a dense random orthonormal rotation, and both reference implementations do this at the cost of an O(d²) matrix-vector multiply against a full d×d matrix held in memory. The paper also notes that a fast structured transform (randomized Hadamard / Kac's walk) can substitute "while preserving near-isotropy." We default to a structured, randomized Hadamard transform (fast_rotation, O(d·log d), no matrix to materialize), because at our target dimensions (up to 16,000) storing and applying a dense d×d rotation per build is incredibly slow. The dense rotation from my first implementation is still available via fast_rotation = false. I confirmed the structured transform is accurate enough for the part of the algorithm that's included. The per-coordinate marginal stays close to the analytic Beta distribution, so the data-oblivious codebook holds, and tqflat reaches recall 1.0000 after rerank.

2. We rerank; the paper and references don't. Neither the paper nor the reference implementations rerank. They rely on the quantized estimator being unbiased through one of two per-vector debiasing schemes: turbovec adapts RaBitQ's (arXiv:2405.12497, SIGMOD 2024) length-renormalization, storing one scalar per vector (‖x‖ / ⟨y,ŷ⟩), while the paper and 0xSero/turboquant append a second 1-bit stage, Quantized Johnson-Lindenstrauss (QJL), that estimates the sign of the residual (sign(S·r)). That stage is the only thing separating the tq_mse and tq_prod estimators.

We add the step they leave out. Every scan refetches the top-K candidates and replaces the quantized estimate with the exact distance. For the residual term that remains, we default to length-renormalization, because it costs nothing at query time and adds no storage.

We also implemented the QJL path (tq_prod), and it gave us clear negative results. First, QJL's unbiasing constant √(π/2)/d is derived for one specific projection: a sketch whose entries are independent Gaussian draws. The default fast_rotation uses a structured, fixed transform whose outputs are correlated rather than independent, so the constant no longer cancels the bias, and the leftover bias grows with dimension (about 20% at 128 dimensions). Second, even with a true Gaussian sketch, sharpening the estimate is redundant with the exact rerank, which already replaces it with the exact value. QJL spends about 25% extra storage (sign bits plus a residual norm, 4 + 1) to recover accuracy the rerank already provides.

That set the direction for the rest of the design: with an exact rerank in place, the useful levers are memory and speed, not estimator accuracy, and reranking a few more candidates is cheaper than sharpening each estimate. (tq_prod is covered again under "Known limitations and future work.")

3. SIMD scoring kernels. The scoring inner loop runs once per candidate vector and dominates query time. For each query we build a small lookup table with one entry per 4-bit code value, then apply it to vectors in batches of 32 with a single byte-shuffle instruction (vpshufb on x86, vqtbl1q on ARM). Partial scores accumulate in small integer counters that we flush periodically so they can't overflow. This FastScan-style kernel comes directly from turbovec (which in turn follows FAISS's fast-scan product quantization); the contribution is the Postgres-native plumbing around it: an on-page layout that groups each coordinate's codes together so the shuffle can stream through them, a runtime choice between AVX-512, NEON, and scalar versions (matching how halfutils.c and bitutils.c dispatch), and regression tests confirming the SIMD and scalar paths produce bit-identical results.

4. Bit width pinned to 4. The paper and both libraries let you pick anywhere from 1 to 4 bits. We fix it at 4 because our fast-scan layout packs two 4-bit codes into each byte and the byte-shuffle scoring assumes that packing. The codebook math (picking each code's representative value) works at any bit width, so the only thing tying us to 4 is the storage layout. Exposing 2- and 3-bit codes is a natural follow-up: they compress more aggressively, and since the exact rerank already fixes the final ordering, the extra estimation error from coarser codes is exactly what rerank is built to absorb. I left it out of this PR.

Benchmarks

5 methods × 5 datasets on a Minisforum UM790 Pro (AMD Ryzen 9 7940HS, Zen 4, 8 cores / 16 threads, AVX-512 active), 64 GB RAM, 1 TB NVMe, PG 18.4, k=10, exact ground truth, one index resident at a time. The two graph methods (tqhnsw, hnsw) are compared at identical m=32 / ef_construction=128 and the same ef_search ∈ {100,200,400} curve. That matched-m=32 setup holds across the tables below.

Index size and shrink factor:

dataset (dim)	tqflat	tqivf	tqhnsw	hnsw	ivfflat	tqhnsw vs hnsw	tqivf vs ivfflat
forum corpus (7.74M × 768)	3.92 GB	3.98 GB	7.55 GB	30.21 GB	30.23 GB	4.0×	7.6×
SIFT1M (128)	78 MB	88 MB	491 MB	966 MB	525 MB	2.0×	6.0×
GIST1M (960)	507 MB	530 MB	977 MB	7.68 GB	3.91 GB	7.9×	7.4×
GloVe (200)	165 MB	178 MB	661 MB	1.54 GB	1.03 GB	2.3×	5.8×
OpenAI-1M (1536)	998 MB	1.03 GB	1.56 GB	7.81 GB	7.82 GB	5.0×	7.6×

The 4-bit code plane replaces the float32 vectors, so the saving grows with dimension. tqivf is a flat 6–7.6× smaller than ivfflat across the board.

Build time:

dataset (dim)	tqhnsw	hnsw	tqhnsw vs hnsw
forum corpus (7.74M × 768)	6,315 s	3,421 s	1.85×
SIFT1M (128)	190 s	168 s	1.13×
GIST1M (960)	960 s	587 s	1.64×
GloVe (200)	544 s	325 s	1.67×
OpenAI-1M (1536)	1,195 s	691 s	1.73×

Build time is tqhnsw's main cost. The graph is built by scoring rotated 4-bit codes, which is heavier per node than hnsw's plain float dot product. The build distance kernel uses fp16 accumulation, which keeps the gap to 1.1–1.7× on the 1M sets and 1.85× on the 7.74M forum corpus. That forum figure is against an hnsw build given enough maintenance_work_mem (32 GB) to stay entirely in RAM; when hnsw's 30 GB graph instead spills to disk, its build slows sharply while tqhnsw's 7.5 GB graph still fits. tqivf builds in time comparable to ivfflat (forum corpus 945 s vs 1,009 s, and the 1M sets are within a few seconds of each other), and tqflat is the fastest to build (no graph). There are definitely more improvements/optimizations to be had here.

tqhnsw vs hnsw — recall@10 / QPS (forum corpus, 7.74M × 768, cosine; tqhnsw 7.55 GB / 6,315 s build vs hnsw 30.21 GB / 3,421 s build):

ef_search	tqhnsw recall	tqhnsw QPS	hnsw recall	hnsw QPS
100	0.9804	36.7	0.9793	85.6
200	0.9890	31.9	0.9907	49.7
400	0.9954	17.0	0.9952	27.7

Across all five datasets tqhnsw tracks hnsw recall closely. It scores within ~1 recall point at low ef_search (widest on GIST), tightening to ~0.2 point at ef 400, where it meets or exceeds hnsw on OpenAI-1M (0.9990 vs 0.9970 @ ef 400) and the forum corpus (above) with 2–8× less memory. The trade is query throughput (the ADC-LUT gather + heap rerank costs ~1.1–2× QPS at matched recall) and build time. On the same corpus, tqivf reaches 0.9931 recall at 2.0 QPS in 3.98 GB vs ivfflat's 0.9882 at 0.8 QPS in 30.2 GB: ~2.5× faster, 7.6× smaller. tqflat is exact (recall 1.0000 with rerank) and the smallest, but flat-scan throughput limits it to ~1M-row scale.

Tests

• 12 regression tests (tqflat_{math,internals,build,scan,vacuum}, tqivf_{build,scan,vacuum}, tqhnsw_{build,insert,scan,vacuum}): math/estimator invariants (rotation orthogonality, codebook MSE, pack/unpack and transpose round-trips, SIMD-vs-scalar kernel consistency), page layout, scan/insert/vacuum behavior, and NULL/edge-case semantics matching hnsw/ivfflat. Test-only C helpers are not part of the extension SQL; each test CREATE FUNCTIONs what it needs from the installed module.

• 8 TAP tests (100–107): recall gates for all three AMs across all metrics and types (halfvec/sparsevec included), concurrent-insert recall + crash/WAL replay, vacuum-then-recall, and WAL standby replay for tqflat/tqivf (modeled on 010_hnsw_wal.pl).

• Suite status: 26/26 pg_regress (macOS clang/arm64 + Linux gcc/x86-64 assert builds), 8/8 TAP files / 158 subtests (Linux, AVX-512 kernel active), plus 001_ivfflat_wal/010_hnsw_wal confirming the existing AMs are untouched. The full upstream CI matrix (PG 13–19 incl. -Wall -Wextra -Werror + asserts, Windows/MSVC 14+17, mac, i386, valgrind — 13 jobs) is green on the fork I made.

Known limitations and future work

1. tqhnsw builds more slowly than hnsw. It takes 1.1× as long on SIFT and 1.7× on OpenAI at 1M vectors, and 1.85× on the 7.74M build run entirely in memory (where hnsw is especially fast, because a large enough maintenance_work_mem keeps its whole build in RAM instead of spilling to disk). Changing how the build writes its WAL records would likely close part of the gap.

2. tqhnsw has no iterative scan yet. tqivf has one; this is a gap versus hnsw, which supports it.

3. tqivf does not support sparsevec. ivfflat has no sparse-vector support for us to reuse when clustering, so adding it would need either densified centroids or a sparse k-means implementation.

4. tqhnsw stores one heap row pointer (TID) per graph element. It does not merge duplicate vectors into a shared element the way hnsw does.

5. tqflat scans every vector, so its speed scales with table size. It's the right choice below roughly 1M rows, or as an exact baseline. Its memory stays bounded: the scan reads codes one block at a time and buffers candidates in a sort that respects work_mem and spills to disk if needed (the same approach as ivfflat), so scan memory depends on work_mem, not table size.

6. The tq_prod QJL stage should probably be removed. I built the optional 1-bit QJL refinement (the tq_prod reloption), but it's likely not worth keeping: with the default fast rotation its estimate is biased, and the exact rerank already recovers the accuracy it would add. It's off by default and undocumented, so rather than ship a dead code path I plan to remove it before merge.

Questions?

I know this is a large set of changes. I'm happy to break it up, run more tests, or make any other changes. Let me know your thoughts!