Skip to content

LongFlow: Efficient KV Cache Compression for Reasoning Models

Conference: EMNLP 2026
Paper: ACL Anthology
Code: https://github.com/yisunlp/LongFLow
Area: Model Compression
Keywords: KV cache compression, reasoning models, operator fusion, static memory management, sparse attention

TL;DR

Addressing severe KV cache memory inflation and bandwidth bottlenecks in long Chain-of-Thought reasoning models, LongFlow proposes a zero-history importance metric derived directly from intermediate attention contribution vectors using only the current query, and co-designs a fused Triton kernel integrating FlashAttention, token scoring, and in-place eviction to achieve an 80% KV cache reduction and up to an 11.8x throughput speedup while preserving reasoning accuracy.

Background & Motivation

Recent reasoning foundation models, pioneered by OpenAI-o1 and DeepSeek-R1, have established new state-of-the-art benchmarks on challenging logical domains such as competitive mathematics, code synthesis, and advanced scientific inquiry. These performance breakthroughs are powered by scaling test-time compute, where models deliberately generate extensive intermediate reasoning steps across thousands or tens of thousands of tokens. However, this long-output paradigm imposes severe practical deployment costs: the autoregressively expanding Key-Value (KV) cache drastically inflates GPU high-bandwidth memory (HBM) consumption and induces critical memory-bandwidth contention during per-step attention computation.

Existing KV cache optimization methodologies are ill-suited for the long-output regime characteristic of reasoning models. One class of approaches, such as SnapKV, restricts compression exclusively to the prefill phase, compressing only the initial prompt and leaving the subsequent explosive generation phase unmanaged. Another class of dynamic eviction algorithms, including H2O and VATP, relies on accumulating attention weights over historical query trajectories or evaluating multi-step importance scores. Such strategies incur significant computational overhead and necessitate allocating auxiliary metadata tensors in GPU memory, which largely cancels the efficiency benefits of cache pruning. Crucially, modern LLM serving engines depend heavily on hardware-aware fused kernels like FlashAttention, whereas conventional eviction methods disrupt operator fusion by forcing intermediate activations to round-trip between on-chip SRAM and off-chip HBM, frequently resulting in higher real-world latency despite smaller cache footprints.

To resolve this bottleneck, this paper challenges the prevailing belief that accurate token pruning demands historical score tracking, identifying strong adjacent-query cosine similarity throughout long-horizon reasoning. Core idea: LongFlow uses the un-normalized contribution vector (\(\alpha_{it} v_i\) via its L1 norm) from standard attention forward computation with only the current query as a zero-history, zero-storage proxy for token importance, and couples it with a custom Triton fused kernel that merges FlashAttention, importance evaluation, and in-place token eviction into a single operator under static memory pre-allocation.

Method

Overall Architecture

LongFlow establishes a hardware-software co-designed KV cache compression pipeline tailored for autoregressive long-form generation. At initialization, the system allocates a static, fixed-budget KV buffer (e.g., 3,200 tokens) accompanied by a valid slot mask, entirely eliminating dynamic allocation and runtime memory fragmentation. During each autoregressive decoding step, the single-vector query \(q_t\), static KV cache, and mask are fed into a custom Triton fused kernel. Operating on-chip within SRAM, the kernel tiles the KV cache, computes block-wise scaled dot-product attention, extracts intermediate contribution vectors, accumulates the attention output, and computes un-normalized importance scores in a single pass. The token slot with the lowest score is determined via an on-chip reduction, which is subsequently overwritten in-place by the newly generated key-value pair in the next generation step.

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["Current Single Query $q_t$ and New Input"] --> B["In-place Overwrite Evicted Slot<br/>Static Pre-allocated KV Cache Buffer"]
    B --> C["Block-wise Load to On-chip SRAM<br/>I/O-Aware Tiling Execution"]
    C --> D["Single-Query Attention & Intermediate Extraction<br/>$C_j = \\exp(S_j) \\cdot V_j$ Restructured Formulation"]
    D --> E["Zero-History Importance Metric<br/>$\\text{LongFlowScore} = \\sum |C_j|$ On-chip Reduction"]
    E --> F["Triton Fused Eviction Decision & Normalization<br/>Produce Output $o_t$ and Pin Eviction Index $i_{\\text{evict}}$"]

