OctoInformBeta

OpenAI preprint, September 2026 · §2. The induction and global scales

Proposition 2.3: Common overlap and explicit count multipliers for size nn and working rate δ\delta when n→∞n\to\infty and δ3log⁡n→∞\delta^3\log n\to\infty

Level pairs eventually reach every scheduled scale.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

The induction uses pairs of distinct binary words whose complete deletion traces admit finite simulations with a controlled likelihood score. Write qq for the requested deletion probability, with 0<q≤10<q\le1, so that each bit survives with probability 1−q1-q. For requested deletion probability qq, the working rate δ\delta and its scale parameter Λ\Lambda are the positive real numbers in (1); the construction theorems call this working rate qq. δ=min⁡{q,1/2},Λ=δ−3.\delta=\min\{q,1/2\},\qquad \Lambda=\delta^{-3}.(1)

A finite probability law PP on a finite set Ω\Omega is a nonnegative mass function of total mass one.✦ For a finite law PP on Ω\Omega, the expectation 𝔼P[u]\mathbb E_P[u] of a function u:Ω→ℝu:\Omega\to\mathbb R is the weighted sum in (2)✦, and the mixture PKPK of laws KaK_a on a finite set Ξ\Xi, indexed by a∈Ωa\in\Omega, is the law on Ξ\Xi given there.✦ For an element aa of a finite set, the point mass at aa is the probability law on that set that assigns mass one to aa and zero elsewhere.✦ The pushforward f#Pf_\#P of a finite law PP on Ω\Omega under a map f:Ω→Ξf:\Omega\to\Xi is the law on Ξ\Xi obtained by mixing the point masses at f(a)f(a) with weights P(a)P(a).✦ P(a)≥0,∑a∈ΩP(a)=1,𝔼P[u]=∑a∈ΩP(a)u(a),(PK)(b)=∑a∈ΩP(a)Ka(b),(f#P)(b)=∑a:f(a)=bP(a).\begin{aligned} &P(a)\ge0,\qquad \sum_{a\in\Omega}P(a)=1, \qquad \mathbb E_P[u]=\sum_{a\in\Omega}P(a)u(a),\\ &(PK)(b)=\sum_{a\in\Omega}P(a)K_a(b),\qquad (f_\#P)(b)=\sum_{a:f(a)=b}P(a). \end{aligned}(2) For laws P,QP,Q on a finite set Ω\Omega, their overlap overlap⁡(P,Q)\operatorname{overlap}(P,Q) and total variation distance TV⁡(P,Q)\operatorname{TV}(P,Q) are the real numbers defined in (3). overlap⁡(P,Q)=∑a∈Ωmin⁡{P(a),Q(a)}=1−TV⁡(P,Q),TV⁡(P,Q)=12∑a∈Ω|P(a)−Q(a)|.\operatorname{overlap}(P,Q)=\sum_{a\in\Omega}\min\{P(a),Q(a)\} =1-\operatorname{TV}(P,Q),\qquad \operatorname{TV}(P,Q)=\frac12\sum_{a\in\Omega}|P(a)-Q(a)|.(3)

