Skip to content

Enabling KV Caching of Shared Prefix for Diffusion Language Models

Conference: EMNLP 2026
Paper: ACL Anthology
Code: https://github.com/OSSS-KU/BiCache
Area: Model Compression
Keywords: Diffusion Language Models, Key-Value Cache, Shared Prefix Caching, Layer-Partitioned Caching, High-Throughput Serving

TL;DR

To overcome the severe accuracy collapse to near-zero caused by naively porting autoregressive shared-prefix caching to diffusion language models (DLMs), BICACHE introduces the first bidirectional prefix caching framework, which dynamically determines safe shallow layers based on the shared prefix ratio and applies periodic refresh in deep layers, boosting throughput by 36.3%–98.3% while keeping accuracy drops within 0%–1.8%.

Background & Motivation

In high-throughput large language model (LLM) serving systems, key-value (KV) caching is an indispensable performance optimization. In particular, real-world serving workloads are dominated by shared prefixes—such as fixed system prompts, role guidelines, formatting rules, and multi-turn conversational history—which routinely account for 85% to 97% of total prompt tokens. In conventional autoregressive models (ARMs), attention mechanisms strictly obey a causal mask, meaning that the KV states of past tokens remain mathematically invariant once computed, even when future tokens are appended or across distinct requests sharing the same prefix. Consequently, production serving engines such as vLLM leverage shared prefix caching to precompute and reuse prefix KVs across requests, achieving massive latency reductions and multi-fold throughput speedups.

Recently, diffusion language models (DLMs, such as LLaDA) have emerged as a highly compelling alternative to ARMs. By discarding the rigid left-to-right generation order in favor of all-to-all bidirectional attention across iterative denoising steps, DLMs predict tokens at arbitrary positions simultaneously, mitigating autoregressive inference latency bottlenecks and cognitive limitations like the reversal curse. However, this bidirectional generation paradigm introduces a catastrophic roadblock for shared prefix caching: whenever any token is updated or unmasked during a denoising step, bidirectional attention alters the global representation context, which continuously updates the hidden states and KV projections of all tokens across steps and requests, including those within the shared prefix. When standard ARM-style shared prefix caching (e.g., vLLM) is applied to DLMs without modification, reusing static prefix KVs computed without suffix context severely corrupts the global attention distribution. Motivating experiments clearly demonstrate that naively applying ARM prefix caching to LLaDA drives accuracy on ARC-Challenge-Chat, GPQA, and MATH-500 to near zero (e.g., plummeting from 86.1% to 0.1% on ARC-C, and from 18.2% to 0.0% on MATH-500).

Existing acceleration methods for DLMs (such as Fast-dLLM and dLLM-Cache) focus exclusively on intra-request KV reuse across denoising steps, offering no mechanism for inter-request prefix sharing. Core idea: Through a rigorous characterization of KV dynamics under bidirectional attention, this paper reveals that shared prefix KVs remain highly similar and stable across requests in shallow layers, while the maximum reusable depth is strongly governed by the request's shared prefix ratio; BICACHE capitalizes on these insights by profiling a safe shallow layer depth per prefix ratio to enable zero-overhead cross-request reuse, while enforcing periodic step-wise refresh in deeper layers to eliminate redundant computation without sacrificing accuracy.

Method

Overall Architecture

BICACHE implements a dual-stage architecture combining offline shared prefix profiling with online layer-partitioned caching. In the offline phase, BICACHE profiles the cosine similarity between cached prefix KVs and full-context reference KVs across layers and steps over a diverse set of real-world dialogue requests, evaluating different shared prefix ratios \(r\). Using a strict empirical similarity threshold \(\tau\), it derives a lookup table \(\mathcal{T}\) mapping any given prefix ratio \(r\) to the maximum safe shallow layer depth \(b\). During online inference, when a new user request arrives, BICACHE measures its shared prefix ratio \(r\), queries \(\mathcal{T}\) to retrieve the boundary depth \(b\), and hashes the prefix string to check an in-memory KV table \(\mathcal{H}\). On a cache hit, shallow layers (\(\ell \le b\)) directly load and reuse the precomputed prefix KVs across all steps and requests; meanwhile, deep layers (\(\ell > b\)) compute prefix KVs within the request and periodically refresh them every \(\Delta\) denoising steps.

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["Incoming request with prefix p and user prompt"] --> B["Shared prefix profiling<br/>Compute ratio r and lookup safe depth b from T"]
    B --> C{"Layer index ℓ ≤ b ?"}
    C -->|Yes: shallow layers| D["Shallow cross-request reuse<br/>Hash lookup in H loads static prefix KVs"]
    C -->|No: deep layers| E{"Step t satisfies<br/>(t-1) mod Δ == 0 ?"}
    E -->|Yes: refresh step| F["Deep intra-request recomputation<br/>Update prefix KVs with current dynamic context"]
    E -->|No: intermediate step| G["Deep step-wise reuse<br/>Reuse prefix KVs from step t-1"]
    D --> H["Bidirectional attention denoising and multi-step decoding"]
    F --> H
    G --> H

