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.
Figures & tables
Figure 1. Workflow of an LLM agent.
Figure 2. Example recurring tool-call patterns and latent data dependencies in agent traces.
Figure 3. Breakdown of tool execution and LLM generation.
Figure 4. Tool execution time histogram. Blue: args from prior outputs; orange: LLM-generated args.
Figure 5. LLM generation and tool execution have different load sensitivity under concurrent agent tasks.
Figure 6. Bursty GPU pressure from alternating LLM generation and tool execution.
Figure 7. System architecture of PASTE . PASTE places a session-level control plane across the agent runtime, tool executor, and LLM serving engine.
Figure 8. Lossless speculative tool execution. Workflow showing speculative tool calls running in parallel with LLM generation, followed by a match decision that either reuses the speculative result or runs the authoritative tool call normally before committing a tool result.
Figure 9. Gain-preserving LLM–tool co-scheduling keeps LLM load near the task-optimal region. Two timeline panels compare native execution and overlapped execution for four tasks. Native execution finishes later and shows LLM GPU load fluctuating above and below the optimal load, while overlapped execution finishes earlier and keeps GPU load close to the optimal level.
Component
Setting
Cluster
4 nodes
Per-node CPU
96 vCPUs, AMD EPYC 7V13
Per-node Memory
512 GB
Per-node GPU
8 GPU, NVIDIA A100 80GB
Total GPUs
32 × NVIDIA A100
LLM Serving Engine
vLLM
Table 1. Evaluation setup
Figure 10. Average E2E latency comparison against all baselines.
Figure 11. Average tool latency comparison against tool-side baselines.
Figure 12. CDF of tool latency for each task
Figure 13. Tool throughput under trace-driven arrivals.
Figure 14. CDF of per-request tool speedup over ORION/SpecFaaS.
Figure 15. Time breakdown across all baselines.
Figure 16. Scalability under multi-session concurrent agent requests: speedup compared with LLM-side baselines.
Figure 17. Task’s E2E latency in ablation evaluation.
Figure 18. Pattern prediction quality: Top-1 accuracy, Top-3 recall, and overall hit rate.
LLM agents execute in an interleaved reasoning-and-action loop, where future tool calls cannot be launched until the current reasoning step completes. This serial dependency inflates end-to-end latency and leaves the model idle while waiting for tool execution. Prior work, Pattern-Aware Speculative Tool Execution (PASTE), mitigates this bottleneck by speculating likely future tool invocations from mined control-flow and data-flow regularities. However, PASTE is tool-centric and speculates only individual invocations rather than bounded future branches. We propose B-PASTE, a beam-aware extension that lifts speculation from single tools to local branch hypotheses under strict resource constraints. B-PASTE maintains a bounded beam of future execution subgraphs, ranks them by expected critical-path reduction rather than raw execution probability, and schedules only high-value branch prefixes on transient slack resources. It explicitly models co-run interference, downstream unlock value, and state-safety constraints, enabling the system to prioritize serial fast-path execution when early completion unlocks valuable future work, while still exploiting safe parallelism under low contention. This design is especially important for edge-side deployments, where speculative work must not steal scarce resources from latency-critical authoritative execution. Preliminary internal testing on Thor-class edge environments shows up to 1.4X end-to-end speedup, suggesting that branch-aware speculative execution remains effective even under tight resource budgets.
Long-running tools can dominate coding-agent latency: compilers, test suites, and repository commands take seconds to minutes while the agent idles. This observation stall presents the same tension that drove out-of-order processors -- asequential interface hides work that can be predicted and started early, but a speculative result may become visible only after it and every earlier step have been validated. We present TomasuLLM, a runtime that executes agent tool calls out of trajectory order while preserving task-execution correctness. It drafts future actions, runs them in isolated copy-on-write sandboxes, traces their dependencies and effects, and commits results in trajectory order only after validation against committed state. Across three benchmarks spanning sub-second to minutes-long tool calls, TomasuLLM improves the reported benchmark means and scales with tool latency: 1.31x on 100 SWE-bench Verified tasks, 1.35x on 28 Terminal-Bench 2.0 tasks, and 1.27x matched progress on 18 SWE-Marathon sessions. Across 4,010 audited commit-validation records, it produces zero false accepts.
Jiangnan Yu, Ceyu Xu, Mengming Li +6
HKUST Hong Kong, Hong Kong · Nanjing University Nanjing, China · King Abdullah University of Science and Technology Thuwal, Saudi Arabia +1
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.