🤖 machine learning

AOSpec: Action and Observation Co-Speculation for Low-Latency Agent Serving

AOSpec is a lossless framework that reduces agent serving latency by co-speculating actions and observations through Expected Value Decoding and Joint Action-State Verification, thereby breaking the lookahead-accuracy tradeoff and achieving significant end-to-end latency reductions across diverse benchmarks.

Original authors: Hao Mark Chen, Jinnan Guo, Wayne Luk, Hongxiang Fan

Published 2026-08-04

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Hao Mark Chen, Jinnan Guo, Wayne Luk, Hongxiang Fan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the conductor of a massive, high-speed orchestra where the musicians are super-smart computers (Large Language Models) and the stage is a complex, living world full of tools, files, and programs. In this digital symphony, the computer thinks of a musical note (an action), then the stage has to physically play it (execute the tool), and only then can the computer hear the result and decide on the next note. For a long time, this process was a strict relay race: the computer had to wait in silence while the stage played the note before it could even think about the next one. As computers get faster at thinking, the waiting time for the stage to play the notes has become the bottleneck, slowing down the whole performance. Scientists have tried to fix this by guessing the next note early (action speculation) or guessing what the sound will be (observation speculation), but these solo guesses often fail because the stage is unpredictable, and guessing a whole sequence of notes usually leads to a cacophony of errors.

This paper introduces a new conductor's technique called AOSpec (Action and Observation Co-Speculation). Instead of guessing just one thing, AOSpec runs a clever, parallel rehearsal where it guesses both the next move and the resulting sound at the same time, but with a safety net. It uses a smart strategy to focus its guesses on the slowest, most time-consuming parts of the show, and it sets up "safe zones" (isolated sandboxes) where it can try out risky moves without messing up the real stage. If the guess turns out to be right, the show moves forward instantly; if it's wrong, the rehearsal is quietly discarded, and the real show continues without a hitch. The authors measured this on a variety of complex tasks and found that this method can cut the total waiting time by up to 32.5% on average, and for the slowest, most frustrating delays, it can shave off nearly 43% of the time, making the digital orchestra play much faster without missing a beat.

The Problem: The Waiting Game

Imagine you are playing a video game where your character is a genius strategist. Every time you type a command like "open the treasure chest," your character has to stop thinking and wait for the game engine to actually open the chest, check what's inside, and show you the gold. If the chest takes 10 seconds to open, your character sits there for 10 seconds, doing nothing.

As computer chips get faster, your character starts thinking in milliseconds. But the chest-opening (the "tool execution") still takes seconds. This creates a frustrating gap: the thinker is lightning-fast, but the doer is slow. The paper points out that most of the waiting time comes from just a few very slow actions, like opening a giant vault, while many other actions are quick. Old methods tried to guess the next command to save time, but they often guessed wrong because they didn't account for the fact that some results (like the contents of a chest) can't be predicted without actually opening it.

The Solution: The "Safe Rehearsal" Strategy

The authors of this paper, working at Imperial College London, built a system called AOSpec to solve this. Think of it as a director who doesn't just wait for the actor to finish a scene before planning the next one. Instead, the director runs a "safe rehearsal" in a parallel universe.

Here is how the three main tricks work:

The Smart Gambler (Expected Value Decoding):
Not all guesses are worth the same. Guessing the result of a quick "hello" command is easy but saves very little time. Guessing the result of a "download a movie" command is hard, but if you get it right, you save a huge amount of waiting time. AOSpec uses a method called Expected Value Decoding (EVD). Instead of just guessing the most likely outcome, it guesses the outcome that offers the biggest time savings. It's like a gambler who ignores the small, safe bets and focuses only on the high-stakes, high-reward moves. If the guess is right, the system skips the wait entirely.
The Safe Sandbox (Isolated Forks):
Some things simply cannot be guessed. You can't know if a file is corrupted or if a server is down until you actually try to open it. To handle this, AOSpec creates a "safe sandbox" or a parallel universe. It launches the risky action (like opening the file) in this isolated copy of the world. If the action is wrong, the sandbox is just thrown away, and the real world remains untouched. If the action is right, the system grabs the result and uses it immediately. This allows the system to "pre-play" dangerous or slow actions without the risk of crashing the real show.
The Double-Check (Joint Action–State Verification):
The biggest problem with guessing a long chain of future actions is that one small mistake ruins the whole chain. If you guess step 1, 2, and 3, and step 2 is wrong, steps 1 and 3 become useless. AOSpec avoids this by not guessing the whole chain. Instead, it only guesses the target action (the one that will save the most time) and checks if the "starting state" of the sandbox matches the real world. It's like checking if the stage is set correctly before the actor steps on it. If the stage matches, the pre-played action is valid. If not, the system discards the guess and starts fresh. This breaks the "accuracy vs. speed" trade-off, allowing the system to look far ahead without needing a perfect crystal ball for every single step in between.

