OctoInformBeta

OpenAI preprint, September 2026 · §2. An evaluator with weighted dependency paths · §2

Lemma 5 [Evaluation along weighted paths]: Every request at vv adds λs(v)¯\lambda\overline{s(v)} to its target register and leaves the other two, within stack budget B(v)B(v), from every pool

Three registers evaluate a good circuit within its meter.

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

In a dependency circuit, the dd-bit value of each node is fixed by the values of a head child and of ℓ\ell further children through an identity over a prime field, in which a few guessed bits are summed out. Lemma 5 is about evaluating such a circuit by recursion in little space. The evaluator holds three registers of field vectors, shared by all levels of the recursion, and answers requests: a request at a node vv asks it to add a multiple of the value of vv, written as a field vector with an extra coordinate 11, to one register and to leave the other two as they were. The question is whether every request is answered whatever the registers hold at the start, and with how large a stack.

Dependency Circuits

A dependency circuit CC of width dd with ℓ\ell children per node has as nodes the numbers below some nn, some of them flagged as base nodes. Each node vv has a head child h(v)h(v), children c(v,i)c(v, i) for i<ℓi < \ell, a number g(v)g(v) of guess bits, a first value f(v)f(v), which is the value prescribed at a base node, and a semantic value s(v)s(v); the guesses at vv are the numbers y<2g(v)y < 2^{g(v)}. The outer degree of CC is D=(ℓ+1)dD = (\ell + 1)d✦, and its modulus is the largest prime pp with D+1<p≤2D+2D + 1 < p \le 2D + 2✦; scalars are elements of the field 𝔽p=ℤ/pℤ\mathbb{F}_p = \mathbb{Z}/p\mathbb{Z}✦. The two local rules of CC, read in 𝔽p\mathbb{F}_p, are the proposal G(v,z,y,H)G(v, z, y, H) at a coordinate zz, a guess yy and a head value HH, and the allowance test T(v,z,y,i,H,A)T(v, z, y, i, H, A), which also takes a child index ii and a child value AA.

A vector is a sequence u=(u0,u1,…)u = (u_0, u_1, \dots) of elements of 𝔽p\mathbb{F}_p. The augmented vector m¯\overline{m} of a number mm has the binary digits of mm, least significant first, in coordinates 00 to d−1d - 1, a 11 in coordinate dd and zeros beyond✦; the augmented value of a node vv is s(v)¯\overline{s(v)}✦. For a dd-bit word HH, the Boolean basis polynomial χH(u)\chi_H(u) is the product over j<dj < d of uju_j where bit jj of HH is 11 and of ud−uju_d - u_j where it is 00.✦ The word extensions of the two rules at vectors hh and aa are EG(v,z,y,h)=∑H<2dχH(h)G(v,z,y,H),ET(v,z,y,i,h,a)=∑H,A<2dχH(h)χA(a)T(v,z,y,i,H,A).E_G(v, z, y, h) = \sum_{H < 2^d} \chi_H(h)\,G(v, z, y, H), \qquad E_T(v, z, y, i, h, a) = \sum_{H, A < 2^d} \chi_H(h)\,\chi_A(a)\,T(v, z, y, i, H, A).(1)

The 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 its first value as semantic value, and every other node vv obeys the identity rule ∑y<2g(v)G(v,z,y,s(h(v)))∏i<ℓT(v,z,y,i,s(h(v)),s(c(v,i)))=s(v)¯z(z≤d).\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(c(v, i))\bigr) = \overline{s(v)}_z \qquad (z \le d).(2)✦

The price of gg guesses is π(g)=100(|n|+|d|+|ℓ|+|p|+g+2)\pi(g) = 100\,(|n| + |d| + |\ell| + |p| + g + 2), where |m||m| is the bit length of a number mm.✦ A meter for CC is an assignment BB of a number of coins to each node that pays for every step down from a node vv that is not a base node, at the price of no guesses to the head child and at the price of the guess bits of vv to each child: B(h(v))+π(0)≤B(v),B(c(v,i))+π(g(v))≤B(v)(i<ℓ).B(h(v)) + \pi(0) \le B(v), \qquad B(c(v, i)) + \pi(g(v)) \le B(v) \quad (i < \ell).(3)✦

