GINGER: Spicing Up Graph-Based Vector Search

arXiv:2611.08306 · cs.IR, cs.DC · Submitted 2026-11-05 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: We're looking at the paper: "GINGER: Spicing Up Graph-Based Vector Search".

Jane: Here's the gist of the paper. Ginger presents a state-of-the-art open-source C++ library for graph-based approximate nearest neighbor search (ANNS) that surpasses existing ANNS libraries with regards to query throughput and indexing time while matching the memory footprint of the most space-efficient competitors Core Contributions

Title and authors: Tom: To start, let's look at the title and who wrote this. It’s GINGER: Spicing Up Graph-Based Vector Search, and it’s written by Daniel Salwasser from Google Research, Lars Gottesbüren from Google Research Zürich, Laxman Dhulipala from Google Research and UMD College Park, USA, Jakub Łącki from Google Research New York City, USA Guy Blelloch from Google Research and CMU Pittsburgh, USA Rajesh Jayaram also at Google Research New York City, and Tobias Rubelato also at UMD College Park.

Jane: It’s a big team of researchers coming together to build this library at Google. The title itself says "Spicing Up," which suggests they aren't just doing minor tweaks; they are fundamentally improving the way we search through these graphs for nearest neighbors.

Tom: Exactly, it implies a more significant architectural improvement than just adding a few lines of code. They’re tackling the underlying structure of how graph-based approximate nearest neighbor search works.

Lu: What I see in the author list is that it's a very deep collaboration across different Google Research locations and institutions, which suggests they’ve been building this from a very foundational level up.

Meng: It’s cool to see this kind of internal research being put out as open source. But for me, the question is how easily we can integrate something like this into our existing production pipelines without it becoming a massive headache to maintain at scale.

Lalam: The fact that it's open source means the community gets to look under the hood, which is valuable because these kinds of performance boosts usually come from very specific low-level optimizations.

The paper's summary: Tom: So, summarizing what this paper does for GINGER: Spicing Up Graph-Based Vector Search, they present a state-of-the-art open source C++ library for graph-based approximate nearest neighbor search. The core goal is to push the speed and memory efficiency of graph search when dealing with large and high dimensional embedding datasets.

Jane: They are directly comparing their library against existing ANNS libraries and showing that GINGER surpasses them in both query throughput, which is how fast it answers a question, and indexing time, which is how long it takes to build the searchable index.

Lu: The main implication here is that they’ve found a way to significantly speed up the process of finding those neighbors in a graph structure without having to drastically reduce the quality of the search results.

Meng: Speeding up indexing time is usually a huge win because it means faster model retraining or faster data updates. But what about high dimensional datasets? That's where most of our real-world problems live, so I want to know how this holds up there.

Lalam: They achieved this by designing every step of their beam search implementation around two main things: reducing memory traffic and reducing the index footprint through lossless graph compression.

The paper's improvements: Tom: Now let’s talk about the specific improvements they made, because that’s where the real engineering happens. First, they introduced something called Nested TurboQuant, or NTQ. This allows a single code per vector to handle both graph navigation and reranking tasks simultaneously.

Jane: That sounds like it simplifies the process by having one set of codes do two jobs instead of needing separate structures for navigation and refinement, which should inherently save memory. How much memory saving are we talking about here?

Tom: They claim that with NTQ, a single code per vector serves both roles, and it uses twelve bits per coordinate <ref:2611.08306#pg1>. This is compared to standard methods using thirty-two-bit floats, and they say it uses two point six times less memory while nearly matching the accuracy of those float methods <ref:2611.08306#pg1>.

Lu: The way they use that leading four bits for navigation and then a nested Lloyd–Max codebook for refinement sounds like a smart way to balance speed and precision in one go. It’s trying to get near float precision with a much smaller codebook size.

Meng: If it uses twelve bits per coordinate, that’s still quite large, but if it saves you two point six times the memory during the search phase on high dimensional embeddings, that translates into serious scaling benefits for us when we run inference on massive models <ref:2611.08306#pg1>.

Lalam: They also added a very fast SIMD kernel specifically for scoring those four-bit codes in a one-to-many scenario, and they mentioned two ways to further speed that up depending on the dimensionality of the embeddings.

Jane: And they didn't stop there, right? I want to know about the other techniques that help them manage memory traffic during the search phase.

Tom: Right, they have Fast graph search. They use this extremely fast SIMD kernel for scoring those four-bit codes and they offer two ways to further speed things up based on the embedding dimension. One of those is projecting vectors into a lower dimensional space using PCA or applying a prefilter called TurboSlice.

Lu: Projecting vectors into a lower dimensional space with PCA sounds like it’s trying to reduce the complexity of the search space itself before you even start scoring, which should definitely help reduce memory bandwidth usage.

Meng: Reducing memory bandwidth is critical for us when we move from a small test batch to serving millions of requests per second. If this reduces the bytes fetched during distance evaluation, that’s a concrete operational win.

Lalam: They also have AdaptiveGap combined with recursive graph partitioning, which shrinks the proximity graph by an average of two point one times relative to an uncompressed CSR layout without slowing down queries at all. They pack small gaps into fewer than eight bits while keeping the single-shuffle SIMD decoding of StreamVByte.

Jane: Shrinking the graph size by packing those gaps sounds like a great way to reduce the index footprint while maintaining search quality, especially when dealing with sparse graphs.

Tom: And they also have Search on Projected Coordinates, where they project both your database vectors and your queries into a lower dimensional space using PCA, and then quantize the rows of P to four bits to reduce the data fetched during query projection.

