Long-Context Decoding Slowdown: KV Cache Bandwidth and Sparse Attention

    Long-context decoding often slows down not because compute is insufficient, but because KV cache reads saturate memory bandwidth. This article explains prefill and decode phases, estimates KV traffic with an illustrative 64-layer GQA setup, uses roofline analysis to show bandwidth bottlenecks, compares full KV, fixed-window, and shared-subspace sparse attention, distinguishes fixed-size compressed state from per-token summary caches, and provides engineering guidance for quantization, paging, sparse selection, memory budgeting, decoupling selection from generation, and evaluation.

    1. A Counterintuitive Phenomenon: Long-Context Decoding Becomes Slower

    When a large model reads a very long document, such as an approximately 400,000-character novel, and then answers a specific plot-detail question, a common experience is: generating the final answer may not take long, but the wait between finishing reading and starting to speak becomes noticeably longer. This is a typical symptom of long-context decoding slowdown. The cause is often not insufficient GPU compute, but memory bandwidth being saturated by KV cache reads.

    Inference can be divided into two phases. In prefill, all input tokens are processed at once; the computation resembles matrix-matrix multiplication, and weights and intermediate data can be reused. In decode, new tokens are generated one by one, and each step depends on historical content. As context grows, prefill time increases, while decoding slows down because every step must re-read the historical KV cache.

    Each time a large model generates a new token, it usually has to read the key-value cache for all previous positions, known as the KV Cache. When the context doubles, the amount read at each decode step roughly doubles. Once the context is long enough, the bottleneck shifts from compute to bandwidth. This is why KV cache bandwidth becomes a core constraint for long-text inference, and why sparse attention acceleration is considered a response to this bottleneck.

    As an example, shared-subspace sparse attention aims to let the model read only a small amount of history that is most relevant to the current generation, without noticeably degrading generation quality. These methods can be close to standard attention under paper settings and target tasks, but they still need to be measured for the specific scenario. They should not be treated as free or risk-free default acceleration.

    For discussion, use an illustrative configuration: 64 Transformer layers, hidden dimension d=2048, query head count m=16, GQA key-value head count g=2, dimension per key-value head d_s=128, bf16 precision, low-rank state dimension r=8, number of shared subspaces J=8, total retained history tokens t=2048, local window 512, decode length L=10000, block size p=128.

    2. Why Decoding Gets Slower

    A standard Transformer layer usually has three steps: projection, attention, and feed-forward network. Projection produces query Q, key K, and value V. Attention computes relevance between Q and historical K, then performs a weighted sum over V. The feed-forward network applies nonlinear transformation and passes the result upward.

    During prefill, all input positions are computed in parallel, and weights and KV can be reused in batches, making compute easier to utilize. During decode, each step usually has only one new token. Matrix-matrix multiplication degrades into vector-matrix multiplication; after weights are loaded, they serve only one token. Attention also degrades into many small-granularity accesses between a vector and historical K/V. The KV cache avoids recomputing history, but the cost is that historical data must be moved repeatedly at every step.

    1. How Much Data Does One Decode Step Move?

    Using the parameters above, each historical position and each layer stores K and V. K has g × d_s = 256 values, and V also has 256 values, for a total of 512 values. In bf16, each value is 2 bytes, so each token costs about 1 KB per layer. Across 64 layers, that is about 64 KB per token.

    If the full KV cache is read, the approximate read volume is:

    Context length KV cache footprint Read per decode step
    10,000 tokens ~0.64 GB ~0.64 GB
    100,000 tokens ~6.4 GB ~6.4 GB
    500,000 tokens ~32 GB ~32 GB
    1,000,000 tokens ~64 GB ~64 GB

    Assume a single GPU has about 80 GB of memory and 8 TB/s of bandwidth. Reading 32 GB should theoretically take about 4 ms. Real systems are often lower due to operator efficiency, kernel launch overhead, and memory-access utilization. If 500 tokens are generated while the context stays around 500,000 tokens, the attention portion alone may cause about 16 TB of cumulative reads. Weight reads also cost something: for example, a 3-billion-parameter bf16 model needs about 6 GB of weights per step.

    2. Roofline Model Explains the Bottleneck

    The roofline model separates the hardware performance ceiling into a compute line and a bandwidth line. The compute line corresponds to peak FLOP/s. The bandwidth line corresponds to bandwidth multiplied by arithmetic intensity. Arithmetic intensity is the number of floating-point operations completed for each byte of data moved. The ridge point is peak compute divided by peak bandwidth.

    Using 1 PFLOPS of compute and 8 TB/s of bandwidth as an illustrative hardware specification, not all GPU generations, the ridge point is about 125 FLOP/Byte. When arithmetic intensity is below the ridge point, the workload is usually more bandwidth-bound; above the ridge point, it is more likely to be compute-bound.

    Under the setting of 500,000 tokens, 64 layers, m=16, and d_s=128, the attention stage needs to read about 32 GB of KV, and the related floating-point work is about 2.6 × 10^11 FLOP. Arithmetic intensity is about 8 FLOP/Byte, far below the illustrative ridge point. At 1 PFLOPS peak compute, the same computation would theoretically take about 0.26 ms; at 8 TB/s bandwidth, reading 32 GB takes about 4 ms. The bottleneck is closer to bandwidth than compute.

    3. Why Batching Does Not Fundamentally Solve the Problem

    Batching improves throughput by sharing weight reads across multiple requests, but it cannot be scaled indefinitely. KV caches are stored independently per sequence. The more requests in a batch, the higher memory consumption. In long-context scenarios, memory may be exhausted first, forcing the system to reduce concurrency or process requests one by one. At that point, the problem is not only wasted compute, but that memory which should have supported higher concurrency is consumed by caches.

    4. Reading Less Does Not Automatically Mean Immediate Speedup

    Sparse reads do not automatically produce linear acceleration. Memory is accessed in blocks, and scattered per-position reads reduce utilization. The GPU needs enough parallelism to hide memory-access latency. Fixed overheads such as kernel launch and positional encoding do not disappear just because fewer positions are read. Therefore, sparse designs must ensure block-level contiguous reads, sufficient parallelism, and context-length thresholds. With short contexts, sparse indexing itself may not be worthwhile.

    3. Why “Looking at Only Part” Can Work

    Sparse attention relies on the fact that attention distributions are highly uneven. Common observations include:

    • Attention sinks: A few positions at the beginning of the sequence may receive high weights from many queries. They act like stable anchors, and a simple truncation window can accidentally remove them.
    • On-demand concentration: When answering about a character’s fate, relevant information may be concentrated in only a few chapters, while most content has low weight.
    • Block correlation: Adjacent tokens are often important or unimportant together. Selecting by block better matches both data structure and hardware memory-access behavior.

    This leads to two types of approaches: dynamic eviction reduces memory footprint, while dynamic sparsity reduces bandwidth reads. The former decides how much cache to keep; the latter decides how much to read at each step. In engineering, they can be combined.

    4. Shared Subspace: Coarse Filter First, Then Precise Read

    The goal of shared-subspace sparse attention is to add a low-cost “directory”. The directory does not need to be as fine as the original KV; it only needs to help the system locate history blocks most likely to be relevant. The core process can be summarized as follows:

    1. Project Q and K into a low-dimensional shared subspace and compute approximate relevance in that subspace.
    2. Share subspace indexes across all positions so that selection is suitable for parallel and contiguous memory access.
    3. The selected original positions then participate in attention computation at their original precision.

    Shared-subspace scoring does not rely on fine-grained scoring with the original K. Subspace scoring reuses intermediate results from the projection process and depends only on low-rank representations, so it is lighter than full-precision scoring over all original KV. Actual speedups vary with dimensions, head counts, block sizes, and kernel implementations, so a fixed ratio should not be assumed.

    1. Two Implementations Must Be Distinguished: Fixed State vs. Per-Token Summary

    The most important and most confusing point is to separate the “coarse directory” into two implementations with different properties. Their memory and read behaviors are not the same.

    Implementation A: Fixed-size compressed state (r=8). A fixed-size, cross-step reusable linear-attention-like state approximates historical information. The state is updated during decoding, but its size remains constant and does not grow linearly with context. The cost is that it is only a “compressed impression” with limited capacity, so it cannot perform exact fine-grained reading over arbitrary historical blocks. It can provide global relevance tendencies, but cannot replace block-by-block precise reads of original KV.

    Implementation B: Per-token summary cache. For each historical token and each layer, an additional low-dimensional summary is stored. For example, one shared bf16 summary per token per layer is about 256 B. This summary cache does grow linearly with context: at 500,000 tokens and 64 layers, the summary cache itself occupies a significant amount. However, it changes the per-step read volume to be determined by t or p: during coarse filtering, each step only reads summaries for the selected roughly t tokens, not all summaries.

    One-sentence distinction: A fixed-size state cache does not grow, but sacrifices precise reading of arbitrary blocks; a per-token summary supports block-level precise reading, but the summary cache itself grows with context, although per-step reads are bounded by t or block size p. Confusing the two leads to the incorrect belief that “the cache does not grow and can still read per token precisely”.

    r=8 does not mean “only 8 original KV entries are retained per position”. It is a coarse-filter dimension used to construct compressed channels. In a GQA structure, m=16 query heads are divided into g=2 groups, with 8 heads per group. Within a group, a compressed representation of width 8 × d_s can be formed. Concatenating two groups gives width 16 × d_s = 2048. If sliced by d_s=128, this can be understood as 8 equal-width column blocks, corresponding to J=8 subspaces. This explanation describes the data flow; it does not imply that the model necessarily has 8 physically independent matrices.

    Selection usually uses block-level aggregation: divide history into blocks of size p, compute a combined relevance score for each block, select the t/p highest-scoring blocks, and concatenate them with the local window. Block-level selection favors contiguous reads and aligns well with paged caches. If a block is selected when any position inside it is highly relevant, recall is more aggressive and coverage is higher, making it less likely to miss key information but potentially including more irrelevant blocks. If only the block average is used, the approach is more conservative and may miss a few strongly relevant positions inside a block.

    2. The Read-Volume Definition Must Be Clear

    Using a 500,000-token context as an example. If the full original KV is read, each step’s attention read is about 32 GB. If the shared-subspace scheme is used:

    • The coarse-filter branch reads “one shared bf16 summary”, about 256 B per token per layer. Selecting about 2,560 token entries (t=2048 plus a 512-token window), across 64 layers, is about 40 MB.
    • The precise branch reads the selected original double-head bf16 KV, about 1 KB per token per layer. At the same scale, this is about 160 MB.

    It must be emphasized that the 40 MB and 160 MB figures are per-step read volumes, not cache footprint. The corresponding summary cache itself grows with context, but per-step reads are bounded by t. Therefore, when comparing schemes, three definitions must be stated: whether it refers to original double-head KV, shared single summary, or low-precision quantized cache; and whether it refers to per-step read volume or resident cache volume. Otherwise, differences between 40 MB and 160 MB, and between cache and reads, can lead to misjudgment.

    3. Two Branches in Parallel

    A shared-subspace scheme usually has two branches. The subspace branch only updates a fixed-size or summary-level compressed state. The original branch only reads the selected original positions. The two branches execute in parallel and do not wait for each other. Ideally, the per-step original read volume does not grow linearly with context; whether the original KV, summaries, and index caches grow depends on retention, paging, and eviction policies. This avoids full access while allowing different data layouts to use different kernels.

    5. Engineering Perspective: There Is No Free Lunch

    1. Common Optimization Techniques

    Long-context inference already has several engineering techniques:

    • KV quantization: Store KV in lower precision such as FP8 or INT8 to reduce memory and bandwidth pressure, but it introduces quantization error.
    • Low-rank compression: Compress KV into a low-dimensional latent space to reduce cache size, but adds projection computation.
    • Paging and sharing: Organize cache by blocks to support prefix reuse and block-table management.
    • Scheduling optimization: Use chunked prefill and overlap computation with data movement.
    • State-like structures: Suitable for extremely long streaming scenarios.
    • Dynamic eviction: Evict low-relevance cache blocks according to a budget.
    • Speculative decoding: A small model guesses and a large model verifies.

    Shared subspace does not conflict with these techniques. When combined with low-rank compression, latent vectors can serve as carriers for subspace scoring. When combined with paged caches, block-level selection naturally aligns with page boundaries.

    2. Memory Budget Formula

    Before planning concurrency and context, account for memory usage. Usable memory is approximately: weights + activations + KV cache + concurrency overhead + fragmentation and reserved margin. KV cache is proportional to “context length × concurrency” and is the easiest item to underestimate. In long-context scenarios, prioritize compressing KV with quantization, low-rank methods, and eviction, and use the saved memory for concurrency or context length rather than simply increasing batch size.

    3. Decouple Selection from Generation

    Putting selection and generation in the same step introduces a serial dependency. In engineering, approximate selection can be completed several steps ahead and then trigger the storage layer to prefetch. For conversational long documents, KV release can also be delayed: if a later question falls within the retained window, it can be reused directly; if it points to evicted content, recompute relevant blocks or bring in context with retrieval. This turns “whether to reread the entire long document” into “whether to recompute a few fragments”.

    4. Combining Quantization, Paging, and Sparsity

    In common combinations, quantization reduces the cost per byte, sparsity reduces total read volume, and paging optimizes cache organization and sharing. A recommended order is: first use quantization to lower per-unit cost, then align blocks with paged caches, then enable sparse selection, and finally adjust t, p, window size, and context thresholds based on measurements. The following table separates “whether per-step attention reads grow with context” from “whether cache/index footprint grows with context”, avoiding confusion:

    Scheme Attention read per decode step Read per step grows with context? Cache/index footprint grows with context? Additional cost
    Full KV, bf16 ~32 GB Yes Yes Memory and bandwidth pressure
    Full KV, FP8 ~16 GB Yes Yes Quantization error
    Fixed window 512 ~32 MB No No (only the window is retained) Information outside the window is hard to recall
    Shared-subspace summary (per-token summary) ~40 MB No (determined by t) Yes (summary cache grows linearly with context) Approximation error and indexing overhead
    Shared subspace + FP8 ~20 MB No (determined by t) Yes Stacked approximation and quantization errors

    5. Memory Tax and Fused Kernels

    If conventional attention explicitly constructs the full score matrix, it adds extra memory pressure. In the illustrative accounting here, with 16 heads, 500,000 tokens, and fp32, one layer’s score matrix is about 32 MB, and 64 layers are about 2 GB. If multiple requests are considered or intermediate results are retained, memory demand is larger. Fused attention kernels can avoid writing the full score matrix to memory, reducing this overhead. Shared subspace uses fixed-size states or summary-level states to turn context-growing intermediate memory into a more stable magnitude.

    6. Effects Must Be Measured

    Evaluating sparse attention requires at least two dimensions: first, how close approximate attention is to standard attention, for example measured by cosine similarity; second, the additional quality loss introduced by sparsity, for example perplexity, cross-entropy, or target-task metrics.

    The table below is illustrative, not measured, and does not represent any fixed benefit. Descriptions such as “minimal” or “small” only show trends. Real results depend on model scale, dataset, context length, sparsity ratio (J/t), and quality measurement method (perplexity, cross-entropy, or downstream task metrics). Engineers must scan J, t, block size, and window size on their own target datasets and measure results. Fixed ratios should not be assumed, and “minimal/small” should not be treated as a reproducible promise. Illustrative configurations:

    Configuration (J / t) New quality loss (illustrative) Approximate recall (illustrative) Suitable direction (illustrative)
    16 / 2048 Minimal High High-precision QA
    8 / 2048 Small Relatively high Default balance
    8 / 1024 Relatively small Medium Throughput-first
    4 / 512 Medium Relatively low Long-document summarization
    1 / 256 Relatively large Low Exploratory experiments

    7. Indexes Themselves Have Costs

    Constructing subspaces, computing similarities, and sorting block selections consume compute and memory. In short-context cases, these costs may exceed the bandwidth savings. Production systems can route by context length: short requests use standard attention, while long requests use the sparse path. Thresholds should be determined by the measured crossover point and aligned with paged-cache block granularity.

    6. FAQ: How to Choose and Avoid Pitfalls

    Q1: Why does the KV cache make decoding slower?

    Because each time a new token is generated, the model must read the K and V of previous history. The longer the context, the more is read per step, and bandwidth more easily becomes the bottleneck.

    Q2: How should the roofline ridge point be understood?

    The ridge point is approximately peak compute divided by peak bandwidth. The formula is: ridge point (FLOP/Byte) = peak compute (FLOP/s) ÷ peak bandwidth (Byte/s). For example, 1 PFLOPS (10^15) ÷ 8 TB/s (8 × 10^12) = 125 FLOP/Byte. Readers can plug in their own GPU parameters. For example, a GPU with 2 PFLOPS compute and 3 TB/s bandwidth has a ridge point of about 667 FLOP/Byte. When arithmetic intensity is below the ridge point, the workload is usually more bandwidth-bound.

    Q3: How should sparse attention and quantization be chosen?

    Quantization lowers the cost per byte and is suitable for long contexts. Sparsity lowers total read volume and is suitable for extremely long contexts. When the context is only a few thousand tokens, sparse indexing overhead may not be worthwhile.

    Q4: Are the “fixed state” and “per-token summary” in shared subspace the same thing?

    No. A fixed-state cache does not grow with context, but it cannot precisely read arbitrary blocks. A per-token summary supports block-level precise reading, but the summary cache grows with context; per-step reads are limited by t or p.

    Q5: What are common mistakes?

    • Only looking at single-step latency, not bandwidth utilization.
    • Optimizing attention without managing cache budget.
    • Forcing sparse selection in short-context cases.
    • Ignoring attention-sink prefixes.
    • Confusing “retain t per subspace” with “retain t in total”.
    • Confusing “per-step read volume” with “resident cache volume”.
    • Only measuring offline metrics, without evaluating online long-document QA and multi-hop reasoning.

    7. Practical Checklist

    1. Measure first, optimize later: Observe prefill compute utilization and decode memory traffic separately. Do not look only at single-step latency.
    2. Account for the memory budget: Estimate with “weights + activations + KV cache + concurrency overhead + margin”. For long contexts, prioritize KV compression.
    3. Select by block and retain conservatively: Score by block, ensure contiguous reads, and retain attention-sink prefixes and local windows.
    4. Layer the techniques: Quantize first, then page, then sparsify, and finally adjust t, J, window size, and thresholds.
    5. Tune in three steps: First, determine concurrency and context limits from the memory budget; second, align block size p with paged-cache page size and memory-access granularity; third, scan context thresholds and use the latency-quality crossover point to decide when short requests use standard attention and long requests use the sparse path.
    6. Decouple selection and generation: Prefilter early, prefetch asynchronously, fetch on demand, and release KV lazily.
    7. Build complete evaluations: Include long-document retrieval, multi-hop reasoning, and long-document summarization.
    8. Configure by scenario: Fact-based QA should be conservative, summarization and rewriting can be more aggressive, and streaming long conversations should prioritize state-like structures.

    Conclusion

    The core contradiction in long-context decoding is not “compute too slowly”, but “moving too much”. The KV cache replaces repeated computation with repeated movement. The longer the context, the more obvious bandwidth pressure becomes. The value of shared-subspace sparse attention is to turn page-by-page reading into checking a directory first and then reading key sections: coarse filtering uses fixed states or summaries for localization, while precise reading targets only a small number of block-organized original positions.

    Remember two points: a fixed-state cache does not grow but sacrifices precise reading; a per-token summary cache grows with context but keeps per-step reads within t. When comparing schemes, always distinguish “per-step read volume” from “resident cache volume”. Developers should not chase a single trick, but establish a methodology of “locate the bottleneck first, then optimize in layers”. When bandwidth becomes the main constraint of long-text inference, reducing data movement, improving cache reuse, and controlling memory tax are the keys to letting models reliably read long documents and generate quickly.