GINGER: Spicing Up Graph-Based Vector Search

Introduction

The rapid progress in deep learning has placed Approximate Nearest Neighbor Search (ANNS) at the center of information retrieval and data analysis [31, 49, 50, 62, 72, 88, 93]. Today’s workloads are marked by a sharp increase in both the number of indexed entities and the dimensionality of the embeddings used to represent them.

Proximity graphs have been shown to perform well in very high dimensions, and are thus the dominant technique for ANNS indexing whenever high recall is paramount. A proximity graph represents each entity as a vertex and connects it to nearby and further directionally diverse neighbors. Queries route through the graph via greedy beam search, which iteratively expands the closest unexplored vertices until converging to the query neighborhood. Prominent proximity-graph algorithms include HNSW [57], Vamana (DiskANN) [41], NSG [26], and PiPNN [73, 74]. Compared to cluster-based inverted-file (IVF) indexes such as Faiss [22] and ScaNN [37, 81], proximity graphs achieve high recall with many fewer distance evaluations on modern embeddings.

Still, graph indexes face three bottlenecks in practice: (1) memory bandwidth at search time, (2) memory footprint to host the index, and (3) indexing time. Our prior work PiPNN [73, 74] effectively resolved the issue of index construction, building high-quality

billion-scale indexes in 10s of minutes instead of hours. This paper addresses the other two bottlenecks: search throughput and memory footprint. Moreover, we introduce the first production-grade implementation of PiPNN.

To this end we present and open-source GINGER¹, an in-memory C++ library for graph-based ANNS. It was developed internally at Google to solve a variety of large-scale retrieval problems with a primary focus on efficiency. We developed GINGER from the ground up as a standalone C++ library with portable SIMD kernels written in Highway [87]. GINGER also serves as the official open-source implementation of PiPNN II [73], thus combining SOTA query speed, memory efficiency and indexing time in one package.

Many industrial-grade vector search libraries exist, including Faiss [22], ScaNN [37, 81], DiskANN [41], SVS [1], and Hnswlib [58]. Given this high bar, it might be expected that there exists little room for improvement over these widely adopted and well-optimized systems. Surprisingly, we find that a combination of algorithmic improvements in vector quantization as well as careful performance engineering yields significant speedups over the prior state of the art. Across all 14 benchmarks in our evaluation, Ginger is on average 1.8× faster than the fastest competitor at 95% recall (up to 2.7×). The gap is largest on high-dimensional datasets ($d \ge768$), where Ginger is 2.0× faster on average. Our results come from both designing every step of our beam search implementation around reducing memory traffic as well as reducing the index footprint by way of lossless graph compression. We make the following contributions.

• Nested TurboQuant (Section 3). We introduce Nested TurboQuant (NTQ), an extension of TurboQuant in which a single code per vector serves both graph navigation and reranking. The beam search operates on the leading 4 bits per coordinate, which form a valid TurboQuant code [85, 92]. The remaining $k$ bits refine each 4-bit interval with a nested Lloyd–Max codebook, using the full code to rerank the search results. With 12 bits per coordinate, NTQ nearly matches the accuracy of 32-bit floats while using 2.6× less memory.

• Fast graph search (Sections 3 and 4). We contribute an extremely fast SIMD kernel for one-to-many scoring of the 4-bit codes. On high-dimensional embeddings, we offer two ways to further speed up the search. We either project vectors to a lower dimension with PCA, or apply a tuning-free prefilter called TurboSlice [17] to discard unpromising candidates early.

• Graph compression (Section 5). On low-dimensional datasets, the graph adjacency lists of prior libraries consume as much memory as the quantized vectors themselves. We introduce AdaptiveGap, a lossless codec that packs small gaps into fewer than eight bits while retaining the single-shuffle SIMD decoding of StreamVByte. On the same vertex ordering, AdaptiveGap uses on average 5.4% less graph memory (up to 7.6%) than StreamVByte. We combine this codec with graph partitioning to assign nearby IDs to neighboring vertices. Together, these techniques shrink the graph by an average of 2.1× (up to 2.5×) relative to an uncompressed CSR layout without slowing down queries.

• Extensive evaluation (Section 6). We compare Ginger with seven state-of-the-art graph and IVF libraries on 14 public benchmarks with up to one billion vectors and 4096 dimensions. Ginger achieves the highest query throughput at 90% and 95% recall on 13 of the 14 benchmarks. At 95% recall, Ginger outperforms the fastest competitor by 2.0× on average (up to 2.7×) on high-dimensional data and by 1.45× (up to 2.1×) on low-dimensional data. At 90% recall, the corresponding speedups are 1.8× (up to 2.3×) and 1.55× (up to 2.0×). The complete Ginger index for the billion-point Deep dataset occupies approximately 288 GB of memory with 12-bit NTQ (Figure 5).

Ginger’s modular design and portable SIMD kernels make it easy to integrate state-of-the-art ANNS into new search and data management systems. Our results demonstrate that we can simultaneously deliver state-of-the-art memory footprint, search performance, and indexing time through a mix of algorithmic improvements and performance engineering.

Preliminaries

Let $\mathcal{X} \subseteq\mathbb{R}^{d}$ be a collection of $n$ vectors and let $\operatorname{dist}(\cdot,\cdot)$ be a dissimilarity on $\mathbb{R}^{d}$, such as Euclidean distance or negative inner product.

Approximate Nearest Neighbors (ANNS). Given a query $q$, an approximate nearest neighbors (ANNS) index returns a set $\mathcal{K}'$ that approximates $\mathcal{K}$. The quality is measured by the recall, $|\mathcal{K} \cap\mathcal{K}'|/k$, averaged over a query set. We write $k@k'$ recall when $|\mathcal{K}'| = k' \ge k$, and use 10@10 recall unless stated otherwise. An index is judged by its throughput (queries per second, QPS) at a given recall, by its memory footprint, and by the time taken to construct it.

ANNS Indexes

Proximity Graphs and Search. A graph-based ANNS index organizes vectors into a proximity graph, with a vertex for each vector and directed edges connecting vectors. Neighbors are selected heuristically during graph construction based on closeness and directional diversity. Queries explore the graph using beam search (Algorithm 1). Starting from an entry vertex $s$, the search maintains a beam $B$ of at most $L$ candidates and a set $V$ of expanded vertices. It repeatedly expands the closest vertex in $B \setminus V$, adds its neighbors to the beam, and retains the $L$ closest candidates, stopping when every vertex in the beam has been expanded. Implementations of graph search differ widely in their candidate and visited-set data structures, stopping rules, filtering, batching, and prefetching. They may also navigate using quantized vectors and rerank a larger candidate set using full-precision vectors or more accurate codes. These choices affect memory traffic, query throughput, and recall.

Algorithm 1: BeamSearch

Input: G = (X, E) a proximity graph over X, s ∈ X an entry point, q a query point, and L ∈ N a beam width
Output: B ⊆ X containing the L closest points to q encountered during the search

1  B ← {s};
2  V ← ∅;
3  while B \ V ≠ ∅ do
4      p ← arg min_{u∈B\V} dist(u,q);
5      B ← B ∪ Neighbors(p);
6      V ← V ∪ {p};
7      if |B| > L then
8          B ← the L points in B with smallest distance to q;
9  return B;

Graph Construction. The Vamana [41] index constructs a proximity graph iteratively via beam-search traversals on the partial index and an $\alpha$-Relative Neighborhood Graph ($\alpha$-RNG) pruning heuristic (RobustPrune). This rule enforces directional diversity and injects long-range edges, achieving shorter search paths than hierarchical structures like HNSW [57]. Many other proximity-graph construction algorithms have been proposed [21, 24, 25, 26, 38, 40, 56, 63, 86, 90, 91, 94]. In practice, Vamana and HNSW are the most widely used. However, search-driven graph construction suffers from a fundamental “search bottleneck” [74] requiring millions of random-access memory lookups and thus incurring long build times.

PiPNN (Pick-in-Partitions Nearest Neighbors) [74] speeds up index construction by replacing searches during construction with a partitioning-based build paradigm. Instead of global beam searches, PiPNN recursively decomposes the dataset into overlapping clusters via randomized ball carving and generates candidate edges using cache-friendly many-to-many top-$k$ kernels. This achieves an order-of-magnitude faster index construction across CPUs and accelerators while maintaining equivalent graph quality. In Ginger, we offer both PiPNN and Vamana index builds to give users flexibility and choice.

Inverted Indexes. Inverted-file (IVF) indexes partition vectors into clusters and store each cluster in an inverted list. A query probes a subset of the clusters and scores the vectors in their lists, often using quantized representations followed by higher-precision reranking.

Quantization. Quantization replaces floating-point vectors with compact codes representing regions of the vector space, reducing both index memory and the bytes fetched during distance evaluation [1, 42]. The codes must support fast scoring while preserving enough accuracy to identify the nearest neighbors. Scalar quantization encodes each coordinate independently using $b$ bits to select one of $2^b$ representative values. Product quantization partitions a vector into subvectors and encodes each with an index into a learned codebook; distances are estimated by combining per-subvector table lookups [32, 42]. Rotation-based scalar quantizers first apply a shared random orthogonal transformation, then encode the transformed coordinates. Examples include DRIVE/EDEN [8, 84, 85], RaBitQ [27, 28, 30], and TurboQuant [92]. The representation and scoring kernel must also suit the search access pattern. Graph traversal scores scattered candidates, whereas IVF search scans lists of vectors. Quantization has a rich literature, and we refer readers to the excellent surveys [36, 60] for background on its foundations and applications to nearest-neighbor search. § 3 presents our nested quantizer and SIMD scoring kernels for graph navigation and reranking.

