1 Introduction↩︎

Large language model (LLM) agents interact with external environments through tool calls, browser actions, and physical commands, where each step incurs latency from both the LLM inference and the action execution. In interactive settings such as customer service, web navigation, and embodied control, this sequential latency accumulates and directly affects user experience. Speculative execution addresses this bottleneck by using a smaller, faster model to predict the agent’s next action and pre-launch it before the agent commits [1]. The idea draws on speculative execution in processor architecture and speculative decoding in LLM inference [2]. If the prediction is correct, the result is already available and latency is hidden. If incorrect, the pre-launched work is discarded at no functional cost. However, most speculative execution methods for LLM agents are stateless, treating every task independently. Recent work mines tool-calling patterns offline [3], but no existing method retrieves contextually similar past trajectories or adapts to its own prediction failures during deployment. A customer-service speculator that has processed 500 prior interactions makes the same predictions as one that has seen none. Yet agent tasks exhibit strong regularity. The same action sequences recur across episodes: looking up a user followed by retrieving their order in customer service, or navigating to a shelf followed by picking up a mug in household tasks. A system that remembers these patterns should predict more accurately over time.

We augment the speculator with structured memory that accumulates online from past agent trajectories. Drawing on recent advances in agent memory systems [4]–[6], we equip the speculator with three complementary components that capture aggregate workflow patterns, retrieve contextually similar past episodes as in-context examples, and correct recurring prediction errors. While the actor is busy, the speculator predicts the outcome and pre-launches the next step along each predicted branch. When the actor’s real output arrives, the system checks whether any speculative branch matches. On a hit, the pre-launched work is already complete, so the agent advances immediately instead of issuing a fresh blocking call. On a miss, the speculative work is discarded and execution proceeds normally, so the actor’s trajectory is identical to non-speculative execution. Pre-launched work is restricted to side-effect-free operations (LLM calls, read-only API queries, page fetches), ensuring that incorrect predictions never produce irreversible changes and preserving the lossless guarantee (2.1). Only pre-launchable predictions, those whose execution can overlap with and hide latency, translate into wall-clock savings. We evaluate seven progressive memory settings on six benchmarks spanning web navigation [7], [8], embodied control [9], planning [10], customer service [11], [12], and multi-hop QA [13].

Memory-augmented speculation consistently outperforms the stateless baseline across all six benchmarks. The magnitude varies by speculation type: 19–39% relative improvement on action-prediction tasks and up to \(2.5\times\) on observation-prediction tasks with structured action spaces. 1 (left) illustrates the mechanism. During environment idle time (API calls, user responses, page loads), the speculator predicts the next output and pre-launches it. Memory of past trajectories increases the hit rate. 1 (right) shows the estimated latency reduction on ALFWorld over 120 episodes. Each correct speculation hides the latency of one actor LLM call, and the memory-augmented speculator improves from \(\sim\)​28% to over 50% as it accumulates experience, while the stateless baseline remains flat. The improvements are model-agnostic and generalize across speculator models of varying capability and cost, and the optimal memory configuration varies by domain. Our contributions are as follows:

• We augment speculative execution for LLM agents with three complementary memory systems that accumulate experience from past trajectories: a contrastive transition table, an episodic memory with miss-episode recording, and a confusion tracker.

• We identify three speculation types based on where latency falls in the agent-environment loop, unifying prior work under a single framework.

• We evaluate seven progressive memory settings across six benchmarks and three speculation types, showing consistent improvement over stateless speculation, with the largest gains on observation-prediction benchmarks with structured action spaces (up to \(2.5\times\)).

2 Speculate with Memory↩︎

2.1 Speculation Framework↩︎

Consider an LLM agent interacting with an environment in a turn-based loop. At each turn \(t\), the agent observes state \(s_t\), comprising the conversation history and environment feedback, and selects an action \(a_t = (\textit{type}, \textit{args})\) via an LLM call with latency \(\ell_{\text{LLM}}\). The environment returns observation \(o_t\) with latency \(\ell_{\text{env}}\), which encompasses waiting for API responses, user input, or environment state computation. A speculator is a smaller, faster model that predicts future outputs in this loop. Let \(\ell_{\text{spec}}\) denote the speculator’s inference latency. Depending on the prediction target, the speculator runs either during environment processing or in parallel with the actor. In both cases, its cost is fully hidden because it overlaps with ongoing computation. With \(k\) parallel speculators, a best-of-\(k\) strategy succeeds if any single prediction matches.

