acceptodds
Under review as a conference paper at ICLR 2027

Speculate with Memory: Lossless Acceleration for LLM Agents

Abstract

Speculative execution accelerates large language model (LLM) agents by using a smaller, cheaper model to predict future actions or observations and pre-launch subsequent work. However, many existing speculators are stateless and cannot benefit from experience accumulated across tasks. We equip the speculator with three online memory components that learn from past agent trajectories: a contrastive transition table tracking action-sequence statistics, an episodic memory retrieving contextually similar segments, and a confusion tracker suppressing recurring errors. We evaluate this approach on six benchmarks spanning three speculation types: action prediction, observation prediction, and chained prediction. Compared with stateless speculation, memory augmentation improves action-prediction accuracy by approximately 20–39% and achieves up to 2.5 times the observation-prediction accuracy on benchmarks with repetitive structure. These benefits generalize across speculator models of varying cost, with further gains from memory accumulation in domains with recurring patterns. Predictions are verified before speculative results are reused, and pre-launched work is restricted to side-effect-free operations. This preserves the actor’s trajectory while reducing latency through overlap with ongoing computation.

Primary area:
foundation or frontier models, including LLMs
Keywords:
LLM agent, agent memory, speculative execution

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_W8eoOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper adds an online transition table, episodic retrieval, and a confusion tracker to an LLM-agent speculator, improving action, observation, and chained predictions while the actor or environment is busy. Six benchmarks compare progressive memory settings with adapted AWM and ReasoningBank baselines. Structured observation tasks show substantial gains: ALFWorld improves from 16.3% to 40.0%, while web-action gains are smaller. The paper also reports live latency traces and estimates potential execution savings. Its main contribution is an empirical study of speculator memory, alongside a proposed execution framework that reuses predictions only after verification.

Critical strengths
  1. The method lets the speculator learn from past trajectories while keeping the actor’s decision context unchanged. Transition statistics, episodic retrieval, and confusion tracking capture recurring workflows and prediction errors without modifying the actor.

  2. Across six benchmarks covering action, observation, and chained prediction, memory consistently improves prediction accuracy, especially in ALFWorld and PDDL. The ablations are informative: speculation-miss episodes drive much of the observation-prediction gain, while episodic retrieval outperforms the full configuration on VisualWebArena.

Critical weaknesses
  1. The acceleration evidence is modest and relies substantially on estimates. HotpotQA reports a 1.05× analytical speedup, while ALFWorld’s estimated savings assume environment delays despite near-zero feedback latency in its text simulator. Live actor/speculator timings are useful but do not establish integrated end-to-end gains. Substantial accuracy improvements therefore offer limited support for broader acceleration claims. Paired online comparisons should include actual delays and retrieval, verification, and scheduling overhead.

  2. The lossless guarantee needs clearer assumptions and validation. Exact action matching checks the operation and parameters, and a read-only whitelist limits side effects. Neither ensures that an early read returns the same observation at the actor’s original execution time. In changing environments, cached observations could alter later decisions despite an exact action match. The paper should specify and enforce observation-equivalence conditions and test changes between speculation and verification. This concern limits the general guarantee; it does not establish failures in the reported experiments.

Questions for authors

Can you report a paired end-to-end comparison of non-speculative, stateless speculative, and memory-based speculative execution on one benchmark with actual environment latency?

3 comments
AuthorsOpenReview ↗

Response to Reviewer W8eo

Thank you for identifying the distinction between prediction accuracy, integrated execution time and the conditions required for lossless reuse.

1. Online execution with actual environment latency

Can you report a paired end-to-end comparison of non-speculative, stateless speculative, and memory-based speculative execution on one benchmark with actual environment latency?

Following your suggestion, we evaluated non-speculative execution, stateless speculation and memory-based speculation on the same 80 tasks in each of WebArena's Reddit and Shopping domains, with actual browser execution, no injected delays, and averaged over three runs. We used a Qwen3-235B-A22B actor and Qwen3-32B speculator served through Bedrock, with k=3 for both speculative methods.

These Type 1 experiments pre-execute only eligible read-only navigations. Memory uses Episodic+Miss and updates after each completed task, starting from 20 prior tasks in both domains and using full-page pre-execution.

Domain     Arm                    Mean episode (s)   API USD/task
Reddit     None                         22.11          0.01016
Reddit     Stateless k=3                19.92          0.01168
Reddit     Memory k=3                   18.82          0.01203
Shopping   None                         55.27          0.02270
Shopping   Stateless k=3                45.69          0.02311
Shopping   Memory k=3                   42.90          0.02389

