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_α}
ProvedTokenComplexity.Tradeoff.theorem_1Consider questions answered by one LLM under a family of prompts, with accuracy , average token length , and the optima
Suppose
- Assumption 1 holds with token complexities : question is answered correctly under if and only if its chain of thought has at least tokens;
- for every token-count vector some prompt produces exactly these token lengths;
- the finite token complexities are pairwise distinct.
Let , and . Let be the largest finite with , and the smallest finite with (the α-quantile of the empirical distribution). Then for every and every the optima are attained and
where the sums run over finite and the first sum is when no finite has .
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 on lossless chain-of-thought compression.
Formalization Note The theorem is posed in corrected form. As printed, does not involve and " if " uses for ; even the reading fails (, , gives instead of ). The printed overshoots (, gives instead of ). The corrected follows the proof's description (p. 14), and the text's ("the α-quantile"). Added hypotheses: ; (no prompt is feasible otherwise); (above no prompt is feasible; at the quantile would pick the smallest instead of giving ); pairwise distinct finite token complexities, which the proof uses ("") and without which the closed form fails (, : but the closed form gives ). The LLM is fixed and its superscript dropped.
import Mathlib import Definitions.Def_TokenComplexity_Tradeoff_Model
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.