Prove2Me
Navigate
DiscoverFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

Proposition 1 — finite-horizon latency ratio (goal theorem)

Proved
SpecActions.prop1_finite_horizon

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

machine-learningprobabilitytheoretical-computer-science

Under Assumptions 1–2 of the paper, with per-step hit probability pk=p(k)p_k=p(k)pk​=p(k), speculator latency Exp(α)\mathrm{Exp}(\alpha)Exp(α) and real-call latency Exp(β)\mathrm{Exp}(\beta)Exp(β), the ratio of the expected runtime of Algorithm 1 to that of strictly sequential execution is

E[Tspec]E[Tseq]=1−1T αα+β[(T−1)pk1+pk+pk2(1+pk)2−pk2(1+pk)2(−pk)T−1]\frac{\mathbb{E}[T_{\mathrm{spec}}]}{\mathbb{E}[T_{\mathrm{seq}}]}=1-\frac{1}{T}\,\frac{\alpha}{\alpha+\beta}\left[\frac{(T-1)p_k}{1+p_k}+\frac{p_k^2}{(1+p_k)^2}-\frac{p_k^2}{(1+p_k)^2}(-p_k)^{T-1}\right]E[Tseq​]E[Tspec​]​=1−T1​α+βα​[1+pk​(T−1)pk​​+(1+pk​)2pk2​​−(1+pk​)2pk2​​(−pk​)T−1]

for every horizon T≥1T\ge 1T≥1, α,β>0\alpha,\beta>0α,β>0 and pk∈[0,1]p_k\in[0,1]pk​∈[0,1].

Here E[Tseq]=T/β\mathbb{E}[T_{\mathrm{seq}}]=T/\betaE[Tseq​]=T/β and E[Tspec]=T/β−ST−1⋅αβ(α+β)\mathbb{E}[T_{\mathrm{spec}}]=T/\beta-S_{T-1}\cdot\frac{\alpha}{\beta(\alpha+\beta)}E[Tspec​]=T/β−ST−1​⋅β(α+β)α​, the sequential runtime less one expected saving per hit. The identity is the goal theorem of this mission.

Preamble
import Definitions.Def_SpecActions_model
Formal statement
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
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, Proposition 1 (p. 4), with proof in Appendix A (pp. 13–14)
Read-back

What the Lean code literally says, in plain math · claude-opus-5

Read-back — SpecActions.prop1_finite_horizon.

The declaration is a universally quantified statement about a natural number TTT and three real numbers α\alphaα, β\betaβ, pkp_kpk​, under the five hypotheses

1≤T,α>0,β>0,0≤pk,pk≤1.1 \le T,\qquad \alpha > 0,\qquad \beta > 0,\qquad 0 \le p_k,\qquad p_k \le 1 .1≤T,α>0,β>0,0≤pk​,pk​≤1.

No other assumption is imposed: in particular no ordering between α\alphaα and β\betaβ is required, pkp_kpk​ is allowed to be exactly 000 or exactly 111, and TTT may be arbitrarily large. All five hypotheses are simultaneously satisfiable (e.g. T=1T = 1T=1, α=β=1\alpha = \beta = 1α=β=1, pk=0p_k = 0pk​=0), so the statement is not vacuous.

Two quantities from the imported bundle occur in the claim, and both must be unfolded. First,

seqTime(T,β)  =  Tβ,\mathrm{seqTime}(T,\beta) \;=\; \frac{T}{\beta},seqTime(T,β)=βT​,

with the natural number TTT cast to a real. Second,

specTime(T,α,β,pk)  =  Tβ  −  S T−1(pk)⋅αβ (α+β),\mathrm{specTime}(T,\alpha,\beta,p_k) \;=\; \frac{T}{\beta} \;-\; S_{\,T-1}(p_k)\cdot\frac{\alpha}{\beta\,(\alpha+\beta)},specTime(T,α,β,pk​)=βT​−ST−1​(pk​)⋅β(α+β)α​,

where Sn(p)S_n(p)Sn​(p) is the recursively defined sequence of the bundle (not the separately supplied closed-form expression hitsClosed), given by

S0(p)=0,S1(p)=p,Sn+2(p)=p(1+Sn(p))+(1−p) Sn+1(p).S_0(p) = 0,\qquad S_1(p) = p,\qquad S_{n+2}(p) = p\bigl(1 + S_n(p)\bigr) + (1-p)\,S_{n+1}(p).S0​(p)=0,S1​(p)=p,Sn+2​(p)=p(1+Sn​(p))+(1−p)Sn+1​(p).

