Prove2Me
Navigate
DiscoverFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

The 50% latency-reduction ceiling for breadth speculation

Proved
SpecActions.latency_reduction_le_half

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

machine-learningprobabilitytheoretical-computer-science

For all α,β>0\alpha,\beta>0α,β>0 and pk∈[0,1]p_k\in[0,1]pk​∈[0,1] the asymptotic latency reduction achieved by single-step breadth speculation is strictly less than one half:

pk1+pk⋅αα+β<12.\frac{p_k}{1+p_k}\cdot\frac{\alpha}{\alpha+\beta}<\frac12 .1+pk​pk​​⋅α+βα​<21​.

This is the negative result motivating the depth-focused regime: the paper's "upper bound of 50%, occurring when p=1p=1p=1 and α=∞\alpha=\inftyα=∞" describes a supremum that is approached but never attained, since pk1+pk≤12\frac{p_k}{1+p_k}\le\frac121+pk​pk​​≤21​ with equality only at pk=1p_k=1pk​=1, while αα+β<1\frac{\alpha}{\alpha+\beta}<1α+βα​<1 for every finite α\alphaα and β>0\beta>0β>0.

Preamble
import Definitions.Def_SpecActions_model
Formal statement
import Definitions.Def_SpecActions_model

namespace SpecActions
theorem latency_reduction_le_half (α β pk : ℝ) (hα : 0 < α) (hβ : 0 < β)
    (hpk0 : 0 ≤ pk) (hpk1 : pk ≤ 1) :
    pk / (1 + pk) * (α / (α + β)) < 1 / 2 := 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 discussion (p. 5): "the end-to-end latency reduction has an upper bound of 50%"
Read-back

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

Declaration latency_reduction_le_half (namespace SpecActions).

The statement is about three real numbers, all of them explicit arguments: α\alphaα, β\betaβ, and a third real number written pkp_kpk​ (the identifier pk, a single real variable, not a function of an index kkk). Four hypotheses are assumed:

  • α>0\alpha > 0α>0;
  • β>0\beta > 0β>0;
  • pk≥0p_k \ge 0pk​≥0;
  • pk≤1p_k \le 1pk​≤1.

There are no other binders, no implicit arguments, no typeclass assumptions beyond the three variables being real numbers, and no quantification over any natural number, index, horizon, or sequence.

Under exactly those four hypotheses, the assertion is the strict inequality

pk1+pk⋅αα+β  <  12,\frac{p_k}{1 + p_k}\cdot\frac{\alpha}{\alpha + \beta} \;<\; \frac{1}{2},1+pk​pk​​⋅α+βα​<21​,

where all operations are the real-number ones and 12\tfrac1221​ is the real number one-half. The claim is <<<, not ≤\le≤, and it is a one-directional inequality (no equivalence, no matching lower bound, and no claim about when equality or near-equality occurs).

Concerning the degenerate cases the hypotheses permit: since pk≥0p_k \ge 0pk​≥0 we have 1+pk≥1>01 + p_k \ge 1 > 01+pk​≥1>0, and since α,β>0\alpha, \beta > 0α,β>0 we have α+β>0\alpha + \beta > 0α+β>0, so neither division is by zero and no total-division junk value arises. The endpoints of the allowed range for pkp_kpk​ are included: at pk=0p_k = 0pk​=0 the left-hand side is 000, and at pk=1p_k = 1pk​=1 it is α2(α+β)\dfrac{\alpha}{2(\alpha+\beta)}2(α+β)α​. Nothing relates α\alphaα and β\betaβ to each other — the statement covers α<β\alpha < \betaα<β, α=β\alpha = \betaα=β, and α>β\alpha > \betaα>β alike, and neither is bounded above. The hypotheses are jointly satisfiable (for instance α=β=1\alpha = \beta = 1α=β=1, pk=12p_k = \tfrac12pk​=21​), so the claim is not vacuous.

None of the definitions of the imported bundle occur in the statement: there is no reference to phit\text{phit}phit, to the hit-count recursion SnS_nSn​ or its closed form, to seqTime\text{seqTime}seqTime, specTime\text{specTime}specTime, seqCost\text{seqCost}seqCost, specCost\text{specCost}specCost, to any of the depth-focused quantities, or to q(m)q(m)q(m), δq(m)\delta q(m)δq(m), and the per-window objective. In particular the statement mentions no step horizon TTT, no latency, no cost, and no algorithm; it is a purely arithmetic inequality among three real parameters.

The declaration is stated with its proof omitted.

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