Overview
Semantic search serves as a foundational component in contemporary applications, including recommender systems, web search, and retrieval-augmented generation (RAG) for large language models. In current deployments, the provider retains control over both the search index and query execution mechanisms. This configuration necessitates client trust that search results adhere to the specified algorithm and originate from the intended index. Providers, however, possess the capacity to modify search operations without client detection, potentially by truncating search processes to reduce costs, introducing biases into results, or deviating from agreed execution protocols.
Verifiability offers a mechanism to mitigate this trust dependency by furnishing proof that search results align with the predetermined algorithm applied to a committed index. The efficient realization of such verifiability presents significant challenges, particularly because retrieval at scale often relies on Hierarchical Navigable Small World (HNSW) graphs. HNSW is a graph-based algorithm characterized by data-dependent traversal patterns, which present difficulties in mapping onto the fixed constraint systems typically employed by zero-knowledge proofs (ZKPs).
Prior verifiable systems have generally focused on regular, cluster-based indices due to their simpler encoding properties for ZKPs. This approach, however, often entails a compromise in recall performance when compared to graph-based search methods. This research introduces Atlas, a system designed to enable a provider to cryptographically prove the accurate answering of a query against its committed index, without disclosing the index's contents. Atlas represents the first system to demonstrate verifiable graph-based search capabilities at scale.
Research Context
The imperative for verifiable semantic search stems from the inherent trust model in provider-controlled search infrastructures. Existing systems grant providers unilateral control over the search index and execution. This control implies that providers could, for instance, limit search depth to optimize operational expenditures, manipulate result ordering to favor certain outcomes, or otherwise deviate from agreed-upon algorithmic specifications. Such deviations can occur without explicit client knowledge or detection.
Traditional approaches to verifiability face a fundamental challenge when applied to advanced search algorithms like HNSW. HNSW's efficiency in large-scale retrieval is partly attributed to its data-dependent graph traversal, where the path taken during a search is not fixed but dynamically determined by the input query and the index structure. This characteristic conflicts with the requirements of many zero-knowledge proof systems, which often require fixed, predictable computational structures for efficient proof generation. Consequently, previous verifiable retrieval systems have often gravitated towards index structures that are more amenable to ZKP encoding, such as cluster-based indices. This choice, while simplifying verifiability, typically results in a reduction of search recall compared to the performance offered by HNSW.
Approach
Atlas is fundamentally built upon a novel zero-knowledge proof specifically engineered for HNSW search. Its design incorporates three core techniques to achieve efficient verifiability without compromising HNSW's performance characteristics or revealing the underlying index:
- Offline Preprocessing for Cost Shifting: The system employs a preprocessing phase that shifts all database-dependent computational costs to an offline stage. This design ensures that the per-query proving cost scales with the length or complexity of the HNSW traversal during query execution, rather than with the overall size of the entire database.
- HNSW Restructuring for Fixed-Size State: Atlas includes a restructuring of the HNSW algorithm itself. This modification transforms HNSW into a procedure with a fixed-size state, while rigorously proving that this restructured version yields identical search results to the original HNSW algorithm. This fixed-size state is crucial for efficient ZKP integration.
- Timestep-Tagged Batching: To further optimize proving efficiency, Atlas incorporates a timestep-tagged batching mechanism. This technique merges the individual per-step arguments generated throughout the entire HNSW traversal into a single, consolidated argument. This reduces the overhead associated with proving each discrete step of the search process.
These techniques collectively enable Atlas to generate cryptographic proofs for HNSW search efficiently, making it feasible to verify search operations at scale while maintaining the performance advantages of graph-based indexing.
Findings
The Atlas system demonstrated verifiable graph-based search capabilities at scale, achieving specific performance metrics:
- Atlas proved a query on the SIFT1M benchmark in under one second.
- For a larger scale, it completed query verification in 2.0 seconds when operating with 100 million vectors.
- The system consistently maintained the recall performance equivalent to that of plaintext HNSW.
- During the verification process, Atlas revealed no information about the underlying index beyond the actual search result itself.
- When integrated into a complete Retrieval-Augmented Generation (RAG) pipeline, Atlas's proven retrieval mechanism preserved end-to-end answer quality.
- Furthermore, within the RAG context, Atlas achieved higher quality results at a lower proving cost compared to all previously established verifiable retrieval systems.
Why This Matters
This research addresses a fundamental trust deficit in provider-controlled semantic search environments, where clients currently rely on implicit assurance that search operations are executed as specified. By enabling efficient verifiability for graph-based search, Atlas offers a mechanism to cryptographically guarantee algorithmic adherence and index integrity, fostering greater transparency and trust in critical applications like recommender systems and RAG. The system's ability to maintain high recall and improve RAG quality while introducing verifiability at practical speeds represents a significant advancement for secure and reliable information retrieval.