Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3 / Corollary 5 — optimality of the greedy threshold breadth

Proved
SpecActions.greedy_threshold_optimal

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

machine-learningprobabilitytheoretical-computer-science

Fix a continuation value Δ>0\Delta>0Δ>0 and a marginal cost c>0c>0c>0, and consider the per-window objective

f(m)=q(m) Δ−c m,m∈{0,…,k},f(m)=q(m)\,\Delta-c\,m,\qquad m\in\{0,\dots,k\},f(m)=q(m)Δ−cm,m∈{0,…,k},

with qqq as above and confidences sorted in descending order. If mmm is an index at which the greedy stopping rule fires — that is, c≤Δ δq(j)c\le\Delta\,\delta q(j)c≤Δδq(j) for every j<mj<mj<m and Δ δq(j)≤c\Delta\,\delta q(j)\le cΔδq(j)≤c for every j≥mj\ge mj≥m — then mmm maximizes fff over {0,…,k}\{0,\dots,k\}{0,…,k}.

This is the structural content of the confidence-aware selection theorem: the dynamic program collapses to a one-dimensional trade-off, so at runtime the system sorts confidences and adds branches greedily while the incremental hit probability scaled by Δ\DeltaΔ exceeds ccc, in O(k)O(k)O(k) per step.

Preamble
import Definitions.Def_SpecActions_model
Formal statement
import Definitions.Def_SpecActions_model

namespace SpecActions
theorem greedy_threshold_optimal (pv : ℕ → ℝ) (Δ c : ℝ) (k : ℕ)
    (hΔ : 0 < Δ) (hc : 0 < c)
    (hpv0 : ∀ j, 0 ≤ pv j) (hpv1 : ∀ j, pv j ≤ 1)
    (hsorted : ∀ i j, i ≤ j → pv j ≤ pv i)
    (m : ℕ) (hm : m ≤ k)
    (hbelow : ∀ j < m, c ≤ Δ * dqhit pv j)
    (habove : ∀ j, m ≤ j → Δ * dqhit pv j ≤ c) :
    ∀ n ≤ k, specObjective pv Δ c n ≤ specObjective pv Δ c m := 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 3 (p. 10) and Corollary 5 with proof, Appendix C.3 (pp. 21–23)
Read-back

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

Read-back — SpecActions.greedy_threshold_optimal.

The statement fixes an infinite sequence of real numbers p:N→Rp : \mathbb{N} \to \mathbb{R}p:N→R, written p0,p1,p2,…p_0, p_1, p_2, \dotsp0​,p1​,p2​,… (the argument pv), two real parameters Δ\DeltaΔ and ccc, and a natural number kkk. Three quantities from the imported bundle appear in it, and they mean literally the following, for a natural number mmm:

q(m)  =  1−∏j=0m−1(1−pj),δq(m)  =  (∏j=0m−1(1−pj)) pm,F(m)  =  Δ q(m)  −  c m,q(m) \;=\; 1 - \prod_{j=0}^{m-1}\bigl(1 - p_j\bigr), \qquad \delta q(m) \;=\; \Bigl(\prod_{j=0}^{m-1}\bigl(1 - p_j\bigr)\Bigr)\, p_m, \qquad F(m) \;=\; \Delta\, q(m) \;-\; c\,m ,q(m)=1−j=0∏m−1​(1−pj​),δq(m)=(j=0∏m−1​(1−pj​))pm​,F(m)=Δq(m)−cm,

so that, written out fully, the objective being compared is

F(m)  =  Δ(1−∏j=0m−1(1−pj))  −  c m,F(m) \;=\; \Delta\Bigl(1 - \prod_{j=0}^{m-1}(1-p_j)\Bigr) \;-\; c\,m ,F(m)=Δ(1−j=0∏m−1​(1−pj​))−cm,

where the index mmm of the second term is the natural number mmm regarded as a real number. The products are over the indices j=0,1,…,m−1j = 0, 1, \dots, m-1j=0,1,…,m−1; for m=0m = 0m=0 the product is empty and equals 111, hence q(0)=0q(0) = 0q(0)=0, F(0)=0F(0) = 0F(0)=0, and δq(0)=p0\delta q(0) = p_0δq(0)=p0​.

