mlsanityData to 7 Oct 2026

Scout Before You Attend: Sketch-and-Walk Sparse Attention for Efficient LLM Inference

arXiv 2602.07397 ↗First posted 7 Feb 2026cs.LG cs.AIcited by 4

On the map: Efficient LLM inference and serving → KV cache optimization

Abstract (arXiv)

Self-attention dominates the computational and memory cost of long-context LLM inference across both prefill and decode phases. To address this challenge, we introduce Sketch&Walk Attention, a training-free sparse attention method that determines sparsity with lightweight sketches and deterministic walk. Sketch&Walk applies Hadamard sketching to get inexpensive approximations of attention scores, then aggregates these estimates across layers via a walk mechanism that captures attention influence beyond direct interactions between tokens. The accumulated walk scores are used to select top-k attention blocks, enabling dynamic sparsity with a single training-free algorithm that applies uniformly to both the prefill and decode phases, together with custom sparse attention kernels. Across a wide range of models and tasks, Sketch&Walk maintains near-lossless accuracy at 20% attention density and can slightly outperform dense attention in some settings, while achieving up to 6x inference speedup.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Placed in KV cache optimization, one of 12 directions in Efficient LLM inference and serving. Builds on 35 of its 51 references that are in the map. First posted on arXiv 7 Feb 2026.

Builds on

35 of 51 references.

Closest ancestors · 4

Same direction, newest first

  1. 2024KV Cache Compression, But What Must We Give in Return? A Comprehensive Benchmark of Long Context Capable Approaches1 Jul
  2. 2024Quest: Query-Aware Sparsity for Efficient Long-Context LLM Inference16 Jun
  3. 2024PyramidKV: Dynamic KV Cache Compression based on Pyramidal Information Funneling4 Jun
  4. 2023H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models24 Jun

Other references · 31

  1. 2017Attention Is All You Needcited by 59,932
  2. 2023Mamba: Linear-Time Sequence Modeling with Selective State Spacescited by 4,616
  3. 2022FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awarenesscited by 3,611
  4. 2023Efficient Streaming Language Models with Attention Sinkscited by 2,115
  5. 2020Big Bird: Transformers for Longer Sequencescited by 1,673
  6. 2019Generating Long Sequences with Sparse Transformerscited by 1,523
  7. 2023LongBench: A Bilingual, Multitask Benchmark for Long Context Understandingcited by 1,378
  8. 2024RULER: What's the Real Context Size of Your Long-Context Language Models?cited by 1,270
  9. 2020Quantifying Attention Flow in Transformerscited by 759
  10. 2025DeepSeek-V3.2: Pushing the Frontier of Open Large Language Modelscited by 755
  11. 2022Efficiently Scaling Transformer Inferencecited by 529
  12. 2025Native Sparse Attention: Hardware-Aligned and Natively Trainable Sparse Attentioncited by 391
19 more
  1. 2024MInference 1.0: Accelerating Pre-filling for Long-Context LLMs via Dynamic Sparse Attentioncited by 375
  2. 2025Gated Attention for Large Language Models: Non-linearity, Sparsity, and Attention-Sink-Freecited by 266
  3. 2024InfLLM: Training-Free Long-Context Extrapolation for LLMs with an Efficient Context Memorycited by 192
  4. 2024SeerAttention: Learning Intrinsic Sparse Attention in Your LLMscited by 121
  5. 2025FlexPrefill: A Context-Aware Sparse Attention Mechanism for Efficient Long-Sequence Inferencecited by 121
  6. 2024Transformers are Multi-State RNNscited by 120
  7. 2015Practical and Optimal LSH for Angular Distancecited by 105
  8. 2024Challenges in Deploying Long-Context Transformers: A Theoretical Peak Performance Analysiscited by 44
  9. 2015Optimal Data-Dependent Hashing for Approximate Near Neighborscited by 43
  10. 2013Beyond Locality-Sensitive Hashingcited by 23
  11. 2021Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structurescited by 19
  12. 2016Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighborscited by 18
  13. 2023OPORP: One Permutation + One Random Projectioncited by 11
  14. 2020Scaling up Kernel Ridge Regression via Locality Sensitive Hashingcited by 8
  15. 2018Navigating with Graph Representations for Fast and Scalable Decoding of Neural Language Modelscited by 7
  16. 2021Quantization Algorithms for Random Fourier Featurescited by 7
  17. 2025ALinFiK: Learning to Approximate Linearized Future Influence Kernel for Scalable Third-Party LLM Data Valuationcited by 6
  18. 2025Adamas: Hadamard Sparse Attention for Efficient Long-Context Inferencecited by 4
  19. 2023Empowering Distributed Training with Sparsity-driven Data Synchronizationcited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 4.

4 papers.

  1. 2026LoKA: Low-precision Kernel Applications for Recommendation Models At Scalecited by 1
  2. 2026Forget Without Compromise: Nexus Sampling for Streaming KV-Cache Eviction Under Fixed Budgetscited by 1
  3. 2026Flux Attention: Context-Aware Hybrid Attention for Efficient LLMs Inferencecited by 0
  4. 2026Self-Indexing Attention for Compression-Compatible Sparse Long-Context LLM Inferencecited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Kascade: A Practical Sparse Attention Method for Long-Context LLM Inference
  2. 2025Tactic: Adaptive Sparse Attention with Clustering and Distribution Fitting for Long-Context LLMs
  3. 2026SparDA: Sparse Decoupled Attention for Efficient Long-Context LLM Inference
  4. 2026Sparse Attention as a Range Searching Problem: Towards an Inference-Efficient Index for KV Cache
  5. 2026You Only Index Once: Cross-Layer Sparse Attention with Shared Routing
  6. 2025Stream: Scaling up Mechanistic Interpretability to Long Context in LLMs via Sparse Attention
  7. 2026Double-P: Hierarchical Top-P Sparse Attention for Long-Context LLMs
  8. 2025Progressive Sparse Attention: Algorithm and System Co-design for Efficient Attention in LLM Serving