Memory's observed mean episode time was 5.5% lower than Stateless and 14.9% lower than None on Reddit. On Shopping, the differences were 6.1% versus Stateless and 22.4% versus None. Reported episode time includes retrieval, verification, scheduling and memory updates, but excludes setup, evaluation and cleanup. API cost excludes warm-start collection and infrastructure.

Realized savings depend on both prediction hit rate and the available overlap window (Section 2.1). We use WebArena for integrated browser execution; benchmarks such as ALFWorld and PDDL have fast simulated feedback with little environment waiting time. WebArena also showed a comparatively modest prediction gain in the original replay study (19.8% to 23.7%, +3.9 percentage points; Table 2). To examine broader timing conditions, Section 4.3 and Appendix A.9 combine measured model latencies with assumed environment delays, illustrating how sufficiently early predictions and longer overlap windows can hide more latency per correct prediction.

2. Observation equivalence and lossless reuse

In changing environments, cached observations could alter later decisions despite an exact action match.

Thank you for raising this concern. Section 2.1 describes the read-only whitelist and exact action-and-argument matching, while Appendix B.4 notes related risks from changing temporal context. We will formalize observation equivalence (state invariance of the read-only target within the short speculation window) as an explicit precondition for lossless reuse.

We conducted additional checks. On PDDL, a scripted Type-2 prototype comparing complete next-actor inputs rejected reuse in all 20 tested cases with relevant state changes. In an earlier HotpotQA online run, 240 of 242 adopted Search observations (99.2%) were identical when re-queried after task completion. The first is controlled validation of a gate; the second is evidence of observed stability, not an adoption-time equivalence guarantee.

In the revision, we will state this observation-equivalence precondition explicitly, specify how volatile or state-dependent endpoints are excluded from the read-only whitelist, and expand our limitations discussion for rapidly changing environments.

Thanks for the additional results. My concerns are mostly solved. I raised my rating to weak accept

Thank you for the update, and we appreciate the careful review.

Reviewer_15RAOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This work presents Speculate with Memory, a lossless speculative acceleration framework for LLM agents. Existing agent speculators are stateless: they discard cross-episode historical information and cannot learn from past prediction failures. The authors introduce three complementary online memory modules (Contrastive Transition Table, Episodic Memory, Confusion Tracker) for the speculator instead of the main actor. They unify three speculation paradigms: action prediction, observation prediction, and chained prediction. The memory system accumulates experience across finished tasks and retrieves relevant historical trajectories to boost speculation hit rate, while preserving the original behavior of the main actor to guarantee lossless execution. Only read-only, side-effect-free operations are permitted for pre-execution. Evaluations are conducted on six benchmarks covering web navigation, embodied simulation, planning, multi-hop QA and customer service. Experimental results show consistent gains in speculation accuracy across all domains, especially a 2.5× accuracy boost on ALFWorld. Real wall-clock latency tests and theoretical speedup analysis verify end-to-end acceleration, with larger gains when environment waiting latency is substantial.

Critical strengths
  1. Novel and well-motivated core idea. The insight of attaching memory to the speculator (rather than the main actor) is conceptually clean and correct. It avoids altering agent policy while reusing idle environment waiting time to improve speculation quality, which is a meaningful new direction for agent speculative execution.
  2. Strong empirical validation across diverse benchmarks with large accuracy improvements. The memory modules deliver substantial speculation hit-rate gains across six heterogeneous domains. The 2.5× accuracy improvement on ALFWorld is notable, and consistent positive gains hold across different speculator model sizes, showing the improvement is not limited to one specific setup. The paper is clearly written and easy to follow.
Critical weaknesses
  1. The discussion of speedup across different speculation types is insufficient. Although the paper unifies Type 1, Type 2 and Type 3 speculation under one framework, it lacks deep dissection of the distinct latency-reduction mechanism for each category. This gap becomes more noticeable given that most evaluations use API calls where raw round-trip delays are relatively stable. Whether the proposed memory-augmented speculation can push the accuracy/speed Pareto frontier also remains underexplored.
  2. The empirical evaluation is limited to GPT-family closed models. The findings’ generalizability would be strengthened if results on open-weight models such as Qwen or DeepSeek were included.
Questions for authors
  1. Figure 1 (right) demonstrates that memory yields substantial latency reduction compared to the stateless baseline. Memory introduces longer input context for the speculator. I would like the authors to report input and output token counts of the same underlying speculator model as episodes accumulate, to help explain the observed latency reduction.
  2. Most evaluated scenarios rely on API calls. From my experience, the raw delay between different API invocations tends to be relatively stable. Please clarify the distinct root causes of acceleration for the three speculation types separately. In addition, I am interested whether this memory-augmented speculation can push the accuracy/speed Pareto frontier.
  3. The current experiments are limited to GPT-family models, which makes empirical validation somewhat thin. I encourage the authors to add experiments with open-weight models such as Qwen or DeepSeek to strengthen the generality of their findings.