What to predict, and what latency is saved on a hit, depends on the structure of the agent-environment loop. We identify three speculation types. In action prediction (Type 1), the speculator predicts the agent’s next action \(\hat{a}_{t+1}\) in parallel with the actor. On a hit, the predicted action was already pre-launched, saving up to \(\ell_{\text{env}}\). The realized saving is \(\min(\ell_{\text{env}},\; \ell_{\text{LLM}} - \ell_{\text{spec}})\) since the speculator must finish within the actor’s \(\ell_{\text{LLM}}\) window to pre-launch. In observation prediction (Type 2), the speculator predicts the environment’s next observation \(\hat{o}_t\) during environment processing. On a hit, the actor’s next LLM call was already pre-started with the predicted observation, saving up to \(\ell_{\text{LLM}}\). The realized saving is \(\min(\ell_{\text{LLM}},\; \ell_{\text{env}} - \ell_{\text{spec}})\). Therefore, Type 2 is most effective when environment feedback is slow relative to the speculator, such as in robot execution, user input delays, or heavy API calls. In chained prediction (Type 3), the speculator predicts both the observation and the next action during environment processing, chaining Type 2 and Type 1 in a single round. On a full hit, both the actor call and the action are pre-computed, saving up to \(\ell_{\text{LLM}} + \ell_{\text{env}}\). In all cases, the saving approaches its upper bound when \(\ell_{\text{spec}} \ll \ell_{\text{window}}\), which motivates using a smaller, faster speculator model. 2 (left) illustrates the three types. The choice of type is determined by which steps incur significant latency and whether the environment’s response is tractable to predict.

A correct prediction is useful only if the predicted work can be safely initiated before verification completes. For Type 2, the pre-launched work is an actor LLM call with predicted input. This is always safe since no environment state is modified. For Types 1 and 3, the pre-launched work is action execution, which is safe only for read-only actions such as API queries, page navigations, and database reads. Write actions with irreversible side effects are excluded. In practice, each benchmark defines a static whitelist of read-only action types derived from its API schema or action space. The speculator’s predicted action type is checked against this whitelist before pre-launching. In all cases, we require a full exact match. Both the action type and all parameters must agree, because wrong parameters cannot be safely pre-launched.

2.2 Memory Systems↩︎

We equip the speculator with three complementary memory systems that learn from past agent trajectories (2, right): a contrastive transition table, an episodic memory, and a confusion tracker.

2.2.0.1 Contrastive Transition Table.

Agent trajectories contain reusable action patterns [4], [14], [15]. We capture these in a transition table \(\mathcal{T}\) indexed by action-type pairs \((a_i, a_j)\). For each observed transition in a completed trajectory \(\tau = [(a^{(1)}, \text{args}^{(1)}), \ldots, (a^{(n)}, \text{args}^{(n)})]\) with outcome label \(y \in \{+, -\}\), we record:

\[\begin{align} \forall\; 1 \le t < n: \quad & n^{y}_{a^{(t)}, a^{(t+1)}} \mathrel{+}= 1, \text{ArgSig}(a^{(t)}, a^{(t+1)}) \mathrel{\leftarrow} \text{ArgSig}(a^{(t)}, a^{(t+1)}) \\ & \qquad \cup \{\text{sorted\_keys}(\text{args}^{(t+1)})\} \end{align}\]

where \(n^{+}_{ij}\) and \(n^{-}_{ij}\) are success and failure counts, and \(\text{ArgSig}\) accumulates the sorted parameter names observed for action \(a_j\) when preceded by \(a_i\) (e.g., order_id,reason). The table provides transition confidence and per-transition success rate:

\[\text{Confidence}(a_i \to a_j) = \frac{n^{+}_{ij} + n^{-}_{ij}}{\sum_k (n^{+}_{ik} + n^{-}_{ik})} \qquad \text{SuccessRate}(a_i \to a_j) = \frac{n^{+}_{ij}}{n^{+}_{ij} + n^{-}_{ij}}\]

Storing success and failure counts separately provides a contrastive signal. This is motivated by work showing that contrasting successful versus failed trajectories yields richer learning signals [5], [6], and enables the speculator to prioritize high-confidence, high-success-rate continuations. The table is fundamentally unconditional: it captures \(P(\text{next\_action} \mid \text{current\_action})\) but not the dependence on conversational context or specific argument values.

2.2.0.2 Episodic Memory.

To capture context-dependent patterns that the transition table misses, we store full trajectory segments from past episodes in an episodic memory \(\mathcal{E}\) [4], [16]–[18]. Each episode \(e\) is a trajectory segment from a completed task:

\[e = (\textit{context}, \textit{actions}, \textit{observation}, \textit{arg\_sources}, \textit{outcome}, \textit{lesson})\]

where context is a natural-language summary of the agent’s current situation, actions is the list of actions with full arguments, observation is the environment response, arg_sources maps each argument value to its provenance by substring matching against prior tool observations, outcome indicates task success, and lesson is a takeaway auto-generated from episode metadata via template rules. All episode fields are constructed by rule-based heuristics without auxiliary LLM calls, meaning memory updates add zero inference latency. At speculation time, the current context is embedded using OpenAI’s text-embedding-3-small model (1536 dimensions) and the top-\(k\) most similar episodes are retrieved via cosine similarity, providing the speculator with structured examples of similar past situations. The only retrieval-time API call is this embedding query (\(<\)​50 ms), which runs during environment idle time alongside the speculator. We also record speculation-miss episodes [6], [19] that store the predicted versus actual action, giving the speculator explicit examples of its own past errors. Finally, retrieval-time pruning inspired by Evo-Memory [20] did not improve accuracy and is omitted from our reported results (see Appendix 7.8).

2.2.0.3 Confusion Tracker.

The confusion tracker identifies recurring prediction errors [5], [21]. After each speculation verification, we record the (predicted_action_type, actual_action_type) pair. When a specific confusion pattern is observed \(\ge 3\) times, it is surfaced as a hard constraint in the speculator’s prompt, explicitly instructing the speculator to avoid the confused action type. Unlike episodic memory, which requires embedding retrieval, the confusion tracker is a lightweight dictionary of counts that provides immediate feedback as patterns cross the threshold.

