Attention via Black-Box Vector Search
The authors investigate how many keys must be retrieved from a black-box Maximum Inner Product Search (MIPS) oracle to achieve an epsilon-accurate attention estimate. They propose priority sampling and a 'Softmax Lift' algorithm that demonstrate efficient tradeoffs between retrieval cost and oracle access, showing that specific key retrieval counts are necessary and sufficient for accuracy.