4 comments
AuthorsOpenReview ↗

Response to Reviewer 15RA (1/2)

Thank you for the constructive assessment. We address your concerns as follows.

1. Distinct sources of acceleration

Please clarify the distinct root causes of acceleration for the three speculation types separately.

As outlined in Section 2.1 and Figure 2, the three types exploit different opportunities to overlap computation and execution:

  • Type 1: action prediction. Predict the next action during actor inference, allowing an eligible read-only tool to start early.
  • Type 2: observation prediction. Predict the observation during tool execution, allowing the next actor call to start early.
  • Type 3: chained prediction. Predict both the observation and the subsequent action during tool execution, allowing the next actor call and eligible read-only tool execution to begin early.

Correct predictions that arrive early enough reduce sequential waiting, even when individual API response times are stable. Memory improves the prediction hit rate within these windows.

We will make these distinctions clearer in the revised paper. We also provide new online Type 1 measurements on WebArena with actual browser latency.

2. Tokens and latency as memory accumulates

I would like the authors to report input and output token counts of the same underlying speculator model as episodes accumulate, to help explain the observed latency reduction.

Thank you for this helpful suggestion. Section 2.2 describes top-k episodic retrieval, while Appendix C illustrates how retrieved examples and transition/confusion summaries enter the prompt. In these measurements, each prediction retrieved up to three regular episodes and two speculation-miss episodes; the entire episode store was not inserted into the prompt.

Using the same speculator model and Full memory setting, we compared the first 34 and last 33 tasks in 100-task prediction replays on WebArena and VWA. The per-call averages below show early -> late within the Full setting:

Benchmark     Input tokens      Output tokens   API latency (s)
WebArena      2,311 -> 2,736     35.4 -> 36.9    1.574 -> 1.658
VWA           2,159 -> 2,545     31.1 -> 31.2    1.420 -> 1.477

Over 90% of calls in each early cohort already retrieved all five episodes. Subsequent memory accumulation primarily enlarged the retrieval pool, while the number of retrieved episodes remained capped. Total input length grew by about 18%, output length remained nearly constant (~31–37 tokens), and average prediction API latency increased only marginally (+0.06–0.08 s, or ~4–5%). These historical replay diagnostics describe token/call behavior, not online speedup or a strict rerun of the main-table scoring. We will add early/middle/late token and latency statistics, with bin definitions and separate preparation accounting, to the revised paper.

AuthorsOpenReview ↗

Response to Reviewer 15RA (2/2)

3. Prediction accuracy and execution cost–latency

In addition, I am interested whether this memory-augmented speculation can push the accuracy/speed Pareto frontier.

Thank you for this suggestion. Under the lossless-reuse assumptions, expected actor task quality is preserved, while the speculator's prediction hit rate can improve. For execution efficiency, we therefore examine the cost–latency trade-off separately from prediction accuracy.

We evaluated None, Stateless and Memory on 80 WebArena Shopping tasks (averaged over three runs), using the same Bedrock Qwen3-235B-A22B actor and Qwen3-32B speculator. Both speculative arms used k=3; Memory used the paper's Episodic+Miss setting, updated online from 20 prior tasks.

Arm                    Mean episode (s)   API USD/task
None                         55.27          0.02270
Stateless k=3                45.69          0.02311
Memory k=3                   42.90          0.02389

Within this fixed k=3 comparison, Stateless and Memory are both non-dominated in the observed API-cost–episode-time trade-off: Stateless has lower cost, while Memory has lower episode latency. Memory provides a lower-latency point on this observed frontier, with 6.1% lower mean episode time at 3.4% higher API cost ($0.00078 more per task).

Reported episode time includes retrieval, verification, scheduling and memory updates, but excludes setup, evaluation and cleanup.

4. Open-weight models

I encourage the authors to add experiments with open-weight models such as Qwen or DeepSeek to strengthen the generality of their findings.

Thank you for this helpful suggestion. We evaluated Qwen3-32B and DeepSeek-V3.2 as speculators on all six benchmarks. Within each model, Stateless and Memory use the same frozen actor trajectories and one candidate per prediction. Memory settings are benchmark-specific and held fixed across the two model families.

