Adversarially Robust Approximate Furthest Neighbor

AIPR assessment

This is a hard, moderately saturated theoretical problem in high-dimensional geometry, with years of work on nearest, furthest, and adaptive query structures. The main strengths reinforce each other: a clean theoretical framing, a new robustness recipe, and a concrete sublinear-time guarantee on a previously open adaptive setting. The weaknesses also compound: no experimental validation, no code, and a technically dense proof make the result harder to audit and harder to translate into practice.

Abstract

We work in the adaptive query model, where one is given a point set $P \subset \mathbb{R}^d$ and seeks to construct a data structure that can answer correctly and efficiently a sequence of adaptive queries. In this model, an adversary observes the answers returned by the data structure to previous queries $q_1, \ldots, q_{i-1}$ and, based on this information, chooses the next query point $q_i$. This setting captures strong forms of adaptivity that naturally arise in modern machine learning pipelines, and rules out many classical randomized techniques that assume oblivious queries. Our focus is the problem of furthest neighbor search in this adaptive setting, a fundamental problem in several learning tasks, including diversity maximization, outlier and anomaly detection, adversarial example generation, and more. We present the first adversarially robust data structure for $c$-approximate furthest neighbor queries that achieves query time $\tilde{O}( \min( d n^{1/c^2}, n^{2/c^2} + d))$. This matches the $n$ dependency in the query time of the seminal result by Indyk~[SODA'03] for $c$-approximate furthest neighbor in the oblivious setting, and improves upon the $\tilde{O}(n + d)$ query time achieved via the adaptive distance estimation framework of Cherapanamjeri and Nelson~[NeurIPS'20] for a wide range of natural parameters. To complement this result, we present an adversarial attack against oblivious approximate furthest neighbor algorithms. Specifically, we show that the data structure from the algorithm by Indyk fails to maintain its guarantees against adaptive queries.

Score Breakdown

More from this week

• VeriCache: Turning Lossy KV Cache into Lossless LLM Inference
• TriAxialKV: Toward Extreme Low-Precision KV-Cache Quantization for Agentic Inference Tasks
• ContraFix: Agentic Vulnerability Repair via Differential Runtime Evidence and Skill Reuse
• Loaded Dice: Solving the Non-Selection Problem for Scalable Probabilistic RowHammer Defense
• Stop Starving or Stuffing Me: Boosting Firmware Fuzzing Efficiency with On-demand Input Delivery