OctoInformBeta

OpenAI preprint, September 2026 · §4. The exact correction and copy hierarchy · §4

Proposition 4.7 [Reward identity and a shallow target]: For a correct prize triple and 2i+k≤n2^{i+k}\le n, kk steps leave the reward at the all-primary copy of xx within |S|2k−4(i+k)|S|2^{k-4(i+k)} of v(x)v(x)

The reward identity survives the prize step.

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 copy hierarchy carries the acceptance probability of a randomized logspace machine through a sequence of stages. A stage is a weighted graph on a finite set of nodes, read as one step of a random walk whose moves only climb; passing to the next stage replaces every node by a fixed number MM of copies, one of them primary, and shares the transitions of the walk out among them. Rewards are paid at the nodes, and a reward identity ties them to the probability.

The item asks whether the reward identity survives the passage to the next stage, and how far, after kk passages, the reward at the copy that was primary at every passage falls below the probability at the node it descends from. On the way it bounds the number of nodes still active.

Stages

Vectors and matrices are indexed by the natural numbers: a real vector uu assigns a real number u(x)u(x) to each natural number xx✦, and a matrix of reals CC assigns a real number C(x,y)C(x,y) to each pair (x,y)(x,y).✦ A finite domain is a finite set SS of natural numbers, its nodes.✦ Products over SS of a matrix CC with a matrix GG or a vector uu, and the row weight wS(C,x)w_S(C,x) of CC at a row xx, sum over the nodes of SS: (CG)(x,y)=∑z∈SC(x,z)G(z,y),(Cu)(x)=∑y∈SC(x,y)u(y),wS(C,x)=∑y∈SC(x,y).(CG)(x,y)=\sum_{z\in S}C(x,z)\,G(z,y),\qquad (Cu)(x)=\sum_{y\in S}C(x,y)\,u(y),\qquad w_S(C,x)=\sum_{y\in S}C(x,y).(1)

Given finite domains SS and S′S' and reals ff and λ\lambda, a matrix CC is a bounded support matrix when 0≤C(x,y)≤λf0\le C(x,y)\le\lambda f for all xx and yy, wS(C,x)≤λw_S(C,x)\le\lambda for every xx, and C(x,y)>0C(x,y)>0 only when xx and yy lie in the active set S′S' and x<yx<y.✦ A stochastic step matrix on SS at rate ff is a bounded support matrix with S′=SS'=S and λ=1\lambda=1.✦

The parameter constants are four natural numbers p=(T,K,J,M)p=(T,K,J,M), an iteration count TT, two parameters KK and JJ, and a number MM of copies, subject to T>0,(5/A)TT!≤11024,128(1+32(T+1)η(δ))≤K+1,M>16(T+1),64M(T+1)2≤δ(J+1),T>0,\quad \frac{(5/A)^T}{T!}\le\frac{1}{1024},\quad 128\Big(1+\frac{32(T+1)}{\eta(\delta)}\Big)\le K+1,\quad M>16(T+1),\quad 64\,M(T+1)^2\le\delta\,(J+1),(2)✦ where A=1/4096A=1/4096 is the cutoff scale, δ=A/400\delta=A/400 and η(z)=z/1000\eta(z)=z/1000; an iteration count TT is admissible when it meets the first two conditions.✦

A stage P=(p,i,S,C)P=(p,i,S,C) consists of parameter constants pp, a level ii, a finite domain SS of nodes and a matrix CC of transition weights.✦ The rate of level ii is 2−4i2^{-4i}✦, and it is the stage rate ff of PP.✦

The Copy Step