Prior Libraries

We focus on a representative selection of widely used libraries and high-performance ANNS methods. Our selection emphasizes methods that are widely adopted and/or very high performance while covering graph-based and inverted-file search.

DiskANN. DiskANN [41, 46] is Microsoft’s widely used library for in-memory and SSD-backed search using the Vamana proximity graph. Its SSD-backed design enables billion-scale search on a single machine by keeping compressed vectors in memory and fetching graph neighborhoods and full-precision vectors from disk.

ParlayANN. ParlayANN [59, 66] is a highly optimized parallel graph-based ANNS library built on the ParlayLib [12] runtime. It provides deterministic implementations of proximity-graph algorithms, including Vamana, designed to avoid synchronization bottlenecks and scale to large datasets on shared-memory machines.

SVS. Intel’s Scalable Vector Search (SVS) [1] combines Vamana-based search with highly optimized SIMD kernels and compressed vector representations. Its LVQ codec uses per-vector scaling and scalar quantization to reduce memory traffic, while LeanVec [83] combines dimensionality reduction with quantization.

Hnswlib. Hnswlib [58] provides a lightweight, header-only C++ implementation of HNSW [57] with Python bindings and support for custom distance functions. It supports incremental index construction, vector updates and deletions, and multithreaded search, with configurable graph connectivity and search effort.

SymphonyQG. SymphonyQG [27, 35] combines RaBitQ quantization [30] with FastScan [4], storing codes on graph edges to score neighbors sequentially. Its layout aligns vertex degrees with 32-edge FastScan batches, trading increased memory usage from replicated codes for fewer random accesses during graph search.

Faiss. Faiss [22, 43] is Meta’s similarity search library, offering flat, IVF, and graph indexes with scalar and product quantization. Its widely-used CPU implementations support large-scale search, with index and compression choices that provide different tradeoffs between memory usage, query throughput, and recall.

ScaNN. ScaNN [37, 81] is an existing IVF-based similarity search library developed at Google, combining partitioning with anisotropic vector quantization and optimized scoring kernels for maximum inner-product search. Its two-stage pipeline scores candidates using low-bit representations before reranking a smaller set, reducing the cost of evaluating large candidate pools.

Nested TurboQuant (NTQ)

All production-grade ANNS libraries use quantization. Because distance evaluation performs only a small constant number of arithmetic operations per loaded byte, ANNS is limited by memory bandwidth. Compressing coordinates to low-precision codes reduces both memory traffic and the memory footprint of the index.

Graph beam search imposes a specific access pattern on the quantizer: each expansion fetches an arbitrary subset of non-contiguous points in $\mathcal{X}$ and scores each point by scanning across its coordinates. Unfortunately, standard PQ [32, 42], as used in IVF indexes, is ill-suited for this task because loading each of the $M$ subspace lookup tables is expensive relative to scoring a single point. Uniform scalar quantization methods avoid per-subspace codebooks and support fast coordinate-wise scans, but suffer higher quantization error. Recently, rotation-based quantizers [28, 30, 84, 85, 92] have become popular. They keep the fast coordinate-wise scans of uniform scalar quantizers and need no per-subspace tables, while achieving much lower quantization error. A random rotation makes every coordinate approximately Gaussian, so a single scalar codebook serves all coordinates. EDEN [85] and TurboQuant [92] place this codebook non-uniformly at the Lloyd–Max points of the Gaussian [52, 61], which minimizes the mean-squared error per coordinate.

Graph search needs two precisions with conflicting goals. Beam search scores thousands of random candidates per query and needs a compact code that is cheap to load from memory and score. Reranking scores only the final beam, but needs the accuracy of floats to achieve very high recall. A standard recipe is therefore to navigate with aggressive quantization and then rerank the converged beam with floats or higher-precision codes. Storing a second code for reranking, or maintaining the float vectors, wastes significant memory. A single nested code avoids this waste, but only if nesting does not degrade the quality of the codes. We developed Nested TurboQuant (NTQ) to achieve this.

Overview of Our Approach. NTQ builds on TurboQuant [92] and EDEN [8, 85]. It takes the 4-bit Lloyd–Max codebook and splits each of its intervals into $2^k$ finer sub-intervals, which yields a $(4+k)$-bit code. The 4-bit prefix of every code is therefore a complete TurboQuant code for navigation. The full code nearly matches float accuracy for reranking. Search cost stays fixed, while the $k$ additional bits per coordinate trade memory for reranking accuracy. We mostly focus on 10- and 12-bit codes ($k=6$ and 8). Nesting is nearly free, because the rotation makes every coordinate approximately Gaussian, and Gaussian sources are successively refinable [23]. Both levels of NTQ are therefore close to optimal for the rotated coordinates. We make both levels fast to score by evaluating their codebooks in registers rather than memory.

The following subsections describe NTQ in detail for interested readers. Section 3.1 sets up the TurboQuant encoding that NTQ builds on and points out where we deviate from it. Section 3.2 introduces the nested refinement, which is the core of NTQ. Sections 3.3 and 3.4 describe fast scoring kernels for 4-bit navigation and $(4+k)$-bit reranking. All quantization and scoring kernels are implemented in portable SIMD using Highway [87]. For concreteness, we refer to AVX-512 instructions in the text.

Rotation and Codebook

To encode a non-zero vector $x \in\mathbb{R}^d$, NTQ normalizes and rotates it to $y=\sqrt{d}\,R\hat{x}$ with $\hat{x}=x/\lVert x\rVert_2$. It then quantizes each coordinate $y_i$ with a scalar codebook and stores a per-vector scale factor that corrects for the norm and for the shrinkage caused by quantization.

Non-Power-of-Two Rotation. Applying a dense orthogonal matrix $R$ costs $O(d^2)$ operations per vector, which is too expensive. Therefore, we use a randomized Walsh–Hadamard transform [2, 3], which takes $O(d\log d)$ operations. However, this transform is limited to dimensions that are a power of two. Zero-padding $d$ to the next power of two as in EDEN [85] can nearly double the memory footprint and scoring work.

Instead, we factor $d=r\cdot2^\ell$ with $r$ odd and $\ell\geq0$ maximal. Let $S=\operatorname{diag}(\sigma_1,\ldots,\sigma_d)$ with independent uniform random signs $\sigma_i\in\{\pm1\}$. We split $Sx$ into $r$ contiguous blocks of $2^\ell$ coordinates and stack these blocks as the rows of a matrix $X\in\mathbb{R}^{r\times2^\ell}$. We then define $Rx$ as the concatenation of the rows of $QXH_{2^\ell}$. Here $H_{2^\ell}\in\{\pm2^{-\ell/2}\}^{2^\ell\times2^\ell}$ is the normalized (orthonormal) Walsh–Hadamard matrix, so right-multiplication applies the Walsh–Hadamard transform to each block. The matrix $Q$ is an $r\times r$ Haar-random orthogonal matrix, so left-multiplication mixes corresponding coordinates across $r$ blocks. Since $S$, $H_{2^\ell}$, and $Q$ are orthogonal, $R$ is an orthogonal matrix. Evaluating $Rx$ takes $O(d(\ell+r))$ operations, which is $O(d\log d)$ for small constant $r$ (e.g., $r=3$ for common dimensions $d\in\{96,768,1536,3072\}$). For these dimensions, zero-padding to the next power of two would add 33% more codes and distance scoring work.

Gaussian Lloyd–Max Codebook. Following TurboQuant [92], we quantize each rotated coordinate using a symmetric $b$-bit Gaussian Lloyd–Max codebook [52, 61]. The codebook packs $\mathbb{R}_{\geq0}$ using $2^{b-1}$ positive centroids $0<c_0<\cdots<c_{2^{b-1}-1}$ separated by mid-point thresholds $t_1,\ldots,t_{2^{b-1}-1}$. Each coordinate $y_i$ stores its sign $\operatorname{sgn}(y_i)\in\{\pm1\}$ and the index $u_i\in\{0,\ldots,2^{b-1}-1\}$ of the centroid nearest to $\lvert y_i\rvert$, giving reconstruction $\tilde{y}_i=\operatorname{sgn}(y_i)c_{u_i}$. NTQ uses this codebook with $b=4$ for navigation, and Section 3.2 refines its intervals for reranking.

Norm and Shrinkage Rescaling. Inner products with quantized vectors are biased unless they are corrected. Under the standard normal density $\phi(z)=(2\pi)^{-1/2}e^{-z^2/2}$, the $b$-bit codebook incurs a per-coordinate mean-squared error

with $t_0=0$ and $t_{2^{b-1}}=\infty$. Because each centroid $c_u$ is the conditional mean of its interval, $\mathbb{E}[(y_i-\tilde{y}_i)\tilde{y}_i]=0$, which gives $\mathbb{E}[y_i\tilde{y}_i]=\mathbb{E}[\tilde{y}_i^2]=1-D_b$. Normalizing $\tilde{y}$ using the groundtruth shifts inner products with $Rx$ by $\mathbb{E}[\langle Rx,\tilde{y}\rangle]/\sqrt{\mathbb{E}[\lVert\tilde{y}\rVert_2^2]}=\sqrt{1-D_b}$. Rotation-based quantizers correct this bias in different ways. EDEN [85] divides by $\langle Rx,\tilde{y}\rangle$. TurboQuant [92] uses $(b-1)$-bit Lloyd–Max quantization and reserves 1 bit per coordinate for a quantized Johnson–Lindenstrauss (QJL) sign sketch of the quantization residual. We store the per-vector scale factor $s_b(x)=\lVert x\rVert_2/(\sqrt{1-D_b}\lVert\tilde{y}\rVert_2)$, so that $s_b(x)\tilde{y}$ estimates $Rx$ without shrinkage bias. This costs a single float per vector and leaves all $b$ bits to the codebook. By orthogonality of $R$, we then estimate $\langle q,x\rangle=\langle Rq,Rx\rangle$ as $s_b(q)s_b(x)\langle\tilde{q},\tilde{y}\rangle$ for a quantized query or $s_b(x)\langle Rq,\tilde{y}\rangle$ for an unquantized query.

