OctoInformBeta

OpenAI preprint, September 2026 · §3. Block visits and epoch transcripts · §3

Lemma 8 [Factored round rule]: At a history vertex the guesses are kk controllers and tests replay the NN blocks; a tour with bounded words has a good circuit

Non-base vertices of a tour circuit obey the identity rule.

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

A reference tour follows a computation on a tape cut into NN blocks: a controller of cc bits visits one block at a time. Fix a positive integer kk and group the visits into E=k+1E = k + 1 epochs of b=k2b = k^2 visits, and each epoch into kk rounds of kk visits. For every epoch, record the content of each block at its start and, for r=0,…,kr = 0, \dots, k, the controllers met from its start to the end of round rr. These records are the vertices of a circuit, and each depends on earlier ones: a block’s content on its content one epoch before, a history on the history one round shorter and on the blocks.

The item is about writing each of these dependencies in one algebraic shape over a prime field 𝔽p\mathbb{F}_p: a coordinate of a vertex’s value, written as a bit vector, as a sum over guesses of products of local checks, one check for each child of the vertex.

Dependency Circuits

A dependency circuit CC of width dd with ℓ\ell children per node has finitely many nodes, numbered from 00, a flag marking its base nodes, and at each node vv a head child h(v)h(v), children ch⁡i(v)\operatorname{ch}_i(v) for i<ℓi < \ell, a number g(v)g(v) of guess bits, a first value f(v)f(v) and a semantic value s(v)s(v).✦ The local rules of a dependency circuit CC are a proposal G(v,z,y,w)G(v,z,y,w) and an allowance test T(v,z,y,i,w,a)T(v,z,y,i,w,a), each a natural number for every node vv, coordinate zz, guess yy, child index ii, value ww of the head child and value aa of a child; the guesses at vv are the 2g(v)2^{g(v)} numbers y<2g(v)y < 2^{g(v)}.

