acceptodds
Under review as a conference paper at ICLR 2027

CSAttention: Centroid-Scoring Sparse Attention for Reusable-Prefix Long-Context LLM Serving

Abstract

Long-context LLM serving increasingly relies on long, reusable prefixes, such as cached retrieval contexts, tool schemas, agent memory, and domain-specific system prompts. In this write-once, read-many regime, dense attention over the accumulated KV cache becomes a dominant decode-time bottleneck, while aggressive sparse attention often loses accuracy because online queries and cached keys follow different distributions. We propose CSAttention, a training-free sparse attention method designed for reusable-prefix long-context inference. CSAttention shifts expensive retrieval work from online decoding to an offline prefix-build stage: it clusters prefill queries in subspaces, precomputes centroid-to-key partial scores, and stores bounded Top- lookup tables for each query centroid. At decode time, each new query selects its nearest query centroids, fetches the corresponding shortlists, aggregates centroid scores by key index, and performs attention only over the selected KV entries. This formulation does not remove the linear memory growth of long-context KV cache; instead, it creates a decode-stationary auxiliary index whose capacity is fixed after a reusable prefix is built and whose online work is regular and bounded by the shortlist budget. Extensive experiments on LongBench and LongBench-v2 show that CSAttention preserves near-full-attention accuracy at 95% sparsity across Llama, Qwen, and Mistral backbones. Compared with strong sparse-attention baselines, CSAttention achieves higher recall and downstream accuracy under matched sparse budgets, and delivers up to decode-throughput speedup and up to end-to-end speedup in long-prefix, moderate-to-long generation regimes, while making its TTFT, memory, and batch-scaling trade-offs explicit.

Primary area:
infrastructure, software libraries, hardware, systems, etc.
Keywords:
Sparse Attention, Long-Context LLM Inference, Decode Acceleration, Training-Free Inference

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_c7n8OpenReview ↗
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 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:

MATH-500, 50 questionsFullCS budget rule
Correct answers35/5036/50
Accuracy70.0%72.0%
Median generated tokens3,732.53,196.0

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.

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.

Reviewer_9L5MOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes CSAttention, a training-free sparse attention method for long-context serving with reusable prefixes. It clusters prefill queries into subspace centroids and precomputes centroid-to-key score tables. During decoding, queries retrieve and aggregate these scores to select a small subset of original KV entries for attention. Experiments report near-full-attention quality at 5% active KV, with up to 4.24× decode throughput and 3.80× end-to-end speedup, at the cost of additional index memory and construction time.

Critical strengths
  • CSAttention presents a clear, training-free approach that moves retrieval work into reusable prefix construction, enabling efficient decoding through precomputed query-centroid score tables.
  • Experiments show near-full-attention quality at 5% active KV across multiple backbones, supported by a controlled query-centric versus key-centric comparison.
  • The evaluation reports both decode and end-to-end speedups while explicitly accounting for index memory, construction overhead, and prefix-reuse break-even points.
Critical weaknesses

Q1. Broader evaluation. Could the authors evaluate CSAttention on agentic tasks, such as coding or terminal benchmarks, beyond static long-context benchmarks?

Q2. Long-generation robustness. Table 14 suggests increasing query-centroid drift and quality degradation up to 8K generated tokens. Does this trend continue at 16K or 32K, and how could it be mitigated?

Q3. RetrievalAttention comparison. Could the authors extend the comparison with RetrievalAttention beyond quality to include latency, memory usage, and index construction cost?

Questions for authors

see weaknesses.

3 comments

Thank you for the suggestions. We have extended the long-generation experiment and summarize the relevant quality and serving results below.

1. Coding workloads and the cost of prefix construction

CSAttention can share repository content, documentation and tool instructions as fixed prefixes, while keeping generated tokens and table updates local to each continuation.

For coding quality, the paper evaluates LongBench LCC code completion, comparing Full with CS at 5% active prefix KV:

ModelFullCS
Qwen3-8B69.1368.89
Llama-3.1-8B-Instruct64.8963.33
Mistral-7B-Instruct-v0.364.3263.98

CS preserves most of Full's completion quality across three backbones at this small budget.

The 128K-prefix serving experiment below tests when construction pays off by varying output length and prefix reuse. TTFT includes construction; E2E includes construction, prefill and decoding.