Nested Refinement

For reranking, NTQ adds $k$ refinement bits per coordinate to the 4-bit code. A standard way to add such bits is two-stage residual quantization, which encodes the residual $y_i-\tilde{y}_i$ of the 4-bit reconstruction with a second codebook shared across all 4-bit intervals [22, 42]. However, because the conditional distribution of a rotated coordinate varies significantly between the 4-bit intervals, a shared residual codebook is suboptimal. In our experiments, residual quantization achieves lower recall than the nested codebook described next (see § 6.3).

We instead split each positive 4-bit interval $[t_u,t_{u+1})$ into $2^k$ contiguous sub-intervals with centroids $c_{u,v}$ for $v\in\{0,\ldots,2^k-1\}$ (Figure 2a). Here $u\in\{0,\ldots,7\}$, $t_0=0$, and $t_8=\infty$. The centroids $c_{u,0},\ldots,c_{u,2^k-1}$ form a $2^k$-entry Lloyd–Max codebook for the standard normal density restricted to $[t_u,t_{u+1})$. Each 4-bit interval therefore gets its own refinement codebook, adapted to the shape of $\phi(z)$ on that interval. Encoding first finds the 4-bit interval $u_i$ of $|y_i|$ as in Section 3.1 and then the nearest centroid $c_{u_i,v_i}$ within that interval. Since the sub-intervals never cross the 4-bit thresholds, each coordinate’s $(4+k)$-bit code splits into its 4-bit code $u_i$ and a $k$-bit refinement code $v_i$. The $(4+k)$-bit reconstruction is $\tilde{y}_i^{(4+k)}=\operatorname{sgn}(y_i)c_{u_i,v_i}$. Its scale factor $s_{4+k}(x)$ follows Section 3.1, with the mean-squared error $D_{4+k}$ summed over all $8\cdot2^k$ positive sub-intervals.

Why Nesting Is Nearly Free. Forcing the $(4+k)$-bit code to refine the 4-bit intervals could cost accuracy, because an unconstrained $(4+k)$-bit Lloyd–Max codebook would place all of its thresholds freely. This constraint costs almost nothing, because Gaussian sources are successively refinable under mean-squared error [23].

Storage Layout. The 4-bit codes, packed two per byte, and their per-vector scale factor form the navigation array read by beam search. The refinement codes and $s_{4+k}(x)$ form a separate array read only for reranking, so beam search loads no extra bytes.

Vectorized 4-Bit Scoring for Beam Search

Each coordinate of a data vector is stored as a 4-bit code for beam search, so the codebook has only 16 entries. To score candidates with fast 8-bit integer dot-product instructions, we round these 16 centroids to int8 values and quantize the query coordinates to int8 as well. Each codebook entry then occupies a single byte, so the entire codebook forms a 16-entry lookup table. We load this table into a vector register. Scoring a candidate looks up each of its 4-bit codes in this register and accumulates the products with the query coordinates.

Codes and Table Entries. For each database vector $x$, coordinate $i\in\{0,\ldots,d-1\}$ packs its sign and 3-bit index $u_i\in\{0,\ldots,7\}$ into a 4-bit nibble $n_i\in\{0,\ldots,15\}$, which serves directly as the table index. The table holds the 16 signed centroids $\pm c_0,\ldots,\pm c_7$ quantized to int8 as $\pm\operatorname{round}(127c_u/c_7)$, so looking up $n_i$ yields $\bar{y}_i\in[-127,127]$. For a query $q$, we quantize the rotated coordinates to int8 as $\bar{q}_i=\operatorname{round}(127(Rq)_i/\lVert Rq\rVert_\infty)\in[-127,127]$. The scale factors $\bar{s}_4(x)=\lVert x\rVert_2/(\sqrt{1-D_4}\lVert\bar{y}\rVert_2)$ and $\bar{s}(q)=\lVert q\rVert_2/\lVert\bar{q}\rVert_2$ absorb the int8 scales, so $\bar{s}(q)\bar{s}_4(x)\langle\bar{y},\bar{q}\rangle$ estimates $\langle q,x\rangle$.

Shifted Table Entries. We accumulate the products with the x86 8-bit integer dot-product instruction v p d p b u s d [39], which multiplies unsigned by signed bytes and accumulates into 32-bit integers. The table therefore stores the shifted unsigned entries $\bar{y}_i+128\in\{1,\ldots,255\}$, while the query bytes $\bar{q}_i$ remain signed. The shift adds a query-dependent, candidate-independent bias:

We precompute this bias per query and subtract it from each candidate’s accumulated dot product before multiplying by $\bar{s}(q)\bar{s}_4(x)$.

Table Lookups. The byte shuffle instruction pshufb performs the lookups. It replaces each index byte in $\{0,\ldots,15\}$ by the table entry at that position. With a copy of the table in each 128-bit lane, one AVX-512 shuffle performs 64 lookups. For each candidate vector, coordinate pairs $(n_{2j},n_{2j+1})$ are packed into the low and high nibbles of byte $j\in\{0,\ldots,\lfloor d/2\rfloor-1\}$. Rather than unpacking nibbles into coordinate order via cross-lane shuffles, we split $\bar{q}$ into contiguous even coordinates $(\bar{q}_0,\bar{q}_2,\ldots)$ and odd coordinates $(\bar{q}_1,\bar{q}_3,\ldots)$. Each SIMD step loads one vector register of packed code bytes. A bitwise mask (0x0F) extracts the even indices, and a 4-bit right shift followed by the same mask extracts the odd indices. Two shuffles, each performing 64 table lookups, map both index streams to $\bar{y}_i+128$, and two vpdpbusd instructions accumulate their dot products with the even and odd query coordinates. Since each step takes only a few SIMD instructions, scoring is dominated by fetching neighbors from dispersed memory addresses. We therefore issue software prefetches several candidates ahead during neighbor-list expansion to hide DRAM latency.

Fast (4+k)-Bit Reranking

Reranking fetches the refinement codes of the top candidates. It scores each candidate against the unquantized rotated query $Rq$ as $s_{4+k}(x)\langle Rq,\tilde{y}^{(4+k)}\rangle$. Unlike the int8 table of Section 3.3, reranking computes in float precision. Refinement codebooks for small $k$ fit in registers, but the 10- and 12-bit codebooks have 512 or 2048 positive centroids and need memory gathers, which take roughly 80% of reranking time at $d=4096$.

Piecewise-Cubic Codebook Approximation. We therefore replace the table with a piecewise-cubic polynomial that computes each centroid $\hat{c}_{u,v}$ in registers from its integer index. The coefficients of each piece are fit offline by least squares to the codebook centroids.

On each of the seven bounded intervals ($u\leq6$), $\phi(z)$ is smooth and bounded away from zero. A single cubic per interval therefore fits all $2^k$ sub-centroids with small error. On the unbounded tail $[t_7,\infty)$, $\phi(z)$ decays rapidly and the sub-intervals grow progressively wider, so a single cubic cannot fit all tail centroids (Figure 2b). We split the $2^k$ tail sub-intervals into $M_k$ equal segments of $B_k=2^k/M_k$ sub-intervals each. $M_k$ must be a power of two so that $B_k$ is one as well, which lets each SIMD lane find its segment with a shift and a mask. We choose $M_6=8$ and $M_8=16$, the largest such values for which the coefficients of all $7+M_k$ segments fit in one 16-lane float register per polynomial degree for $k=6$, and in two for $k=8$.

In-Register SIMD Evaluation. A coordinate with codes $(u,v)$ belongs to segment $s=u$ with local index $\tau=v$ if $u<7$. In the tail, it belongs to segment $s=7+\lfloor v/B_k\rfloor$ with $\tau=v\bmod B_k$. We evaluate 16 coordinates in parallel, and each SIMD lane computes $(s,\tau)$ with a shift and a mask. Each lane then selects its segment’s coefficients $(a_{s,0},\ldots,a_{s,3})$ with an in-register permutation (vpermp s for $k=6$, or two-register vpermi2ps for $k=8$). Finally, it evaluates the cubic in Horner form with three fused multiply-adds:

Replacing memory gathers with in-register permutations and fused multiply-adds roughly halves 10- and 12-bit reranking latency, with no loss in recall.

Search Optimizations

Although the basic beam search (Algorithm 1) is simple, ANN systems vary significantly in the details of how the search is implemented. In Ginger, we build on our fast 4-bit scoring kernel (Section 3.3) with search optimizations that reduce memory traffic and the overhead of maintaining the candidate beam.

Search on Projected Coordinates

On high-dimensional datasets, fetching and scoring even quantized candidate vectors consumes substantial memory bandwidth. In Ginger, we reduce this cost by projecting database vectors and queries into a lower-dimensional space using Principal Component Analysis (PCA) [44]. We encode the projected vectors with 4-bit navigation codes and score them using the kernel from Section 3.3. Each candidate evaluation therefore reads and scores fewer coordinates, reducing memory traffic beyond quantization alone.

