Star Attention: Efficient LLM Inference over Long Sequences

We thank Reviewer dKGV for their detailed and insightful feedback. Below, we respond to the concerns regarding system performance analysis, literature coverage, compatibility, and presentation.

1. System Performance Analysis:

• While we agree that kernel-level profiling and analysis across hardware configurations (e.g., PCIe vs. NVLink interconnects) can provide valuable insights, our primary focus in this work is to introduce and validate the Star Attention algorithm from an algorithmic and end-to-end performance standpoint. We view detailed kernel-level profiling and hardware-specific optimization as an exciting avenue for future work that could further enhance deployment efficiency.
• All experiments were conducted under consistent hardware and software environments for Star Attention and the baselines, ensuring that the reported relative speedups (e.g., up to 11x on Llama-3.1-8B-Instruct for long contexts) fairly capture the algorithmic advantage.
• Notably, Star Attention’s phase 1 avoids inter-host communication entirely, unlike Ring Attention. Even assuming an infinitely fast interconnect, global attention still incurs computation proportional to the total number of tokens per host, while Star Attention reduces this via localized blockwise attention in phase 1.

2. Literature Survey (KV Cache Optimization):

• Thank you for the helpful references [1–3]. We will revise the related work section to include and discuss these references.
• Based on the reviewer's feedback, we conducted new comparisons between Star Attention and other sparse KV cache methods such as StreamingLLM and MInference, on long-context inference tasks. Star Attention outperforms these alternatives in both accuracy and scalability, as shown below:

Table B: Accuracy on RULER (Llama-3.1-8B-Instruct)

We also evaluated Star Attention on the InfiniteBench benchmark. Given its broad coverage across multilingual and programmatic tasks, we include this for further evidence of Star Attention’s generalization:

Table C: Accuracy on Infinite Bench (Llama-3.1-8B-Instruct)

3. Compatibility with Parallelism Methods and Serving Frameworks:

• Model Parallelism [4, 5]: Star Attention is complementary to tensor and pipeline parallelism. These can be applied within each host, while Star Attention governs how input context is distributed across hosts via sequence parallelism. No assumptions are made about the intra-host setup.
• Serving Frameworks [6-7]: Star Attention is compatible with modern LLM serving frameworks. For instance, memory management techniques like PagedAttention [6] can be applied within each host to efficiently handle the local KV cache. Because Star Attention distributes context blocks across hosts and isolates them during Phase 1, such memory-optimized serving layers can operate independently within each node. Similarly, the two-phase structure of Star Attention aligns well with structured execution frameworks like SGLang [7], and can potentially be integrated into such systems without requiring fundamental changes to their scheduling or runtime semantics.

We thank the reviewer dnhh for their feedback and acknowledge their points regarding novelty, motivation, baselines, and benchmarks. We address these points below:

1. Novelty and Relation to Prior Work:

• While Star Attention draws inspiration from prior work like StreamingLLM and attention sinks, it introduces a distinct two-phase distributed inference architecture. Unlike StreamingLLM, which struggles with long-context retention and is not inherently distributed, Star Attention processes the context in parallel without inter-host communication in Phase 1 and leverages global attention only during decoding. This results in both accuracy preservation and significant latency reduction.
• Regarding “tri-shape attention,” we were unable to identify a specific paper with that terminology. If you are referring to a particular method, we would appreciate a citation to better contextualize and compare it in the final version.

2. Motivation for Sparse Prefill vs. Dense Decoding:

• In Phase 1 (sparse prefill), attention is localized, as context tokens generally require only local neighborhood interactions. This allows efficient processing via distributed blockwise attention. In contrast, during query encoding and decoding (Phase 2), the tokens must integrate information from the entire context, necessitating dense attention. This design reflects practical needs in long-context tasks and allows us to optimize for both throughput and accuracy.
• Conversely, during the query processing and response generation phase (decoding phase), the query tokens and subsequent generated tokens often require access to information scattered throughout the entire preceding context to formulate an accurate response. Therefore, employing dense global attention in Phase 2, accessing the full cached KV state from Phase 1, is crucial for preserving the model's understanding and generation capabilities, particularly for tasks requiring synthesis of information from distant parts of the context.

3. Comparison with Sparse Attention Baselines:

• In response to the reviewer’s feedback, we extended our baseline comparisons to include StreamingLLM and MInference. Results are shown in Table A.

Table A: Accuracy on RULER (Llama-3.1-8B-Instruct)

• The results show that Star Attention outperforms all the other sparse KV methods. Furthermore, due to the distributed nature of Star Attention, since there is no inter-block communication during phase 1, the latency on 128K sequence length is equivalent to the latency that the model will have when processing a sequence length of 64K (32K block + 32K anchor), since each host will process each block parallely.
• Unlike methods such as MInference, which may require offline analysis to determine optimal sparsity patterns, Star Attention can be applied directly to most pretrained Transformer models without model-specific tuning or preprocessing.

4. Evaluation on Comprehensive Benchmarks:

• In response to the reviewer’s suggestion, we expanded our evaluation to include InfiniteBench—a more comprehensive benchmark suite for long-context performance. As shown in Table B, Star Attention outperforms other sparse baselines across diverse tasks, demonstrating its robustness beyond synthetic datasets like RULER and BABILong.

