OctoInformBeta

OpenAI preprint, September 2026 · §2. The transition model and resource parameters · §2

Lemma 2.1 [Configuration reduction]: A forward substochastic matrix with out-degree ≤2\le 2 and bounded in-degree, whose potential at the start node is the acceptance probability when space is logarithmic

Configuration graphs of clocked machines form a correct first stage.

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 randomized machine that runs for τ\tau steps reads one fair coin per step, and its acceptance probability on an input is an average over 2τ2^\tau coin strings. The small-space way to reach it is the configuration graph. Its nodes are configurations stamped with the time, each node has one edge of weight 12\tfrac12 for each coin value, and the acceptance probability is the value at the start node of the potential that collects 11 at every accepting configuration of time τ\tau. Under a polynomial clock and a logarithmic space bound the graph has polynomially many nodes, and the time stamp makes every edge go forward.

The library builds this graph for its own machine model and states that it, with its reward vector and potential, is a correct first stage of the probability hierarchy, whose stages are forward weighted graphs carrying a value vector.

Sources and Their Runs

An input is a word x∈{0,1}nx \in \{0,1\}^n, read on a tape with cells 0,…,n+10, \dots, n+1 that holds a left endmarker in cell 00, the bits of xx in cells 11 to nn and a right endmarker in cell n+1n+1.

A probabilistic machine MM with states 0,…,q0, \dots, q, with hh input heads and ww binary work tapes, consists of an initial state, an output map marking some states as accepting and some as rejecting, and a transition function.✦ From the state, the symbols under the input heads, the bits under the work heads and a coin b∈{0,1}b \in \{0,1\}, the transition function gives the next state, a bit to write on each work tape and a move left, stay or right for each head.✦

A configuration of MM on an input of length nn is a state together with a cell in {0,…,n+1}\{0, \dots, n+1\} for each input head, a position in ℤ\mathbb{Z} for each work head and contents ℤ→{0,1}\mathbb{Z} \to \{0,1\} for each work tape.✦ On a coin sequence β=(β0,β1,…)\beta = (\beta_0, \beta_1, \dots), the run of MM on xx starts from the initial configuration and makes its move at step ss with coin βs\beta_s.✦ The acceptance probability of MM on xx at time tt is the share of coin strings of length tt that leave the run in an accepting state: acc⁡M(x,t)=2−t#{β∈{0,1}t:the run with coins β is in an accepting state after t steps}.\operatorname{acc}_M(x,t) = 2^{-t}\,\#\bigl\{\beta \in \{0,1\}^t : \text{the run with coins $\beta$ is in an accepting state after $t$ steps}\bigr\}.(1)✦ The space used through time tt, written space⁡M(x,β,t)\operatorname{space}_M(x,\beta,t), is the sum over the work tapes of the number of distinct cells the tape’s head occupies at steps 0,…,t0, \dots, t of that run.✦

A source is a machine MM with three constants csc_s, cc, kk.✦ The clock of MM on an input of length nn is τ=c(n+2)k\tau = c(n+2)^k.✦ A source MM satisfies the space bound when for every input xx of length nn, every coin sequence β\beta and every time tt, space⁡M(x,β,t)≤cs⌈log⁡2(n+2)⌉.\operatorname{space}_M(x,\beta,t) \le c_s \lceil \log_2(n+2) \rceil.(2)✦

The Configuration Graph

Fix a source MM and an input xx of length nn with clock τ\tau. A record of MM is a tuple A=(t,s,i1,…,ih,ℓ1,…,ℓw,r1,…,rw)A = (t, s, i_1, \dots, i_h, \ell_1, \dots, \ell_w, r_1, \dots, r_w) of natural numbers: a time stamp tt, a state ss, a cell iji_j for each input head, and for each work tape the bits left of the head and the bits from the head rightward, as binary numbers ℓj\ell_j and rjr_j whose lowest digit is the cell nearest the head.✦

The step σb(A)\sigma_b(A) of a record AA with coin bb is the record after one move of MM on xx.✦ It raises the time stamp by one and applies the transition function to the state ss (read modulo q+1q+1), the input symbols in the cells iji_j, the lowest digits of the rjr_j and the coin bb; writing replaces the lowest digit of rjr_j, a work head move shifts one digit between ℓj\ell_j and rjr_j✦, and the input heads stay within the cells 0,…,n+10, \dots, n+1✦. In a state with an output, the step changes only the time stamp. The start record A0A_0 has time stamp 00, the initial state, every input head in cell 00 and every work tape blank.✦

