- Rating
- 3
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper studies how many keys need to be retrieved to approximate softmax attention when maximum inner product search is a black-box operation. It develops a priority-sampling framework, gives algorithms and lower bounds for different index budgets, and proposes SoftmaxLift, which implements priority sampling through only a single MIPS index by adding one random coordinate. Experiments show attention approximation and downstream performance at 128K and 1M context lengths.
Critical strengths
-
The paper answers a interesting question and builds a clear theoretical framework. Sampling + topk for attention is not new, as known as vAttention (ICLR 2026). What is interesting here is the systematic treatment of retrieval cost: the paper studies what can be achieved with different numbers of indices and provides lower bounds explaining the limitations.
-
The idea makes sense, and SoftmaxLift is simple but practical. Only using the largest attention weights is not always enough to estimate the full weighted sum. Priority sampling addresses this naturally, and SoftmaxLift supports blackbox MIPS implementing priority sampling by adding one coordinate is a natural and useful method.
-
The experiments show a clear estimation benefit. At 128K with exact retrieval and a budget of 128, SoftmaxLift reduces attention error from 0.3831 for TopK to 0.0794 and improves the RULER score from 40.56 to 60.22 (Table 2). The comparisons across budgets and search backends support the usefulness of the sampling strategy.
Critical weaknesses
-
The experiment on Table 2 needs more explanation. IVF achieves higher recall than HNSW (0.966 vs. 0.926), yet has a lower RULER score (45.28 vs. 50.53). What explains this discrepancy? Moreover, their RULER scores fall approximately 15 and 10 percentage points below SoftmaxLift–Flat (60.22), respectively. What makes these retrieval errors so consequential for downstream quality? Figure 3 already explores larger retrieval budgets; could the authors explain how much increasing (k) recovers the lost quality, and why any remaining gap persists?
-
Additional experiment with an existing sparse-attention method would be more helpful. Since your framework treats vector search as a black box, SoftmaxLift seems applicable to existing MIPS-based top-k attention methods, such as PQCache (SIGMOD 2025) or RetrievalAttention (NeurIPS 2025). I am curious whether these methods would benefit from your technique.
-
Some minors in Appendix: In Claim 7, the variance bound at lines 717–718 is missing a square on the maximum value norm. In Lemma 12, the query is defined as (q_i=\tau\log p_i), but the proof subsequently states (\langle q,x_i\rangle=\log p_i) and uses (\exp(q_i)) to recover weights (p_i). The \tau is missing.
Questions for authors
Please check the weaknesses above.
3 comments
If IVF and HNSW miss keys in roughly the same way, I’d expect higher recall to generally bring SoftmaxLift closer to the exact-search result(highest among the SoftmaxLift variants in Table 2). IVF may have happened to miss a few keys needed to answer questions that HNSW got right. It’s also possible that IVF’s partitioning makes it systematically more likely to miss certain keys. This rebuttal only gives me a plausible explanation for why recall and RULER score can diverge. I would have liked to see a few more runs or an analysis of individual failures to tell which explanation fits this result. I understand that testing SoftmaxLift with PQCache or RetrievalAttention would take more work. For me, the problem about recall and RULER mismatch in the existing experiment is the more important to answer.
Thank you for following up -- we agree that this is an interesting question to dig into. We ran some additional experiments to address why IVF has higher recall yet HNSW has similar attention error and better benchmark scores. We address this in two parts: (1) why HNSW gets better benchmark scores than IVF even though the attention errors are roughly the same, and (2) why HNSW gets similar attention error to IVF even though IVF has much better recall.
(1) Attention error vs. benchmark score. When we look at attention errors and benchmark scores task-by-task rather than aggregated across tasks, we see that attention error and benchmark score are actually well-aligned. Aggregating creates a “gerrymandering”-style effect: the tasks where HNSW loses to IVF substantially increase the attention error of HNSW but only slightly increase the average benchmark score.
For more detail, here is a table showing benchmark scores, attention accuracies, and recall for SoftmaxLift with HNSW and with IVF run on 130 document examples (13 from each task, the 60 from the paper and 70 more we have added since).
| Task | IVF attention error ↓ | HNSW attention error ↓ | IVF RULER (%) ↑ | HNSW RULER (%) ↑ | IVF recall ↑ | HNSW recall ↑ |
|---|---|---|---|---|---|---|
| niah_single_1 | 0.1129 | 0.1880 | 92.31 | 30.77 | 0.9685 | 0.9429 |
| niah_single_2 | 0.1380 | 0.1106 | 84.62 | 100.00 | 0.9666 | 0.9159 |
| niah_multikey_1 | 0.1361 | 0.1108 | 69.23 | 100.00 | 0.9653 | 0.9150 |
| niah_multikey_2 | 0.0971 | 0.1164 | 53.85 | 46.15 | 0.9741 | 0.9354 |
| niah_multivalue | 0.1409 | 0.1056 | 25.00 | 32.69 | 0.9636 | 0.9142 |
| niah_multiquery | 0.1354 | 0.1047 | 26.92 | 53.85 | 0.9637 | 0.9114 |
| vt | 0.1040 | 0.1193 | 33.85 | 53.85 | 0.9608 | 0.9474 |
| fwe | 0.0855 | 0.1178 | 56.41 | 61.54 | 0.9720 | 0.9431 |
| qa_1 | 0.1187 | 0.1154 | 23.08 | 46.15 | 0.9668 | 0.9167 |
| qa_2 | 0.1277 | 0.1166 | 23.08 | 23.08 | 0.9646 | 0.9118 |
| Overall | 0.1205 | 0.1197 | 48.83 | 54.81 | 0.9662 | 0.9263 |
(IVF uses 1,024 clusters and nprobe=96. HNSW uses M=48, efConstruction=500, efSearch=176)
There are 4 tasks where HNSW incurs larger attention error than IVF. These contain the only 2 tasks where HNSW has a lower benchmark score (niah_single_1, niah_multikey_2). In the other 2 tasks (vt, fwe), HNSW has a higher benchmark score, but either the attention errors or benchmark scores are close to tied. Interestingly, these 4 tasks are exactly those where a common set of words is repeated many times (e.g., in niah_single_1, the key words are inserted inside a repeating small phrase). It’s possible that this generates key vectors with many near-duplicates of the same point (up to positional embeddings). We did not look further at how exactly this geometry affects the different oracles, but perhaps graph-based oracles like HNSW struggle with such duplicates. The other 6 tested tasks have a much more diverse set of words with few repetitions.
(2) Recall vs. attention error. For this part of the question, we confirmed that even though IVF consistently misses less points in the top-k than HNSW, the missed points for IVF carry more attention weight. The following table contains the average attention mass of the keys in the true top-k that are missed by the approximate oracle:
| Oracle | Recall@128 ↑ | Average attention weight of a missed key | Total missed attention mass, averaged per query |
|---|---|---|---|
| IVF | 96.46% | 0.002084 | 0.009438 |
| HNSW | 92.36% | 0.000833 | 0.008141 |
Results are averaged over 41,244 queries from a sample of 192 heads in our 128k-context experiments.
The average key missed by IVF has about 2.5x the attention weight of the average key missed by HNSW. Notably, IVF misses less than half as many keys as HNSW, but it misses more attention weight in total. Restricting to the 6 tasks where HNSW has better attention error, the effect is even stronger: the average key missed by IVF has about 3.2x the attention weight of the average key missed by HNSW.
So, it seems that HNSW misses more keys than IVF, but the keys missed by HNSW are in the top-k due their large lift components (i.e., their final coordinate in the SoftmaxLift transform) rather than having large attention mass. We do not have a concrete explanation for this phenomenon. But, one hypothesis is that IVF’s spherical k-means clustering concentrates keys with large lift components into clusters whose centroids score highly against many queries, using up probes that could otherwise reach some keys with high attention weight. HNSW’s graph search might be less susceptible to this effect. Testing this would require further experimentation.
These results suggest that although SoftmaxLift outperforms other retrieval strategies, its transformation of the key vectors may introduce systematic biases in approximate MIPS oracles. Designing retrieval strategies that reduce these biases could be an interesting direction for future work.
Thanks for the constructive and detailed review!
Mismatch between recall and benchmark score. The reviewer points out an interesting discrepancy between IVF and HNSW (with SoftmaxLift). IVF achieves better recall (0.966 vs 0.926), similar attention error, but worse RULER score (45.28 vs. 50.53). While we don’t have a definitive explanation for this particular result, we believe there are two relevant factors.
First, recall@k does not capture the relative importance of the retrieved keys. It treats all keys equally, whereas their contributions to the attention vector can vary substantially. Thus, a method with higher recall may still miss a small number of keys with large attention contributions and incur more attention error.
Second, average attention error does not fully determine downstream task completion. RULER consists of needle-in-a-haystack-like tasks where success is determined by retrieving a small number of tokens from a long context. It is possible that for these tasks, approximating the attention vector is less important than finding the value vectors corresponding to the important tokens. An important direction for future work is to evaluate our methods on a more diverse set of benchmarks to see if this discrepancy persists.
Increasing the retrieval budget. Increasing the retrieval budget k helps reduce the variance of the attention estimator. However, for most approximate oracles such as IVF and HNSW, increasing k alone only extends the list of retrieved keys and does not recover important keys that were missed at smaller retrieval budgets. Such errors can only be corrected by adjusting the parameters of the search oracle or choosing a different search oracle altogether.
Comparison with existing methods. We thank the reviewer for this suggestion. SoftmaxLift is directly applicable to both PQCache and RetrievalAttention. Both use TopK retrieval but differ in their choice of MIPS oracle: PQCache performs MIPS over product-quantized keys, and RetrievalAttention uses a graph index designed for out-of-distribution queries. Our work instead focuses on improving the retrieval strategy and estimator for a fixed oracle, which is why we evaluated a relatively small set of standard oracles. Combining SoftmaxLift with the search oracles of PQCache and RetrievalAttention (and developing more optimized oracles in general) is a reasonable avenue for further experimentation, and we leave it for future work.
Typographical fixes. We thank the reviewer for pointing out these typos. They have been fixed in the updated version of the paper.