Star Attention: Efficient LLM Inference over Long Sequences

Analysis

Why This Paper Matters

Star Attention addresses a critical bottleneck in deploying large language models (LLMs) for long-context tasks: the quadratic cost of self-attention. As models like GPT-4 and Llama 2 are increasingly used for processing entire books, legal documents, or long conversation histories, inference latency and memory become prohibitive. Existing sparse attention methods often require retraining or degrade accuracy, while full attention is impractical for sequences exceeding tens of thousands of tokens. Star Attention provides a drop-in approximation that works with pre-trained models, making it immediately applicable to production systems.

The paper's two-phase design is particularly clever: it exploits the observation that during context processing, tokens can be attended locally without global communication, saving bandwidth. Only during the generation phase do queries need global attention. This asymmetry mirrors the typical usage pattern of LLMs (long context, short generation) and minimizes overhead. The result is a method that scales linearly with the number of hosts, enabling inference on sequences that would otherwise exceed single-device memory.

Technical Contributions

• Two-phase block-sparse attention: Phase 1 processes context with blockwise-local attention across hosts in parallel, avoiding inter-host communication. Phase 2 uses sequence-global attention for query and response tokens, ensuring no loss of long-range context.
• Minimal communication overhead: Only cached key-value pairs from the context phase are shared during generation, not intermediate activations, reducing bandwidth requirements.
• Seamless integration: The method requires no model retraining or architectural changes; it can be applied to any Transformer-based LLM trained with global attention by simply modifying the attention mask during inference.
• Scalable sharding: Attention is sharded across hosts by splitting the sequence into blocks, with each host responsible for a contiguous segment. This enables linear scaling of memory and compute with the number of hosts.

Results

The paper reports up to 11x reduction in memory and inference time on long sequences (e.g., 128K tokens) compared to full attention baselines. Accuracy is preserved within 97-100% on standard benchmarks such as LongBench and RULER, with the highest degradation observed on tasks requiring exact token recall (e.g., needle-in-a-haystack). The method is evaluated on models from the Llama 2 and Mistral families, showing consistent performance across different architectures and sizes.

Significance

Star Attention represents a practical advance for deploying LLMs in long-context applications. By enabling efficient inference without retraining, it lowers the barrier for using large models on tasks like document analysis, codebase understanding, and long-form question answering. The approach is complementary to other efficiency techniques like quantization and speculative decoding, and could be combined for further gains. However, the paper does not explore the impact on tasks requiring fine-grained attention over distant tokens, such as mathematical reasoning or multi-hop QA, where accuracy might degrade more. Future work could investigate adaptive block sizes or hybrid approaches to address these edge cases. Overall, Star Attention is a valuable contribution to the growing toolkit for practical LLM inference.