All three memory systems are updated online after each completed task, so subsequent speculations benefit from accumulated experience. Speculation itself never affects the actor. The actor sees identical context regardless of prediction outcomes. Correct predictions use the cached result. Incorrect ones are discarded and execution proceeds normally, preserving the trajectory exactly as it would be without speculation.

3 Experiments↩︎

3.1 Setup↩︎

We evaluate on six benchmarks spanning four agent modalities: customer service, web navigation, embodied tasks, and multi-hop question answering (1). The benchmarks are grouped by speculation type: two benchmarks per type.

3.1.0.1 Benchmarks.

Type 1 (action prediction): WebArena [7] tests web navigation across shopping, forum, and content management sites using 812 tasks. VisualWebArena (VWA) [8] extends WebArena with visual grounding on 910 tasks. Type 2 (observation prediction): ALFWorld [9] is a household task benchmark with a discrete 13-verb action space over 134 valid_unseen episodes. PDDL planning tasks [10], [22] require agents to navigate grid worlds and solve structured puzzles across 60 tasks. Type 3 (chained prediction): \(\tau^{2}\)-bench [12] is a dual-control customer-service benchmark; we use both the retail and airline domains, totaling 164 tasks. HotpotQA [13] is a multi-hop question answering benchmark where a ReAct agent [23] iteratively searches Wikipedia over 300 tasks.

3.1.0.2 Evaluation.

Each speculation type determines the evaluation metric. For Type 1, we evaluate read-only action full match; for Type 2, observation exact match. For Type 3, the speculator predicts the environment response and then the agent’s next action; we use action full match as the primary metric since it determines pre-launchability. We report aggregate accuracy: total correct steps divided by total steps, pooled across all tasks. For \(\tau^{2}\)-bench, we exclude turn 0 from the denominator since the user’s identity is initially unknown.

3.1.0.3 Models.

Actor trajectories are collected once and replayed, eliminating actor variance across settings and isolating API costs to the speculator. The actor model is GPT-5.4 for ALFWorld, PDDL, \(\tau^{2}\)-bench, and HotpotQA, and GPT-5-mini for WebArena and VWA. The primary speculator is GPT-4.1-mini. We also leverage LLMs for visualization of experimental results.

3.1.0.4 Ablation settings.

We evaluate seven progressive memory settings, all running in parallel during environment idle time with \(n=3\) speculator instances per setting: (1) Stateless: conversation history only, no memory; (2) Confusion: adds confusion pattern constraints. To build cumulatively, all subsequent settings include this confusion tracking as a base layer: (3) Table: adds transition table statistics; (4) Episodic: replaces the table with retrieved past episodes to isolate retrieval effects; (5) Table+Episodic: combines table and episodic memory; (6) Episodic+Miss: identical to Episodic but adds speculation-miss episodes; (7) Full: all components combined. A best-of-\(k\) evaluation checks whether any instance predicted correctly. The prediction targets match the speculation types: Type 1 predicts actions, Type 2 predicts observations, and Type 3 chains both.

3.2 Main Results↩︎

3.5pt

2 summarizes speculation accuracy across all six benchmarks and seven ablation settings at \(k\)=1. Memory-augmented speculation improves over the Stateless baseline on every benchmark, with the best setting varying by domain and speculation type.

3.2.0.1 Type 1: Action prediction (WebArena, VWA).

On WebArena, Episodic+Miss achieves 23.7% read-only full match accuracy, +3.9 pp absolute over Stateless at 19.8%. The confusion tracker, transition table, and episodic memory each contribute, with the Stateless\(\to\)Confusion step at +1.6 pp and Table\(\to\)Episodic swap at +1.5 pp providing the largest incremental gains. Miss episodes add only +0.3 pp, indicating that web navigation errors are less systematic than those on embodied tasks. On VWA, Episodic achieves 17.4%, +4.9 pp over Stateless. The confusion tracker alone provides +2.8 pp, the largest single-step gain. Adding the transition table on top of episodic memory decreases accuracy by 0.8 pp, reinforcing that episodic memory alone is preferable when action spaces are diverse.

3.2.0.2 Type 2: Observation prediction (ALFWorld, PDDL).

On ALFWorld, Full achieves 40.0%, \(2.5\times\) the Stateless baseline at 16.3%. This is the largest relative improvement across all benchmarks, reflecting ALFWorld’s highly repetitive action sequences. Isolating each component’s contribution, miss episodes provide the largest gain at +14.8 pp when added to Episodic (Episodic\(\to\)Episodic+Miss, 23.8\(\to\)​38.6%), episodic memory adds +7.8 pp over Confusion alone (Confusion\(\to\)Episodic, 16.0\(\to\)​23.8%), and the transition table adds +3.5 pp (Confusion\(\to\)Table, 16.0\(\to\)​19.5%). On PDDL, Full achieves 33.8%, \(1.9\times\) Stateless. Failure learning dominates. Adding miss episodes to Episodic yields +14.0 pp (Episodic\(\to\)Episodic+Miss, 19.0\(\to\)​33.0%), the largest single-component gain across all benchmarks, suggesting that planning tasks generate highly systematic prediction errors that miss episodes effectively correct.

