Skip to content

AgentSpec: Speculative Decoding for Batch Inference of LLM Agents

Conference: EMNLP 2026
Paper: ACL Anthology
Area: LLM Agent
Keywords: speculative decoding, LLM agents, batch inference, structure-isolated drafting, redundancy-aware budget allocation

TL;DR

Addressing the severe throughput degradation of speculative decoding in large-batch LLM agent serving caused by high token rejection rates and dynamic budget under-utilization, AgentSpec introduces pushdown automaton-guided structure-isolated drafting and redundancy-aware token budget allocation, achieving up to 2.02ร— end-to-end goodput speedup in vLLM without compromising generation quality.

Background & Motivation

Large language model (LLM)โ€“based autonomous agents have emerged as a dominant paradigm for resolving complex problems requiring multi-step reasoning, external tool execution, and dynamic environment feedback. In real-world enterprise deployments, however, serving LLM agents incurs substantial computational expenditure and user-facing latency due to extended generation horizons, iterative verbal reflection, and repeated multi-turn API calls. While speculative decoding offers a provably lossless acceleration approach by proposing multiple draft tokens and verifying them in parallel with the target model, existing speculative decoding algorithms suffer from severe speedup degradation as concurrency increases. Under large-batch conditions standard in production engines like vLLM and SGLang, speculative decoding frequently slows down below regular autoregressive decoding.

This performance collapse stems from two fundamental architectural bottlenecks in agentic serving. First, existing speculative decoding methodsโ€”ranging from small-draft models like EAGLE-3 to model-free retrieval schemes like NGram and SuffixDecodingโ€”retrieve draft continuations uniformly across heterogeneous execution phases and diverse conversational queries. In multi-turn agent execution, where thoughts, tool parameters, and observation feedbacks exhibit sharp semantic divergence, global retrieval yields drafts on mismatched trajectories. Consequently, draft rejection rates escalate to 50%โ€“88%, causing the verification overhead on rejected tokens to quickly eclipse the latency saved by accepted tokens. Second, the available token budget for speculative verification varies dynamically across batches depending on hardware arithmetic intensity. Existing schedulers either partition budgets uniformly or rely on coarse-grained historical acceptance rates, resulting in severe over-allocation to low-confidence requests and under-allocation to high-redundancy requests.

This paper's key insight is that while agent workflows exhibit drastic semantic shifts across steps or user tasks, the generation patterns within the same semantic execution block (e.g., Python code blocks, structured tool calls, or formula segments) are highly homogeneous and recurrent. Restricting draft candidate retrieval strictly within structurally isolated boundaries while weighting allocation budgets by candidate prefix consensus eliminates speculative waste. Core idea: abstract agent execution into semantically isolated blocks tracked via a lightweight string-based pushdown automaton (PDA), confine draft retrieval to matched intra-block caches, and dynamically allocate batch token budgets via prefix redundancy scores to minimize verification overhead.

Method

Overall Architecture

AgentSpec is a model-free speculative decoding framework tailored for batched LLM agent serving. The agent client supplies a lightweight structure identifier metadata \(S_i = \{a_i, q_i, B_i\}\) alongside the input prompt, encoding the agent identity, query identifier, and paired string delimiters defining semantic execution blocks. During token generation, newly emitted tokens are incrementally mapped to strings and ingested by a per-request pushdown automaton (PDA) to track the active semantic block. Draft candidates are then retrieved exclusively from a dedicated structure-isolated cache corresponding to that block. Prior to target model verification, a batch allocator evaluates the statistical consensus of candidate prefixes, computes per-request redundancy scores, and adjusts individual draft lengths under the dynamic hardware-constrained token budget.

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["Concurrent Agent Batch Requests<br/>Input Prompt & Structure Identifiers"] --> B["PDA-based Semantic Block Tracking<br/>Token-to-string mapping & PDA updates"]
    B --> C["Structure-Isolated Drafting<br/>Retrieval from isolated intra-block cache"]
    C --> D["Redundancy-Aware Budget Allocation<br/>Candidate consensus scoring & budget split"]
    D --> E["Batched Parallel Model Verification<br/>Lossless acceptance & context cache update"]

Key Designs

1. PDA-based Semantic Block Tracking: Resolving Subword Boundary Misalignment Without Tokenization Overhead

