Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1 (corrected), p. 7 — under Assumption 1 and rich prompts, α*(T) = (1/n)Σ 1{τ_i ≤ t_T} and T*(α) = (1/n)Σ τ_i 1{τ_i ≤ q_α}

Proved
TokenComplexity.Tradeoff.theorem_1

by mikedeng1 · Oct 21, 2026 · Mathlib 0df444a (Lean v4.33.1)

accuracy-length-tradeoffchain-of-thoughtgreedyknapsackp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1token-complexity

Consider n≥1n \ge 1n≥1 questions answered by one LLM under a family of prompts, with accuracy Acc(P)\mathrm{Acc}(P)Acc(P), average token length tˉ(P)\bar t(P)tˉ(P), and the optima

α∗(T)=max⁡P{Acc(P):tˉ(P)≤T},T∗(α)=min⁡P{tˉ(P):Acc(P)≥α}.\alpha^*(T) = \max_P \{\mathrm{Acc}(P) : \bar t(P) \le T\}, \qquad T^*(\alpha) = \min_P \{\bar t(P) : \mathrm{Acc}(P) \ge \alpha\}.α∗(T)=Pmax​{Acc(P):tˉ(P)≤T},T∗(α)=Pmin​{tˉ(P):Acc(P)≥α}.

Suppose

  1. Assumption 1 holds with token complexities τi∈N∪{∞}\tau_i \in \mathbb N\cup\{\infty\}τi​∈N∪{∞}: question iii is answered correctly under PPP if and only if its chain of thought has at least τi\tau_iτi​ tokens;
  2. for every token-count vector (ti)i=1n∈Nn(t_i)_{i=1}^n \in \mathbb N^n(ti​)i=1n​∈Nn some prompt PPP produces exactly these token lengths;
  3. the finite token complexities are pairwise distinct.

Let Fn(t)=1n∑i1{τi≤t}F_n(t) = \frac1n\sum_i \mathbf 1\{\tau_i \le t\}Fn​(t)=n1​∑i​1{τi​≤t}, En(t)=1n∑iτi1{τi≤t}E_n(t) = \frac1n\sum_i \tau_i\mathbf 1\{\tau_i \le t\}En​(t)=n1​∑i​τi​1{τi​≤t} and A∗=1n∑i1{τi<∞}A^* = \frac1n\sum_i \mathbf 1\{\tau_i < \infty\}A∗=n1​∑i​1{τi​<∞}. Let tTt_TtT​ be the largest finite τj\tau_jτj​ with En(τj)≤TE_n(\tau_j) \le TEn​(τj​)≤T, and qαq_\alphaqα​ the smallest finite τj\tau_jτj​ with Fn(τj)≥αF_n(\tau_j) \ge \alphaFn​(τj​)≥α (the α-quantile of the empirical distribution). Then for every T≥0T \ge 0T≥0 and every 0<α≤A∗0 < \alpha \le A^*0<α≤A∗ the optima are attained and

α∗(T)=1n∑i=1n1{τi≤tT},T∗(α)=1n∑i=1nτi 1{τi≤qα},\alpha^*(T) = \frac1n \sum_{i=1}^n \mathbf 1\{\tau_i \le t_T\}, \qquad T^*(\alpha) = \frac1n \sum_{i=1}^n \tau_i\,\mathbf 1\{\tau_i \le q_\alpha\},α∗(T)=n1​i=1∑n​1{τi​≤tT​},T∗(α)=n1​i=1∑n​τi​1{τi​≤qα​},

where the sums run over finite τi\tau_iτi​ and the first sum is 000 when no finite τj\tau_jτj​ has En(τj)≤TE_n(\tau_j) \le TEn​(τj​)≤T.

The theorem gives the exact accuracy–length frontier attainable by any prompting strategy under the token complexity hypothesis: the optimum solves the questions of smallest token complexity first. The paper uses it to compute the lower bound T∗(A∗)T^*(A^*)T∗(A∗) on lossless chain-of-thought compression.