The radix mm of the input xx is the number m=q+2+c(n+2)k+(n+2)+2(2(n+2))2cs.m = q + 2 + c(n+2)^k + (n+2) + 2\bigl(2(n+2)\bigr)^{2c_s}.(3) A record AA is legal for xx when its state is at most qq and each of its entries is below mm.✦ The node ⟨A⟩\langle A \rangle of a record AA is the natural number whose base-mm digits are tt, ss, the iji_j, the ℓj\ell_j and the rjr_j, the time stamp leading✦; every natural number uu is read back as a record through its base-mm digits in the same order✦. The node set of xx is Vx={0,1,…,m2w+h+2−1}V_x = \{0, 1, \dots, m^{2w+h+2}-1\}✦, of size polynomial in nn, and its start node is u0=⟨A0⟩u_0 = \langle A_0 \rangle✦.

For a natural number uu with record AA and a coin bb, the bb-successor of uu is νb(u)=⟨σb(A)⟩\nu_b(u) = \langle \sigma_b(A) \rangle when AA is legal with time stamp below τ\tau and σb(A)\sigma_b(A) is legal; otherwise uu has no bb-successor.✦ For a vector ff on the natural numbers, f(νb(u))f(\nu_b(u)) stands for 00 when uu has no bb-successor.✦

The transition matrix SS of xx is the matrix indexed by pairs of natural numbers with S(u,y)=12#{b∈{0,1}:νb(u)=y}.S(u,y) = \tfrac12\,\#\{b \in \{0,1\} : \nu_b(u) = y\}.(4)✦ The reward vector ee of xx has e(u)=1e(u) = 1 when the record of uu is legal, has time stamp τ\tau and has an accepting state, and e(u)=0e(u) = 0 otherwise.✦ The potentials of xx are the vectors pjp_j with p0=ep_0 = e and pj+1(u)=e(u)+12(pj(ν0(u))+pj(ν1(u))),p_{j+1}(u) = e(u) + \tfrac12\bigl(p_j(\nu_0(u)) + p_j(\nu_1(u))\bigr),(5)✦ and the potential of xx is p=pτp = p_\tau✦.

The hint κ(A,b)\kappa(A,b) of a record AA and a coin bb is the tuple κ(A,b)=(b,smod⁡(q+1),(i1mod⁡3,…,ihmod⁡3),(r1mod⁡2,…,rwmod⁡2)),\kappa(A,b) = \bigl(b,\ s \bmod (q+1),\ (i_1 \bmod 3, \dots, i_h \bmod 3),\ (r_1 \bmod 2, \dots, r_w \bmod 2)\bigr),(6)✦ and there are 2(q+1)3h2w2(q+1)3^h2^w possible hints.

Prizes of the Probability Hierarchy

A stage 𝒫\mathcal{P} of the probability hierarchy consists of a choice of the numerical constants that parametrize the hierarchy, a level i∈ℕi \in \mathbb{N}, a finite domain D⊂ℕD \subset \mathbb{N} and a real matrix CC indexed by pairs of natural numbers; its rate is f=2−4if = 2^{-4i}✦. A matrix CC is a step matrix on DD at rate ff when, for all natural numbers uu and yy, 0≤C(u,y)≤f,∑y′∈DC(u,y′)≤1,C(u,y)>0⟹u,y∈D and u<y.0 \le C(u,y) \le f, \qquad \sum_{y' \in D} C(u,y') \le 1, \qquad C(u,y) > 0 \implies u, y \in D \text{ and } u < y.(7)✦

A prize (𝒫,W,v)(\mathcal{P}, W, v) is a stage 𝒫\mathcal{P} with a weight vector WW and a value vector vv, both real vectors on the natural numbers.✦ A prize (𝒫,W,v)(\mathcal{P}, W, v) whose stage has domain DD, matrix CC and rate ff is correct when CC is a step matrix on DD at rate ff, W≥0W \ge 0, 0≤v(u)≤10 \le v(u) \le 1 for every uu, and v(u)=W(u)+∑y∈DC(u,y)v(y)for every u.v(u) = W(u) + \sum_{y \in D} C(u,y)\,v(y) \qquad \text{for every } u.(8)✦

