- Rating
- 3
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This paper proposes CSAttention, a training-free sparse attention method for reusable-prefix long-context LLM serving. It precomputes query-centroid-to-key score tables during prefix construction, enabling efficient KV selection through centroid routing and score aggregation during decoding. Experiments on LongBench, LongBench-v2, and RULER demonstrate near-full-attention accuracy at 95% sparsity and substantial decoding speedups. The paper also provides comprehensive evaluations of retrieval quality, end-to-end latency, memory overhead, prefix reuse, and batch scaling.
Critical strengths
1. Effective sparse attention design. CSAttention effectively exploits reusable prefixes by precomputing query-centroid-to-key scores, reducing online KV retrieval overhead. Its subspace centroid routing and score aggregation achieve strong retrieval quality while preserving exact attention over selected KV entries.
2. Comprehensive experimental evaluation. The paper evaluates multiple models and benchmarks, demonstrating near-full-attention accuracy at high sparsity and substantial decoding speedups. The detailed analysis of TTFT, end-to-end latency, memory overhead, prefix reuse, and batch scaling further strengthens its practical relevance.
Critical weaknesses
1. Limited evaluation on short-input, long-output workloads. The current experiments primarily focus on long-input scenarios, including the CoT evaluations on LongBench-v2. Although the paper includes long-generation stress tests, these do not fully characterize the method's effectiveness on short-input, long-output tasks such as AIME and MATH-500. Since CSAttention relies on query centroids constructed from prefill queries, it is unclear whether these centroids can adequately represent decoding queries when the generated sequence becomes substantially longer than the input context.
2. The main method illustration could be improved. While the overall methodology is understandable from the text, Figure 2 is relatively dense and does not clearly highlight the key operations and data flow.
Questions for authors
1. Generalization to short-input, long-output tasks. How does CSAttention perform on reasoning tasks such as AIME and MATH-500?
2 comments
Thank you for the additional experiments and clarifications. The new evaluations on MATH-500 and long-context reasoning help address my concern regarding short-input, long-output workloads and the effectiveness of the fixed prefill codebook during extended generation. I will maintain my original rating.
Thank you for raising the question about how prefill queries represent later reasoning steps. We evaluated both short-prompt mathematical reasoning and long-context question answering, which exercise different parts of the method.
1. Short-input, long-output reasoning
We evaluated Qwen3-8B on a fixed 50-question subset of MATH-500, using H100 and a 4,096-token generation cap:
The budget follows the input-prefix length:
K_{\mathrm{recent}}=\min(32,K),\qquad K_{\mathrm{retrieval}}=K-K_{\mathrm{recent}}.$$ $K$ remains fixed throughout generation, and the recent window is included within this budget. These prompts contain 39–203 tokens, giving $K=2$–$11$. Consequently, all available slots are assigned to recent tokens: prefill uses full causal attention, and decoding uses the most recent $K$ KV positions while retaining the historical cache. Even with this small active-KV budget, the model answers 36/50 questions correctly, compared with 35/50 for Full, with a median output exceeding 3,000 tokens. This shows that the budget rule handles the very-short-prefix boundary through its recent-window branch while preserving comparable reasoning accuracy on this subset. ### 2. Long-context reasoning with a fixed prefill codebook We also evaluated a fixed set of 16 questions from the **Long subset of LongBench-v2**, using Qwen3-32B with chain-of-thought generation. This is long-context question answering: the input contains the source documents and the question. Following the original long-generation setup, the document portion is truncated to give a total input of **98,304 tokens (96K)**. The purpose of the 96K context is to test the setting CSAttention is designed for: a substantial prefix supplies the prefill queries used to build a reusable scoring codebook, and subsequent reasoning repeatedly accesses that context. We keep this input and codebook fixed while extending generation, so the experiment tests whether the same precomputed representation remains useful as reasoning continues. Both methods use A100 TP2, BF16 and greedy decoding; CS uses a 32-token recent window. We use the same 16 questions and generation trajectories at every cap and re-extract the answers at each point. | LongBench-v2 Long, 16 questions, 96K input | Full accuracy | CS accuracy | |---|---:|---:| | 2,048-token generation cap | 37.50% | 37.50% | | 4,096-token generation cap | 37.50% | 37.50% | | 8,192-token generation cap | 37.50% | 43.75% | | 16,384-token generation cap | 31.25% | 37.50% | Accuracy is computed over all 16 questions at every cap. Six pairs remain active in the final 16K diagnostic window. The result supports our central claim about long-context decoding: **the fixed prefill codebook continues to support Full-comparable task quality as generation extends to a 16K cap.** Query-centroid cosine decreases from 0.8845 to 0.7912, yet the relative accuracy gap does not deteriorate. Between 8K and 16K, both Full and CS lose one correct answer, leaving the gap unchanged. This matters for the design of CSAttention. The cached scoring representation remains useful despite the gradual movement of decoding queries, allowing us to reuse the prefill computation without reclustering the query codebook during generation. Together with the short-prompt result, this gives a clearer picture of how the recent-window branch and centroid-based retrieval serve their respective input regimes. ### 3. Figure 2 The intended flow has three stages: 1. **Prefix construction:** cluster prefill queries in subspaces, compute centroid-to-key signed scores, and store bounded Top-$L$ lists of original key IDs and scores alongside the original KV. 2. **Decoding:** route the current query to one centroid per subspace, read the corresponding lists and aggregate scores by key ID. Reserve recent-history slots within the Top-$K$ budget, fill the remaining slots by the aggregated ranking, and compute attention on the selected original KV. 3. **Suffix maintenance:** score each newly generated key against the fixed centroids and insert eligible entries into bounded request-local lists. The shared prefix snapshot remains unchanged. Centroids guide token selection; attention still uses the original KV. We will label these stages, the connecting arrows, and the shared versus request-local states more clearly in Figure 2 so that this distinction and the complete data flow are immediately visible.