A binary word ww of length ℓ\ell is a function assigning a bit to each zero-based position 0,…,ℓ−10,\ldots,\ell-1.✦ A deletion mask aa for a binary word of length ℓ\ell is a function assigning a retention indicator to each position 0,…,ℓ−10,\ldots,\ell-1.✦ The retained subsequence Ta(w)T_a(w) of a binary word ww under a deletion mask aa is the finite list of the bits of ww retained by aa, in their original order.✦ A binary trace is a finite bit list, including its surviving length.✦ For a nonnegative integer MM, the complete trace space 𝒯M\mathcal T_M is the set of binary traces of length at most MM✦, whose elements are called bounded traces of bound MM✦; the deletion mask probability pq(a)p_q(a) of a mask aa is the product in (4).✦ 𝒯M=⋃ℓ=0M{0,1}ℓ,pq(a)=∏j=0ℓ−1{1−q,a(j)=1,q,a(j)=0.\mathcal T_M=\bigcup_{\ell=0}^M\{0,1\}^{\ell},\qquad p_q(a)=\prod_{j=0}^{\ell-1} \begin{cases}1-q,&a(j)=1,\\q,&a(j)=0.\end{cases}(4) For q∈[0,1]q\in[0,1], the deletion mask law on masks of a fixed word length is the probability law with masses pq(a)p_q(a).✦ The complete trace law 𝒟qM(w)\mathcal D_q^M(w) of a binary word ww with |w|≤M|w|\le M is the probability law on 𝒯M\mathcal T_M obtained by pushing the deletion mask law forward under a↦Ta(w)a\mapsto T_a(w).✦ For a real function FF on finite binary traces, the complete trace expectation Lq(w;F)L_q(w;F) of a binary word ww is the expectation of FF under its complete trace law, equivalently the recursion in (5), where ⌀\varnothing is the empty trace and bwbw prepends bit bb to word ww.✦ Lq(⌀;F)=F(⌀),Lq(bw;F)=qLq(w;F)+(1−q)Lq(w;t↦F(bt)).L_q(\varnothing;F)=F(\varnothing),\qquad L_q(bw;F)=qL_q(w;F)+(1-q)L_q(w;t\mapsto F(bt)).(5) For binary words x,yx,y, the complete trace overlap 𝒪q(x,y)\mathcal O_q(x,y) is the overlap of their complete trace laws using the common bound M=max⁡{|x|,|y|}M=\max\{|x|,|y|\} in (6).✦ The repeated word wmw^m, for a binary word ww and a nonnegative integer mm, is the concatenation of mm copies of ww.✦ 𝒪q(x,y)=overlap⁡(𝒟qM(x),𝒟qM(y)).\mathcal O_q(x,y)=\operatorname{overlap} \bigl(\mathcal D_q^M(x),\mathcal D_q^M(y)\bigr).(6)

An EE-approximate trace simulation of a binary word ww at rate δ\delta is a finite law PP on Ω\Omega and a decoder h:Ω→⋃M𝒯Mh:\Omega\to\bigcup_M\mathcal T_M satisfying (7); denote this condition by 𝒜δ(P,h,w;E)\mathcal A_\delta(P,h,w;E).✦ |𝔼P[F∘h]−Lδ(w;F)|≤Efor every trace function F with 0≤F≤1.\left|\mathbb E_P[F\circ h]-L_\delta(w;F)\right|\le E \quad\text{for every trace function }F\text{ with }0\le F\le1.(7) For a finite law PP on Ω\Omega, a score s:Ω→ℝs:\Omega\to\mathbb R, and a nonnegative integer half-order kk, the squared even moment 𝔪P,k(s)\mathfrak m_{P,k}(s) is the nonnegative real number in (8), taking 1/0=01/0=0 when k=0k=0.✦ 𝔪P,k(s)=(𝔼P[|s|2k])1/k.\mathfrak m_{P,k}(s)= \left(\mathbb E_P[|s|^{2k}]\right)^{1/k}.(8)

Given a target length NN, error allowance Δ\Delta, score exponent dd, overlap lower bound ω\omega, count multiplier AA, level ii, and half-order kk, a concrete level pair in 𝒞δ(N,Δ,d,ω,A;i,k)\mathcal C_\delta(N,\Delta,d,\omega,A;i,k) consists of distinct words x,yx,y of common length ℓ\ell, finite laws P,QP,Q on a common finite set Ω\Omega, a decoder hh, an error E≥0E\ge0, a score ss, and an integer m≥0m\ge0, subject to (9).✦ N/2≤ℓ≤N,E/ℓ≤(i+1)Δ,𝒜δ(P,h,x;E),𝒜δ(Q,h,y;E),Q(a)=P(a)(1+s(a))(a∈Ω),𝔪P,k(s)≤N−d,ℓ≤m≤Aℓ,ω≤𝒪δ(xm,xm+1).\begin{aligned} &N/2\le\ell\le N,\qquad E/\ell\le(i+1)\Delta,\\ &\mathcal A_\delta(P,h,x;E),\qquad \mathcal A_\delta(Q,h,y;E),\\ &Q(a)=P(a)(1+s(a))\quad(a\in\Omega),\qquad \mathfrak m_{P,k}(s)\le N^{-d},\\ &\ell\le m\le A\ell,\qquad \omega\le\mathcal O_\delta(x^m,x^{m+1}). \end{aligned}(9)

The Schedule and Level Pairs

For an integer B≥2B\ge2, a slack ζ∈(0,1)\zeta\in(0,1), and H>0H>0, the induction depth D(B,ζ,H)D(B,\zeta,H) is the truncated floor in (10).✦ Here ⌊u⌋+=max⁡{0,⌊u⌋}\lfloor u\rfloor_+=\max\{0,\lfloor u\rfloor\}. D(B,ζ,H)=⌊(1−ζ)log⁡HBlog⁡2⌋+.D(B,\zeta,H)= \left\lfloor\frac{(1-\zeta)\log H}{B\log2}\right\rfloor_+.(10) For a zero-based block index ii referring to block i+1i+1 and a block dimension bb, the warmup block count WBW_B, source block dimensions bi+1b_{i+1}, block gain g(b)g(b), and total score exponents did_i are defined in (11). WB=5⋅2B,bi+1={2,i<WB,B,i≥WB,g(b)=b−14−120,di=115+∑j=0i−1g(bj+1).\begin{aligned} W_B&=5\cdot2^B,& b_{i+1}&=\begin{cases}2,&i<W_B,\\B,&i\ge W_B,\end{cases}\\ g(b)&=\frac{b-1}{4}-\frac1{20},& d_i&=\frac{11}{5}+\sum_{j=0}^{i-1}g(b_{j+1}). \end{aligned}(11) At depth DD and size n>1n>1, with zero-based scale index jj, (12) defines the scale slack ε\varepsilon, scale exponent ab(j)a_b(j), exponent product pip_i, and backwards target scale NiN_i. An empty product is one. ε=124B+100(D+1),ab(j)=(1+ε)2j2b−ε,pi=∏j=iD−1abj+1(0),Ni=npi.\begin{aligned} \varepsilon&=\frac1{2^{4B+100}(D+1)},& a_b(j)&=(1+\varepsilon)\frac{2^j}{2^b}-\varepsilon,\\ p_i&=\prod_{j=i}^{D-1}a_{b_{j+1}}(0),&N_i&=n^{p_i}. \end{aligned}(12) The error allowance Δ\Delta and half moment orders kik_i are defined in (13). The even score exponent is ri=2kir_i=2k_i, and ⌈u⌉+=max⁡{0,⌈u⌉}\lceil u\rceil_+=\max\{0,\lceil u\rceil\}. Δ=n−100(dD+B+1),ki=⌈108210B(dD+B+1)log⁡nlog⁡Ni⌉+.\Delta=n^{-100(d_D+B+1)},\qquad k_i=\left\lceil 10^8 2^{10B}(d_D+B+1)\frac{\log n}{\log N_i} \right\rceil_+.(13) The rank Schur constant KSK_S and primitive period constant KPK_P determine the initial overlap lower bound ω(δ)\omega(\delta) and source overlap constant C(δ)C(\delta) in (14). KS=8847362e1−e−1/1024,KP=36KS2,ω(δ)=exp⁡(−(32+3KP)/δ3)1536,C(δ)=240δω(δ).\begin{aligned} K_S&=884736\,\frac{2e}{1-e^{-1/1024}},&K_P&=36K_S^2,\\ \omega(\delta)&=\frac{\exp(-(32+3K_P)/\delta^3)}{1536},& C(\delta)&=\frac{2^{40}}{\delta\omega(\delta)}. \end{aligned}(14) For the schedule determined by B,D,n,δB,D,n,\delta, a source level pair in 𝒮i(B,D,n,δ)\mathcal S_i(B,D,n,\delta) at level ii is a concrete level pair with the scheduled parameters in (15).✦ 𝒮i(B,D,n,δ)=𝒞δ(Ni,Δ,di,ω(δ),C(δ)2Bi+2;i,ki).\mathcal S_i(B,D,n,\delta)= \mathcal C_\delta\bigl(N_i,\Delta,d_i,\omega(\delta), C(\delta)^{2Bi+2};i,k_i\bigr).(15)

The Claim

Theorem 1. Fix an integer B≥2B\ge2 and ζ∈(0,1)\zeta\in(0,1). Let ntn_t be a real sequence tending to infinity, and let 0<δt≤1/20<\delta_t\le1/2 satisfy Ht=δt3log⁡nt→∞H_t=\delta_t^3\log n_t\to\infty. Put Dt=D(B,ζ,Ht)D_t=D(B,\zeta,H_t), and evaluate the schedule at nt,Dtn_t,D_t, writing Δt\Delta_t and ki,tk_{i,t} for its error allowance and half moment order. For every sufficiently large tt, the simultaneous assertion (16) and final-scale assertion (17) hold. 𝒮i(B,Dt,nt,δt)≠⌀(0≤i≤Dt).\mathcal S_i(B,D_t,n_t,\delta_t)\ne\varnothing \qquad(0\le i\le D_t).(16)✦ 𝒞δt(nt,Δt,dDt,ω(δt),C(δt)2BDt+2;Dt,kDt,t)≠⌀.\mathcal C_{\delta_t}\bigl(n_t,\Delta_t,d_{D_t},\omega(\delta_t), C(\delta_t)^{2BD_t+2};D_t,k_{D_t,t}\bigr)\ne\varnothing.(17)✦

In the paper, the result reads: fixing B,ζB,\zeta, the section parameter c+c_+ and the remaining section parameters, along every sequence with n→∞n\to\infty and δ3log⁡n→∞\delta^3\log n\to\infty, eventually level pairs satisfying Definition 2.2 exist simultaneously for 0≤i≤D0\le i\le D, with common C,ωC,\omega depending only on δ\delta and satisfying the stated logarithmic bounds, and one constant MBM_B depending only on BB that works at every level.

What Is Checked

The assertions are stated over the concrete finite probability constructions in (9), specialized by the source schedule (15). The deletion mask probabilities sum to one over all masks of a fixed length for every real qq.✦