3.2.0.3 Type 3: Chained prediction (\(\tau^{2}\)-bench, HotpotQA).

On \(\tau^{2}\)-bench, Full achieves 19.9%, +7.2 pp over Stateless. Each memory component contributes positively: confusion adds +0.4 pp, the transition table adds +2.1 pp over confusion (Confusion\(\to\)Table, 13.1\(\to\)​15.2%), and adding episodic memory on top of the table yields a further +2.4 pp (Table\(\to\)Table+Episodic, 15.2\(\to\)​17.6%). On HotpotQA, Full achieves 27.5%, +7.0 pp over Stateless. The gain is driven by action prediction, which requires structural reasoning about when to search, look up, or finish. These are exactly the workflow patterns that episodic memory captures.

Across benchmarks, each memory component has a distinct profile. The confusion tracker helps on five of six benchmarks, with the largest effect on VWA (+2.8 pp), but slightly reduces accuracy on ALFWorld where prediction errors are less systematic. The transition table benefits embodied benchmarks with regular action sequences and also helps on \(\tau^{2}\)-bench (+2.1 pp), though its gains are smaller than episodic memory on most benchmarks. Episodic memory provides consistent gains across all benchmarks by supplying argument values and observation templates from similar past situations. While the best memory settings achieve 17–40% accuracy depending on the benchmark, which may appear low in isolation, speculative execution is lossless. Incorrect predictions are discarded at zero functional cost, meaning only the hit rate matters. At 20% accuracy on a benchmark with \(\ell_{\text{hit}} = 7\) s, memory hides \(\sim\)​140 s of latency per 100 steps compared to non-speculative execution, and \(\sim\)​50 s more than the stateless baseline. The cost-benefit analysis in 4.3 quantifies these savings across all benchmarks. The speculator call is one to two orders of magnitude cheaper than the actor, so speculation yields a net benefit at any accuracy above \(\sim\)​5%.

4 Analysis↩︎

4.1 Experience Accumulation↩︎

3 plots cumulative accuracy as tasks accumulate across all six benchmarks, comparing the stateless speculator against the best-performing memory setting per benchmark. The accumulation effect varies by speculation type. On Type 2 benchmarks, where repetitive action sequences provide reusable patterns, accuracy grows steadily with experience. On ALFWorld, memory quickly climbs to \(\sim\)​40% and stabilizes, while Stateless stays flat around 16%. On PDDL, memory rises from \(\sim\)​24% to 34% in the second half, while Stateless remains below 18%. On Type 1 benchmarks, memory maintains a consistent 3–5 pp advantage throughout without a strong upward trend, indicating that gains come primarily from the memory content itself rather than continued accumulation. On Type 3 benchmarks, memory maintains a consistent advantage on \(\tau^{2}\)-bench, reaching 19.9% vs.% for Stateless. HotpotQA shows a growing gap, with Full reaching 27.5% vs.% for Stateless, driven by action-pattern recognition rather than accumulating observation examples. Results are generally robust to task presentation order, with the Stateless baseline varying by at most 1.6 pp and the top-ranked setting shifting only on benchmarks with smaller evaluation sets (see Appendix 7.3).

4.2 Speculator Model Sensitivity↩︎

3 compares three speculator models of varying capability and cost. We omit GPT-5.4-mini for WebArena and VWA because its capability is comparable to their actor model, GPT-5-mini. The central finding is that memory improvement is model-agnostic. The Stateless-to-best delta is consistent across all tested models, ranging from +2–7 pp on \(\tau^{2}\)-bench and HotpotQA to +16–27 pp on ALFWorld and PDDL. Model capability primarily affects observation prediction, where GPT-5.4-mini improves over GPT-4.1-mini by +11 pp on ALFWorld and +18 pp on PDDL. The cheapest model, GPT-5.4-nano at \(0.6\times\) the cost, achieves competitive memory deltas across all benchmarks, making it a highly cost-effective speculator.

4.3 Latency Analysis↩︎

4.3.0.1 Cost and theoretical savings.

The speculator LLM call is one to two orders of magnitude cheaper than the actor across all benchmarks.¹ For Types 2 and 3, each speculation additionally pre-launches an actor call, but on a hit the pre-launched result substitutes for the next step’s actor call, so the net expected additional cost is \(k \cdot C_{\text{S}} + (1 - \text{acc}) \cdot C_{\text{act}}\). 6 in Appendix 7.4 reports the full cost-latency breakdown per 100 steps for all six benchmarks.

4.3.0.2 Live validation.