Serving measurement at 128KResult
TTFT, Full / CS11.5 / 14.0 s
Additional TTFT2.5 s
Approximate one-request break-even120 generated tokens
E2E speedup, 512 output tokens1.70x
E2E speedup, 2,048 output tokens3.80x
Break-even requests, 32 / 64 output tokens4 / 2

A single 512-token continuation is 1.70x faster after paying construction. Four 32-token requests or two 64-token requests also suffice. These results support both use cases: long one-off requests recover preprocessing, while prefix reuse brings the benefit to short outputs.

2. Longer generation and codebook drift

We evaluated 16 fixed questions from LongBench-v2's Long subset, using Qwen3-32B with A100 TP2, BF16, greedy decoding and a 32-token recent window. These are long-context question-answering tasks; the original document content is truncated to give a total input of 98,304 tokens.

The 96K context supplies the prefill queries for the reusable codebook in our target long-prefix setting. We fix the input and codebook, extend generation, and re-extract answers from the same trajectories at each cap. This tests whether the cached representation remains effective during later reasoning.

Generation capFull accuracyCS accuracyQuery-centroid cosine
2,04837.50%37.50%0.8845
4,09637.50%37.50%0.8274
8,19237.50%43.75%0.8145
16,38431.25%37.50%0.7912

Accuracy uses all 16 questions at every cap. Cosine is a CS-side diagnostic; six pairs remain active in the final 16K window.

The fixed codebook remains useful as generation extends to a 16K cap. Although cosine decreases, CS's relative quality does not deteriorate: between 8K and 16K, both methods lose one correct answer, leaving their gap unchanged. This supports our design choice to reuse prefill-derived scores without reclustering queries during generation.

The recent window protects new keys initially; bounded insertion keeps eligible keys retrievable after they leave it. For stronger query-distribution shifts, budget expansion or codebook refresh are possible extensions, which we will distinguish from the maintenance used here.

3. RetrievalAttention and the query-centric design

RetrievalAttention also uses query information. CSAttention's contribution is to cache signed query-centroid-to-key scores, then reuse them through routing and aggregation during decoding.

To examine the resulting selection quality, we compare Llama-3.1-8B-Instruct on all 503 LongBench-v2 questions, with matched 5% active KV for the sparse methods. CoT uses a 2,048-token cap. R@32 measures recall of Full's top-32 keys on a fixed 50-example subset.

MethodR@32 (%)Overall scoreCoT score
Full100.031.036.5
RetrievalAttention88.930.033.1
Key-centric control87.629.834.7
CSAttention92.731.136.2

CS gains 3.8 recall points and 3.1 CoT points over RetrievalAttention, bringing CoT quality within 0.3 points of Full. Changing only the centroidization target from keys to queries also improves recall by 5.1 points. This controlled result identifies the value of the query-centric design: it retains more useful KV entries at the same attention budget.

For system costs, CS adds 9.6 GiB of tables to 16.0 GiB of KV at 128K, totaling 45.6 GiB with approximately 20 GiB of model state. The construction-inclusive results above quantify when this extra storage and preprocessing deliver a net latency benefit. Our RetrievalAttention comparison uses a quality-compatible backend; a direct latency/memory/build comparison requires benchmarking its native serving implementation. We will make the backend and cost accounting explicit in the revision.

Follow-up on Q1: multi-round coding results

Following your suggestion, we have now completed a multi-round code-repair experiment on 38 QuixBugs Python problems. This supplements the LCC code-completion results in our earlier response with an evaluation of iterative coding.

We used Qwen3-32B, with each run on a single A100, TP=1, BF16, comparing Full Attention against CSAttention with a 5% KV budget. We report both task success and mean total agent time to assess the quality–efficiency trade-off at the task level.

MethodProblems passedSuccess rateMean total agent time
Full Attention20 / 3852.63%194.91 s/problem
CSAttention, 5% KV19 / 3850.00%133.73 s/problem

CSAttention passes 19 problems compared with 20 for Full Attention, while reducing average agent time by 61.18 seconds per problem. This is a 31.39% reduction in total agent time, or a 1.46× speedup, with a success-rate difference of 2.63 percentage points.

These results support the practical benefit of CSAttention in multi-round coding: the small KV budget retains near-Full task success while substantially reducing agent runtime. The additional experiment therefore extends our evidence beyond static code completion to iterative code repair, directly addressing your request for a broader evaluation.

