Agentic LLM workflows decide their execution paths at runtime. Downstream computation may be predictable, or may have run before, yet it cannot begin until the model or the user resolves the branch. We call this serialization the branch-resolution barrier. Caching alone does not hide it: the key that identifies a reusable result is not known until then. In this paper, we propose DynBranch, which makes an unresolved branch addressable before it resolves. Its stable coordinate lets candidate subgraphs run during resolution and completed subgraph results be reused across later requests. A two-level controller admits this work when its expected benefit exceeds the load price. DynBranch sits at the model-API boundary and requires no changes to agent harnesses or model execution engines. Across four agentic workloads with Qwen3-32B on 4x H200 GPUs, DynBranch reduces mean latency by up to 32% over each workload's strongest prior system and by 46-66% against a no-reuse floor, while preserving workflow results. The benefit persists across backbone families and on a commodity Qwen3-8B/RTX 4090 deployment.
Figures & tables
Figure 1. Predicted subgraphs fill during the shaded resolution window; each candidate’s status is printed beside it. (a) independent top- K . (b) exclusive route. Two timelines compare branch promotion policies. In the human-wait case, the offered candidates A, B, and C fill independently: A is used after the click, completed B is kept as a reusable shadow, and unfinished C is discarded. In the LLM-decode case, emission of h1 commits its branch and cancels h2.
Figure 2. Opportunities for early execution (C2) and cross-request reuse (C1), subject to available serving capacity (C3). Upright figures are from prior work; italic figures are our own measurements with speculation disabled. A funnel narrowing downward through four stages — agent work, the serialized barrier, fillable, reusable — each annotated with a prior-work measurement and the corresponding measurement on our own workloads, above a bar marking the spare serving capacity that admission prices.
Figure 3. Four representative workloads. Shaded boxes are resolution windows; dashed boxes are candidate work; the heavy-outlined box is a subgraph that recurs across requests. Italic labels differ from Routing . Four workload panels. Routing resolves a bounded handler choice during router decode and then runs the selected executor; ReAct predicts an open-vocabulary retrieval entity inside a per-hop loop; Sub-Agent plans which sub-agent to run, and the chosen one's retrieve-to-read subtask can recur across requests before the synthesis step; HCI fills independently offered continuations during user wait.
Figure 4. Resolution windows and downstream execution times; bars show p50, whiskers p25–p75. † Normalized by post-click execution, not wall-clock. Horizontal paired bars compare the median branch-resolution window and downstream execution time for Routing, ReAct, Sub-Agent, and HCI, with interquartile whiskers and each workload's overlap share.
Figure 5. (a) Share of MuSiQue questions that repeat an earlier sub-topic, and of sub-topic mentions that are repeats, as the stream grows. (b) Slowdown of a canonical request as fills grow in number and context. Panel a plots, as a MuSiQue question stream grows, the share of questions that repeat an earlier sub-topic and the share of sub-topic mentions that are repeats. Panel b plots canonical decode slowdown as either the number of co-resident fills or the context each one holds increases.
Figure 6. Lifecycle of a speculative branch result. Lanes are components, time runs left to right; ✗ marks the discarded loser. A four-lane timeline with agent, \sys{}, engines, and stores lanes and time running left to right. In the first panel a request opens a branch; \sys{} proposes and prices candidates, whose admitted fills execute on the engines concurrently with the canonical decode that names the stage, for the whole window in which the agent is blocked. The completed fill becomes an invisible shadow in the stores and the losing candidate is reclaimed. When the decode resolves, the selection returns to the agent, whose stage request authorizes the matching shadow; it is promoted and consumed to answer without further engine work, marked by a dashed slot labeled saved serialized work. In the second panel a later exact demand is served from the store while the engines stay idle, and an external write invalidates both the stored entry and engine-resident state.
Figure 7. One realized change (red ✗) under three exact serving boundaries. Green: served from cache; dashed arrows reach control-only descendants; dotted u is an untaken branch. Footers: nodes served of six taken. Three copies of the same workflow show whole-response, prefix-region, and subgraph-splice reuse after one node changes. Whole-response reuse serves nothing, region reuse serves the unchanged prefix, and subgraph splicing additionally serves two self-contained downstream tasks whose inputs exclude the changed value.
Figure 8. Open-loop mean latency, normalized to each workload’s own no-reuse floor (dashed =1.0 ). Rows are hardware; columns are load, at λ=0.12 ( HCI 0.3 ) and 0.8 req/s on H200 and at lower per-workload rates on RTX 4090. Four grouped bar panels in two rows: the top row is Qwen3-32B on four H200 GPUs at low and at load, the bottom row repeats the same four workloads with Qwen3-8B on four commodity RTX4090 GPUs. Each panel shows latency normalized to the no-reuse floor for DynBranch, its C1-only arm, DSP, SPAgent, InstCache, Helium, and Parrot across Routing, ReAct, Sub-Agent, and HCI. A DynBranch arm is the lowest bar in every group of every panel.
Figure 9. Speculation width and scale on Routing . (a) Fixed four-worker box, K swept. (b) Box and K grown together ( K=W−1 ). Two panels sharing a latency axis on the left and a speculative GPU-seconds axis on the right. Panel a holds the box at four workers and raises the speculative fanout K from 0 to 3: mean latency falls from 18.2 to 15.2 seconds while speculative engine time rises from zero to 19.8 GPU-seconds per request, of which the discarded part grows from a fifth to a third. Panel b scales the box and K together from one to four workers: latency falls from 22.3 to 15.2 seconds for zero, 10.1, 17.9 and 19.8 GPU-seconds per request. Both panels finish at the same point.
Figure 10. Sensitivity on Routing to (a) exact-replay rate and (b) serving-model size (dotted: mean over sizes). Two small panels. Panel a shows speedup over the no-reuse floor rising monotonically from 1.8x to 8.6x as the repeat rate grows. Panel b shows speedup flat near 1.9x across model sizes while the absolute saved seconds grow from about 1.6 seconds at 0.6B to 8.9 seconds at 32B.
Figure 11. Sensitivity to the models. (a) Served backbone on Routing (dashed: Qwen3-32B). (b) Drafter size on ReAct . Two small panels. Panel a plots mean-latency speedup for five served backbones, all between 1.55 and 1.99 times the floor, with Yi-1.5-34B lowest. Panel b plots the drafter's top-1 and top-3 branch accuracy against parameter count on a log axis, both rising to their highest values at 8B; two isolated points mark the 0.6B drafter with a LoRA adapter, sitting above the 8B point on both cut-offs.
Arm
repeat
partial overlap
fresh
floor
14.4 s
14.8 s
13.6 s
InstCache
0.01 s
13.8 s ( −7% )
14.6 s
Helium +
0.16 s
10.3 s ( −30% )
14.0 s
DynBranch
0.01 s
10.2 s ( −31% )
14.1 s
Table 1. Reuse alone by request type (Qwen3-32B, paired by request id); partial overlap = a sub-DAG shared with another record.
System
Routing
ReAct
Sub-Agent
HCI
2 GPUs
DynBranch
−18.6
−8.7
−34.4
−46.6
SPAgent
−12.3
−0.7
−23.6
−1.0
DSP
−13.1
−0.4
−23.8
−0.7
4 GPUs
DynBranch
−21.9
−8.5
−34.0
−47.7
Table 2. C2 isolation (serial closed-loop): mean Δ% against the shared no-reuse floor, C1 off on every arm.
Figure 12. A paired Routing request. Each decision ( router t ) gates a handler and executor ( h t , e t ). Three lanes over 20 seconds. The system lane runs two router stages back to back and an aggregator, finishing at 14.2 seconds, with ticks where the four handler and executor stages were served without running. A middle lane shows two speculative fills of 2.7 and 3.7 seconds, each beginning as the router before it starts decoding and finishing about three seconds before that router ends, on different workers. The floor lane runs the same two routers plus all four handler and executor stages and finishes at 19.9 seconds. An arrow between the two completion times is labeled minus 5.75 seconds.
Figure 13. Two-level admission on ReAct . (a) The 2×2 ablation. (b) The same gate vs. fixed thresholds (95% CIs). Two panels. The left plots fills per request on a logarithmic axis for the two by two of Action 0 and Action 1, as two lines: with Action 1 priced, 0.35 rising to 0.62 as Action 0 is disabled; with Action 1 fixed, 0.97 rising to 2.91. The vertical gaps are 2.8 and 4.7 times. The right panel plots paired wall time against the p-star 0.999 control on a logarithmic fill axis: the remaining arms sit below the control by 0.5 to 0.95 seconds, the system lowest at 0.95 seconds and the only one whose confidence interval clears zero, with the intervals of the firing arms overlapping each other.
Figure 14. Routing under load, three seeds. (a) Latency decomposition. (b) What C2 saves and the fills it issues. Two panels over five arrival rates. Panel a decomposes the no-reuse latency into full-system latency and the savings from C1 and C2. Panel b shows C2 latency saving rising from 1.28 to a peak of 1.39 seconds at 0.3 requests per second and then falling to 0.25, while the speculative fills issued per request fall from 1.38 to 0.89.
Figure 15. Phased adaptation on Routing . (a) What the two levels decide. (b) What the simple controls cost. Two panels over phases A through D. The left shows load peaking in the burst phase, where the candidate break-even threshold rises to 0.678 and the share of candidate-opening branches falls to 43 percent. With higher reuse at the same arrival rate, the threshold falls to 0.380 and that share returns to 100 percent. The right shows the latency excess of the static and always-open controls over \sys{}.
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
Measure
Repriced / exact oracle
Oracle-set match
626/639 ( 98.0% )
∑Jseq/∑Jseq⋆
99.36%
Median Jseq/Jseq⋆
99.86%
5th percentile
97.35%
Minimum
94.32%
Appendix
Table B.1. Exact replay of the sequence-aware admission objective. All rows use the 639 snapshots with positive optimum; the other 117 have zero optimum and both methods select nothing.
As LLM applications grow more complex, developers are increasingly adopting multi-agent architectures to decompose workflows into specialized, collaborative components, introducing structure that constrains agent behavior and exposes useful semantic predictability. Unlike traditional LLM serving, which operates under highly dynamic and uncertain conditions, this structured topology enables opportunities to reduce runtime uncertainty\unicodex2015yet existing systems fail to exploit it, treating agentic workloads as generic traffic and incurring significant inefficiencies. Our analysis of production traces from an agent-serving platform and an internal coding assistant reveals key bottlenecks, including low prefix cache hit rates, severe resource contention from long-context requests, and substantial queuing delays due to suboptimal scaling. To address these challenges, we propose Pythia, a multi-agent serving system that captures workflow semantics through a simple interface at the serving layer, unlocking new optimization opportunities and substantially improving throughput and job completion time over state-of-the-art baselines.
Agentic workflows are composed of sequences of interdependent Large Language Model (LLM) calls, and they have become a dominant workload in modern AI systems. These workflows exhibit extensive redundancy from overlapping prompts and intermediate results due to speculative and parallel exploration. Existing LLM serving systems, such as vLLM, focus on optimizing individual inference calls and overlook cross-call dependencies, leading to significant inefficiencies. This paper rethinks LLM and agent serving from a data systems perspective and introduces Helium, a workflow-aware serving framework that models agentic workloads as query plans and treats LLM invocations as first-class operators. Helium integrates proactive caching and cache-aware scheduling to maximize reuse across prompts, KV states, and workflows. Through these techniques, Helium bridges classic query optimization principles with LLM serving, achieving up to 1.56x speedup over state-of-the-art agent serving systems on various workloads. Our results demonstrate that end-to-end optimization across workflows is essential for scalable and efficient LLM-based agents.
Agentic AI applications form an emerging serving workload in which a request creates a workflow: a directed acyclic graph of LLM and tool calls that exposes per-node model choices and optional quality operators such as verifiers. This workload falls between two existing layers. Model-serving engines execute individual calls efficiently but cannot see workflow structure, while agent frameworks fix the workflow but cannot see backend load, so neither jointly chooses each node's model, verifier, and backend under serving-time conditions. We present Dyserve, a workflow-aware serving layer that fills this gap. Dyserve compiles each workflow's per-node model and verifier choices in one integer linear program (ILP) over a heterogeneous backend pool, priced by skill-conditioned offline profiles that transfer across workflows. This couples with hardware entering only through per-model throughput sweeps, and is weighted to concentrate strong models and verification on the nodes whose errors propagate the furthest. Because no single latency-quality preference fits every workload mix, Dyserve pre-solves the program at several pressure levels at admission and shifts a workflow's uncommitted suffix among these strategies under load, keeping the solver off the load-shift path; a failed tool call triggers a one-time residual re-solve that preserves committed work.
Jiayi Qian, Zishen Wan, Hanchen Yang +3
Columbia University New York, NY, USA · Intel Los Angeles, CA, USA