To validate that replay-measured accuracy translates to real-world savings, we run the actor and speculator live on the 300 tasks of HotpotQA and 134 episodes of ALFWorld, recording per-step latencies alongside prediction accuracy. On HotpotQA, the GPT-5.4 actor has an overall median latency of 4.9 s, whereas the GPT-4.1-mini speculator finishes in 1.7 s, yielding a \(\sim\)​3 s head start per hit. The live action hit rate is 40.0% across 610 speculated steps, yielding a \(1.05\times\) analytical speedup and saving 892 s over a 19,024 s baseline. On ALFWorld, the actor has an overall median latency of 4.5 s and the speculator 2.7 s, with a 44.9% observation hit rate across 1,638 speculated steps. Because ALFWorld evaluates observation prediction, time savings depend on the environment feedback latency \(\ell_{\text{env}}\). As 4 (a) shows, the measured savings closely track the replay-based prediction across environment delays from 2 s to 20 s, confirming that offline accuracy reliably predicts online savings. However, three factors reduce these practical savings below the theoretical upper bound of an instant speculator. First, the 2.7 s median latency of the speculator itself consumes a portion of the delay window. At small delays where \(\ell_{\text{env}} < 3\) s, most of this window is spent executing the speculator rather than building a head start, as highlighted by the red annotation in 4 (a). Second, variance in API latency causes some individual speculator calls to exceed the environment delay even if the median time remains well within it. Third, successful predictions on the final step of a task cannot save time because there is no subsequent action to pre-launch. Together, these effects explain the gap between the theoretical upper bound and the measured performance, a gap that steadily diminishes as \(\ell_{\text{env}}\) increases.

4.4 Step-Depth Accuracy↩︎

Memory-augmented speculation maintains its accuracy advantage across step depths on all six benchmarks, as detailed in 8 of Appendix 7.7. The advantage is largest at early steps where workflow patterns are most predictable, but persists at later steps where episodic retrieval supplies relevant templates. 4 (b) connects accuracy to latency: the speculator remains near 1.7 s regardless of depth, whereas the actor varies from roughly 3 to 9.5 s. Consequently, each correct speculation at deeper steps saves more wall-clock time. As plotted on the right axis, the full memory setting maintains a consistent accuracy advantage over the stateless baseline at every depth. The combined effect of higher accuracy and a larger latency gap makes deeper steps particularly valuable targets for speculation.

5 Related Work↩︎

5.0.0.1 Speculative and parallel execution for agents.

Tool-using LLM agents [23]–[25] execute actions sequentially, making latency proportional to the number of tool calls. [1] propose Speculative Actions, predicting the agent’s next tool call during idle time with a stateless speculator. Other approaches target different bottlenecks: LLMCompiler [26] parallelizes independent calls within a single turn via a task-dependency DAG, which is complementary to our cross-turn speculation. SpecReason [27] and ConfSpec [28] apply speculative decoding at the internal reasoning-step level, whereas our work operates at the environment-action level. Most closely related is PASTE [3], which learns DAG-structured tool-calling patterns to guide speculation. Unlike PASTE, our approach retrieves contextually similar past trajectories with concrete argument values, learns from prediction failures online, and updates all memory dynamically during deployment.

5.0.0.2 Memory systems for agents.

A growing body of work equips agents with non-parametric memory updated from past trajectories. ExpeL [5] extracts insights by contrasting successful and failed trajectory pairs, while AWM [4] distills reusable action workflows from past episodes for retrieval at test time. Other systems store procedural abstractions [14], [15], full trajectories as exemplars [17], [18], [29], or reasoning strategies derived from success and failure [6]. Retrieval-augmented episodic memory [16], [30]–[32] and failure-aware learning [19], [21], [33] have similarly become foundational to agent design. Recent work also addresses memory curation: EvolveR [34] applies explicit distill, deduplicate, update, and filter operations, whereas Memory-R1 [35] and AgeMem [36] train RL controllers over memory management actions. Crucially, all these systems target the actor’s task performance; we apply this same family of techniques to improve the speculator’s prediction accuracy.

6 Conclusion↩︎

We presented memory-augmented speculative execution, which equips LLM agent speculators with three complementary memory systems to learn from past trajectories. Evaluation across six diverse benchmarks shows that structured memory consistently improves accuracy for all speculation types. The largest gains occur in observation prediction, where repetitive environment responses provide highly reusable patterns. These model-agnostic improvements vary by domain: Type 2 tasks benefit from continuous experience accumulation, while Type 1 tasks rely primarily on retrieving specific past content. Because speculation runs during environment idle time, these accuracy gains translate directly to measured latency reductions without adding wall-clock cost to the actor. However, combining all memory components is not always optimal, and unpredictable elements like page-specific UI indices still bottleneck absolute accuracy. Future work includes confidence-based memory routing, structure-aware web prediction, and broader production deployments.

7 Additional Results↩︎

7.1 Best-of-\(k\) Scaling↩︎

5 illustrates the accuracy scaling from \(k=1\) to \(k=3\) speculators across all six benchmarks. Two primary patterns emerge. First, increasing the number of speculators yields consistent gains across the board, ranging from a +1.4 pp increase for ALFWorld Stateless to +5.6 pp for HotpotQA Memory. Second, memory-informed settings generally benefit more from scaling than the stateless baseline on observation-prediction benchmarks. For instance, on ALFWorld, the Full setting gains +3.8 pp compared to +1.4 pp for Stateless. This divergence suggests that memory-guided predictions explore a more diverse set of plausible environment continuations rather than producing near-identical guesses.

7.2 Won vs.Lost Trajectory Split↩︎

