Speculate with Memory: Lossless Acceleration for LLM Agents

Large Language Model (LLM) agents often suffer from high latency due to sequential dependencies between LLM inference and environment execution. Speculative execution mitigates this by using a smaller, faster model to predict and pre-launch the next step during environment idle time. However, traditional speculators are stateless, meaning they fail to learn from recurring patterns across tasks. This paper introduces a memory-augmented framework that enables speculators to accumulate experience from past agent trajectories, allowing them to improve their prediction hit rates over time.

The authors propose three complementary memory components that update online without adding inference overhead:

• Contrastive Transition Table: Tracks action-sequence statistics and success rates to identify high-confidence transitions.
• Episodic Memory: Stores past trajectory segments, allowing the speculator to retrieve contextually similar examples to guide current predictions.
• Confusion Tracker: Identifies and suppresses recurring prediction errors by treating frequently confused action pairs as hard constraints.

These components operate during the environment's idle time, ensuring that the speculator's work is fully hidden. If a prediction is correct, the agent saves time by using the pre-computed result; if incorrect, the work is discarded with no impact on the agent's final trajectory, maintaining a strictly lossless guarantee.

The approach was evaluated across six benchmarks covering web navigation, embodied control, planning, and multi-hop QA. The results demonstrate that memory-augmented speculation consistently outperforms stateless baselines. The most dramatic gains were observed in tasks with repetitive action spaces, such as ALFWorld, where accuracy increased by 2.5x. Because the speculation runs in parallel with existing idle time, these accuracy improvements translate directly into reduced wall-clock latency for the end user.