OctoInformBeta

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

Lemma 9 [Weight of the epoch path]: One hard price and k+2k + 2 easy ones per epoch, and no vertex holds more than EE epochs’ worth of coins

Coins that pay for every step down the epoch circuit.

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 DD is a block computation given by a positive integer kk, a controller width of cc bits, a positive number NN of blocks, an initial controller q0q_0, an initial word Bi0B^0_i for each block ii, a selection σ\sigma that names for each controller zz the block σ(z)<N\sigma(z) < N it reads and rewrites, and a visit map δ\delta that sends a controller and the word of that block to the next controller and the block’s new word.✦ The story of a reference tour DD is the sequence of scenes sn=(qn,Bn)s_n = (q_n, B^n), where qnq_n is the controller and BnB^n the words of all blocks after nn visits, with s0=(q0,B0)s_0 = (q_0, B^0) and one visit from each scene to the next.✦

The epoch circuit 𝒞D\mathcal{C}_D of DD reads the story every b=k2b = k^2 visits, over E=k+1E = k + 1 epochs. Its E(N+k+1)E(N + k + 1) vertices are the numbers ve,j=e(N+k+1)+jv_{e,j} = e(N + k + 1) + j for an epoch e<Ee < E and a column j<N+k+1j < N + k + 1, so that a vertex vv has epoch ⌊v/(N+k+1)⌋\lfloor v/(N + k + 1) \rfloor and column vmod⁡(N+k+1)v \bmod (N + k + 1). In column j<Nj < N stands the array vertex of block jj, whose value is the word BjebB^{eb}_j held by block jj after ebeb visits. Column N+rN + r, for 0≤r≤k0 \le r \le k, holds the start vertex when r=0r = 0 and the history vertex of round rr otherwise. The round index of a vertex in column N+rN + r is rr, and that of an array vertex is 00. With m=2cm = 2^c, the value of the vertex in epoch ee and column N+rN + r is the controller history L(eb,rk)=∑i=0rkqeb+imiL(eb, rk) = \sum_{i=0}^{rk} q_{eb+i}\, m^i, written in base mm.

A recursive evaluation of 𝒞D\mathcal{C}_D descends from a vertex to the vertices its value depends on, and each descent costs work space for a frame, more when the frame holds guessed controllers; the space used is that of the heaviest chain of descents. Instead of enumerating chains, one puts a potential on the vertices: coins that pay for each descent out of the vertex it starts from.

Circuits, Prices and Meters

An evaluation circuit CC of width dd with ℓ\ell children per node has nodes 0,…,n−10, \dots, n - 1, some of them marked as base nodes.✦ Each node vv has a head child h(v)h(v), children ch(v,i)\mathrm{ch}(v, i), a number g(v)g(v) of guessed bits, a first value prescribed at base nodes and a semantic value, and the circuit has two local rules, each a number for every node and coordinate: a proposal, from a guess and the value of the head, and an admissibility test, from a guess, a child index and the values of the head and of that child.✦ The outer degree of CC is (ℓ+1)d(\ell + 1)d✦, and the circuit modulus pp of CC is the largest prime with (ℓ+1)d+1<p≤2(ℓ+1)d+2(\ell + 1)d + 1 < p \le 2(\ell + 1)d + 2✦.

The price π(g)\pi(g) of a frame with gg guessed bits in CC is π(g)=100(|n|+|d|+|ℓ|+|p|+g+2),\pi(g) = 100\,\bigl(|n| + |d| + |\ell| + |p| + g + 2\bigr),(1)✦ where |x||x| is the bit length of xx.

A coin meter for CC is an assignment κ\kappa of a natural number of coins to each node of CC that pays for every step down from a node vv that is not a base node: κ(h(v))+π(0)≤κ(v)\kappa(h(v)) + \pi(0) \le \kappa(v) for the cheap step to the head child, and κ(ch(v,i))+π(g(v))≤κ(v)\kappa(\mathrm{ch}(v, i)) + \pi(g(v)) \le \kappa(v) for the expensive step to each child with i<ℓi < \ell.✦ We write ℳ(C)\mathcal{M}(C) for the set of coin meters for CC.