4 analyzes speculation accuracy based on task outcome across five benchmarks; ALFWorld is omitted as all episodes were successful. Successful trajectories generally yield higher speculation accuracy, suggesting that they follow more predictable, standard patterns. This gap is most pronounced on HotpotQA, where successful tasks achieve 26.7% Stateless accuracy compared to 12.7% for failures, a \(2.1\times\) difference. This suggests that failed tasks involve more exploratory or erratic search behaviors that are inherently harder to speculate.

A similar trend holds for WebArena, VWA, and \(\tau^{2}\)-bench. PDDL is a slight outlier, showing marginally higher Memory accuracy on lost tasks (35.0% vs.% for won). However, the limited number of failures in PDDL (\(n=10\)) makes this estimate less reliable than the other benchmarks. Overall, the data confirms that speculation is most effective when the agent is on a successful, predictable path.

7.3 Ordering Effects↩︎

2.5pt

5 reports aggregate accuracy across three task orderings on all six benchmarks. Three primary findings emerge from this analysis.

7.3.0.1 Stability of the Stateless baseline.

The Stateless baseline is remarkably stable, varying by at most 1.6 pp across orderings on PDDL and by less than 1 pp on five of the six benchmarks. Since the Stateless setting uses no memory, this minor variation reflects only the inherent difference in predictability among specific task sequences within the benchmarks.

7.3.0.2 Bounded variation in memory settings.

Observation-prediction benchmarks (ALFWorld and PDDL) show the highest sensitivity to task ordering when memory is enabled. For instance, ALFWorld Full ranges from 38.0% in the grouped ordering to 42.4% when shuffled, representing a 4.4 pp spread. The grouped ordering, which clusters similar task types, likely produces less diverse episodic memory during the early stages of a run. Conversely, the shuffled ordering performs best on these benchmarks, suggesting that early exposure to a diverse set of examples improves the quality of subsequent episodic retrieval.

7.3.0.3 Rank shifts among top settings.

The optimal memory configuration is consistent for some benchmarks but shifts for others. On VWA, the Episodic setting is consistently best across all orderings, while the Full setting remains top-ranked for ALFWorld and PDDL. On WebArena, the top-ranked setting alternates between Episodic, Tbl+Epi, and Epi+Miss, though the absolute difference between these winners is less than 0.6 pp. On \(\tau^{2}\)-bench and HotpotQA, the best setting shifts more substantially, with specific configurations varying by up to 3.0 pp (e.g., HotpotQA Full). Despite these rank shifts, the Stateless-to-best gap remains positive across all orderings for every benchmark, confirming that memory-augmented speculation is robust to task presentation order.

7.4 Cost–Benefit Analysis↩︎

3.5pt

6 provides a per-benchmark cost-benefit breakdown. All values are normalized to 100 agent steps for direct comparison. The columns are constructed as follows. The wall-clock time saved per correct speculation, \(\ell_{\text{hit}}\), is determined by the speculation type as described in 2.1. For Type 1, \(\ell_{\text{hit}} = \ell_{\text{env}}\) represents the environment processing time saved by pre-launching the predicted action. These values are measured from trajectory timestamps, yielding 12.3 s for WebArena and 17.1 s for VWA, which includes visual processing overhead. For Type 2, \(\ell_{\text{hit}} = \min(\ell_{\text{LLM}},\; \ell_{\text{env}} - \ell_{\text{spec}})\). The table uses representative deployment latencies where \(\ell_{\text{env}} \approx 7\) s for embodied tasks. For Type 3, \(\ell_{\text{hit}} = \ell_{\text{LLM}} - \ell_{\text{spec}}\), representing the head start gained by the speculator finishing before the actor. \(T_{100}\) is the baseline total latency for 100 steps without speculation, computed from the actor latencies recorded during trajectory collection. \(C_{\text{act}}\) is the actor LLM cost for 100 steps, computed from token counts in the collected trajectories and the provider’s pricing (see footnote in 4.3). \(C_{\text{S}}\) and \(C_{\text{M}}\) are the speculator costs without and with memory context. Memory adds 200–500 extra input tokens per call, increasing cost by $0.01–0.02 per 100 steps. The Spec and +Mem columns show the estimated latency reduction calculated as \(\text{acc} \times \ell_{\text{hit}} \times 100\), where acc is the aggregate accuracy from 2.

Representative API latencies from our provider include \(\ell_{\text{LLM}} \approx 5\text{--}10\) s for GPT-5.4, \(\ell_{\text{spec}} \approx 1\text{--}3\) s for GPT-4.1-mini, and \(\ell_{\text{env}}\) ranging from less than 0.1 s for text simulators to approximately 17 s for VWA. The speculator call is \(10\text{--}70\times\) cheaper than the actor call, so speculation yields a net benefit at any accuracy above roughly 5%. Memory systems improve accuracy at negligible incremental cost because embedding retrieval adds less than 50 ms per turn.

7.5 All-Setting Learning Curves↩︎

3 in the main text compares the stateless baseline against the best-performing memory configuration for each benchmark. 6 plots all seven configurations to show the full performance progression as experience accumulates across the task sequence. On ALFWorld and PDDL, the configurations separate into two clear tiers. The Epi+Miss and Memory settings form an upper tier that diverges sharply from the remaining five settings after roughly 40 tasks. This separation demonstrates that learning from prediction failures is the dominant performance factor for observation-prediction benchmarks. On WebArena and VWA, all memory settings cluster more tightly. In these domains, Episodic retrieval provides the largest initial lift, while additional components offer diminishing returns. On \(\tau^{2}\)-bench, the Memory setting gradually pulls ahead of all other configurations during the second half of the trajectory. On HotpotQA, Tbl+Epi and Memory track closely throughout the run, and both outperform the other configurations by approximately 7 pp.