Key Designs

1. Zero-History Importance Metric: Single-Query Proxy and Intermediate Contribution Reuse

Prior eviction techniques require maintaining historical attention accumulators across decoding steps, causing substantial memory traffic and latency. LongFlow starts by formulating the ideal eviction objective at step \(t\): selecting the historical token \(t_i\) whose removal minimizes the perturbation on the attention output of the immediate next step \(o_{t+1}\): $\(\arg\min_i \| o_{t+1} - o_{t+1}^{(\setminus i)} \|_2^2\)$ where \(o_{t+1}^{(\setminus i)}\) denotes the attention output computed without the key-value representation of token \(t_i\). Because future query \(q_{t+1}\) is unavailable at step \(t\), the authors observe that consecutive queries in reasoning chains exhibit exceptionally high cosine similarity (averaging above 0.83 across millions of layer-head measurements). Consequently, the current attention distribution serves as a faithful proxy for the next step, allowing \(q_t\) to substitute for \(q_{t+1}\).

Next, considering the exact attention output change \(\Delta o_t = o_t - o_t^{(\setminus i)}\) under eviction, the softmax denominator shift between \(Z = \sum_j \exp(s_{jt})\) and \(Z^{(\setminus i)} = \sum_{j \ne i} \exp(s_{jt})\) is negligible when the context length is large and the candidate token receives minimal attention (\(Z \approx Z^{(\setminus i)}\)). Under this denominator approximation, the perturbation simplifies directly to the individual contribution vector of token \(t_i\): $\(c_{it} = \alpha_{it} v_i\)$ where \(\alpha_{it}\) is the normalized attention weight and \(v_i\) is the value vector. To eliminate extra operations, LongFlow adopts the L1 norm to quantify contribution magnitude: $\(\text{LongFlowScore}(t_i) = \| c_{it} \|_1 = \alpha_{it} \sum_{l=1}^d |(v_i)_l|\)$ Crucially, the un-normalized contribution tensor \(C_j = \exp(S_j) \cdot V_j\) is an essential intermediate product already formed during standard attention computation. Thus, token importance is acquired via a lightweight on-chip reduction over this tensor, requiring zero auxiliary metadata tensors and zero re-computation.

2. Theoretical Error Bound Derivation: Denominator Perturbation and Query Drift

To justify approximating the ideal future objective with the instant \(\text{LongFlowScore}\), the paper decomposes the total approximation error \(E_i = \| o_{t+1} - o_{t+1}^{(\setminus i)} \|^2 - \| c_{it} \|^2\) via the triangle inequality into two orthogonal sources: $\(E_i \le \left| \| o_{t+1} - o_{t+1}^{(\setminus i)} \|^2 - \| c_{i, t+1} \|^2 \right| + \left| \| c_{i, t+1} \|^2 - \| c_{it} \|^2 \right|\)$ The first term corresponds to the Denominator Approximation Error. Rigorous algebraic expansion reveals that the remainder vector \(R_{i, t+1} = \Delta o_{t+1} - c_{i, t+1}\) is strictly bounded: $\(\| R_{i, t+1} \| \le 2 V \frac{\alpha_{i, t+1}}{1 - \alpha_{i, t+1}}\)$ where \(V = \max_j \| v_j \|\). Because LongFlow targets tokens with near-zero attention weights (\(\alpha_{i, t+1} \ll 1\)), this bound guarantees that the denominator approximation error vanishes rapidly for pruned candidates.

The second term represents the Query Drift Error resulting from temporal approximation. By leveraging the 1-Lipschitz continuity of the softmax operator under the \(L_\infty \to L_1\) mapping, the variation in attention weights is bounded by the maximum perturbation in pre-softmax logits: \(|\alpha_{i, t+1} - \alpha_{it}| \le \max_j |s_{j, t+1} - s_{jt}|\). Applying the Cauchy-Schwarz inequality for unit-normalized queries yields: $\(\max_j |s_{j, t+1} - s_{jt}| \le \frac{\sqrt{2(1 - \cos(q_t, q_{t+1}))}}{\sqrt{d_k}} \max_j \| k_j \|\)$ This proves that as the cosine similarity between adjacent queries approaches 1, the temporal approximation error converges to 0, providing firm theoretical validation for the single-query estimation mechanism.

