PaperlayerView exact revision on arXiv

Source-linked AI summary

DynBranch: Speculative Subgraph Reuse for Dynamic Agentic LLM Serving

Junyi Shen, Noppanat Wadlom, Zhengyuan Su, Yao Lu

arXiv:2609.31047v1cs.DCcs.AIcs.LG

TL;DR

Agentic workflows serialize downstream computation behind model or user choices, even when that work may be predictable or previously completed. DynBranch gives unresolved branches stable coordinates for early execution and cross-request reuse, with a controller that prices work against serving load. Across four workloads, it reduces mean latency while preserving workflow results.

  • Problem

    In agentic workflows, downstream work waits for a model or user choice to resolve the branch, and caching alone cannot reuse a result whose identifying key is not yet known.

    Source: §1 · p. 1

  • Method

    DynBranch gives each decision point a stable coordinate for running candidate subgraphs during resolution and reusing completed results after exact-match and freshness checks, with load-priced admission.

    Source: §1 · p. 2

  • Results

    Up to 32% lower mean latency than each workload’s strongest prior system and 46–66% lower than a no-reuse floor, while preserving workflow results.

    Source: §1 · p. 2

  • Takeaways & Limitations

    DynBranch operates at the model-API boundary with unmodified agent harnesses and serving engines, and its benefits persist across backbone families and on a Qwen3-8B/RTX 4090 deployment.

    Source: §1 · p. 2

    The evaluated workflows use homogeneous serving models, stable branch coordinates before resolution, and side-effect-free speculative stages.

    Source: §5.6 · p. 11

Abstract

from arXiv · show

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.

1 Introduction

Agentic workflows repeatedly wait at branch-resolution barriers, where downstream work cannot begin until a model or user selects a path. DynBranch makes unresolved branches addressable for early execution and later reuse, with load-aware admission; across four workloads it cuts latency while preserving workflow results.

1 Introduction

  • 45–57% of end-to-end latency in measured coding, research, and scientific agents is downstream time serialized after model output.The paper calls this the branch-resolution barrier; likely downstream work can overlap the first occurrence, while validated results may avoid later computation.Source: §1 · p. 1
  • DynBranch uses a workflow-template decision-point coordinate to start candidate subgraphs during resolution and reuses completed results only after exact input matching and fresh dependencies are verified.Writes to recorded external reads invalidate an entry, and fills remain invisible until branch selection and canonical demand authorize their use.Source: §1 · p. 2
  • Its two-level controller admits candidate generation and individual fills when expected benefit exceeds the load price, which reflects current decode and KV occupancy.The paper identifies shared-subgraph reuse, early fill, and load-priced admission as its three contributions.Source: §1 · p. 2
  • Up to 32% lower mean latency than each workload’s strongest prior system, and 46–66% lower than a no-reuse floor, with workflow results preserved.Evaluated with Qwen3-32B on 4× H200 GPUs; benefits also persist across backbone families and on Qwen3-8B/RTX 4090.Source: §1 · p. 2

C2 Fillable

  • 26% of sub-tasks recur, alongside 54–62% prefix hits, in the reported C2 Fillable evidence.The passage gives these figures without specifying their tasks or measurement conditions.Source: C2 Fillable · p. 2

C1 Reuse

  • Figure 2 frames cross-request reuse and early execution as opportunities constrained by available serving capacity.Its caption distinguishes prior-work figures from the authors’ measurements with speculation disabled.Source: Figure 2 · p. 2

2 Background and Motivation

Agentic workflows create repeated decision windows where downstream work waits for a model or user choice, while existing caching and speculation do not jointly support reusable subgraphs, early execution, and load-priced admission. The section characterizes four workloads and shows that overlap, recurrence, prediction coverage, and resource contention shape the opportunity for reuse.

2 Background and Motivation

  • Existing caches anchor reuse at whole requests or prefixes, while prior speculative agents use predicted results only within the request that produced them.Cross-request reuse needs an identity available before resolution and invalidation when recorded external dependencies are written.Source: §2 · pp. 2–3
  • Safe workloads need a runtime-content-independent identity and stages safe to run twice, with the same result for the same input and dependency versions.Stages that sample or mutate external state run only after resolution.Source: §2 · p. 3

2.1 Dynamic Agentic Workloads

  • Four workloads span model-decode or human-wait windows, bounded or open candidate spaces, winner-promotion semantics, and reuse horizons; they are Routing, ReAct, Sub-Agent, and HCI.Routing uses BFCL function calls, ReAct performs multi-hop question answering, Sub-Agent dispatches tasks, and HCI waits for a user's action choice.Source: §2.1 · p. 3