We will add these results and the evaluation protocol to the revision. Thank you for encouraging us to test this setting.

Reviewer_9L5MOpenReview ↗

Official Comment by Reviewer 9L5M

I appreciate the author's additional results. Most of my concerns are addressed. Therefore, I have raised my score to 3.

Reviewer_orbtOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

CSAttention builds query-centroid lookup tables from a reusable prefix. During decoding, it combines candidate scores from these tables, selects tokens, and applies attention to their original KV. The paper reports near-full accuracy and faster decoding at a small active-KV budget.

Critical strengths
  1. Precomputing query-centroid scores is a reasonable way to reduce repeated work for reusable prefixes.
  2. The method achieves accuracy close to full attention while accessing only 5% of the prefix KV cache. It also reports up to 4.24× faster decoding.
Critical weaknesses

Different token selections across heads or groups can limit KV reuse and make efficient GEMM-based computation difficult. The paper does not clearly explain how the implementation handles this issue.

Questions for authors
  1. Which Top-K algorithm is used? Could candidate aggregation and Top-K cost as much as directly computing attention? Please provide a comparison.
  2. Can you evaluate the method on MLA models, including those using DSA? A shared latent KV representation with a larger dimension may be better suited to this method.
  3. Which inference framework is used for the speed tests? Please provide more details, including framework and kernel versions, hardware, batch size, and precision.
3 comments

Thank you for these questions. We measured whether selection overhead cancels the savings from sparse attention and added an experiment with a pretrained DSA model.

1. Top-K and aggregation

We use radix_v2 for Top-K. Each query selects one centroid per subspace; we read the corresponding shortlists, accumulate their signed scores by original key ID, and select the final KV set. Recent-history positions occupy slots within this budget. Attention then uses the selected original KV, not centroid representations.

On one A100-SXM4-80GB, with Llama-3.1-8B-Instruct, FP16, batch 1, TP1, 131,072 input tokens and approximately 5% active KV, we measured:

CS componentms/token
Centroid routing1.192 ± 0.025
Shortlist read + signed reduce-by-key0.364 ± 0.006
Top-K + recent-window union3.440 ± 0.627
Table maintenance0.253 ± 0.008
Original-KV gather0.420 ± 0.003
Sparse attention1.784 ± 0.004
Remaining module operations9.344 ± 0.210

Read/reduce and Top-K/window together take 3.804 ms, versus 15.786 ms for dense attention: 24.1% of its cost, or 31.6% after including routing. This is the benefit of caching centroid-to-key scores: online selection reuses scoring work already performed during construction. It does not replace dense attention with an equally expensive search.

We also compare the complete self-attention module, including the work outside the attention kernel:

ComponentFull, ms/tokenCS, ms/token
Attention kernel15.7861.784
All other module work5715.013
Totalapproximately 72.78616.797

The second row includes retrieval/selection where applicable, projections, RoPE, cache management, maintenance, gather, and residual launch/profiling overhead. Thus, Dense's residual is compared with all CS work outside the attention kernel, not just CS's residual.

The approximately 4.33x profiled module speedup shows that the benefit survives the full selection and data-access path; it is not merely a faster sparse-attention kernel.

2. Head-dependent selection and KV reuse

Different selected sets can make KV access less regular. The relevant question is whether that cost outweighs the work avoided. Here, gather takes 0.420 ms, or 2.5% of the CS module time, and is already included in the comparison above. These measurements support a net benefit despite irregular selection; we do not equate fewer attended tokens with an automatic proportional speedup.

The paper's same-backend comparison provides complementary evidence: at 128K and the same 5% budget, Quest and CSAttention achieve 3.17x and 4.24x decode speedup against the same FlashAttention Full reference. The gain therefore remains when the sparse-attention backend is shared.

The DSA experiment below also uses shared selected IDs across GQA groups. This shows that caching scores does not require every head to gather an independent KV set.

3. Native DSA evaluation and MLA

We evaluated Keye-VL-2.0-30B-A3B, using its pretrained Lightning-indexer weights. CS proposes 4,096 candidates, then the original query-dependent scoring formula reranks them to the same final 2,048 KV positions.