The database vectors can be projected offline, whereas each incoming query must be multiplied by the projection matrix $P$ before navigation begins. This matrix multiplication is itself memory-bound and competes with graph traversal for memory bandwidth when queries run in parallel across threads. To alleviate this bottleneck, we also quantize the rows of $P$ to 4 bits, reducing the data fetched during query projection. Our results show that this does not impair recall (Figure 8).

Candidate Prefiltering

During beam search, most scanned neighbors $v \in N(p)$ are not useful and will never enter the beam $B$. On high-dimensional datasets, we can use a cheaper filter distance $d_{\mathrm{filt}}(q,v)$ to prune unpromising candidates early and thus avoid computing the 4-bit navigation distance $d_{\mathrm{nav}}(q,v)$. Only the neighbors with $d_{\mathrm{filt}}(q,v)$ below a cutoff threshold are scored with $d_{\mathrm{nav}}$.

This general idea has been used in several recent systems [15, 29, 45, 53, 54, 82]. For example, ADSampling [29] uses Johnson–Lindenstrauss projections for Euclidean distance, and FINGER [15] uses angle approximation. However, prior methods rely on a specific relationship between the two distance measures so that a candidate’s filter score can be compared against the navigation distance $d_{\mathrm{nav}}(q,b_L)$ of the furthest point $b_L \in B$ [89].

Our Approach. We instead allow pairing arbitrary filter and navigation measures, such as Hamming distance and inner product. All we require is that each measure independently approximates the distance ordering relative to $q$, which makes this framework flexible. This decoupling works because beam admission depends only on relative distance ordering around $q$ rather than calibrated distance values. Any coarse sketch whose ranking correlates with $d_{\mathrm{nav}}(q,\cdot)$ can separate the few promising neighbors from the many that lie far behind the beam boundary. At the same time, $d_{\mathrm{filt}}$ has higher variance than $d_{\mathrm{nav}}$ and cannot replace it for graph navigation, even in early hops. Navigating directly with $d_{\mathrm{filt}}$ commits the greedy traversal to its ranking errors and can steer the beam away from the query neighborhood. Using $d_{\mathrm{filt}}$ solely as a conservative gate backed by $d_{\mathrm{nav}}$ preserves the 4-bit search trajectory while skipping full distance evaluations on clearly unpromising neighbors. Because the two measures may not be comparable, we derive the filter cutoff from the beam using $d_{\mathrm{filt}}$ itself. Thresholding against $d_{\mathrm{filt}}(q,b_L)$ alone would be brittle, because a noisy filter can assign $b_L$ a small distance by chance and prune candidates that beat $b_L$ under $d_{\mathrm{nav}}$. While the beam is filling up ($|B| < L$), prefiltering is disabled. Once the beam is full (at step $t_0$), we compute the mean filter distance $\mu_t$ over the $w$ furthest points at the tail of $B = (b_1, \ldots, b_L)$ to smooth out single-point noise. We then set the cutoff $\tau_t$ to the running average of $\mu_s$ over all steps since $t_0$:

If $b_L$ did not change on step $t$, we reuse $\mu_t = \mu_{t-1}$. As the beam improves, $\mu_t$ decreases, so $\tau_t$ tightens over time while staying slightly looser than $\mu_t$. We instantiate this scheme with two filters:

TurboSlice. Because the random rotation in Section 3.1 spreads a vector’s energy evenly across all rotated coordinates, any prefix of $d_{\mathrm{ts}} < d$ rotated 4-bit coordinates acts as a low-dimensional sketch, which provides an unbiased estimator of the dot product [17]. This sketch sits at the front of the 4-bit navigation code and requires no extra vector storage. For typical prefix lengths $d_{\mathrm{ts}} \in\{128,256\}$, the filter reads only one or two cache lines and skips loading the rest of the vector for rejected neighbors. We score the prefix with the 4-bit kernel of Section 3.3 over the first $d_{\mathrm{ts}}$ coordinates and rescale by a precomputed prefix norm factor $\bar{s}_4^{(d_{\mathrm{ts}})}(x)=\lVert x\rVert_2/(\sqrt{1-D_4}\lVert\bar{y}_{1:d_{\mathrm{ts}}}\rVert_2)$.

1-Bit Sparse Johnson–Lindenstrauss (JL). ParlayANN [59] already offers a filter based on JL, whose details have not been published so far, however. This filter maps each vector $x \in\mathbb{R}^d$ to a $d_{\mathrm{jl}}$-bit sign sketch $h(x) \in\{0,1\}^{d_{\mathrm{jl}}}$ with bits $h_i(x)=1[\langle a_i,x\rangle> 0]$ (we usually use $d_{\mathrm{jl}} = 1024$). We pack the sketches into 64-bit words and compare them by Hamming distance $\lVert h(q) \oplus h(v)\rVert_1$. Because our cutoff (3) only compares filter scores against other filter scores, we can use the Hamming distances directly without reconstructing angles or norms. To make projecting the query fast, it suffices to use a sparse random projection matrix $A \in\{-1,0,+1\}^{d_{\mathrm{jl}}\times d}$ with only a few non-zero entries per row.

While our experiments show that PCA is generally more effective than the prefilters and they do not stack well (both reduce memory traffic in a similar way), we note that the prefilters are quite useful in scenarios where we cannot work with PCA. One example is network-constrained deployments, where we do not want to send multiple sets of vectors per query over the wire. Here, taking a TurboSlice prefix does not incur additional traffic. Another example is extremely high-dimensional vectors, where the projection matrix is so large that it slows down projection.

Beam Management

A naive beam search maintains two priority queues for the closest unexplored vertices and the furthest points in $B$. However, priority-queue operations take $O(\log L)$ time and have poor cache locality. Following ParlayANN [59] and SVS [1], instead keep $B$ in a single array of size at most $L$ sorted by distance. Each entry stores a flag indicating whether it has been explored, and we track the index of the first unexplored entry. Picking the next vertex to expand then takes $O(1)$ time. Because $B$ is sorted, the furthest element $b_L$ sits at the end of the array and provides the distance cutoff for entering the beam. Inserting new points into the sorted array one at a time would take $O(L)$ time per point. Instead, when expanding a vertex $p \in B$, we keep only the unvisited neighbors that beat $b_L$, sort the survivors, and merge them into $B$ in a single linear pass.

Later in the search, most neighbors have already been visited or fail to beat $b_L$, so merging after every expansion scans the whole beam just to insert one or two points. Once the initial phase of the search is over, we therefore batch across consecutive expansions. We collect unvisited neighbors from several unexplored beam vertices, score them together, and merge the survivors into $B$ in a single pass. Batching also exposes a longer stream of candidates, which helps amortize startup latency (due to prefetching) in the TurboQuant scoring kernel.

Graph Compression

In Ginger, we also reduce the memory occupied by the proximity graph itself, which can exceed the footprint of the quantized vectors on low-dimensional datasets. For example, a 96-dimensional vector occupies 144 bytes at 12 bits per coordinate, whereas a flat adjacency list with 64 four-byte slots and a degree counter occupies 260 bytes. We therefore compress the graph losslessly while keeping decoding fast enough to avoid slowing search.

Our approach first relabels vertices so that neighbors receive nearby IDs (Section 5.1), then stores each sorted neighbor list as gaps between consecutive IDs. We encode these gaps with a codec that packs small values into fewer than eight bits and decodes four at a time using a few SIMD instructions (Section 5.2).

Gap encoding. Let $v_1 < v_2 < \cdots< v_{\operatorname{deg}(u)}$ be the sorted neighbor IDs of a vertex $u$. Gap encoding stores the first ID $g_1 = v_1$, followed by the differences $g_i = v_i - v_{i-1}$ for $2 \le i \le\operatorname{deg}(u)$. A gap $g_i$ needs about $\log_2(g_i + 1)$ bits, so small gaps mean a small graph. A prefix sum over the gaps recovers the IDs.

Graph Reordering

To reduce gaps between consecutive neighbor IDs, we place well-connected groups of vertices into contiguous ID ranges, an approach well studied for web and social graphs [5, 11, 13, 14, 16, 51, 70, 75, 77] and inverted indexes [9, 10, 19, 20, 76, 78]. In Ginger, recursive graph partitioning (RGP) uses a parallel multilevel partitioner [33, 34] to recursively split the graph into balanced blocks with few crossing edges. We number the small leaf blocks in recursion order, assign consecutive IDs within each block, and permute the vectors accordingly.

Balanced graph partitioning only works on undirected graphs, hence we symmetrize the graph by adding the reverse of every edge. Reciprocal connections then carry twice the weight, reflecting the potential for long gaps in both adjacency lists when their endpoints are separated. RGP yields smaller gaps than recursive graph bisection [19] on all six datasets and is faster to compute on all but the smallest (Section 6.3).

AdaptiveGap: Sub-Byte Gap Coding with SIMD Decoding

Beam search decodes a neighbor list at every expansion, so graph compression must keep decoding cheap enough to preserve query throughput. In codecs such as PrefixVarint [18], each gap takes one

to five bytes and begins with a unary length prefix, so locating the next gap requires reading the current gap’s length.

