Atlas: Efficient Verifiable Semantic Search

• URL: http://arxiv.org/abs/2609.11841v1
• Date: Thu, 10 Sep 2026 17:30:39 GMT
• Title: Atlas: Efficient Verifiable Semantic Search
• Abstract summary: We present Atlas, a system that lets a provider prove a query was answered correctly against its committed index without revealing the index.<n>At its core is a new zero-knowledge proof for HNSW search, built on three techniques.<n> Atlas is the first to demonstrate verifiable graph-based search at scale.
• Score: 42.56979915155187
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Semantic 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. A provider may truncate search to cut cost, bias results, or otherwise deviate from the specified execution undetected. Verifiability can remove this trust assumption by proving that results follow the agreed algorithm over a committed index. Realizing this efficiently is hard, as retrieval at scale relies on HNSW, a graph-based algorithm whose data-dependent traversal maps poorly onto the fixed constraint systems of zero-knowledge proofs. Prior verifiable systems therefore target regular, cluster-based indices that are easier to encode, sacrificing the recall of graph-based search. We present Atlas, a system that lets a provider prove a query was answered correctly against its committed index without revealing the index. At its core is a new zero-knowledge proof for HNSW search, built on three techniques: preprocessing that shifts all database-dependent cost offline, so per-query proving scales with the traversal rather than the database; a restructuring of HNSW into a fixed-size-state procedure that we prove returns the same result; and a timestep-tagged batching that merges the per-step arguments of the entire traversal into one. Atlas is the first to demonstrate verifiable graph-based search at scale, proving a query in under a second on the SIFT1M benchmark and in 2.0 seconds at 100 million vectors, while maintaining the recall of plaintext HNSW and revealing nothing about the index beyond the result. In a complete RAG pipeline, Atlas' proven retrieval preserves end-to-end answer quality, and reaches higher quality at lower proving cost than all prior verifiable retrieval systems.

Related papers

• Pre-retrieval Query Clustering for Adaptive Top-k Document Retrieval in RAG Systems [7.440012812118169]
  RAG systems commonly retrieve a fixed number of documents to ground generation.<n>simple queries suffer over-retrieval (adding noise and cost) while complex queries are under-retrieved.<n>We propose a practical, general framework for query-adaptive retrieval depth.
  arXiv  Detail & Related papers  (2026-09-11T19:57:12Z)
• SearchAtlas: Analyzing Agentic Search Strategies via Evidential Query Graphs [30.494397052362384]
  We introduce SearchAtlas, a framework that converts search trajectories into structured graphs.<n>Our automated parsing pipeline achieves a mean edge F1 of 86.4% against human-annotated graphs.<n>We analyze five search agents on three benchmarks, revealing systematic differences in search scale and evidence aggregation.
  arXiv  Detail & Related papers  (2026-09-09T23:09:26Z)
• Beyond Semantic Similarity: Rethinking Retrieval for Agentic Search via Direct Corpus Interaction [127.64173950476702]
  We study direct corpus interaction (DCI), where an agent searches the raw corpus directly with general-purpose terminal tools.<n>This approach requires no offline indexing and adapts naturally to evolving local corpora.<n>Across IR benchmarks and end-to-end agentic search tasks, this simple setup substantially outperforms strong sparse, dense, and reranking baselines.
  arXiv  Detail & Related papers  (2026-05-03T19:13:11Z)
• HaS: Accelerating RAG through Homology-Aware Speculative Retrieval [9.230969223605602]
  Retrieval becomes time-consuming as the knowledge databases grow in size.<n>We propose HaS, a homology-aware speculative retrieval framework.<n>Benefiting from the prevalence of queries under real-world popularity patterns, HaS achieves substantial efficiency gains.
  arXiv  Detail & Related papers  (2026-04-22T11:15:54Z)
• Rethinking ANN-based Retrieval: Multifaceted Learnable Index for Large-scale Recommendation System [46.70111672855811]
  MultiFaceted Learnable Index (MFLI) is a scalable, real-time retrieval paradigm that learns multifaceted item embeddings and indices within a unified framework.<n>MFLI improves recall on engagement tasks by up to 11.8%, cold-content delivery by up to 57.29%, and semantic relevance by 13.5% compared with prior state-of-the-art methods.
  arXiv  Detail & Related papers  (2026-02-18T01:31:29Z)
• Progressive Searching for Retrieval in RAG [1.1912082737504726]
  Retrieval Augmented Generation (RAG) is a promising technique for mitigating two key limitations of large language models (LLMs): outdated information and hallucinations.<n>We propose a cost-effective searching algorithm for retrieval process.<n>Our findings demonstrate that progressive search in RAG systems achieves a balance between dimensionality, speed, and accuracy, enabling scalable and high-performance retrieval even for large databases.
  arXiv  Detail & Related papers  (2026-02-07T01:12:53Z)
• TeaRAG: A Token-Efficient Agentic Retrieval-Augmented Generation Framework [62.66056331998838]
  TeaRAG is a token-efficient agentic RAG framework capable of compressing both retrieval content and reasoning steps.<n>Our reward function evaluates the knowledge sufficiency by a knowledge matching mechanism, while penalizing excessive reasoning steps.
  arXiv  Detail & Related papers  (2025-11-07T16:08:34Z)
• Semi-Parametric Retrieval via Binary Bag-of-Tokens Index [71.78109794895065]
  SemI-parametric Disentangled Retrieval (SiDR) is a bi-encoder retrieval framework that decouples retrieval index from neural parameters.<n>SiDR supports a non-parametric tokenization index for search, achieving BM25-like indexing complexity with significantly better effectiveness.
  arXiv  Detail & Related papers  (2024-05-03T08:34:13Z)
• Lexically-Accelerated Dense Retrieval [29.327878974130055]
  'LADR' (Lexically-Accelerated Dense Retrieval) is a simple-yet-effective approach that improves the efficiency of existing dense retrieval models. LADR consistently achieves both precision and recall that are on par with an exhaustive search on standard benchmarks.
  arXiv  Detail & Related papers  (2023-07-31T15:44:26Z)
• How Does Generative Retrieval Scale to Millions of Passages? [68.98628807288972]
  We conduct the first empirical study of generative retrieval techniques across various corpus scales. We scale generative retrieval to millions of passages with a corpus of 8.8M passages and evaluating model sizes up to 11B parameters. While generative retrieval is competitive with state-of-the-art dual encoders on small corpora, scaling to millions of passages remains an important and unsolved challenge.
  arXiv  Detail & Related papers  (2023-05-19T17:33:38Z)
• Autoregressive Search Engines: Generating Substrings as Document Identifiers [53.0729058170278]
  Autoregressive language models are emerging as the de-facto standard for generating answers. Previous work has explored ways to partition the search space into hierarchical structures. In this work we propose an alternative that doesn't force any structure in the search space: using all ngrams in a passage as its possible identifiers.
  arXiv  Detail & Related papers  (2022-04-22T10:45:01Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.