3. Custom Fused Triton Kernel for In-Place Eviction

In standard inference architectures, decoupling attention kernels from eviction logic incurs prohibitive overheads: the attention operator writes full outputs to HBM, and external dispatch routines read the cache back to perform sorting. LongFlow addresses this through an optimized Triton kernel tailored for decoding: - Loop Restructuring: Because the decoding query length is strictly 1, the outer query iteration in standard FlashAttention is eliminated, streaming blocks of cached \(K, V\) through SRAM in a single unified loop. - Intermediate Reuse and Numerically Stable Softmax: Intermediate logits are exponentiated in FP32 precision. Instead of materializing full softmax probabilities before matrix multiplication with \(V\), the kernel directly computes un-normalized contribution vectors \(C_j = \exp(S_j) \cdot V_j\). This tensor is simultaneously summed along the sequence dimension into the global attention output accumulator \(o_{\text{acc}}\) and reduced along the hidden dimension via absolute-value summation to yield the un-normalized block score \(S_{\text{loss}, j}\). - On-Chip Eviction Decision: Upon finishing the KV loop, the accumulator is normalized by the scalar denominator \(l_{\text{acc}}\) to produce the final attention vector \(o_t\). In parallel, \(S_{\text{loss}}\) is divided by \(l_{\text{acc}}\) to produce global \(\text{LongFlowScore}\), and an on-chip argmin pins the eviction index \(i_{\text{evict}}\). This completely fuses attention computation and eviction into a single hardware pass, reducing attention module latency from 47 ms to 8 ms (measured on Qwen3-8B with batch size 128 and sequence length 3,200).

4. Static Memory Allocation and Uniform Per-Step Eviction

Dynamic memory schemes that repeatedly allocate, slice, and deallocate KV cache tensors create severe memory fragmentation within the CUDA caching allocator, capping batch sizes and inducing out-of-memory crashes during long generations. LongFlow resolves this by pre-allocating a contiguous, static memory pool matching the exact KV budget (e.g., 3,200 tokens). Every decoding step operates with an invariant workload: exactly one token is pruned and overwritten at the index selected in the preceding step. This static layout guarantees predictable memory consumption, entirely prevents runtime fragmentation, and enables deployment with significantly larger batch sizes.

A Worked Example

Consider a reasoning model generating an extensive solution at decoding step 4,000, operating under a configured static KV cache budget of 3,200 tokens (which is currently full): 1. In-place Overwrite: The runtime retrieves the eviction index \(i_{\text{evict}} = 1420\) identified at step 3,999. The newly projected \(k_{4000}, v_{4000}\) vectors are directly written into row 1420 of the static KV buffer in GPU memory. 2. Fused Block Execution: The Triton kernel loads the static cache into SRAM in blocks of size \(B_k = 128\). For each block, the kernel computes logits against the current query \(q_{4000} \in \mathbb{R}^{1 \times d}\), forms the intermediate contribution matrix \(C_j = \exp(S_j) \cdot V_j\), and updates both the output vector accumulator and the block-level L1 importance scores on-chip. 3. Decision Return: After iterating through all 25 blocks (3,200 tokens), the kernel normalizes the output vector \(o_{4000}\) and identifies the global minimum importance score, returning \(i_{\text{evict}} = 853\) (a transient scratchpad token from an earlier derivation). Slot 853 is recorded to be overwritten at step 4,001. No temporary allocations or external sorting calls are made.

Loss & Training

LongFlow is entirely training-free and requires no fine-tuning, weight adaptation, or architectural modifications. When the prompt length in the prefill stage exceeds the configured KV budget, SnapKV is invoked once to initialize the cache within budget boundaries; subsequent autoregressive generation is handled end-to-end by the fused LongFlow kernel.

Key Experimental Results

