acceptodds
Under review as a conference paper at ICLR 2027

SOCKET: SOft Collision Kernel EsTimator for Sparse Attention

Abstract

Exploiting sparsity is key to efficient long-context inference, as attention dominates the cost of autoregressive decoding. Sparse attention reduces this cost by restricting computation to a subset of tokens, but its effectiveness hinges on fast and accurate token scoring and selection at inference time. Data-agnostic approaches offer an attractive way to perform this selection, but often incur substantial memory overhead to maintain high recall. We revisit Locality-Sensitive Hashing (LSH) and introduce SOCKET, a SOft Collision Kernel EsTimator that replaces hard bucket matches with probabilistic, similarity-aware aggregation. Traditional LSH relies on binary collision signals, providing limited information for ranking tokens and necessitating many hash tables for accurate retrieval. In contrast, soft LSH accumulates graded collision evidence across hash tables, closely preserving the true top- ordering with significantly less memory. This reframes LSH from a candidate-generation mechanism into a principled scoring kernel for sparse attention. Building on this insight, SOCKET enables efficient token selection without ad hoc voting and matches or outperforms existing sparse attention methods across multiple long-context benchmarks and diverse language models. With a custom set of CUDA/Triton kernels for scoring, selection, and attention, SOCKET achieves up to approximately higher throughput than FlashAttention.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Sparse Attention, Soft Locality Sensitive Hashing, Inference, Long-Context

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_SepnOpenReview ↗
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 LL tables of PP 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 2P2^P buckets with temperature τ\tau, 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 τ\tau from Table 5c. With one fixed τ\tau, the best SOCKET average is 83.28, below the 84.0 of hard LSH (P=2P=2, L=300L=300) at the same 600 bits. The τ\tau is also set per dataset (0.3–0.7, Table 20), some tasks override (P,L)(P, L), and fwe uses τ=10−3\tau=10^{-3}, 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 τ→0\tau \to 0, so it cannot show that soft collisions are better. Its bias term ετ\varepsilon_\tau is also essentially 1 at the settings used: since ∣ui∣≤1/d|u_i| \le 1/\sqrt{d}, we have ετ  ≥  1−σ ⁣(2d τ)P  ≥  0.97\varepsilon_\tau \;\ge\; 1-\sigma\!\left(\frac{2}{\sqrt{d}\,\tau}\right)^{P} \;\ge\; 0.97 for d=128d=128, P∈{8,10}P \in \{8, 10\}, τ∈[0.3,0.7]\tau \in [0.3, 0.7]. 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 WqWq (Cauchy--Schwarz), which does not match Algorithm 1 (rows ∼N(0,1)\sim \mathcal{N}(0, 1), ∣(Wq)i∣≈0.8 ∥q∥|(Wq)_i| \approx 0.8\,\lVert q \rVert), 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 (P,L,τ)(P, L, \tau) 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 ετ≥0.97\varepsilon_\tau \ge 0.97? Can you measure recall against oracle top-k for the deployed procedure, and report the empirical distribution of ∣(Wq)i∣|(Wq)_i| to check the linearization in Lemma 4? How are Corr and Var defined in Table 3?

2 comments

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\epsilon_t is close to 1, not approaching 0.

Therefore, I keep my original rating of 2.

AuthorsOpenReview ↗

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 O~\widetilde{\mathcal O} 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 LL, MM, and τ\tau. 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 ετ(q)\varepsilon_\tau(q). In the setting of [3], the mean-squared error has a sampling contribution of order N−1N^{-1} for NN simulated paths and a squared discretization bias of order h2h^2 for step size hh. At fixed hh, simulating more paths reduces the sampling variance while the discretization bias persists. In SOCKET, at fixed τ\tau, increasing LL improves the approximation of the population soft-score output at rate L−1/2L^{-1/2}, and increasing MM improves the sampling approximation of the finite-table output at rate M−1/2M^{-1/2}. Under the conditions of Theorem 3, these rates hold even when ετ(q)≥0.97\varepsilon_\tau(q)\ge 0.97.

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.

Reviewer_LsoUOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes SOCKET, a training-free sparse attention method based on soft locality-sensitive hashing. By replacing binary hash collisions with probabilistic bucket assignments, SOCKET estimates continuous relevance scores for efficient key selection. Combined with value-aware top-k selection and optimized CUDA/Triton kernels, the method achieves competitive performance on LongBench and RULER across multiple language models, with up to 1.5× decoding throughput compared with FlashAttention.

