OctoInformBeta

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

§2 (setting): word graphs, factored rules and weighted paths: dd-bit words at the vertices, a sum-product rule over 𝔽p\mathbb{F}_p for good circuits, coin prices on edges and computability in space SS

Dependency circuits with factored rules and a coin 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

To simulate time-bounded computation in less space, one cuts the tape into blocks and evaluates the resulting computation graph: each vertex stands for a word of dd bits, such as the contents of one block at one moment, and the word at a vertex is fixed by the words at a few vertices below it. An evaluator finds the word at a vertex by recursion, recomputing the words below it instead of storing them.

The circuits of this item factor the rule at a vertex through arithmetic in a prime field. One child, the head, is singled out. The rule at a vertex is a sum over guesses of a selector on the head’s word times tests on the head and one child each. The cost of the recursion is measured by a potential, the meter: coins on the vertices, at least a fixed price more at a vertex than at its head, and at least a price growing with the guess length gg more than at each child. A family of circuits, one for each input, is ready when its parts are computable in a space bound SS.

Words as Vectors Over a Prime Field

For a prime pp, 𝔽p\mathbb{F}_p is the field of integers modulo pp✦, and a coordinate vector over 𝔽p\mathbb{F}_p is a sequence h=(h0,h1,h2,…)h = (h_0, h_1, h_2, \dots) of elements of 𝔽p\mathbb{F}_p✦. The prime modulus chosen for a natural number DD is the largest prime pp with D+1<p<2D+3D + 1 < p < 2D + 3.✦

A dd-bit word is a natural number w<2dw < 2^d, read through its binary digits wi=⌊w/2i⌋mod⁡2w_i = \lfloor w / 2^i \rfloor \bmod 2, least significant first. The bit length ℓ(m)\ell(m) of a natural number mm is the number of its binary digits, with ℓ(0)=0\ell(0) = 0. The augmentation of a natural number ww at width dd is the coordinate vector augd(w)\mathrm{aug}_d(w) given by augd(w)i=wi(i<d),augd(w)d=1,augd(w)i=0(i>d).\mathrm{aug}_d(w)_i = w_i \ \ (i < d), \qquad \mathrm{aug}_d(w)_d = 1, \qquad \mathrm{aug}_d(w)_i = 0 \ \ (i > d).(1)✦

