5 papers · 1 filter
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…
Learning Partition Trees for Nearest Neighbor Search
Sanjeev Khanna, Ashwin Padaki, Erik Waingarten
We study nearest neighbor search from the perspective of data-driven algorithm design: given a dataset of size and sample access to a query distributio…
Prune, Don't Rebuild: Efficiently Tuning -Reachable Graphs for Nearest Neighbor Search
Tian Zhang, Ashwin Padaki, Jiaming Liang +2
Vector similarity search is an essential primitive in modern AI and ML applications. Most vector databases adopt graph-based approximate nearest neighbor (ANN) search algorithms, s…
A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams
Sanjeev Khanna, Ashwin Padaki, Krish Singal +1
We study the space complexity of estimating the diameter of a subset of points in an arbitrary metric space in the dynamic (turnstile) streaming model. The input is given as a stre…
Sparse Navigable Graphs for Nearest Neighbor Search: Algorithms and Hardness
Sanjeev Khanna, Ashwin Padaki, Erik Waingarten
We initiate the study of approximation algorithms and computational barriers for constructing sparse -navigable graphs [IX23, DGM+24], a core primitive underlying recent advance…