Semantic execution blocks in LLM agents are naturally defined by paired delimiter strings such as python ..., <tool_call> ... </tool_call>, or $$ ... $$. However, LLM inference operates at the subword token level, where token boundaries frequently cross and split string boundaries. Re-invoking the full tokenizer to convert tokens back into text at each decoding step in high-throughput engines like vLLM incurs unacceptable CPU overhead and GPU stalls. AgentSpec resolves this tension by pre-building a static token-to-string prefix map and maintaining a lightweight pushdown automaton (PDA) per active request on the server. As new tokens are generated, they are mapped to text fragments in amortized \(O(1)\) time and pushed into the PDA, accurately tracking whether the request is entering, processing, or exiting a specific semantic block \(b_i^k\).

2. Structure-Isolated Drafting: Suppressing Token Rejection by Confining Search to Semantically Homogeneous Contexts

Conventional draft-model-free methods (e.g., NGram, SuffixDecoding) search globally across all historical generation steps, inadvertently matching tokens across heterogeneous stages such as natural language reasoning, structured tool invocation, and environment observations. This context mismatch is the root cause of the empirical 50%โ€“88% token rejection rates in agent inference. AgentSpec assigns a dedicated, isolated cache \(H(a_i, q_i, b_i^k)\) to each combination of agent, query, and active semantic block. Speculative draft candidates are retrieved strictly from the matching semantic group, filtering out irrelevant semantic branches. By constraining the search space to structurally and grammatically coherent contexts, AgentSpec slashes the average rejection rate to 26.4%, cutting token rejection by more than half relative to baseline methods.

3. Redundancy-Aware Budget Allocation: Aligning Speculative Token Lengths with Dynamic Compute-Bound Budgets

In batched inference, the maximum hardware token budget per decoding step scales inversely with concurrency, formalized as \(B_t = \lfloor \alpha / b_z \rfloor\) where \(b_z\) is the batch size and \(\alpha\) governs total compute headroom. Uniform or static allocation wastes verification capacity on erratic, low-probability drafts while throttling requests with high speculative certainty. To dynamically optimize allocation, AgentSpec formulates a redundancy confidence score \(g(c_i, n_i)\) based on historical candidate prefix consensus: $\(g(c_i, n_i) = \frac{c_i}{n_i} \cdot p(n_i), \quad p(n_i) = g_{\min} + (1 - g_{\min})(1 - e^{-n_i})\)$ Here, \(n_i = |CT_i|\) denotes the number of candidate continuations matching the current prefix, \(c_i\) represents the number of candidates agreeing on the most frequent common continuation prefix \(CT_i^*\), \(p(n_i)\) penalizes low-sample variance, and \(g_{\min}\) sets a baseline confidence floor. Using the batch-normalized redundancy scores, the speculative draft length \(L_i\) assigned to request \(r_i\) is determined as: $\(L_i = \max \left( |CT_i^*|, \left\lfloor B_t \cdot \frac{g_i}{\sum_j g_j} \right\rfloor \right)\)$ This ensures every request speculates at least its most confident consensus prefix, while dynamically funneling surplus token budgets to high-redundancy requests to maximize batch execution throughput.

A Worked Example

