An LLM agent acting in an environment spends most of its wall-clock time waiting. Each step — a model call, a tool or MCP request, a browser action, sometimes a human reply — must complete before the next can be issued, and the round trips dominate end-to-end latency: a chess game between two reasoning agents runs for hours, and an operating-system tuning task for tens of minutes. When a training or prompt-optimization loop repeats such a run thousands of times, the waiting is the cost.
Speculative actions (Ye, Ahuja, Liargkovas, Lu, Kaffes, Peng, ICLR 2026) transplants a classical systems idea — speculative execution in microprocessors, and speculative decoding for LLM inference — to the agent's environment loop. A cheap, fast speculator guesses the action a slow, authoritative actor is about to produce, the guess is used to launch the next environment call early, and the work is committed only when the actor's real action confirms the guess. The interface stays sequential and lossless; the internals run in parallel.
What makes this a formalization target rather than an engineering report is the paper's §5 cost–latency analysis. Speculating more branches buys hit probability but costs tokens, and the paper derives closed-form expressions for both sides of that trade — a self-contained piece of applied probability sitting underneath a systems paper. This mission asks for those expressions, machine-checked.
Fix a horizon and index steps . At each step a policy maps the state to an API call; the actor executes it with latency , while the speculator proposes candidate actions with latency , where (the speculator is faster in expectation). A speculative branch hits when the action it guesses implies the same next call the actor's true action would have implied; branches hit independently across steps with probability .
Two knobs define the two regimes analyzed. Breadth : at each step, launch independent one-step speculations in parallel, each immediately followed by a real call. At least one of the succeeds with probability
Depth: follow a single branch, extending it whenever a speculative or real call returns and pruning subtrees the actor contradicts.
The quantity driving both results is , the expected number of hits by round . A hit consumes the following step's speculation window — after a correct guess the next call is already cached, so no new speculation is launched there — which yields the two-term recursion
Write for the latency and token cost of strictly sequential execution, and for their speculative counterparts. In the depth regime latencies are taken deterministic: for a real call, for a speculative one.
The goal theorem is the finite-horizon latency ratio for breadth-focused speculation (Proposition 1), with abbreviated :
The supporting targets, ordered as the analysis builds them:
The analysis is what turns speculation from a trick into a tunable system. Proposition 1 and Theorem 4 are governed by the same quantity , so a practitioner who can estimate hit probability can choose offline against a latency/cost budget rather than by trial. The 50% ceiling is a genuine negative result — it says breadth alone cannot do better, and motivates the depth regime, where the ceiling becomes 1. Theorem 3 explains why confidence-based branch selection is cheap in practice: the whole dynamic program collapses to one scalar continuation value, so a runtime system sorts confidences and adds branches greedily in per step.
The paper's proofs are pen-and-paper and, as far as we are aware, none of these results has a machine-checked proof. Three parts reward formalization specifically. The recursion's closed form is derived by a characteristic-equation argument with a particular solution that collides with the homogeneous part — routine but error-prone. The per-hit saving is an honest two-dimensional integral over independent exponentials. And Theorem 6's cost expression is stated in the paper with a floor function and then immediately replaced by an approximation, so formalizing it forces a decision about which claim is actually being asserted (see Formalization scope).
The obvious first move on the recursion — guess a constant particular solution — fails, because is a root of the characteristic polynomial and a constant trial collides with the homogeneous family; the particular solution is linear in , and the coefficient comes out of matching both initial conditions, not one.
The interesting hypothesis is the one the recursion's shape encodes and the prose states only in passing: a hit at round removes the speculation window at round . Drop it and the recursion becomes one-term and the answer changes.
For the per-hit saving, the difficulty is analytic rather than algebraic: the inner antiderivative of must be handled, and the outer integral runs over an unbounded interval, so integrability has to be established rather than assumed.
The asymptotic statements need the oscillating term controlled uniformly — it is bounded, not vanishing termwise in an obvious way — before the prefactor can be taken to zero.
Everything is over . The model lives in one definition bundle,
Def_SpecActions_model, in namespace SpecActions; the mission's Lean names match the
prose symbols ( is hits, is phit, is kt).
The model is formalized at the level the paper's own proofs use: and
are defined by the expressions Appendix A derives for them
(specTime, specCost, and their depth analogues), and the theorems assert the
algebraic and asymptotic identities relating those quantities. Deriving those
expressions from a measure-theoretic model of the execution trace is deliberately not
in scope — with one exception: milestone 2 states the per-hit saving as a genuine
iterated integral against the exponential densities, so the one probabilistic step the
paper actually computes is formalized as an integral rather than assumed.
Conventions a solver should know before starting:
hits takes (the per-step hit probability ), not the per-branch ;
phit relates the two, and Thm_SpecActions_phit_bounds supplies the
range facts the other statements assume.Reusable beyond this mission: the two-term linear recursion solved in milestone 1, and
the computation for independent exponentials, which is a standard
fact absent from Mathlib. Contributions extending the model toward an actual measure on
execution traces — deriving specTime rather than defining it — are welcome as
follow-on work.
import Definitions.Def_SpecActions_model
namespace SpecActions
theorem prop1_finite_horizon (T : ℕ) (α β pk : ℝ) (hT : 1 ≤ T)
(hα : 0 < α) (hβ : 0 < β) (hpk0 : 0 ≤ pk) (hpk1 : pk ≤ 1) :
specTime T α β pk / seqTime T β
= 1 - (1 / (T : ℝ)) * (α / (α + β)) *
(((T : ℝ) - 1) * pk / (1 + pk)
+ pk ^ 2 / (1 + pk) ^ 2
- pk ^ 2 / (1 + pk) ^ 2 * (-pk) ^ (T - 1)) := by sorry
end SpecActions
Under Assumptions 1–2 of the paper, with per-step hit probability , speculator latency and real-call latency , the ratio of the expected runtime of Algorithm 1 to that of strictly sequential execution is
for every horizon , and .
Here and , the sequential runtime less one expected saving per hit. The identity is the goal theorem of this mission.
No open leaves. Every sub-goal is proved or awaiting decomposition.