Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4 — finite-horizon relative cost increase

Proved
SpecActions.thm4_cost_finite_horizon

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

machine-learningprobabilitytheoretical-computer-science

Let k~\tilde kk~ be the number of distinct actions produced across the kkk speculative branches (duplicated speculations are killed). Then for every T≥1T\ge 1T≥1, α,β>0\alpha,\beta>0α,β>0 and pk∈[0,1]p_k\in[0,1]pk​∈[0,1],

E[Mspec−Mseq]E[Mseq]=k~−1T(k~+αα+β)[(T−1)pk1+pk+pk2(1+pk)2−pk2(1+pk)2(−pk)T−1].\frac{\mathbb{E}[M_{\mathrm{spec}}-M_{\mathrm{seq}}]}{\mathbb{E}[M_{\mathrm{seq}}]}=\tilde k-\frac{1}{T}\left(\tilde k+\frac{\alpha}{\alpha+\beta}\right)\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[Mseq​]E[Mspec​−Mseq​]​=k~−T1​(k~+α+βα​)[1+pk​(T−1)pk​​+(1+pk​)2pk2​​−(1+pk​)2pk2​​(−pk​)T−1].

The bracket is the same ST−1S_{T-1}ST−1​ that governs the latency ratio, which is what lets a practitioner tune the breadth kkk against a joint latency/cost budget from a single estimate of pkp_kpk​.

Preamble
import Definitions.Def_SpecActions_model
Formal statement
import Definitions.Def_SpecActions_model