2.2 The Branch-Resolution Barrier

  • 45–57% of task latency is downstream execution on serial model–tool paths; Figure 4 reports 26–43% wall-clock overlap for decode-window workloads, with HCI execution fitting within its modeled think window.Outside HCI, the p50 resolution window is 0.36–0.77× the downstream execution time.Source: §2.2 · p. 3, Figure 4 · p. 4
  • Prediction coverage varies by branch: bounded API selection reaches 91–94% with an oracle retriever and 59–84% with a deployed one, while ReAct places the next entity in its top three 61% of the time.In HCI, the top candidate matches the user's selection in 29 of 30 turns.Source: §2.2 · p. 3
  • With speculation disabled, 12% of ReAct retrievals within a run and 26% of Sub-Agent subtasks across runs have byte-identical inputs.Repeated MuSiQue subtopics rise from 19% at 100 questions to 61% at 5,000; SWE-agent and SWE-rebench commands recur verbatim 42–45% within a repository.Source: §2.2 · p. 4
  • At fixed context, 1–3 co-resident fills raise p50 latency by 4–6%, while 48 raise it by 53%; 24 fills with 4,500-word contexts raise latency from 11% to 145%.Resident KV rises with fill count and context, motivating its use to measure speculation in flight.Source: §2.2 · p. 4

3 DynBranch Design

DynBranch separates exact subgraph reuse, early execution, and load-priced admission: stable branch coordinates enable work before resolution, while canonical demands promote only exact, fresh results. Its components coordinate these decisions as one lifecycle.

3.3 Early Fill During Resolution (C2)

  • A stable workflow coordinate lets candidate fills run during branch resolution, but completed results remain unreadable until exact canonical demand and freshness checks authorize promotion.Source: §3.1 · p. 4, §3.3 · p. 6

3.2 Shared-Subgraph Reuse (C1)

  • DynBranch names a self-contained subgraph by its fingerprint and realized input, recording its output, external read-set, and single-execution provenance.Source: §3.2 · p. 5
  • Under one realized change, whole-response, prefix-region, and subgraph boundaries serve 0, 2, and 4 of six taken nodes, respectively, at the same exactness and freshness.Source: Figure 7 · p. 5, §3.2 · p. 5

3.3 Early Fill During Resolution (C2)

  • Promotion requires matching stage fingerprint, rendered input, and parameters plus fresh dependencies, yielding canonical-equivalent results; unpromoted work remains unobserved.Source: §3.3 · p. 6

3.4 Load-Priced Admission (C3)

  • A generation gate prices predictor setup, then a fill gate admits candidates only when expected savings exceed load-dependent delay, repricing after each admission.Source: §3.4 · pp. 6–7
  • After branch resolution, C3 updates selection for all predicted candidates but usability only for admitted, selected fills, using delayed events to revise the originating branch’s target.Source: §3.4 · p. 7

3.1 System Overview

  • DynBranch admits fills, runs them during branch resolution, and promotes exact, fresh results only when a canonical demand authorizes reuse.Source: §3.1 · p. 4, §3.4 · p. 7

4 Implementation

DynBranch integrates with agent harnesses through normalized model requests and hooks serving lifecycle events while retaining existing execution paths.

4 Implementation

  • Framework and text-based coding-agent harnesses normalize requests through an HTTP interceptor or their wire protocols, without requiring changes to the agent loop or protocol.Source: §4 · p. 7
  • Serving hooks use existing queue, slot, and KV accounting and SGLang or vLLM executors; disabling DynBranch preserves original semantics.Source: §4 · p. 8

5 Evaluation

DynBranch is evaluated across four agentic workloads, two load levels, and two hardware configurations; it lowers mean latency while preserving task accuracy. The evaluation also examines speculation costs, reuse and admission ablations, performance under load, and scope limits.

5.1 Experimental Setup

  • The testbed pairs Qwen3-32B on four H200 GPUs with a Qwen3-8B, four-node RTX 4090 replication, and evaluates Routing, ReAct, Sub-Agent, and HCI against reuse, scheduling, and speculation baselines.Open-loop experiments use client-observed mean wall time and p99; correctness is accuracy relative to the no-reuse floor.Source: §5.1 · p. 8

5.2 End-to-End Comparison

  • 14–32% lower mean latency at low load than each workload’s strongest external baseline, with reductions of 6.2–31% at load and 46–66% against the no-reuse floor.DynBranch has the lowest mean latency across all four workloads, both load levels, and both hardware configurations; task accuracy tracks the floor.Source: §5.2 · p. 8, Figure 8 · p. 9