Critical strengths
  1. SOCKET extends traditional LSH by introducing soft collision scores for more stable token ranking. The method is intuitive, requires no model retraining or data-dependent calibration, and provides an interesting approach to efficient sparse attention.

  2. The evaluation covers multiple language models, sparsity levels, and representative baselines. SOCKET achieves competitive accuracy, particularly under aggressive sparsification. The ranking-quality analysis, memory comparisons, and optimized CUDA/Triton implementation further support its effectiveness.

Critical weaknesses
  1. Theorem 3 analyzes a sampling-based estimator for angular attention, while the actual implementation uses deterministic value-aware top-k selection followed by standard softmax. These involve different approximation mechanisms, and the theoretical error bound does not directly characterize the output error of the deployed method. The authors should clarify the practical implications and limitations of the theoretical analysis.

  2. The practical algorithm ranks tokens using soft collision scores weighted by value norms, whereas much of the theoretical analysis focuses on the soft LSH scoring mechanism. It would be useful to distinguish the benefits of soft collision estimation from those of value-norm weighting and examine their respective effects on ranking accuracy and downstream performance.

  3. The reported throughput gains are measured primarily in decode-only settings, with the largest improvements appearing at longer contexts. Although the method reduces KV access, the practical benefits depend on hash construction, scoring, selection, and sparse attention overhead. A more complete latency breakdown and evaluation under realistic generation workloads would strengthen the efficiency claims.

Questions for authors
  1. How do the theoretical guarantees for the sampling-based angular attention estimator relate to the deterministic top-k selection used in SOCKET? Can the authors clarify which guarantees, if any, apply to the actual implementation?

  2. How much of the improvement comes from soft collision scoring versus value-norm weighting? Could the authors clarify their individual contributions under matched sparsity and memory budgets?

  3. Does the reported decoding throughput include all scoring, selection, and sparse attention operations? How does the overall speedup change when prefill and hash construction are included, particularly at moderate context lengths?

Reviewer_4ui3OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

SOCKET improves LSH-based token retrieval for sparse attention by replacing hard query–bucket matches with soft collision probabilities. It aggregates these probabilities to rank cached tokens, selects top-k candidates, and computes attention over their original KV states. Experiments show competitive quality and up to approximately 1.5× decode-only throughput improvement over FlashAttention3.

Critical strengths
  1. Intuitive, training-free improvement over conventional LSH.
  2. Soft collision scores preserve more information for ranking than binary matches.
  3. Competitive results across multiple models, benchmarks, and sparsity levels.
  4. Custom kernel design targets the practical overhead of scoring and selection.
Critical weaknesses
  1. Additional memory overhead. Hash representations add approximately 15% storage beyond the original KV cache, potentially reducing supported concurrency and offsetting throughput gains.
  2. Limited serving evaluation. Batch size is not explicitly reported, and throughput is not evaluated across batch sizes or near maximum concurrency.
  3. Missing compact-retrieval comparisons. Spotlight Attention and BinaryPC appear relevant, particularly given their smaller reported representations and BinaryPC’s training-free design.
  4. Incomplete performance transparency. The paper lacks a latency breakdown, and the optimized CUDA/Triton kernels used for throughput measurements could not be found in the linked public repository.
  5. Unclear practical advantage. Quality comparisons include sparse baselines, but the main throughput comparison is against dense FlashAttention3.
Questions for authors
  1. What batch size was used for the throughput results?
  2. How does throughput vary across batch sizes and context lengths, particularly near each method’s maximum supported concurrency?
  3. How much does the additional index memory reduce concurrency, and what is the resulting aggregate serving throughput?
  4. How does SOCKET compare with Spotlight Attention and BinaryPC in representation size, retrieval quality, and computational cost? A conceptual comparison would be useful within the rebuttal period.
  5. Can the authors release the optimized kernels and report separate timings for query projection, soft-bucket computation, scoring, top-k selection, selected-KV access, and sparse attention?
  6. How does decoding speed compare with other sparse methods at comparable quality?
1 comment
AuthorsOpenReview ↗

Gentle Reminder

Dear Reviewer 4ui3,

Thank you for your thoughtful review. With the discussion period ending shortly on Nov 18 (AoE), we would deeply appreciate it if you could take a look at our rebuttal and follow-up comments.

Please let us know if you have any remaining concerns. Thank you for your time and consideration!

Sincerely,

The Authors

Comments on the paper