Consider a batch of coding requests running under a Reflexion agent workflow served in vLLM with batch size \(b_z = 256\), budget scale \(\alpha = 1024\), yielding an aggregate speculative token budget \(B_t = 4\). 1. Semantic Tracking: Request 1 outputs the tokens ```python\ndef, which the token-to-string PDA parses into the active block \(b_{\text{code}}\). Request 2 outputs natural language reflection, mapping to \(b_{\text{text}}\). 2. Structure-Isolated Matching: Request 1 queries \(H(\text{agent}_1, q_1, b_{\text{code}})\) and discovers 4 historical candidate branches; 3 of them agree on the prefix solve():\n n = int(input()) of length 6. Request 2 queries \(H(\text{agent}_2, q_2, b_{\text{text}})\) and locates only 1 sparse, unrepeated match. 3. Redundancy Scoring & Allocation: Request 1 exhibits strong consensus with \(c_1/n_1 = 3/4 = 0.75\), translating via \(p(n_1)\) to a high redundancy score \(g_1 = 0.71\). Request 2 yields a low score \(g_2 = 0.15\). The batch allocator routes virtually all remaining speculative token budget to Request 1, expanding its draft length to the full prefix, while Request 2 is restricted to minimal conservative generation. 4. Target Model Verification: The target LLM evaluates the batch in a single forward verification pass. Request 1 has all 6 tokens accepted simultaneously, advancing 7 tokens in one step and saving 6 sequential forward passes.

Key Experimental Results

Main Results

AgentSpec was integrated and evaluated in the vLLM engine (v0.12.0 V1) on an NVIDIA A100-SXM4-80GB GPU at the production-standard maximum batch size of 256 (where models are compute-bound), with additional scaling validated on H100 GPUs. The benchmarks evaluate four representative agentic workloads across two categories: workflow-based agents (Code Generation via Reflexion on USACO; Deep Research via LangChain on DeepResearch-Bench) and model-based agents (GAIA and SWE-Bench-Lite on OpenHands). Evaluation spans four diverse foundation models: Qwen-3-8B, GPT-OSS-20B, DeepSeek-R1-Distill-Llama-8B, and MiMo-7B. The primary efficiency metric is Goodput (generated tokens per second across the entire workload lifecycle) alongside speedup relative to standard autoregressive decoding.

The quantitative results from Table 2 of the paper are presented below:

Model Method Deep Research Agent (Tokens/s) Deep Research Speedup Code Generation Agent (Tokens/s) Code Generation Speedup GAIA (Tokens/s) GAIA Speedup SWE-Bench (Tokens/s) SWE-Bench Speedup
Qwen-3-8B Normal 617.41 1.00ร— 636.09 1.00ร— 501.27 1.00ร— 652.44 1.00ร—
EAGLE-3 605.14 0.98ร— 539.01 0.85ร— 468.22 0.93ร— 523.12 0.80ร—
NGram 509.62 0.83ร— 422.58 0.66ร— 308.27 0.61ร— 408.28 0.63ร—
SuffixDecoding 598.74 0.97ร— 579.21 0.91ร— 498.16 0.99ร— 556.64 0.85ร—
AgentSpec (Ours) 661.43 1.07ร— 828.10 1.30ร— 537.78 1.07ร— 854.69 1.31ร—
GPT-OSS-20B Normal 201.43 1.00ร— 289.26 1.00ร— 247.67 1.00ร— 351.22 1.00ร—
EAGLE-3 125.71 0.62ร— 161.34 0.56ร— 112.16 0.45ร— 198.81 0.57ร—
NGram 158.91 0.79ร— 175.19 0.61ร— 109.22 0.44ร— 253.36 0.72ร—
SuffixDecoding 196.54 0.98ร— 295.85 1.02ร— 187.79 0.76ร— 319.73 0.91ร—
AgentSpec (Ours) 297.54 1.48ร— 584.43 2.02ร— 295.76 1.19ร— 595.20 1.69ร—
DSK-Distill-8B Normal 987.66 1.00ร— 1230.28 1.00ร— 823.39 1.00ร— 1432.27 1.00ร—
EAGLE-3 965.43 0.98ร— 1119.29 0.91ร— 864.43 1.05ร— 1098.82 0.77ร—
NGram 752.66 0.76ร— 797.18 0.65ร— 725.29 0.88ร— 1014.47 0.71ร—
SuffixDecoding 995.14 1.01ร— 1041.29 0.85ร— 820.09 1.00ร— 1498.69 1.05ร—
AgentSpec (Ours) 1294.65 1.31ร— 1671.34 1.36ร— 924.47 1.12ร— 2281.87 1.59ร—

Ablation Study & Execution Overhead

To isolate the individual benefits of each algorithmic component, ablations were conducted using Qwen-3-8B on the Deep Research and Code Generation workflows. The variants evaluated include AgentSpec (S) featuring structure-isolated drafting only, AgentSpec (R) pairing SuffixDecoding with redundancy-aware budget allocation only, and AgentSpec (N) which operates without explicit structural metadata provided by the client application. In addition, execution time breakdown on the CodeGen workflow evaluates the drafting versus verification costs.

The empirical data from Tables 5 and 6 of the paper are reported below:

Dimension Configuration / Variant Quantitative Metric Note & Analysis
Modular Ablation Normal (Baseline) DeepResearch: 617.41 (1.00ร—) / CodeGen: 636.09 (1.00ร—) Standard autoregressive baseline
(Qwen-3-8B) AgentSpec (S) isolated drafting only DeepResearch: 647.12 (1.05ร—) / CodeGen: 795.54 (1.25ร—) Isolating semantic blocks cuts rejection and delivers major gains
AgentSpec (R) budget allocation only DeepResearch: 623.33 (1.01ร—) / CodeGen: 702.28 (1.10ร—) Dynamically tuning budgets provides steady positive improvements
AgentSpec (N) without structure inputs DeepResearch: 661.08 (1.07ร—) / CodeGen: 809.12 (1.27ร—) Operates robustly even without explicit application metadata
AgentSpec (Full Model) DeepResearch: 661.43 (1.07ร—) / CodeGen: 828.10 (1.30ร—) Full system combining both modules achieves peak throughput
Execution Breakdown EAGLE-3 Draft: 5.72 min / Verification: 34.24 min / Total: 39.96 min Heavy draft model execution latency in large-batch settings
(CodeGen Task) NGram Draft: 0.68 min / Verification: 39.82 min / Total: 40.50 min Low drafting time offset by heavy rejected verification cost
SuffixDecoding Draft: 1.41 min / Verification: 33.12 min / Total: 34.53 min Unconstrained matching leaves verification occupying >95% time
AgentSpec (Ours) Draft: 1.74 min / Verification: 26.11 min / Total: 27.85 min Verification latency reduced by 21%, overall runtime reduced by 19%

Key Findings

  • Severe Large-Batch Degradation of Prior Speculative Algorithms: In high-concurrency environments (batch size = 256), baseline algorithms like EAGLE-3, NGram, and SuffixDecoding degrade severely, delivering speedups between 0.44ร— and 0.98ร—โ€”becoming slower than standard autoregressive decoding. In contrast, AgentSpec consistently achieves end-to-end acceleration across all models and workloads, reaching up to 2.02ร— speedup on GPT-OSS-20B.
  • Structure Isolation is the Dominant Factor: The ablation comparison demonstrates that AgentSpec (S) accounts for the vast majority of throughput improvement over AgentSpec (R). Suppressing the mismatch of cross-block tokens is paramount to avoiding wasted verification compute.
  • Negligible Scheduling Overhead for Substantial Verification Relief: Maintaining the PDA and calculating redundancy distributions introduces under 2 ms of CPU drafting time per step, while reducing GPU-bound verification latency by 21%, resulting in a net 19% reduction in total job execution time.
  • Outperforming Multi-Token Prediction (MTP): On MiMo-7B with native MTP pre-training, MTP degrades under large-batch agent workloads (USACO-All speedup of 0.73ร—), while the training-free AgentSpec maintains a 1.29ร— speedup over autoregressive decoding.

Highlights & Insights

  • Leveraging Structural Execution Locality: Identifies that agent workflows are not uniform token streams; token repetition is tightly localized within specific semantic execution blocks (code, tool calls, reasoning blocks). Restricting the draft search space to matching blocks cuts draft token rejection by over 50%.
  • Zero-Training System-Level Acceleration: Unlike EAGLE-3 or MTP which require auxiliary draft model fine-tuning or pre-training modifications, AgentSpec is completely model-free, parameter-free, and provably lossless for any base LLM.
  • Hardware-Aware Adaptive Speculation: Formulates dynamic speculative budgets based on hardware arithmetic intensity and batch size, replacing static speculation hyperparameters with continuous consensus-driven allocation.

Limitations & Future Work

  • Reliance on Application-Server Interface: Peak efficiency requires the agent framework to expose high-level semantic tags (e.g., block start and end strings). While the fallback variant AgentSpec (N) maintains strong performance, environments where client metadata is completely stripped will see slightly lower acceleration margins.
  • Lower Speedups on Highly Divergent, Non-Repetitive Tasks: Because AgentSpec is a retrieval-based speculative approach, tasks that feature unique, non-repeating generation with negligible historical pattern reuse (such as open-ended creative dialogue) provide fewer match opportunities.
  • vs EAGLE-3 / MTP: Draft-model-based and multi-token prediction methods incur non-negligible forward pass overhead at large batch sizes and cannot easily track structural transitions in multi-round agent interactions; AgentSpec achieves higher net throughput with zero model parameters and lower drafting latency.
  • vs NGram / SuffixDecoding: Existing model-free methods construct suffix trees or n-gram tables globally across the entire conversation history, yielding excessive false-positive drafts (>65%โ€“88% rejection rate); AgentSpec uses pushdown automata to isolate semantic blocks, cutting the rejection rate to 26.4%.
  • vs AdaSpec: AdaSpec adapts speculative budgets using coarse-grained historical acceptance rates; AgentSpec calculates instantaneous consensus among retrieved candidate continuations, better capturing per-step confidence variations.

Rating

  • Novelty: โญโญโญโญ [Identifies the structural causes of speculative decoding degradation in large-batch agent serving; cleverly adopts pushdown automata and prefix redundancy metrics]
  • Experimental Thoroughness: โญโญโญโญโญ [Extensive evaluations across 4 LLM families, 4 distinct agent workflows, Spec-Bench, fine-grained latency breakdown, and A100/H100 hardware scaling]
  • Writing Quality: โญโญโญโญโญ [Clear mathematical modeling of efficiency bottlenecks, rigorous empirical validation, and highly coherent exposition]
  • Value: โญโญโญโญโญ [Crucial engineering and algorithmic contribution for lowering the serving cost and response latency of production-scale LLM agents]