MetricOriginal indexerCS adaptation
HotpotQA F178.9679.58
PassageRetrieval accuracy100.00100.00
Two-task macro score89.4889.79
Decode tokens/s6.13610.740

Reducing the candidate set preserves comparable downstream accuracy without retraining the indexer. This supports cached scoring beyond the conventional attention models in the paper.

The 1.75x throughput gain is for the reported implementations. Both store the main KV on CPU; the original-indexer path accesses it through GPU UVA, while CS transfers selected KV through fused_h2d. The gain therefore includes both selection and KV-access changes. Speed was measured serially on the same A100.

Keye is GQA + DSA, not MLA, so this addresses the DSA part of your question. A shared latent cache is a promising fit: the selector can return positions into that cache, and larger scoring dimensions may make cached scoring more valuable. We have not yet measured that MLA configuration.

4. Setting

The DSA run uses the full 48-layer text model, BF16, batch 1, TP1, vLLM 0.26.0, eager execution, no CUDA Graph/compile or prefix caching, and prefill chunks of 512. CS uses C=64C=64, residual rank 28, at most 512 training queries and 5 k-means iterations. Its CPU Top-K is nth_element with eight threads, distinct from radix_v2 above. We will include these settings, kernel versions and timing boundaries together in the revision.

Thank you for the detailed response. I have one further question regarding the memory–throughput trade-off. The lookup tables add 9.6 GiB on top of the 16 GiB KV cache for a 128K prefix, introducing 60% additional storage overhead. When stored on GPU, this overhead may reduce the maximum feasible batch size and offset some of the decoding gains under memory-constrained or high-concurrency workloads. The batch-size-1 speed measurements in the response do not establish whether the gains persist under a fixed GPU memory budget.

Thank you for raising this point. We have now evaluated the all-GPU configuration under the same GPU memory budget, including the lookup-table overhead and allowing each method to use its own best feasible batch size.

Throughput under the same GPU memory budget

We swept the batch size at 64K and 128K context lengths. Throughput below is normalized to Full Attention at its own best-throughput batch for the same context length. These are aggregate decoding throughput comparisons, rather than batch-size-1 speedups.

ContextMethodMaximum feasible batchBest-throughput batchPeak GPU memory (GiB)Throughput relative to Full
64KFull Attention7773.341.00×
64KCSAttention, 5% KV4470.721.17×
128KFull Attention3365.341.00×
128KCSAttention, 5% KV2272.711.42×

The results capture the trade-off you describe: storing the lookup tables reduces the maximum feasible batch from 7 to 4 at 64K and from 3 to 2 at 128K. Nevertheless, CSAttention delivers 17% and 42% higher aggregate throughput, respectively, after accounting for this capacity reduction. The decoding savings therefore translate into a net throughput benefit under the same GPU memory budget, rather than only a single-request latency improvement. The peak allocations differ because feasible batch sizes are discrete; both methods are subject to the same memory limit.

Reusable-prefix and CPU–GPU serving

Reusable-prefix and CPU–GPU serving are central motivations of our design. These settings further strengthen the practical benefits of CSAttention by amortizing its auxiliary costs or reducing their impact on GPU memory capacity.

In reusable-prefix serving, multiple requests share the immutable prefix KV cache and its score-table snapshot. The table's construction and storage costs are therefore amortized across requests, while each continuation benefits from cheaper decoding. Full Attention can also share its prefix KV; the additional shared cost of CSAttention is one score-table snapshot per distinct prefix, rather than one complete prefix table per request. Generated-suffix KV, mutable update state, and execution buffers remain request-specific. We will make this accounting explicit in the revision.

In CPU–GPU serving, the full KV cache and lookup tables reside in host memory. CPU workers perform shortlist processing, aggregation, Top-K selection, and maintenance, while selected KV entries are transferred to the GPU for decoding attention. The auxiliary tables therefore do not compete with GPU-resident KV storage for the same HBM capacity. Moreover, accurate selection at a small KV budget reduces both CPU–GPU transfer volume and sparse-attention work, making this an especially relevant setting for our method.

These deployment advantages complement the new fixed-memory results: even in the fully GPU-resident setting, where the lookup tables directly reduce the feasible batch size, CSAttention still achieves 17% and 42% higher aggregate throughput at 64K and 128K. We will include these measurements and clearly distinguish the storage and sharing assumptions of each deployment mode.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.