The coefficient field of a dependency circuit CC is the prime field 𝔽p=ℤ/pℤ\mathbb{F}_p = \mathbb{Z}/p\mathbb{Z}, where pp is the largest prime with Δ+1<p≤2Δ+2\Delta + 1 < p \le 2\Delta + 2 and Δ=(ℓ+1)d\Delta = (\ell + 1)d is the outer degree of CC; GG and TT are read in 𝔽p\mathbb{F}_p, and vectors over 𝔽p\mathbb{F}_p are sequences indexed by the natural numbers✦. The augmented vector of a number uu at width dd is the vector over 𝔽p\mathbb{F}_p with coordinates αz(u)={bit z of u,z<d,1,z=d,0,z>d.\alpha_z(u) = \begin{cases} \text{bit } z \text{ of } u, & z < d,\\ 1, & z = d,\\ 0, & z > d. \end{cases}(1)✦

A dependency circuit CC is good when every node vv has s(v)<2ds(v) < 2^d and g(v)≤dg(v) \le d, every base node has s(v)=f(v)s(v) = f(v), and every other node vv obeys the identity rule: for every coordinate z≤dz \le d, ∑y<2g(v)G(v,z,y,s(h(v)))∏i<ℓT(v,z,y,i,s(h(v)),s(ch⁡i(v)))=αz(s(v))in 𝔽p.\sum_{y < 2^{g(v)}} G\bigl(v,z,y,s(h(v))\bigr) \prod_{i < \ell} T\bigl(v,z,y,i,s(h(v)),s(\operatorname{ch}_i(v))\bigr) = \alpha_z\bigl(s(v)\bigr) \quad \text{in } \mathbb{F}_p.(2)✦

Reference Tours

A reference tour DD consists of a positive integer kk, a controller width cc, a positive number NN of blocks, an initial controller ζ0\zeta_0, an initial content B0(i)B_0(i) of every block ii, a selection σ\sigma naming for each controller ζ\zeta the block σ(ζ)<N\sigma(\zeta) < N it reads and rewrites, and a visit map sending a controller and the content of that block to the next controller and the block’s new content.✦ The controller radix of a reference tour DD is m=2cm = 2^c; DD has b=k2b = k^2 digits per block, guess length ckck and width d=c(b+1)d = c(b + 1), the number of bits in b+1b + 1 controllers, at which all its augmented coordinates are taken.

A reference tour DD has finite word bounds when its controllers are words below mm and its block contents words below mbm^b: ζ0<m\zeta_0 < m, every B0(i)<mbB_0(i) < m^b, and the visit map sends a controller below mm and a content below mbm^b to a controller below mm and a content below mbm^b.✦

The story of DD is its sequence of scenes (ζt,Bt)(\zeta_t, B_t), each a controller ζt\zeta_t with the contents Bt(i)B_t(i) of all blocks; it starts from ζ0\zeta_0 and B0B_0 and passes from tt to t+1t + 1 by one visit.✦ The controller history L(t,n)L(t,n) from visit tt over nn steps packs the n+1n + 1 controllers ζt,…,ζt+n\zeta_t, \dots, \zeta_{t+n} in base mm, least significant first: L(t,n)=∑i=0nζt+imi.L(t,n) = \sum_{i=0}^{n} \zeta_{t+i}\, m^i.(3)✦

The circuit of DD has the vertices v<E(N+k+1)v < E(N + k + 1), and the epoch and the column of vv are the quotient and the remainder of vv divided by the stride N+k+1N + k + 1. In epoch ee, column j<Nj < N holds the array vertex Ae,jA_{e,j}, column NN the start vertex He,0H_{e,0}, and column N+rN + r, for 1≤r≤k1 \le r \le k, the history vertex He,rH_{e,r} of round rr; the round index of a vertex is its column minus NN, or 00 at columns up to NN✦. Values are read off the story at visit ebeb: s(Ae,j)=Beb(j),s(He,r)=L(eb,rk).s(A_{e,j}) = B_{eb}(j), \qquad s(H_{e,r}) = L(eb, rk).(4)✦

The header h(v)h(v) of a vertex vv of epoch ee is He−1,kH_{e-1,k} when vv is an array vertex or the start vertex, and He,r−1H_{e,r-1} when v=He,rv = H_{e,r} with r≥1r \ge 1.✦ The children ch⁡i(v)\operatorname{ch}_i(v) of a vertex vv of epoch ee, for i<Ni < N, are all Ae−1,jA_{e-1,j} when v=Ae,jv = A_{e,j}, all equal to the header when v=He,0v = H_{e,0}, and ch⁡i(v)=Ae,i\operatorname{ch}_i(v) = A_{e,i} when v=He,rv = H_{e,r} with r≥1r \ge 1.✦ A vertex has g(v)=0g(v) = 0 guess bits at columns up to NN and g(v)=ckg(v) = ck beyond.✦ The first value f(v)f(v) of a vertex vv is B0(j)B_0(j) at a column j<Nj < N and ζ0\zeta_0 at the others.✦ The base vertices of DD are the vertices of epoch 00 at columns up to NN.✦

Offers and Validity Checks

The round proposal πr(w,y)\pi_r(w,y) at a history vertex of round r≥1r \ge 1, for a header value ww and a guess yy, is the number whose lowest n=(r−1)k+1n = (r - 1)k + 1 digits in base mm are those of ww and whose higher digits are those of yy: πr(w,y)=(wmod⁡mn)+mny,n=(r−1)k+1.\pi_r(w,y) = (w \bmod m^n) + m^n y, \qquad n = (r - 1)k + 1.(5)✦

Write dig⁡b(w)=⌊w/mb⌋mod⁡m\operatorname{dig}_b(w) = \lfloor w / m^b \rfloor \bmod m for the digit of ww at place bb in base mm.✦ The offer at a vertex vv of epoch ee, in coordinate zz, for a guess yy and a header value ww, is ωv(z,y,w)={1,v=Ae,j,αz(dig⁡b(w)),v=He,0,αz(πr(w,y)),v=He,r,r≥1.\omega_v(z,y,w) = \begin{cases} 1, & v = A_{e,j},\\ \alpha_z\bigl(\operatorname{dig}_b(w)\bigr), & v = H_{e,0},\\ \alpha_z\bigl(\pi_r(w,y)\bigr), & v = H_{e,r},\ r \ge 1. \end{cases}(6)✦

The replay of block ii under a transcript ZZ, a number read digit by digit in base mm, from a content BB is the sequence of pairs ρi(Z,B,n)=(βi(Z,B,n),εi(Z,B,n))\rho_i(Z,B,n) = \bigl(\beta_i(Z,B,n), \varepsilon_i(Z,B,n)\bigr) of a block content and a verdict, true or false, read as 11 or 00: it starts from ρi(Z,B,0)=(Bmod⁡mb,1)\rho_i(Z,B,0) = (B \bmod m^b, 1), and its term n+1n + 1 is obtained from its term nn by one replay step of block ii in the visit map of DD, taken at digit nn of ZZ, which updates the content and the verdict according to the visit map and that digit.✦

The validity check at a vertex vv of epoch ee, in coordinate zz, for a guess yy, a child ii, a header value ww and a child value aa, is τv(z,y,i,w,a)={αz(βj(w,a,b)),v=Ae,j,i=0,1,v=Ae,j,i≠0, or v=He,0,εi(πr(w,y),a,rk),v=He,r,r≥1.\tau_v(z,y,i,w,a) = \begin{cases} \alpha_z\bigl(\beta_j(w,a,b)\bigr), & v = A_{e,j},\ i = 0,\\ 1, & v = A_{e,j},\ i \ne 0, \text{ or } v = H_{e,0},\\ \varepsilon_i\bigl(\pi_r(w,y), a, rk\bigr), & v = H_{e,r},\ r \ge 1. \end{cases}(7)✦

The tour circuit CDC_D is the dependency circuit whose nodes are the vertices of DD, of the width dd of DD with ℓ=N\ell = N children per node, with the base vertices, headers, children, guess bits, first values and values of DD, the offer as proposal and the validity check as allowance test.✦ The required identity at a vertex vv and a coordinate zz is the identity (2) of CDC_D at vv and zz.✦

The Claim

Theorem 1. Let DD be a reference tour and zz any coordinate; the identities below are in the coefficient field 𝔽p\mathbb{F}_p of CDC_D.

  1. For every epoch e<Ee < E and every j<kj < k, the required identity holds at the history vertex He,j+1H_{e,j+1}: with w=s(He,j)w = s(H_{e,j}), ∑y<2ckαz(πj+1(w,y))∏i<Nεi(πj+1(w,y),s(Ae,i),(j+1)k)=αz(s(He,j+1)).\sum_{y < 2^{ck}} \alpha_z\bigl(\pi_{j+1}(w,y)\bigr) \prod_{i < N} \varepsilon_i\bigl(\pi_{j+1}(w,y), s(A_{e,i}), (j + 1)k\bigr) = \alpha_z\bigl(s(H_{e,j+1})\bigr).(8)✦

  2. For every ee with e+1<Ee + 1 < E and every block i<Ni < N, the required identity holds at the array vertex Ae+1,iA_{e+1,i}: αz(βi(s(He,k),s(Ae,i),b))=αz(s(Ae+1,i)).\alpha_z\Bigl(\beta_i\bigl(s(H_{e,k}), s(A_{e,i}), b\bigr)\Bigr) = \alpha_z\bigl(s(A_{e+1,i})\bigr).(9)✦

  3. For every ee with e+1<Ee + 1 < E, the required identity holds at the start vertex He+1,0H_{e+1,0}: αz(dig⁡b(s(He,k)))=αz(s(He+1,0)).\alpha_z\Bigl(\operatorname{dig}_b\bigl(s(H_{e,k})\bigr)\Bigr) = \alpha_z\bigl(s(H_{e+1,0})\bigr).(10)✦

  4. If DD has finite word bounds, then CD is good.C_D \text{ is good.}(11)✦

In the paper, the result reads: for 0≤j<k0 \le j < k, each round update He,j↦He,j+1H_{e,j} \mapsto H_{e,j+1} is a factored rule of the paper’s Lemma 5, with distinguished child He,jH_{e,j}, the NN array vertices of epoch ee as its other children and guess length g=ck≤dg = ck \le d.

What Is Checked

The claim is stated over a reference tour DD with its story, controller histories (3) and block replays, the vertices of its circuit with their values (4), headers and children, the round proposal (5), the offer (6), the validity check (7), the required identity of the tour circuit CDC_D over 𝔽p\mathbb{F}_p and the notion of a good dependency circuit, with finite word bounds on DD as the hypothesis of its last part.