StreamVByte. We build on StreamVByte [48], which removes this dependency by storing lengths separately from gaps. It encodes groups of four gaps using a control byte with four 2-bit length selectors and a separate payload holding the gap values back to back. Each selector specifies a gap length of one to four bytes. To decode a group, StreamVByte loads 16 payload bytes into a SIMD register and uses one byte shuffle (pshufb) to distribute the values among four 32-bit lanes. A precomputed shuffle mask for each of the 256 control bytes specifies which payload bytes to copy into each lane, and a SIMD prefix sum recovers the neighbor IDs. However, rounding each gap to whole bytes wastes space; for example, a 9-bit gap requires two bytes.

AdaptiveGap. AdaptiveGap retains StreamVByte’s single-shuffle decoding while adding adaptive bit widths and optional separate storage of the first neighbor ID. Each neighbor list selects one of 16 modes, each specifying four bit widths that the 2-bit selectors choose among. Mode 0 uses the widths $\{8, 16, 24, 32\}$, which corresponds to StreamVByte, while the other modes use sub-byte widths, such as $\{4, 12, 20, 28\}$. For example, StreamVByte stores the gaps $3$, $9$, $1000$, and $5$ in $1 + 2 + 2 + 1 = 5$ bytes. In the mode $\{4, 12, 20, 28\}$, they occupy $4 + 4 + 12 + 4 = 24$ bits, or 3 bytes, with the same single control byte.

AdaptiveGap packs gaps without padding within each byte-aligned group, so adjacent gaps can share a byte. In Figure 3, for example, the gap 9 starts at bit 4 of byte 0. A single shuffle gathers the bytes covering each gap into a 32-bit lane, and a right shift and mask isolate its value. For this to work, all bytes that contain a gap must fit into its lane. A gap of width $w$ that starts at bit offset $o$ of a byte spans $o + w$ bits, so every gap must satisfy $o + w \le32$. In mode 0, all gaps are byte-aligned, so the offset is always 0. In the other modes, all widths are even, so the offset is at most 6, and widths up to 26 bits are safe. If all widths of a mode are multiples of 4, the offset is 0 or 4, and widths up to 28 bits are safe. Unlike in StreamVByte, the shuffle mask depends on both the mode and the control byte, so we precompute a mask, along with the per-lane shifts and bit masks, for each of the 16 × 256 combinations.

Vector (PDF)

The first entry $g_1 = v_1$ is an absolute ID and can require 30 bits at $n = 10^9$, potentially forcing the entire list onto mode 0. AdaptiveGap avoids this by optionally storing the first ID separately as a varint, called the anchor. The encoder picks the mode, with or without the anchor, that minimizes the encoded size, and a 1-byte tag at the start of the list records its choice. As in a CSR layout, an offset array locates each encoded list, and each list stores its degree.

Summary. Together, reordering and AdaptiveGap shrink the graph by 2.1× on average (up to 2.5×) relative to a CSR layout without slowing down queries (§ 6.3). Compared with StreamVByte on the same ordering, AdaptiveGap stores an average of 0.9 fewer bits per edge (up to 1.2 bits). This reduction saves a further 5.4% of graph memory (up to 7.6%).

Experimental Evaluation

We compare Ginger with seven widely used ANNS libraries across 14 large-scale datasets ranging up to a billion points and up to four-thousand dimensions. We assess query throughput, memory footprint, and indexing time for each method. Subsequently, we run ablation studies to isolate where our performance gains come from and how key design choices affect performance, including standalone evaluations of NTQ and AdaptiveGap (§ 6.3).

Experimental Setup

Machine. We use a Google Cloud c4-highmem-288 instance, a dual-socket server with two 72-core Intel Xeon 6985P-C processors (Granite Rapids) and 2.3 TB of RAM across 6 NUMA nodes.

Datasets. We evaluate Ginger on 14 public ANNS datasets covering Euclidean and maximum inner-product search (MIPS), summarized in Table 1. Six low-dimensional datasets ($d \le200$) comprise GloVe and five billion-vector benchmarks spanning image, web-search, and cross-modal retrieval. Eight high-dimensional datasets ($768 \le d \le4096$) contain up to 101 million vectors and cover text, encyclopedia, scientific, multimodal, and LLM embeddings. Input coordinates are 8-bit integers for MS-SPACEV and BigANN, and 32-bit floats for the remaining twelve datasets.

Dataset	$d$	$n$	$n_q$	Type	Metric
Low dimensional
GloVe [67]	100	1.2M	10k	float	MIPS
Deep [7]	96	1B	10k	float	L2
MS-Turing [80]	100	1B	100k	float	L2
MS-SPACEV [80]	100	1B	29k	int8	L2
BigANN [42]	128	1B	10k	uint8	L2
Text2Image [80]	200	1B	100k	float	MIPS
High dimensional
Wiki-Cohere [71]	768	35M	5k	float	MIPS
Wiki-All [65]	768	88M	10k	float	MIPS
MS-MARCO [79]	768	101.07M	9376	float	MIPS
DBpedia-1536 [68]	1536	999k	1k	float	L2
OpenAI-arXiv [64]	1536	2.32M	20k	float	L2
DataComp-DR [6]	1536	12.78M	1k	float	L2
DBpedia-3072 [69]	3072	999k	1k	float	L2
Wiki-Qwen [55]	4096	500k	100k	float	L2

Existing Libraries. We compare Ginger against the seven libraries introduced in Section 2.2: the Vamana implementations in ParlayANN [59, 66], SVS [1], and DiskANN [41, 46]; HNSW [57] from Hnswlib [58]; the IVF implementations in ScaNN [37, 81] and Faiss [22]; and SymphonyQG [35] from the RaBitQ-Library [27]. Together, these libraries form a comprehensive comparison set spanning both widely adopted industrial systems and highly optimized research implementations. We select SymphonyQG to represent methods that store auxiliary data on graph edges because of its reported query performance and scalable, multithreaded C++ implementation [27, 35].

Environment. All C++ implementations are compiled with Clang v19.1.7. DiskANN is built with Rust v1.97.0. We use full compile-time (-O3) and link-time optimizations (-lto), and native architecture tuning (-march=native). To avoid allocator contention and ensure a fair comparison, we link all implementations against jemalloc v5.3.0. This change is either neutral or positive on QPS for all methods. To ensure accurate query timings, we perform one warm-up run (discarded) followed by 5 timed runs of the query set for each parameter configuration and report the average throughput. To prevent cache interference across runs, we flush the CPU cache between runs.

Query Setup. We evaluate query throughput without batching: individual queries are processed in parallel across threads. To obtain the Pareto-optimal frontier of throughput at each recall level, we sweep the search beam width $L_{\mathrm{search}}$ with select values in the range $[10, 2000]$ for graph-based indexes. For IVF-based indexes, we sweep the number of probed leaf clusters $n_{\mathrm{probe}}$ over select values in $[1, 1000]$ and the number of candidates to rerank $n_{\mathrm{rerank}} \in\{2k, 4k, 8k, 16k, 32k, 64k\}$. For multi-level SCANN, we additionally sweep the number of top-level clusters to probe on two-level trees, and three of the three-level trees we evaluate selected pairs of middle- and top-level probe counts to cover various routing profiles that vary the search cost at each level, which we model by the amount of data loaded. See Appendix § 9 for more details.

Table 5 in Appendix § 9 summarizes the vector representations used by each library. On the 8-bit integer datasets (MS-SPACEV and BigANN), all graph libraries operate directly on the native int8/uint8 coordinates without quantization. On high-dimensional float datasets ($d \ge768$), libraries combine dimensionality reduction (PCA, OPQ, or JL prefiltering) or 1–2-bit spherical codes with higher-precision reranking. On low-dimensional float datasets ($d \le200$), dimensionality reduction degrades accuracy so we omit it.

Index Parameters. All graph-based indexes are constructed with maximum out-degree $R = 64$ and construction beam width $L = 128$ (corresponds to $M = 32$, $\epsilon_{\mathrm{fc}} = 128$ for HNSWLIB). P\textsc{n}N uses the standard parameters from the original paper: leaf size $L = 1024$ and tree fanout (10, 3). On GloVe, we use $R = 100$, $L = 250$ for Vamana, and $M = 50$, $\epsilon_{\mathrm{fc}} = 250$ for HNSWLIB. For DiskANN methods we use the standard two build passes, except for DiskANN which only supports single-pass. We instead double the insertion beam-width to match the build effort and improve index quality. For SCANN, we use anisotropic vector quantization (AVQ = 2.5) and spilling with orthogonality-amplified residuals (SOAR = 1.5, with $\lambda= 1.0$ on GloVe and Wiki-Cohere, and $\lambda= 2.0$ on DataComp-DR and DBpedia). We set the noise shaping threshold to NST = 0.2 for unit-norm datasets (NST = 0.1 on OpenAI-arXiv, DataComp-DR, and DBpedia), and scale it proportionally to the average vector norm on non-unit-norm datasets (NST = 24.0 on MS-SPACEV, 100.0 on BigANN, 2.75 on Wiki-Cohere, and 2.0 on MS-MARCO). Refer to Table 6 for the dataset-specific parameters such as RobustPrune $\alpha$ values, partition sizes, and IVF quantizer configurations. All methods use multi-threading for the builds.

Dataset

$\alpha_{\mathrm{PiPNN}}$

$\alpha_{\mathrm{Vamana}}$

Ginger

SVS

ScaNN

$C_1$

$C_2$

$C_3$

Rerank

OPQ

IVF

PQ

Refine

GloVe

0.87

0.95

–

–

–

2,000

–

–

float

–

IVF1024

PQ50x4fsr

RFlat

Deep

1.15

1.10

–

–

–

2,398,082

17,916

134

bf16

OPQ48_96