Formalization Note The theorem is posed in corrected form. As printed, tT≡inf⁡{t∈R:En(t)=t}t_T \equiv \inf\{t \in \mathbb R : E_n(t) = t\}tT​≡inf{t∈R:En​(t)=t} does not involve TTT and "tT=∞t_T = \inftytT​=∞ if t>τˉt > \bar\taut>τˉ" uses ttt for TTT; even the reading tT=sup⁡{t:En(t)≤T}t_T = \sup\{t : E_n(t) \le T\}tT​=sup{t:En​(t)≤T} fails (n=1n = 1n=1, τ=(1)\tau = (1)τ=(1), T=0T = 0T=0 gives 111 instead of α∗(0)=0\alpha^*(0) = 0α∗(0)=0). The printed qα=sup⁡{t:Fn(t)≤α}q_\alpha = \sup\{t : F_n(t) \le \alpha\}qα​=sup{t:Fn​(t)≤α} overshoots (τ=(1,2)\tau = (1,2)τ=(1,2), α=1/2\alpha = 1/2α=1/2 gives 3/23/23/2 instead of 1/21/21/2). The corrected tTt_TtT​ follows the proof's description (p. 14), and qαq_\alphaqα​ the text's ("the α-quantile"). Added hypotheses: n≥1n \ge 1n≥1; T≥0T \ge 0T≥0 (no prompt is feasible otherwise); 0<α≤A∗0 < \alpha \le A^*0<α≤A∗ (above A∗A^*A∗ no prompt is feasible; at α≤0\alpha \le 0α≤0 the quantile would pick the smallest τ\tauτ instead of giving 000); pairwise distinct finite token complexities, which the proof uses ("τ(1)<⋯<τ(n)\tau_{(1)} < \dots < \tau_{(n)}τ(1)​<⋯<τ(n)​") and without which the closed form fails (τ=(1,1)\tau = (1,1)τ=(1,1), T=1/2T = 1/2T=1/2: α∗=1/2\alpha^* = 1/2α∗=1/2 but the closed form gives 000). The LLM is fixed and its superscript π\piπ dropped.

Preamble
import Mathlib
import Definitions.Def_TokenComplexity_Tradeoff_Model
Formal statement
namespace TokenComplexity.Tradeoff

/-- Theorem 1 (corrected), p. 7: under Assumption 1, rich prompts and pairwise distinct finite token
complexities, `α*(T) = (1/n) ∑ᵢ 1{τᵢ ≤ t_T}` for every budget `T ≥ 0` and
`T*(α) = (1/n) ∑ᵢ τᵢ 1{τᵢ ≤ q_α}` for every `0 < α ≤ A*`, with `t_T` the largest finite `τ_j` with
`E_n(τ_j) ≤ T` and `q_α` the smallest finite `τ_j` with `F_n(τ_j) ≥ α`. -/
theorem theorem_1 {n : ℕ} (hn : 0 < n) {Prompt : Type} (B : Benchmark n Prompt)
    (τ : Fin n → ℕ∞) (hA1 : TokenComplexityHyp B τ) (hRich : Rich B)
    (hdist : ∀ i j, τ i ≠ ⊤ → τ i = τ j → i = j) :
    (∀ T : ℝ, 0 ≤ T → IsOptAccuracy B T (alphaClosed τ T)) ∧
    (∀ α : ℝ, 0 < α → α ≤ Astar τ → IsMinAvgLen B α (TClosed τ α)) := by sorry

end TokenComplexity.Tradeoff
Source
Lee, Che, Peng, How Well do LLMs Compress Their Own Chain-of-Thought? A Token Complexity Approach, arXiv:2503.01141v2, p. 7, Theorem 1 (eqs. (5)–(6)); proof in Appendix D, p. 14
Human review
  • Endorsed by Shuze Chen · Oct 21, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 21, 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