Can Verifiable Semantic Search Scale to HNSW Graphs? Atlas and the Zero-Knowledge Proof Challenge

The trust gap that verifiable semantic search must close

Semantic search has become a default retrieval mechanism for recommender systems, web search, and retrieval-augmented generation, but the provider controls both the index and the computation while the client sees only the returned results [1]. A provider may serve stale results, truncate the search to cut costs, bias the ranking toward preferred outcomes, or quietly depart from the specified algorithm, and these risks compound as retrieval results are consumed directly by downstream services without human oversight [1]. Zero-knowledge proofs can in principle remove this trust assumption by proving that results follow the agreed algorithm over a committed index, but realizing this efficiently is hard because HNSW, the de facto standard for approximate nearest neighbor search at scale, is control-flow heavy by construction [1].

HNSW navigates a layered proximity graph using priority queues, data-dependent branching, and early exits, a computation that maps poorly onto the arithmetic constraint systems underlying modern ZKPs, which require circuits to be fixed in advance and provisioned for worst-case behavior at every step [1]. Prior verifiable search systems therefore avoid HNSW and instead build on cluster-based indices that partition the dataset offline and answer a query by searching the clusters nearest to it [1]. This data-independent search pattern encodes compactly as polynomial constraints, but it sacrifices recall because clusters are selected once and a closer neighbor outside them is unreachable for the remainder of the search [1].

How Atlas makes HNSW provable without abandoning the graph

Atlas addresses the encoding problem through three techniques. First, preprocessing shifts all database-dependent cost offline via cq lookup arguments, so per-query proving scales with the length of the traversal rather than the size of the database, preserving HNSW's sublinear per-query cost [1]. Second, Atlas restructures HNSW into a fixed-size-state procedure by collapsing the multi-layer descent into a single graph walk and replacing the two interdependent priority queues with one bounded candidate set, and the authors prove the reformulated output equivalent to HNSW's [1]. Third, timestep-tagged batching tags every tuple with a step identifier and merges the per-step permutation and lookup arguments of the entire traversal into a single invocation, preventing proving overhead from growing with the step budget [1].

The step bound is the only point at which the reformulated search differs from HNSW, with sufficiently large budgets recovering HNSW's result exactly and smaller ones lowering proving cost at the expense of recall [1]. This design choice is what makes the system tunable: operators can trade a small amount of recall for a shorter proof trace, and the evaluation quantifies exactly how much recall is lost at different budget quantiles [1].

Recall preservation and proving cost across dataset scales

On SIFT1M, Atlas proves a query in 0.80 seconds with a 16.5 kB proof that the client verifies in 40 milliseconds, and at the smallest configuration reaching recall@1 above 0.9 the step budgets are Tg=6 and Tb=26 [1]. Proving cost scales with the beam width and step budget needed to reach a recall target, not with database size: BIGANN-100M raises proving time only to 1.98 seconds, and the corpus size affects proving cost only through the search configuration, as a larger corpus requires a larger ef to reach the recall target, which rises from 26 to 48 while M=16 remains fixed [1]. Truncation to a fixed step budget sacrifices little recall, as at 95th-percentile budgets the proven search stays within 0.8 recall@1 points of plaintext HNSW on integer datasets and every dataset exceeds 0.9 recall@1 at a deployable configuration [1].

The picture changes with embedding dimension. On GIST1M (d=960), Atlas proves a query in 36.66 seconds with a 75.5 kB proof, and verification time reaches 1.94 seconds, a cost that combines the high dimension with the largest configuration required to reach the recall target [1]. On the floating-point datasets Deep10M and GIST1M, quantization introduces an additional recall loss that reaches 5.2 recall@1 points on GIST1M at (M,ef)=(32,64), measured at the maximum budget where the fixed-step search is equivalent to unbounded HNSW, isolating the quantization effect from truncation [1].

Comparison with prior verifiable retrieval systems

Against zkRAG, concurrent work that likewise proves HNSW search, Atlas proves a query 2.8× faster at the same parameters (M,ef)=(32,64) and the same number of processed level-0 nodes (Nexp=2^12), in 18.6 seconds on one thread of a Xeon 8151 against zkRAG's 51.5 seconds on one thread of a Xeon 6126, two processors within 10% in single-core performance [1]. The speedup comes alongside a stronger guarantee, as zkRAG's proof reveals the number of steps taken at every layer while Atlas' reveals nothing beyond the result [1]. In the multithreaded setting, Atlas also outperforms V3DB, an IVF-PQ system, reaching every recall level V3DB attains between 10× and 45× faster, as product quantization caps V3DB's recall@1 at 0.50, a ceiling Atlas exceeds in 0.64 seconds against V3DB's 29.2 seconds [1].

In a complete RAG pipeline with BGE-M3 for embedding and Qwen2-7B for generation, Atlas exceeds VeriRAG's F1 at a fraction of its proving time, reaching 60.3 F1 in 2.5 seconds on SQuAD against VeriRAG's 46.9 in 6.6, and 51.3 in 3.2 seconds on TriviaQA-Val against 41.1 in 38.7 [1]. The gap follows from the retrieval quality bottleneck of IVF-PQ, as the cluster-based index recovers fewer of the most relevant passages and degrades the context the generator receives [1]. Atlas' proving cost depends on the search configuration rather than the corpus size, while VeriRAG's grows directly with the corpus, from 6.6 seconds on SQuAD to 56.0 on TriviaQA-Train and 96.2 on KILT [1].

Where the verifiability guarantee stops

The proof is limited to HNSW search and specific benchmarks, and the evaluation covers six standard ANN benchmarks spanning one million to one hundred million vectors and embedding dimensions from 96 to 960, but does not extend to other index structures or query types [1]. The recall reported reflects the loss from both quantization and truncation, and on floating-point datasets the quantization loss alone reaches 5.2 recall@1 points on GIST1M, meaning the verifiable system's recall is not identical to the unquantized float32 baseline even at maximum budget [1]. Dimensionality-reduction techniques make the projected dimension another tunable parameter that trades answer quality for proving cost, with PCA to d=128 reducing proving time 3× at a cost of 3.5 to 6.1 F1 points across datasets [1].

The broader context of verifiable computation suggests both the promise and the limits of this line of work. RaG-Tree shows that HNSW graphs can be coupled with R-trees for multi-attribute range-filtered search, achieving 2.8×, 2.4×, and 1.9× higher QPS than the strongest competing method at recall around 0.95 on DBLP, MSMarco, and LAION respectively, but its focus is query efficiency under filtering rather than cryptographic verifiability [2]. Zero-knowledge verification has been explored for edge generative AI inference using cooperative UAV swarms and trust-aware multiagent learning, where verification timeliness, malicious server detection delay, and energy efficiency are the measured outcomes, indicating that verifiability is being pursued across multiple layers of the AI stack with different constraints and threat models [4]. Earlier work on approximate nearest neighbor search established that compression and quantization techniques such as structure sensitive hashing with adaptive product quantization and set compression trees can achieve low memory footprints and accurate approximation on SIFT1M and GIST1M, providing the retrieval-quality baselines against which verifiable systems must be measured [3][5]. What remains uncertain is whether the Atlas approach generalizes to other graph-based indices, to filtered search, and to embedding dimensions beyond those tested without prohibitive proving cost.

About These Sources

This research page is built on 5 studies (4 peer-reviewed, 1 preprint) — published from 2015 to 2026, 3 from 2024 or later — selected as the most relevant from 6 studies that passed quality screening, drawn from 50 papers retrieved from a database of over 500 million.

Sources used in this answer