OctoInformBeta

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

Lemma 7 [Local replay]: For a tour with finite words, a list opening with the reference controller passes the replay of every block exactly when it agrees with the run

Local block replays certify a controller transcript.

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

Cut the work tape of a one-tape computation of TT steps into NN blocks and run it as a tour, a sequence of visits: at each visit a controller, a word of cc bits, selects one block, and the visit turns the controller and the content of that block into an outgoing controller and new content for the block.

A proposed transcript of nn visits, a list of n+1n+1 controllers, can be checked one block at a time. Block ii needs only its own content at the start and the list: it replays the visits of the list that select ii and compares each outgoing controller with the next entry. The question is whether these NN local checks together certify the list, and in what space one replay runs.

Tours and Their Runs

A tour 𝒯\mathcal T consists of positive integers kk and NN, a natural number cc, an initial controller zinitz_{\mathrm{init}}, initial blocks τ(0),τ(1),…\tau(0),\tau(1),\dots, a selector that sends every natural number zz to a block index sel(z)<N\mathrm{sel}(z)<N, and a visit map that sends a controller zz and a block BB to a pair visit(z,B)=(z′,B′)\mathrm{visit}(z,B)=(z',B') of an outgoing controller and a new block, controllers and blocks being natural numbers.✦ The radix of a tour 𝒯\mathcal T is m=2cm=2^c and its block length is b=k2b=k^2.✦

A tour has finite words when its controllers stay below mm and its blocks below mbm^b: zinit<mz_{\mathrm{init}}<m, τ(i)<mb\tau(i)<m^b for every ii, and visit(z,B)=(z′,B′)\mathrm{visit}(z,B)=(z',B') has z′<mz'<m and B′<mbB'<m^b whenever z<mz<m and B<mbB<m^b.✦

The reference run of 𝒯\mathcal T is its sequence of scenes, a scene being a controller together with a sequence of blocks: the scene at visit 00 is zinitz_{\mathrm{init}} with the blocks τ\tau, and each later scene comes from the one before by one visit.✦ We write ztz_t for the controller and Bt(i)B_t(i) for the content of block ii in the scene at visit tt.

A natural number ZZ is read as a list of controllers through its digits in radix mm, Zj=⌊Z/mj⌋mod⁡mZ_j=\lfloor Z/m^j\rfloor \bmod m, least significant first.✦ A natural number ZZ agrees with the run from visit tt for nn visits when its digits Z0,…,ZnZ_0,\dots,Z_n are the reference controllers zt,…,zt+nz_t,\dots,z_{t+n}.✦

Local Replay

