RadixFlow: Filling Execution Bubbles in Prefix-Cached Hybrid LLM Serving

Huihao Jing; Wenbin Hu; Shaojin Chen; Haochen Shi; Haoyu Huang; Sirui Zhang; Yuxuan Liu; Zhongwei Xie

cs.AIOct 13, 2026

RadixFlow: Filling Execution Bubbles in Prefix-Cached Hybrid LLM Serving

Authors: Huihao Jing, Wenbin Hu, Shaojin Chen, Haochen Shi, Haoyu Huang, Sirui Zhang, Yuxuan Liu, Zhongwei Xie,

Organizations: HKUST

Abstract

Prefix reuse improves LLM inference by sharing the KV cache of common prompt prefixes. This helps only if the scheduler can execute a matched branch in the current worker round. Schedulers assume that a matched prefix is ready, which holds for full attention but fails for hybrid LLMs. There, a branch (the consumer) may need recurrent state that another branch (the producer) is still computing in the same round. The native scheduler stops its waiting-queue scan at this blocked consumer, and the resulting head-of-line blocking creates execution bubbles: idle batch slots that independent work could fill. We introduce RadixFlow, which decouples prefix matching from state readiness. Its state-ready traversal turns a global scan barrier into a local wait: only the consumer is blocked until the next round, while feasible independent branches keep filling the batch under the native state check. On five hybrid models, RadixFlow lowers mean latency by 3% to 24% and worker rounds by 11% to 44% at almost unchanged reuse. On the larger Qwen3.5 models, ablations show that most of the gain comes from traversal, which adds little on a full-attention control. Heavier rounds limit how much of this saving reaches latency.

Figures & tables

Figure 1: Consumer

A

waits for

P

, while independent

D

can still enter the round. Both panels share the same prefix structure and fifteen work fragments. The baseline stops at consumer

A

, whose state depends on producer

P

; RadixFlow blocks only

A

and keeps scanning. Blue outlines mark first-round selections, dashed cells are empty, and shaded lengths show token load. Blocked consumers are woken for a recheck in the next round. These idealized schedules process the same 12,970 tokens in six versus four rounds.

Figure 2: RadixFlow changes selection, not native state checks or cache updates. A checkmark selects feasible work for

\mathcal{B}_{t}

; a pause blocks a consumer with a same-round dependency in the wait queue

D_{t}

, and a cross preserves native handling. Solid state components are published. The outlined recurrent component is still in flight and is not part of

\mathcal{C}_{t}

; blocked consumers are woken for a recheck in round

t+1

. The queue inset contrasts head-of-line blocking with continuing past the blocked consumer.

Qwen3.5-0.8B $S{=}16$ , $T{=}8192$ , 5.0 req/s
Method	Latency (s) $\downarrow$	Replay (req/s) $\uparrow$	Rounds $K$ $\downarrow$	Reuse (%) $\uparrow$
Radix	0.256	4.806	19,803	81.362
Radix+Timer5	0.260	4.805	19,371	81.367
Radix+Timer10	0.264	4.805	19,181	81.373
Radix+Flex	0.249	4.805	18,409	81.364
RadixFlow	0.232	4.806	17,610	81.366

Table 1: RadixFlow lowers mean client latency on the hybrid models while preserving almost the same reused input. The first three methods are baselines; the last three are our ablation, main method, and extension. Each block covers 9306 requests across three regimes and two orders. Replay throughput divides completions by arm wall time, including arrivals and drain; it is not a saturation limit. Bold marks the best latency, round count, and reuse. FA denotes full attention.

Figure 3: Round savings and latency gains differ across the measured configurations. Left: reductions relative to Radix. Right: blue is net host-time credit and orange is the cost shift of remaining rounds; together they equal the gross round credit under Equation 2 . The panels share model order.

Figure 4: (a)–(c) Round fullness: RadixFlow shifts rounds toward fuller budgets; rightward is better. (d)–(f) Request latency: the benefit reaches requests only partly and varies by model; leftward is faster. Curves pool three regimes and two orders per model. Latency is measured after submission and displayed through the largest p99 among the three policies.

Model	Rows / round $\uparrow$			First selection (s) $\downarrow$
	Radix	RadixFlow	Gain (%)	Radix	RadixFlow	Reduction (%)
Qwen3.5-0.8B	3.63	4.10	12.9	0.057	0.049	14.0
Qwen3.5-4B	5.42	7.31	34.9	12.576	9.273	26.3
Qwen3.5-9B	6.61	10.02	51.6	25.682	23.255	9.5
Qwen3.5-27B	6.51	12.11	86.0	160.538	153.314	4.5
Nemotron-9B	2.91	4.38	50.5	1.898	1.582	16.6