Hypotheses assumed. (i) 0<Δ0 < \Delta0<Δ; (ii) 0<c0 < c0<c; (iii) 0≤pj0 \le p_j0≤pj​ for every natural number jjj; (iv) pj≤1p_j \le 1pj​≤1 for every natural number jjj; (v) the sequence is non-increasing in the weak sense that for all natural i,ji, ji,j with i≤ji \le ji≤j one has pj≤pip_j \le p_ipj​≤pi​; (vi) a natural number mmm is given together with m≤km \le km≤k; (vii) (below-threshold) for every natural jjj with j<mj < mj<m,

c  ≤  Δ⋅δq(j)  =  Δ(∏i<j(1−pi))pj;c \;\le\; \Delta \cdot \delta q(j) \;=\; \Delta\Bigl(\prod_{i<j}(1-p_i)\Bigr) p_j ;c≤Δ⋅δq(j)=Δ(i<j∏​(1−pi​))pj​;

(viii) (above-threshold) for every natural jjj with m≤jm \le jm≤j — this includes j=mj = mj=m itself and all indices beyond kkk, the quantification being over all of N\mathbb{N}N —

Δ⋅δq(j)  =  Δ(∏i<j(1−pi))pj  ≤  c.\Delta \cdot \delta q(j) \;=\; \Delta\Bigl(\prod_{i<j}(1-p_i)\Bigr) p_j \;\le\; c .Δ⋅δq(j)=Δ(i<j∏​(1−pi​))pj​≤c.

Both threshold inequalities are non-strict, and they point in opposite directions on the two index ranges, which are disjoint (j<mj < mj<m versus j≥mj \ge mj≥m), so no index is constrained by both.

Conclusion asserted. For every natural number nnn with n≤kn \le kn≤k,

F(n)  ≤  F(m),i.e.Δ(1−∏j<n(1−pj))−c n    ≤    Δ(1−∏j<m(1−pj))−c m.F(n) \;\le\; F(m), \qquad\text{i.e.}\qquad \Delta\Bigl(1 - \prod_{j<n}(1-p_j)\Bigr) - c\,n \;\;\le\;\; \Delta\Bigl(1 - \prod_{j<m}(1-p_j)\Bigr) - c\,m .F(n)≤F(m),i.e.Δ(1−j<n∏​(1−pj​))−cn≤Δ(1−j<m∏​(1−pj​))−cm.

That is: among the indices 0,1,…,k0, 1, \dots, k0,1,…,k, the given index mmm attains a value of FFF that is at least as large as that of any other index in that range.

Scope and degenerate cases. The comparison is made only over n≤kn \le kn≤k; nothing is claimed about F(n)F(n)F(n) for n>kn > kn>k. The inequality is non-strict, so no uniqueness of the maximizing index is claimed, and mmm is not asserted to be the least or the greatest such index — it is supplied as a hypothesis-satisfying input, and no claim is made that an index satisfying (vi)–(viii) exists. If k=0k = 0k=0 then m=0m = 0m=0 is forced and the conclusion reduces to F(0)≤F(0)F(0) \le F(0)F(0)≤F(0). If m=0m = 0m=0, hypothesis (vii) is vacuous and (viii) constrains every index j∈Nj \in \mathbb{N}j∈N; the conclusion then says F(n)≤0F(n) \le 0F(n)≤0 for all n≤kn \le kn≤k. Hypotheses (iii), (iv), (v) and (viii) constrain the entire infinite sequence, not merely its first kkk entries, even though the conclusion only involves indices up to kkk. Because 0≤pj≤10 \le p_j \le 10≤pj​≤1, each factor 1−pj1 - p_j1−pj​ lies in [0,1][0,1][0,1]; if some pj=1p_j = 1pj​=1 then every product with an index range reaching past jjj vanishes, so δq(i)=0\delta q(i) = 0δq(i)=0 and q(i)=q(j+1)q(i) = q(j+1)q(i)=q(j+1) for all i>ji > ji>j. The hypothesis set is jointly satisfiable — for instance pj=0p_j = 0pj​=0 for all jjj with m=0m = 0m=0 and any kkk, any Δ,c>0\Delta, c > 0Δ,c>0 — so the statement is not vacuous. The identity relating δq\delta qδq to increments of qqq is not part of what is asserted; δq\delta qδq enters only through hypotheses (vii) and (viii), and qqq only through the objective FFF.

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