TomasuLLM: Speeding Up LLM Agents with Out-of-Order Speculative Execution

The Latency Bottleneck for Coding Agents: Waiting on Tools

Long-running tool calls have become one of the most invisible performance killers for coding AI agents. Compilers, test suites, repository commands — these operations can take anywhere from several seconds to several minutes to complete, and during that entire window, the agent just sits idle, wasting both compute and response time.

TomasuLLM, introduced in a new arXiv paper, targets exactly this pain point. Its core insight is elegantly simple: the "stalls" that agents experience are fundamentally the same problem that motivated the invention of out-of-order processors. A sequential interface hides a large amount of work that can be predicted and started early — but speculative results only become visible once they and all prior steps have been verified.

The analogy isn't a stretch. The Tomasulo algorithm from CPU design — which the paper's name clearly pays homage to — has long demonstrated that out-of-order execution combined with dependency tracking and in-order commit can dramatically improve throughput without breaking correctness. TomasuLLM transplants this proven hardware concept into the LLM agent runtime.

The Tomasulo algorithm was designed by IBM engineer Robert Tomasulo in 1967 for the IBM System/360 Model 91 floating-point unit, and is the cornerstone of modern out-of-order processors. Its key idea is the introduction of "Reservation Stations" to buffer pending instructions and their operands, paired with a "Common Data Bus" for result broadcasting and dynamic dependency resolution. When an instruction is waiting on an unavailable operand, later independent instructions can bypass it and execute first, hiding pipeline stalls caused by data hazards. The algorithm's elegance lies in decoupling execution order from commit order: instructions may complete out of order, but a Re-Order Buffer (ROB) ensures results are made visible in the original program order, preserving sequential semantics while extracting parallelism. This idea lives on in virtually every modern high-performance processor, including the Intel Pentium Pro and ARM Cortex families.

How TomasuLLM Works: Out-of-Order Execution, In-Order Commit

TomasuLLM is a runtime system that allows an agent's tool calls to execute out of trajectory order while guaranteeing correctness. The mechanism breaks down into four key components:

Speculative Drafting and Isolated Sandboxes

The system "drafts" actions the agent might take in the future and runs them early inside isolated copy-on-write (CoW) sandboxes. Copy-on-write is a critical design choice — it confines the side effects of speculative execution to the sandbox without polluting the real committed state, while avoiding the overhead of fully copying the environment.

Copy-on-Write (CoW) is a classic memory management technique widely used in OS process forking and virtual machine snapshots. Multiple execution contexts initially share the same memory pages; a private copy is only made when a context attempts to write, and modifications are applied only to that copy. This avoids the enormous overhead of pre-allocating full memory for each sandbox while preserving isolation between them. In TomasuLLM, each speculative branch forks a sandbox from the current committed state — filesystem writes, environment variable changes, shell state modifications, and other side effects are all contained within. If the speculative result is validated, the sandbox's changes are merged back into the main state; if validation fails, the sandbox is simply discarded with zero impact on the main state.

Dependency Tracking and Effect Logging

During speculative execution, TomasuLLM tracks the dependencies and side effects (effects) of each action. This is analogous to the scoreboard mechanism in CPU out-of-order execution, ensuring the system always knows which results depend on which preconditions.

In-Order Verification and Commit

The most critical step: speculative results are only formally committed after being validated in trajectory order against the committed state. Execution may happen out of order and ahead of time, but results visible to the outside world must materialize in strict original sequence. This is the correctness guarantee — if a speculative action's preconditions change during real execution, that speculative result is discarded.

This "out-of-order execute, in-order commit" architecture lets an agent kick off steps that will most likely be needed next while waiting on a slow tool call, and cash them in immediately once validated — effectively overlapping what would otherwise be serial wait time.

Benchmark Results: Higher Latency Means Bigger Gains

TomasuLLM was evaluated on three benchmarks covering tool latency scenarios ranging from sub-second to minute-scale:

• SWE-bench Verified: 1.31× speedup across 100 tasks
• Terminal-Bench 2.0: 1.35× speedup across 28 tasks
• SWE-Marathon: 1.27× improvement in matched progress across 18 sessions

A notable pattern: speedup scales with tool latency. This is entirely intuitive — the slower the tool call, the more time the agent spends waiting, and the more work speculative execution can overlap and hide. For large codebases where test suites routinely run for several minutes, the value of this architecture becomes even more pronounced.

SWE-bench is one of the most influential benchmarks for evaluating AI coding agents, built by the Princeton NLP team. Its test set comes from real GitHub repository issue-fix tasks, requiring the agent to autonomously locate and modify code based on a problem description, with success defined as passing official test cases. SWE-bench Verified is a human-reviewed subset with ambiguous descriptions and flawed test cases filtered out, making results more reliable. SWE-Marathon is a longer-horizon multi-turn session evaluation focused on cumulative performance in sustained engineering tasks, where both tool call frequency and per-call latency are significantly higher than single-issue fix scenarios — making it particularly well-suited to demonstrate the value of latency hiding. Terminal-Bench 2.0 focuses on task completion in pure command-line environments, with shell commands as the primary tool type and a latency distribution close to real development environments.

Correctness Is the Real Test

The biggest risk of speculative execution is acting on a wrong prediction. For a coding agent, one incorrect commit could mean corrupting the codebase or polluting test results — consequences far more serious than a performance loss.

TomasuLLM delivers a notably strong result here: across 4,010 audited commit-verify records, the system produced zero false accepts. In other words, not a single speculative result that shouldn't have been accepted was incorrectly committed as ground truth.

This zero false-accept result is the dividing line between TomasuLLM as a research curiosity and TomasuLLM as something practical. Performance gains are appealing, but not at the cost of correctness — that's simply not acceptable for coding agents in production environments. The in-order commit and verification mechanism serves as the gatekeeper here.

Implications for AI Agent Engineering

TomasuLLM's significance goes beyond a single acceleration technique. It represents a conceptual shift: systematically bringing mature computer architecture ideas into the LLM agent runtime.

Over the past few decades, CPU designers have accumulated a rich toolkit for balancing "sequential semantics" with "parallel execution" — out-of-order execution, speculative execution, dependency tracking, commit queues. Now, as LLM agents face the same tension between "sequential interfaces" and "parallelizable work," these classic ideas are ready to be reactivated.

As agents take on more real engineering tasks — running tests, building compiles, executing command-line operations — latency hiding will become a core optimization frontier. TomasuLLM demonstrates that meaningful speedups are achievable through runtime-level speculative execution without changing agent logic or sacrificing correctness. For AI programming tools where responsiveness matters, this is a path worth exploring further.

Of course, the paper is still in early stages (a fresh arXiv submission), and its behavior in more complex multi-tool, multi-dependency scenarios — along with the additional memory overhead of copy-on-write sandboxing — remains to be studied. But as an attempt to migrate hardware wisdom into the AI runtime, TomasuLLM offers a genuinely thought-provoking paradigm.