Atlas Proves a Semantic Search Result Was Actually Computed Over the Committed HNSW Index

arXiv 2609.11841·medium signalXBlueskyLinkedInCopy link

The provider of a semantic search service controls both index and query execution, so a client has no way to detect truncated search, biased results, or any other deviation from the specified algorithm. Prior verifiable retrieval systems dodged this by targeting regular cluster-based indices that encode cleanly into zero-knowledge constraint systems, giving up the recall of graph-based search. Atlas builds a zero-knowledge proof for HNSW itself using preprocessing that pushes all database-dependent cost offline so per-query proving scales with the traversal rather than the database, plus a restructuring of HNSW into a fixed-size-state procedure the authors prove returns the same results.