cs.CLSep 22, 2026
SaveTomasuLLM: Out-of-Order Speculative Execution for LLM Agents
Organizations: HKUST Hong Kong, Hong Kong · Nanjing University Nanjing, China · King Abdullah University of Science and Technology Thuwal, Saudi Arabia · Zhejiang Lab Hangzhou, China
Abstract
Long-running tools can dominate coding-agent latency: compilers, test suites, and repository commands take seconds to minutes while the agent idles. This observation stall presents the same tension that drove out-of-order processors -- asequential interface hides work that can be predicted and started early, but a speculative result may become visible only after it and every earlier step have been validated. We present TomasuLLM, a runtime that executes agent tool calls out of trajectory order while preserving task-execution correctness. It drafts future actions, runs them in isolated copy-on-write sandboxes, traces their dependencies and effects, and commits results in trajectory order only after validation against committed state. Across three benchmarks spanning sub-second to minutes-long tool calls, TomasuLLM improves the reported benchmark means and scales with tool latency: 1.31x on 100 SWE-bench Verified tasks, 1.35x on 28 Terminal-Bench 2.0 tasks, and 1.27x matched progress on 18 SWE-Marathon sessions. Across 4,010 audited commit-validation records, it produces zero false accepts.
Figures & tables
Figure 1. Observation-stall slack and the commit boundary. (a) The base agent serializes at observation boundaries. (b) TomasuLLM executes drafted actions in COW overlays and publishes only validated observations in main-agent order. (c) The CPU analogy separates prediction from in-order commit. Three side-by-side panels. Panel a shows the base-agent serial path: LLM reasoning, tool execution T1, LLM reasoning, tool execution T2, and the final answer, where each tool observation must return before the next action issues. Panel b shows the TomasuLLM runtime with a drafting region and an overlay-execution region. The Action Drafter emits predicted tool actions, the Observation Drafter emits a predicted observation, and real tool executions T1 and T2 run in copy-on-write overlays, with T2 finishing first; sandbox observations flow into the Validate and in-order commit stage before publication, and a mismatch discards the speculative suffix. Panel c shows the CPU analogy: branch and value prediction feed fetch, decode, rename, and issue; instructions I1 and I2 execute out of order; validation and the reorder buffer commit in order, with mispredictions squashed.
Figure 2. Trajectory order versus true dependences for six consecutive calls from a measured slack-clone run. The dependence DAG reduces the serial chain of depth six to a critical path of depth four. Two panels. The left panel shows six circles labelled s1 through s6 joined top to bottom by arrows into a single chain, labelled depth six. The right panel shows the same six calls as a graph: s1 and s2 sit side by side with no edge between them and both point to s3; s3 points to s4; and s4 points to both s5 and s6, which sit side by side with no edge between them. Edges carry labels reading write-after-read (WAR) on logic.js, read-after-write (RAW) on logic.js, and loaded-version record.
Figure 3. TomasuLLM runtime with drafter engines. A single-column block diagram with three stacked boundaries. The top row is the main-agent loop, with four equal boxes for the committed observation, prompt construction, main-agent LLM, and next action. The middle row is drafter engines, with equal boxes for the Action Drafter and Observation Drafter connected by a predicted-observation arrow. The bottom row is the TomasuLLM runtime. Its right side is an equal-size vertical pipeline from Issue, Fork, Execute, Trace IR record, Validate, to Commit, with a commit frontier before Commit. Its left side contains compact equal-size boxes for the Run-Ahead Controller and COW overlays, plus Squash and the committed-observation queue. Straight arrows show the canonical action entering Issue, drafted actions entering the controller, candidate execution feeding the Observation Drafter, and validated observations returning to the main-agent loop.
Figure 4. Walkthrough trace for twelve slack-clone actions. (a) Serial vs. run-ahead timing; (b) c121–c124 expanded, showing stale-file rejection, waiting on c122’s loaded-version record, and in-order commit. Two panels. Panel a shows two horizontal bars on one time axis from 0 to 92 seconds: the serial-baseline bar alternates blue decode segments with orange tool-wait segments for twelve actions and ends at 91.4 seconds; the TomasuLLM bar is mostly blue with three orange segments and ends at 52.9 seconds, with a dashed box around 21 to 54 seconds and a red cross at 26 seconds. Panel b enlarges the box as four rows, c121 to c124: c121 shows draft, fork, an early execution labelled file at version one, a red cross, a re-run segment and a decode strip above; c122 shows a decode strip and a restart bar with a commit mark at 41 seconds from which dashed arrows descend to c123 and c124; c123 and c124 each show draft, fork, a hatched held segment ending at 41 seconds, an execute bar to 51 seconds and a decode strip that starts after execution began; commit marks appear in order. Circled numbers one, two and three mark the three cases.
Figure 5. Ready and in-flight operands. (a) Workspace files track edits; the running process follows its loaded-version record. (b1) A ready read runs early; a committed edit triggers mismatch and discards the overlay. (b2) An in-flight dependent forks early but is held until the restart commits. Three stacked schematic panels. Panel a shows an upper workspace track stepping from file at version 1 to version 2 to version 3 at two edits, and a lower process track showing that the running process still loads file version 1 until a restart reloads file version 3. A shaded band marks the stale interval. Panel b1 shows Candidate 1 reading file at version 1, a V-dep check detecting version mismatch caused by the committed edit, discarding the overlay, and serial re-execution; Candidate 2 is chained on C1 and squashed. A causal arrow connects the committed edit to the mismatch. Panel b2 shows Candidates 3 and 4 forking and preparing early, held until the restart commit makes the loaded-version record ready, then executing; in-order commit marks appear.
Figure 6. End-to-end speedup over Serial Pi. Panel (a) reports the three benchmark means; panel (b) reports per-task SWE-Marathon speedup for Prefetch (PASTE) and TomasuLLM. Starred entries report matched-progress time at the 6.0 h E2B cap rather than task completion. Two-panel speedup figure. The left panel shows mean speedup for SWE-bench Verified, Terminal-Bench 2.0, and SWE-Marathon. The right panel shows grouped bars of per-task speedup over Serial Pi for the PASTE-style prefetch baseline and \systemacross 18 SWE-Marathon tasks, sorted by \systemspeedup. Starred labels denote matched-progress rows at the 6.0 hour cap; dashed lines mark the Serial Pi baseline.
Figure 7. Tool time on the Serial Pi baseline. (a) Share of end-to-end wall clock spent inside tool executions; the SWE-Marathon bar averages the per-task shares of Table 6 . (b) Median and interquartile range of tool time per call. Two stacked panels. Panel a is a horizontal bar chart of tool-time fraction with SWE-bench Verified at 0.35, Terminal-Bench 2.0 at 0.40 and SWE-Marathon at 0.24. Panel b plots tool time per call on a logarithmic axis, with median markers at 2.1, 8.5 and 12 seconds and interquartile ranges spanning 0.6 to 7, 2.5 to 28 and 3.5 to 58 seconds.
| Injected hidden dependency | Cases | Caught | First failing check |
|---|---|---|---|
| Stale file version after committed edit | 4 | 4 | |
| Absence set: failed lookup, later create | 3 | 3 | |
| Directory rename changes path resolution | 3 | 3 | |
| Shared process state before restart | 3 | 3 | held on producer |
| Wall-clock or randomness in observation | 3 | 3 | |
| Untraced read outside the process tree | 2 | 2 | speculation barrier |
Table 1. Fault injection. Hidden dependencies deliberately introduced into tool wrappers, and the check that rejected each candidate.
Figure 8. Serial Pi latency normalized to one, split into the parts TomasuLLM hides and the parts that stay on the critical path. A stacked horizontal bar of Serial Pi latency normalized to one, with tool pre-execution 0.30, retained reasoning 0.10 and replay 0.07 hidden, and main-agent decode 0.19 and serial-path tools 0.34 remaining.
Figure 9. Speculative chain diagnostics. (a) Consecutive candidates committed before first chain termination. (b) First mismatch cause share. (c) Drafter match rates. Three panels. Panela is a bar chart giving the probability of each valid action prefix length from zero to four, with values 0.18, 0.28, 0.26, 0.17, and 0.11. Panelb is a horizontal bar chart of first-mismatch shares: Action 0.36, Observation 0.26, Dependency 0.17, Speculation barrier 0.14, and Timeout 0.07. Panel~c is a horizontal bar chart of match rates: Action top-1 0.46, Action top-2 0.61, and Observation 0.65.
| Primitive | Elapsed time |
|---|---|
| Read-only E2B overlay fork | 0.08 s |
| Fork with private data copy | 3–5.5 s |
| Full snapshot creation | 10–60 s |
| Warm reconnect | 0.5–3 s |
| Trace IR recording | 0.1–1 s |
| Canonical verification | ms |
Table 2. Microbenchmark of runtime primitive costs.
Figure 10. Measured speedup and the unlimited-sandbox dependence roofline over Serial Pi. A bar chart with three groups, SWE-bench Verified, Terminal-Bench 2.0 and starred SWE-Marathon, each with a filled bar for measured speedup and a hollow bar for the unlimited-sandbox roofline; values 1.31 and 1.54, 1.35 and 1.67, and 1.27 and 1.32.
Appendix figures & tables12 assets
Supplementary material from the paper’s appendix.
Appendix
| Tool class | Projected fields | Comparator |
|---|---|---|
| read | path, existence, content hash, path-absence dependencies, mtime policy | Exact digest |
| edit / write | target paths, patch/effect digest, written bytes, post-state digest | Exact digest |
| test/compile | exit code, failed tests, error types, source locations, artifact hashes | Field-wise exact |
| search | query, matched paths, line numbers, content hashes, stable ordering policy | Canonical set |
| bash | exit code, declared stdout/stderr fields, effects, opaque flag | Tool-specific |
| opaque/API | none; optional prepare intent only | Speculation barrier |
Table 3. Implemented tool-wrapper classes and comparators. Test, compile, search, and general bash commands share the bash wrapper; class-specific projected fields and comparators are implemented through the canonicalization policy (Section 3.6 ).
Figure 11. Trace IR record from a measured test execution and the commit check each field must pass. Predicates are defined in Section 3.6 . The left column lists four fields of one Trace IR record: the canonical action, which is a test.run call with suite, revision, fixture and mode arguments; the read set, listing three file versions and the loaded-version record of the process contacted; the observation, a passed status with four named checks and a digest; and the effects, an empty write set with an ephemeral database replica and a postcondition digest. An arrow joins each field to the commit check it must pass in the right column: the action to V-act, the read set to V-dep, the observation to V-record, and the effects to V-effect. A line at the bottom states that all four hold, so the observation is returned and the frontier advances.
| Field | Records | Commit validation |
|---|---|---|
| Canonical tool name, JSON arguments, working directory, and environment. | Match the next serial action. | |
| Committed or speculative parent state used to fork the sandbox. | Lineage precondition of : reject a candidate forked from a superseded or squashed parent. | |
| Read set with versions or content digests. | Reject if an older committed effect changes a resource the tool read. | |
| Absence set: failed path or resource lookups that affected execution. | Reject if an older committed effect creates one of those paths or resources. | |
| Private writes and deferred effect deltas. | Publish only captured deltas; no unrelated committed state may change. | |
| Sandbox observation and observation digest. | Validate the recorded observation under the wrapper’s canonicalization rule; compare it with predicted observations only to keep descendants eligible. |
Table 4. Trace IR fields and commit checks.
| Input | Online source | If wrong |
|---|---|---|
| Drafted tool action | Action Drafter output from an online context built from the committed history, optionally extended by prediction-eligible drafted steps | Action mismatch at the frontier; discard |
| Expected duration | Exponentially weighted running mean over that class within the task | Suboptimal wait-or-discard decision at the frontier only |
| Speculatable | Tool registry safety class for the drafted tool action | Call becomes a speculation barrier |
| Loaded-version binding | Test arguments; readiness probe at restart commit | Loaded-version mismatch; discard and serially re-execute |
Table 5. Run-ahead scheduling inputs. None is a correctness input.
| Task | Serial | PASTE | TomasuLLM | Actions | Tool |
|---|---|---|---|---|---|
| BioFabric rust | 6.0h cap | 5.3h eq-prog. | 5.1h eq-prog. | 7,677 | 22.4% |
| Embedding eval | 59m | 44.7m | 39.0m | 1,036 | 48.5% |
| Excel clone | 39m | 36.9m | 36.0m | 4,513 | 10.9% |
| Network align. | 6.0h cap | 4.1h eq-prog. | 3.4h eq-prog. | 3,494 | 62.7% |
| JAX PyTorch | 3.2h | 2.5h | 133.8m | 1,897 | 43.3% |
| K8s rust | 6.0h cap | 5.4h eq-prog. | 5.2h eq-prog. | 4,100 | 19.7% |
Table 6. End-to-end wall-clock latency on the SWE-Marathon online subset. Cap marks the E2B session limit. Eq-prog. entries are equal-progress times: the configuration has reached the committed-tool-result count that Serial Pi had at the 6.0 h cap, not task completion. Actions counts recorded tool actions. Tool is the share of Serial Pi wall clock spent inside tool executions.
| Task | Qwen3.8-27B | DeepSeek V4 Pro |
|---|---|---|
| BioFabric rust ∗ | 1.19 | 1.16 |
| Embedding eval | 1.51 | 1.53 |
| Excel clone | 1.08 | 1.08 |
| Network align. ∗ | 1.78 | 1.81 |
| JAX PyTorch | 1.43 | 1.42 |
| K8s rust ∗ | 1.16 | 1.14 |
Table 7. Per-task TomasuLLM speedup over Serial Pi under two target models. Starred rows are matched-progress ratios at the 6.0 h E2B cap.
Figure 12. Out-of-order issue diagnostics. (a) Run-ahead depth at issue for committed calls. (b) Execution reorder distance in a traced SWE-Marathon window. Two panels. Panel a is a grouped bar chart with run-ahead depth from zero to four on the horizontal axis and share of committed calls on the vertical axis, with SWE-bench Verified concentrated at depth zero and SWE-Marathon showing the largest nonzero depths. Panel b is a bar chart over a commit-ordered traced window, with positive and negative reorder-distance bars.
| Action Drafter | Obs. | Accept- | Speed- | ||
|---|---|---|---|---|---|
| Drafter variant | top-1 | top-2 | match | ance | up |
| Qwen3.8-8B, no LoRA | 0.29 | 0.44 | 0.52 | 0.22 | 1.12 |
| Early LoRA checkpoint | 0.36 | 0.53 | 0.58 | 0.30 | 1.45 |
| Mid LoRA checkpoint | 0.42 | 0.58 | 0.62 | 0.37 | 1.80 |
| Final LoRA (deployed) | 0.46 | 0.61 | 0.65 | 0.42 | 2.05 |
Table 8. Accuracy, acceptance, and latency across Action Drafter variants. Acceptance counts dispatched candidates accepted at the commit frontier.
Figure 13. Speedup as a function of dispatched-candidate acceptance across Action Drafter variants. A line chart with dispatched-candidate acceptance rate on the horizontal axis and speedup over Serial Pi on the vertical axis. Four points rise from 0.22 acceptance and 1.12 times speedup to 0.42 acceptance and 2.05 times speedup. A dashed fit extrapolates break-even near 0.20 acceptance.
| Serial Pi | TomasuLLM | Ratio | |
| Main-agent prompt tokens (M/task) | 0 8.2 | 0 8.3 | 1.01 |
| Main-agent completion tokens (M/task) | 0 0.41 | 0 0.41 | 1.00 |
| Main-agent decode time (s/task) | 1,640 | 1,660 | 1.01 |
| Main-agent TTFT, median (ms) | 0 310 | 0 330 | 1.06 |
| Main-agent TTFT, p95 (ms) | 0 740 | 0 890 | 1.20 |
| Drafter tokens (M/task) | 0 0 | 0 1.6 | — |
Table 9. Main-agent parity and speculative resource use.
| Single-version | |||
| TomasuLLM | Permissive | Conservative | |
| Normalized latency | 0.58 | 0.68 | 0.85 |
| Stale loaded-version rejects / task | 1.1 | 10.6 | 0 |
| Serial re-executions / task | 2.2 | 12.4 | 2.1 |
| False accepts | 0 | 0 | 0 |
| Held in-flight operands | 15% | 0% | 61% |
Table 10. Operand ablation. Normalized latency, stale loaded-version rejects and serial re-executions per task, false accepts, and the share of in-flight operands held.
Figure 14. Trace-driven sensitivity of speedup to each run-ahead allocation, with the other allocation held at its reported value. Only the reported configuration ( , eight slots, 2.05 ) is measured; the remaining points are replay estimates anchored on it. Two small line charts of replay-estimated speedup. Left: speedup against maximum draft depth from one to six, rising from about 1.5 at depth one to about 2.05 at depth four and flat thereafter, with a dashed horizontal line labelled drafter's reach at 2.05 and an open circle at depth six. Right: speedup against maximum sandbox concurrency at 1, 2, 4, 8, 16 and 32 slots, rising from about 1.25 to 2.17 at sixteen slots and flat thereafter, with a dashed line labelled producer chain at 2.17 and an open circle labelled measured at eight slots, the only configuration that was actually run.
More in this topic
LLM Agent Workflow Optimization
LLM agent workflow optimization studies how to design and run multi-step agents for better task success, reliability, latency, and cost.
See all 256 papers