Main Results

Evaluations were conducted on NVIDIA A100-40GB GPUs across challenging reasoning benchmarks with an output generation horizon of up to 16,000 tokens. Models evaluated include DeepSeek-R1-Distill-Llama-8B and Qwen3-8B across competitive math (AIME24, AIME25, AMC-23, MATH-500), complex scientific reasoning (GPQA, Minerva, OlympiadBench), and grade-school arithmetic (GSM8K).

Model KV Budget Method AIME24 (30) AIME25 (30) AMC (40) GPQA (198) GSM8K (1318) MATH (500) Minerva (272) Olympiad (675)
DeepSeek-R1-Distill-Llama-8B Budget=3200 Vanilla (Full KV) 30.00 20.00 77.50 41.41 77.47 83.40 20.59 44.30
DeepSeek-R1-Distill-Llama-8B Budget=3200 H2O 36.67 23.33 72.50 38.38 77.69 81.60 21.32 46.22
DeepSeek-R1-Distill-Llama-8B Budget=3200 R-KV 30.00 23.33 77.50 42.93 77.62 82.40 19.49 46.81
DeepSeek-R1-Distill-Llama-8B Budget=3200 VATP 40.00 16.67 72.50 42.42 77.39 81.60 19.12 46.67
DeepSeek-R1-Distill-Llama-8B Budget=3200 LongFlow (Ours) 33.33 26.67 82.50 40.91 77.62 79.80 20.22 45.93
DeepSeek-R1-Distill-Llama-8B Budget=2400 Vanilla (Full KV) 30.00 20.00 77.50 41.41 77.48 83.40 20.59 44.30
DeepSeek-R1-Distill-Llama-8B Budget=2400 LongFlow (Ours) 33.33 16.67 70.00 40.40 77.71 79.80 20.22 43.85
Qwen3-8B Budget=3200 Vanilla (Full KV) 60.00 46.67 90.00 34.85 95.68 92.60 33.46 58.22
Qwen3-8B Budget=3200 H2O 46.67 26.67 80.00 27.78 96.36 90.40 35.29 53.78
Qwen3-8B Budget=3200 R-KV 50.00 33.33 82.50 32.32 96.36 91.60 33.46 55.56
Qwen3-8B Budget=3200 VATP 43.33 33.33 82.50 30.30 96.43 91.00 34.19 55.41
Qwen3-8B Budget=3200 LongFlow (Ours) 50.00 26.67 85.00 30.30 96.36 89.80 34.19 55.56
Qwen3-8B Budget=2400 LongFlow (Ours) 36.67 26.67 80.00 30.81 95.83 88.00 31.25 51.11

Ablation Study & System Performance

Operator-level latency breakdown and system throughput benchmarks were conducted to isolate the contribution of kernel fusion from the eviction algorithm itself.

Operator-Level Latency Comparison Batch Size KV Cache Length PyTorch Baseline (ms) Triton Fused Kernel (ms) Speedup Note
Fixed LongFlow Metric (Qwen3-4B, H20-96GB) 128 3,200 26.34 5.22 5.05× Demonstrates dramatic reduction in HBM traffic
H2O Attention & Eviction Pipeline 128 3,200 47.00 8.00 (Ours) 5.88× Eliminates external metadata accumulation
Norm Choice Ablation (Qwen3-8B, Budget=3200) AIME24 AIME25 AMC GPQA GSM8K MATH Minerva Olympiad
L1 Norm (Default) 50.00 26.67 85.00 30.30 96.36 89.80 34.19 55.56
L2 Norm 50.00 30.00 82.50 30.80 96.21 90.20 34.19 55.11
End-to-End Throughput (tokens/s, H20-96GB, Budget=3200) Model Batch Size H2O VATP R-KV LongFlow (Ours)
Qwen3-4B (Output 4096) 4B 32 261.32 225.96 169.68 504.07
Qwen3-8B (Output 4096) 8B 16 223.83 208.51 110.86 356.47
Qwen3-8B (Output 4096) 8B 24 188.24 225.46 119.30 450.13
Qwen3-8B (Output 4096) 8B 32 254.17 238.02 251.83 485.18

