Metraipolis › archive › dc_b4e3624a35dc

Atlas: Efficient Verifiable Semantic Search — arXiv:2609.11841

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.11841
License (as archived)
CC0-1.0
Archived
2026-10-16T05:46:44.898Z
SHA-256 of the archived text
2e03671b915a24263d2150c452c928f687f82043d034edc8ea9ac19e195af0be
Stable URL of this page
https://metraipolis.com/documento/dc_b4e3624a35dc

How to cite

Atlas: Efficient Verifiable Semantic Search — arXiv:2609.11841 — arXiv (en), https://arxiv.org/abs/2609.11841 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_b4e3624a35dc (Metraipolis archive dc_b4e3624a35dc, sha256 2e03671b915a24263d2150c452c928f687f82043d034edc8ea9ac19e195af0be)
BibTeX
@misc{dcb4e3624a35dc,
  title = {Atlas: Efficient Verifiable Semantic Search — arXiv:2609.11841},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.11841},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_b4e3624a35dc; sha256 2e03671b915a24263d2150c452c928f687f82043d034edc8ea9ac19e195af0be},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.11841. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: fiducia digitale e crittografia (retro-catalogo arXiv: annunci del 2026-09-11 in cs.CR).
Categorie arXiv: Cryptography and Security (cs.CR).
Pagina del lavoro: https://arxiv.org/abs/2609.11841 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T05:30:39.405Z dalla pagina https://arxiv.org/catchup/cs.CR/2026-09-11?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).