Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4 — asymptotic relative cost increase

Proved
SpecActions.thm4_cost_limit

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

machine-learningprobabilitytheoretical-computer-science

As the horizon grows, the relative cost increase of Algorithm 1 converges:

E[Mspec−Mseq]E[Mseq]  →T→∞  k~−(k~+αα+β)pk1+pk\frac{\mathbb{E}[M_{\mathrm{spec}}-M_{\mathrm{seq}}]}{\mathbb{E}[M_{\mathrm{seq}}]}\;\xrightarrow[T\to\infty]{}\;\tilde k-\left(\tilde k+\frac{\alpha}{\alpha+\beta}\right)\frac{p_k}{1+p_k}E[Mseq​]E[Mspec​−Mseq​]​T→∞​k~−(k~+α+βα​)1+pk​pk​​

for all α,β>0\alpha,\beta>0α,β>0 and pk∈[0,1]p_k\in[0,1]pk​∈[0,1], with k~\tilde kk~ the number of distinct actions across the kkk branches. Paired with the asymptotic latency ratio, this is the closed-form Pareto trade-off the paper uses to choose the speculative breadth offline.

Preamble
import Definitions.Def_SpecActions_model
Formal statement
import Definitions.Def_SpecActions_model
import Mathlib.Order.Filter.AtTopBot.Basic

namespace SpecActions
open Filter Topology
theorem thm4_cost_limit (α β pk kt : ℝ) (hα : 0 < α) (hβ : 0 < β)
    (hpk0 : 0 ≤ pk) (hpk1 : pk ≤ 1) :
    Tendsto (fun T : ℕ => (specCost T α β pk kt - seqCost T β) / seqCost T β)
      atTop (𝓝 (kt - (kt + α / (α + β)) * (pk / (1 + pk)))) := 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), the T→∞T\to\inftyT→∞ limit; also §5.1 (p. 9)
Read-back

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

Read-back of thm4_cost_limit.

The statement fixes four real numbers α, β, pk, k~\alpha,\ \beta,\ p_k,\ \tilde kα, β, pk​, k~ together with exactly four hypotheses:

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

Nothing else is assumed about them. In particular there is no assumption relating α\alphaα and β\betaβ to each other (neither β<α\beta < \alphaβ<α nor any ordering), and k~\tilde kk~ is a completely unconstrained real number — it may be negative, zero, or non-integral, and is not required to be a positive integer or to be related to pkp_kpk​ in any way.

Two auxiliary quantities from the imported bundle enter the statement, and both must be unfolded.

First, the hit count Sp(n)S_p(n)Sp​(n), a real-valued function of a natural number nnn defined by the total two-step recursion

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

This recursion is the only thing the statement knows about SpS_pSp​; the separately-defined closed form p1+pn+p2(1+p)2(1−(−p)n)\frac{p}{1+p}n + \frac{p^2}{(1+p)^2}\bigl(1-(-p)^n\bigr)1+pp​n+(1+p)2p2​(1−(−p)n) is not referenced here, and no identity between the two is asserted.

Second, the two cost functions of a natural number TTT (in both, TTT is cast from N\mathbb{N}N into R\mathbb{R}R):

Cseq(T)  =  Tβ,C_{\mathrm{seq}}(T) \;=\; \frac{T}{\beta},Cseq​(T)=βT​, Cspec(T)  =  Tβ (k~+1)  −  Spk(T−˙1)(k~β+αβ(α+β)),C_{\mathrm{spec}}(T) \;=\; \frac{T}{\beta}\,(\tilde k + 1)\;-\;S_{p_k}(T \mathbin{\dot-} 1)\left(\frac{\tilde k}{\beta} + \frac{\alpha}{\beta(\alpha+\beta)}\right),Cspec​(T)=βT​(k~+1)−Spk​​(T−˙​1)(βk~​+β(α+β)α​),

where T−˙1T \mathbin{\dot-} 1T−˙​1 denotes truncated natural-number subtraction: it equals T−1T-1T−1 for T≥1T \ge 1T≥1 and equals 000 when T=0T = 0T=0.