The Boolean basis polynomial of a dd-bit word ww is the function on coordinate vectors χw(h)=∏i<d,wi=1hi∏i<d,wi=0(hd−hi),\chi_w(h) = \prod_{i < d,\ w_i = 1} h_i \prod_{i < d,\ w_i = 0} (h_d - h_i),(2)✦ and the word extension of a table ff of elements of 𝔽p\mathbb{F}_p indexed by dd-bit words is the function on coordinate vectors ℰf(h)=∑w<2dχw(h)f(w).\mathcal{E} f(h) = \sum_{w < 2^d} \chi_w(h)\, f(w).(3)✦ The pair extension of a table ff indexed by pairs of dd-bit words is the function ℰ2f\mathcal{E}_2 f on pairs of coordinate vectors that extends one argument at a time: ℰ2f(h,h′)=∑w<2dχw(h)∑w′<2dχw′(h′)f(w,w′).\mathcal{E}_2 f(h, h') = \sum_{w < 2^d} \chi_w(h) \sum_{w' < 2^d} \chi_{w'}(h')\, f(w, w').(4)

Computing in Space SS

A stack machine is a finite-state machine with read-only heads on its inputs whose work storage is a finite set of stacks of bits.✦ For a family xx of words over an alphabet and families SS, aa, bb of natural numbers, all indexed by a set II, bb is computable from aa in space SS on public inputs xx, written Compx,S(a,b)\mathrm{Comp}_{x,S}(a, b), when one fixed stack machine, at every index j∈Ij \in I, reads x(j)x(j) as its public input and turns a stack holding the binary digits of a(j)a(j) into a stack holding those of b(j)b(j), least significant first, within c(S(j)+1)c\,(S(j) + 1) work bits, for a constant cc independent of jj.✦

For a map ρ:U→I\rho\colon U \to I, computability after the change of index ρ\rho is Compx∘ρ,S∘ρ\mathrm{Comp}_{x \circ \rho,\, S \circ \rho}: at each u∈Uu \in U the public input is x(ρ(u))x(\rho(u)) and the space bound is S(ρ(u))S(\rho(u)).✦

The Definition

Definition 1. A dependency circuit CC of width dd and fan-in rr on the vertices 𝒱={0,…,n−1}\mathcal{V} = \{0, \dots, n-1\} consists of a set of base vertices and, at every vertex VV, a head H(V)H(V), children A0(V),A1(V),…A_0(V), A_1(V), \dots, a guess length g(V)g(V), a base word β(V)\beta(V), a semantic value v(V)v(V), selector values GV,z,y(w)G_{V,z,y}(w) and test values PV,z,y,i(w,w′)P_{V,z,y,i}(w, w'), for all natural numbers zz, yy, ii, ww, w′w': H(V),Ai(V)∈𝒱,g(V),β(V),v(V),GV,z,y(w),PV,z,y,i(w,w′)∈ℕ.H(V),\ A_i(V) \in \mathcal{V}, \qquad g(V),\ \beta(V),\ v(V),\ G_{V,z,y}(w),\ P_{V,z,y,i}(w, w') \in \mathbb{N}.(5)✦ The field of CC is 𝔽p\mathbb{F}_p for the prime pp chosen for the outer degree (r+1)d(r+1)d of CC, and the selector and test values of CC are read in 𝔽p\mathbb{F}_p. The augmented value of a vertex VV is v(V)¯=augd(v(V)),\overline{v(V)} = \mathrm{aug}_d\bigl(v(V)\bigr),(6)✦ and the word extension of the selector and the pair extension of the tests are, at coordinate vectors hh and h′h' over 𝔽p\mathbb{F}_p, EG(V,z,y;h)=ℰGV,z,y(h),E_G(V, z, y; h) = \mathcal{E} G_{V,z,y}(h),(7)✦ ET(V,z,y,i;h,h′)=ℰ2PV,z,y,i(h,h′).E_T(V, z, y, i; h, h') = \mathcal{E}_2 P_{V,z,y,i}(h, h').(8)✦

The circuit CC is good when every semantic value is a dd-bit word, every guess length is at most dd, every base vertex VV has v(V)=β(V)v(V) = \beta(V), and every vertex VV that is not a base vertex obeys the factored rule at each coordinate z≤dz \le d, in 𝔽p\mathbb{F}_p: v(V)¯z=∑y<2g(V)GV,z,y(v(H(V)))∏i<rPV,z,y,i(v(H(V)),v(Ai(V))).\overline{v(V)}_z = \sum_{y < 2^{g(V)}} G_{V,z,y}\bigl(v(H(V))\bigr) \prod_{i < r} P_{V,z,y,i}\bigl(v(H(V)),\, v(A_i(V))\bigr).(9)✦

The price of a guess length gg is π(g)=100(s+g+1),s=1+ℓ(n)+ℓ(d)+ℓ(r)+ℓ(p),\pi(g) = 100\,(s + g + 1), \qquad s = 1 + \ell(n) + \ell(d) + \ell(r) + \ell(p),(10)✦ and a meter for CC is a function μ\mu from the vertices to the natural numbers, the coins, such that every vertex VV that is not a base vertex satisfies, for each i<ri < r, μ(H(V))+π(0)≤μ(V),μ(Ai(V))+π(g(V))≤μ(V).\mu\bigl(H(V)\bigr) + \pi(0) \le \mu(V), \qquad \mu\bigl(A_i(V)\bigr) + \pi\bigl(g(V)\bigr) \le \mu(V).(11)✦

A family (Cj)j∈I(C_j)_{j \in I} of dependency circuits, with widths djd_j, fan-ins rjr_j, vertex counts njn_j and primes pjp_j, is ready for public inputs xx, a space bound SS and parameters qq, families indexed by II, when, for a constant cc independent of jj, Compx,S(q,d),Compx,S(q,r),ℓ(nj)≤c(S(j)+1),ℓ(pjdj+1)≤c(S(j)+1),\mathrm{Comp}_{x,S}(q, d), \qquad \mathrm{Comp}_{x,S}(q, r), \qquad \ell(n_j) \le c\,(S(j) + 1), \qquad \ell\bigl(p_j^{\,d_j + 1}\bigr) \le c\,(S(j) + 1),(12)✦ and when the family is navigable in space SS: for every map ρ:U→I\rho\colon U \to I and family aa over UU, whenever q∘ρq \circ \rho and a choice of a vertex VV of Cρ(u)C_{\rho(u)} at each u∈Uu \in U are computable from aa after the change of index ρ\rho, so are, with dd and rr standing for dρ(u)d_{\rho(u)} and rρ(u)r_{\rho(u)}, the bit saying whether VV is a base vertex, g(V)g(V), H(V)H(V) and β(V)\beta(V); the child Ak(V)A_k(V) for every such computable kk with k≤rk \le r; the selector value GV,z,y(w)G_{V,z,y}(w) for such computable zz, yy, ww with z≤d+1z \le d + 1, y≤2dy \le 2^d and w<2dw < 2^d; and the test value PV,z,y,k(w,w′)P_{V,z,y,k}(w, w') for such computable zz, yy, kk, ww, w′w' under the same bounds with k≤rk \le r and w′<2dw' < 2^d.

In the paper, the result reads: a finite acyclic graph on polynomially many word identifiers VV with semantic values v(V)∈{0,1}dv(V) \in \{0,1\}^d has base words, ordinary vertices with v(V)=fV(v(U1),…,v(Ua))v(V) = f_V(v(U_1), \dots, v(U_a)) for a≤ra \le r, and history vertices with a distinguished child HH, children A1,…,ANA_1, \dots, A_N, a guess length gg and the identity v(V)¯=∑YGY(v(H))¯∏iPY,i(v(H),v(Ai))\overline{v(V)} = \sum_Y \overline{G_Y(v(H))} \prod_i P_{Y,i}(v(H), v(A_i)) in characteristic two, where edges to HH and ordinary edges weigh 11, edges to the AiA_i weigh g+1g + 1, W(V)W(V) is the maximal weight of a path from VV, and navigation and the local functions are uniformly computable.

What Is Checked

The definitions are stated over the field 𝔽p\mathbb{F}_p of the prime chosen for the outer degree (r+1)d(r+1)d, the coordinate vectors over it with the augmentation (1) and the extensions (3) and (4), and computability in space SS by stack machines.