Atlas: Efficient Verifiable Semantic Search
[Kryptografia i bezpieczeństwo] Autorzy: Nikolay Avramov, Hidde Lycklama, Alexander Viand i 1 więcej
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 pr…
- Kategoria arxiv
- cs.CR
- Kategoria
- Kryptografia i bezpieczeństwo