Skip to content

Speculate with Memory: Lossless Acceleration for LLM Agents

🕒 Published (v1): 2026-07-14 00:36 UTC · Source: Arxiv · link

Why this paper was selected

Chien-Sheng Wu (Salesforce AI); memory-augmented speculative execution gives lossless agent speedup; immediately buildable

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

Speculative execution for LLM agents—where a cheap model pre-launches the next step during idle time—is traditionally stateless, discarding all inter-task information. This paper augments the speculator with three online memory systems learned from past trajectories, achieving 19–39% relative accuracy improvement on action prediction and up to 2.5× on observation prediction, while preserving the lossless guarantee that incorrect predictions are discarded at zero functional cost.

Problem

Existing speculative execution methods for LLM agents treat every task independently: a speculator that has processed 500 prior customer-service interactions makes identical predictions to one that has seen none. Agent tasks exhibit strong regularity (recurring action sequences, domain-specific API call patterns), but no prior method retrieves contextually similar past trajectories or adapts to its own recurring prediction failures during deployment.

Method

The framework first taxonomizes speculation into three types based on which latency component is hidden: - Type 1 (action prediction): speculator predicts \(\hat{a}_{t+1}\) in parallel with the actor; a hit saves \(\min(\ell_{\text{env}}, \ell_{\text{LLM}} - \ell_{\text{spec}})\). - Type 2 (observation prediction): speculator predicts \(\hat{o}_t\) during environment processing; a hit saves \(\min(\ell_{\text{LLM}}, \ell_{\text{env}} - \ell_{\text{spec}})\). - Type 3 (chained): predicts both, saving up to \(\ell_{\text{LLM}} + \ell_{\text{env}}\).

Pre-launched work is restricted to side-effect-free operations (read-only API calls, page fetches, actor LLM calls with predicted inputs), ensuring losslessness.

Three complementary memory systems augment the speculator, all updated online after each completed task:

  1. Contrastive Transition Table: Indexed by action-type pairs \((a_i, a_j)\); maintains success counts \(n_{ij}^+\), failure counts \(n_{ij}^-\), and observed argument signatures per transition. Provides \(\text{Confidence}(a_i \to a_j)\) and \(\text{SuccessRate}(a_i \to a_j)\) to steer the speculator toward high-probability, high-success continuations.

  2. Episodic Memory: Stores trajectory segments \(e = (\text{context}, \text{actions}, \text{observation}, \text{arg\_sources}, \text{outcome}, \text{lesson})\) constructed entirely by rule-based heuristics (zero auxiliary LLM calls). At speculation time, the current context is embedded with text-embedding-3-small (1536-d) and top-\(k\) episodes are retrieved via cosine similarity (<50 ms). Miss episodes (predicted vs. actual action pairs) are also stored as negative examples.

  3. Confusion Tracker: Lightweight dictionary of (predicted_type, actual_type) co-occurrence counts; when a confusion pattern reaches ≥3 observations, it is injected as a hard constraint in the speculator's prompt.

Seven progressive ablation settings (Stateless → Confusion → Table → Episodic → Table+Episodic → Episodic+Miss → Full) are evaluated with \(k=3\) parallel speculator instances per setting.

Key Contributions

  • Three online memory systems (contrastive transition table, episodic memory with miss-episode recording, confusion tracker) that accumulate experience from past agent trajectories without auxiliary LLM inference overhead.
  • A unified three-type taxonomy of speculative execution (action, observation, chained) that maps prediction targets to specific latency components in the agent-environment loop.
  • Evaluation across 6 benchmarks (WebArena, VWA, ALFWorld, PDDL, τ²-bench, HotpotQA) and 3 speculation types showing consistent, statistically significant improvement (McNemar's test, \(p < 0.001\)) over stateless baselines.
  • Demonstration that memory gains are model-agnostic across speculator models ranging from GPT-4.1-mini to GPT-5.4-nano.
  • Live latency validation on HotpotQA (892 s saved over 19,024 s baseline) and ALFWorld (44.9% observation hit rate), confirming that offline replay accuracy predicts real-world savings.

Results

  • WebArena (Type 1): Episodic+Miss 23.7% vs. Stateless 19.8% (+3.9 pp; +19.7% relative).
  • VWA (Type 1): Episodic 17.4% vs. Stateless 12.5% (+4.9 pp; +39.2% relative).
  • ALFWorld (Type 2): Full 40.0% vs. Stateless 16.3% (+23.7 pp; 2.5× relative); miss-episode addition (Episodic→Episodic+Miss) alone yields +14.8 pp.
  • PDDL (Type 2): Full 33.8% vs. Stateless 17.6% (+16.2 pp; 1.9×); Episodic→Episodic+Miss yields +14.0 pp, the largest single-component gain across all benchmarks.
  • τ²-bench (Type 3): Full 19.9% vs. Stateless 12.7% (+7.2 pp).
  • HotpotQA (Type 3): Full 27.5% vs. Stateless 20.5% (+7.0 pp).
  • Model sensitivity: Stateless-to-best delta is consistent across GPT-4.1-mini, GPT-5.4-mini, and GPT-5.4-nano; GPT-5.4-nano achieves competitive deltas at 0.6× the cost of GPT-4.1-mini.
  • Live HotpotQA: 40.0% hit rate across 610 steps; 1.05× analytical speedup, 892 s saved.
  • Live ALFWorld: 44.9% observation hit rate across 1,638 steps; measured savings track offline replay predictions from â„“_env = 2 s to 20 s.
  • Speculator cost is 1–2 orders of magnitude less than actor cost; net benefit at any accuracy above ~5%.

Limitations

  • Speculator latency (~2.7 s on ALFWorld) consumes most of the latency window when \(\ell_{\text{env}} < 3\) s, reducing practical savings below the theoretical upper bound.
  • API latency variance causes individual speculator calls to occasionally exceed the environment delay even when median latency is within the window.
  • Correct predictions on the final step of a task yield no savings (no subsequent action to pre-launch).
  • Memory benefits are domain-dependent: gains are large for tasks with repetitive action patterns (Type 2, embodied) but modest for diverse action spaces (Type 1, web navigation).
  • Confusion tracker slightly hurts ALFWorld accuracy (−0.3 pp Stateless→Confusion) where prediction errors are non-systematic, indicating the component can introduce noise in high-entropy domains.
  • Retrieval requires embedding API access (OpenAI text-embedding-3-small), adding an external dependency and ~50 ms overhead per speculation step.
  • Absolute accuracy remains low (17–40%), though this is inconsequential for lossless speculation where only hit rate—not recall—matters for latency savings.

Relevance to Agentic AI / LLM Agents

This paper directly addresses inference-time latency in interactive LLM agent pipelines, a critical bottleneck as agents are deployed in customer-facing and real-time settings. The memory augmentation framework connects to the broader research thread on agent memory systems (episodic, procedural, and semantic), demonstrating that online learning from past trajectories can improve operational efficiency without modifying the actor or compromising trajectory fidelity. The three-type speculation taxonomy also provides a clean abstraction for reasoning about where idle time exists in the agent-environment loop, which is applicable to any tool-calling agent regardless of domain. The lossless guarantee makes this directly composable with any existing agent framework without risk of behavioral divergence.