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

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 $4.7\times$ end-to-end attention speedup over FlashAttention-2.

Modern AI assistants spend most of their time on a single operation called attention, in which the model decides which earlier words in the input matter for the next word. As the input grows longer — say, an entire book or a long meeting transcript — this step becomes the main bottleneck, slowing responses and consuming large amounts of energy. Existing speed-ups skip parts of the attention computation, but they each look at only one layer of the model at a time and often miss connections that emerge across several layers, hurting accuracy. We developed Sketch&Walk, a method that makes attention faster without retraining the model: it first builds a quick, compressed sketch of who-attends-to-whom, then takes a short "walk" across the model's layers to surface indirect connections, the way mutual friends reveal that two people are linked even when they've never met, so the model only computes the most relevant ones. In our experiments, Sketch&Walk runs attention up to 4.7× faster than other implementation while preserving accuracy on long-document benchmarks, making long-context AI assistants meaningfully cheaper to deploy and more responsive to use.