Key Designs

1. Similarity characterization across dimensions and prefix ratio-governed depth bounds

To resolve the tension between bidirectional attention drift and KV caching, the authors performed comprehensive cosine similarity analyses across layers, steps, and requests. The empirical findings reveal two fundamental phenomena: first, shared prefix KVs in shallow layers (layers 1 to 16 in a 32-layer LLaDA) exhibit near-perfect similarity across requests (averaging 0.98 with a tiny step-wise standard deviation of 0.007), showing that early representations capture foundational lexical and syntactic features that are largely impervious to suffix variations; in contrast, deeper layers (layers 17 to 32) show a pronounced drop to an average similarity of 0.86. Second, the maximum safe depth \(b\) is invariant to downstream task domains (e.g., mathematics versus reasoning) but strongly correlated with the shared prefix ratio \(r = m / N\). When \(r\) is large, the sequence is dominated by prefix tokens, strictly bounding the attention leakage from suffix tokens to prefix tokens. The paper provides a formal theoretical proof in the appendix showing that under bounded value norms and Lipschitz attention stability, the cosine similarity between cached and reference prefix KVs satisfies a step-wise lower bound:

\[\text{sim}_{\ell,t} \ge 1 - c_{\ell,t} \, g_{\ell,t}(1 - r)^2 = \text{LB}_{\ell,t}(r)\]

This theorem mathematically establishes that a guaranteed shallow layer depth \(b_{\text{safe}}(r)\) exists and is strictly dictated by the shared prefix ratio \(r\), ensuring that thresholding at \(\tau = 0.97\) provides a safe boundary against accuracy degradation.

2. Offline shared prefix profiling and constant-time hash lookup table

To eliminate runtime overhead in deriving the partition boundary \(b\), BICACHE performs an offline, one-time profiling procedure. Using the WildChat-4.8M dataset, it constructs requests spanning 100 uniform prefix ratios \(r \in \{0.01, \dots, 1.00\}\) with \(M=500\) samples each, recording the first-step cosine similarity at every layer. The safe depth \(b_i\) is logged where all layers \(\ell \le b_i\) satisfy \(\text{sim}_{\ell,1} \ge \tau\), and the average across samples yields the representative depth stored in lookup table \(\mathcal{T}\). In the serving phase, BICACHE identifies the shared prefix sequence \(p\), generates a deterministic 64-bit integer identifier using xxHash, and looks up the cached tensor block in hash table \(\mathcal{H}\). On a cache hit, cached prefix KVs for shallow layers \(\ell \le b\) are fetched in \(O(1)\) time, bypassing redundant projections across all \(s\) denoising steps. Unseen prefixes trigger a standard forward pass at step 1 to populate \(\mathcal{H}\), managed under a first-in, first-out (FIFO) cache eviction policy.

3. Deep-layer periodic refresh within individual requests

While cross-request reuse is unsafe in deep layers (\(\ell > b\)), completely recalculating prefix KVs at every step and layer remains computationally prohibitive. The authors observed that reusing a single step-1 snapshot across all 128 denoising steps leads to stale representations, dropping similarity to 0.93; however, introducing a periodic refresh interval \(\Delta\) restores deep-layer similarity to 0.96, matching the safe operating regime. BICACHE therefore formalizes deep-layer KV computation as:

\[\text{KV}_{\ell,t}^{\text{use}} = \begin{cases} \text{KV}_{\ell,t}^{\text{ref}}, & \ell > b, \, (t - 1) \bmod \Delta = 0 \\ \text{KV}_{\ell,t-1}^{\text{use}}, & \ell > b, \, \text{otherwise} \end{cases}\]

Selecting \(\Delta=16\) ensures that deep-layer KVs are refreshed only 8 times across 128 steps, eliminating over 85% of redundant deep-layer prefix projections while fully preserving generation fidelity.

A Worked Example