IVF1048576_HNSW32

PQ48x4fsr

Refine(SQbf16)

MS-Turing

1.08

1.10

–

–

–

2,500,000

18,420

136

bf16

OPQ50_100

IVF1048576_HNSW32

PQ50x4fsr

Refine(Pad128,SQbf16)

MS-SPACEV

1.13

1.10

–

–

–

2,500,000

18,420

136

int8

OPQ50_100

IVF1048576_HNSW32

PQ50x4fsr

Refine(Pad128,SQ8_direct_signed)

BigANN

1.15

1.10

–

–

–

3,205,129

21,739

147

bf16

OPQ64_128

IVF1048576_HNSW32

PQ64x4fsr

Refine(SQ8_direct)

Text2Image†

0.95

1.00

–

–

–

5,000,000

–

–

–

OPQ100_200

IVF1048576_HNSW32

PQ100x4fsr

Refine(SQbf16)

Wiki-Cohere

0.98

0.98

248

256

192

35,000

350

–

bf16

OPQ96_192

IVF65536_HNSW32

PQ96x4fs

Refine(SQbf16)

Wiki-All

0.93

0.95

248

256

192

87,556

1,369

–

bf16

OPQ96_192

IVF131072_HNSW32

PQ96x4fs

Refine(SQbf16)

MS-MARCO

0.96

0.98

248

256

256

101,071

1,580

–

bf16

OPQ128_256

IVF16384_HNSW32

PQ128x4fs

Refine(SQbf16)

DBpedia-1536

1.05

1.00

368

256

256

2,048

–

–

int8

OPQ96_192

IVF2048

PQ96x4fs

Refine(SQ8)

OpenAI-arXiv

1.10

1.05

368

256

446

10,000

300

–

int8

OPQ128_256

IVF4096

PQ128x4fs

Refine(SQ8)

DataComp-DR

1.15

1.15

624

640

512

12,805

201

–

bf16

OPQ256_512

IVF98304_HNSW32

PQ256x4fs

Refine(SQbf16)

DBpedia-3072

1.05

1.00

496

256

384

2,048

–

–

int8

OPQ96_192

IVF2048

PQ96x4fs

Refine(SQ8)

Wiki-Qwen

0.95

1.00

880

768

384

1,024

–

–

bf16

OPQ192_384

IVF2048

PQ192x4fs

Refine(SQbf16)

To support reproducibility, we will release our experimental setup, including the benchmark harness, build scripts, and dataset configurations alongside.

Comparison with other Libraries

We evaluate the libraries along three dimensions: query throughput, memory footprint, and indexing time. These three properties jointly comprise the bedrock of index performance. We use geometric means for comparing across datasets. In general: Ginger produces smaller indexes which support higher query throughput with less indexing time as compared with all other libraries.

Query Throughput. Figure 4 shows throughput (queries per second) with respect to recall. Ginger leads on 13 of 14 datasets across the [90%, 100%] recall range and in area under the QPS-recall curve (AUC). At 95% recall, its mean speedup over the fastest competitor on each dataset is 1.8× overall and 2.0× on high-dimensional datasets, with the largest dataset-specific gain of 2.7× on Wiki-Cohere. The strongest competitors on high-dimensional datasets are SymphonyQG and SVS. The only exception is BigANN, whose byte coordinates we do not encode with TurboQuant; there, SVS is 4% faster at both 90% and 95% recall. Because different competitors are second-best on different datasets, the advantage over any individual library across completed datasets is larger. In AUC, Ginger achieves a geometric mean gain of 2.35× over ParlayANN, 2.38× over SVS, 2.42× over SymphonyQG, and 2.79× over DiskANN.

The IVF indexes Faiss and ScaNN trail the graph methods across all datasets, with Ginger achieving a geometric mean AUC gain of 10.3× over ScaNN and 11.7× over Faiss.

Memory Footprint. The memory comparison exposes two different sources of savings: graph compression on low-dimensional datasets and vector quantization on high-dimensional datasets. In Figure 5, we compare the memory footprints. We split each index into five parts. Graph is the adjacency structure, which only Ginger compresses. Raw Vectors are the uncompressed vectors, for indexes that keep them. Quantized Vectors (Navigation) are the codes scored during graph traversal or IVF scanning, including JL sketches and, for IVF indexes, the inverted lists and the coarse quantizer. Quantized Vectors (Reranking) are the higher-precision codes used to rerank candidates instead of raw vectors. Other covers ID remapping tables and locks.

On the four low-dimensional datasets in Figure 5, Ginger has the smallest index of all graph-based methods. It is on average 1.54× (up to 1.65×) smaller than SVS, the most compact competitor. Most of this saving comes from graph compression. The graph of Ginger takes on average 111 bytes per vector, compared with 260 bytes for the flat adjacency arrays of SVS and ParlayANN. Only the IVF indexes Faiss and ScaNN are competitive with regards to memory footprint on low-dimensional datasets.

On high-dimensional datasets the embeddings themselves dominate the memory footprint. Ginger needs on average 43% of the raw vector size across all eight high-dimensional datasets due to NTQ with 12 bits. ParlayANN, DiskANN, and Hnswlib keep the raw float vectors and are 2.7× larger. SymphonyQG is 7.4× larger because of its per-edge codes. SVS, Faiss, and ScaNN are smaller on some datasets, by up to 1.6× (Faiss on OpenAI-arXiv), mainly because they rerank with 8-bit instead of 12-bit codes. SVS uses 19.8% less memory in the geometric mean across all eight high-dimensional datasets. However, SVS is 2.9× slower in the geometric mean at 95% recall. It also reaches lower peak recall than 12-bit Ginger on every dataset. With 8-bit NTQ, Ginger uses less memory than SVS on all datasets, still achieves 2.6× higher mean QPS at 95% recall and higher peak recall on seven of the eight datasets.

Indexing Time. These memory savings require additional pre- and post-processing, so we compare complete index construction times, including graph reordering, compression, quantization, and PCA. Table 2 breaks down Ginger (PiPNN) builds into graph construction, graph compression, and quantization plus PCA. Fast graph construction comes from PiPNN [73, 74]; quantization is fast and grouped with PCA to save space.

Dataset

Quantization & PCA

Graph Compression

Graph Construction

Total

Ginger (Vamana) (No Compression)

SVS*

ParlayANN

DiskANN

SymphonyQG

Hnswlib

ScaNN†

Faiss

Low dimensional

GloVe

<1s

3s

1s

4s

7s

1m 11s

13s

8s

14s

12s

7s

2s

Deep

42s

16m 3s

17m 44s

34m 30s

1h 8m

9h 31m

2h 13m

2h 25m

OOM

3h 34m

38h 23m

57m 51s

MS-Turing

48s

20m 9s

18m 31s

39m 28s

49m 0s

18h 53m

1h 46m

1h 51m

OOM

2h 58m

41h 55m

1h 6m

MS-SPACEV

–

13m 21s

17m 55s

31m 16s

1h 37m

16h 4m

2h 4m

1h 44m

OOM

3h 11m

41h 52m

1h 7m

BigANN

–

16m 12s

18m 18s

34m 30s

1h 40m

5h 40m

2h 47m

2h 20m

OOM

3h 14m

31h 17m

1h 9m

Text2Image

1m 30s

15m 52s

20m 24s

37m 47s

1h 2m

13h 54m

4h 30m

1h 41m

OOM

OOM

OOM

1h 28m

High dimensional

Wiki-Cohere

17s

28s

49s

1m 34s

5m 9s

19m 56s

8m 16s

9m 20s

7m 33s

18m 37s

7m 33s

3m 52s

Wiki-All

43s

1m 13s

2m 0s

3m 56s

10m 45s

40m 25s

13m 38s

20m 41s

40m 52s

39m 59s

10m 0s

9m 7s

MS-MARCO

50s

2m 5s

2m 34s

5m 29s

18m 53s

1h 10m

30m 14s

33m 28s

47m 17s

1h 3m

13m 35s

9m 47s

DBpedia-1536

2s

2s

2s

6s

9s

31s

8s

24s

24s

36s

19s

46s

OpenAI-arXiv

4s

3s

4s

11s

22s

1m 8s

23s

1m 0s

50s

…

DataComp-DR

15s

10s

27s

52s

2m 19s

5m 47s

10m 53s

6m 32s

9m 57s

8m 49s

4m 20s

4m 13s

DBpedia-3072

11s

2s

5s

18s

33s

1m 8s

11s

48s

48s

1m 6s

51s

50s

Wiki-Qwen

22s

1s

5s

29s

35s

1m 10s

5s

30s

36s

39s

1m 16s

1m 34s

With PiPNN, Ginger builds fastest on 11 of 14 datasets, achieving a mean speedup of 1.4× over the fastest competitor (up to 4.9× on DataComp-DR). Note that these times include graph reordering and compression for Ginger, but not the other methods, trading some of the advantage of PiPNN for lower memory footprint. On the five billion-scale datasets, complete builds take an average of 35 minutes (up to 39 minutes), including 18 to 20 minutes for graph construction and 13 to 20 minutes for reordering and compression. Faiss, the fastest competitor, takes on average 69 minutes (up to 88 minutes), giving Ginger a 2.0× mean speedup (up to 2.3×). The remaining libraries require 1.8 to 42 hours or run out of memory. On the three large high-dimensional datasets (35M to 101M vectors), Ginger builds 2.0× faster in the geometric mean (up to 2.3×) than the fastest competitor.