Prediction hit rate (%)   Qwen3-32B       DeepSeek-V3.2
WebArena (n=739)           11.9 -> 14.6    14.9 -> 15.3
VWA (n=817)                 6.0 -> 8.0      5.8 -> 9.2
ALFWorld (n=1,696)         20.8 -> 37.8    28.2 -> 43.0
PDDL (n=1,018)             19.1 -> 36.6    26.7 -> 51.1
tau2 (n=488)              18.4 -> 20.5    20.5 -> 26.0
HotpotQA (n=875)           15.9 -> 19.5    19.7 -> 24.9

Entries are Stateless -> Memory; n counts scored predictions. We score observations on ALFWorld/PDDL, actions including arguments on WA/VWA, read-only calls on tau2, and next actions on HotpotQA.

Memory improves prediction hit rate in all 12 comparisons, supporting generalization beyond GPT-family speculators. We will include these results and evaluation settings in the revised paper.

As the discussion period is approaching its end, we wanted to make sure our response reached you. We would be glad to clarify any remaining points. Thank you again.

Thanks for the additional results. I keep my score.

Reviewer_4QAcOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper introduces a speculative execution method for LLM agents, consisting of applying agent-memory techniques to a speculator in order to speculate at the level of agent steps, instead of tokens. The idea is to use a smaller/cheaper LLM to speculate the next step in the agent-environment loop while the LLM actor / environment is busy. The speculation allows us to launch in advance the agentic work for the next step and, if the prediction was correct, hide the latency for that work. If the speculation is incorrect, the work is discarded. Only read-only operations from a whitelist are pre-launched, so there are no irreversible rollbacks.

Critical strengths
  • The paper addresses a real and timely problem (speculating agentic steps). The key idea is sensible: speculators that ignore past trajectories leave low-hanging fruits on the table; by taking advantage of memory, the authors were able to improve upon all six benchmarks across three speculator models, and the results are robust to task order
  • Very thorough component ablations. The ablation makes it easy to understand which components the gains come from.
Critical weaknesses
  • The latency and cost benefits appear overstated. For example, Figure 1 claims latency reduction grows from about 28% to over 50% on ALFWorld, but this estimate counts every correct speculation as hiding a full actor LLM call, even though ALFWorld is a text simulator with near-zero environment latency, and appendix a.9 show Type 2 savings depend on that delay: about 1.003× at 2 s and at best 1.13× at an assumed 10 s.
  • the technique introduced by the paper has limited novelty, consisting of applying existing memory techniques (ExpeL, AWM, Synapse, Reflexion). the key difference is their application to the speculator instead of the actor. No new algorithm is introduced. While novelty by application can be enough for acceptance, the paper needs to yield a substantial reusable insight or large practical gain. The findings here (miss episodes help most on observation prediction, combining all components sometimes hurts) are useful but modest, and the practical gains are small
Questions for authors
  • Can you reconcile the ALFWorld latency numbers?
  • How does a simple non-LLM predictor do on ALFWorld and PDDL, such as returning the most frequent past observation for the same action type and arguments?
  • The paper reports a best-of-seven memory configuration per benchmark. How does the system perform when using a single memory configuration set in advance for all benchmarks?
3 comments
AuthorsOpenReview ↗

Response to Reviewer 4QAc (1/2)

Thank you for recognizing the motivation and the component ablations. We address the latency accounting and the two requested predictor comparisons below.

1. Reconciling the ALFWorld latency numbers

Can you reconcile the ALFWorld latency numbers?

Figure 1 reports idealized savings in actor-inference time, assuming the environment execution window is long enough to hide speculation overhead, each correct prediction eliminates one full actor LLM call from the critical path. The percentage is normalized by actor-inference time.

Our ALFWorld experiments use its text-based simulator, which abstracts away low-level embodied execution. Its feedback time therefore does not represent physical action duration. Appendix A.9 combines measured actor/speculator latencies with assumed environment delays of 2–20 seconds to analyze scenarios with non-negligible execution time. The appendix estimates total task-time speedup at each delay, while Figure 1 shows idealized actor-inference savings.

We will make this distinction explicit in the Figure 1 caption and the corresponding description in the main text, and label the axis "Idealized actor-inference latency savings (%)".

2. Non-LLM frequency predictor

How does a simple non-LLM predictor do on ALFWorld and PDDL, such as returning the most frequent past observation for the same action type and arguments?

We evaluated exactly this baseline: a frequency table keyed by the normalized complete action, including its type and all arguments. Within each environment domain, it returns the most frequent raw observation from earlier completed tasks; ties use first historical occurrence. Unseen keys abstain and count as misses.

The comparison uses the same trajectories, task order, and lowercase/whitespace-normalized exact-observation metric. There are 134 tasks/1,696 scored steps on ALFWorld and 60 tasks/1,018 steps on PDDL.

