Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Diminishing marginal returns of speculative breadth

Proved
SpecActions.dqhit_antitone

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

machine-learningprobabilitytheoretical-computer-science

At a speculation window let p(1)≥p(2)≥⋯p^{(1)}\ge p^{(2)}\ge\cdotsp(1)≥p(2)≥⋯ be the realized per-branch confidences, and let

q(m)=1−∏j<m(1−p(j))q(m)=1-\prod_{j<m}\bigl(1-p^{(j)}\bigr)q(m)=1−j<m∏​(1−p(j))

be the probability of obtaining a cached action when the top mmm branches are launched. The marginal gain from adding one more branch,

δq(m)=q(m+1)−q(m)=(∏j<m(1−p(j)))p(m),\delta q(m)=q(m+1)-q(m)=\Bigl(\prod_{j<m}(1-p^{(j)})\Bigr)p^{(m)},δq(m)=q(m+1)−q(m)=(j<m∏​(1−p(j)))p(m),

is non-increasing in mmm whenever the confidences lie in [0,1][0,1][0,1] and are sorted in descending order. Both factors are non-increasing in mmm, which is what makes the optimal breadth a threshold rule.

Preamble
import Definitions.Def_SpecActions_model
Formal statement
import Definitions.Def_SpecActions_model

namespace SpecActions
theorem dqhit_antitone (pv : ℕ → ℝ) (hpv0 : ∀ j, 0 ≤ pv j) (hpv1 : ∀ j, pv j ≤ 1)
    (hsorted : ∀ i j, i ≤ j → pv j ≤ pv i) (m : ℕ) :
    dqhit pv (m + 1) ≤ dqhit pv 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, Corollary 5 proof, Appendix C.3 (pp. 22–23): "δq(m;p)\delta q(m;p)δq(m;p) is nonincreasing in mmm (diminishing returns)"
Read-back

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

Read-back of SpecActions.dqhit_antitone.

Fix an arbitrary sequence of real numbers p∙=(p0,p1,p2,… )p_\bullet = (p_0, p_1, p_2, \dots)p∙​=(p0​,p1​,p2​,…), indexed by the natural numbers (in the code, pv : ℕ → ℝ; nothing forces these values to be probabilities beyond the hypotheses listed next). Three hypotheses are assumed about this sequence, each quantified over all natural-number indices:

  • Nonnegativity: 0≤pj0 \le p_j0≤pj​ for every j∈Nj \in \mathbb{N}j∈N.
  • Upper bound: pj≤1p_j \le 1pj​≤1 for every j∈Nj \in \mathbb{N}j∈N.
  • Descending order: for all i,j∈Ni, j \in \mathbb{N}i,j∈N with i≤ji \le ji≤j, one has pj≤pip_j \le p_ipj​≤pi​; i.e. the whole sequence is non-increasing (weakly), not merely non-increasing on some finite initial segment.

Fix in addition an arbitrary natural number mmm (no positivity or upper-bound restriction on mmm; m=0m = 0m=0 is included).

The quantity under discussion is the bundle's definition

δq(m)  :=  (∏j=0m−1(1−pj))⋅pm,\delta q(m) \;:=\; \Big(\textstyle\prod_{j=0}^{m-1} (1 - p_j)\Big)\cdot p_m,δq(m):=(∏j=0m−1​(1−pj​))⋅pm​,

where the product ranges over the mmm indices j=0,1,…,m−1j = 0, 1, \dots, m-1j=0,1,…,m−1 (in particular it is the empty product, equal to 111, when m=0m = 0m=0). This is the definition dqhit pv m expanded inline; the statement makes no reference to qhit, to any probabilistic interpretation, or to any optimization objective — it is a bare inequality between two real numbers built from the sequence p∙p_\bulletp∙​.

The assertion is the single non-strict inequality

(∏j=0m(1−pj))⋅pm+1    ≤    (∏j=0m−1(1−pj))⋅pm,\Big(\textstyle\prod_{j=0}^{m} (1 - p_j)\Big)\cdot p_{m+1} \;\;\le\;\; \Big(\textstyle\prod_{j=0}^{m-1} (1 - p_j)\Big)\cdot p_m,(∏j=0m​(1−pj​))⋅pm+1​≤(∏j=0m−1​(1−pj​))⋅pm​,

that is, δq(m+1)≤δq(m)\delta q(m+1) \le \delta q(m)δq(m+1)≤δq(m), for the fixed mmm above — and, since mmm is universally quantified, for every m∈Nm \in \mathbb{N}m∈N. Note that this is the one-step comparison only; no claim is made about monotonicity of any other quantity, about limits, about strictness anywhere, or about the sequence δq\delta qδq being nonnegative.

Degenerate cases silently covered: when m=0m = 0m=0 the claim reads (1−p0) p1≤p0(1 - p_0)\, p_1 \le p_0(1−p0​)p1​≤p0​. If some pj=1p_j = 1pj​=1 for j≤mj \le mj≤m, both sides may collapse to 000 and the inequality holds as an equality; if pm=pm+1=0p_m = p_{m+1} = 0pm​=pm+1​=0 both sides are 000 likewise. The hypotheses are jointly satisfiable — for instance by the constant sequence pj=0p_j = 0pj​=0, or by any non-increasing sequence with values in [0,1][0,1][0,1] — so the statement is not vacuous. Nothing in the hypotheses forces p∙p_\bulletp∙​ to be summable, eventually zero, or strictly decreasing.

The declaration is stated with its proof left as a placeholder (sorry), so no proof content is asserted.

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