OctoInformBeta

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

§2: The global schedule: Backward target scales and moment orders for the trace reconstruction induction

A schedule for the multiscale construction.

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 multiscale trace reconstruction construction uses blocks of varying dimension and compares scores at different target scales. A global schedule specifies the depth of the construction and the even moments used for its score estimates.

Let q∈(0,1)q\in(0,1) be the requested deletion probability, so that each bit survives with probability 1−q1-q, and put δ=min⁡{q,1/2}\delta=\min\{q,1/2\} and Λ=δ−3\Lambda=\delta^{-3}; the construction theorems call their working rate qq. Write Hdel>1H_{\mathrm{del}}>1 for the parameter governing the depth, and n>1n>1 for the terminal scale. Block indices start at zero: block ii has dimension bi+1b_{i+1}.

For a real number xx, write ⌊x⌋+=max⁡{0,⌊x⌋}\lfloor x\rfloor_+=\max\{0,\lfloor x\rfloor\} and ⌈x⌉+=max⁡{0,⌈x⌉}\lceil x\rceil_+=\max\{0,\lceil x\rceil\} for rounding to nonnegative integers.

The Definition

For a dimension b∈ℕb\in\mathbb N, a scale index j∈ℕj\in\mathbb N and a real slack ε\varepsilon, the scale exponent aj(b;ε)∈ℝa_j(b;\varepsilon)\in\mathbb R is the quantity in (1). aj(b;ε)=(1+ε)2j2b−ε.a_j(b;\varepsilon)=(1+\varepsilon)\frac{2^j}{2^b}-\varepsilon.(1)✦ The block gain g(b)∈ℝg(b)\in\mathbb R associated with dimension b∈ℕb\in\mathbb N is defined by (2). g(b)=b−14−120.g(b)=\frac{b-1}{4}-\frac1{20}.(2)✦

Definition 1 (Global schedule). Let B≥2B\geq2 be an integer and let 0<ζ<10<\zeta<1. The depth D∈ℕD\in\mathbb N and warmup block count j0∈ℕj_0\in\mathbb N are given by (3) and (4), respectively. D=⌊(1−ζ)log⁡HdelBlog⁡2⌋+.D=\left\lfloor \frac{(1-\zeta)\log H_{\mathrm{del}}}{B\log2} \right\rfloor_+.(3)✦ j0=5⋅2B.j_0=5\cdot2^B.(4)✦ The scale slack ε∈ℝ\varepsilon\in\mathbb R is defined by (5), and the dimension bi+1∈ℕb_{i+1}\in\mathbb N of block i∈ℕi\in\mathbb N by (6). ε=124B+100(D+1).\varepsilon=\frac{1}{2^{4B+100}(D+1)}.(5)✦ bi+1={2,i<j0,B,i≥j0.b_{i+1}=\begin{cases} 2,&i<j_0,\\ B,&i\geq j_0. \end{cases}(6)✦ The backward scale exponent product Ai∈ℝA_i\in\mathbb R at level i∈ℕi\in\mathbb N is defined by (7), using the scale exponent in (1). Ai=∏j∈ℕi≤j<Da0(bj+1;ε).A_i=\prod_{\substack{j\in\mathbb N\\i\leq j<D}} a_0(b_{j+1};\varepsilon).(7)✦ The backward target scale Ni∈ℝN_i\in\mathbb R is the power of the terminal scale specified in (8). Ni=nAi.N_i=n^{A_i}.(8)✦ The total score exponent dD∈ℝd_D\in\mathbb R is defined by (9) using the block gain in (2). dD=115+∑i=0D−1g(bi+1).d_D=\frac{11}{5}+\sum_{i=0}^{D-1}g(b_{i+1}).(9)✦ The half moment order ki∈ℕk_i\in\mathbb N in (10) determines the even score exponent ri=2kir_i=2k_i. ki=⌈108210B(dD+B+1)log⁡nlog⁡Ni⌉+.k_i=\left\lceil 10^8\,2^{10B}(d_D+B+1)\frac{\log n}{\log N_i} \right\rceil_+.(10)✦

In the paper, the result reads: fix 0<c<c+<1/(4log⁡2)0<c<c_+<1/(4\log2), choose an integer B≥2B\geq2 and 0<ζ<10<\zeta<1 such that (1−ζ)((B−1)/4−0.05)/(Blog⁡2)>c+(1-\zeta)((B-1)/4-0.05)/(B\log2)>c_+, set D=⌊(1−ζ)log⁡Hdel/(Blog⁡2)⌋D=\lfloor(1-\zeta)\log H_{\mathrm{del}}/(B\log2)\rfloor, j0=5⋅2Bj_0=5\cdot2^B, ε=2−4B−100/(D+1)\varepsilon=2^{-4B-100}/(D+1) and bi=2b_i=2 for i≤j0i\leq j_0 and bi=Bb_i=B afterward, with eventually D>j0D>j_0; set a0(b;ε)=(1+ε)2−b−εa_0(b;\varepsilon)=(1+\varepsilon)2^{-b}-\varepsilon, ND=nN_D=n, Ni−1=Nia0(bi;ε)N_{i-1}=N_i^{a_0(b_i;\varepsilon)}, d0=2.20d_0=2.20 and di=di−1+(bi−1)/4−0.05d_i=d_{i-1}+(b_i-1)/4-0.05; finally set Δ=n−100(dD+B+1)\Delta=n^{-100(d_D+B+1)} and ri=2⌈108210B(dD+B+1)log⁡n/log⁡Ni⌉r_i=2\lceil10^8\,2^{10B}(d_D+B+1)\log n/\log N_i\rceil, with all statements invoking the global parameters taken in the joint regime n→∞n\to\infty and δ3log⁡n→∞\delta^3\log n\to\infty.

What Is Checked

The depth and warmup count are defined over natural block dimensions and real depth parameters; the scale and moment schedules are defined over natural depths and level indices, with real terminal scales and real slack for the local scale exponents.