PaperlayerView exact revision on arXiv

Source-linked AI summary

Parallelizing Tool Execution and LLM Generation for Low-Latency Agent Serving

Yifan Sui, Han Zhao, Rui Ma, Zhiyuan He, Hao Wang, Jianxun Li, Kaiqiang Xu, Kai Chen, Yuqing Yang

arXiv:2603.18897v3cs.DCcs.AI

TL;DR

Agent-serving systems serialize LLM generation and tool execution, exposing substantial tool latency on the task critical path. PASTE predicts concrete future tool invocations from recurring patterns, executes them speculatively while generation continues, and co-schedules returning sessions. Across deep research, software engineering, and scientific-agent workloads, it reduces average task completion time by 43.5% and speeds average tool execution by 1.8×.

  • Problem

    Serialized LLM–tool execution exposes tool time on the agent’s critical path, while existing serving systems do not jointly optimize tool execution and LLM scheduling.

  • Method

    PASTE predicts concrete future tool invocations from recurring agent patterns, isolates speculative results until confirmation, and co-schedules tool execution with returning LLM sessions.

  • Results

    43.5% lower average task completion time and 1.8× faster average tool execution were achieved versus state-of-the-art baselines across the evaluated workloads.

  • Takeaways & Limitations

    PASTE reduces exposed tool stalls and LLM-side waiting while preserving the agent’s semantically sequential execution.

  • Takeaways & Limitations

    Speculation must recover concrete arguments under uncertainty because wrong arguments waste speculative work and cannot be reused when authoritative invocations arrive.

Abstract

from arXiv · show

LLM-powered agents execute tasks through a sequential loop of model generation and tool execution. Today's serving systems serialize this loop, leaving tool latency exposed on the task critical path. This paper presents PASTE, a tool-aware agent-serving system that predicts concrete future tool invocations from recurring agent patterns and executes them speculatively while the LLM is still generating. PASTE isolates speculative results until confirmed by the LLM and jointly schedules tool execution and returning LLM sessions to avoid shifting bottlenecks to the GPU. Across deep research, coding, and scientific-agent workloads, PASTE reduces average task completion time by 43.5% and lowers observed tool latency by 1.8x.

1 Introduction

LLM agents serialize generation and tool execution, making exposed tool time a major task-level bottleneck. PASTE predicts concrete future invocations from recurring patterns, executes them speculatively, and coordinates tool and LLM scheduling to reduce end-to-end latency while preserving semantic order.

  • Execution model: Agent execution is semantically sequential, but current systems physically serialize LLM generation, tool waiting, and resumed generation on one critical path.This shifts the serving objective from token-level latency to task-level end-to-end latency.
  • Execution model: 45%–57% of agent end-to-end latency is attributed to tool execution across representative deep research, coding, and scientific tasks.Because tool time is serialized, reducing task latency requires reducing exposed tool time, not only accelerating generation.
  • Opportunity: Recurring patterns such as search→visit, edit→run test, and grep→file_editor make future tool calls predictable before explicit emission.Implicit data dependencies can expose later arguments in earlier outputs; 55% of successful file_editor calls are followed by terminal execution, and 95% of web visits use URLs contained in preceding search output.
  • PASTE: PASTE moves concrete tool execution earlier while preserving semantically sequential execution through speculative-result isolation and cross-phase control.Its control plane spans prediction, speculative scheduling, authoritative execution, and the timing of sessions returning to the LLM engine.
  • PASTE: PASTE combines a Pattern Analyzer, Tool Speculation Scheduler, and LLM–Tool Co-Scheduler to turn recurring patterns into coordinated overlap.The components instantiate calls from live state, protect authoritative calls, and pace returning sessions to avoid shifting bottlenecks to the LLM engine.
  • Evaluation: 43.5% lower average task completion time and 1.8× faster average tool execution were reported against state-of-the-art baselines.The system was implemented across agent applications and the vLLM serving stack.

2 Background and Motivation

Agent serving serializes semantically sequential LLM–tool loops, making tool execution a substantial task-level bottleneck. Predictable future invocations create an opportunity for speculation, but safe latency reduction requires coordinating speculation with load-sensitive LLM serving.

  • Agent Serving: Tool execution accounts for 45%–57% of agent E2E latency across representative deep research, coding, and scientific tasks.The measurements use Qwen-DeepResearch-30B on eight NVIDIA A100-80G GPUs with one agent request at a time.
  • Agent Serving: Serialized LLM generation and tool execution place exposed tool time directly on the task critical path.Reducing task E2E latency therefore requires reducing exposed tool time, not only accelerating LLM generation.
  • Future Tool Use Is Predictable: Recurring sub-workflows and implicit dependencies make future tool invocations predictable before the LLM emits them.Examples include search followed by visit, edit followed by run test, and grep followed by file_editor.
  • Opportunities: Speculative execution overlaps predicted tool work with ongoing LLM generation without changing the agent’s semantic order.The approach targets concrete future invocations rather than waiting for every tool call to be emitted.
  • Challenges: When concurrency grows from one to 192 sessions, LLM generation time grows by more than 17× while tool execution changes only modestly.This differing load sensitivity makes blind speculation vulnerable to shifting the bottleneck toward the LLM phase.
  • Challenges: Under high load, accelerating tools by 2× without changing the LLM scheduler can eliminate the tool-side gain and make end-to-end latency worse than baseline.Joint decisions about speculative execution and returning-session pacing are therefore required.