Key Findings

  • High Retention of Complex Reasoning: Compressing the KV cache by 80% (budget of 3.2k tokens on 16k generation) causes negligible performance degradation compared to Full KV: an average drop of merely 0.08% for DeepSeek-R1-Distill-Llama-8B and approximately 1.3% for Qwen3-8B, remaining highly competitive with or outperforming H2O, VATP, and TOVA.
  • Superior Throughput and Batch Scaling: On Qwen3-1.7B, LongFlow improves serving throughput by up to 11.8x over Vanilla Full KV and is approximately 4.0x faster than competing compression baselines. Static allocation eliminates memory fragmentation, allowing LongFlow to serve batch sizes exceeding 60, compared to around 10 for Full KV.
  • Invariance to Norm Selection: Using the L1 norm instead of the L2 norm yields virtually identical benchmark accuracy across all tasks, validating the hypothesis that token ranking is dominated by attention weight \(\alpha_{it}\) and justifying L1 reduction for faster on-chip execution.
  • Absence of Length Inflation: On OlympiadBench, average sequence length was 8488.62 for Vanilla and 8523.06 for LongFlow (a negligible 0.4% variation), demonstrating that token pruning does not induce repetitive degeneration or systemic overthinking.

Highlights & Insights

  • Zero-History Mathematical Formulation: The paper demonstrates that tracking long-term attention history is unnecessary during long reasoning generation; approximating future output loss via the current step's un-normalized contribution vector \(\alpha_{it} v_i\) provides a theoretically justified, nearly cost-free eviction metric.
  • Full-Stack Hardware-Algorithm Co-Design: Rather than treating compression as an isolated algorithmic post-processing step, LongFlow fuses attention computation, intermediate reduction, and eviction selection into a single Triton kernel, overcoming memory bandwidth bottlenecks.
  • Static Workload Determinism: Replacing dynamic buffer resizing with pre-allocated static cache buffers and constant per-step in-place overwriting eliminates PyTorch memory fragmentation and unlocks massive concurrency gains in real-world serving systems.

Limitations & Future Work

  • Reliance on Query Continuity: The single-query proxy assumes adjacent decoding steps share high cosine similarity. In scenarios with sudden distribution shifts—such as frequent tool-use invocations, multi-turn conversational jumps, or highly stochastic temperature sampling—the current query may serve as a less reliable proxy for future attention.
  • Decoding-Centric Specialization: LongFlow's fused kernel is optimized for autoregressive decoding where query length equals 1. It does not natively optimize the bidirectional prefill phase or non-autoregressive architectures, leaving unified prefill-decode compression as future work.
  • vs H2O / Scissorhands: H2O requires cumulative tracking of historical attention weights across decoding steps, storing extra metadata and invoking periodic sorting routines; LongFlow proves that single-query intermediate contribution vectors achieve equal or better quality with zero storage overhead.
  • vs SnapKV: SnapKV compresses only the prompt during prefill, leaving subsequent long-form decoding uncompressed; LongFlow maintains a constant memory footprint throughout prolonged generation sequences.
  • vs VATP / R-KV: VATP introduces Value norms into historical scores, while R-KV monitors repetitive generation patterns with heavy computational overhead. LongFlow integrates scoring directly into the attention forward pass as an organic byproduct, achieving practical wall-clock speedups.

Rating

  • Novelty: ⭐⭐⭐⭐⭐ Replaces costly multi-step attention history tracking with an elegant, theoretically sound single-query intermediate metric.
  • Experimental Thoroughness: ⭐⭐⭐⭐⭐ Rigorously tested across 8 rigorous reasoning benchmarks, 0.6B to 8B parameter models, operator-level latency breakdowns, and multi-batch throughput profiles.
  • Writing Quality: ⭐⭐⭐⭐⭐ Highly coherent, providing strict mathematical error bounds, lucid hardware architectural explanations, and clear empirical motivation.
  • Value: ⭐⭐⭐⭐⭐ Offers an exceptionally practical, hardware-friendly KV cache compression paradigm for deploying long Chain-of-Thought reasoning models.