Table 2: Denser batches accompany earlier selection on hybrids. First selection measures registration-to-selection waiting; percentage changes use displayed values. See Appendix M for output sensitivity.

Appendix figures & tables11 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 5: Frozen budgets and matched inputs isolate the scheduling comparison within each model. (a) Native-only calibration fixes the row and token budgets before evaluation. Each policy receives the same 1551 questions in three regimes and two input orders. (b) Sender lag precedes actual submission; client latency starts at submission. The timeline is schematic, with no time scale.

Policy	Overlap	Reset	Total extra
Radix	66,944	0	66,944
Radix+Timer5	49,584	0	49,584
Radix+Timer10	53,760	512	54,272
Radix+Flex	48,864	0	48,864
RadixFlow	182,384	0	182,384
RadixFlow+Frag	186,096	0	186,096

Appendix

Table 3: Additional scheduled tokens in the 27B replay. Worker calls and token totals are kept rather than deduplicated.

Figure 6: Round reductions and latency gains respond differently to the reuse regime. Each cell compares RadixFlow with Radix on the same model and stream, pooling both input orders. Blue indicates a reduction; orange indicates a regression. The panels use the same percentage scale; cold prevents sharing across questions, not within one question. Values summarize the frozen replays in Table 4 .

Model	Stream	Radix $K$	Flex $K$	RadixFlow $K$	Latency reduction (%)	$K/L_{\mathrm{cap}}$
Qwen3.5-0.8B	Cold	6,849	6,563	6,152	7.1	3.33
	Mixed	6,603	6,101	5,884	8.7	3.94
	Reuse	6,351	5,745	5,574	13.2	3.88
Qwen3.5-4B	Cold	4,477	4,382	2,753	10.7	1.49
	Mixed	3,866	3,805	2,905	61.2	2.56
	Reuse	5,081	4,755	4,488	12.6	7.71

Appendix

Table 4: Regime analysis, pooling both orders. Latency reduction compares RadixFlow with Radix. Flex denotes Radix+Flex.

L_{\mathrm{cap}}

sums the separate capacity bounds for the two orders using RadixFlow’s observed work. Cold prevents sharing across questions, not within a question.

Model	Policy	p50 (s)	p95 (s)	p99 (s)	Offered latency (s)
Qwen3.5-0.8B	Radix	0.217	0.503	0.767	0.256
	Radix+Timer5	0.225	0.512	0.842	0.261
	Radix+Timer10	0.227	0.526	0.828	0.265
	Radix+Flex	0.210	0.521	0.798	0.249
	RadixFlow	0.201	0.455	0.630	0.232
	RadixFlow+Frag	0.200	0.443	0.606	0.228

Appendix

Table 5: Latency distribution and mean sender lag on all measured requests. The last two columns are means, not tail quantiles. The offered rate differs between Qwen and Nemotron-9B.

Model	Tokens/round		Rows/round		$\delta$ (ms)	$R^{2}$
	Radix	RadixFlow	Radix	RadixFlow
Qwen3.5-0.8B	1401	1575	3.63	4.10	0.51	0.328
Qwen3.5-4B	2173	2871	5.42	7.31	2.70	0.911
Qwen3.5-9B	2739	4060	6.61	10.02	3.05	0.957
Qwen3.5-27B	3998	7208	6.51	12.11	18.41	0.997
Nemotron-9B	2482	3701	2.91	4.38	-0.61	0.238

Appendix

Table 6: Batch-shape changes and descriptive host-cost regression. Separate fits are used for each model.

Model	Registration to first selection (s)		After first selection (s)
	Radix	RadixFlow	Radix	RadixFlow
Qwen3.5-0.8B	0.057	0.049	0.120	0.124
Qwen3.5-4B	12.576	9.273	0.373	0.528
Qwen3.5-9B	25.682	23.255	0.664	1.013
Qwen3.5-27B	160.538	153.314	2.457	3.718
Nemotron-9B	1.898	1.582	0.347	0.396

Appendix

Table 7: Mean native branch intervals on all 37,224 measured branches per policy. First selection is the first scheduler selection, not GPU execution start. The second interval includes subsequent rounds, intervening waiting, and completion processing. These native branch intervals are not directly additive to logical client latency.

Figure 7: Earlier selection offsets a longer interval after selection on the hybrid models. Points show the RadixFlow-minus-Radix change in each interval, normalized by the sum of the two Radix mean intervals. Labels give absolute changes in seconds, calculated from the rounded means in Table 7 . The later interval includes intervening waiting and completion processing as well as execution; these are native branch intervals, not logical client latency.

