Temporal Working Sets for Sparse Attention

Sparse attention algorithms output the attention support over a small subset of input tokens, but finding this subset can require full cache search at each step in the decoder. We prove that this search has further structure not captured by the sparsity of attention support compared to previous attention supports. Larger working sets in two pretrained models are useful for finding subsequent attention sets. Query permutation against fixed memory reduces working set lifetimes from 22.9 and 19.7 to 4.3 and 3.9 steps for the Llama-3.1-8B and Qwen3-8B models respectively, without affecting each query's answer. Recurrent Attention Routing (RAR) maintains working sets and updates bounds from previous page visits instead of learning these bounds. Each query ranks the best set of current candidates and the best scores for new keys, and expands attention search to pages that may change its top-$k$. We prove that this algorithm exhaustively selects all relevant tokens, derive sufficient conditions to reuse working sets by margins in query ranks and query displacements, and show a RAR speedup in routing with 128K context of $3.9\times$ and $3.6\times$, and a $1.4\times$ decoding speedup for both models. All 65,069,056 selected head routes coincide with exhaustive selection. Temporal working sets lower the cost of computing each new attention support without training.