The replay Replayi(Z,B,n)\mathrm{Replay}_i(Z,B,n) of block ii on a list ZZ from a block BB, for nn entries, is the pair (Yn,βn)(Y_n,\beta_n) of a buffer YnY_n and a flag βn∈{0,1}\beta_n\in\{0,1\} that starts at (Y0,β0)=(Bmod⁡mb,1)(Y_0,\beta_0)=(B\bmod m^b,1) and takes at entry jj the step✦ (Yj+1,βj+1)={(B′,βj∧[z′=Zj+1])if sel(Zj)=i, where (z′,B′)=visit(Zj,Yj),(Yj,βj)otherwise,(Y_{j+1},\beta_{j+1})= \begin{cases} \bigl(B',\ \beta_j\wedge[z'=Z_{j+1}]\bigr) & \text{if } \mathrm{sel}(Z_j)=i, \text{ where } (z',B')=\mathrm{visit}(Z_j,Y_j),\\ (Y_j,\beta_j) & \text{otherwise}, \end{cases}(1)✦ where [z′=Zj+1][z'=Z_{j+1}] is 11 when z′=Zj+1z'=Z_{j+1} and 00 otherwise. The replay of block ii from visit tt is Replayi(Z,Bt(i),n)\mathrm{Replay}_i(Z,B_t(i),n), and it passes when its flag βn\beta_n is 11.✦

Computation in Space

For families xx of words over an alphabet and SS, aa, yy of natural numbers, all indexed by a set II, yy is computable from aa in space SS over xx, written a→x,Sya\to_{x,S}y, when one stack machine, a finite control with a read-only head on the public input and finitely many stacks of bits as work storage, turns at every index ι\iota a stack holding the bits of aιa_\iota into one holding the bits of yιy_\iota, least significant first, on public input xιx_\iota and within C(Sι+1)C\,(S_\iota+1) work bits, for a constant CC independent of ι\iota.✦ Along a map r:U→Ir\colon U\to I, families indexed by UU are computed over x∘rx\circ r in space S∘rS\circ r: instance uu has public input xr(u)x_{r(u)} and space bound Sr(u)S_{r(u)}.✦

The pairing ⟨u,v⟩\langle u,v\rangle of natural numbers uu and vv is the number whose binary expansion, least significant bit first, writes every bit of uu preceded by a 00, then a 11, then the bits of vv.✦

The prime pp of a tour 𝒯\mathcal T is the largest prime with D+1<p≤2D+2D+1<p\le 2D+2, where D=(N+1)c(b+1)D=(N+1)\,c\,(b+1) is the outer degree.✦ The evaluation circuit of 𝒯\mathcal T, the circuit that evaluates its run, has width c(b+1)c(b+1) and NN children per node.

A family of tours 𝒯ι\mathcal T_\iota, ι∈I\iota\in I, is runnable over xx in space SS from parameters qιq_\iota when, with kk, cc, NN, mm, bb and pp read in 𝒯ι\mathcal T_\iota:✦

  • kk, cc, NN and zinitz_{\mathrm{init}} are computable from qq in space SS over xx;✦

  • the bit length of pc(b+1)+1p^{\,c(b+1)+1} is at most a constant multiple of Sι+1S_\iota+1, one constant for every ι\iota;✦

  • the initial blocks, the selector and the visit map are computable at computable arguments: for every map r:U→Ir\colon U\to I and families aa, yy, hh indexed by UU with q∘rq\circ r, yy and hh computable from aa in space S∘rS\circ r over x∘rx\circ r, so is τ(yu)\tau(y_u), so is sel(yu)\mathrm{sel}(y_u) when every yu<my_u<m, and so is ⟨z′,B′⟩\langle z',B'\rangle for (z′,B′)=visit(yu,hu)(z',B')=\mathrm{visit}(y_u,h_u) when moreover every hu<mbh_u<m^b, all in the tour 𝒯r(u)\mathcal T_{r(u)}.✦

The Claim

Theorem 1 (Local replay). Let 𝒯\mathcal T be a tour with finite words and reference run (zt,Bt)(z_t,B_t), let ZZ be a natural number, and let tt and nn be natural numbers.

  1. For every block index ii and block BB, the buffer of Replayi(Z,B,n)=(Yn,βn)\mathrm{Replay}_i(Z,B,n)=(Y_n,\beta_n) satisfies Yn<mb.Y_n<m^b.(2)✦

  2. If ZZ agrees with the run from visit tt for nn visits, then for every block index ii, Replayi(Z,Bt(i),n)=(Bt+n(i),1).\mathrm{Replay}_i\bigl(Z,B_t(i),n\bigr)=\bigl(B_{t+n}(i),1\bigr).(3)✦

  3. If Z0=ztZ_0=z_t and the replay of every block i<Ni<N from visit tt for nn entries passes, then Zj=zt+j(0≤j≤n).Z_j=z_{t+j}\qquad (0\le j\le n).(4)✦

  4. Let 𝒯ι\mathcal T_\iota, ι∈I\iota\in I, be tours with finite words forming a family runnable over xx in space SS from parameters qq, let r:U→Ir\colon U\to I be a map, and let aa, ii, ZZ, BB, nn be families indexed by UU such that q∘rq\circ r, ii, ZZ, BB and nn are computable from aa in space S∘rS\circ r over x∘rx\circ r and nu≤bn_u\le b in the tour 𝒯r(u)\mathcal T_{r(u)} for every uu. Then, with (Yu,βu)(Y_u,\beta_u) the replay Replayiu(Zu,Bu,nu)\mathrm{Replay}_{i_u}(Z_u,B_u,n_u) in 𝒯r(u)\mathcal T_{r(u)}, a→x∘r,S∘r(⟨Yu,βu⟩)u∈U.a\to_{x\circ r,\,S\circ r}\bigl(\langle Y_u,\beta_u\rangle\bigr)_{u\in U}.(5)✦

In the paper, the result reads: for 0≤n≤b0\le n\le b, the replay Replayi(Z,B)\mathrm{Replay}_i(Z,B) scans the controller list Z=(z0,…,zn)Z=(z_0,\dots,z_n), applies the visits that select block ii to a buffer initialized to BB and conjoins the bitwise checks, continuing after failures, is total and uses O((b+(n+1)c+1)polylogT)O\bigl((b+(n+1)c+1)\,\mathrm{polylog}\,T\bigr) workspace and no word evaluation, and for a proposed list with the reference z0z_0 all replay flags equal one if and only if the list is the reference controller list, in which case each buffer is the reference block after nn visits, the page’s nn standing for the paper’s mm.

What Is Checked

The claim is stated over tours with finite words and their reference runs, lists of controllers read through their digits in radix mm, agreement with the run, and the replay (1) of a block from a visit, and its fourth part over runnable families of tours, the prime of a tour’s evaluation circuit, the pairing of numbers and computability in space over a family of public inputs along a map of index sets.