Figure 8: Latency improves in both input orders and both datasets on every hybrid model. Points show the percentage reduction in mean client latency for RadixFlow relative to Radix, pooling the other conditions. Connectors pair the two strata within a model; they are not uncertainty intervals. Forward and reverse are different input assignments within the frozen evaluation.

Model	Decoded agreement (%)
Qwen3.5-0.8B	98.477
Qwen3.5-4B	99.850
Qwen3.5-9B	99.680
Qwen3.5-27B	99.995
Nemotron-9B	99.688
Qwen3-8B (FA)	99.441

Appendix

Table 8: Exact decoded first-token agreement between RadixFlow and Radix on 37,224 paired branches per model.

Model	Radix	Timer5	Timer10	Flex	RadixFlow	+Frag
Qwen3.5-0.8B	52.95	52.99	53.09	53.64	54.24	53.94
Qwen3.5-4B	82.63	83.26	84.14	83.42	92.95	91.69
Qwen3.5-9B	112.85	116.78	116.67	113.38	145.50	144.16
Qwen3.5-27B	729.94	829.01	836.45	738.22	1262.95	1246.66
Nemotron-9B	53.06	53.82	53.10	53.69	53.87	54.31
Qwen3-8B (FA)	26.60	27.55	27.73	27.42	27.54	27.42

Appendix

Table 9: Mean host-wrapper milliseconds per nonempty global worker round, retained for all six methods.

LLM Serving

Large language model serving studies how to deliver model responses with low latency, high throughput, and efficient use of compute and memory.

See all 211 papers

Requests of a Feather Must Flock Together: Batch Size vs. Prefix Homogeneity in LLM Inference
May 7, 2026Saksham Rathi, Preeti, Mythili VutukuruLLM Inference Scheduling KV-Cache Management
Indian Institute of Technology Bombay, Mumbai, India
Just Let Linear States Forget the Distant Past: Prefix Caching via Suffix Replay for Hybrid LLMs
Sep 27, 2026Yirui Liu, Ruoling Qi, Xuaner Wu +6Long-Context Language Model Inference LLM Inference Acceleration
Institute of Artificial Intelligence, China Telecom (TeleAI) China · Shanghai Jiao Tong University · Individual Researcher +1
Sparse Prefix Caching for Hybrid and Recurrent LLM Serving
Apr 17, 2026Mikhail Shirokikh, Sergey NikolenkoLLM Serving KV-Cache Management

May 7, 2026J/K move · Enter open · S save

Requests of a Feather Must Flock Together: Batch Size vs. Prefix Homogeneity in LLM Inference

Saksham Rathi, Preeti, Mythili Vutukuru

Indian Institute of Technology Bombay, Mumbai, India

LLM Inference Scheduling KV-Cache Management LLM Inference Acceleration

Open paper AskPDF arXiv

Auto-regressive token generation in large language models is memory-bound because it requires "attending to" key and value tensors (KV cache) of all previous tokens. Prior work aims to improve the efficiency of this decode process by batching multiple requests together, and maximizing batch size subject to GPU memory constraints. The key observation of our work is that with prefix-sharing workloads, smaller, prefix-homogeneous batches - where all requests share a common prefix - can achieve higher decode throughput than larger, heterogeneous batches, due to better spatial and temporal locality during KV cache accesses. However, current prefix-aware schedulers maximize prefix reuse within a batch only to reduce KV cache memory footprint, but do not stop batch formation at smaller homogeneous batches that could have performed better. Further, we show that shared prefix detection in existing schedulers relies on radix-tree traversals, incurring substantial CPU overhead that is often comparable to GPU execution time. This paper presents Feather, a prefix-aware scheduler that uses reinforcement learning (RL) to learn the optimal tradeoff between batch size and prefix homogeneity. We also introduce Chunked Hash Tree (CHT), a lightweight data structure that enables fast prefix detection and efficient request selection for the RL scheduler, avoiding expensive tree traversals. We integrate Feather into vLLM and SGLang, and our evaluation shows that Feather achieves 2-10X higher end-to-end throughput as compared to existing schedulers by reducing the total number of KV cache accesses, while doing no worse than the status quo when there insufficient prefix sharing.

Abstract

LLM Serving

Explore similar work

Requests of a Feather Must Flock Together: Batch Size vs. Prefix Homogeneity in LLM Inference

Just Let Linear States Forget the Distant Past: Prefix Caching via Suffix Replay for Hybrid LLMs

Sparse Prefix Caching for Hybrid and Recurrent LLM Serving