Efficient Algorithms for Adversarially Robust Approximate Nearest Neighbor Search
Alexandr Andoni, Themistoklis Haris, Esty Kelman, Krzysztof Onak · 2026
Read Efficient Algorithms for Adversarially Robust Approximate Nearest Neighbor Search by Alexandr Andoni, Themistoklis Haris, Esty Kelman, Krzysztof Onak (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-00272.txt.
Introduction
Alexandr Andoni works with Themistoklis Haris, Esty Kelman, and Krzysztof Onak on nearest neighbor search that survives a hostile adversary. The foe controls both the dataset and the query stream. It adapts each query to what it has learned. Standard search structures can leak their inner randomness. That leak lets an attacker steer later queries badly.
A fairness link gives the first line of defense. Fair search hides randomness with information theoretic cover. A private mechanism on hashing then adds data independent strength. One barrier, though, pins query time too high. A new ring shaped hashing design breaks that barrier. It blends fairness and privacy in one construction. Timing data is released in a robust new way. Low dimension cases get their own algorithms. Those promise correctness on every query, with high probability. Hamming and normed spaces both gain simpler covers.
Catalog record
| CREATOR | Alexandr Andoni, Themistoklis Haris, Esty Kelman, Krzysztof Onak |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 86 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-00272
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Efficient Algorithms for Adversarially Robust Approximate Nearest Neighbor Search Alexandr Andoni, Themistoklis Haris, Esty Kelman, Krzysztof Onak Abstract We study the Approximate Nearest Neighbor (ANN) problem under a powerful adaptive adversary that controls both the dataset and a sequence of Q Q queries. Primarily, for the high-dimensional regime of d = ω ( Q ) d=\omega(\sqrt{Q}) , we introduce a sequence of algorithms with progressively stronger guarantees. We first establish a novel connection between adaptive security and fairness , leveraging fair ANN search ( 10 ) to hide internal randomness from the adversary with information-theoretic guarantees. To achieve data-independent performance, we then reduce the search problem to a robust decision primitive, solved using a differentially private mechanism ( 40 ) on a Locality-Sensitive Hashing (LSH) data structure. This approach, however, faces an inherent n \sqrt{n} query time barrier. To break the barrier, we propose a novel concentric-annuli LSH construction that synthesizes these fairness and differential privacy techniques. The analysis introduces a new method for robustly releasing timing information from the underlying algorithm instances and, as a corollary, also improves existing results for fair ANN. In addition, for the low-dimensional regime d = O ( Q ) d=O(\sqrt{Q}) , we propose specialized algorithms that provide a strong “for-all” guarantee: correctness on every possible query with high probability. We introduce novel metric covering constructions that simplify and improve prior approaches for ANN in Hamming and ℓ p \ell_{p} spaces. 1 Introduction Randomness is a crucial tool in algorithm design, enabling resource-efficient solutions by circumventing the worst-case scenarios that plague deterministic approaches ( 48 ) . The classical analysis of such algorithms assumes an oblivious setting, where data updates and queries are fixed beforehand. However, this assumption breaks down in the face of an adaptive adversary , who can issue queries based on the algorithm’s previous outputs. These outputs can leak information about the algorithm’s internal randomness, allowing an adversary to construct query sequences that maliciously break the algorithm’s performance guarantees ( 39 ; 36 ) . Significant progress has been made in designing adversarially robust algorithms for estimation problems , where the output is a single value ( 47 ; 40 ; 21 ; 9 ; 16 ; 57 ; 26 ) . A common defense involves sanitizing the output, for example, by rounding or adding noise, often borrowing techniques from differential privacy to ensure the output reveals little about the algorithm’s internal state ( 40 ; 9 ; 15 ) . However, these techniques do not directly apply to search problems . In a search problem, the algorithm must return a specific element from a given dataset. Outputting a raw data point can leak substantial information, and there is no obvious way to add noise or otherwise obscure the output without violating the problem’s core constraint of returning a valid dataset element. Perhaps the most fundamental search problem is Approximate Nearest Neighbor (ANN) Search , which has numerous applications ranging from data compression and robotics to DNA sequencing, anomaly detection and Retrieval-Augmented Generation (RAG) ( 50 ; 44 ; 41 ; 55 ; 54 ; 18 ; 37 ; 46 ) . Formally, we define the problem as follows: Definition 1.1 (The (c,r) -ANN problem) . Given a dataset S of n points in a metric space (\mathcal{M},||\cdot||) and a radius r>0 , let B_{S}(q,r):=\{p\in S:||p-q||\leq r\} . Given a query point q\in\mathcal{M} and approximation parameter c\geq 1 , the goal is to build a data structure which finds a point in B_{S}(q,cr) if B_{S}(q,r)\neq\emptyset . If B_{S}(q,cr)=\emptyset , the algorithm is required to answer \perp . Apart from queries, the dataset S itself may also be obliviously updated via additions or deletions of points. A data structure for solving this problem is evaluated in terms of its space complexity, query runtime, and update runtime as functions of the dataset size n , the parameter c and possibly the total number of queries. Achieving the desired trade-off of sublinear query time and near-linear space has largely been possible only through randomization. Indeed, one of the most prominent family of algorithms for ANN is based on Locality-Sensitive Hashing (LSH) , which has been the subject of a long and fruitful line of research in the oblivious setting ( 35 ; 43 ; 8 ; 2 ; 6 ; 4 ; 3 ; 5 ; 42 ; 19 ; 1 ) . ANN Algorithms that rely on LSH achieve query time complexity of \widetilde{O}(dn^{\rho}) * * * We use the \widetilde{O} notation to hide polylogarithmic factors. and space complexity \widetilde{O}(n^{1+\rho}) , where d is the dimension of \mathcal{M} and \rho=\rho(c)\in(0,1) is a fixed constant depending on c and the LSH construction † † † For example, when \mathcal{M}=\{0,1\}^{k} under the Hamming distance and c\geq 1 is the approximation parameter, the state-of-the-art construction of 7 yields \rho=\frac{1}{2c-1} . We shall use \rho and \rho(c) interchangeably. . The vulnerability of these classical randomized structures was recently highlighted by 45 , who demonstrated an attack on standard LSH data structures. They showed that an adaptive adversary can use a polylogarithmic number of queries to learn enough about the internal hash functions to force the algorithm to fail. Inspired by their work, which relies on certain structural properties of the dataset (e.g., an “isolated” point), we consider a powerful adversarial model where the adversary chooses both the dataset and the sequence of queries . We study the following question: Can search problems like ANN be solved efficiently in the face of adversarial queries? Our adversarial model for the (c,r) -ANN problem empowers the adversary by giving them unbounded computational resources, the ability to specify the dataset S completely, the ability to obliviously choose a sequence of updates to that dataset, and, perhaps most importantly, the ability to choose each query based on the full history of their interaction with the algorithm. While alternative adversarial models could be considered, our chosen framework maximizes generality to demonstrate that efficient data structures remain achievable even under broad constraints. 1.1 Roadmap and Discussion We begin by placing our results in the broader context of adversarial robustness, which has primarily followed two paradigms. The first is robustification via privacy ( 40 ) , where multiple independent copies of an algorithm are aggregated using a differentially private mechanism. Privacy obfuscates the internal randomness, preventing an adaptive adversary from predicting future behavior. The second is for-all algorithms ( 34 ) , which succeed on every input, but typically incur high runtime or space overhead due to discretization and union bounds, making them problem-specific. The ANN problem poses a further challenge: it is a search problem rather than an estimation problem, so adding noise to outputs would destroy correctness. One natural way to resolve this is by reducing search to collections of decision problems that admit privacy-based robustification. In ANN, partitioning the dataset and solving weak decision problems in each part allows robust recovery of a valid neighbor while retaining sublinear query time and space. We believe that the idea of reducing from search to robust decision may extend to other search problems. Our main conceptual contribution is identifying a third route to robustness: fairness . Informally, fair algorithms avoid bias toward particular