The copy step uses smooth ramps built from the clamp c(u)=min⁡(1,max⁡(0,u))c(u)=\min(1,\max(0,u)), the point of [0,1][0,1] nearest to a real number uu. The fade function is ϕ(x)=12(c(2x)4+1−c(2−2x)4),\phi(x)=\tfrac12\big(c(2x)^4+1-c(2-2x)^4\big),(3)✦ a continuously differentiable ramp that vanishes for x≤0x\le0, equals 8x48x^4 on [0,12][0,\tfrac12] and 1−8(1−x)41-8(1-x)^4 on [12,1][\tfrac12,1], and equals 11 for x≥1x\ge1. The smooth rising ramp from aa to a′a' is ρa,a′(x)=ϕ((x−a)/(a′−a))\rho_{a,a'}(x)=\phi\big((x-a)/(a'-a)\big).✦ The boost function is h=ρ1/4,1/2h=\rho_{1/4,1/2}✦, the cutoff function is γ=1−ρ1/2,4/5\gamma=1-\rho_{1/2,4/5}✦, and the slice function is s=ρ1/128,1/64s=\rho_{1/128,1/64}, which vanishes up to its lower threshold 1/1281/128 and equals 11 from its upper threshold 1/641/64 on.✦

A pilot pair (V,E)(V,E) is a real vector VV of probed values together with a matrix EE of corrections.✦ The pilot sequence of a stage PP is the sequence of pilot pairs that starts from the zero vector and the zero matrix and whose term of index m+1m+1 is obtained from its term of index mm by the update of PP, a map on pilot pairs that depends on nn, the prime field size of the channels over (ℤ/n)4(\mathbb Z/n)^4.✦ The probed vector qmq_m after mm rounds is the vector of the term of index mm.✦

For a finite domain SS, a scale ff, a real vector gg and a matrix CC, the corrected iteration of CC is the sequence of matrices with F0=0F_0=0 and Fm+1F_{m+1} obtained from the combined matrix C+FmCC+F_mC by the entrywise correction, the operation on matrices that adjusts each entry at scale ff with weights gg.✦ The stage correction matrix FmF_m of a stage PP is the term of index mm in the corrected iteration of its matrix CC on SS at its rate ff, with weights the cutoffs γ(qT(x))\gamma(q_T(x)) of the probed values after TT rounds.✦ The residual of CC against a matrix FF over SS is C+FC−FC+FC-F✦, and the corrected residual DD of PP is the residual of CC against FTF_T.✦

With MM copies per node, copy z<Mz<M of a node xx is the radix index z+Mxz+Mx, the copy z=0z=0 being primary, and every natural number x′x' is copy x′mod⁡Mx'\bmod M of ⌊x′/M⌋\lfloor x'/M\rfloor.✦ The copy zone of SS is the set S+={z+Mx:x∈S,z<M}S^+=\{z+Mx : x\in S,\ z<M\}.✦ The boost factor of copy zz of xx is β0(x)=1\beta_0(x)=1 for the primary copy and βz(x)=h(qT(x))\beta_z(x)=h(q_T(x)) for z≠0z\ne0.✦ The share of copy zz at a ratio tt is σ0(t)=1−s(t)+s(t)/M\sigma_0(t)=1-s(t)+s(t)/M for the primary copy and σz(t)=s(t)/M\sigma_z(t)=s(t)/M for z≠0z\ne0, so that the MM shares sum to 11.✦

The next stage of PP is P+=(p,i+1,S+,C+)P^+=(p,i+1,S^+,C^+)✦, whose matrix is the next stage matrix C+(z+Mx,z′+My)=βz(x)D(x,y)σz′(D(x,y)/f)(z,z′<M).C^+(z+Mx,\,z'+My)=\beta_z(x)\,D(x,y)\,\sigma_{z'}\big(D(x,y)/f\big)\qquad(z,z'<M).(4)✦

The projection to copies of a real vector uu is the vector Πu\Pi u with (Πu)(z+Mx)=βz(x)u(x)(z<M).(\Pi u)(z+Mx)=\beta_z(x)\,u(x)\qquad(z<M).(5)✦

Prize Triples

A prize triple Q=(P,W,v)Q=(P,W,v) consists of a stage PP, a real vector WW of rewards paid at the nodes, and a real vector vv standing for the true acceptance probability transported to the nodes.✦ With P=(p,i,S,C)P=(p,i,S,C) and stage rate ff, the triple QQ is correct when CC is a stochastic step matrix on SS at rate ff, W≥0W\ge0, v(x)v(x) lies in [0,1][0,1] for every xx, and the reward identity holds: v=W+Cv.v=W+Cv.(6)✦

The prize step at field size nn takes QQ to Q+=(P+,W+,v+)Q^+=(P^+,W^+,v^+), where W+=Π(W+FTW),v+=Πv.W^+=\Pi\big(W+F_TW\big),\qquad v^+=\Pi v.(7)✦ The iterates of the prize step at field size nn starting from QQ are Q0=QQ_0=Q and Qk+1=(Qk)+Q_{k+1}=(Q_k)^+, written Qk=(Pk,Wk,vk)Q_k=(P_k,W_k,v_k), with SkS_k and CkC_k the domain and matrix of PkP_k. The all-primary copy of a node xx after kk steps is x(k)x^{(k)}, given by x(0)=xx^{(0)}=x and x(k+1)=Mx(k)x^{(k+1)}=Mx^{(k)}, the primary copy of x(k)x^{(k)}.✦

The active nodes of a matrix CC on a finite domain SS form the set N(S,C)N(S,C) of the x∈Sx\in S for which some y∈Sy\in S has C(x,y)>0C(x,y)>0 or C(y,x)>0C(y,x)>0.✦

The Claim

Theorem 1. Let Q=(P,W,v)Q=(P,W,v) be a prize triple whose stage PP has level ii and domain SS, let nn be the field size, and let kk and xx be natural numbers. Then vk(x(k))=v(x).v_k\big(x^{(k)}\big)=v(x).(8)✦ If QQ is correct, then 0≤W(x)≤10\le W(x)\le1(9)✦ and Q+is correct.Q^+\ \text{is correct}.(10)✦ If QQ is correct and 2i+k≤n2^{i+k}\le n, then |N(Sk,Ck)|≤|S|2k\bigl|N(S_k,C_k)\bigr|\le|S|\,2^k(11)✦ and 0≤v(x)−Wk(x(k))≤|S|2k2−4(i+k).0\le v(x)-W_k\big(x^{(k)}\big)\le|S|\,2^k\,2^{-4(i+k)}.(12)✦

In the paper, the result reads: for every stage ℓ\ell, CℓPcℓ=Pcℓ−Bℓ(I−S)C_\ell P^{c_\ell}=P^{c_\ell}-B_\ell(I-S), the reward Wℓ=BℓeW_\ell=B_\ell e satisfies 0≤Wℓ≤10\le W_\ell\le1 and Wℓ=Pcℓp0−CℓPcℓp0W_\ell=P^{c_\ell}p_0-C_\ell P^{c_\ell}p_0, Wℓ+1(xi)=ri(x)(Wℓ(x)+(EℓWℓ)(x))W_{\ell+1}(x_i)=r_i(x)\big(W_\ell(x)+(E_\ell W_\ell)(x)\big), and at the all-primary copy x‾ℓ\bar x_\ell of a base vertex xx, 0≤p0(x)−Wℓ(x‾ℓ)≤|V0|2−(H−1)ℓ0\le p_0(x)-W_\ell(\bar x_\ell)\le|V_0|\,2^{-(H-1)\ell}, where the paper’s p0p_0, EℓE_\ell, ri(x)r_i(x) and V0V_0 stand for the page’s vv, FTF_T, βi(x)\beta_i(x) and the domain of the first stage.

What Is Checked

The claim is stated over prize triples on the stages of the copy hierarchy at field size nn, their correctness, the prize step with its projection Π\Pi and correction matrix FTF_T, its iterates QkQ_k, the all-primary copy x(k)x^{(k)} and the active nodes N(Sk,Ck)N(S_k,C_k), with the rate 2−4(i+k)2^{-4(i+k)} in the bound.