What They Found

The researchers tested AOSpec on a wide range of tasks, from solving coding puzzles to managing complex computer systems, using different types of AI models and different speeds. They compared their method against existing techniques that only guessed actions or only guessed observations.

The results were clear:

Speed Boost: AOSpec reduced the total time it took to complete tasks by 11.8% to 32.5% on average.
Fixing the Slowest Moments: The biggest wins came in the "tail latency"—the slowest, most frustrating delays. For the slowest 1% of tasks (p99), AOSpec cut the waiting time by up to 42.8%.
Better at High Speeds: As the AI's thinking speed increased (from 20 milliseconds per word down to 1 millisecond), the benefits of AOSpec grew even larger. This is because the faster the AI thinks, the more time is wasted waiting for the tools, and AOSpec is best at hiding that waiting time.
No Retraining Needed: The system worked just as well on a completely new set of tasks (SWE-bench) without needing to be retrained, showing that the method is robust and general.

Why It Matters

This paper suggests that the future of fast AI agents isn't just about making the AI think faster, but about making the whole loop of thinking and doing more efficient. By combining smart guessing with safe, parallel testing, AOSpec shows that we can hide the "waiting room" time of AI agents, making them feel instant and responsive even when they are doing heavy, complex work. It proves that you don't have to choose between speed and accuracy; with the right safety nets, you can have both.

Technical Summary: AOSpec – Action and Observation Co-Speculation for Low-Latency Agent Serving

1. Problem Statement

Large Language Model (LLM) agents increasingly rely on stateful tools that inspect or modify evolving runtime environments. In standard agent loops, model generation and tool execution are serialized: the agent must generate an action, wait for the environment to execute it and return an observation, and then generate the next step. As model decoding speeds accelerate (e.g., via specialized hardware), the time spent waiting for tool execution becomes the dominant bottleneck in end-to-end latency.

Existing speculation techniques attempt to break this serialization but face three fundamental barriers when applied to heterogeneous, stateful workloads:

Latency Concentration: A small fraction of tool calls (approx. 17%) accounts for the vast majority of tool time (approx. 97%). Speculation methods optimized for hit rate (accuracy) often miss these high-value, slow calls, failing to hide significant latency.
Environment Dependence: Many critical observations depend on hidden environment states (e.g., file contents, process outputs) that cannot be reliably predicted from the agent's context alone. Pure observation speculation fails here, while pure action speculation risks corrupting the committed environment if predictions are wrong.
Lookahead-Accuracy Tradeoff: Extending the speculation horizon to hide more latency typically requires predicting a full chain of future actions. However, the probability of an entire chain being correct collapses multiplicatively with depth, rendering long-range speculation ineffective.

2. Methodology: AOSpec

AOSpec is a lossless framework that jointly co-speculates actions and observations across the full agent–environment loop. It operates within a disaggregated agent architecture where the actor (LLM) and the environment runtime are decoupled. The framework employs three core mechanisms:

2.1 Expected Value Decoding (EVD) for Observation Speculation

To address latency concentration, AOSpec moves beyond optimizing for hit rate. Instead, it uses Expected Value Decoding (EVD) to select observation candidates that maximize expected time hidden.

