通过黑盒向量搜索实现注意力：稀疏注意力检索键数量的理论边界

研究以黑盒 MIPS 预言机检索多少键才能输出 ε-精确的注意力估计，通过 priority sampling 框架统一了已有方法。单个 MIPS 索引下 Θ(√n/ε) 个键既充分又必要；使用 Θ(log n) 个索引时仅需 O(log n+1/ε²) 个键且接近最优。