Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Speculative actions: the cost--latency model

Definition
SpecActions_model

by naimengye · Sep 10, 2026 · Mathlib 0df444a (Lean v4.33.1)

machine-learningprobabilitytheoretical-computer-science

The 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 TTT steps. At each step an actor issues a real API call with latency Exp(β)\mathrm{Exp}(\beta)Exp(β) while a speculator guesses the action with latency Exp(α)\mathrm{Exp}(\alpha)Exp(α); a guess implies the correct next call with probability ppp, independently across steps.

The bundle defines: p(k)=1−(1−p)kp(k)=1-(1-p)^kp(k)=1−(1−p)k, the probability at least one of kkk branches hits (phit); the expected hit count SnS_nSn​ 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 aaa and b<ab<ab<a (depthSeqTime, depthSpecTime, depthSeqCost, depthSpecCost); and the confidence-aware quantities q(m)q(m)q(m), δq(m)\delta q(m)δq(m) and the per-window objective q(m)Δ−cmq(m)\Delta-cmq(m)Δ−cm (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.

Definition code
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
Source
Ye, Ahuja, Liargkovas, Lu, Kaffes, Peng, "Speculative Actions: A Lossless Framework for Faster Agentic Systems", ICLR 2026, arXiv:2510.04371, https://arxiv.org/abs/2510.04371, §5 (pp. 9-10) and Appendices A, C (pp. 13-14, 19-24)
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 R\mathbb{R}R, the integer floor, and finite products. None of the definitions carries any hypothesis: every numeric parameter ranges over all of R\mathbb{R}R (there is no requirement that any "probability" argument lie in [0,1][0,1][0,1], that latency parameters be positive, or that β<α\beta < \alphaβ<α), and every count parameter ranges over all of N\mathbb{N}N. Consequently all divisions are Lean's total division, so a division by 000 evaluates to 000 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. φ(k,p)\varphi(k,p)φ(k,p) (phit). For a natural number kkk and an arbitrary real ppp,

φ(k,p)  =  1−(1−p)k,\varphi(k,p) \;=\; 1-(1-p)^{k},φ(k,p)=1−(1−p)k,

where the exponent is the natural-number power of the real base 1−p1-p1−p. At k=0k=0k=0 the power is 111 by convention, so φ(0,p)=0\varphi(0,p)=0φ(0,p)=0 for every ppp, including p=1p=1p=1 (where 00=10^0=100=1 is used). Nothing constrains ppp, so e.g. p=2p=2p=2 gives φ(k,2)=1−(−1)k\varphi(k,2)=1-(-1)^kφ(k,2)=1−(−1)k and p=−1p=-1p=−1 gives 1−2k1-2^k1−2k. This function is not referenced by any other declaration in the bundle.


2. Sp(n)S_p(n)Sp​(n) (hits). For a fixed arbitrary real ppp, a function N→R\mathbb{N}\to\mathbb{R}N→R is defined by recursion on its natural-number argument, with two base cases and a two-step step:

Sp(0)=0,Sp(1)=p,Sp(n+2)=p(1+Sp(n))+(1−p) Sp(n+1)(n≥0).S_p(0)=0,\qquad S_p(1)=p,\qquad S_p(n+2)=p\bigl(1+S_p(n)\bigr)+(1-p)\,S_p(n+1)\quad(n\ge 0).Sp​(0)=0,Sp​(1)=p,Sp​(n+2)=p(1+Sp​(n))+(1−p)Sp​(n+1)(n≥0).

The recursion is total: it defines a value at every natural number for every real ppp, with no positivity or boundedness assumption. Note the step uses the value two indices back multiplied by ppp and the value one index back multiplied by 1−p1-p1−p; the constant 111 appears inside the first bracket only. No closed form is asserted for SpS_pSp​ anywhere in the bundle.


3. S^(p,n)\hat S(p,n)S^(p,n) (hitsClosed). For an arbitrary real ppp and a natural number nnn,

S^(p,n)  =  p1+p⋅n  +  p2(1+p)2(1−(−p)n),\hat S(p,n) \;=\; \frac{p}{1+p}\cdot n \;+\; \frac{p^{2}}{(1+p)^{2}}\Bigl(1-(-p)^{n}\Bigr),S^(p,n)=1+pp​⋅n+(1+p)2p2​(1−(−p)n),

where nnn is regarded as a real number in the first summand and as a natural exponent in (−p)n(-p)^n(−p)n. At p=−1p=-1p=−1 both denominators vanish, and by the total-division convention each quotient is 000, so S^(−1,n)=0\hat S(-1,n)=0S^(−1,n)=0 for all nnn. At n=0n=0n=0 the second summand vanishes (since (−p)0=1(-p)^0=1(−p)0=1) and the first is 000, so S^(p,0)=0\hat S(p,0)=0S^(p,0)=0. This is an independent definition; the code contains no statement that S^(p,n)\hat S(p,n)S^(p,n) equals Sp(n)S_p(n)Sp​(n) or approximates it.


4. Tseq(T,β)T_{\mathrm{seq}}(T,\beta)Tseq​(T,β) (seqTime). For a natural number TTT and an arbitrary real β\betaβ,

Tseq(T,β)=Tβ,T_{\mathrm{seq}}(T,\beta)=\frac{T}{\beta},Tseq​(T,β)=βT​,

with TTT coerced to a real. At β=0\beta=0β=0 this is 000; at T=0T=0T=0 it is 000; β<0\beta<0β<0 is permitted and yields a negative value.


5. Tspec(T,α,β,pk)T_{\mathrm{spec}}(T,\alpha,\beta,p_k)Tspec​(T,α,β,pk​) (specTime). For a natural number TTT and arbitrary reals α,β,pk\alpha,\beta,p_kα,β,pk​,

Tspec(T,α,β,pk)=Tβ  −  Spk(T⊖1)⋅αβ(α+β),T_{\mathrm{spec}}(T,\alpha,\beta,p_k)=\frac{T}{\beta}\;-\;S_{p_k}(T\ominus 1)\cdot\frac{\alpha}{\beta(\alpha+\beta)},Tspec​(T,α,β,pk​)=βT​−Spk​​(T⊖1)⋅β(α+β)α​,

where SSS is the recursively defined function of item 2 and T⊖1T\ominus 1T⊖1 denotes truncated natural subtraction: the index is T−1T-1T−1 for T≥1T\ge 1T≥1 and is 000 when T=0T=0T=0. Hence at T=0T=0T=0 the whole expression is 0−Spk(0)⋅(⋅)=00-S_{p_k}(0)\cdot(\cdot)=00−Spk​​(0)⋅(⋅)=0, and at T=1T=1T=1 it is 1/β1/\beta1/β exactly (since Spk(0)=0S_{p_k}(0)=0Spk​​(0)=0). The fourth parameter pkp_kpk​ is an arbitrary real fed directly into the recursion; nothing connects it to φ\varphiφ of item 1. If β=0\beta=0β=0, or α+β=0\alpha+\beta=0α+β=0, the fraction α/(β(α+β))\alpha/(\beta(\alpha+\beta))α/(β(α+β)) is 000 and the first term T/βT/\betaT/β may also be 000.


6. Cseq(T,β)C_{\mathrm{seq}}(T,\beta)Cseq​(T,β) (seqCost). For a natural number TTT and an arbitrary real β\betaβ,

Cseq(T,β)=Tβ.C_{\mathrm{seq}}(T,\beta)=\frac{T}{\beta}.Cseq​(T,β)=βT​.

This is the same expression as TseqT_{\mathrm{seq}}Tseq​ in item 4, under a different name.


7. Cspec(T,α,β,pk,k~)C_{\mathrm{spec}}(T,\alpha,\beta,p_k,\tilde k)Cspec​(T,α,β,pk​,k~) (specCost). For a natural number TTT and arbitrary reals α,β,pk,k~\alpha,\beta,p_k,\tilde kα,β,pk​,k~,

Cspec  =  Tβ (k~+1)  −  Spk(T⊖1)(k~⋅1β+αβ(α+β)),C_{\mathrm{spec}} \;=\; \frac{T}{\beta}\,(\tilde k+1)\;-\;S_{p_k}(T\ominus 1)\left(\tilde k\cdot\frac{1}{\beta}+\frac{\alpha}{\beta(\alpha+\beta)}\right),Cspec​=βT​(k~+1)−Spk​​(T⊖1)(k~⋅β1​+β(α+β)α​),

again with truncated natural subtraction in the index, so Cspec=0C_{\mathrm{spec}}=0Cspec​=0 when T=0T=0T=0 and Cspec=(k~+1)/βC_{\mathrm{spec}}=(\tilde k+1)/\betaCspec​=(k~+1)/β when T=1T=1T=1. The parameter k~\tilde kk~ is an arbitrary real, not a natural number: it may be negative or fractional. As above, β=0\beta=0β=0 or α+β=0\alpha+\beta=0α+β=0 makes the corresponding quotients 000.


8. Dseq(T,a)D_{\mathrm{seq}}(T,a)Dseq​(T,a) (depthSeqTime). For a natural number TTT and an arbitrary real aaa,

Dseq(T,a)=a⋅T,D_{\mathrm{seq}}(T,a)=a\cdot T,Dseq​(T,a)=a⋅T,

with TTT coerced to a real; it is 000 at T=0T=0T=0 and is negative for negative aaa.


9. Dspec(T,a,b,p)D_{\mathrm{spec}}(T,a,b,p)Dspec​(T,a,b,p) (depthSpecTime). For a natural number TTT and arbitrary reals a,b,pa,b,pa,b,p,

Dspec(T,a,b,p)=a T+(T−1) p (b−a),D_{\mathrm{spec}}(T,a,b,p)=a\,T+(T-1)\,p\,(b-a),Dspec​(T,a,b,p)=aT+(T−1)p(b−a),

where TTT is coerced to a real before the subtraction, so here T−1T-1T−1 is genuine real subtraction (not truncated): at T=0T=0T=0 the second summand is −p(b−a)-p(b-a)−p(b−a), so Dspec(0,a,b,p)=−p(b−a)D_{\mathrm{spec}}(0,a,b,p)=-p(b-a)Dspec​(0,a,b,p)=−p(b−a), which is nonzero in general. The sign convention is b−ab-ab−a, i.e. the second term is added, and it is proportional to ppp and to T−1T-1T−1 with no cap or truncation.


10. DCseq(T,a)DC_{\mathrm{seq}}(T,a)DCseq​(T,a) (depthSeqCost). For a natural number TTT and an arbitrary real aaa,

DCseq(T,a)=a⋅T,DC_{\mathrm{seq}}(T,a)=a\cdot T,DCseq​(T,a)=a⋅T,

the same expression as item 8 under a different name.


11. DCspec(T,a,b,p)DC_{\mathrm{spec}}(T,a,b,p)DCspec​(T,a,b,p) (depthSpecCost). For a natural number TTT and arbitrary reals a,b,pa,b,pa,b,p, write F=⌊a/b⌋F=\lfloor a/b\rfloorF=⌊a/b⌋ for the integer floor of the real quotient a/ba/ba/b, regarded thereafter as a real number. Then

DCspec(T,a,b,p)=a+(T−1)[p(a+F b)+(1−p)(a (F+1)−(1+F) F2 b)].DC_{\mathrm{spec}}(T,a,b,p)=a+(T-1)\Bigl[p\bigl(a+F\,b\bigr)+(1-p)\Bigl(a\,(F+1)-\frac{(1+F)\,F}{2}\,b\Bigr)\Bigr].DCspec​(T,a,b,p)=a+(T−1)[p(a+Fb)+(1−p)(a(F+1)−2(1+F)F​b)].

Points fixed by the code: the leading term is the bare constant aaa, not a Ta\,TaT; TTT is coerced to a real so T−1T-1T−1 is real subtraction, giving DCspec(0,a,b,p)=a−[ ⋯ ]DC_{\mathrm{spec}}(0,a,b,p)=a-\bigl[\,\cdots\,\bigr]DCspec​(0,a,b,p)=a−[⋯]; the two bracketed branches are weighted by ppp and 1−p1-p1−p with no requirement that these weights be in [0,1][0,1][0,1]; the arithmetic (1+F)F2\tfrac{(1+F)F}{2}2(1+F)F​ is exact real division of the (possibly negative) integer FFF, not integer division; and if b=0b=0b=0 then a/b=0a/b=0a/b=0 and F=0F=0F=0, so the bracket collapses to p a+(1−p) a=ap\,a+(1-p)\,a=apa+(1−p)a=a and the whole expression becomes a+(T−1)a=aTa+(T-1)a=aTa+(T−1)a=aT. If a/b<0a/b<0a/b<0 then F≤−1F\le -1F≤−1, which is permitted.


12. q(m)q(m)q(m) (qhit). For an arbitrary function p∙:N→Rp_\bullet:\mathbb{N}\to\mathbb{R}p∙​:N→R and a natural number mmm,

q(p∙,m)=1−∏j=0m−1(1−p∙(j)),q(p_\bullet,m)=1-\prod_{j=0}^{m-1}\bigl(1-p_\bullet(j)\bigr),q(p∙​,m)=1−j=0∏m−1​(1−p∙​(j)),

the product being over the finite index set {0,1,…,m−1}\{0,1,\dots,m-1\}{0,1,…,m−1}. At m=0m=0m=0 the empty product is 111, so q(p∙,0)=0q(p_\bullet,0)=0q(p∙​,0)=0. The values p∙(j)p_\bullet(j)p∙​(j) are arbitrary reals: there is no assumption that they lie in [0,1][0,1][0,1], that they are nonincreasing in jjj (despite the doc-comment's "descending order"), or that qqq is monotone in mmm. Only the first mmm values of the sequence are used.


13. δq(m)\delta q(m)δq(m) (dqhit). For the same arbitrary p∙:N→Rp_\bullet:\mathbb{N}\to\mathbb{R}p∙​:N→R and natural mmm,

δq(p∙,m)=(∏j=0m−1(1−p∙(j)))⋅p∙(m),\delta q(p_\bullet,m)=\left(\prod_{j=0}^{m-1}\bigl(1-p_\bullet(j)\bigr)\right)\cdot p_\bullet(m),δq(p∙​,m)=(j=0∏m−1​(1−p∙​(j)))⋅p∙​(m),

so at m=0m=0m=0 it equals p∙(0)p_\bullet(0)p∙​(0) (empty product =1=1=1). Note it uses the mmm-th value p∙(m)p_\bullet(m)p∙​(m), which is not among the factors of the product. No relation to qqq (such as δq(m)=q(m+1)−q(m)\delta q(m)=q(m+1)-q(m)δq(m)=q(m+1)−q(m)) is asserted.


14. J(m)J(m)J(m) (specObjective). For an arbitrary function p∙:N→Rp_\bullet:\mathbb{N}\to\mathbb{R}p∙​:N→R, arbitrary reals Δ\DeltaΔ and ccc, and a natural number mmm,

J(p∙,Δ,c,m)=q(p∙,m)⋅Δ−c m,J(p_\bullet,\Delta,c,m)=q(p_\bullet,m)\cdot \Delta-c\,m,J(p∙​,Δ,c,m)=q(p∙​,m)⋅Δ−cm,

with qqq as in item 12 and mmm coerced to a real in the second term. At m=0m=0m=0 this is 000. This is a definition of a quantity only: the code contains no claim that any mmm maximizes it, no existence or uniqueness statement about a maximizer, and no optimality characterization.

Human review
  • Endorsed by Shuze Chen · Sep 12, 2026

  • Endorsed by naimengye · Sep 12, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me