The index T−1T-1T−1 is truncated subtraction on natural numbers; under the hypothesis T≥1T \ge 1T≥1 it is the ordinary T−1T-1T−1 (had T=0T = 0T=0 been allowed it would evaluate to S0=0S_0 = 0S0​=0).

The assertion is the exact equality of the ratio specTime/seqTime\mathrm{specTime}/\mathrm{seqTime}specTime/seqTime with an explicit closed-form expression:

Tβ−S T−1(pk)⋅αβ(α+β)Tβ  =  1  −  1T⋅αα+β[ (T−1) pk1+pk  +  pk2(1+pk)2  −  pk2(1+pk)2 (−pk) T−1 ].\frac{\dfrac{T}{\beta} - S_{\,T-1}(p_k)\cdot\dfrac{\alpha}{\beta(\alpha+\beta)}}{\dfrac{T}{\beta}} \;=\; 1 \;-\; \frac{1}{T}\cdot\frac{\alpha}{\alpha+\beta}\left[\,(T-1)\,\frac{p_k}{1+p_k} \;+\; \frac{p_k^{2}}{(1+p_k)^{2}} \;-\; \frac{p_k^{2}}{(1+p_k)^{2}}\,(-p_k)^{\,T-1}\,\right].βT​βT​−ST−1​(pk​)⋅β(α+β)α​​=1−T1​⋅α+βα​[(T−1)1+pk​pk​​+(1+pk​)2pk2​​−(1+pk​)2pk2​​(−pk​)T−1].

Two occurrences of "T−1T-1T−1" on the right-hand side are of different kinds: the factor (T−1)(T-1)(T−1) multiplying pk/(1+pk)p_k/(1+p_k)pk​/(1+pk​) is real subtraction applied to the cast of TTT, whereas the exponent in (−pk)T−1(-p_k)^{T-1}(−pk​)T−1 is a natural-number exponent formed by truncated subtraction. Under T≥1T \ge 1T≥1 the two agree numerically. The power (−pk)T−1(-p_k)^{T-1}(−pk​)T−1 is a natural power of a non-positive real, so it alternates in sign with the parity of T−1T-1T−1.

On well-definedness and degenerate cases: because T≥1T \ge 1T≥1 and β>0\beta > 0β>0, the divisor seqTime(T,β)=T/β\mathrm{seqTime}(T,\beta) = T/\betaseqTime(T,β)=T/β is strictly positive, so the quotient on the left is an honest division and not a division by zero; likewise 1/T1/T1/T is well defined and 1+pk≥1>01 + p_k \ge 1 > 01+pk​≥1>0, so neither pk/(1+pk)p_k/(1+p_k)pk​/(1+pk​) nor pk2/(1+pk)2p_k^{2}/(1+p_k)^{2}pk2​/(1+pk​)2 can degenerate. In the boundary case T=1T = 1T=1 the left-hand side is 111 (since S0(pk)=0S_0(p_k) = 0S0​(pk​)=0) and the bracket on the right is 0⋅pk1+pk+pk2(1+pk)2−pk2(1+pk)2⋅(−pk)0=00 \cdot \frac{p_k}{1+p_k} + \frac{p_k^{2}}{(1+p_k)^{2}} - \frac{p_k^{2}}{(1+p_k)^{2}}\cdot(-p_k)^{0} = 00⋅1+pk​pk​​+(1+pk​)2pk2​​−(1+pk​)2pk2​​⋅(−pk​)0=0, so both sides equal 111. In the case pk=0p_k = 0pk​=0 the recursion gives Sn(0)=0S_n(0) = 0Sn​(0)=0 for every nnn and the bracket vanishes, again making both sides equal to 111. Since α>0\alpha > 0α>0 and β>0\beta > 0β>0 force α/(α+β)≠0\alpha/(\alpha+\beta) \ne 0α/(α+β)=0, and T≠0T \ne 0T=0, the asserted identity is equivalent to the plain statement that

S T−1(pk)  =  (T−1) pk1+pk+pk2(1+pk)2(1−(−pk) T−1),S_{\,T-1}(p_k) \;=\; (T-1)\,\frac{p_k}{1+p_k} + \frac{p_k^{2}}{(1+p_k)^{2}}\bigl(1 - (-p_k)^{\,T-1}\bigr),ST−1​(pk​)=(T−1)1+pk​pk​​+(1+pk​)2pk2​​(1−(−pk​)T−1),

i.e. the equality of the recursively defined sequence with that explicit formula at index T−1T-1T−1; the parameters α\alphaα and β\betaβ cancel entirely from the content of the claim and enter only through the requirement that they be positive.

The declaration carries no proof (its body is left as an unproved placeholder).

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 paper
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me