cs.DCSep 25, 2026
SaveDynBranch: Speculative Subgraph Reuse for Dynamic Agentic LLM Serving
Organizations: National University of Singapore Singapore
Abstract
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- . (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 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 ). Rows are hardware; columns are load, at ( HCI ) and 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, swept. (b) Box and grown together ( ). 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 | s | s | s |
| InstCache | s | s ( ) | s |
| Helium + | s | s ( ) | s |
| DynBranch | s | s ( ) | 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 | ||||
| SPAgent | ||||
| DSP | ||||
| 4 GPUs | ||||
| DynBranch | ||||
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 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 | ( ) |
| Median | |
| 5th percentile | |
| Minimum |
Table B.1. Exact replay of the sequence-aware admission objective. All rows use the snapshots with positive optimum; the other have zero optimum and both methods select nothing.
More in this topic
LLM Agent Workflow Optimization
LLM agent workflow optimization studies how to design and run multi-step agents for better task success, reliability, latency, and cost.
See all 251 papers