Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 6 — depth-focused relative cost

Proved
SpecActions.thm6_depth_cost

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

machine-learningprobabilitytheoretical-computer-science

Under the depth-focused policy with deterministic latencies b<ab<ab<a and correctness probability ppp, the relative cost increase is exactly

E[Mspec−Mseq]E[Mseq]=T−1T⋅(1−p)(a⌊a/b⌋−b (1+⌊a/b⌋)⌊a/b⌋2)+p b⌊a/b⌋a\frac{\mathbb{E}[M_{\mathrm{spec}}-M_{\mathrm{seq}}]}{\mathbb{E}[M_{\mathrm{seq}}]}=\frac{T-1}{T}\cdot\frac{(1-p)\left(a\lfloor a/b\rfloor-b\,\frac{(1+\lfloor a/b\rfloor)\lfloor a/b\rfloor}{2}\right)+p\,b\lfloor a/b\rfloor}{a}E[Mseq​]E[Mspec​−Mseq​]​=TT−1​⋅a(1−p)(a⌊a/b⌋−b2(1+⌊a/b⌋)⌊a/b⌋​)+pb⌊a/b⌋​

for every T≥1T\ge 1T≥1. A step whose guess is correct spends a+⌊a/b⌋ba+\lfloor a/b\rfloor ba+⌊a/b⌋b; a step whose guess is wrong also pays for the branches spawned before the real response arrived, the series a+(a−b)+⋯+(a−⌊a/b⌋b)a+(a-b)+\cdots+(a-\lfloor a/b\rfloor b)a+(a−b)+⋯+(a−⌊a/b⌋b).

This is the exact identity. The paper immediately replaces it with the approximation T−1T((1−p)(a2b−12)+p)\frac{T-1}{T}\left((1-p)\left(\frac{a}{2b}-\frac12\right)+p\right)TT−1​((1−p)(2ba​−21​)+p), which agrees with the exact expression only when a/ba/ba/b is an integer; the milestone asserts the exact floor version, which is what the proof establishes.

Preamble
import Definitions.Def_SpecActions_model
Formal statement
import Definitions.Def_SpecActions_model

namespace SpecActions
theorem thm6_depth_cost (T : ℕ) (a b p : ℝ) (ha : 0 < a) (hb : 0 < b)
    (hba : b < a) (hp0 : 0 ≤ p) (hp1 : p ≤ 1) (hT : 1 ≤ T) :
    (depthSpecCost T a b p - depthSeqCost T a) / depthSeqCost T a
      = ((T : ℝ) - 1) / (T : ℝ) *
          ((1 - p) * (a * ⌊a / b⌋ - b * ((1 + ⌊a / b⌋) * ⌊a / b⌋ / 2))
            + p * (b * ⌊a / b⌋)) / a := 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 6, Appendix C.4 (pp. 23–24), exact cost expression before the ≈\approx≈ simplification
Read-back

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

Read-back — SpecActions.thm6_depth_cost

The declaration fixes one natural number TTT and three real numbers aaa, bbb, ppp, all universally quantified as explicit arguments, together with six hypotheses that are assumed to hold simultaneously:

  • 0<a0 < a0<a,
  • 0<b0 < b0<b,
  • b<ab < ab<a,
  • 0≤p0 \le p0≤p,
  • p≤1p \le 1p≤1,
  • 1≤T1 \le T1≤T (an inequality between natural numbers, so T≥1T \ge 1T≥1 and the case T=0T = 0T=0 is excluded).

All arithmetic in the conclusion happens in R\mathbb{R}R: TTT is cast from N\mathbb{N}N into R\mathbb{R}R, and every occurrence of T−1T - 1T−1 is real subtraction of the cast, not truncated natural subtraction.

Two quantities imported from the definition bundle occur in the statement. Writing K:=⌊a/b⌋K := \lfloor a/b \rfloorK:=⌊a/b⌋ for the integer floor of the real quotient a/ba/ba/b, cast back into R\mathbb{R}R (with 0<b<a0 < b < a0<b<a one has a/b>1a/b > 1a/b>1, hence K≥1K \ge 1K≥1), they are

