Speculative actions: the cost--latency model
DefinitionSpecActions_modelThe formal model underlying the cost--latency analysis of Speculative Actions (ICLR 2026), §5 and Appendices A, C.
An agentic system runs for a horizon of steps. At each step an actor issues a real API call with latency while a speculator guesses the action with latency ; a guess implies the correct next call with probability , independently across steps.
The bundle defines: , the probability at least one of branches hits (phit); the expected hit count and its claimed closed form (hits, hitsClosed); the expected latency and token cost of sequential and speculative execution in the breadth regime (seqTime, specTime, seqCost, specCost); their depth-regime analogues under deterministic latencies and (depthSeqTime, depthSpecTime, depthSeqCost, depthSpecCost); and the confidence-aware quantities , and the per-window objective (qhit, dqhit, specObjective).
Following the paper's own proofs, the expected latency and cost are defined by the expressions Appendix A derives for them; the theorems then assert the algebraic and asymptotic identities relating them.
import Mathlib.Analysis.SpecialFunctions.Exp
import Mathlib.Analysis.SpecificLimits.Basic
import Mathlib.Algebra.BigOperators.Intervals
import Mathlib.Algebra.Order.Field.Basic
/-!
# Speculative actions: the cost–latency model
The model underlying the cost–latency analysis of *Speculative Actions: A
Lossless Framework for Faster Agentic Systems* (ICLR 2026), §5 and
Appendices A, C.
An agentic system runs for a horizon of `T` steps. At each step an *actor*
issues a real API call whose latency is `Exp(β)`, while a *speculator*
guesses the action with latency `Exp(α)`, `β < α`. A guess implies the
correct next call with probability `p`, independently across steps.
-/
namespace SpecActions
/-! ## Breadth-focused speculation (Algorithm 1) -/
/-- `phit k p = 1 - (1 - p) ^ k`: the probability that at least one of `k`
independent speculative branches implies the correct next call. Written
`p(k)` in the paper. -/
noncomputable def phit (k : ℕ) (p : ℝ) : ℝ := 1 - (1 - p) ^ k
/-- Expected number of speculation hits by round `n` (`S n` in Appendix A).
A hit consumes the following round's speculation window, which gives the
two-term recursion
`S 0 = 0`, `S 1 = p`, `S (n+2) = p (1 + S n) + (1 - p) S (n+1)`. -/
noncomputable def hits (p : ℝ) : ℕ → ℝ
| 0 => 0
| 1 => p
| (n + 2) => p * (1 + hits p n) + (1 - p) * hits p (n + 1)
/-- The closed form that Appendix A derives for `hits`:
`S n = p/(1+p) · n + p²/(1+p)² · (1 - (-p)^n)`. -/
noncomputable def hitsClosed (p : ℝ) (n : ℕ) : ℝ :=
p / (1 + p) * n + p ^ 2 / (1 + p) ^ 2 * (1 - (-p) ^ n)
/-- Expected runtime of strictly sequential execution: each of the `T` steps
costs one real API call of mean latency `1 / β`. -/
noncomputable def seqTime (T : ℕ) (β : ℝ) : ℝ := T / β
/-- Expected runtime of Algorithm 1: the sequential runtime less the expected
saving, namely `S (T-1)` hits each saving `E[(B - A)⁺] = α / (β(α+β))`. -/
noncomputable def specTime (T : ℕ) (α β pk : ℝ) : ℝ :=
T / β - hits pk (T - 1) * (α / (β * (α + β)))
/-- Token-cost proxy for sequential execution (fixed tokens per unit time). -/
noncomputable def seqCost (T : ℕ) (β : ℝ) : ℝ := T / β
/-- Token-cost proxy for Algorithm 1. `kt` is `k̃`, the number of *distinct*
actions across the `k` speculative branches (duplicates are killed). -/
noncomputable def specCost (T : ℕ) (α β pk kt : ℝ) : ℝ :=
T / β * (kt + 1) - hits pk (T - 1) * (kt * (1 / β) + α / (β * (α + β)))
/-! ## Depth-focused speculation -/
/-- Sequential runtime when the real API latency is deterministically `a`. -/
noncomputable def depthSeqTime (T : ℕ) (a : ℝ) : ℝ := a * T
/-- Runtime of the depth-focused policy: `a·T + (T-1)·p·(b - a)`. -/
noncomputable def depthSpecTime (T : ℕ) (a b p : ℝ) : ℝ :=
a * T + (T - 1) * p * (b - a)
/-- Sequential token cost with deterministic real latency `a`. -/
noncomputable def depthSeqCost (T : ℕ) (a : ℝ) : ℝ := a * T
/-- Token cost of the depth-focused policy. A step whose guess is correct
spends `a + ⌊a/b⌋·b`; a step whose guess is wrong also pays for the branches
spawned before the real response arrived, the series
`a + (a - b) + ⋯ + (a - ⌊a/b⌋·b)`. -/
noncomputable def depthSpecCost (T : ℕ) (a b p : ℝ) : ℝ :=
a + (T - 1) *
(p * (a + ⌊a / b⌋ * b) +
(1 - p) * (a * (⌊a / b⌋ + 1) - (1 + ⌊a / b⌋) * ⌊a / b⌋ / 2 * b))
/-! ## Confidence-aware selective speculation -/
/-- `qhit pv m = 1 - ∏_{j < m} (1 - pv j)`: probability of obtaining a cached
action when the top `m` branches are launched, where `pv` lists the realized
per-branch confidences in descending order. -/
noncomputable def qhit (pv : ℕ → ℝ) (m : ℕ) : ℝ :=
1 - ∏ j ∈ Finset.range m, (1 - pv j)
/-- Marginal gain in hit probability from launching one more branch:
`δq(m) = (∏_{j<m} (1 - pv j)) · pv m`. -/
noncomputable def dqhit (pv : ℕ → ℝ) (m : ℕ) : ℝ :=
(∏ j ∈ Finset.range m, (1 - pv j)) * pv m
/-- The per-window objective `q(m) · Δ - c·m` maximized by the optimal
speculative breadth. -/
noncomputable def specObjective (pv : ℕ → ℝ) (Δ c : ℝ) (m : ℕ) : ℝ :=
qhit pv m * Δ - c * m
end SpecActions
Read-back
What the Lean code literally says, in plain math · claude-opus-5
Scope of this read-back. The bundle consists of a namespace SpecActions containing fourteen definitions and no propositions: there is no theorem, lemma, axiom, or Prop-valued statement anywhere, so nothing in the artifact asserts a mathematical claim. Each declaration introduces a total real-valued function built from ordinary field operations on , the integer floor, and finite products. None of the definitions carries any hypothesis: every numeric parameter ranges over all of (there is no requirement that any "probability" argument lie in , that latency parameters be positive, or that ), and every count parameter ranges over all of . Consequently all divisions are Lean's total division, so a division by evaluates to rather than being undefined. The doc-comments and module header describe an intended interpretation (horizons, API latencies, exponential distributions, an ICLR paper's algorithms), but none of that appears in the code: the code defines formulas only, and no declaration relates any two of these formulas to each other.
1. (phit). For a natural number and an arbitrary real ,
where the exponent is the natural-number power of the real base . At the power is by convention, so for every , including (where is used). Nothing constrains , so e.g. gives and gives . This function is not referenced by any other declaration in the bundle.
2. (hits). For a fixed arbitrary real , a function is defined by recursion on its natural-number argument, with two base cases and a two-step step:
The recursion is total: it defines a value at every natural number for every real , with no positivity or boundedness assumption. Note the step uses the value two indices back multiplied by and the value one index back multiplied by ; the constant appears inside the first bracket only. No closed form is asserted for anywhere in the bundle.
3. (hitsClosed). For an arbitrary real and a natural number ,
where is regarded as a real number in the first summand and as a natural exponent in . At both denominators vanish, and by the total-division convention each quotient is , so for all . At the second summand vanishes (since ) and the first is , so . This is an independent definition; the code contains no statement that equals or approximates it.
4. (seqTime). For a natural number and an arbitrary real ,
with coerced to a real. At this is ; at it is ; is permitted and yields a negative value.
5. (specTime). For a natural number and arbitrary reals ,
where is the recursively defined function of item 2 and denotes truncated natural subtraction: the index is for and is when . Hence at the whole expression is , and at it is exactly (since ). The fourth parameter is an arbitrary real fed directly into the recursion; nothing connects it to of item 1. If , or , the fraction is and the first term may also be .
6. (seqCost). For a natural number and an arbitrary real ,
This is the same expression as in item 4, under a different name.
7. (specCost). For a natural number and arbitrary reals ,
again with truncated natural subtraction in the index, so when and when . The parameter is an arbitrary real, not a natural number: it may be negative or fractional. As above, or makes the corresponding quotients .
8. (depthSeqTime). For a natural number and an arbitrary real ,
with coerced to a real; it is at and is negative for negative .
9. (depthSpecTime). For a natural number and arbitrary reals ,
where is coerced to a real before the subtraction, so here is genuine real subtraction (not truncated): at the second summand is , so , which is nonzero in general. The sign convention is , i.e. the second term is added, and it is proportional to and to with no cap or truncation.
10. (depthSeqCost). For a natural number and an arbitrary real ,
the same expression as item 8 under a different name.
11. (depthSpecCost). For a natural number and arbitrary reals , write for the integer floor of the real quotient , regarded thereafter as a real number. Then
Points fixed by the code: the leading term is the bare constant , not ; is coerced to a real so is real subtraction, giving ; the two bracketed branches are weighted by and with no requirement that these weights be in ; the arithmetic is exact real division of the (possibly negative) integer , not integer division; and if then and , so the bracket collapses to and the whole expression becomes . If then , which is permitted.
12. (qhit). For an arbitrary function and a natural number ,
the product being over the finite index set . At the empty product is , so . The values are arbitrary reals: there is no assumption that they lie in , that they are nonincreasing in (despite the doc-comment's "descending order"), or that is monotone in . Only the first values of the sequence are used.
13. (dqhit). For the same arbitrary and natural ,
so at it equals (empty product ). Note it uses the -th value , which is not among the factors of the product. No relation to (such as ) is asserted.
14. (specObjective). For an arbitrary function , arbitrary reals and , and a natural number ,
with as in item 12 and coerced to a real in the second term. At this is . This is a definition of a quantity only: the code contains no claim that any maximizes it, no existence or uniqueness statement about a maximizer, and no optimality characterization.
Confirmed by the mission captain (proposal self-audit).