PaperlayerView exact revision on arXiv

Source-linked AI summary

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, Haoran Li

arXiv:2610.18143v1cs.AI

TL;DR

In hybrid LLM serving, a matched prefix may not have usable recurrent state, so a blocked consumer can stop the scheduler’s queue scan. RadixFlow blocks that consumer while continuing to select feasible independent work. Across five hybrid models, it lowers latency and worker rounds with nearly unchanged reuse.

  • Problem

    In hybrid LLMs, matching a cached prefix does not ensure a branch can run because needed recurrent state may still be produced in the same worker round.

    Source: §1 · p. 1

  • Method

    RadixFlow separates prefix matching from state readiness, blocking a dependent consumer for recheck next round while continuing to select feasible independent branches.

    Source: §1 · p. 1

  • Results

    3% to 24% lower mean latency and 11% to 44% fewer worker rounds across five hybrid models, with nearly unchanged prefix reuse.

    Source: §1 · p. 2

  • Takeaways & Limitations

    A blocked consumer needs only a recheck in the next round; schedulers can continue selecting independent work without changing the native state check.

    Source: §6 · p. 8

    The evaluation focuses on candidate-conditioned prefill with one generated token under frozen model, budget, and arrival settings.

    Source: Limitations · p. 9

Abstract

from arXiv · show

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 \emph{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.

1 Introduction

Prefix reuse helps prefill-heavy serving, but in hybrid LLMs a matched prefix may not have usable state yet, allowing a blocked consumer to stop the scheduler’s scan. RadixFlow blocks only that consumer while continuing to select independent work; on five hybrid models, it reduces latency and worker rounds with almost unchanged reuse.

1 Introduction

  • Prefix reuse supports repeated documents, system prompts, and histories in prefill-dominated online workloads, but its benefit depends on how schedulers group work into rounds.Source: §1 · p. 1
  • In hybrid LLMs, a consumer may need recurrent state still being computed by a producer, and its allocation failure can end the waiting-queue scan.Independent work that fits the remaining budget may then be excluded, creating avoidable execution bubbles.Source: §1 · pp. 1–2
  • RadixFlow separates prefix matching from state readiness, blocking only the consumer while independent feasible branches continue entering the batch.It preserves native state checks and cache updates.Source: §1 · pp. 1–2
  • 3% to 24% lower mean latency and 11% to 44% fewer worker rounds on five hybrid models, with nearly unchanged prefix reuse.The latency range is reported for the five hybrid models; the round reduction is 11% to 44%.Source: §1 · p. 2

2 Related Work

Prior work addresses prefix caching and scheduling through distinct mechanisms. RadixFlow operates within a worker round, changing branch selection while preserving native order and state checks.

2 Related Work

  • Prefix-caching systems share KV pages and index exact prefixes, while hybrid caches retain recurrent components needed at reuse boundaries.Source: §2 · p. 2
  • Scheduling systems manage reuse, load, and waiting through request ordering or batch formation, and bounded dynamic batching motivates timer controls.Source: §2 · p. 2
  • RadixFlow changes which branches are selected within a round without changing native order or bypassing state reads.Kernel and tree-aware batching work motivates measuring per-round cost.Source: §2 · pp. 2–3

3 Problem Formulation

The formulation treats batch construction as online selection among arrived branches subject to prefix, state-readiness, and resource constraints. It defines avoidable execution bubbles as unused capacity that feasible arrived work could fill, and identifies prefix-stop scanning as a source of such bubbles.

3 Problem Formulation

  • Online batch construction selects feasible arrived branches that match the intended prefix, have usable resume-boundary state, and fit remaining resources.Source: §3 · p. 3

3.1 How a branch executes

  • A branch resumes through prefix lookup and a native state check; restoration precedes its resumed forward, and publication precedes dependent reuse.Source: §3.1 · p. 3

3.2 Streams, state, and rounds

  • A worker round is bounded by row and token budgets; the policy observes arrived inputs, and request completion is determined by its last branch.Round count and round cost determine service work, while arrivals and queueing determine when requests receive it.Source: §3.2 · p. 3
  • A hybrid reuse boundary requires KV, recurrent, and convolutional state; its longest token match can exceed its ready length while a producer is still computing state.The new state becomes available after execution.Source: §3.2 · p. 3
  • The native state check classifies work as READY when it is feasible, BLOCKED when a selected producer is still writing needed state, or OTHER for remaining outcomes.A READY branch must both have a usable boundary and fit the round.Source: §3.2 · p. 3
  • An avoidable execution bubble occurs when rows remain unused despite arrived work that the native check marks READY; unused rows alone do not establish one.A full token budget or an empty executable set can also leave rows unused.Source: §3.2 · p. 3

3.3 Where bubbles arise

  • Prefix-stop ends scanning at the first non-READY branch, so a blocked consumer can leave later READY work unscheduled.Continuing past the consumer helps when independent arrived work passes the native check and fits remaining capacity.Source: §3.3 · pp. 3–4
  • In the illustrated schedule, continuing past the consumer processes the same 12,970 tokens in four rounds instead of six; the four-round schedule meets the stated capacity bound.The figure also contrasts head-of-line blocking with continued scanning while leaving native state checks and cache updates unchanged.Source: §3.3 · p. 4, Figure 2 · p. 4

4 RadixFlow

RadixFlow separates prefix matching from state readiness, blocking only consumers of same-round dependencies so independent branches can still join the batch. Flexible admission controls when arrived branches become eligible for the scan.

4 RadixFlow

  • RadixFlow blocks only the consumer of a same-round dependency and continues selecting independent work, while retaining native state checks and cache management.A blocked consumer waits for a next-round recheck; OTHER outcomes retain native handling.Source: §4 · p. 4, §4.1 · p. 4

4.1 State-ready traversal

  • For fixed state and native order, RadixFlow preserves every branch selected by prefix-stop; with monotone readiness and no OTHER stop, continuing the scan removes avoidable bubbles.This is a fixed-round guarantee; stream-wide savings are measured separately.Source: §4.1 · pp. 4–5
  • Continuing the scan adds queue visits and repeats native state checks, with extra work growing linearly in inspected branches.Source: §4.1 · p. 5

4.2 Flexible admission

  • Admission uses a 5 ms deadline, releasing branches earlier when work is running, rows are full, or residual token demand fills the budget.The deadline is fixed across models rather than tuned on evaluation results; each branch is released independently of its request group.Source: §4.2 · p. 5

4.3 Fragmentation extension

  • RadixFlow+Frag defers a branch when a residual-budget split would shorten its next aligned segment, which can reduce fragmentation but may delay progress.The paper retains RadixFlow as the main method and tests RadixFlow+Frag as an ablation.Source: §4.3 · p. 5

5 Experiments

The experiments compare RadixFlow and scheduling ablations under a shared serving backend, finding lower hybrid-model latency with nearly unchanged reuse. They isolate traversal’s contribution and examine how round cost shapes the latency benefit.

5.2 Q1: Serving performance

  • Mean client latency falls 9.3%, 23.6%, 7.1%, and 3.1% across Qwen3.5-0.8B/4B/9B/27B and 12.0% on Nemotron-9B, with reused input within 0.03 percentage points of Radix.The Table 1 blocks cover 9,306 requests across three regimes and two input orders.Source: Table 1 · p. 6, §5.2 · p. 6

5.3 Q2: Admission and state-ready traversal

  • On Qwen3.5-27B, traversal cuts rounds 44% versus 1.6% for Flex; Nemotron gains chiefly from admission, while full-attention traversal adds little.The full-attention control uses 6,782 rounds with Flex and 6,746 with RadixFlow; Nemotron gains 27% from admission and another 8% from traversal.Source: Table 2 · p. 6, §5.3 · p. 7

5.4 Q3: Round savings and their cost

  • On Qwen3.5-27B, tokens per round rise 80%, host cost per thousand scheduled tokens falls from 183 to 175 ms, and total host-wrapper time falls 3.8%.The accounting separates savings from eliminated rounds from the cost shift in the remaining rounds.Source: §5.4 · p. 7, Figure 3 · p. 7
  • On Qwen3.5-9B, retained-round cost absorbs about 60% of gross credit, while p95 latency falls from 73.3 to 70.6 s.Round fullness improves, but the latency benefit reaches requests only partly and varies by model.Source: §5.4 · p. 7, Figure 4 · p. 8
  • +Frag lowers Qwen3.5-27B latency another 5.0% versus RadixFlow, with 3.6% fewer rounds and 1.66 percentage points more reuse.Deferring a shortened aligned fragment changes batch packing and cache boundaries encountered by later consumers.Source: §5.4 · p. 8
  • At sustained overload, queueing dominates client latency; traversal contributes little on full attention when the recurrent-state check is inactive.The evaluation uses four-branch reading-comprehension requests and compares five hybrid models with a Qwen3-8B full-attention control.Source: §5.1 · p. 5, §5.4 · p. 8

6 Conclusion

In hybrid LLM serving, a cache match alone does not make a branch runnable. RadixFlow blocks only a consumer waiting on same-round state and continues selecting independent work that fits.

6 Conclusion

  • RadixFlow blocks only consumers of same-round dependencies while continuing to select independent work that fits the batch.A blocked consumer waits for a recheck in the next round; the scheduler retains its native state check.Source: §6 · p. 8

Limitations

The evaluation focuses on candidate-conditioned prefill with one generated token under frozen model, budget, and arrival settings. It reports worker-call timing and decoded-output agreement.

Limitations

  • The evaluation covers candidate-conditioned prefill with one generated token under frozen model, budget, and arrival settings, reporting worker-call timing and decoded-output agreement.Load sweeps, production scheduling, and finer dependency traces extend beyond this setting.Source: Limitations · p. 9

Ethical Considerations

The appendix explains the method’s design choices, replay protocol, measurement conventions, and traversal model. It distinguishes prefix matching from state readiness and legal scheduling, and separates scheduling quantities from elapsed time.

A.1 From prefix matches to executable work

  • The design separates finding a prefix, having complete valid state, and placing work in a legal round; cached tokens, worker rounds, and elapsed time measure distinct things.Fewer cached tokens or rounds do not necessarily shorten completion time because of capacity, alignment, other requests, or dependencies.Source: §A.1 · pp. 10–11

A.2 Why not save a checkpoint at every branch?

  • Checkpointing every branch can require state copies and retention, while extra serial prefill can consume the time it aims to save; the method leaves checkpoint construction to the native backend.Rather than waiting for whole request groups, admission releases arrived work independently and state-ready traversal responds to a specific native rejection.Source: §A.2 · p. 11, §A.3 · p. 11

A.4 Why not minimize rounds alone?

  • Rounds with more rows or tokens can cost more, so RadixFlow measures round cost and client latency separately; fragmentation is tested as an ablation rather than presumed beneficial.The full-attention control helps distinguish gains from an inactive recurrent rule from admission gains.Source: §A.4 · p. 11

B Replay and Calibration Protocol

  • The replay uses shared-document, candidate-specific inputs with one generated token, isolates cache namespaces across policies, and rejects overlength inputs rather than silently truncating them.It uses the same 1551 questions per policy, three regimes, and two input orders.Source: §B.1 · p. 11, §B.2 · p. 11, Figure 5 · p. 12

B.2 Cache isolation and arrival traces

  • Configuration is calibrated on disjoint questions using native scheduling and then fixed; runs are paired within each model, and failed or partial arms are not filled from other runs.The Qwen series uses a common offered trace with forward and reversed assignments, while recording sender lateness under overload.Source: §B.3 · p. 12, §B.4 · p. 12, §B.2 · p. 12

C.1 Tokens and global rounds

  • Worker rounds count global invocations with scheduled work, while client latency, host-wrapper time, and CUDA intervals are distinct clocks and cannot be added interchangeably.A successful one-token response may lack a first nonempty text event; such missing times remain missing rather than being treated as zero latency.Source: §C.1 · pp. 12–13, §C.2 · p. 13, §C.3 · p. 13

D Full Stream Model and Traversal Properties

  • In the stream model, a boundary is ready only when every required state component is published and passes the native check; a feasible batch also respects row and token limits.A consumer cannot use state its producer is still computing, though an independent branch may join if capacity allows.Source: D Full Stream Model and Traversal… · pp. 13–14
  • For a fixed round, state-ready traversal preserves feasibility and selects a superset of the prefix-stop batch; under stated conditions, continuing past blocked branches leaves no avoidable bubble.The guarantee is for fixed state; across a stream, policies reach different states, so total rounds require measurement.Source: D Full Stream Model and Traversal… · p. 14

E Proofs

The appendix proves fixed-round properties of state-ready traversal and documents the native path, reproducibility checks, accounting, and saved-trace analyses. It also identifies limits on what the counters and capacity diagnostics can establish.

E Proofs

  • For a fixed round, RadixFlow preserves feasibility and includes the prefix-stop batch; when no other outcome ends the scan, continuing past blocked branches removes avoidable bubbles.The guarantee concerns a fixed state, while total round counts across a stream are measured separately.Source: E Proofs · p. 14

F.1 Native prefix-stop path

  • The evaluated native waiting loop ends its scan on allocation failure, including a same-round hybrid-state rejection; RadixFlow recognizes that dependency without changing other native paths.Blocked consumers remain registered and are woken for a later native state recheck.Source: §F.1 · pp. 14–15

G Anonymous Reproducibility Record

  • The anonymized reproducibility release is planned to include pinned revisions, hashes, frozen configurations, traces, counts, and token-accounting summaries, with logs scrubbed of credentials and machine-specific paths.The review manuscript omits identifying repository and machine details.Source: G Anonymous Reproducibility Record · p. 15

H Timing and Extension Protocol

  • Component profiling separates CPU lookup, selection, dispatch, GPU restoration, prefill, and publication while preserving overlap; load sweeps and wider branching remain extensions of the frozen replay.Source: H Timing and Extension Protocol · p. 15

I 27B Token-Accounting Ledger

  • The 27B ledger reconciles reported cache hits with scheduled intervals and records repeated work separately; RadixFlow overlap is 0.39% of scheduled tokens versus 0.14% for Radix.The traces identify repeated intervals and two reset prefixes, but attributing their cause to preemption would require native preemption events.Source: I 27B Token-Accounting Ledger · p. 15

J Saved-Trace Mechanism and Cost Analysis

  • Saved-trace analyses verify joined rounds and budgets, and Figure 6 compares round and latency reductions across reuse regimes; the largest latency gain need not match the largest round reduction.The figure pools both input orders and uses a shared percentage scale.Source: J Saved-Trace Mechanism and Cost… · p. 15, Figure 6 · p. 16

J.1 Batch shape and cost association

  • On Qwen3.5-27B, mean registration-to-first-selection time falls by 7.22 s while the remaining interval grows by 1.26 s; on Qwen3.5-9B, the changes are a 2.43 s reduction and a 0.35 s increase.The remaining interval includes waiting as well as execution and does not isolate restoration cost.Source: §J.1 · p. 16

J.2 Capacity gap and counter scope

  • The capacity bound is policy-specific rather than a shared optimum, and unused capacity does not by itself establish avoidable bubbles or GPU idleness; cumulative state-check counters do not identify per-request blocked or recovered rows.Separating scale effects would require per-round dependency and recovered-row traces; the available counters include smoke traffic and repeated scans.Source: §J.2 · p. 16, §J.3 · p. 16

J.4 Dataset and order sensitivity

Both dataset assignment orders favor RadixFlow on each hybrid model, while the full-attention control shows small order-dependent effects. The related-work discussion distinguishes RadixFlow’s within-round eligibility change from approaches that alter state retention, request placement, or batch computation.

J.4 Dataset and order sensitivity

  • Article-level sharing makes arrival order affect both realized reuse and the executable set, so both orders remain in the primary comparison.Global rounds are reported at stream level because mixed batches cannot be assigned uniquely to QuALITY or RACE.Source: §J.4 · pp. 16–17
  • Both input orders favor RadixFlow on each hybrid model, while the full-attention control has small effects that change sign across orders.The two orders are different input assignments, not independent timing repetitions.Source: §J.4 · p. 17

K Extended Related Work

  • RadixFlow targets eligibility within batch construction, distinguishing published hybrid state from same-round dependencies while retaining native request order.This differs from state-retention policies and from methods that place or reorder requests.Source: K Extended Related Work · p. 17
  • Cache-transfer and batch-computation methods change reuse availability or execution cost, whereas RadixFlow schedules work remaining after the native state check.The discussion also contrasts dynamic batching and kernel or layout improvements, whose per-round cost is measured separately.Source: K Extended Related Work · pp. 17–18

L Additional Waiting and Capacity Analysis

The analysis shows that fewer rounds do not translate uniformly into lower latency: round filling, per-round cost, and workload regime matter. It also reports tail-latency, capacity-bound, branch-interval, and output-agreement results, with limitations on interpreting some comparisons.

L Additional Waiting and Capacity Analysis

  • In full-attention Qwen3-8B, the recurrent check never fires, and Radix+Flex and RadixFlow have almost the same round count in every stream; their aggregate reduction versus Radix is about 27%, with little change in mean latency.Source: L Additional Waiting and Capacity… · p. 18
  • Admission removes 27% of Nemotron-9B rounds, and traversal removes another 8% relative to Radix+Flex; rows per round rise from 2.91 to 3.99 to 4.38 out of 16.The pattern is consistent with admission filling sparsely occupied rounds, while nearly constant host cost lets fewer rounds translate more directly into time savings.Source: L Additional Waiting and Capacity… · p. 18
  • On Qwen3.5-9B, the cost shift absorbs about 60% of the gross credit from eliminating rounds, while Nemotron-9B per-round cost changes little.The shape-adjusted analysis similarly attributes much of Qwen variation to batch shape, with smaller residual policy associations.Source: L Additional Waiting and Capacity… · pp. 18–19
  • Qwen3.5-9B p95 and p99 fall from 73.3 to 70.6 s and 75.2 to 72.6 s; Nemotron-9B tails fall from 15.8 to 13.3 s and 18.8 to 16.1 s.The full-attention control has nearly unchanged tails.Source: L Additional Waiting and Capacity… · p. 19
  • RadixFlow reaches 1.13–1.14 times the capacity-only bound on Qwen3.5-27B, but the ratio is 1.44 in cold and 4.18 in reuse traffic on Qwen3.5-9B.The bound relaxes alignment, arrival-time, and state-dependency constraints, so it is not an attainable online schedule.Source: L Additional Waiting and Capacity… · p. 19

M Worker Cost and Output Audit

  • Across 37,224 paired branches per model, decoded first-token agreement with Radix ranges from 98.477% to 99.995%; native branch intervals are not directly additive to logical client latency.The second branch interval includes subsequent rounds, intervening waiting, and completion processing.Source: M Worker Cost and Output Audit · p. 19, Table 8 · p. 19, Table 7 · p. 19

N Baseline Audit and Replay Sensitivity

The audit compares six policies on a common experimental backend and examines timer eligibility, replay sensitivity, and operating conditions. Results vary by input assignment, while single-run conditions and untested asynchronous scheduling bound interpretation.

N Baseline Audit and Replay Sensitivity

  • Radix is the native-selection arm of the common backend, so paired differences measure scheduling on that backend rather than stock vLLM+APC.A stock comparison would remove the overlay while retaining the same model, tokens, arrival trace, and resource settings.Source: N Baseline Audit and Replay Sensitivity · p. 20
  • Timer5/10 changes effective eligibility by releasing peers during the held-list test, allowing later branches to execute before earlier held ones.An order-preserving control would snapshot eligibility before selection and record overtakes and deferral counts.Source: N Baseline Audit and Replay Sensitivity · p. 20
  • The 27B Timer10 tail split appears within every stream and both orders, with p50 of 10.53–11.80 s and p99 of 910.83–1104.77 s.Eligibility changes are consistent with the split, but attributing starvation would require per-request deferral events.Source: N Baseline Audit and Replay Sensitivity · pp. 20–21
  • The 4B mixed-stream mean reduction is 61.2% and persists in both assignment orders, with reductions of 68.0% forward and 54.0% reverse.The orders are not independent timing repetitions, and the benefit’s magnitude changes with workload order.Source: N Baseline Audit and Replay Sensitivity · p. 21
  • The 27B replay rate of 5 requests/s exceeds its observed drain-inclusive completion rate near 0.74 requests/s, indicating sustained overload rather than a throughput-ceiling estimate.Post-send and offered-to-completion latency are separate outcomes, and the plotted configurations do not establish a causal model-size trend.Source: N Baseline Audit and Replay Sensitivity · p. 21
  • Each frozen condition is run once, so forward/reverse comparisons measure assignment sensitivity rather than run-to-run variance; asynchronous scheduling requires separate matched runs.For asynchronous dependencies, the limitation calls for producer-generation and completion-fence identification rather than a synchronous step number alone.Source: N Baseline Audit and Replay Sensitivity · p. 21

Related papers

Loading 2610.18143v1…