Abstract
The computational cost of standard self-attention grows quadratically with sequence length, posing a significant bottleneck for long-context processing in Large Language Models (LLMs). We present All-or-Here Attention (AHA), a novel binary routing mechanism that dynamically selects between full global attention and local sliding window attention. Our findings indicate that for a window size of 256 tokens, over 93% of global attention operations are redundant. AHA maintains or even slightly improves model performance while drastically reducing the necessity for global context retrieval, offering a path toward more efficient long-document processing.
Introduction
Modern LLMs rely on self-attention to capture dependencies across sequences. However, the quadratic complexity of this mechanism limits scalability. While various "efficient attention" techniques attempt to compress or approximate the attention matrix, we argue that the primary issue is inherent redundancy. Most tokens primarily require local context for grammatical and semantic coherence, with only a small subset needing long-range retrieval to resolve complex dependencies. AHA addresses this by teaching models to distinguish between these needs on a per-token basis, using a dynamic "on-demand" retrieval strategy.
The All-or-Here Attention (AHA) Framework
AHA introduces a lightweight "router" into each attention head to facilitate conditional computation, allowing the model to decide whether a token requires a global view or just a local one.
Binary Routing and Training
For every token, the router generates an importance score. If this score exceeds a predefined threshold, the head executes Full Causal Attention ("All"). Otherwise, it defaults to Sliding Window Attention ("Here"), focusing only on the $w$ most recent tokens.
To handle the non-differentiable nature of this binary decision, the authors employ a Straight-Through Estimator (STE) during training. This allows gradients to propagate through the discrete gate, enabling the router to learn optimal switching behavior. Furthermore, an L1 sparsity regularization penalty is applied to the router scores, incentivizing the model to prefer the "cheaper" local attention unless global context is truly essential for the task.
Experimental Results and Key Insights
The researchers evaluated AHA using the OLMo-2-1B-SFT base model, fine-tuned on the Tulu-v3 dataset. Performance was measured across a diverse battery of standard benchmarks, including MMLU (general knowledge), HellaSwag (reasoning), GSM8K (math), and MultiNews (summarization).
High Sparsity with Performance Parity
With a local window size of 256, AHA bypassed 93.3% of full attention operations. Remarkably, the model retained 102.5% of the vanilla model's average performance, suggesting that the sparsity regularization might even act as a beneficial inductive bias that filters out irrelevant long-range noise.
The Long-Tail of Context Dependency
As shown in the attention usage distribution across tasks, context dependency follows a "long-tail" pattern. The demand for global access drops significantly as the local window size increases. For instance, increasing the window from 128 to 256 tokens reduced global attention demand from 11.6% to just 6.7%. This confirms that for the vast majority of tokens, a relatively small local window is sufficient.
Head Specialization
AHA leads to a clear "division of labor" among attention heads. The model learns to specialize: some heads become "always-on" global retrievers, while others operate almost exclusively in local mode, triggering global look-backs only for specific, high-importance tokens. This specialization allows the model to maintain a safety net of global context without the full computational cost.
Conclusion and Future Directions
AHA demonstrates that global attention is largely a safety net that can be replaced by on-demand retrieval. While this algorithmic sparsity is significant, future work must focus on developing hardware-aware kernels (such as specialized FlashAttention variants) to translate these gains into actual wall-clock speedups on GPUs. Additionally, exploring multi-choice routers that can select from multiple window sizes could further optimize the efficiency-performance trade-off for the next generation of large-scale models.
Summary updated