Atlas: Efficient Verifiable Semantic Search
Atlas delivers zero-knowledge proofs for HNSW semantic search, verifying RAG retrieval in under a second on SIFT1M and 2.0 seconds at 100M vectors.
Atlas lets a search provider prove that a query was answered correctly against a committed HNSW index without revealing the index, addressing provider deviations like truncation or bias. It combines offline preprocessing, a fixed-size-state restructuring of HNSW with a correctness proof, and timestep-tagged batching of per-step arguments. The system proves queries in under a second on SIFT1M and 2.0 seconds at 100 million vectors while preserving plaintext HNSW recall, and proven retrieval maintains end-to-end RAG answer quality at lower cost than prior verifiable retrieval systems.
- First system to demonstrate verifiable graph-based (HNSW) semantic search at scale.
- Proving costs scale with traversal, not database size, via offline preprocessing.
- Under 1 second per-query proving on SIFT1M; 2.0 seconds at 100M vectors.
- Preserves plaintext HNSW recall and keeps the index hidden beyond returned results.
- Proven retrieval maintains RAG end-to-end answer quality at lower proving cost.
From the original article
1 min read at arxiv.orgSemantic search is a core primitive of modern applications, powering recommender systems, web search, and retrieval-augmented generation for language models. The provider controls the index and query execution, leaving clients to trust that results come from the right algorithm over the intended index.
By Nikolay Avramov · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.