1 comment
AuthorsOpenReview ↗

Genereal Response (Summary of Contributions and Rebuttal Phase Discussion)

We thank all the reviewers for their constructive feedback and thoughtful questions. Below, we provide a concise summary highlighting the key strengths highlighted by the reviewers, the concerns addressed and clarifications provided during the rebuttal period, and emphasizing the novelty of our work.

Strengths

1. [4ui3, LsoU, Sepn]: highlighted SOCKET's intuitive and training-free formulation, emphasizing its use of soft collision probabilities to improve token ranking over conventional hard LSH without requiring model retraining or data-dependent indexing.

2. [4ui3, LsoU]: appreciated the comprehensive empirical evaluation across multiple language models, benchmarks, sparsity levels, and representative baselines, demonstrating competitive accuracy even under aggressive sparsification.

3. [4ui3, LsoU, Sepn]: acknowledged the practical significance of SOCKET's optimized CUDA/Triton kernel implementation, demonstrating decoding throughput improvements over FlashAttention3 at long context lengths.

4. [LsoU]: appreciated the additional ranking-quality analysis and memory comparisons, which further support SOCKET's empirical effectiveness.

5. [LsoU]: praised the clarity and presentation of the manuscript, describing it as clear and easy to follow.

Concerns Addressed

1. [Sepn, LsoU]: requested additional long-context accuracy evaluations to establish SOCKET's effectiveness in the regime where decoding speedups emerge. In response, we provided RULER-HARD evaluations at 64K and 128K under 20$\times$ and 50$\times$ sparsity, along with additional experiments at 33$\times$ sparsity on Llama-3.1-8B and Qwen3.5-9B. These results demonstrate that accuracy degradation is model-dependent, with SOCKET achieving near-dense accuracy on Qwen3.5-9B at both 64K and 128K.

2. [4ui3, Sepn, LsoU]: requested comprehensive runtime evaluations, comparisons against sparse baselines, and clarification of memory overhead and serving concurrency. In response, we provided matched-hardware comparisons against MagicPIG, demonstrating improvements in both TTFT and decoding throughput. We further evaluated throughput across batch sizes, quantified the impact of additional index memory on maximum concurrency, and provided a detailed kernel-level latency breakdown. Importantly, SOCKET achieves 14-28% higher aggregate serving throughput than FlashAttention3 at 32K-128K, despite its additional memory overhead.

3. [Sepn, LsoU]: requested clarification of hyperparameter selection, fixed-configuration evaluations, statistical variability, and the individual contributions of soft collision scoring and value-norm weighting. We clarified our minimal calibration procedure using 5-10 independent examples per task, corrected the calibration-free claim in the revised version, and provided fixed-configuration evaluations and additional seed-level error bars. We also conducted controlled ablations under matched budgets, demonstrating that soft collision scoring consistently matches or outperforms hard LSH, while value-norm weighting provides complementary, task-dependent benefits.

4. [4ui3, Sepn]: requested clarifications regarding retrieval metadata overhead, fair comparisons with hard LSH, and related methods such as Spotlight Attention and BinaryPC. In response, we implemented bit-packing for both SOCKET and hard LSH, demonstrating comparable memory footprints while preserving SOCKET's retrieval-quality advantages. We further clarified SOCKET's positioning relative to learned and data-dependent hashing approaches, emphasizing its training-free, data-independent formulation and rigorous evaluation protocol that explicitly highlights the accuracy-memory trade-offs.

5. [Sepn, LsoU]: requested clarification of the theoretical connection between SOCKET's sampling-based estimator and deployed deterministic top-kk selection, the practical interpretation of Theorem 3, and the assumptions underlying Lemma 4. In response, we clarified that Theorem 3 decomposes the approximation error of the underlying soft-collision estimator into LL, MM, τ\tau, and emphasized that its primary contribution lies in characterizing the convergence rates and approximation-computation trade-offs. We further strengthened Lemma 4 with an exact proof eliminating the small-signal approximation, clarified oracle top-kk recall measurements, and precisely defined the correlation and variance metrics.

Novelty of Our Work

SOCKET advances conventional hard LSH by introducing soft collision scoring, transforming binary collision signals into a more informative and efficient token-ranking mechanism for sparse attention. Importantly, SOCKET narrows the accuracy and memory-efficiency gap between data-agnostic and data-dependent retrieval methods while preserving the advantages of a training-free, data-independent formulation that avoids model-specific training and costly preprocessing.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.