Robust Approximate Nearest Neighbor Search for Any Dataset

Approximate Nearest Neighbor Search (ANN) is an important algorithmic primitive that has found a plethora of applications in machine learning and information retrieval. The classic approach to this problem due to Indyk and Motwani (1998) leverages Locality Sensitive Hashing (LSH) by sampling multiple hash functions that are likely to identify similar data points. This approach has, however, been demonstrated to be vulnerable to adaptive queries and updates which may not be independent of its internal randomness (Kapralov et al. 2024). While differential-privacy-based techniques have yielded robust versions of randomized algorithms and data structures for estimation problems (Hassidim et al., 2022), ANN is a search problem: the algorithm must return an actual dataset point, without obfuscating the output by adding noise or rounding it. Feng et al. (2025) circumvent this limitation by relying on a density assumption that bounds the number of points near each query point. We study a stronger worst-case model in which the adversary chooses both the initial dataset and an adaptive query sequence. For LSH-equipped metric spaces, we give adversarially robust ANN algorithms with sublinear query time whose guarantees do not depend on any structural assumption on the dataset. The main technical challenge is to preserve sublinear search time when the adversary selects a dataset with arbitrarily many points near a query. Rather than applying differential-privacy robustification as a black box, we develop search-specific mechanisms: fairness as a route to adaptive security, a bucketing reduction from search to robust decision, and a concentric annuli construction that improves the query-time exponent. Moreover, for low-dimensional spaces, we give algorithms with a strong ``for-all'' guarantee, which are correct for every possible query.