LISA: Linear-Indexed Sparse Attention for Efficient Long-Context Reasoning

Attention is the dominant source of latency during long-context LLM inference, an increasingly popular workload with reasoning models and RAG. We propose Kascade, a training-free sparse attention method that leverages known observations such as 1) post-softmax attention is intrinsically sparse, and 2) the identity of high-weight keys is stable across nearby layers. Kascade computes exact Top-k indices in a small set of anchor layers, then reuses those indices in intermediate reuse layers. The anchor layers are selected algorithmically, via a dynamic-programming objective that maximizes cross-layer similarity over a development set, allowing easy deployment across models. The method incorporates efficient implementation constraints (e.g. tile-level operations), across both prefill and decode attention. The Top-k selection and reuse in Kascade is head-aware and we show in our experiments that this is critical for high accuracy. Kascade achieves up to 4.1x speedup in decode attention and 2.2x speedup in prefill attention over FlashAttention-3 baseline on H100 GPUs while closely matching dense attention accuracy on long-context benchmarks such as LongBench and AIME-24.

Long-context inference in large language models is bottlenecked by the quadratic cost of full attention. Existing efficient alternatives often rely either on native sparse training or on heuristic token eviction, creating an undesirable trade-off among efficiency, training cost, and accuracy. In this work, we show that full-attention LLMs are already intrinsically sparse and can be transformed into highly sparse models with only minimal adaptation. Our approach is built on three observations: (1) only a small subset of attention heads truly requires full long-context processing; (2) long-range retrieval is governed primarily by a low-dimensional subspace, allowing relevant tokens to be retrieved efficiently with a 16-dimensional indexer; and (3) the useful token budget is strongly query-dependent, making dynamic top-$p$ selection more suitable than fixed top-$k$ sparsification. Based on these insights, we propose RTPurbo, which retains the full KV cache only for retrieval heads and introduces a lightweight token indexer for sparse attention. By exploiting the model's intrinsic sparsity, RTPurbo achieves sparsification with only a few hundred training steps. Experiments on long-context benchmarks and reasoning tasks show that RTPurbo preserves near-lossless accuracy while delivering substantial efficiency gains, including up to a 9.36$\times$ prefill speedup at 1M context and about a 2.01$\times$ decode speedup. These results suggest that strong sparse inference can be obtained from standard full-attention training without expensive native sparse pretraining.

Full self-attention in large language models scales as O(N^2), limiting long-context analysis to 65k tokens and requiring costly GPU clusters. The Reduced Interaction Sampling (RIS) inference engine addresses this as a model-agnostic architecture. Without modifying weights, RIS introduces sparse stochastic attention geometries that operate under extreme pruning (up to 99% under 1% density) while preserving factual retrieval. While foundational graph-theoretic RIS formulations establish an asymptotic O(N log N) bound, this work evaluates a practical fixed-density regime on unaccelerated commodity CPU systems. We validate RIS on Qwen2-1.5B-Instruct across two regimes. At 32,768 tokens (where native dense attention serves as the upper bound), RIS-Stochastic at 1% density and 70 ensemble seeds achieves 75.00% accuracy, outperforming the native dense baseline (71.88%), while 5% density at 10 seeds matches it (71.88%), demonstrating that multi-seed sparsity filters sequence-level noise. Crucially, a controlled ablation evaluating a single static mask at matched budget (N=1, d=0.50) yields only 53.12% accuracy, proving that multi-seed topological diversity, rather than raw edge density, drives contextual recovery. Under tight budgets, RIS-Structural reaches 65.62% accuracy at 1% density with 10 seeds (recovering 50.0% of the gap over the 59.38% zero-context floor) and 68.75% (75.0% recovery) with 30 seeds. At 65,536 tokens, where dense attention triggers out-of-memory faults, RIS yields retrieval gains of up to 14.06 percentage points over the zero-context floor (51.56%), confirmed as marginally significant under McNemar's paired test (p = 0.078 < 0.10). All evaluations run on commodity CPU servers (16-128 GB RAM), demonstrating that long-context LLM inference is feasible on standard academic hardware without GPU acceleration.