Observation-prediction accuracy (%)      ALFWorld   PDDL
Stateless LLM                              16.04   16.31
Non-LLM: exact-action frequency lookup     27.59   26.92
Memory LLM: Full recipe rerun              40.80   35.85

The memory predictor exceeds this lookup by 13.2 percentage points on ALFWorld and 8.9 percentage points on PDDL. These are new matched prediction results, not latency estimates. Unlike exact lookup which must abstain whenever object IDs or arguments vary, the memory-guided LLM generalizes across structurally similar actions and states.

3. One memory configuration across benchmarks

The paper reports a best-of-seven memory configuration per benchmark. How does the system perform when using a single memory configuration set in advance for all benchmarks?

Table 2 already reports a common component selection in its Full row; that row does not select a different setting for each benchmark. It combines the transition table, episodic memory with miss episodes, and confusion tracking, with benchmark-specific record formats.

Table 2 accuracy (%)     Stateless   Full
WebArena                     19.8     23.5
VisualWebArena               12.5     16.2
ALFWorld                     16.3     40.0
PDDL                         17.6     33.8
tau2-bench                   12.7     19.9
HotpotQA                     20.5     27.5

Full improves over Stateless on all six benchmarks. It is the best reported setting on all four Type 2/3 benchmarks in the main table (ALFWorld, PDDL, tau2-bench, and HotpotQA). For Type 1, all six memory settings improve over Stateless, but Full is not always best: it trails Episodic+Miss by 0.2 points on WebArena and Episodic by 1.2 points on VisualWebArena.

As discussed in Section 3.2 and Appendix B.2 (Memory Combination and Interference), diverse web action spaces favor context-specific episodic examples. Adding aggregate transition statistics can introduce redundant or conflicting guidance, for example when a frequent transition conflicts with a retrieved miss episode. This helps explain why combining every component need not yield the highest accuracy. Full therefore provides a common configuration that improves accuracy across all six benchmarks, while benchmark-specific selection can offer further gains. We will distinguish common-Full results from per-benchmark-best summaries more clearly.

AuthorsOpenReview ↗

Response to Reviewer 4QAc (2/2)

4. Contribution and practical significance

While novelty by application can be enough for acceptance, the paper needs to yield a substantial reusable insight or large practical gain.

We agree that the memory primitives build on prior work. Our core insight is decoupling speculator memory from the actor's decision context and optimizing it for transition predictability rather than task completion. An actor can complete a task successfully while the speculator repeatedly mispredicts its transitions. Actor task success and prediction utility therefore provide different signals for organizing memory.

The ablations in Table 2 and the non-LLM comparison above provide guidance on memory selection and demonstrate gains beyond simple frequency lookup.

To examine practical execution, we evaluated non-speculative execution, stateless speculation and memory-based speculation online on 80 tasks each from the Reddit and Shopping domains of WebArena, without injected delays, averaged over three runs. The actor and speculator were Qwen3-235B-A22B and Qwen3-32B served through Bedrock. Both speculative arms used one call producing up to three candidates (k=3). We used the paper's Episodic+Miss setting, updated after each completed task. Both domains started with 20 warm-start tasks and used full-page pre-execution.

Domain      Arm                    Mean episode (s)   API USD/task
Reddit      None                         22.11          0.01016
Reddit      Stateless k=3                19.92          0.01168
Reddit      Memory k=3                   18.82          0.01203
Shopping    None                         55.27          0.02270
Shopping    Stateless k=3                45.69          0.02311
Shopping    Memory k=3                   42.90          0.02389

API cost excludes warm-start collection and infrastructure.

Memory's observed mean episode time was 5.5% lower than Stateless and 14.9% lower than None on Reddit. On Shopping, the differences were 6.1% versus Stateless and 22.4% versus None. Reported episode time includes retrieval, verification, scheduling and memory updates, but excludes setup, evaluation and cleanup.

Realized savings depend on both prediction hit rate and the available overlap window (Section 2.1). We use WebArena for integrated browser execution; benchmarks such as ALFWorld and PDDL have fast simulated feedback with little environment waiting time. WebArena also showed a comparatively modest prediction gain in the original replay study (19.8% to 23.7%, +3.9 percentage points; Table 2). To examine broader timing conditions, Section 4.3 and Appendix A.9 combine measured model latencies with assumed environment delays, illustrating how sufficiently early predictions and longer overlap windows can hide more latency per correct prediction.

As the discussion period is approaching its end, we wanted to make sure our response reached you. We would be glad to clarify any remaining points. Thank you again.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.