Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Expected time saved per hit: E[(B−A)+]=αβ(α+β)\mathbb{E}[(B-A)^+]=\frac{\alpha}{\beta(\alpha+\beta)}E[(B−A)+]=β(α+β)α​

Proved
SpecActions.expected_saving_per_hit

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

machine-learningprobabilitytheoretical-computer-science

Let A∼Exp(α)A\sim\mathrm{Exp}(\alpha)A∼Exp(α) be the speculator's latency and B∼Exp(β)B\sim\mathrm{Exp}(\beta)B∼Exp(β) the real API call's latency, independent. When a guess is correct the block of two consecutive steps finishes at C+min⁡{A,B}C+\min\{A,B\}C+min{A,B} instead of B+CB+CB+C, so the time saved is (B−A)+(B-A)^+(B−A)+. Its expectation is

E[(B−A)+]=∫0∞ ⁣ ⁣∫0b(b−a) αe−αa βe−βb da db=αβ(α+β)\mathbb{E}\bigl[(B-A)^+\bigr]=\int_0^\infty\!\!\int_0^b (b-a)\,\alpha e^{-\alpha a}\,\beta e^{-\beta b}\,da\,db=\frac{\alpha}{\beta(\alpha+\beta)}E[(B−A)+]=∫0∞​∫0b​(b−a)αe−αaβe−βbdadb=β(α+β)α​

for all α,β>0\alpha,\beta>0α,β>0. The statement is the iterated integral against the two exponential densities; since the asserted value is strictly positive, a proof must establish integrability rather than appeal to the convention that a non-integrable integral is zero.

Preamble
import Definitions.Def_SpecActions_model
Formal statement
import Definitions.Def_SpecActions_model
import Mathlib.Analysis.SpecialFunctions.Integrals.Basic
import Mathlib.MeasureTheory.Integral.IntervalIntegral.Basic

namespace SpecActions
theorem expected_saving_per_hit (α β : ℝ) (hα : 0 < α) (hβ : 0 < β) :
    ∫ b in Set.Ioi (0:ℝ),
        (∫ a in (0:ℝ)..b, (b - a) * (α * Real.exp (-α * a)))
          * (β * Real.exp (-β * b))
      = α / (β * (α + β)) := 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, Appendix A (p. 13), the computation of E[(B−A)+]=α/(β(α+β))\mathbb{E}[(B-A)^+]=\alpha/(\beta(\alpha+\beta))E[(B−A)+]=α/(β(α+β))
Read-back

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

Read-back — SpecActions.expected_saving_per_hit.

The declaration asserts a single equality between two real numbers, parametrized by two real numbers α\alphaα and β\betaβ that are supplied explicitly, together with two hypotheses, namely 0<α0 < \alpha0<α and 0<β0 < \beta0<β. No further assumption is made: in particular no ordering between α\alphaα and β\betaβ is imposed (they may be equal, and either may be the larger), and no integrability hypothesis is assumed. Under those two positivity hypotheses the claim is

∫(0,∞)(∫0b(b−a) (αe−αa) da)⋅(βe−βb) db  =  αβ (α+β).\int_{(0,\infty)} \left( \int_{0}^{b} (b - a)\,\bigl(\alpha e^{-\alpha a}\bigr)\, da \right)\cdot \bigl(\beta e^{-\beta b}\bigr)\, db \;=\; \frac{\alpha}{\beta\,(\alpha + \beta)} .∫(0,∞)​(∫0b​(b−a)(αe−αa)da)⋅(βe−βb)db=β(α+β)α​.

Reading the two integrals precisely: the outer one is the Lebesgue (Bochner) integral of a real-valued function of the variable bbb over the open half-line (0,∞)(0,\infty)(0,∞) — the point 000 is excluded, and the ambient measure is Lebesgue measure on R\mathbb{R}R; the integrand at a given bbb is the product of two factors, the first being the inner integral evaluated at that same bbb, the second being βe−βb\beta e^{-\beta b}βe−βb. The inner one is an oriented interval integral in the variable aaa from the lower limit 000 to the upper limit bbb, i.e. ∫(0,b)⋅ da\int_{(0,b)} \cdot\, da∫(0,b)​⋅da when b≥0b \ge 0b≥0 and −∫(b,0)⋅ da-\int_{(b,0)} \cdot\, da−∫(b,0)​⋅da when b<0b < 0b<0; because the outer variable bbb ranges only over strictly positive reals, only the first case is ever reached inside this statement, so the inner integral is the ordinary integral of (b−a) αe−αa(b-a)\,\alpha e^{-\alpha a}(b−a)αe−αa over a∈(0,b)a \in (0,b)a∈(0,b), on which the factor b−ab - ab−a is non-negative. The exponents are −α⋅a-\alpha \cdot a−α⋅a and −β⋅b-\beta \cdot b−β⋅b respectively, and the multiplicative prefactors α\alphaα and β\betaβ sit inside the respective integrands.

Two conventions are silently in force and are not excluded by any hypothesis. First, both the interval integral and the outer set integral are defined to be 000 whenever the integrand fails to be integrable; the equality asserted is the equality of the resulting real numbers under whichever case actually obtains, since nothing in the statement requires either integrand to be integrable. Second, division on the reals is total, so the right-hand side would still denote a real number even if its denominator vanished; here the hypotheses 0<α0 < \alpha0<α and 0<β0 < \beta0<β force β>0\beta > 0β>0 and α+β>0\alpha + \beta > 0α+β>0, hence β(α+β)≠0\beta(\alpha+\beta) \neq 0β(α+β)=0, so no junk value of division is invoked and the right-hand side is the genuine quotient α/(β(α+β))\alpha / (\beta(\alpha+\beta))α/(β(α+β)).

The hypotheses are simultaneously satisfiable (for instance α=β=1\alpha = \beta = 1α=β=1), so the claim is not vacuous. The statement is purely an identity of real numbers about exponential-type integrands: it introduces no probability space, no random variables, no distributions, and no notion of expectation, latency, saving, or hit, and it uses none of the definitions from the accompanying bundle — the only notions appearing are the real exponential function, the interval integral, the Lebesgue integral over (0,∞)(0,\infty)(0,∞), and field operations on R\mathbb{R}R. Nothing is asserted for non-positive α\alphaα or β\betaβ.

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