On smaller datasets, all methods finish within two minutes. ParlayANN builds up to 5.7× faster than Ginger on the very small datasets DBpedia-3072 and Wiki-Qwen, where PCA dominates our build time, while Faiss is 2.1× faster on GloVe. If we look only at PiPNN graph construction time, it is fastest.

The Ginger (Vamana) column reports our Vamana implementation without graph compression for reference. Even with Vamana, Ginger builds faster than all external Vamana libraries on the 11 datasets with $n > 1$M.

To be able to include them in the experiments, we patched SVS and ScaNN to accelerate index construction. For SVS, we eliminate lock contention when adding backward edges to the Vamana graph by scaling the number of backedge buffers and clearing them in parallel, giving greater than 2× speedup without changing the resulting graph. For ScaNN, we parallelize several sequential loops and accelerate k-means by running on quantized 8-bit vectors (SF8), which has been shown to not compromise k-means quality [47].

Ablation Studies

We now analyze the contributions of Ginger’s main components through ablation studies. We first examine search optimizations, then evaluate NTQ accuracy independently of graph traversal, and finally study how reordering and encoding affect graph size and query speed.

Search Optimizations. Figure 6 breaks down where Ginger’s speedups come from. At 90% recall, navigating on 4-bit TurboQuant codes instead of float vectors is the largest step, speeding up search by 5.7× in the geometric mean (up to 7.2×). Searching on PCA-projected coordinates speeds up search by another 1.8× in the geometric mean (up to 2.4× on DBpedia-3072, which has the largest reduction in dimension). The prefilters help to a lesser extent at 90% recall. TurboSearch speeds up search by 1.26× in the geometric mean (up to 1.5×). JL speeds up search by 1.12× in the geometric mean (up to 1.4× on DBpedia-3072), but incurs a 15% slowdown on Wiki-All. TurboSlice beats JL on six of the seven datasets. On Wiki-Qwen, TurboSlice is 1.27× faster than PCA at 97% recall, and the two are on par at 99% recall. We attribute this to the fact that the projection is expensive on Wiki-Qwen. PCA and the prefilters both cut memory traffic per candidate, so their gains do not stack.

Next, we investigate how much time each phase of the search procedure takes. Figure 7 shows how the runtime balance shifts as dimensionality increases from 768 (Wiki-Cohere) to 1,536 (DBpedia-1536) and 4,096 (Wiki-Qwen). Beam search dominates on the first two datasets, while projection accounts for roughly half the runtime on Wiki-Qwen at 95% recall. This reflects the growing cost of multiplying each query by a projection matrix whose size increases with both the input and projected dimensions. On larger dimensionalities, we can significantly speed up projection without sacrificing recall by quantizing the matrix entries. Figure 8 shows little benefit from quantizing Wiki-Cohere’s projection matrix, whose float representation occupies only 0.73 MiB and can fit in L2 cache. The larger float matrices for DBpedia-1536 and Wiki-Qwen occupy 2.16 MiB and 13.75 MiB, respectively. Quantization reduces their code storage to 0.27 MiB and 1.72 MiB, consistent with improved cache residency and the substantial throughput gains on these datasets. The benefit narrows near full recall as the fixed query-projection cost is amortized over more expensive search and reranking.

Quantization Ablations. In Figure 9 we plot the recall of NTQ at different bitwidths, showing that 12 bits achieves near float accuracy. We measure the accuracy of the quantizer separate from the quality of an approximate search index by evaluating recall over a brute-force scoring of the dataset. We use subsets of 5 million datapoints per dataset so as to make this computationally tractable. Moreover, these results show that a simpler residual scheme, which quantizes $r = y - \tilde{y}$ with a second TurboQuant, plain uniform scalar quantization, and bf16 are all insufficient. We also compare with a reimplementation of Intel’s proprietary LVQ codec [1]. Like NTQ, two-level LVQ (LVQ-4×k) pairs a 4-bit navigation code with $k$ additional bits per coordinate for reranking. For LVQ-4×8, the recall of our reimplementation agrees with Intel’s SVS binaries to four decimal places. LVQ centers each vector by the global dataset mean and quantizes it uniformly to 4 bits with per-vector minimum and maximum bounds. For reranking, the residual of the centered vector with respect to its 4-bit code is requantized with uniform scalar quantization. At 4 bits, LVQ is less accurate than NTQ on the three high-dimensional datasets, while both approach float accuracy at 12 bits. The use of the global mean is crucial for LVQ’s recall which makes the codec less flexible in dynamic settings. Adding centering to NTQ can optionally boost recall on some datasets, such as DBPedia-3072.

Extended RaBitQ [28] is another method that splits its codes, into a 1-bit sign and a $k$-bit magnitude. Its only coarse level is thus the 1-bit sign code. Truncating the magnitude bits does not yield a well-tuned coarse code either, because all bits share one uniform grid whose per-vector scale is fit to the full code.

Graph Compression and Reordering

Lastly, we evaluate the impact of graph reordering on compression and query speed. Table 3 compares RGP (Section 5.1) against the original vertex order (Unreordered), and two baselines from the literature: bottom-up agglomerative clustering on normalized edge weights (RGC [11]), and top-down Recursive Graph Bisection (RGB [19]). RGP achieves the smallest gaps on all six datasets and reduces the bits per edge under AdaptiveGap by 31.5% in the geometric mean (up to 46.7%) over the original order. On the larger graphs (35M to 100M vertices), RGP is also 4.2× faster in the geometric mean (up to 26.3×) than RGC and 4.8× faster in the geometric mean (up to 6.6×) than RGB.

The graph-memory measurements in Table 4 include the CSR row-offset array, whereas Table 3 reports encoded neighbor-list storage alone. Table 4 compares query throughput at 95% recall and graph memory for three compression codecs on RGP-reordered graphs (AdaptiveGap, StreamVByte [48], and PrefixVarint [18]) against uncompressed CSR (CSRGraph) and fixed-degree arrays (FlatGraph). AdaptiveGap shrinks the graph by 2.1× in the geometric mean (up to 2.5×) over CSRGraph and by 3.4× in the geometric mean (up to 5.1×) over FlatGraph, compared with 2.0× and 3.2× in the geometric mean for StreamVByte. AdaptiveGap comes within 1.4% of CSRGraph and 2.8% of FlatGraph in the geometric mean while using 2.1× and 3.4× less graph memory. Non-vectorized decoding makes PrefixVarint 5.9% slower in the geometric mean (up to 11.3%) than AdaptiveGap. AdaptiveGap matches the throughput of StreamVByte while saving 0.9 bits per edge in the geometric mean (up to 1.2 bits), or 5.4% of graph memory (up to 7.6%).

Metric	Reordering Method	OpenAI-arXiv (2.3M)	Wiki-Cohere (35M)	Wiki-All (88M)	Text2Image (100M)	Deep (100M)	MS-Turing (100M)
LogGap / AdaptiveGap (bits/edge)	Unreordered	14.53 / 19.34	16.88 / 22.05	16.78 / 22.43	19.95 / 24.55	20.14 / 24.85	20.22 / 24.93
	RGC	10.10 / 15.66	12.84 / 18.38	13.89 / 19.69	9.71 / 15.22	15.04 / 20.55	15.19 / 20.63
	RGB [19]	8.80 / 14.17	11.08 / 16.54	12.01 / 17.82	8.65 / 13.99	11.99 / 17.51	13.18 / 18.79
	RGP (Ours)	8.57 / 13.97	10.59 / 16.02	11.02 / 16.86	7.81 / 13.08	11.74 / 17.27	12.03 / 17.63
Reorder Time (s)	RGC	2.4s	83.2s	1573.4s	248.3s	210.7s	189.5s
	RGB [19]	3.5s	103.8s	213.1s	521.5s	458.6s	474.4s
	RGP (Ours)	3.2s	20.0s	59.8s	79.6s	91.4s	113.3s

Graph Format & Reordering	OpenAI-arXiv (2.3M)	Wiki-Cohere (35M)	Wiki-All (88M)	Text2Image (100M)	Deep (100M)	MS-Turing (100M)
AdaptiveGap + Reordered (CSR)	519.5k / 14.5b	721.4k / 16.5b	1149.9k / 17.6b	118.5k / 13.4b	775.9k / 17.7b	501.9k / 18.1b
StreamVByte + Reordered (CSR)	527.9k / 15.7b	723.3k / 17.4b	1160.6k / 18.6b	117.9k / 14.3b	782.2k / 18.5b	511.2k / 18.7b
PrefixVarint + Reordered (CSR)	499.6k / 14.7b	693.9k / 17.0b	1098.1k / 18.0b	111.8k / 13.6b	688.4k / 18.1b	471.8k / 18.6b
Uncompressed + Reordered (FlatGraph)	523.9k / 65.2b	740.9k / 53.9b	1195.5k / 89.3b	119.6k / 39.2b	807.4k / 48.1b	527.0k / 49.6b
Uncompressed (FlatGraph)	526.9k / 65.2b	747.0k / 53.9b	1203.2k / 89.3b	119.2k / 39.2b	745.5k / 48.1b	525.6k / 49.6b
Uncompressed + Reordered (CSRGraph)	520.9k / 34.0b	726.2k / 33.7b	1180.0k / 34.7b	119.7k / 33.2b	752.1k / 33.5b	515.1k / 33.5b
Uncompressed (CSRGraph)	523.3k / 34.0b	731.9k / 33.7b	1176.7k / 34.7b	120.1k / 33.2b	777.3k / 33.5b	515.0k / 33.5b

Discussion & Conclusion