7.6 Per-Group Breakdown↩︎

7 details the per-group accuracy for the Stateless and Memory settings across all six benchmarks. On ALFWorld, the Memory setting improves accuracy across all six task types. The largest gains occur on Heat tasks with a +32.6 pp increase and Cool tasks with a +26.1 pp increase. These tasks feature repetitive action sequences that are highly amenable to learning from past trajectories. Similarly, on PDDL, Tyreworld benefits dramatically with a +33.7 pp gain, whereas Blockworld sees a more modest improvement of +6.4 pp because of its more variable state transitions. WebArena shows consistent improvement across all six websites, led by Reddit with a +4.3 pp absolute gain. VWA also shows moderate, uniform gains across its three site categories. On \(\tau^{2}\)-bench, the retail domain benefits substantially, achieving 25.2% accuracy with Memory compared to 18.2% for Stateless. The airline domain shows lower absolute accuracy due to its smaller training set and more diverse API patterns. On HotpotQA, comparison questions remain easier to predict than bridge questions for both settings, but Memory provides consistent gains for both types. These results on VWA and HotpotQA demonstrate that episodic retrieval provides stable benefits even across heterogeneous task groups.

7.7 Step-Depth Accuracy↩︎

8 illustrates how speculation accuracy evolves with step depth across all six benchmarks. On WebArena, accuracy is highest at step 0, where Memory reaches 56% compared to 40% for Stateless. Performance drops at step 2 as predictions shift from general navigational commands to more granular, element-specific interactions. ALFWorld maintains a consistent 15–20 pp advantage across all depths, indicating that the benefit of memory is not restricted to initial steps. On PDDL, the Memory setting achieves 37–43% accuracy at steps 1–3 while the Stateless baseline remains below 20%, a gap that persists through step 10. VWA displays a steady 3–5 pp Memory advantage across most depths. On \(\tau^{2}\)-bench, Stateless shows low initial accuracy, whereas Memory provides an 11 pp advantage at step 0 and peaks at 24.5% by step 2. Finally, HotpotQA exhibits a tighter separation, with Memory maintaining a 6–8 pp advantage during intermediate reasoning steps.

7.8 Episodic Memory Pruning↩︎

We explored three retrieval-time pruning passes inspired by Evo-Memory [20]. The first is a low-utility penalty that halves the similarity score for episodes from failed tasks where speculation was also incorrect. The second is redundancy deduplication, which removes candidates with an inter-episode cosine similarity above 0.92. The third is a miss-pattern penalty that reduces scores by \(0.7\times\) for episodes whose primary action is mispredicted in at least three instances. The pruning process over-fetches by a factor of \(3\times\) before filtering the results to \(k\) candidates.

Across all benchmarks, pruning did not meaningfully change accuracy. On ALFWorld, the Memory setting increased from 40.0% to 40.4% with pruning enabled, while other benchmarks showed similarly negligible effects. We attribute this to two factors. First, the episodic memory is relatively small, containing hundreds rather than thousands of episodes, so redundancy is not yet a significant bottleneck. Second, the miss-pattern penalty can inadvertently suppress useful episodes if a frequently mispredicted action type also appears in successful retrieved records. Consequently, all results reported in this paper use the configuration with pruning disabled.

7.9 Environment Delay Sensitivity (ALFWorld)↩︎

For Type 2 benchmarks, the speculator executes during the environment feedback window. While ALFWorld utilizes a text simulator with near-zero latency, target deployments such as household robotics involve physical execution delays. We measured actual actor and speculator latencies across all 134 episodes and analytically computed the speedup for a range of representative environment delays.

As shown in the table, absolute time saved grows monotonically with the environment delay, increasing from 39 s at a 2 s delay to 4,023 s at a 20 s delay. However, the speedup ratio peaks near \(\ell_{\mathrm{env}} = 10\) s. This occurs because larger delays inflate the baseline latency faster than the savings grow. The per-hit savings, defined as \(\min(\ell_{\mathrm{env}} - \ell_{\mathrm{spec}}, \ell_{\mathrm{actor}})\), are increasingly capped by the actor latency of the subsequent step rather than the environment delay window. In practical deployments, the environment latency is typically fixed by the hardware, making the speedup at that specific delay the relevant performance metric.

8 Limitations and Broader Impact↩︎

8.1 Element Index Prediction↩︎

The primary source of prediction error in web navigation benchmarks is element index prediction for click_element actions. Element indices are arbitrary, page-specific identifiers assigned by the accessibility tree parser. These indices frequently change across different pages, page loads, or even within a single session as dynamic content renders. Because the speculator lacks access to the target page’s DOM at the time of prediction, it cannot resolve which specific index corresponds to the intended element. This volatility fundamentally limits full-match accuracy on WebArena and VWA, where click_element accounts for the majority of read-only actions. Incorporating lightweight page-structure features, such as a compressed DOM skeleton or element-role embeddings, into the speculation context represents a promising direction to mitigate this bottleneck.