Conclusion: Tom: So wrapping up this discussion on GINGER: Spicing Up Graph-Based Vector Search, we’ve seen they are delivering significant performance gains across the board. They achieved an average speedup of one point eight times faster than the fastest competitor at ninety five percent recall on their evaluation benchmarks, and up to two point seven times faster on high dimensional datasets where they were two point zero times faster.

Jane: The core takeaway for us is that they’ve managed to get massive improvements in query throughput and indexing time while keeping the memory footprint very competitive with other space-efficient libraries. It seems like they found a solid way to handle the complexity of graph search without needing an enormous amount of RAM.

Lu: I think what really stands out is the combination of Nested TurboQuant for navigation and reranking, combined with the fast SIMD kernel for scoring those four bits. That’s a very dense optimization strategy that addresses both parts of the search process efficiently.

Meng: From a deployment standpoint, if we can get this level of performance on high dimensional data without needing to scale our memory requirements linearly, that changes how we think about deploying large embedding models in production environments. I’m curious if they mentioned any specific limitations on the size of the graph they could handle before things start breaking at scale.

Lalam: The authors did mention their methods for shrinking the graph through AdaptiveGap and Recursive Graph Partitioning, and they noted that this packing technique is done while retaining the single-shuffle SIMD decoding of StreamVByte, which keeps things efficient. However, one limitation they pointed out is that the effectiveness of Search on Projected Coordinates really depends on how well you can project your vectors into that lower dimensional space first.

Tom: That makes sense; it’s not a magic fix if the input projection isn't good enough. So while the performance metrics are impressive, we need to consider how much work is required upfront to set up those projections for our specific embedding space before we can see those gains realized.

Jane: It really comes down to engineering trade-offs, doesn't it? They’ve shown a very effective way to balance speed and memory by using these specific quantization and projection techniques in GINGER: Spicing Up Graph-Based Vector Search. That gives us a new tool for building faster systems on graph data.

Daniel Salwasser, Lars Gottesbueren, Laxman Dhulipala, Jakub Łcki, Guy Blelloch, Rajesh Jayaram, Tobias Rubel, Fshiteej Sheth, *mir Zandieh

Google Research & KIT

cs.IR, cs.DC

Submitted: 2026-11-05

Updated: 2026-11-05

Code: https://github.com/google/ginger

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 100/100

The gist: Ginger presents a state-of-the-art open-source C++ library for graph-based approximate nearest neighbor search (ANNS) that surpasses existing ANNS libraries with regards to query throughput and…

Key concepts

Nested TurboQuant (NTQ)
NTQ is a technique that allows a single code to handle both graph navigation and reranking. It achieves near-float precision while using only 26 times less memory than traditional methods, ensuring high query throughput.
Fast Graph Search
This search method uses an extremely fast SIMD kernel to score one-to-many relationships based on 4-bit codes. It can be further accelerated by reducing the vector dimension using PCA or employing a prefilter called TurboSlice.
AdaptiveGap with Recursive Graph Partitioning (RGP)
This combination shrinks the proximity graph by an average of 2.1x to 2.5x compared to standard layouts without slowing down queries. It achieves this by packing small gaps into fewer than eight bits while keeping the efficient StreamVByte decoding.
Search on Projected Coordinates
This method reduces memory bandwidth by projecting database vectors and queries into a lower-dimensional space using PCA. Rows of the proximity matrix are then quantized to 4 bits, minimizing data fetched during query projection.

Terminology

Summary

Ginger presents a state-of-the-art open-source C++ library for graph-based approximate nearest neighbor search (ANNS) that surpasses existing ANNS libraries with regards to query throughput and indexing time while matching the memory footprint of the most space-efficient competitors

Core Contributions

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Nested TurboQuant (NTQ) allows a single code to serve both graph navigation and reranking, achieving near float precision with 26x less memory than standard methods while maintaining query throughput.

  2. Fast graph search utilizes an extremely fast SIMD kernel for one-to-many scoring of the 4-bit codes and can be further sped up by projecting vectors to a lower dimension with PCA or applying a tuning-free prefilter called TurboSlice.

  3. AdaptiveGap, combined with recursive graph partitioning (RGP), shrinks the proximity graph by an average of 2.1x (up to 2.5x) relative to an uncompressed CSR layout without slowing down queries, by packing small gaps into fewer than eight bits while retaining the single-shuffle SIMD decoding of StreamVByte.

  4. Search on Projected Coordinates reduces memory bandwidth consumption by projecting database vectors and queries into a lower-dimensional space using PCA, and quantizing the rows of P to 4 bits to reduce data fetched during query projection.

  5. Candidate Prefiltering allows pruning unpromising candidates early by using a cheaper filter distance dfilt(q, v) to discard candidates before computing the 4-bit navigation distance dnav(q, v).

Abstract

We present Ginger, a state-of-the-art open-source C++ library for graph-based approximate nearest neighbor search (ANNS). We developed Ginger at Google to push the speed and memory efficiency of graph search on large and high-dimensional embedding datasets. Ginger surpasses existing ANNS libraries with regards to query throughput and indexing time while matching the memory footprint of the most space-efficient competitors. Ginger builds upon recent advances in proximity graph construction (PiPNN) and vector quantization (TurboQuant). We introduce Nested TurboQuant (NTQ), a two-level quantizer which supports low precision graph navigation and high precision reranking in a single code. This representation achieves near floating point precision with 2.6 times less memory. We also compress the size of our proximity graphs by up to 2.5 times without impacting query throughput. We combine graph reordering with a new lossless compression codec called AdaptiveGap, which builds upon StreamVByte. At 95% recall, Ginger speeds up query throughput by an average of 1.8 times over each dataset's fastest competitor and by at least 2.3 times over any single library. This lead grows to 2.9 times over compact libraries on high-dimensional embeddings.

Sources

Related papers