Modern open models are hybrids: most layers are linear-attention (Gated DeltaNet, GDN) layers carrying a small fixed-size recurrent state instead of a growing key-value (KV) cache. This makes ordinary decoding memory-efficient, but hurts speculative decoding. To verify a batch of draft tokens and then roll back the rejected ones, today's systems snapshot the full recurrent state at every draft position for GDN layers, and those snapshots cannot be shared across branches of a draft tree, so a wide, high-acceptance tree becomes memory-infeasible. We remove the snapshots. Using a tree-structured WY transform of the gated delta rule, we compute every draft node's output with a single triangular solve and reconstruct only the one accepted state on commit, storing a small pseudo-value matrix instead of per-node states; the derivation depends only on the gated delta rule, not on any other architectural detail. In serving benchmarks on two scales of one hybrid model family (Qwen3.5 35B and 397B) this cuts speculative recurrent-state memory and KV-cache pressure at essentially identical acceptance length, turning the freed HBM into higher throughput and much lower time-to-first-token (TTFT) wherever memory binds, and costing a few percent where it does not. For tree width the same memory buys affordability: a wider, higher-acceptance draft becomes possible, though not yet a throughput win.
Figures & tables
Table 1
Appendix figures & tables6 assets
Supplementary material from the paper’s appendix.
Appendix
conc.
tput
KV red.
TTFT
TPOT
b
Qwen3.5-35B-A3B , gmu 0.75
1
0.95
2.32
1.09
0.94
1.00
8
0.98
2.44
1.00
1.00
1.00
32
1.00
2.45
1.01
0.99
1.00
64
1.00
2.48
0.94
1.00
1.00
128
1.02
2.43
0.99
1.02
1.01
Appendix
Table 3: The higher memory budgets, same axes and orientation as Table 2 . At 397B the knee appears only at 0.75 /256. Wherever b reads 1.00 the freed memory is real but unspent, as discussed in Section 5 .
Ours
ReplaySSM
storeall
TreeWY
storeall
ReplaySSM
peak running requests
151.1
238.2
153.6
223.9
output tok/s
8469
10094
8250
11357
mean TPOT (ms)
16.4
21.2
17.0
17.6
p99 TTFT (ms)
8167
2746
8965
2958
ratio vs own baseline, and the batch ÷ cost check
Appendix
Table 4: Why the ratios differ, decomposed at 256 concurrency (Qwen3.5-35B-A3B, all 15 points: 5 workloads (ShareGPT, spec-bench, synthetic balanced-chat, generation-heavy, summarize-heavy) × 3 gmu ; BurstGPT excluded, its own independent variable). Geomeans of the raw values over the 15 points first, then each method’s ratios to its own baseline and the batch ÷ cost check. Both methods admit essentially the same work: 238 vs 224 peak running requests, and at gmu 0.6 per workload they are indistinguishable (253/255, 254/255, 256/256, 256/256, 109/107 for ShareGPT/spec-bench/balanced-chat/generation-heavy/ summarize-heavy), because both simply reach the offered concurrency once the snapshots are gone. TreeWY’s larger admitted batch ratio below ( 1.577 vs. 1.458 ) is therefore a denominator artifact: its own baseline happened to admit slightly fewer at gmu 0.6 (92 vs 97 on balanced-chat, 61 vs 63 on summarize-heavy). What separates the two is per-token cost, and once both are saturated and decode-bound the throughput ratio is just batch÷cost , which closes to within 3% for both. So at this operating point the memory mechanism is a tie and the whole difference is per-step efficiency.
Output tput.
Peak KV
p99 TTFT
Per-token
concurrency
gain ↑
reduction ↑
speedup ↑
speedup ↑
ours / Replay
ours / Replay
ours / Replay
ours / Replay
1
0.94 / 1.06
2.36 / 2.15
1.00 / 0.98
0.94 / 1.07
8
0.99 / 1.08
2.43 / 2.26
0.87 / 1.20
1.00 / 1.07
32
1.00 / 1.11
2.45 / 2.29
1.03 / 0.99
0.99 / 1.11
64
0.99 / 1.17
2.46 / 2.29
0.96 / 1.01
0.99 / 1.17
Appendix
Table 5: The same load axis for both methods (Qwen3.5-35B-A3B), each normalised to the storeall baseline from its own vLLM build, so the two columns are comparable even though the builds are not. Each row is a geomean over the 15 points ( 5 workloads ×3 gmu ) at that concurrency. Per-token speedup is based on mean TPOT. ReplaySSM leads on throughput at every load, and the gap is already present where neither method is admitting anything extra (batch 1.00 , loads 1–64), which is what identifies it as per-step cost rather than a memory effect. Past the knee the two converge on the memory-driven columns: at 256 concurrency the peak-KV reduction is nearly equal ( 1.56 vs. 1.57 ), i.e. both free the same headroom, and Table 4 shows they spend it the same way ( 238 vs. 224 peak running requests). On the BurstGPT arrival-rate sweep at 64 req/s the p99 TTFT improvements are 10.72× and 10.20× respectively. The per-token column is the clearest read on per-step cost: ReplaySSM leads it at every load, and Table 4 decomposes the 256-concurrency point.
Figure 1: Peak KV-cache usage (fraction of pool) vs. offered load (generation-heavy workload), per model and GPU memory utilization ( gmu ). The snapshotting baseline ( storeall ) hits the 100% ceiling early and must then queue the requests it cannot fit; TreeWY uses about 2× less of the KV pool at the same load, until it admits more requests. That freed capacity buys the admission, throughput and TTFT wins (Fig. 2 ).
Figure 2: p99 time-to-first-token (TTFT) vs. offered load (generation-heavy workload). As concurrency rises, the snapshotting baseline’s KV pool saturates and it must queue requests, so its TTFT blows up (log scale): at 256 concurrency it is up to ∼30× (35B, utilization 0.75) and 26× (397B, utilization 0.75) worse than TreeWY. The largest gap over the whole sweep, 40× ( 683 vs. 27489 ms), is at 128 concurrency (35B, utilization 0.6), where the baseline saturates but TreeWY still does not. The gap closes only when memory is slack (397B, utilization 0.9).
Figure 3: treewy / storeall ratios over all 175 matched points (the concurrency sweeps of Tables 2 and 3 plus BurstGPT), split by whether the baseline had run out of KV headroom at that point, the same partition as Appendix B . Open markers are the headroom control: every metric except KV usage sits within a few percent of parity there. Filled markers are where the freed HBM is actually spent: at 35B (31/105 points memory-bound) TreeWY reaches 1.15× throughput, 2.94× lower p99 TTFT and 1.17× lower mean end-to-end latency at 1.60× more KV headroom, for a 0.83× per-token cost; 397B ( 17/70 points memory-bound) shows the same shape at smaller magnitude ( 1.06× throughput, 1.66× lower p99 TTFT, 1.63× more KV headroom, 0.95× per-token cost), since its sweep reaches fewer points past the knee. This is the single figure that makes the paper’s central qualifier legible at a glance: the win is not a fixed multiplier, it is conditional on memory pressure, and averaging over both regimes (as a single headline number would) hides exactly that.
Tree speculative decoding for recurrent-hybrid language models requires each accepted path to maintain consistent recurrent state, convolution history, and attention caches. We present LumoTree, a GPU serving design that coordinates verification and commitment through a shared tree descriptor. The verifier processes independent paths in parallel and reuses recurrent state tiles across local updates. Boundary states connect dependent paths. Accepted-path replay publishes the selected continuation into native running state, alongside coordinated convolution gathering and attention-cache remapping. Fused selection, device-resident acceptance, graph replay, and tree-aware attention integrate this organization into the serving cycle. The design separates temporary branch computation from persistent request state while retaining native prefix-cache interfaces. We evaluate numerical behavior, serving performance, and coding-agent outcomes on NVIDIA DGX Spark.
Speculative decoding (SD) accelerates large language model inference by leveraging a draft-then-verify paradigm. To maximize the acceptance rate, recent methods construct expansive draft trees, which unfortunately incur severe VRAM bandwidth and computational overheads that bottleneck end-to-end speedups. While dynamic-depth pruning can reduce this latency by removing marginal branches, it also discards potentially valid candidates, preventing the acceptance rate from reaching the upper bound of dense trees. In this paper, we identify a critical opportunity in resource allocation: the transition from dense to pruned drafting frees up significant computational budget. To break this Pareto tradeoff, we introduce Graft, a compensation framework that couples pruning and retrieval as mutually reinforcing operations. Pruning supplies sufficient budget for retrieval, while retrieval compensates for pruning-induced coverage loss and recovers accepted length. By employing a sequential `prune-then-graft' mechanism, Graft attaches highly predictive retrieved tokens into positions opened by pruning, filling the topological gaps with near-zero overhead. Graft is entirely training-free and lossless. Comprehensive evaluations show that Graft establishes a new Pareto frontier across practical deployment settings, including short-context generation, long-context generation, and large-scale models. On short-context benchmarks, it achieves up to 5.41× speedup and improves average speedup over EAGLE-3 by up to 21.8% on the large-scale Qwen3-235B. We also provide a preliminary exploration of applying Graft to the DFlash-style block drafting paradigm, offering initial evidence and insights for extending grafting beyond autoregressive draft trees.
Yuhao Shen, Tianyu Liu, Xinyi Hu +9
1Zhejiang University · 2Qwen Applications Business Group of Alibaba · University of Science and Technology of China
We investigate the expressive power of hybrid recurrent-attention decoders, a class of architectures used in recent open-source language models such as Qwen3-Next and its successors. These models combine Gated Attention heads with recurrent Gated DeltaNet heads. Is there a formal advantage, in terms of model expressivity or efficiency, to such a hybrid architecture? We show that there is. We define parity-conditioned retrieval task and show that under constant-precision assumption, a Qwen-style hybrid of Gated DeltaNet and Gated Attention solves this task with a constant scratchpad, or equivalently O(1) chain-of-thought steps. In contrast, no similar solution exists for pure Gated DeltaNet models, while pure Gated Attention requires at least a polynomial scratchpad.
Tomasz Steifer
Centre for Credible AI Warsaw University of Technology Rektorska 4, Warszawa 00-614, Poland