4 papers
Attention via Black-Box Vector Search
Stepan Zharkov, Krish Singal, Ashwin Padaki +1
Sparse attention mechanisms estimate attention over tokens using a small subset of keys. Many existing approaches use maximum inner product search (MIPS) to retrieve the heavie…
Fast Geometric Spanners via Approximate Nearest Neighbor Search
Alexandr Andoni, Manuel Paez, Krish Singal +1
We study the problem of constructing metric spanners in general metric spaces in subquadratic time when given blackbox access to a fast algorithm for batch approximate nearest neig…
Nearly Optimal Attention Coresets
Edo Liberty, Alexandr Andoni, Eldar Kleiner
We consider the problem of estimating the Attention mechanism in small space, and prove the existence of coresets for it of nearly optimal size. Specifically, we show that for any…
A Framework for Building Data Structures from Communication Protocols
Alexandr Andoni, Shunhua Jiang, Omri Weinstein
We present a general framework for designing efficient data structures for high-dimensional pattern-matching problems () through communication mode…