Consider serving LLaDA (\(L=32\) layers, output length \(g=256\), denoising steps \(s=128\)) on a GSM8K math request prepended with a real-world Grok-4 system prompt: 1. Prefix Identification & Profiling: The request has a system prompt length of 2080 tokens and a user prompt of 120 tokens, yielding a high prefix ratio \(r = 94.5\%\). Querying \(\mathcal{T}(0.945)\) yields a shallow boundary depth of \(b = 20\). 2. Shallow Inter-Request KV Reuse: Computing the 64-bit xxHash on the prefix tokens produces a cache hit in \(\mathcal{H}\). For layers 1 through 20 across all 128 denoising steps, the prefix KVs are fetched directly from \(\mathcal{H}\), bypassing all shallow prefix projections. 3. Deep Intra-Request Periodic Refresh: For layers 21 through 32, full reference KVs are recomputed only at step indices \(t \in \{1, 17, 33, \dots, 113\}\). For all intermediate steps (e.g., \(t \in [2, 16]\)), deep-layer prefix KVs are directly inherited from the prior step. This execution pipeline achieves an 82.8% throughput increase over the un-cached baseline, maintaining GSM8K accuracy virtually intact (55.5% versus 56.3%).

Key Experimental Results

Main Results

Evaluation was conducted on an NVIDIA B200 GPU (180 GB memory) using LLaDA (\(L=32, g=256, s=128\), batch size 1) under strict answer matching. BICACHE is compared against No caching, vLLM, and orthogonal intra-request accelerator Fast-dLLM.

Method ARC-C Thr. (tok/s) ARC-C Acc. (%) GPQA Thr. (tok/s) GPQA Acc. (%) MATH Thr. (tok/s) MATH Acc. (%) GSM8K Thr. (tok/s) GSM8K Acc. (%)
No caching 79.4 86.1 72.0 27.9 72.9 18.2 50.0 56.3
vLLM (cross-request all-layer) 113.3 (+42.7%) 0.1 (-86.0%) 99.7 (+38.5%) 0.7 (-27.2%) 108.4 (+48.5%) 0.0 (-18.2%) 94.2 (+88.4%) 30.9 (-25.4%)
BICACHE (Ours) 111.7 (+40.7%) 85.3 (-0.8%) 98.1 (+36.3%) 27.5 (-0.4%) 107.0 (+46.8%) 18.8 (+0.6%) 91.4 (+82.8%) 55.5 (-0.8%)
Fast-dLLM 85.1 84.3 82.1 27.0 76.5 16.4 51.7 63.1
BICACHE + Fast-dLLM 129.0 (+51.6%) 84.3 (+0.0%) 124.6 (+51.8%) 27.2 (+0.2%) 123.3 (+61.2%) 14.6 (-1.8%) 102.5 (+98.3%) 63.9 (+0.8%)

Ablation Study & Multi-Tenant Serving

Sensitivity sweeps on similarity threshold \(\tau\), refresh interval \(\Delta\), and sample count \(M\), alongside concurrent multi-tenant serving results (ShareGPT benchmark, Poisson arrival rate 4 req/s, batch size 8), highlight the robustness of the system:

Evaluation Dimension / Setup Throughput Primary Metric (Acc. / Latency) Analysis & Core Takeaways
Threshold Sensitivity (\(\tau=0.91\)) 111.9 tok/s ARC-C Acc: 64.0% Lower threshold overestimates shallow depth \(b\), corrupting deep bidirectional context
Threshold Sensitivity (\(\tau=0.97\), default) 111.7 tok/s ARC-C Acc: 85.3% Optimal inflection point: achieves maximum accuracy plateau with negligible throughput difference
Threshold Sensitivity (\(\tau=0.99\)) 111.5 tok/s ARC-C Acc: 85.0% Overly conservative threshold reduces \(b\), lowering throughput by 0.4% without accuracy gains
Refresh Interval (\(\Delta=8\)) 110.5 tok/s ARC-C Acc: 85.3% Frequent refresh preserves accuracy perfectly but incurs slight throughput penalty
Refresh Interval (\(\Delta=16\), default) 111.7 tok/s ARC-C Acc: 85.3% Optimal trade-off: throughput improves by 1.2 tok/s while accuracy matches \(\Delta=8\)
Refresh Interval (\(\Delta=64\)) 113.2 tok/s ARC-C Acc: 84.1% 4x larger interval yields only 1.3% throughput gain at the cost of 1.2% accuracy drop
Multi-Tenant Serving (No caching) 2.8 tok/s E2E Latency: 3081.0 s Severe serving bottlenecks under concurrent traffic without prefix caching
Multi-Tenant Serving (vLLM) 10.0 tok/s E2E Latency: 854.3 s High throughput gain but outputs suffer total accuracy breakdown
Multi-Tenant Serving (BICACHE) 9.7 tok/s E2E Latency: 884.5 s 3.5x higher throughput and 3.5x lower latency over baseline, matching vLLM speed without accuracy collapse
Multi-Tenant Serving (BICACHE + Fast-dLLM) 31.9 tok/s E2E Latency: 259.7 s 3.4x throughput increase and 3.6x latency reduction over Fast-dLLM alone