Flow Machines

A flow machine consists of a set of states, whose elements are written γ\gamma, and a set of frames, whose elements are written φ\varphi, each with a code, a number written #γ\#\gamma or #φ\#\varphi, together with an action, which takes a state and a frame to a new state and a move.✦ A move finishes, written 𝖿𝗂𝗇\mathsf{fin}, continues with a frame φ′\varphi', written 𝖼𝗈𝗇𝗍φ′\mathsf{cont}\,\varphi', or calls a child frame ψ\psi to be followed by a return frame φ′\varphi', written 𝖼𝖺𝗅𝗅(ψ,φ′)\mathsf{call}(\psi, \varphi').✦ The fee of a frame φ\varphi is fee(φ)=2|#φ|+1.\mathrm{fee}(\varphi) = 2\,|\#\varphi| + 1.(4)✦

Execution within a budget BB, which bounds the total fee of the return frames suspended at one time, is defined inductively. The machine started on a state γ\gamma in a frame φ\varphi executes within BB to a state γ′\gamma', written (γ,φ)⇓Bγ′(\gamma, \varphi) \Downarrow_B \gamma', when its action at (γ,φ)(\gamma, \varphi) finishes with state γ′\gamma'; when the action continues with a state γ1\gamma_1 and a frame φ′\varphi' such that (γ1,φ′)⇓Bγ′(\gamma_1, \varphi') \Downarrow_B \gamma'; or when the action calls ψ\psi with return frame φ′\varphi' from a state γ1\gamma_1, and (γ1,ψ)⇓Aγ2(\gamma_1, \psi) \Downarrow_A \gamma_2 and (γ2,φ′)⇓Bγ′(\gamma_2, \varphi') \Downarrow_B \gamma' for a budget AA with fee(φ′)+A≤B\mathrm{fee}(\varphi') + A \le B.✦

The Evaluator

Over a prime pp, a pool is an assignment of a vector to each of three registers, numbered modulo 33: R:{0,1,2}→𝔽pℕ,j↦Rj.R \colon \{0, 1, 2\} \to \mathbb{F}_p^{\mathbb{N}}, \qquad j \mapsto R_j.(5)✦ For a register tt and a vector uu, R+tuR +_t u is the pool with uu added to register tt and the other two unchanged✦, and eze_z is the unit vector with 11 in coordinate zz. A request at a node vv of CC is a triple x=(v,λ,t)x = (v, \lambda, t) of vv, a scalar λ\lambda and a target register tt✦; its head register is t+1t + 1✦, its array register is t+2t + 2✦, its reverse is (v,−λ,t)(v, -\lambda, t)✦, and its result on a pool RR is the pool x(R)=R+tλs(v)¯.x(R) = R +_t \lambda\,\overline{s(v)}.(6)✦ For a request x=(v,λ,t)x = (v, \lambda, t) and a scale ss, the request on the head child of xx with scale ss is the request at the head child h(v)h(v) of vv with scalar ss, read in 𝔽p\mathbb{F}_p, and target the head register t+1t + 1 of xx. For a request x=(v,λ,t)x = (v, \lambda, t), an index i<ℓi < \ell and a scale rr, the request on child array ii of xx with scale rr is the request at the child c(v,i)c(v, i) of vv with scalar rr, read in 𝔽p\mathbb{F}_p, and target the array register t+2t + 2 of xx.