5.3 Speculation Cost and Sensitivity

  • At four workers, Routing fanout K=0 to 3 lowers mean latency from 18.2 to 15.2 s while adding 19.8 GPU-seconds of speculative work per request; the discarded share rises to 33%.Scaling from one to four workers lowers latency from 22.3 to 15.2 s, but the fourth worker saves only 0.25 s; on ReAct, one run-ahead cycle captures useful overlap while deeper cycles consume no results.Source: §5.3 · pp. 8–9, Figure 9 · p. 9
  • Across four alternative backbones, speedup is 1.55–1.99× with accuracy within 0.012 of the floor; across 0.6B–8B drafters, speedup stays 1.63–1.70× without significant size differences.The 8B drafter has the highest top-1 accuracy but a 50% consumption rate, versus 70% for 1.7B; raising exact replay from 0.22 to 0.77 increases speedup from 1.8× to 8.6×.Source: §5.3 · pp. 9–10, Figure 11 · p. 10

5.4 Ablation Study

  • With early fill disabled, DynBranch cuts mean latency by 32.2% across a partial-overlap request mix with zero unsafe splices; fresh requests receive no reuse benefit.On partial-overlap requests, DynBranch reduces latency by 31%, matching Helium+’s 30% reduction, while InstCache gains 7%; Table 1 scopes the reuse-alone comparison.Source: §5.4 · p. 10, Table 1 · p. 10
  • With reuse disabled, early fill reduces latency by 8.5–47.7% across four workloads and both deployments; on HCI, completed fills serve 73% of choices and cut user-turn wait by 46.6–47.7%.On Routing, 349 fills yield 500 consumed stages through chained promotion; in the paired case study, early fill saves 5.75 s end to end.Source: §5.4 · p. 10, Table 2 · p. 10
  • Pricing both admission levels issues 8.3× fewer fills at indistinguishable latency than disabling Action 0 and fixing Action 1; priced gates also lower ReAct latency by 4.5% while drafting 2.8× less.Fixed thresholds vary fills 55× yet leave drafting at 2.5–2.6 s per request; Figure 13 compares the 2 × 2 ablation and fixed thresholds.Source: §5.4 · p. 11, Figure 13 · p. 11

5.5 Stress Test and 5.6 Limitations and Future Work

  • Under load, C1 removes 40–48% of floor latency and C2 a further 0.25–1.39 s across five Routing rates; C2’s gain stays positive as load rises but falls 82% from its peak.On a complete trace, priced admission lowers mean latency to 8.09 s, 5.7% below static and 5.5% below always; the evaluated workflows use homogeneous serving models, stable branch coordinates, and side-effect-free stages.Source: §5.5 · p. 11, §5.6 · pp. 11–12

6 Related Work

Related systems address caching, reusable computation, workflow scheduling, and agent speculation, but DynBranch combines early candidate-subgraph execution with later cross-request reuse. Its distinguishing point is making work addressable before a branch resolves and repricing it as load and outcomes change.

LLM state and result caches

  • Existing caches retain completed responses, plans, KV state, or tool outputs whose identity is already known, whereas DynBranch starts candidate work before the branch outcome exists and promotes validated results for later requests.Related systems include whole-response and plan caching, prefix or chunk KV reuse, and tool-output memoization.Source: §6 · p. 12

Reusable computation and freshness

  • Reusable-computation systems track dependencies and freshness, and DynBranch applies that contract to LLM subgraphs using external reads rather than base tables.The passage situates this beside semantic caching, incremental view maintenance, freshness scheduling, and adaptive query processing.Source: §6 · p. 12

Workflow and dataflow optimization; Speculative agents and serving

  • Workflow schedulers optimize known DAGs and speculative agents verify predicted work, but DynBranch supplies a not-yet-visible dependency and retains confirmed results for later exact matches with freshness checks.Unlike PASTE’s originating-request consumption, DynBranch persists validated products and reprices branch generation and fills using live load and observed outcomes.Source: §6 · p. 12

7 Conclusion

DynBranch addresses the branch-resolution barrier by naming candidate work before a branch resolves, then authorizing reuse through exact matching and fresh dependencies. Across four workloads it lowers latency while preserving workflow results, subject to requirements for named decision points and safe-to-repeat stages.

7 Conclusion

  • A stable coordinate makes candidate work addressable before branch resolution, while exact input matching, fresh dependencies, and a two-level controller govern reuse and admission.The controller prices work against live load.Source: §7 · p. 12
  • Across four agentic workloads, mean latency falls by up to 32% versus the strongest prior system and 46–66% versus a no-reuse floor, with workflow results unchanged.With reuse disabled, early fill alone still removes 8.5–47.7%.Source: §7 · p. 12
  • The stated contract requires a named decision point and a stage safe to run twice; within those requirements, predictors and pricing policies can evolve without weakening exact reuse or freshness.The conclusion also reports priced admission sustaining benefits from idle to saturated load.Source: §7 · p. 12

