Atlas proves vector search ran on the real index

Atlas proves a semantic search result was computed over the full, committed index.

Whoever runs a semantic search service controls both the index and the query engine. A client has no way to check whether results were cut short or skewed toward certain documents.

Earlier verifiable retrieval work sidestepped that problem by targeting cluster-based indices, structures simple enough to encode directly into zero-knowledge constraint systems. Cluster indices don't search as well as graph-based ones, so that simplicity cost recall.

The Atlas paper instead builds a zero-knowledge proof for HNSW, the graph structure behind fast nearest-neighbor search. It doesn't swap the index out for something easier to prove. The authors restructure HNSW's traversal into a fixed-size-state procedure, then prove it returns identical results to standard HNSW.

Two moves make the proof practical. Preprocessing handles the corpus-dependent cost once, offline. Per-query proving time then tracks how far the traversal goes, not how big the database is.

The authors design per-query proving time to track traversal length rather than corpus size. Their paper doesn't say whether that holds once an index reaches production scale.