Skip the distances you don't need
How the Projection-Augmented Graph makes graph-based nearest-neighbor search up to 5× faster than HNSW, while indexing faster and supporting live insertions.
Six things a modern vector index has to do
Most ANN benchmarks measure one thing — queries per second at a given recall, with K=10, on twenty-year-old SIFT/GIST image descriptors. The authors argue that RAG, recommender, and agent workloads are different, and list six demands. The interesting part of the paper is that it tries to hit all six at once rather than trading one for another.
- D1 · Query throughputQPS at high recall, on embeddings from current models.
- D2 · Fast indexingHNSW-style graphs are slow to build; that blocks "instant deploy" use cases.
- D3 · Moderate memoryAdjustable index size, for a memory-vs-accuracy dial.
- D4 · High dimensionality1,536- and 3,072-d embeddings are normal now; some methods collapse there.
- D5 · Any retrieval size K10 for RAG, hundreds for image retrieval, thousands for recommenders.
- D6 · Online insertionSelf-evolving agents keep appending memories; the index can't be rebuilt.
How graph search works, and what it costs
A similarity graph connects each vector to a handful of nearby vectors. To answer a query q, you start somewhere, look at the current node's neighbors, compute their distances to q, move toward the closest ones, and repeat. That is what the animation at the top is doing.
The expensive line in that loop is "compute their distances." Every neighbor of every visited node gets an exact d-dimensional distance computation, and with d = 1536 that is the whole runtime. Most of those computations are wasted: the neighbor turns out to be farther than what's already in the result list and is thrown away.
Two families have tried to fix this. Quantized graphs (NGT-QG, SymphonyQG) replace exact distances with compressed ones everywhere — fast, but they lose recall in high dimensions and at large K, and the compressed index can be 2× the size. Projection + graph methods (FINGER, PEOs, KS2) keep exact vectors but run a cheap probabilistic test first to decide whether a neighbor deserves an exact distance. PAG belongs to the second family, but builds the test into graph construction rather than bolting it on afterward.
The angle trick
Here is the geometry everything rests on. Say the search is sitting at node u, considering its neighbor w, and the query (or the node being inserted) is v. Whether w is closer to v than some threshold depends only on the angle α between the two vectors w − u and v − u, because the edge lengths are already stored. So the question becomes: can we estimate cos α without a full inner product?
PAG keeps a set of random reference directions. For each edge w − u it precomputes the closest reference direction r* and the angle β to it. At query time it computes, once, the angle θ between v − u and every reference direction — cheap, because the projection structure is built from small subspaces and runs in AVX-512. The paper's Theorem 3.1 says that in high dimensions
cos θ ≈ cos α · cos β so cos α ≈ cos θcos β
with Gaussian error whose variance shrinks as you use more subspaces (L). Drag v below and watch the estimate track the true value. The random reference direction is the dashed line. In two dimensions the estimate carries a visible bias, because the part of v − u perpendicular to the edge still projects onto r*; in hundreds of dimensions that perpendicular contribution averages to nearly zero, which is the content of the theorem.
PRT: the probabilistic routing test
The routing test is now a one-liner. For a neighbor wi of the current node,
PRT = cos θicos βi − τi
and only neighbors with a positive score get an exact distance. The threshold τi is the cosine that wi would need in order to beat the current worst result zmax; it comes straight from the law of cosines using stored edge lengths. The test is asymmetric on purpose: it compares an approximate value against an exact one and only needs to say which is larger. If the true cosine clears the threshold, the test passes with probability at least ½; if it doesn't, the test fails with probability approaching 1 as the projection set grows.
Below, the same graph, the same query, the same entry point. Left: plain best-first search. Right: with the routing test. Skipped neighbors are shown as grey ticks. One caveat the toy makes visible: in two dimensions a graph walk rarely wastes a distance computation, so the test can only skip about a quarter of them here. In 1,500 dimensions distances concentrate — almost every neighbor of the current node is roughly as far from the query as the node itself — and the paper measures fewer than 20% of candidates passing the test. The curse of dimensionality is exactly what makes the trick pay off.
TFB: recycling false positives
A false positive is a neighbor that passed the test, got its exact distance computed, and still wasn't good enough to enter the result list. Earlier methods (PEOs, KS2) just discarded it — the distance was paid for and thrown away. The Test Feedback Buffer notices something from the Gaussian result above: a false positive is, with high probability, only slightly worse than the threshold. As the search proceeds and the threshold loosens (the result set isn't full yet, or the working window moves), that node may become good enough. So keep it.
TFB splits the search into rounds over a small working set W (size max{10, K}) rather than one big priority queue:
During a round, nodes ejected from W go into ring RT; false positives go into ring RF.
At the end of the round, W is flushed into the result list RL, the two rings are merged and sorted, the best refill W, the rest go back to RT, and RF is cleared.
In the toy below, a round visits the nodes that were in W when it began; nodes that enter mid-round are visited in later rounds if they survive the refill.
Two payoffs: the threshold τ is set from the furthest node in the small window W, so it tightens incrementally instead of jumping to the worst of a huge queue, and every exact distance you paid for gets a second chance to be used. Step through a few rounds:
PES: finding edges RobustPrune misses
Graph indexes decide edges with a rule called RobustPrune. When inserting v, you search for its nearest nodes, prune them into an out-neighbor list Nout(v), and then only those out-neighbors are considered for edges pointing into v. That candidate pool is small, and on some real datasets nodes end up with tiny in-degree and become nearly unreachable — one reason HNSW underperforms on certain modern embeddings.
PAG widens the pool to every node visited during the insertion search, which is far larger, without paying RobustPrune's cost on each. The Probabilistic Edge Selection test asks: does u have any out-neighbor that is already closer to v than u itself? If it does, the edge u → v is redundant. If it doesn't, u → v is a promising in-edge. The check reuses the same cos θ/cos β values PRT already computed, with a different threshold δi:
PES(u, v) = maxi ( cos θicos βi − δi )
Because τi − δi is a precomputable constant, PES costs O(1) per neighbor on top of PRT. Edges that PES flags go into a "PES set" and are confirmed by real RobustPrune later, in batches — which is also how online insertion stays cheap.
The toy below uses a deliberately sparse graph (out-degree 2) to mimic the poorly connected regions the paper is worried about; on a well-connected 2-D graph PES finds little, because a walk toward v almost always leaves behind a node with a closer neighbor.
Where the speedup comes from
Searching an HNSW graph costs about O(n′d): n′ visited nodes, each paying a full d-dimensional distance. PAG costs O(n′L + γ n′d): a cheap L-dimensional projection lookup for every candidate, and a full distance only for the fraction γ that pass. The paper reports γ typically below 0.2, and recommends L ≈ √d. Move the sliders to see why high dimensionality helps PAG rather than hurting it.
Results
Six post-2023 datasets (OpenAI text-embedding-3 at 1,536 and 3,072 dims, CLIP food images, CoCa text-to-image with out-of-distribution queries, MiniLM Amazon reviews, DINOv2 satellite imagery at 56M vectors) plus legacy GloVe and DEEP100M. Default K=100, single search thread. Two configurations: PAG-Base tuned for throughput, PAG-Lite tuned for indexing speed and memory.
The headline numbers: PAG-Base is up to 5× faster than HNSW at equal recall and wins on every modern dataset except the high-recall end of WoltFood; it builds its index in 20–40% of HNSW's time at the same or larger construction budget; and the gap widens as dimensionality or K grows, exactly where quantized graphs (SymQG) fall over. PAG-Lite lands near quantization methods on build time and memory while still beating HNSW on QPS. In the ablation, TFB reduces indexing time and improves search on its own; PES adds search quality at almost no indexing cost.
The paper's own summary table, tiers from the authors' experiments (4 dots = best):
| HNSW | Vamana | IVFPQ-FS | ScaNN | RaBitQ+ | SymQG | HNSW+KS2 | PAG-Base | PAG-Lite |
|---|
Honest caveats
The gains are largest where distance computations dominate: high-d, large K, dense semantic embeddings. On sparse, low-dimensional legacy data (SIFT, GIST at K≤100) SymQG's quantization still wins. The theory is asymptotic — it needs many subspaces and many projection vectors per subspace — though the authors note moderate values work in practice, and the KS2 paper gives finite-sample guarantees for the single-neighbor case. Memory is "moderate," not small: PAG-Base uses somewhat more than HNSW on low-dimensional data, and the projection table adds O(nML) on top of the vectors and edges.
If you only remember three things
Distance computations, not graph hops, are what an ANN search pays for. A cheap random-projection angle estimate compared asymmetrically against an exact threshold can skip most of them with a probabilistic guarantee. And the same estimate, with a different threshold, tells you which edges your graph is missing — so the test becomes a building block of the index, not a plug-in on top of it.