Table B: Accuracy on Infinite Bench (Llama-3.1-8B-Instruct)

We thank the reviewer again for raising important points. Their comments led us to incorporate broader baselines and more diverse evaluations, which we believe have significantly strengthened the work. We look forward to incorporating these additions more prominently in the camera-ready version.

We thank the reviewer EMsM for their insightful comments and suggestions. We address each point below:

1. Clarity of Abstract Wording:

Thank you for pointing out the ambiguity in the abstract's final sentence. You are correct that the “up to 11x” improvement specifically refers to inference speed and throughput, not memory. While Star Attention does reduce memory usage (due to sharded attention and localized KV caching), the 11x figure quantifies speedup. We will revise the abstract to explicitly state that the 11x gain pertains to speed/throughput, and mention memory reduction separately, to prevent misinterpretation.

2. Evaluation Benchmarks:

We agree that results on real-world or less synthetic benchmarks are valuable. In response, we have extended our evaluation to include InfiniteBench, a long-context benchmark with diverse and challenging tasks. Additionally, we also added comparisons to some of the other sparse attention methods as well such as StreamingLLM and MInference. The results are summarized in the table below.

Table B: Accuracy on Infinite Bench (Llama-3.1-8B-Instruct)

3. Discussion of Related Work:

Thank you for suggesting the additional relevant references. We will amend the related work section in the revised manuscript to include a more detailed discussion and comparison with related methods.

4. Impact of Block Size and Number of Blocks (Q1):

• Figure 5 illustrates accuracy as a function of block size, holding the total sequence length fixed. We observe that larger blocks result in better approximation to global attention and higher accuracy.
• Figure 6 and Table 5 (Appendix C.1) explore scaling behavior with fixed block size (e.g., 32K) while increasing sequence length up to 1M tokens. We find that Star Attention retains upto 90% of full attention accuracy even at 1M tokens, with up to 17x speedup.

This suggests a graceful degradation, not a sharp drop-off. The method remains robust up to at least 1M tokens, especially with larger blocks.

5. Size of Anchor Block relative to the Block Size:

Since Phase 1 uses causal attention (as in decoder-only LLMs), anchor blocks cannot extend beyond the preceding context block without violating causality. Setting the anchor size equal to the context block size ensures maximal usable context per block while preserving autoregressive constraints, effectively bringing Star Attention’s receptive field closer to that of full attention.

We appreciate the reviewer x5MA's constructive feedback. Below, we address the identified weaknesses regarding anchor blocks, performance on complex tasks, and block size dependency:

1. Role and Configuration of Anchor Blocks:

• Anchor Block Size: The performance peak when the anchor block size equals the context block size can be attributed to Star Attention’s design constraints. Since Phase 1 uses causal attention (as in decoder-only LLMs), anchor blocks cannot extend beyond the preceding context block without violating causality. Setting the anchor size equal to the context block size represents the maximum usable context while respecting this constraint — effectively bringing Star Attention closer to full attention in terms of receptive field.
• Anchor Block Content and Position: As shown in Section 4.1, using the first context block (c1) as the anchor yields optimal performance. The rationale is that Phase 2 performs global attention; therefore, Phase 1 context blocks should attend to anchor tokens representative of the initial sequence context that the full model would observe in a global attention scenario. Our analysis in Section 4.1 further indicates that if the anchor block content is fixed to c1, variations in the position IDs assigned to these anchor tokens during local attention computation have a minimal impact on overall performance.

2. Performance on Complex Tasks:

• Star Attention, like other sparse attention mechanisms, trades off some accuracy for substantial inference speedups. Across a range of tasks — including question answering (Figure 7) — it retains 95–100% of dense attention performance while delivering substantial inference speedups.
• For tasks requiring complex reasoning and inter-block context (e.g., Multi-Hop Tracing), we acknowledge that the absence of direct cross-block attention in Phase 1 introduces challenges. Despite this, Star Attention maintains up to 93% of the dense attention accuracy on these tasks (Figure 7).
• To assess generalization on more complex, real-world tasks, we evaluated Star Attention on InfiniteBench, a diverse benchmark covering multilingual QA, retrieval, math, code debugging, summarization and more. As shown in Table B, Star Attention matches or closely tracks full attention across all categories and outperforms prior sparse inference baselines by a significant margin.

Table B: Accuracy on Infinite Bench (Llama-3.1-8B-Instruct)

• Improving the performance on tasks requiring deeper inter-block reasoning in the early encoding stages remains an important direction for future work.

3. Dependency on Block Size and Flexibility:

• The dependency on block size reflects a common trade-off in blockwise attention: smaller blocks enable faster inference but may limit context aggregation, especially in longer sequences. Our experiments (Figure 5) show that setting the block size to ~1/4 of the total sequence length achieves a strong balance of accuracy and speed. However, the block size depends on the user and they can choose smaller block sizes to prioritize higher inference speeds, accepting slightly more accuracy degradation.
• For variable-length or real-time inputs, users can set the block size based on the maximum expected sequence length or system constraints. As shown in Figure 6 and Table 5, even with smaller blocks (1/8, 1/16, 1/32 of the sequence), Star Attention retains up to 90% of dense attention performance while delivering up to 17× speedups — allowing users to flexibly tune accuracy vs. latency based on application needs.