- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper proposes SOCKET, a training-free sparse attention that ranks cached keys with a soft variant of sign-random-projection LSH. During prefill, each key is hashed once into tables of hyperplanes and stored as bucket codes together with its value norm. At decoding time, instead of assigning the query to a single bucket per table, the query defines a softmax distribution over all buckets with temperature , and each key’s score is the probability mass its bucket receives, summed over tables and weighted by the value norm. The exact softmax attention is computed over only selected top-k keys. They evaluate on LongBench and RULER with several models, and report custom CUDA/Triton kernels that surpass FlashAttention3 in decoding throughput beyond ~70K tokens (up to ~1.5$\times$ at 140K, 33$\times$ sparsity), at about 15% additional memory.
Critical strengths
S1. Simple and training-free method.
SOCKET replaces the hard query bucket of LSH with a soft bucket distribution, requires no calibration or clustering, and gives lower prefill cost than data-dependent indexers like PQCache.
S2. Kernel implementation.
The efficiency claim is backed by actual fused CUDA/Triton kernels, with measured decoding speedups over FlashAttention3 in GPT-FAST at long contexts, rather than simulated or theoretical numbers.
Critical weaknesses
W1. Accuracy and speed are evaluated in non-overlapping regimes.
Accuracy is evaluated on RULER-HARD-32K and LongBench (typically at most around 32K), with no results at 64K or longer, whereas the decoding speedup appears only beyond ~70K. Throughput is compared only against FlashAttention3, with no decoding-speed comparison against the sparse baselines used in the accuracy tables. The hash metadata adds ~15% to the KV cache, but throughput under batched or memory-bound settings is not reported.
W2. No dense reference in the main tables.
Dense results appear only in the appendix, where the gap at high sparsity is substantial. This sits uneasily with the claim of performance “close to dense attention even at extreme sparsity.”
W3. The soft-vs-hard advantage relies on per-task tuning, and the method is not data-agnostic in practice. The headline 85.08 in Table 2 equals the average of per-task best from Table 5c. With one fixed , the best SOCKET average is 83.28, below the 84.0 of hard LSH (, ) at the same 600 bits. The is also set per dataset (0.3–0.7, Table 20), some tasks override , and fwe uses , which is nearly hard hashing.
W4. Baseline coverage and related work on hash-based KV coverage are incomplete. Loki and vAttention are excluded, although the paper evaluates in vAttention's protocol and includes Double Sparsity, a closely related method. Learned hashing for decoding-time KV retrieval [1], which also compares against random-projection LSH, is not discussed, so the positioning of training-free soft LSH relative to learned hashing is unclear.
W5. The theory does not support the central claim. Theorem 3 targets the angular kernel, i.e., the expectation of the hard collision score, and recovers it as , so it cannot show that soft collisions are better. Its bias term is also essentially 1 at the settings used: since , we have for , , . The analyzed sampling estimator is not the one evaluated, and the deployed top-k procedure has no guarantee. Lemma 4's soft-over-hard conclusion follows from assuming soft scores are linear in (Cauchy--Schwarz), which does not match Algorithm 1 (rows , ), and in Table 3 Corr is undefined and Var is not comparable across scores of different scales.
[1] Li, Wenhao, et al. "Spotlight attention: Towards efficient llm generation via non-linear hashing-based kv cache retrieval." Advances in Neural Information Processing Systems 38 (2025): 86091-86115.
Questions for authors
Q1. Can you report accuracy for SOCKET, dense attention and the main baselines at 64K–128K, where the decoding speedup appears? Can you also report decoding latency against the sparse baselines under batched, memory-constrained settings?
Q2. Can you report all tasks with a single per model, and explain how the per-task settings were chosen without access to the evaluation data? Can you also provide seed-level error bars for the soft-vs-hard comparison?
Q3. In Table 2, hard LSH at 600 bits uses 2.8$\times$ the memory of SOCKET. Is this a storage-format difference, and what are its memory and speed with bit-packing?
Q4. Can you discuss Spotlight Attention?
Q5. Can you provide one main-table comparison with a matched metadata budget (bits per token) and seed variance on the averages?
Q6. What does Theorem 3 imply at the settings actually used, given ? Can you measure recall against oracle top-k for the deployed procedure, and report the empirical distribution of to check the linearization in Lemma 4? How are Corr and Var defined in Table 3?
2 comments
Further Clarification
We thank the reviewer for their continued engagement and thoughtful questions. We are pleased that our responses have substantially addressed the concerns raised in Q2, Q3, Q4, and Q5. We appreciate the opportunity to provide further clarification and address each of the remaining questions below.
Q1. Accuracy of SOCKET.
A1. The degradation observed in Llama-3.1-8B under induced sparsity may not generalize to other models. To make this comparison explicit, we additionally evaluate Llama-3.1-8B and Qwen3.5-9B at 33$\times$ sparsity across both 64K and 128K context lengths. Please refer to our response to Q3 of Reviewer LsoU in the "Further Clarifications" section for the corresponding results.
Q2. Calibration claim.
A2. We have incorporated this update into the latest version. We apologize for the delay.
Q3. Theorem 3 Bound Interpretation.
A3. Thank you for the follow-up. We emphasize that Theorem 3 states the asymptotic scaling of a high-probability error bound in notation. Directly substituting the finite parameter values into this asymptotic expression does not yield a meaningful numerical upper bound, since asymptotic scaling bound suppresses constants and logarithmic factors.
The asymptotic rate describes how the bound changes with , , and . Reporting guarantees in terms of their scaling is standard in the analysis of randomized estimators. For example, Claim 1 of [1] gives the feature-count scaling for uniform kernel approximation. In attention approximation, Theorem 4 of [2] similarly gives the scaling of the number of random projections sufficient for a prescribed accuracy and fixed success probability.
On the other hand, the analysis of Euler discretization in [3, p. 607] provides a clean and direct perspective for interpreting our . In the setting of [3], the mean-squared error has a sampling contribution of order for simulated paths and a squared discretization bias of order for step size . At fixed , simulating more paths reduces the sampling variance while the discretization bias persists. In SOCKET, at fixed , increasing improves the approximation of the population soft-score output at rate , and increasing improves the sampling approximation of the finite-table output at rate . Under the conditions of Theorem 3, these rates hold even when .
This type of conservative bound is common in ML and scientific computing. For example, [4] identifies an additive worst-case penalty for truncation and notes that this penalty is often absent in numerical practice (eq. (1.11) and Remark 5.1). The regularized-kernel analysis in Performer offers a parallel within attention. It bounds finite-feature deviations from the regularized softmax kernel and separately bounds the discrepancy between that kernel and the standard softmax kernel [2, Theorems 1 and 3].
We hope these additional details comprehensively address the reviewer’s remaining concerns and provide further clarity of our contributions.
[1] A. Rahimi and B. Recht. Random Features for Large-Scale Kernel Machines. NeurIPS 2007.
[2] K. Choromanski et al. Rethinking Attention with Performers. ICLR 2021.
[3] M. B. Giles. Multilevel Monte Carlo Path Simulation. Operations Research, 56(3), pp. 607-617, 2008.
[4] N. Halko, P. G. Martinsson, and J. A. Tropp. Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions. SIAM Review, 53(2), pp. 217-288, 2011.
Thank you for the detailed response and additional experimental results, including long-context results and comparison with bit-packing. While some of my concerns are addressed, there are still remaining things.
The accuracy of SOCKET is significantly lower than dense at 64K/128K according to suggested results in the rebuttal and sometimes similar to the accuracy of PQCache. The authors responded that per-task calibration is needed, but the paper still says "without retraining or calibration" in the revised manuscript. Also, it remains unclear whether the bound condition of Theorem 3 is meaningful when ϵt is close to 1, not approaching 0.
Therefore, I keep my original rating of 2.