The prize of xx is ℋx=(𝒫x,e,p)\mathcal{H}_x = (\mathcal{P}_x, e, p), where 𝒫x\mathcal{P}_x is the stage at level 00, of rate 11, with domain VxV_x and matrix SS, for a given choice of the hierarchy’s constants.✦

The Claim

Theorem 1 (Configuration reduction). Let MM be a source with q+1q+1 states, hh input heads, ww work tapes and constants csc_s, cc, kk, and let xx be an input of length nn with clock τ\tau. For all natural numbers uu and yy, the transition matrix of xx satisfies 0≤S(u,y),0 \le S(u,y),(9)✦ S(u,y)≤1,S(u,y) \le 1,(10)✦ S(u,y)>0⇔ν0(u)=y or ν1(u)=y,S(u,y) > 0 \iff \nu_0(u) = y \text{ or } \nu_1(u) = y,(11)✦ ∑y′∈VxS(u,y′)≤1;\sum_{y' \in V_x} S(u,y') \le 1;(12)✦ if y=νb(u)y = \nu_b(u) for a coin bb, then u<y;u < y;(13)✦ and #{y′∈Vx:S(u,y′)>0}≤2,\#\{y' \in V_x : S(u,y') > 0\} \le 2,(14)✦ #{u′∈Vx:S(u′,y)>0}≤2(q+1)3h2w.\#\{u' \in V_x : S(u',y) > 0\} \le 2(q+1)3^h2^w.(15)✦ For records AA and A′A' with states at most qq and coins bb and b′b' such that σb(A)=σb′(A′)\sigma_b(A) = \sigma_{b'}(A') and κ(A,b)=κ(A′,b′)\kappa(A,b) = \kappa(A',b'), A=A′.A = A'.(16)✦ For every natural number uu, p(u)=e(u)+12(p(ν0(u))+p(ν1(u))),p(u) = e(u) + \tfrac12\bigl(p(\nu_0(u)) + p(\nu_1(u))\bigr),(17)✦ and for every j∈ℕj \in \mathbb{N}, 0≤pj(u)≤1.0 \le p_j(u) \le 1.(18)✦ For every choice of the hierarchy’s constants, ℋx=(𝒫x,e,p) is a correct prize.\mathcal{H}_x = (\mathcal{P}_x, e, p) \text{ is a correct prize}.(19)✦ If MM satisfies the space bound (2), then u0∈Vx,u_0 \in V_x,(20)✦ p(u0)=acc⁡M(x,τ),p(u_0) = \operatorname{acc}_M(x,\tau),(21)✦ and the value vector vv of ℋx\mathcal{H}_x satisfies v(u0)=acc⁡M(x,τ).v(u_0) = \operatorname{acc}_M(x,\tau).(22)✦

In the paper, the result reads: for a polynomial-time randomized machine using O(log⁡(n+2))O(\log(n+2)) work space and an input of length nn, one can specify, uniformly in logarithmic space, a polynomial-size vertex set VxV_x, a strictly forward substochastic matrix SS, a vector e∈{0,1}Vxe \in \{0,1\}^{V_x} and a start vertex u0u_0 such that the incoming and outgoing port degrees of SS are bounded by constants depending only on the machine, port validity, edge weights and pairing are computable in logarithmic space, the vector (I−S)−1e(I-S)^{-1}e is well-defined and lies in [0,1]Vx[0,1]^{V_x}, and its value at u0u_0 is the acceptance probability, so that for a computation in randomized logarithmic space (RL) that value is 00 or at least 12\tfrac12.

In the box, the potential pp after τ\tau steps stands where the paper has (I−S)−1e(I-S)^{-1}e.

What Is Checked

The claim is stated over the library’s probabilistic machines with their runs, acceptance probability and space used, over the records of a source with their steps, hints and base-mm numbering into the node set VxV_x, over the transition matrix SS, the reward vector ee and the potentials pjp_j built on them, and over the stages and prizes of the probability hierarchy with their correctness condition.