GINGER: Spicing Up Graph-Based Vector Search
Daniel Salwasser, Lars Gottesbüren, Laxman Dhulipala, Jakub Łącki, Guy Blelloch, Rajesh Jayaram, Tobias Rubel, Kshiteej Sheth, Amir Zandieh, Vahab Mirrokni
cs.IR, cs.DC
2026-11-06
Ginger uses one 12-bit nested code to navigate and rerank, near float accuracy at 2.6× less memory, and 1.8× the QPS of each dataset's best rival at 95% recall.
High-recall nearest neighbor search on modern embeddings is usually a proximity graph. HNSW, Vamana, and NSG link each point to nearby neighbors plus a few long-range edges, and a query walks the graph with beam search, always expanding the closest point it has not visited. Against IVF indexes such as Faiss and ScaNN, graphs compute far fewer distances once recall is high. What still hurts is memory bandwidth on the walk, the bytes the index occupies, and build time.
PiPNN already replaced the global searches inside construction with recursive partitioning, so billion-scale builds fall from hours to tens of minutes. Throughput and footprint stayed open. One query scores thousands of scattered candidates, so the navigation code has to be short. The final rerank has to sit close to float32, or recall above 95% slips. Storing both pays for the vectors twice. On low dimensions the graph is just as heavy: a 96-d vector at 12 bits is 144 bytes, and a flat list of 64 neighbors is 260.
Ginger is Google's open-source in-memory C++ library, and the public implementation of PiPNN. A build can use PiPNN or Vamana.
Nested TurboQuant (NTQ) extends TurboQuant. After normalization, a random orthogonal rotation makes coordinates roughly Gaussian, so one scalar codebook covers every dimension. The rotation is not a dense matrix. The dimension is split into r blocks whose length is a power of two, each block takes a Walsh-Hadamard transform, and a small orthogonal matrix mixes across blocks. For 768, 1536, and 3072, r is 3. Padding to the next power of two would add about 33% more codes and scoring work.
The leading 4 bits of each coordinate are a full TurboQuant code, with centroids at the Gaussian Lloyd-Max points. Beam search reads only those bits and scores them with an in-register 8-bit dot product. The extra k bits slice each 4-bit interval into 2^k finer Lloyd-Max bins and are read only at rerank time. The main settings are 10 and 12 bits. Gaussians are successively refinable under squared error, so pinning the fine code to the 4-bit boundaries costs almost nothing. A shared residual codebook ignores how the density changes from interval to interval, and it recalls worse in the paper's comparison. Navigation bytes and refinement bytes sit in separate arrays, so the walk does not fetch rerank bits. One scale per vector corrects the norm and the shrinkage from quantization.
At 10 and 12 bits the positive codebook has 512 or 2048 centroids. Memory gathers then take about 80% of rerank time at 4096 dimensions. A piecewise cubic evaluated in registers cuts that latency by about half, with no recall loss.
On high dimensions Ginger also cuts traffic. PCA projects vectors before the 4-bit walk, and the projection matrix is stored at 4 bits so the projection does not compete with the graph for bandwidth. TurboSlice reads a prefix of 128 or 256 rotated coordinates, skips the rest of a rejected neighbor, and stores nothing extra. The sketch is only a gate. Navigating on it would commit the greedy walk to the sketch's ranking errors. PCA is generally the stronger of the two. Stacking them does not help, because both remove the same kind of traffic.
Recursive partitioning then gives nearby IDs to tightly connected vertices, and adjacency lists store gaps. AdaptiveGap keeps StreamVByte's control byte and single SIMD shuffle for four gaps, but allows widths under 8 bits so small gaps are not rounded up to a whole byte.
The comparison is seven libraries and 14 public datasets on a dual-socket Xeon 6985P-C, 72 cores per socket, with 2.3 TB of RAM. Six sets have dimension at most 200, five of them at a billion points. Eight run from 768 to 4096, the largest being MS-MARCO at about 101 million vectors. Recall is 10@10. Ginger queries with 4+8-bit NTQ and a compressed graph. Some curves are missing because of out-of-memory failures. SymphonyQG tops out near 0.5% recall on Wiki-Cohere.
| Comparison | Baseline | Ginger |
| QPS at 95% recall | Fastest rival on that dataset | 1.8× average; 2.0× on high-d, up to 2.7×; 1.45× on low-d |
| QPS at 95% vs one library | Any single library | At least 2.3×; 2.9× vs compact libraries on high-d |
| High-d index size | Raw float32 | 43% on average with 12-bit NTQ |
| Low-d index size | SVS, the smallest graph rival | 1.54× smaller on average across four sets |
| Billion-scale build | Faiss, 69 min average | 35 min average |
Ginger has the highest throughput at both 90% and 95% recall on 13 of 14 datasets. The exception is BigANN, whose coordinates are already 8-bit integers. Graph libraries skip TurboQuant there, and SVS is 4% faster at both targets. On area under the QPS-recall curve, geometric-mean gains are 2.35× over ParlayANN, 2.38× over SVS, 2.42× over SymphonyQG, 2.79× over DiskANN, 10.3× over ScaNN, and 11.7× over Faiss.
ParlayANN, DiskANN, and Hnswlib keep raw floats, so their high-d indexes are about 2.7× larger. SymphonyQG stores codes on edges and is about 7.4× larger. Across the eight high-d sets, SVS uses 19.8% less memory in the geometric mean, but it is 2.9× slower at 95% recall and its peak recall is lower on every set. With 8-bit NTQ, Ginger is smaller than SVS on all eight, still 2.6× faster at 95% recall, with higher peak recall on seven. The billion-point Deep index is about 288 GB at 12 bits. On the low-d sets in the memory figure, Ginger's graph averages 111 bytes per vector, against 260 for the flat adjacency arrays in SVS and ParlayANN.
Quantizer quality is brute-force recall on 5 million points, separate from errors in the graph walk. Twelve-bit NTQ is close to float. Residual TurboQuant, uniform scalar quantization, and bf16 are not. At 4 bits, NTQ beats a reimplementation of Intel LVQ on the three high-d sets the paper calls out. At 12 bits both sit near float.
At 90% recall, moving navigation from floats to 4-bit TurboQuant is a 5.7× geometric-mean speedup, up to 7.2×. PCA adds another 1.8×, and 2.4× on DBpedia-3072. TurboSlice adds 1.26×. On the same vertex order, AdaptiveGap saves another 5.4% of graph memory versus StreamVByte, up to 7.6%, at matched throughput. With reordering, the graph is 2.1× smaller than uncompressed CSR on average, up to 2.5×, and throughput stays within 1.4% of the uncompressed layout.
PiPNN builds, including reorder, compression, quantization, and PCA, win on 11 of 14 datasets: 1.4× ahead of the best rival on average, and 4.9× on DataComp-DR. The five billion-scale sets average 35 minutes, against 69 for Faiss. On the tiny high-d sets PCA dominates, and ParlayANN can be up to 5.7× faster.
What ships is a library. The gain is largest on high-d text and LLM embeddings: about 2× the best rival's throughput at 95% recall, a full index around 43% of the raw floats, and no second copy of the vectors kept around for reranking. On low-d data, and especially on native 8-bit coordinates, most of what remains is graph compression. On BigANN, SVS is slightly ahead.
Billion-point builds land near half an hour on this machine. Several rivals take hours or do not fit in 2.3 TB. This is still an in-memory, single-node index. DiskANN's disk-backed design spends a different budget.
The measurements cover one dense vector per item. The discussion says the similarity can be Chamfer distance, multi-vectors, or a black-box scorer, and shows none of those. Inserts and deletes are not tested.
The abstract's 2.6× is the 12-bit code against float32. On high-d data the full index averages 43% of the raw vectors, and on low-d data the compressed graph is still a large share. Speedup averages drop sets where SymphonyQG or ScaNN ran out of memory or failed to recall. Build times for SVS and ScaNN include patches written for this paper: less lock contention on reverse edges, and k-means on 8-bit vectors. Query numbers should be unaffected. The build ranking should be read with those patches, and with Ginger paying for a reorder the other timers skip.
PCA is off at dimension 200 and below because it hurts accuracy. At 4096 dimensions the projection can take about half of query time, and it does not stack with TurboSlice. TurboSlice is cited as a concurrent paper still under submission. Every throughput number is from AVX-512 on Granite Rapids. There is no ARM or desktop result, no batched queries, and no disk index under the same RAM cap. Recall is 10@10.