Mechanism: EVD constructs a candidate set of potential observations and ranks them by the product of their predicted probability and their estimated tool execution time ( $V_o(c) = p(c) \cdot \hat{T}(c)$ ).
Execution: While the actual tool execution is pending, the agent generates continuations based on these high-value speculative observations. If the actual observation matches a draft, the agent continues without waiting; otherwise, the draft is discarded, and generation resumes from the true observation.
Training: A small observation model can be fine-tuned on historical traces to improve prediction accuracy, though the framework can operate with off-the-shelf models if sufficient candidate width is provided.

2.2 Isolated Action Execution for Environment-Dependent Outcomes

For observations that cannot be predicted due to hidden environment states, AOSpec launches speculative actions in isolated sandbox forks.

Mechanism: Latency-critical target actions are executed in parallel within isolated environments (using copy-on-write filesystems and process forking). This allows the system to obtain the actual observation early without risking the committed state of the main agent loop.
Safety: If the speculative action is incorrect, the fork is discarded, and the main loop executes the action from the committed state, ensuring lossless semantics.

2.3 Joint Action–State Verification (JASV)

To overcome the lookahead-accuracy tradeoff, AOSpec replaces the requirement for a full-chain prediction match with Joint Action–State Verification.

Mechanism: A speculative fork is only validated and reused if two conditions are met: (1) the speculative action matches the action emitted by the actor, and (2) the environment state at the time of the fork's launch matches the current committed environment state.
Benefit: This allows the system to speculate on a target action far in the future without needing to correctly predict the intervening actions. As long as the environment state remains stable, the "runway" for overlap is extended without the multiplicative error accumulation of full-chain prediction.

3. Key Contributions

The paper makes three primary contributions:

Characterization of Barriers: It quantifies the latency concentration, information boundaries of observation prediction, and the tension between lookahead depth and prediction accuracy in stateful agent workloads.
AOSpec Framework: It introduces a lossless co-speculation framework combining EVD (for latency-aware observation drafting), isolated action execution (for environment-dependent outcomes), and JASV (for lossless long-range lookahead).
Empirical Validation: It demonstrates significant latency reductions across diverse benchmarks, models, and serving speeds, showing that the approach scales as decoding accelerates.

4. Experimental Results

The authors evaluated AOSpec using trace replay on Terminal-Bench 2.0 (spanning four harnesses and five actor models) and SWE-bench Verified.

Latency Reduction: AOSpec reduced mean end-to-end latency by 11.8% to 32.5% across various configurations. The gains increase as the model's time-per-token (TPOT) decreases (i.e., as decoding gets faster), reaching a 32.5% reduction at 1 ms TPOT.
Tail Latency: The framework significantly improved tail latency, reducing p99 latency by up to 42.8%. This aligns with the finding that a few slow calls dominate total latency.
Baselines: AOSpec outperformed all practical baselines, including:
- Speculative Actions (predicting next actions only).
- SpecHop (speculative observation via caching or LLM drafting).
- Oracle-action (one-step action speculation ceiling).
- In 41 of 45 configurations, AOSpec exceeded the one-step action oracle ceiling by leveraging cross-step action lookahead and observation speculation.
Generalization: An observation model trained solely on Terminal-Bench traces transferred to SWE-bench Verified without retraining, achieving 18.9% latency savings at 1 ms TPOT.
Ablation: The combination of observation and action speculation yielded 17.0% savings at 10 ms TPOT, compared to 12.0% and 7.1% for observation-only and action-only respectively.

5. Significance and Claims

The paper claims that AOSpec represents a shift in how agent serving latency is optimized. By moving from hit-rate optimization to expected value optimization and replacing full-chain prediction with state-verified target action lookahead, the framework unlocks long-range overlap without sacrificing serial semantics.

The authors assert that as model decoding continues to accelerate, the bottleneck will increasingly shift to environment execution. AOSpec addresses this by treating the agent-environment loop as a unified system for speculation, effectively hiding tool execution latency through a lossless, co-speculative approach. The results suggest that co-speculating model outputs and stateful environment execution is a viable and effective strategy for low-latency agent serving.