Key Findings

  • Eliminating the Dilemma of DLM Prefix Caching: Where standard vLLM leads to catastrophic collapse (slashing accuracy by up to 86.0%), BICACHE achieves near-identical throughput gains (up to 82.8% on GSM8K) while restricting the accuracy drop to an imperceptible 0.4%–0.8%.
  • Powerful Synergy with Intra-Request Acceleration: Fast-dLLM accelerates suffix generation via block-based diffusion, operating orthogonally to BICACHE's prefix reuse. Combining them yields up to a 98.3% throughput boost on GSM8K, exceeds 101.2% speedup under long generation settings (\(g=512\)), and cuts multi-tenant end-to-end latency from 944.3s to 259.7s.
  • Cross-Architecture Generalization & Micro-Perturbation Robustness: Profiling takes only 87.5 minutes offline and is required once per model. When minor prompt edits occur (modifying up to 50% of tokens in instructions/metadata), the similarity standard deviation is a negligible 0.014. Furthermore, on LLaDA-1.5, which uses preference optimization, BICACHE delivers 72.8%–161.6% throughput gains with accuracy differences under 4%.

Highlights & Insights

  • Decoupled Attention Sensitivity across Transformer Hierarchy: The paper uncovers a vital architectural property of bidirectional language models: shallow layers remain predominantly anchored to local/syntactic representations and are insensitive to suffix perturbations, whereas semantic context synthesis is concentrated in deep layers.
  • Prefix Ratio as a Principled Boundary Predictor: Rather than relying on expensive dynamic heuristics, BICACHE establishes a clean, mathematically proven relationship linking sequence prefix ratio directly to safe caching depth via attention leakage bounds.
  • Plug-and-Play Serving Integration: Because BICACHE operates purely as an attention-level KV retrieval and refresh policy without altering weights or generation algorithms, it natively integrates into production multi-tenant serving frameworks and stacks cleanly with orthogonal decoding optimizers.

Limitations & Future Work

  • Reliance on Exact Prefix Matching: Prefix retrieval relies on xxHash matching of the full prefix string. Sub-token variations or dynamic multi-turn turns that alter prefix ordering cause cache misses. Future research could investigate radix-tree indexing or token-level prefix chunking for partial overlap reuse.
  • One-Time Offline Profiling Cost: Profiling takes approximately 1.5 hours per model architecture. While non-recurring, future work could develop closed-form analytical models or lightweight runtime estimation heuristics to infer \(b\) on the fly.
  • Ecosystem Breadth: Experiments are anchored on LLaDA and LLaDA-1.5. As the discrete and continuous diffusion language model ecosystem expands, validating BICACHE across a wider spectrum of non-autoregressive architectures remains an important milestone.
  • vs vLLM / Prompt Cache (Autoregressive Caching): vLLM exploits causal mask invariance to reuse prefix KVs across all layers and steps; deploying it on DLMs destroys accuracy due to bidirectional pollution. BICACHE introduces prefix ratio-aware layer partitioning and periodic refresh, unlocking safe prefix caching for DLMs for the first time.
  • vs Fast-dLLM / dLLM-Cache / Elastic-Cache (Intra-Request DLM Acceleration): Prior DLM caching works optimize only intra-request step-wise redundancy. BICACHE addresses the orthogonal, workload-dominant inter-request shared prefix dimension, multiplying efficiency when combined with intra-request optimizers.

Rating

  • Novelty: ⭐⭐⭐⭐⭐ First framework to solve the fundamental shared prefix caching challenge in bidirectional diffusion language models with solid mathematical foundations.
  • Experimental Thoroughness: ⭐⭐⭐⭐⭐ Extensive evaluation across 4 competitive benchmarks, multi-tenant serving (ShareGPT), longer context (\(g=512\)), architectural transfer (LLaDA-1.5), and parameter ablations.
  • Writing Quality: ⭐⭐⭐⭐⭐ Lucid problem formulation, rigorous mathematical bounds, transparent and intuitive diagrams, and reproducible open-source release.
  • Value: ⭐⭐⭐⭐⭐ Essential building block for high-throughput, commercially viable deployment of diffusion language models.