Ginger shows that graph-based vector search still has plenty of room to grow. It breaks new ground in query throughput, memory footprint, and indexing time for ANNS. The key is designing every step of the search around reducing memory traffic. Nested TurboQuant lets a single code serve both fast 4-bit navigation and reranking with near-float accuracy. Graph compression shrinks the graph without slowing down queries. PiPNN completes the picture with fast index construction.

Looking Ahead. While this paper focuses on single-vector dense embeddings, retrieval applications at Google increasingly go beyond this setting. We therefore designed Ginger to be flexible for more general retrieval settings. Graph construction and beam search operate only through a user-provided similarity function, abstracting away the specific data representation. This makes it easy to search under novel similarity functions like Chamfer on multi-vectors and black-box similarity functions such as learned relevance scorers. Neural scorer inference is more expensive than computing a dot product, increasing the appeal of the few distance evaluations that graph search needs. We are thrilled to share Ginger with the research community and look forward to seeing what others build with it.

Acknowledgments

We thank Richard Wen, Kishen Gowda, Majid Daliri, Rasto Lenhardt, Jirka Isa, Jan Wassenberg, Peter Sanders, John Owens and Daniel Seemaier for helpful discussions.

Parameter Configuration

For each library, we tune index structure, quantization method, and reranking formats for the highest throughput across the recall range. Every configuration we report is built and evaluated on the full dataset. We sweep query search parameters to extract the Pareto frontier of throughput versus recall. Table 5 summarizes the formats we use for each library, and Table 6 lists the selected parameters for all 14 datasets. Below, we first summarize the settings for graph indexes. For the IVF indexes (ScaNN and Faiss), point clustering, routing structure on top of the clusters, quantization, and reranking interact closely, making them hard to tune, so we describe their tuning in detail below.

Graph Indexes. All graph indexes use maximum degree $R = 64$ and construction beam width $L = 128$, except on GloVe, where they use $R = 100$ and $L = 250$. We tune the pruning threshold $\alpha$ per dataset, with $\alpha_{\mathrm{PiPNN}}$ for PiPNN graphs and a single $\alpha_{\mathrm{Vamana}}$ shared by all Vamana-based indexes. Table 5 lists the quantization methods and formats of each graph index. SymphonyQG runs out of memory during index construction on the billion-scale datasets, so we evaluate it only on GloVe and the eight high-dimensional datasets.

On high-dimensional datasets ($d \ge768$), we initialize the PCA target dimension for Ginger to the smallest dimension that retains roughly 90% of dataset variance, rounded so that the 4-bit NTQ vector and its bundled metadata fill whole cache lines. Starting from there, we reduce the dimension in increments of whole cache lines to find the optimal throughput–recall trade-off against unprojected vectors. For SVS, we use LeanVec4x8 and follow the same tuning procedure, aligning dimensions directly to whole cache lines as it does not embed metadata into the codes. Table 6 lists the chosen dimensions.

ScaNN. ScaNN partitions the dataset with a $k$-means tree. We evaluate up to three levels, with $C_1$ clusters on the bottom, $C_2$ in the middle and $C_3$ on the top. Within a leaf cluster, vectors are stored as anisotropic product-quantization codes [37] with 16 centers per two-dimensional subspace (AH2-LUT16). The best candidates retrieved from the leaves are rescored against higher-precision vectors. In high dimensions, we configure ScaNN to route and quantize in a PCA subspace while reranking against full-dimensional vectors.

We also enable SOAR [81], an optimization that stores each vector in a second leaf, chosen so that the two assignments err in different directions, which delivers recall improvements. We use the default settings for SOAR ($\lambda= 1.5$), except on GloVe and Wiki-Cohere ($\lambda= 1.0$), and on DataComp-DRP and DBPEDIA ($\lambda= 2.0$). For anisotropic vector quantization, we also use the default weight AVQ = 2.5. Because the default noise-shaping threshold NST = 0.2 assumes unit-norm vectors, we scale it proportionally to the average vector norm on non-unit-norm datasets (24.0 on MS-SPACEV, 100.0 on BIGANN, 2.75 on WIKI-COHERE, and 2.0 on MS-MARCO). We also tune it to NST = 0.1 on the unit-norm datasets OPENAI-ARXIV, DATACOMP-DR, and DBPEDIA.

Because ScaNN builds its hierarchy bottom-up, we first size the leaf clusters $C_1$ through target memory budgets of 2-bit AH codes: roughly 10 KB per leaf on billion-scale datasets, 20 to 64 KB in high-dimensional PCA space, and $\approx\sqrt{n}$ on small flat indexes. We train this leaf $k$-means once and build the upper routing levels on the fixed leaf centroids without retraining. To balance centroid routing overhead against leaf scanning, we scale the routing depth with dataset size. Small datasets use flat routing, as scanning all leaf centroids directly is fast. Medium datasets use a two-level tree with $C_2 \approx\sqrt{C_1}$ top-level clusters for a balanced branching factor. Billion-scale datasets use a three-level tree with a uniform geometric branching factor $B \approx C_1^{1/3}$. Over these fixed leaf partitions, we evaluate different upper-level routing layouts to select the best configuration without reclustering the dataset.

For reranking, we choose the most compact format that preserves accuracy: int8 suffices on DBPEDIA-1536, OPENAI-ARXIV, and DBPEDIA-3072, and is lossless on MS-SPACEV. We rerank with bf16 on BIGANN (where signed int8 caps recall at 88.5%), on the $d = 768$ inner-product datasets (where int8 caps recall at 96%), and on the billion-scale float datasets to halve bandwidth with minimal accuracy loss.

At query time, we sweep the number of probed leaves, the number of upper-level clusters visited, and the number of reranked candidates to pick the Pareto-optimal configurations. To choose the upper-level clusters visited, we sweep over them directly on two-level trees. On three-level trees, an independent grid over both upper levels is intractable. Instead, because query latency is dominated by memory bandwidth, we set the upper-level probes as a function of the leaf probes so that each routing level scans a fixed ratio of the leaf bytes. We evaluate nine routing profiles across three categories: uniform allocations (spending 0.5×, 1×, or 2× of leaf bytes at both upper levels), mid-heavy allocations (0.5×–1× at the root and 1×–2× in the middle), and low-routing allocations (0.05×–0.1× at the root and 0.25×–0.5× in the middle).

Faiss. Faiss composes an inverted file (IVF) index from modular pipeline stages [22], listed in Table 6 in factory notation. The dataset is partitioned into $n$ clusters using $k$-means. Within each cluster, vectors are split into $m$ subspaces and stored as 4-bit product-quantization codes in a cache-aligned fast-scan layout [4] (PQ$m$x4fs). To route queries across large numbers of clusters efficiently, Faiss builds an HNSW graph over the $n$ centroids (IVFn_HNSW32).

To balance routing cost against cluster scanning, we sweep the cluster count $n$ around recommended baselines: {1,024, 2,048, 4,096} on small datasets, {16,384, 32,768, 65,536, 98,304, 131,072, 196,608, 262,144} on medium datasets, and {524,288, 1,048,576, 2,097,152} on billion-scale datasets. Small datasets use flat routing, as scanning all cluster centroids directly is fast. Larger datasets route through an HNSW32 graph over the centroids. To keep $k$-means training tractable for tens of thousands to millions of centroids, we use top-down two-level clustering on datasets with $\ge10$M vectors.

An optional OPQ rotation [32] balances the variance across PQ subspaces and can also project vectors to fewer dimensions. We evaluate OPQ across different target dimensions, but omit it on GloVe where rotation does not improve accuracy. In low dimensions, we evaluate two- and four-dimensional OPQ subspaces, where two dimensions per subspace with centroid residuals (PQ$m$x4fsr) performs best. In high dimensions, we sweep OPQ target dimensions in {128, 192, 256, 384, 512}, and store uncentered vectors because centroid subtraction degrades throughput–recall performance.

The best candidates retrieved from the clusters are rescored against higher-precision vectors. We choose the most compact format that preserves accuracy: 8-bit scalar quantization (SQ8) suffices on DBpedia-1536, OpenAI-arXiv, and DBpedia-3072, and is lossless on the two integer datasets. We rerank with bfloat16 (SQbf16) on the $d = 768$ inner-product datasets and the billion-scale float datasets. On GloVe, we rerank against exact floats (RFlat).

Library	High-Dim Transform	Navigation / Search	Reranking
Ginger	PCA	4-bit NTQ	(4+8)-bit NTQ
SVS	PCA (LeanVec)	4-bit LVQ	LVQ4x8 / 8-bit LVQ§
ParlayANN	JL filter	SQ8	float
DiskANN	–	4-bit / 1-bit spherical‡	float
Hnswlib	–	float	–
SymphonyQG	–	RaBitQ	float
ScaNN	PCA	2-bit PQ	float / bf16 / int8
Faiss	Projective OPQ	2-bit PQ	float / bf16 / int8

At query time, we sweep the number of probed clusters and the number of reranked candidates to pick the Pareto-optimal configurations. When using an HNSW coarse quantizer, we additionally sweep the graph search depth (efSearch) to balance centroid routing latency against cluster retrieval recall.

Library Versions

Library	Version	Git Commit
Faiss [22]	v1.15.0	20f14b
Hnswlib [58]	v0.9.0	d9b360
ParlayANN [59, 66]	–	a48c6a
SVS [1]	v0.4.0	75e30f
DiskANN [46]	v0.59.0	c84530
ScaNN [37, 81]	v1.4.3	807d4a
SymphonyQG [27, 35]	v0.3.4	1182cb