namespace SpecActions
theorem thm4_cost_finite_horizon (T : ℕ) (α β pk kt : ℝ) (hT : 1 ≤ T)
    (hα : 0 < α) (hβ : 0 < β) (hpk0 : 0 ≤ pk) (hpk1 : pk ≤ 1) :
    (specCost T α β pk kt - seqCost T β) / seqCost T β
      = kt - (1 / (T : ℝ)) * (kt + α / (α + β)) *
          (((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, Theorem 4, Appendix C.1 (p. 19), cost expression
Read-back

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

Read-back — thm4_cost_finite_horizon

Data and standing assumptions. The statement fixes a natural number TTT and four real numbers α\alphaα, β\betaβ, pkp_kpk​, ktk_tkt​ (all universally quantified; α,β,pk,kt\alpha,\beta,p_k,k_tα,β,pk​,kt​ are arbitrary reals, not constrained to be integers or probabilities except as listed). It assumes exactly five hypotheses:

  • T≥1T \ge 1T≥1 (as a natural number),
  • α>0\alpha > 0α>0,
  • β>0\beta > 0β>0,
  • pk≥0p_k \ge 0pk​≥0,
  • pk≤1p_k \le 1pk​≤1.

Nothing else is assumed: in particular no order relation between α\alphaα and β\betaβ is imposed, and ktk_tkt​ is completely unconstrained — it may be 000, negative, or non-integral.

The two quantities being compared. Both are defined in the imported bundle and are unfolded here.

First, an auxiliary real sequence S(p):N→RS^{(p)} : \mathbb{N} \to \mathbb{R}S(p):N→R, depending on a real parameter ppp, given by the two-step recursion

S0(p)=0,S1(p)=p,Sn+2(p)=p(1+Sn(p))+(1−p) Sn+1(p)(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).S0(p)​=0,S1(p)​=p,Sn+2(p)​=p(1+Sn(p)​)+(1−p)Sn+1(p)​(n≥0).

This is the recursively defined sequence; the statement does not refer to any closed form for it.

Then

Cseq(T,β)  =  Tβ,C_{\mathrm{seq}}(T,\beta) \;=\; \frac{T}{\beta},Cseq​(T,β)=βT​, Cspec(T,α,β,pk,kt)  =  Tβ (kt+1)  −  S T−1(pk)(ktβ  +  αβ (α+β)),C_{\mathrm{spec}}(T,\alpha,\beta,p_k,k_t) \;=\; \frac{T}{\beta}\,(k_t + 1) \;-\; S^{(p_k)}_{\,T-1}\left(\frac{k_t}{\beta} \;+\; \frac{\alpha}{\beta\,(\alpha+\beta)}\right),Cspec​(T,α,β,pk​,kt​)=βT​(kt​+1)−ST−1(pk​)​(βkt​​+β(α+β)α​),

where in the index T−1T-1T−1 the subtraction is truncated natural-number subtraction (so it would be 000 at T=0T=0T=0; under the hypothesis T≥1T\ge 1T≥1 it coincides with the ordinary T−1T-1T−1). Here TTT is coerced to a real number wherever it occurs in an arithmetic expression.

The asserted identity. The claim is the following exact equality of real numbers:

Cspec(T,α,β,pk,kt)−Cseq(T,β)Cseq(T,β)  =  kt  −  1T(kt+αα+β)⋅F,\frac{C_{\mathrm{spec}}(T,\alpha,\beta,p_k,k_t) - C_{\mathrm{seq}}(T,\beta)}{C_{\mathrm{seq}}(T,\beta)} \;=\; k_t \;-\; \frac{1}{T}\left(k_t + \frac{\alpha}{\alpha+\beta}\right) \cdot F,Cseq​(T,β)Cspec​(T,α,β,pk​,kt​)−Cseq​(T,β)​=kt​−T1​(kt​+α+βα​)⋅F,

where the factor FFF is written out explicitly (not via any named definition) as

F  =  (T−1) pk1+pk  +  pk 2(1+pk)2  −  pk 2(1+pk)2 (−pk) T−1.F \;=\; (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}.F=(T−1)1+pk​pk​​+(1+pk​)2pk2​​−(1+pk​)2pk2​​(−pk​)T−1.

In FFF, the coefficient (T−1)(T-1)(T−1) is real subtraction on the coerced value of TTT, while the exponent T−1T-1T−1 in (−pk)T−1(-p_k)^{T-1}(−pk​)T−1 is again truncated natural subtraction, and the power is a natural-number power of the possibly negative base −pk-p_k−pk​. Note that FFF is algebraically the same as pk1+pk(T−1)+pk2(1+pk)2(1−(−pk)T−1)\frac{p_k}{1+p_k}(T-1) + \frac{p_k^2}{(1+p_k)^2}\bigl(1 - (-p_k)^{T-1}\bigr)1+pk​pk​​(T−1)+(1+pk​)2pk2​​(1−(−pk​)T−1).

Well-definedness and the algebraic content. All divisions are total real division (division by zero would yield 000 rather than being undefined), but under the hypotheses no such degeneracy occurs on either side: β>0\beta > 0β>0 and T≥1T \ge 1T≥1 give Cseq=T/β≠0C_{\mathrm{seq}} = T/\beta \ne 0Cseq​=T/β=0, so the left-hand quotient is a genuine ratio; α+β>0\alpha + \beta > 0α+β>0; 1+pk≥1>01 + p_k \ge 1 > 01+pk​≥1>0 since pk≥0p_k \ge 0pk​≥0; and T≠0T \ne 0T=0 makes 1/T1/T1/T genuine. Expanding the definitions, the left-hand side simplifies to kt−1T(kt+αα+β)ST−1(pk)k_t - \frac{1}{T}\left(k_t + \frac{\alpha}{\alpha+\beta}\right) S^{(p_k)}_{T-1}kt​−T1​(kt​+α+βα​)ST−1(pk​)​, so the equality asserts, for every admissible choice of the parameters, that the recursively defined quantity ST−1(pk)S^{(p_k)}_{T-1}ST−1(pk​)​ may be replaced by the explicit expression FFF — except that the replacement is only forced where the multiplier (kt+αα+β)\left(k_t + \frac{\alpha}{\alpha+\beta}\right)(kt​+α+βα​) is nonzero.

Degenerate and boundary cases silently included.

  • T=1T = 1T=1: the index is S0(pk)=0S^{(p_k)}_0 = 0S0(pk​)​=0 and F=0+pk2(1+pk)2−pk2(1+pk)2⋅(−pk)0=0F = 0 + \frac{p_k^2}{(1+p_k)^2} - \frac{p_k^2}{(1+p_k)^2}\cdot(-p_k)^0 = 0F=0+(1+pk​)2pk2​​−(1+pk​)2pk2​​⋅(−pk​)0=0; both sides equal ktk_tkt​, so the assertion is an identity with no content at this value.
  • pk=0p_k = 0pk​=0: every Sn(0)=0S^{(0)}_n = 0Sn(0)​=0 and F=0F = 0F=0; both sides again reduce to ktk_tkt​.
  • pk=1p_k = 1pk​=1 (permitted by pk≤1p_k \le 1pk​≤1): the factor (−pk)T−1=(−1)T−1(-p_k)^{T-1} = (-1)^{T-1}(−pk​)T−1=(−1)T−1 alternates in sign, and 1+pk=21 + p_k = 21+pk​=2.
  • kt=−αα+βk_t = -\frac{\alpha}{\alpha+\beta}kt​=−α+βα​: the multiplier of FFF vanishes and the equality holds for trivial reasons regardless of FFF.
  • T=0T = 0T=0 is excluded by hypothesis; had it been admitted, the left-hand side would be a division by 000.
  • The hypotheses are jointly satisfiable (for instance T=1T = 1T=1, α=β=1\alpha = \beta = 1α=β=1, pk=0p_k = 0pk​=0, kt=0k_t = 0kt​=0), so the statement is not vacuous.

Unused context. The imported bundle also defines quantities named for hit probabilities, a closed form for the hit sequence, runtime (as opposed to cost) analogues, depth-focused runtime and cost expressions, and confidence-aware breadth objectives; none of these appear in this statement. Only the sequence S(p)S^{(p)}S(p), CseqC_{\mathrm{seq}}Cseq​ and CspecC_{\mathrm{spec}}Cspec​ are referenced.

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