The assertion is then a single limit statement about the relative cost gap

R(T)  =  Cspec(T)−Cseq(T)Cseq(T),R(T) \;=\; \frac{C_{\mathrm{spec}}(T) - C_{\mathrm{seq}}(T)}{C_{\mathrm{seq}}(T)},R(T)=Cseq​(T)Cspec​(T)−Cseq​(T)​,

namely that the sequence (R(T))T∈N\bigl(R(T)\bigr)_{T \in \mathbb{N}}(R(T))T∈N​ converges, as TTT runs to infinity through the natural numbers (along the "eventually, for all sufficiently large TTT" filter), to the real number

k~  −  (k~+αα+β)⋅pk1+pk\tilde k \;-\; \left(\tilde k + \frac{\alpha}{\alpha+\beta}\right)\cdot\frac{p_k}{1+p_k}k~−(k~+α+βα​)⋅1+pk​pk​​

in the standard topology of R\mathbb{R}R. This is a claim both that the limit exists and that its value is exactly the displayed expression; it is an unconditional two-sided convergence claim, not an inequality, not a bound, and not a one-sided or asymptotic-order estimate. Nothing is asserted about the rate of convergence, about monotonicity in TTT, or about the value of R(T)R(T)R(T) at any particular finite TTT.

Degenerate and boundary cases silently covered by the quantifiers:

  • T=0T = 0T=0. Here Cseq(0)=0/β=0C_{\mathrm{seq}}(0) = 0/\beta = 0Cseq​(0)=0/β=0 and Cspec(0)=0−Spk(0) (⋯ )=0C_{\mathrm{spec}}(0) = 0 - S_{p_k}(0)\,(\cdots) = 0Cspec​(0)=0−Spk​​(0)(⋯)=0, so the quotient defining R(0)R(0)R(0) is 0/00/00/0, which in this setting evaluates to 000 by the total-division convention rather than being undefined. Because the claim concerns only the behaviour for large TTT, this value (and any finite number of initial values) has no bearing on the assertion.
  • T≥1T \ge 1T≥1. Since β>0\beta > 0β>0, the denominator T/βT/\betaT/β is nonzero, so R(T)R(T)R(T) is an ordinary quotient there.
  • pk=0p_k = 0pk​=0 is permitted by 0≤pk0 \le p_k0≤pk​. Then S0≡0S_0 \equiv 0S0​≡0, so R(T)=k~R(T) = \tilde kR(T)=k~ for every T≥1T \ge 1T≥1, and the claimed limit specializes to k~−0=k~\tilde k - 0 = \tilde kk~−0=k~.
  • pk=1p_k = 1pk​=1 is permitted by pk≤1p_k \le 1pk​≤1; the claimed limit is then k~−12(k~+αα+β)\tilde k - \tfrac{1}{2}\bigl(\tilde k + \tfrac{\alpha}{\alpha+\beta}\bigr)k~−21​(k~+α+βα​).
  • k~\tilde kk~ negative or zero is permitted, in which case CspecC_{\mathrm{spec}}Cspec​ need not exceed CseqC_{\mathrm{seq}}Cseq​ and the limit value can be negative.
  • No division by zero occurs in the limit expression: 1+pk≥1>01 + p_k \ge 1 > 01+pk​≥1>0 from 0≤pk0 \le p_k0≤pk​, and α+β>0\alpha + \beta > 0α+β>0 from α,β>0\alpha,\beta > 0α,β>0.

The four hypotheses are simultaneously satisfiable (for instance α=β=1\alpha = \beta = 1α=β=1, pk=12p_k = \tfrac12pk​=21​, and any k~\tilde kk~), so the statement is not vacuous.

Finally, note the shape of the asserted limit value: it depends on α\alphaα and β\betaβ only through the single ratio αα+β\dfrac{\alpha}{\alpha+\beta}α+βα​, on pkp_kpk​ only through pk1+pk\dfrac{p_k}{1+p_k}1+pk​pk​​, and is affine in k~\tilde kk~; the parameter β\betaβ does not otherwise appear in the limit, even though it appears in both cost functions.

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