A Guarantees and Complexity of Reuse and Admission

The appendix establishes that DynBranch’s reuse key and promotion rule are maximally permissive under input-based soundness and freshness guards, and gives guarantees for invalidation, overlap, and load-priced admission. An archived replay also finds that the implemented admission rule retains nearly all oracle utility for the evaluated snapshots.

Reuse-key guarantees

  • κ★ is the coarsest uniformly sound input-based key and maximizes hit rate and expected reuse savings; Figure 7 shows it serving 4 of six nodes versus 0 and 2 for stricter keys.The guarantees assume input-based keys that do not model the stage semantics.Source: A Guarantees and Complexity of Reuse… · p. 17

Promotion

  • Promotion on κ★ with a fresh recorded read-set is the most permissive sound rule among shadows eligible under the lifecycle and freshness guards.Soundness means promotion never serves a value canonical execution would not have produced.Source: A Guarantees and Complexity of Reuse… · p. 17

Invalidation

  • With complete read sets and producer edges, the reverse-index cascade invalidates exactly affected nodes in O(|W| + |A| + |E_A| + |R_A|) time and O(|A|) auxiliary space.With incomplete provenance, the cascade may be conservative; minimality is not claimed.Source: A Guarantees and Complexity of Reuse… · p. 17

Overlap bound

  • Early execution can remove at most min(Tgen_k) of branch-k execution time when the selected candidate is covered, and zero otherwise.The bound is attainable when eligible fill starts with the resolution window, runs without contention, and is consumed immediately after resolution.Source: A Guarantees and Complexity of Reuse… · p. 17

Complexity

  • For branch b, indexed resolution and promotion take O(K_b + R_b) rather than scanning all shadows; reuse lookup and metadata costs scale with input, payload, and read-set sizes.The passage also specifies O(|q|) content-key construction, expected O(1) indexed probes, and O(N + R) metadata for N entries and R dependency references.Source: A Guarantees and Complexity of Reuse… · p. 17

Action 0

  • Action 0 learns one net return per branch, charging setup and enabled fills once; its sign guarantee is conditional on the stated bound and does not cover unrevealed candidates.Cold trials and seeded audits provide feedback outside the sign decision.Source: A Guarantees and Complexity of Reuse… · pp. 17–18

Action 1

  • Action 1 admits the highest-current-utility feasible candidate with positive utility, but its stepwise optimality and maximal terminal set do not guarantee maximum total utility across orders.The threshold is repriced at projected load after each admission.Source: A Guarantees and Complexity of Reuse… · p. 18

Archived replay

  • The implemented rule selects an exact-oracle set in 626 of 639 positive-optimum snapshots (98.0%) and retains 99.36% of aggregate sequence-aware oracle utility.The replay uses archived admission snapshots and compares against an exact ordered-subset oracle.Source: A Guarantees and Complexity of Reuse… · p. 18

B Checks from Archived Runs

Archived artifacts are used to check deterministic execution and replay sequential admission against an exact oracle. The replay retains 99.36% of aggregate oracle utility across positive-optimum snapshots, while the reproducibility run finds matching answers and hop counts in its stated comparisons.

Deterministic execution

  • In the no-reuse ReAct floor, all 87 within-group execution pairs have identical final answer text, and all 38 groups have identical hop counts.Across the full and C1-only arms, hop counts agree on all 116 paired question IDs; all nine request artifacts match their manifest hashes.Source: B Checks from Archived Runs · p. 18

Replay setup

  • The admission replay uses 756 archived Routing snapshots, with nine startup warmup events and 747 remaining events joined to request artifacts.The snapshots contain two or three candidates each, totaling 2,133; reconstructed costs agree with logged costs within printing precision.Source: B Checks from Archived Runs · pp. 18–19

Sequential-admission replay

  • The implemented rule retains 99.36% of aggregate oracle utility across 639 positive-optimum snapshots and selects an oracle-optimal set in 626 (98.0%).The other 117 snapshots have zero optimum, and both methods select nothing.Source: B Checks from Archived Runs · p. 19, Table B.1 · p. 19

Replay scope

  • All candidates together use at most 16.8% of recorded KV headroom, so the footprint-cap knapsack case does not arise in this archive.The replay compares the implemented order with an exact sequence-aware oracle using archived estimates and revealed candidates.Source: B Checks from Archived Runs · p. 19

Related papers

Loading 2609.31047v1…