8.2 Memory Combination and Interference↩︎

The full memory configuration, which combines all three systems, underperforms simpler settings on benchmarks such as WebArena and VWA. For instance, adding the transition table to episodic memory on VWA reduces accuracy by 0.8 pp. This suggests that aggregate transition statistics can sometimes mislead the speculator when action spaces are highly diverse. More broadly, naively concatenating all memory signals into the speculator’s context can introduce redundancy, as episodic examples may already encode the relevant transition patterns, or conflicting guidance, such as when the transition table favors a frequent action that a miss episode explicitly warns against.

These observations motivate selective memory routing: a lightweight classifier or confidence-based mechanism that chooses the optimal memory configuration for each task or turn rather than always utilizing the full stack. Our evaluation of seven distinct settings provides the necessary training signal for such a router, as accuracy data for each configuration is available across various task types.

8.3 Speculator Variance↩︎

3.5pt

Each experiment utilizes three parallel speculators with identical prompts and temperatures. 7 reports the accuracy for the Stateless baseline and the best-performing memory configuration for each benchmark. In Type 1 and Type 2 benchmarks, three parallel speculators from the same execution show standard deviations ranging from 0.04 pp to 0.66 pp. For Type 3 benchmarks, three independent task orderings serve as replications to produce standard deviations between 0.29 pp and 1.23 pp. McNemar’s tests conducted over all evaluation steps confirm that the accuracy improvement from the Stateless baseline to the Memory setting is statistically significant across all six benchmarks with \(p < 0.001\). This test assesses whether the proportion of steps where memory succeeds but Stateless fails exceeds the reverse, providing a robust per-step significance assessment. Our replay-based evaluation protocol eliminates actor variance across settings because all configurations are evaluated against the identical actor trajectories. The \(s_0\) values in 7 correspond exactly to the primary results reported in 2.

8.4 Replay vs.Online Evaluation↩︎

Our replay-based design evaluates speculation accuracy in isolation. The speculator predicts against pre-recorded actor trajectories, ensuring that correct predictions do not actually accelerate the interaction or change the actor’s context during the evaluation. In a live deployment, however, correct speculations would reduce latency and potentially allow the actor to process more turns within a fixed time budget. This live feedback loop could be positive if faster interactions lead to more coherent trajectories, but it could also be negative if a changed temporal context invalidates the replay assumption. A live deployment study incorporating real API latencies is necessary to measure true end-to-end wall-clock savings and validate that the accuracy measured during replay translates to a proportional speedup in practice.

8.5 Broader Impact↩︎

Speculative execution for LLM agents is a latency-optimization technique that does not alter the agent’s final behavior because the actor’s decisions remain identical regardless of whether speculation is employed. The lossless guarantee ensures that incorrect predictions are silently discarded, introducing no new failure modes beyond those already present in the base agent. However, faster agent execution could amplify existing risks if the underlying agent is deployed in sensitive domains such as autonomous customer service or financial transactions without adequate safeguards. Because our memory systems store action-level trajectory data that could contain user information, production deployments should apply appropriate data retention policies and anonymization to the episodic memory store to protect user privacy.

9 Prompt Templates↩︎

9.0.0.1 Episodic memory format.

Retrieved episodes are formatted as structured tuples injected into the speculator’s context. The stored observation field (Eq. 4) is used for embedding-based retrieval but not surfaced in the prompt, as the speculator already has the current conversation context. The arg_sources field is folded into the action formatting:

— Example 1 (similarity=0.87) —
Situation: User asked to return items from order #W6247578.
Agent actions:
  get_order_details(order_id=#W6247578)
    order_id: from user message
Outcome: SUCCEEDED
Takeaway: Standard order lookup pattern after user provides order ID.

9.0.0.2 Speculation-miss episode format.

Miss episodes store the predicted versus actual action:

— Speculation miss (similarity: 0.82) —
Pattern: Speculator predicted click(7) but agent actually used click(12).
Context: Product listing page with multiple items.
—

9.0.0.3 Contrastive transition table format.

The transition table is serialized as a ranked list of next-action candidates with frequency and success rate, conditioned on the current action:

Historical patterns from 85 past tasks (71 success, 14 failure):
After get_order_details, the most likely next tools are:
  1. get_user_details — 42% of the time (success rate: 88%)
     typical args: order_id,user_id(63%)
  2. cancel_pending_order — 25% of the time (success rate: 72%)
     typical args: order_id,reason(91%)

Transitions to AVOID (high failure rate):
  - modify_pending_order — 12% of the time but only 33% success rate

For benchmarks using turn-level speculation (ALFWorld), get_full_context() provides the complete table rather than conditioning on a single action.

9.0.0.4 Confusion tracker format.

Confusion patterns exceeding the threshold are injected as hard constraints:

KNOWN PREDICTION ERRORS (avoid these):
- You predicted scroll_down 5 times when the agent actually used
click_element. Do NOT predict scroll_down in this context.

References↩︎

---

1. Pricing: GPT-4.1-mini $0.40/$1.60 per MTok (input/output); GPT-5.4 $2.50/$15.00 per MTok. Source: openai.com/api/pricing, May 2026.↩︎