As an evaluation circuit, 𝒞D\mathcal{C}_D has width d=c(b+1)d = c(b + 1), the bits of b+1b + 1 controllers, and NN children per node.✦ The base nodes of 𝒞D\mathcal{C}_D are the vertices of epoch 00 in the columns j≤Nj \le N.✦ The head h(v)h(v) of a vertex vv in epoch ee and column jj is ve−1,N+kv_{e-1, N+k}, the history vertex of round kk one epoch earlier, when j≤Nj \le N, and ve,N+r−1v_{e, N+r-1}, one round back in the same epoch, when j=N+rj = N + r with r≥1r \ge 1.✦ Every child of an array vertex is ve−1,jv_{e-1, j}, the same block one epoch earlier; every child of the start vertex is its head; and the child of index ii of a history vertex is ve,iv_{e, i}, the array vertex of block ii in the same epoch.✦ A history vertex guesses g(v)=ckg(v) = ck bits, kk controllers of cc bits, and every other vertex guesses none.✦

The augmented bit at coordinate ii of a word uu of width dd is the binary digit of uu at place ii when i<di < d, the bit 11 when i=di = d, and 00 when i>di > d.✦

The first value of 𝒞D\mathcal{C}_D at a vertex is the initial word Bj0B^0_j in a column j<Nj < N and the initial controller q0q_0 elsewhere✦, and its semantic value is the value of the vertex in the story. Replaying block ii of DD under a transcript ZZ, a number read as digits in base mm, from a word aa gives a sequence of pairs of a word and a verdict: its first term is amod⁡mba \bmod m^b with the verdict true, and each next term comes from the previous one by one replay step at the next digit of ZZ, where a replay step applies the visit map δ\delta to that digit and the current word and sets the verdict according to whether the selection σ\sigma sends that digit to block ii. The local rules of 𝒞D\mathcal{C}_D replay blocks: at an array vertex, the test on child 00 replays block jj from the value of that child for bb visits under the head’s value, and every other child is admitted; at the start vertex, the proposal is the digit of the head’s value at place bb in base mm and every child is admitted; at a history vertex of round rr, the test on child ii replays block ii from the value of that child for rkrk visits under the history whose lowest (r−1)k+1(r - 1)k + 1 digits in base mm are those of the head’s value and whose higher digits are the guess.

The Coins

The easy price of 𝒞D\mathcal{C}_D is the price of a frame with no guessed bits, πeasy=π(0),\pi_{\mathrm{easy}} = \pi(0),(2)✦ and its hard price is the price of a frame that holds the guess of a history vertex, πhard=π(ck).\pi_{\mathrm{hard}} = \pi(ck).(3)✦

The budget β\beta of one epoch is one hard price and k+2k + 2 easy ones, β=πhard+(k+2)πeasy.\beta = \pi_{\mathrm{hard}} + (k + 2)\,\pi_{\mathrm{easy}}.(4)✦

The coins of 𝒞D\mathcal{C}_D are the assignment κ\kappa that gives a vertex vv in epoch ee, column jj and round index rr the number κ(v)={eβif j<N,eβ+πhard+(r+1)πeasyif j≥N.\kappa(v) = \begin{cases} e\beta & \text{if } j < N,\\ e\beta + \pi_{\mathrm{hard}} + (r + 1)\,\pi_{\mathrm{easy}} & \text{if } j \ge N. \end{cases}(5)✦

The Claim

Theorem 1. Let DD be a reference tour, with epoch circuit 𝒞D\mathcal{C}_D, easy price πeasy\pi_{\mathrm{easy}}, budget β\beta and coins κ\kappa. For every vertex vv of 𝒞D\mathcal{C}_D that is not a base node, κ(h(v))+πeasy≤κ(v)andκ(ch(v,i))+π(g(v))≤κ(v) for every i<N;\kappa(h(v)) + \pi_{\mathrm{easy}} \le \kappa(v) \quad\text{and}\quad \kappa(\mathrm{ch}(v, i)) + \pi(g(v)) \le \kappa(v) \ \text{ for every } i < N;(6)✦ moreover, κ∈ℳ(𝒞D),\kappa \in \mathcal{M}(\mathcal{C}_D),(7)✦ and for every vertex vv of 𝒞D\mathcal{C}_D, κ(v)≤Eβ.\kappa(v) \le E\beta.(8)✦

A dependency path from a vertex is a chain of descents, and its weight is the sum of the prices of its descents. In the paper, the result reads: every dependency path from the final history has weight O(E(k+kc+1))=O(Eklog⁡2(T+2))O(E(k + kc + 1)) = O(Ek \log_2(T + 2)), where TT is the time simulated.

What Is Checked

The claim is stated over a reference tour DD and its epoch circuit 𝒞D\mathcal{C}_D, with the base nodes, heads hh, children ch\mathrm{ch} and guessed bits gg of its vertices, over the price π\pi of (1) and the coin meters of an evaluation circuit, and over the coins κ\kappa of (5), built from the prices (2) and (3) and the budget (4).