A frame of the evaluator of CC consists of a request xx, a program counter among 𝖾𝗇𝗍𝗋𝗒\mathsf{entry}, 𝗈𝗎𝗍𝖾𝗋\mathsf{outer}, 𝖼𝗈𝗈𝗋𝖽\mathsf{coord}, 𝗀𝗎𝖾𝗌𝗌\mathsf{guess}, 𝖿𝖺𝖼𝗍𝗈𝗋\mathsf{factor}, 𝗌𝖺𝗆𝗉𝗅𝖾\mathsf{sample} and 𝖼𝗁𝖾𝖼𝗄\mathsf{check}, counters σ≤p\sigma \le p, z≤d+1z \le d + 1, y≤2dy \le 2^d, i≤ℓi \le \ell and ρ≤p\rho \le p, and two scalars uu and ww.✦ The entry frame 𝖾𝗇𝗍𝗋𝗒(x)\mathsf{entry}(x) of xx has all counters and scalars zero✦; for the other program counters, 𝗈𝗎𝗍𝖾𝗋(σ)\mathsf{outer}(\sigma), 𝖼𝗈𝗈𝗋𝖽(σ,z)\mathsf{coord}(\sigma, z), 𝗀𝗎𝖾𝗌𝗌(σ,z,y)\mathsf{guess}(\sigma, z, y), 𝖿𝖺𝖼𝗍𝗈𝗋(σ,z,y,i;u)\mathsf{factor}(\sigma, z, y, i; u), 𝗌𝖺𝗆𝗉𝗅𝖾(σ,z,y,i,ρ;u,w)\mathsf{sample}(\sigma, z, y, i, \rho; u, w) and 𝖼𝗁𝖾𝖼𝗄(σ,z,y,i,ρ;u,w)\mathsf{check}(\sigma, z, y, i, \rho; u, w) denote the frame with the request of the frame at which the step is taken, the entries shown and zeros elsewhere. With the interpolation weight ωk(σ)=−σp−1−k\omega_k(\sigma) = -\sigma^{p - 1 - k} of degree kk, the step of the evaluator on a pool RR, at a frame with request x=(v,λ,t)x = (v, \lambda, t), is given by the program counter: 𝖾𝗇𝗍𝗋𝗒(x)↦(R+tλf(v)¯,𝖿𝗂𝗇)if v is a base node,↦(R,𝖼𝗈𝗇𝗍𝗈𝗎𝗍𝖾𝗋(0))otherwise;𝗈𝗎𝗍𝖾𝗋(σ)↦(R,𝖼𝖺𝗅𝗅(𝖾𝗇𝗍𝗋𝗒(h(v),σ,t+1),𝖼𝗈𝗈𝗋𝖽(σ,0)))if σ<p,↦(R,𝖿𝗂𝗇)otherwise;𝖼𝗈𝗈𝗋𝖽(σ,z)↦(R,𝖼𝗈𝗇𝗍𝗀𝗎𝖾𝗌𝗌(σ,z,0))if z≤d,↦(R,𝖼𝖺𝗅𝗅(𝖾𝗇𝗍𝗋𝗒(h(v),−σ,t+1),𝗈𝗎𝗍𝖾𝗋(σ+1)))otherwise;𝗀𝗎𝖾𝗌𝗌(σ,z,y)↦(R,𝖼𝗈𝗇𝗍𝖿𝖺𝖼𝗍𝗈𝗋(σ,z,y,0;EG(v,z,y,Rt+1)))if y<2g(v),↦(R,𝖼𝗈𝗇𝗍𝖼𝗈𝗈𝗋𝖽(σ,z+1))otherwise;𝖿𝖺𝖼𝗍𝗈𝗋(σ,z,y,i;u)↦(R,𝖼𝗈𝗇𝗍𝗌𝖺𝗆𝗉𝗅𝖾(σ,z,y,i,0;u,0))if i<ℓ,↦(R+tλωD(σ)uez,𝖼𝗈𝗇𝗍𝗀𝗎𝖾𝗌𝗌(σ,z,y+1))otherwise;𝗌𝖺𝗆𝗉𝗅𝖾(σ,z,y,i,ρ;u,w)↦(R,𝖼𝖺𝗅𝗅(𝖾𝗇𝗍𝗋𝗒(c(v,i),ρ,t+2),𝖼𝗁𝖾𝖼𝗄(σ,z,y,i,ρ;u,w)))if ρ<p,↦(R,𝖼𝗈𝗇𝗍𝖿𝖺𝖼𝗍𝗈𝗋(σ,z,y,i+1;uw))otherwise;𝖼𝗁𝖾𝖼𝗄(σ,z,y,i,ρ;u,w)↦(R,𝖼𝖺𝗅𝗅(𝖾𝗇𝗍𝗋𝗒(c(v,i),−ρ,t+2),𝗌𝖺𝗆𝗉𝗅𝖾(σ,z,y,i,ρ+1;u,w′))),\begin{aligned} \mathsf{entry}(x) &\mapsto \bigl(R +_t \lambda\,\overline{f(v)},\ \mathsf{fin}\bigr) && \text{if $v$ is a base node,}\\ &\mapsto \bigl(R,\ \mathsf{cont}\,\mathsf{outer}(0)\bigr) && \text{otherwise;}\\ \mathsf{outer}(\sigma) &\mapsto \bigl(R,\ \mathsf{call}(\mathsf{entry}(h(v), \sigma, t + 1),\ \mathsf{coord}(\sigma, 0))\bigr) && \text{if } \sigma < p,\\ &\mapsto (R,\ \mathsf{fin}) && \text{otherwise;}\\ \mathsf{coord}(\sigma, z) &\mapsto \bigl(R,\ \mathsf{cont}\,\mathsf{guess}(\sigma, z, 0)\bigr) && \text{if } z \le d,\\ &\mapsto \bigl(R,\ \mathsf{call}(\mathsf{entry}(h(v), -\sigma, t + 1),\ \mathsf{outer}(\sigma + 1))\bigr) && \text{otherwise;}\\ \mathsf{guess}(\sigma, z, y) &\mapsto \bigl(R,\ \mathsf{cont}\,\mathsf{factor}(\sigma, z, y, 0; E_G(v, z, y, R_{t+1}))\bigr) && \text{if } y < 2^{g(v)},\\ &\mapsto \bigl(R,\ \mathsf{cont}\,\mathsf{coord}(\sigma, z + 1)\bigr) && \text{otherwise;}\\ \mathsf{factor}(\sigma, z, y, i; u) &\mapsto \bigl(R,\ \mathsf{cont}\, \mathsf{sample}(\sigma, z, y, i, 0; u, 0)\bigr) && \text{if } i < \ell,\\ &\mapsto \bigl(R +_t \lambda\,\omega_D(\sigma)\,u\,e_z,\ \mathsf{cont}\, \mathsf{guess}(\sigma, z, y + 1)\bigr) && \text{otherwise;}\\ \mathsf{sample}(\sigma, z, y, i, \rho; u, w) &\mapsto \bigl(R,\ \mathsf{call}( \mathsf{entry}(c(v, i), \rho, t + 2),\ \mathsf{check}(\sigma, z, y, i, \rho; u, w))\bigr) && \text{if } \rho < p,\\ &\mapsto \bigl(R,\ \mathsf{cont}\,\mathsf{factor}(\sigma, z, y, i + 1; uw)\bigr) && \text{otherwise;}\\ \mathsf{check}(\sigma, z, y, i, \rho; u, w) &\mapsto \bigl(R,\ \mathsf{call}( \mathsf{entry}(c(v, i), -\rho, t + 2),\ \mathsf{sample}(\sigma, z, y, i, \rho + 1; u, w'))\bigr), \end{aligned}(7)✦ where w′=w+ωd(ρ)ET(v,z,y,i,Rt+1,Rt+2)w' = w + \omega_d(\rho)\,E_T(v, z, y, i, R_{t+1}, R_{t+2}).

The evaluator of CC is the flow machine whose states are the pools over the modulus pp of CC, whose frames are those above and whose action is the step (7).✦ The pairing ⟨a,b⟩\langle a, b\rangle of numbers aa and bb is the number whose binary digits, least significant first, are those of aa, each preceded by a 00, then a 11, then those of bb; longer tuples are nested to the right.✦ The codes of the evaluator use it: a pool has the code #R=⟨[R0],[R1],[R2]⟩\#R = \langle [R_0], [R_1], [R_2]\rangle✦, with [u]=∑k≤dukpk[u] = \sum_{k \le d} u_k\,p^k the base-pp packing of the first d+1d + 1 coordinates of a vector, and a frame has the code #φ=⟨⟨t,v,λ⟩,κ,σ,z,y,i,ρ,u,w⟩\#\varphi = \langle \langle t, v, \lambda\rangle, \kappa, \sigma, z, y, i, \rho, u, w\rangle✦, with κ\kappa the number of its program counter, from 00 for 𝖾𝗇𝗍𝗋𝗒\mathsf{entry} to 66 for 𝖼𝗁𝖾𝖼𝗄\mathsf{check} in the order listed✦, and scalars read as numbers below pp.

A node vv of CC is solved for an assignment BB of coins when every request xx at vv, started in its entry frame on any pool RR, executes within the budget B(v)B(v) to its result x(R)x(R).✦

Space Bounds

Fix an index set II, public inputs xix_i, words over an alphabet XX, and space bounds SiS_i. A family bb of numbers is computable from a family aa in space SS, written a→Sba \to_S b, when one fixed stack machine, with finitely many states, read-only heads and stacks of bits, at every index ii reads xix_i as public input and turns a stack holding the bits of aia_i into one holding the bits of bib_i, least significant first, within c(Si+1)c\,(S_i + 1) bits for a constant cc independent of ii.✦ A family ff is linear in S+1S + 1 when fi≤c(Si+1)f_i \le c\,(S_i + 1) for one constant cc and every ii✦, and it fits in SS when its bit lengths |fi||f_i| are linear in S+1S + 1✦. For a map r:U→Ir \colon U \to I, computation along rr is computation in which the instance j∈Uj \in U has public input xr(j)x_{r(j)} and space bound Sr(j)S_{r(j)}.✦

A family of dependency circuits CiC_i with descriptions cpi\mathrm{cp}_i, numbers that describe the circuits CiC_i, is ready for SS when its widths did_i and its numbers ℓi\ell_i of children per node are computable from cp\mathrm{cp} in space SS, its numbers of nodes and the numbers pidi+1p_i^{d_i + 1} of contents of a register fit in SS, and its local structure is computable along every map r:U→Ir \colon U \to I: whenever the descriptions and nodes of the circuits are computable in space SS, so are the base flag, the number of guess bits, the head child and the first value of these nodes, their children at computable child indices, and their proposals and allowance tests at computable arguments in range.✦

A family of flow machines MiM_i is uniform in space SS for descriptions cpi\mathrm{cp}_i when its actions are computable in space SS over the family of all triples (i,γ,φ)(i, \gamma, \varphi) of an index, a state and a frame of MiM_i, with public input xix_i and bound SiS_i: ⟨cpi,#γ,#φ⟩→S⟨#γ′,k,a1,a2⟩\langle \mathrm{cp}_i, \#\gamma, \#\varphi\rangle \to_S \langle \#\gamma', k, a_1, a_2\rangle, where the action at (γ,φ)(\gamma, \varphi) yields the state γ′\gamma' and a move with tag kk, 00 to finish, 11 to continue and 22 to call, and a1a_1, a2a_2 are the codes of the frames the move names, in order, with 00 in place of a missing one.✦

The Claim

Theorem 1. Let CC be a good dependency circuit with a meter BB. Then every node vv of CC is solved for BB: for every scalar λ\lambda, every target register tt and every pool RR, the evaluator of CC satisfies (R,𝖾𝗇𝗍𝗋𝗒(v,λ,t))⇓B(v)R+tλs(v)¯.\bigl(R, \mathsf{entry}(v, \lambda, t)\bigr) \Downarrow_{B(v)} R +_t \lambda\,\overline{s(v)}.(8)✦ Let further CiC_i, for i∈Ii \in I, be good dependency circuits forming a family ready for SS with descriptions cpi\mathrm{cp}_i, let BiB_i be a meter for CiC_i, and let viv_i be nodes of CiC_i with cp→Sv\mathrm{cp} \to_S v whose budgets Bi(vi)B_i(v_i) are linear in S+1S + 1. Then the semantic values of these nodes are computable in space SS: cp→S(si(vi))i∈I.\mathrm{cp} \to_S \bigl(s_i(v_i)\bigr)_{i \in I}.(9)✦

In the paper, the result reads: under these assumptions the augmented value of vv is computable in O((d+W(v)+1)polylogT)O\bigl((d + W(v) + 1)\,\mathrm{polylog}\,T\bigr) work space, and more strongly a pool of exactly max⁡(3,r+1)\max(3, r + 1) registers in 𝔽d+1\mathbb{F}^{d+1} supports the request adding λs(v)¯\lambda\overline{s(v)} to register tt and restoring every other register, from every initial assignment of the pool, within that space including pool and stack, with W(v)W(v) the paper’s weight of vv, rr a parameter of the paper, 𝔽\mathbb{F} its field and TT the simulated time.

What Is Checked

The claim is stated over good dependency circuits with their meters, the pools (5), requests and their results (6), the evaluator with its step (7), and execution within a budget charged by the fee (4); its second part adds families of circuits ready for a space bound SS and computation in space SS.

For a family of flow machines MiM_i uniform in space SS for descriptions cpi\mathrm{cp}_i, and executions (γi,φi)⇓Biγi′(\gamma_i, \varphi_i) \Downarrow_{B_i} \gamma_i' within budgets BiB_i linear in S+1S + 1, the final states are computable in space SS from the starts: (⟨cpi,#γi,#φi⟩)i∈I→S(#γi′)i∈I.\bigl(\langle \mathrm{cp}_i, \#\gamma_i, \#\varphi_i\rangle\bigr)_{i \in I} \to_S \bigl(\#\gamma_i'\bigr)_{i \in I}.(10)✦

The guess sum of a node vv at a vector hh is the vector Γv(h)\Gamma_v(h) whose coordinates z≤dz \le d are Γv(h)z=∑y<2g(v)EG(v,z,y,h)∏i<ℓET(v,z,y,i,h,s(c(v,i))¯)\Gamma_v(h)_z = \sum_{y < 2^{g(v)}} E_G(v, z, y, h) \prod_{i < \ell} E_T\bigl(v, z, y, i, h, \overline{s(c(v, i))}\bigr)(11)✦ and whose further coordinates are zero. For a request (v,λ,t)(v, \lambda, t) at a node of a good circuit that is not a base node, and every pool RR, the weighted sum of guess sums along the line through the head register in the direction of the augmented value of the head child is the change the request asks for: ∑σ∈𝔽pλωD(σ)Γv(Rt+1+σs(h(v))¯)=λs(v)¯.\sum_{\sigma \in \mathbb{F}_p} \lambda\,\omega_D(\sigma)\, \Gamma_v\bigl(R_{t+1} + \sigma\,\overline{s(h(v))}\bigr) = \lambda\,\overline{s(v)}.(12)✦

A node with solved children, for a meter BB, is a node vv that is not a base node and whose head child and children c(v,i)c(v, i), i<ℓi < \ell, are solved for BB.✦ At such a node of a good circuit, every request xx is answered within the budget of the node from every pool RR: (R,𝖾𝗇𝗍𝗋𝗒(x))⇓B(v)x(R).\bigl(R, \mathsf{entry}(x)\bigr) \Downarrow_{B(v)} x(R).(13)✦