Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 1 — asymptotic latency ratio as T→∞T\to\inftyT→∞

Proved
SpecActions.prop1_limit

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

machine-learningprobabilitytheoretical-computer-science

As the horizon grows, the latency ratio of Algorithm 1 converges:

E[Tspec]E[Tseq]  →T→∞  1−pk1+pk⋅αα+β\frac{\mathbb{E}[T_{\mathrm{spec}}]}{\mathbb{E}[T_{\mathrm{seq}}]}\;\xrightarrow[T\to\infty]{}\;1-\frac{p_k}{1+p_k}\cdot\frac{\alpha}{\alpha+\beta}E[Tseq​]E[Tspec​]​T→∞​1−1+pk​pk​​⋅α+βα​

for all α,β>0\alpha,\beta>0α,β>0 and pk∈[0,1]p_k\in[0,1]pk​∈[0,1]. The oscillating term (−pk)T−1(-p_k)^{T-1}(−pk​)T−1 is bounded but does not vanish termwise in an obvious way, so it must be controlled uniformly before the 1/T1/T1/T prefactor is taken to zero.

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 prop1_limit (α β pk : ℝ) (hα : 0 < α) (hβ : 0 < β)
    (hpk0 : 0 ≤ pk) (hpk1 : pk ≤ 1) :
    Tendsto (fun T : ℕ => specTime T α β pk / seqTime T β) atTop
      (𝓝 (1 - 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, Proposition 1 (p. 4), the T→∞T\to\inftyT→∞ limit; Appendix A (p. 14)
Read-back

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

Read-back of prop1_limit.

Fix three real numbers α\alphaα, β\betaβ and ppp (the third is called pk in the code; it is an arbitrary real parameter, not tied to any of the bundle's other definitions such as 1−(1−p)k1-(1-p)^k1−(1−p)k). The hypotheses are exactly four: α>0\alpha > 0α>0, β>0\beta > 0β>0, 0≤p0 \le p0≤p, and p≤1p \le 1p≤1. Nothing else is assumed — in particular there is no assumed relation between α\alphaα and β\betaβ (neither β<α\beta < \alphaβ<α nor α<β\alpha < \betaα<β), ppp is allowed to equal 000 or 111, and all four hypotheses are simultaneously satisfiable (e.g. α=β=1\alpha = \beta = 1α=β=1, p=1/2p = 1/2p=1/2), so the statement is not vacuous.

Two quantities are built from the imported bundle. First, the real-valued sequence SnS_nSn​ (n∈Nn \in \mathbb{N}n∈N), defined by the two-step recursion

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

This recursive definition is what the statement uses; the separate closed-form expression p1+pn+p2(1+p)2(1−(−p)n)\tfrac{p}{1+p}n + \tfrac{p^2}{(1+p)^2}\bigl(1-(-p)^n\bigr)1+pp​n+(1+p)2p2​(1−(−p)n) that also appears in the bundle is a different definition and is not referenced here, so no identity between the two is asserted or used.

Second, for each natural number TTT, two real numbers

seq(T)  =  Tβ,spec(T)  =  Tβ  −  ST−1⋅αβ (α+β),\mathrm{seq}(T) \;=\; \frac{T}{\beta}, \qquad\qquad \mathrm{spec}(T) \;=\; \frac{T}{\beta} \;-\; S_{T-1}\cdot\frac{\alpha}{\beta\,(\alpha+\beta)},seq(T)=βT​,spec(T)=βT​−ST−1​⋅β(α+β)α​,

where TTT is the natural number TTT viewed as a real number, and the index T−1T-1T−1 is truncated natural-number subtraction: for T=0T = 0T=0 it is 000 (not −1-1−1), and for T≥1T \ge 1T≥1 it is the ordinary T−1T-1T−1. These are simply the two displayed formulas; the statement asserts nothing about their interpretation as runtimes, expectations, or anything probabilistic.

The assertion is a single convergence claim: the sequence of real numbers indexed by the natural numbers

T  ⟼  spec(T)seq(T)  =  Tβ−ST−1⋅αβ(α+β)TβT \;\longmapsto\; \frac{\mathrm{spec}(T)}{\mathrm{seq}(T)} \;=\; \frac{\dfrac{T}{\beta} - S_{T-1}\cdot\dfrac{\alpha}{\beta(\alpha+\beta)}}{\dfrac{T}{\beta}}T⟼seq(T)spec(T)​=βT​βT​−ST−1​⋅β(α+β)α​​

tends, as T→∞T \to \inftyT→∞ through the natural numbers, to the real number

1  −  p1+p⋅αα+β,1 \;-\; \frac{p}{1+p}\cdot\frac{\alpha}{\alpha+\beta},1−1+pp​⋅α+βα​,

convergence being with respect to the usual topology on R\mathbb{R}R (the neighbourhood filter of that point) and the limit being taken along the "eventually large TTT" filter on N\mathbb{N}N. The grouping of the limit value is as displayed: the quotient p/(1+p)p/(1+p)p/(1+p) is multiplied by α/(α+β)\alpha/(\alpha+\beta)α/(α+β), and that product is subtracted from 111. Under the hypotheses every denominator occurring in the limit value is nonzero (1+p≥11 + p \ge 11+p≥1 and α+β>0\alpha + \beta > 0α+β>0), and β≠0\beta \neq 0β=0 inside the sequence.

Degenerate and edge cases the quantifiers silently include:

  • T=0T = 0T=0. The term of the sequence at T=0T=0T=0 is spec(0)/seq(0)=0/0\mathrm{spec}(0)/\mathrm{seq}(0) = 0/0spec(0)/seq(0)=0/0, which is 000 by the total-function convention for real division; likewise S0−1=S0=0S_{0-1} = S_0 = 0S0−1​=S0​=0. Since the limit is along the at-top filter, this term (and any finite number of initial terms) is irrelevant to the truth of the claim.
  • p=0p = 0p=0. Then Sn=0S_n = 0Sn​=0 for every nnn, the sequence is identically 111 for T≥1T \ge 1T≥1, and the asserted limit is 1−0=11 - 0 = 11−0=1.
  • p=1p = 1p=1. Permitted; the recursion becomes Sn+2=1+SnS_{n+2} = 1 + S_nSn+2​=1+Sn​ and the asserted limit is 1−12⋅αα+β1 - \tfrac12\cdot\tfrac{\alpha}{\alpha+\beta}1−21​⋅α+βα​.
  • For T≥1T \ge 1T≥1 the displayed ratio is algebraically equal to 1−ST−1T⋅αα+β1 - \dfrac{S_{T-1}}{T}\cdot\dfrac{\alpha}{\alpha+\beta}1−TST−1​​⋅α+βα​, so the claim concerns the limiting behaviour of ST−1/TS_{T-1}/TST−1​/T; the statement itself, however, is phrased as the limit of the ratio of the two defined quantities.

What is not claimed: no rate of convergence, no monotonicity, no error bound, no statement for a fixed finite TTT, and nothing about the other definitions in the bundle (1−(1−p)k1-(1-p)^k1−(1−p)k, the closed form for SnS_nSn​, the token-cost proxies, the depth-focused quantities, or the confidence-aware objective), none of which appear in this declaration. The declaration is stated with its proof left as an admitted gap.

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

  • Endorsed by naimengye · Sep 12, 2026

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

  • Endorsed by mikedeng1 · Oct 21, 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