3 System Overview

PASTE coordinates speculative tool execution with LLM-side pacing through a session-level control plane. It predicts concrete invocations, protects authoritative execution, and regulates returning sessions to preserve latency gains.

  • Design Goals: PASTE predicts executable future tool invocations, including arguments, from recurring control-flow patterns and implicit data-flow dependencies.This goal extends prediction beyond tool names to concrete calls derived from session history.
  • Design Goals: Speculative results remain isolated until the LLM confirms a matching authoritative invocation, while authoritative jobs retain priority.Mismatched work is discarded, and speculative capacity is bounded or opportunistic.
  • Architecture: PASTE places a session-level control plane across the agent runtime, tool executor, and LLM serving engine.Each request is represented as an event stream containing LLM turns, tool calls, outputs, timing signals, and session metadata.
  • Architecture: The LLM–Tool Co-Scheduler paces returning sessions using tool completions and LLM load signals to keep active LLM load near an efficient region.It accounts for active requests, decode batch pressure, context length, and KV pressure.
  • System Effect: Intra-session overlap hides future tool latency while cross-session pacing keeps the LLM engine in a latency-efficient region.These two effects connect local speculative execution to end-to-end latency reduction.
  • Architecture: The Pattern Analyzer converts recurring session structure into concrete speculative invocation candidates.It watches live session history and emits a predicted invocation when required inputs are available.

4 System Design

PASTE coordinates concrete speculative tool execution with LLM scheduling, preserving semantic order while reducing exposed tool time without shifting bottlenecks to the LLM engine.

  • Overview: PASTE uses middleware around tool dispatch and LLM generation to expose online events and per-session state for prediction, speculation, and pacing.
  • Pattern Analyzer: The Pattern Analyzer mines recurring control-flow and data-flow patterns, then binds validated matches to live session payloads to produce concrete future invocations.It emits preparation hints instead when required payloads are unavailable.
  • Tool Speculation Scheduler: The Tool Speculation Scheduler isolates predicted calls and results from authoritative state until the LLM confirms the canonicalized invocation.Hits reuse completed results or promote in-flight jobs; misses fall back to normal execution.
  • LLM–Tool Co-Scheduler: The LLM–Tool Co-Scheduler admits ready turns according to expected exposed-tool-time reduction and current LLM pressure rather than releasing every completed session immediately.It uses tool-side completion signals and preserves the LLM engine’s task-optimal load region.
  • LLM–Tool Co-Scheduler: In-engine load shaping combines decoding and KV-cache pressure to avoid both under-utilization and overload while preserving tool-side gains.The scheduler feeds active-request, queue, context, and cache measurements back into its pressure estimate.

5 Implementation

PASTE is implemented as a non-invasive control plane around existing agent runtimes and a vLLM backend, requiring only lightweight integration wrappers.

  • Implementation: PASTE spans agent-side middleware and vLLM-side scheduling hooks while preserving agents’ original tool APIs.The prototype contains 5k lines of TypeScript and 2k lines of Python.
  • Implementation: The middleware records session events, binds validated patterns to live payloads, and forwards only fully instantiated predictions to a bounded speculative path.Incomplete predictions remain preparation hints and do not modify authoritative state.

6 Evaluation

The evaluation measures PASTE across agent workloads, baselines, arrival patterns, and latency or throughput axes using controlled, disjoint train and test task sets.

  • Evaluation Setup: The evaluation covers E2E latency, tool latency and throughput, time breakdowns, scalability, scheduling ablations, prediction quality, and speculation overhead.
  • Evaluation Setup: Experiments use the same hardware and software stack, timeouts, and retry policy across systems, with patterns mined from historical tasks and tested on disjoint new tasks.
  • Workloads: The workloads include VirtualLab, Qwen Deep Research, and gemini-cli across DeepResearchBench, SWE-bench, and ScholarQA.
  • Baselines: Baselines isolate LLM-serving and tool-side acceleration through vLLM, Agentix, ORION, and SpecFaaS.ORION and SpecFaaS use vLLM for LLM serving, isolating their tool-side differences from the backend.
  • Evaluation Setup: The study also replays a production Azure Functions trace to preserve realistic bursty request arrivals and reports E2E, tool, tail, queueing, throughput, hit-rate, and overhead metrics.

6.2 E2E Latency Reduction

