Feature proposal: Projection-Augmented Graph as a new CPU ANN index

[KejingLu-810]

Hi Faiss team,

PAG is available here:
https://github.com/KejingLu-810/PAG

I am the author of Projection-Augmented Graph (PAG), and I would like to ask whether you would be interested in evaluating it as a possible new CPU ANN index for Faiss.

Summary

PAG is a graph-based approximate nearest neighbor method designed for high-throughput CPU search. The current public implementation supports cosine similarity, L2 distance, and maximum inner product search, with static indexing, serialization, Python bindings, and in-memory online insertion.

Spotlight

• QPS-recall performance: In our local CPU tests, PAG achieves about 4x-14x higher QPS than HNSW / IP-NSW at matched recall on several ANN workloads.
• Scalability: PAG remains fast and stable across retrieval sizes from top-10 to top-1000, vector dimensions from about 100 to 3000, and large-scale datasets.
• Fast indexing: PAG shows substantially faster graph construction in our tests, typically around 3x-7x on cosine and high-dimensional workloads, while still remaining faster on MIPS workloads.

Two related papers have been accepted to ICLR 2026 Oral and ICML 2026. We believe PAG may be complementary to the existing Faiss index family, especially for high-recall CPU search, high-dimensional cosine workloads, large retrieval sizes, fast graph construction, and online insertion.

We also received an independent 1B-scale community report showing about 4x QPS over HNSW-SQ with no recall loss. The same report also suggested that an int8 backend could provide substantial additional acceleration with about 1% recall drop.

Discussion

If helpful, we would be very happy to provide more detailed documentation, benchmark scripts, reproducibility instructions, and any assistance needed to help the Faiss team test or evaluate the code.

Thank you very much for your time.

[junjieqi]

@KejingLu-810 thanks for reaching out. Would you like to provide more information about your implementation? In addition, it is a new algorithm or some optimization we could apply to existing graph algorithms like Vamana or HNSW

[KejingLu-810]

@junjieqi Thanks for the response.

The related paper is available here: https://arxiv.org/pdf/2603.06660

PAG is a new graph-based ANN index, not just an optimization of HNSW or Vamana.

At a high level, PAG builds a graph index augmented with compact random-projection information. During index construction, the projection information provides a lightweight way to identify promising neighborhood candidates, which reduces the amount of expensive exact-distance work needed during graph construction.

During search, PAG uses the same projection information as an auxiliary geometric signal before exact distance evaluation. For each candidate, the projection-based test can cheaply estimate whether the point is likely to be competitive for the current search. Candidates that pass this test are then evaluated with exact distance or similarity, and the final returned neighbors are always ranked by exact distance or similarity.

If there are specific implementation details you would like to know more about, we would be happy to provide them.