Cseq(T,a)  =  a T,C_{\mathrm{seq}}(T, a) \;=\; a\,T,Cseq​(T,a)=aT, Cspec(T,a,b,p)  =  a  +  (T−1)[ p(a+K b)  +  (1−p)(a (K+1)  −  (1+K) K2 b)].C_{\mathrm{spec}}(T, a, b, p) \;=\; a \;+\; (T-1)\Big[\, p\big(a + K\,b\big) \;+\; (1-p)\Big(a\,(K+1) \;-\; \tfrac{(1+K)\,K}{2}\,b\Big)\Big].Cspec​(T,a,b,p)=a+(T−1)[p(a+Kb)+(1−p)(a(K+1)−2(1+K)K​b)].

Neither definition is given any meaning here beyond these formulas; in particular no probabilistic, temporal, or algorithmic interpretation of aaa, bbb, ppp, TTT, or of the two cost expressions is part of the claim.

The conclusion is the single equation

Cspec(T,a,b,p)−Cseq(T,a)Cseq(T,a)  =  T−1T⋅(1−p)(a K  −  b⋅(1+K) K2)  +  p (b K)a,\frac{C_{\mathrm{spec}}(T,a,b,p) - C_{\mathrm{seq}}(T,a)}{C_{\mathrm{seq}}(T,a)} \;=\; \frac{T-1}{T}\cdot\frac{(1-p)\Big(a\,K \;-\; b\cdot\tfrac{(1+K)\,K}{2}\Big) \;+\; p\,\big(b\,K\big)}{a},Cseq​(T,a)Cspec​(T,a,b,p)−Cseq​(T,a)​=TT−1​⋅a(1−p)(aK−b⋅2(1+K)K​)+p(bK)​,

i.e. the relative excess of CspecC_{\mathrm{spec}}Cspec​ over CseqC_{\mathrm{seq}}Cseq​, measured against CseqC_{\mathrm{seq}}Cseq​, equals the displayed expression. The grouping on the right-hand side is: the factor (T−1)/T(T-1)/T(T−1)/T is multiplied by the bracketed sum, and that whole product is then divided by aaa.

Points the quantifiers silently cover:

  • Division. The left-hand side divides by Cseq(T,a)=a TC_{\mathrm{seq}}(T,a) = a\,TCseq​(T,a)=aT; under the hypotheses a>0a > 0a>0 and T≥1T \ge 1T≥1 this is strictly positive, so no division-by-zero convention is invoked. Likewise T≠0T \ne 0T=0 and a≠0a \ne 0a=0 on the right.
  • T=1T = 1T=1. Then Cspec=aC_{\mathrm{spec}} = aCspec​=a and Cseq=aC_{\mathrm{seq}} = aCseq​=a, so the left side is 000, and the factor (T−1)/T(T-1)/T(T−1)/T makes the right side 000 as well; the equation is the statement 0=00 = 00=0 in this boundary case.
  • p=0p = 0p=0 and p=1p = 1p=1. Both endpoints are admitted; at p=1p = 1p=1 only the term p b Kp\,b\,KpbK survives on the right, at p=0p = 0p=0 only the (1−p)(1-p)(1−p) term.
  • Floor. KKK is an integer-valued quantity depending on aaa and bbb; the equation must hold for every real pair 0<b<a0 < b < a0<b<a, including those where a/ba/ba/b is an exact integer and those where it is not.
  • Non-vacuity. The hypothesis set is satisfiable — e.g. T=2T = 2T=2, a=2a = 2a=2, b=1b = 1b=1, p=1/2p = 1/2p=1/2 — so the statement is not vacuously true for want of admissible arguments.

Nothing beyond this pointwise algebraic identity is asserted: there is no existential claim, no inequality, no monotonicity or optimality statement, and no connection to the other definitions in the bundle (phit\mathrm{phit}phit, hits\mathrm{hits}hits, specTime\mathrm{specTime}specTime, specCost\mathrm{specCost}specCost, depthSpecTime\mathrm{depthSpecTime}depthSpecTime, qqq-hit, or the speculation objective). The declaration is stated with its proof omitted (sorry), so it records the claim only.

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