PASTE reduces both end-to-end and tool-side latency across agents and benchmarks, with gains attributed to speculative tool execution combined with LLM–tool co-scheduling.

  • E2E Latency: 43.5% lower average E2E latency and 55.4% better p99 tail latency are reported against vLLM, Agentix, ORION, and SpecFaaS.
  • E2E Latency: The E2E improvement holds across average and tail latency because speculative execution reduces exposed tool stalls while co-scheduling lowers LLM-side waiting.
  • Tool-Side Acceleration: 55.2% lower average tool latency and 60.6% lower p99 tool latency are reported against ORION and SpecFaaS.
  • Tool-Side Acceleration: 1.71× and 1.83× average tool-side speedups are reported over ORION and SpecFaaS, respectively.
  • Tool-Side Acceleration: PASTE completes more tool work under bursty arrivals while keeping authoritative calls on the high-priority path.
  • Tool-Side Acceleration: 97% of pooled requests observe tool speedup above 1×, while worst-case requests remain close to parity.
  • Tool-Side Acceleration: Gains are largest for tool-heavy tasks and remain nonnegative for more LLM-dominated tasks, indicating low overhead when speculation misses.

6.4 Time Breakdown Analysis

PASTE lowers both exposed tool-side time and LLM-side serving time rather than shifting latency from one side of the agent loop to the other.

  • PASTE reduces exposed tool-side time to 34 s from 84–89 s under tool-side baselines.This represents roughly 60% less exposed tool time.
  • PASTE reduces LLM-side time to 186 s from 226–249 s under LLM-side baselines.The reduction is 18%–25% relative to those baselines.
  • PASTE reduces both latency components simultaneously through speculative tool execution and LLM–tool co-scheduling.ORION and SpecFaaS improve the tool path but leave LLM serving unchanged, whereas Agentix reduces LLM-side waiting without hiding exposed tool stalls.

6.5 System Scalability

PASTE maintains speedups as concurrency increases and uses scheduling controls to prevent speculative work from crowding out authoritative execution, while both scheduling mechanisms are needed for low latency.

  • Scalability: At every concurrency, PASTE sustains at least 1.27× speedup over vLLM and 1.24× over Agentix.Across the full sweep, pooled speedups reach 1.50× over vLLM and 1.30× over Agentix.
  • Scalability: Speculative work remains isolated from authoritative tool execution because explicit budgets throttle it and keep it preemptible.The evaluation sweeps arrival rate and concurrent sessions while holding resource budgets fixed.
  • Ablation Study: Full PASTE reduces E2E latency to 270 s and LLM queueing time to 45 s across the ablation and serving baselines.This combines speculative tools with LLM–tool co-scheduling.
  • Ablation Study: Tool-only speculation raises average LLM queueing to 65 s and E2E latency to 419 s, while LLM-only admission leaves E2E latency at 342 s.The results show that both tool speculation and LLM-side scheduling are necessary.

6.7 Pattern Prediction Accuracy

PASTE’s predictor is imperfect but often identifies useful future tools, with stronger performance on structured sequences and bounded speculative work limiting the cost of uncertainty.

  • Prediction Quality: The predictor achieves up to 27.8% Top-1 accuracy, 43.9% Top-3 recall, and 93.8% overall hit rate.Accuracy is higher for structured tool sequences and lower for open-ended exploration patterns.
  • Prediction Quality: Top-3 recall is useful because PASTE can execute a small set of likely tools when any candidate matches.This allows speculation to reduce exposed tool time despite imperfect Top-1 accuracy.
  • Prediction Quality: Explicit speculation budgets bound wasted work and prevent negative interference with authoritative execution when predictions are uncertain.The same budgeted control supports safe use of multiple speculative candidates.
  • Overhead: At a moderate speculation budget, PASTE reduces tool execution latency by 48% using 1–3 otherwise idle CPU cores and 250 MB of additional memory.The pattern predictor and scheduling policy add less than 100 ms of latency overhead.

7 Related Work

Prior serving and runtime systems improve LLM, agent, or tool execution components separately, while PASTE combines concrete-call speculation with risk-aware control for agent workflows.

  • LLM and agentic serving: General LLM-serving systems optimize token-level serving efficiency, while agentic-serving systems add session-aware mechanisms for multi-turn tool-using programs.These systems address serving and workflow concerns but do not establish joint optimization of tool execution and LLM generation.
  • Tool & runtime acceleration: Tool and runtime acceleration systems reduce orchestration, cold-start, caching, state-management, or data-transfer overhead in workflow and microservice settings.These techniques primarily target tool execution infrastructure rather than the agent’s serialized LLM–tool loop.
  • Speculation: Existing speculation mechanisms execute likely-needed tasks early but struggle to infer context-dependent arguments and manage correctness and side-effect risks.PASTE addresses these challenges with concrete future invocations and explicit risk-aware control.

8 Conclusion

PASTE coordinates speculative tool execution with LLM generation for low-latency agent serving while preserving semantic sequencing. It reduces exposed tool stalls and LLM-side waiting across multiple agent workloads.

  • PASTE predicts concrete future tool invocations from recurring agent patterns and executes them speculatively during LLM generation.
  • PASTE paces returning sessions so hidden tool time does not become additional LLM-side delay.
  • PASTE reduces exposed tool stalls and LLM-side waiting across deep research, software engineering, and scientific-agent workloads while preserving semantic sequencing.
Loading 2603.18897v3…