OctoInformBeta

OpenAI preprint, September 2026 · §11. Uniform controller implementation · §11

Theorem 11.1 [Realization of the estimator interfaces]: Each program compiles into one logspace function correct on its certified runs, and one logspace function computes the estimator’s start value within 1/321/32

Recursive controllers with stack budgets run in logspace.

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

Let PP be a randomized machine running in logarithmic space and xx an input of length nn. The analytic estimator of PP on xx is a real-valued function of a sampling environment, a triple of lines in a four-dimensional space over a prime field; it is built from the configuration graph of PP on xx by a recursion over rounds, driven by a controller program defined below, in which the table answering each request of the controller is assembled from the tables of earlier rounds. A deterministic machine with O(log⁡n)O(\log n) work space has no room for an unbounded call stack: each pending call may save only a short frame, and the frames saved along a chain of nested calls must fit in the bits that a meter, a function assigning a number of bits to each level, grants at the outermost level. The question is whether a recursive program run under such a budget, and in particular the estimator’s controller with suitable parameters, is carried out by one logspace function, and how close that function comes to the estimator’s value at the start.

Logspace Functions and Controller Programs

A counter program reads an input word xx of length nn and acts on registers r0,r1,…r_0,r_1,\dots holding natural numbers. A counter program is built from single steps that increase, decrease or keep one register, from sequencing, and from branches and while loops whose test is a property of the input symbol in the cell whose index a register holds.✦ A numeric function g(x,r)g(x,r) of the input and the registers is register computable when it depends on finitely many registers and, for every register ii and every large enough ll, some counter program with an exponent d>0d>0 overwrites rir_i by g(x,r)g(x,r) whenever it starts from registers below some W≥n+2W\ge n+2 that vanish from index ll on, keeping every register below WdW^d throughout and leaving the registers from index ll on at zero.✦ With arguments and values coded by natural numbers, a function ff of an input word and an argument is logspace computable when, for every register computable gg, the function (x,r)↦⟨f(x,g(x,r)¯)⟩(x,r)\longmapsto\bigl\langle f\bigl(x,\overline{g(x,r)}\bigr)\bigr\rangle(1)✦ is register computable, where z¯\overline{z} is the argument with code zz and ⟨⋅⟩\langle\cdot\rangle is the code of a value.

A controller program acts, for an input word xx and at a level qq, on states a=(a1,a2)a=(a_1,a_2), pairs of natural numbers made of a frame a1a_1 and a shared value a2a_2; one controller program Γ\Gamma is fixed as the main program, the target of every call. Controller programs are built from edit steps, which replace aa by μ(x,q,a)\mu(x,q,a); calls, which compute a callee level q′=θ(x,q,a1)q'=\theta(x,q,a_1), run Γ\Gamma at level q′q' from the state (0,a2)(0,a_2) to a state a′a' and replace aa by ρ(x,q,a1,a′)\rho(x,q,a_1,a'); sequencing; branches on a flag β(x,q,a)\beta(x,q,a); and while loops on such a flag.✦ The maps μ\mu, θ\theta, ρ\rho and the flags are logspace computable.

Under a budget F=(L,m)F=(L,m), a limit LL together with a meter m:ℕ→ℕm\colon\mathbb{N}\to\mathbb{N}, a state aa is admissible at level qq when the first three inequalities below hold, and a call from level qq with frame a1a_1 to level q′q' is affordable when the last one holds: q≤L,a2≤L,∥a1∥≤m(q),∥a1∥+1+m(q′)≤m(q),q\le L,\qquad a_2\le L,\qquad \|a_1\|\le m(q),\qquad\qquad \|a_1\|+1+m(q')\le m(q),(2) where ∥z∥=⌊log⁡2z⌋+1\|z\|=\lfloor\log_2 z\rfloor+1 is the bit length, with ∥0∥=1\|0\|=1. A stack certificate that a controller program CC takes aa to bb at level qq, for the input xx, the budget FF and the main program Γ\Gamma, is a finite derivation of that run by the rules of the constructs, in which every edit step and every call starts and ends in states admissible at level qq, every loop exits from an admissible state, and every call is affordable and rests on a stack certificate that Γ\Gamma takes (0,a2)(0,a_2) to the returned state at the callee level.✦

Instances and the Estimator

An instance rr consists of a source machine PP, analytic constants and a padding pp.✦ The source machine is a probabilistic Turing machine with binary work tapes and input heads, given with a space coefficient csc_s and a polynomial clock c(n+2)kc(n+2)^k✦; it keeps its space bound when, on every input xx, with every coin tape and through every time, the work cells it has visited, summed over its tapes, number at most cs⌈log⁡2(n+2)⌉c_s\lceil\log_2(n+2)\rceil.✦ The analytic constants are a precision A0A_0, a walk length ℓ\ell and parameter constants (T,K,J,M)(T,K,J,M)✦: an iteration count T>0T>0 with (5/A)T/T!≤1/1024(5/A)^T/T!\le 1/1024, indices KK and JJ with 128(1+32(T+1)/η(δ))≤K+1128(1+32(T+1)/\eta(\delta))\le K+1 and 64M(T+1)2≤δ(J+1)64M(T+1)^2\le\delta(J+1), and a number M>16(T+1)M>16(T+1) of copies of each vertex, where A=1/4096A=1/4096, δ=A/400\delta=A/400 and η(z)=z/1000\eta(z)=z/1000.✦

The estimator’s recursion uses three ramps, called boost, cutoff and shutoff, and a profile for every request kind. The analytic constants are admissible with a constant R≥1R\ge 1 when the fourth roots of the three ramps are RR-Lipschitz, and every request kind has profiles, each a triple of a start figure, a row figure and a quotient figure, all nonnegative, constant on each ray outside [−R,R][-R,R], with fourth roots at most RR and RR-Lipschitz, where for the threshold zz of the kind, equal to 1/21/2 for a chip or a slot, to AA for an echo and to δ\delta for a score, the start figure vanishes for x≤z/8x\le z/8, the row figure vanishes for x≥z/40x\ge z/40 and equals 11 for x≤η(z)x\le\eta(z); when there are real budgets, a ceiling, a slip and a toll, with a derived prize and venture, meeting the prescribed inequalities, such that the prize, the venture and 2424 times the squared toll are each at most 2A0β2^{A_0}\beta, where the bank is β=4+2R3(K+cJ+1),cJ=128(1+32(128+4(J+1)));\beta=4+2R^3\,(K+c_J+1),\qquad c_J=128\bigl(1+32(128+4(J+1))\bigr);(3)✦ and when 16(1−λ0)ℓ≤2−7216(1-\lambda_0)^{\ell}\le 2^{-72} for the loss λ0=1/(16384(10g0|𝒞|)2)\lambda_0=1/\bigl(16384\,(10g_0|\mathcal{C}|)^2\bigr) of the walk on the set 𝒞\mathcal{C} of generator choices, with the gap constant g0=6+4/τg_0=6+4/\tau and τ=2(1−cos⁡(π/8))\tau=2(1-\cos(\pi/8)).

For an input xx of length nn, the instance fixes the bit budget BB and the top round MtopM_{\mathrm{top}}, B=p+∥N(x)∥+∥n+2∥,Mtop=8((M+7)B+A0(1+(50+8T)B)),B=p+\|N(x)\|+\|n+2\|,\qquad M_{\mathrm{top}}=8\bigl((M+7)B+A_0(1+(50+8T)B)\bigr),(4) where N(x)N(x) is the number of nodes of the configuration graph of PP on xx; with the roof H=Mtop+(M+2)B+1H=M_{\mathrm{top}}+(M+2)B+1, the field size nxn_x is the largest prime in (λ,2λ](\lambda,2\lambda] for λ=2H+M\lambda=2^H+M.✦

A sampling environment over nxn_x is a triple s=(X,Y,Z)s=(X,Y,Z) of rank channels, each a pair of a nonzero direction aa and an offset bb in (ℤ/nx)4(\mathbb{Z}/n_x)^4 describing the line y↦b+yay\mapsto b+ya.✦ Its code ⟨s⟩\langle s\rangle codes the coordinates of the three channels as natural numbers below nxn_x.

The analytic estimator of PP on xx is the forecast of a scene built from xx, which assigns to every request of the controller, round by round, a table over sampling environments and vertices. The scene has height BB, 2(M+1)B2^{(M+1)B} levels, roof HH, gap A0A_0 and walk length ℓ\ell, and starts from the prize of PP on xx✦: the stage at level 00 whose domain is the set of nodes of the configuration graph and whose matrix gives, for nodes ii and jj, the probability that one coin leads from ii to jj, together with the accepting rewards and the acceptance potentials of the nodes.✦ The forecast at round MtopM_{\mathrm{top}} gives every request of the controller a table over sampling environments and vertices: a request active at that round receives its table built from the forecasts of the earlier rounds, and an inactive one the zero table.✦ The estimator’s value at the start, Φx(s)\Phi_x(s), is the entry at ss of the table of the prize request at level BB, taken at the vertex MBx0M^Bx_0, the copy at depth BB of the initial node x0x_0 of PP on xx.

The estimator’s contract 𝒞r(π,v,κ)\mathcal{C}_r(\pi,v,\kappa) relates the instance to precision parameters π=(πc,πv,πs,πl)\pi=(\pi_c,\pi_v,\pi_s,\pi_l), to controller tags vv, among them an exponent ee, a constant α\alpha, a slope σ\sigma, a clock offset tvt_v and a bonus bvb_v, which give the controller the clock σ(128(Mtop+1)+1)+tv\sigma\,(128(M_{\mathrm{top}}+1)+1)+t_v on xx, and to a natural number κ\kappa. The contract 𝒞r(π,v,κ)\mathcal{C}_r(\pi,v,\kappa) holds when the analytic constants are admissible with a constant RR satisfying R12≤2πcR^{12}\le 2^{\pi_c} and R≤2πsR\le 2^{\pi_s}; when 2−πl≤δ/10002^{-\pi_l}\le\delta/1000, πv\pi_v is at least 44 plus the reserve of the analytic constants, and 36+πv+2πc≤πs36+\pi_v+2\pi_c\le\pi_s; when bv≥c0b_v\ge c_0 and e≥10(10(c0+10+πv)+πv)e\ge 10(10(c_0+10+\pi_v)+\pi_v) for the boot cost c0c_0 of the instance; when κ\kappa is at least 100100, 100e100e, KK and the bit length of the capacity constant, and 1000κ2≤α1000\kappa^2\le\alpha; and when σ\sigma is at least 66, 10e10e, α\alpha, α(2α+40)+6(j+50)+40\alpha(2\alpha+40)+6(j+50)+40 for j=Jj=J and for j=cJj=c_J, and the cost bound of each component program of the estimator; here the reserve, the boot cost, the capacity constant and the cost bounds are quantities determined by the instance and the estimator.✦

The Claim

Theorem 1. Let Γ\Gamma be a controller program. There is a logspace computable function ff of an input word and a pair ((U,q),a)((U,q),a) of a bound UU, a level qq and a state aa with the following property. Let xx be an input word, F=(L,m)F=(L,m) a budget, qq a level, UU a bound with 2m(q)≤U2^{m(q)}\le U and L≤UL\le U, and aa, bb states such that a stack certificate shows that Γ\Gamma takes aa to bb at level qq. Then f(x,((U,q),a))=b.f\bigl(x,((U,q),a)\bigr)=b.(5)✦ Let rr be an instance with admissible analytic constants. For every natural number tt there are precision parameters π\pi, controller tags vv and a natural number κ\kappa such that 𝒞r(π,v,κ)andtv=t.\mathcal{C}_r(\pi,v,\kappa)\quad\text{and}\quad t_v=t.(6)✦ Let rr be an instance with padding p≥6p\ge 6 whose source machine keeps its space bound and whose analytic constants are admissible with a constant RR whose bank satisfies β≤2p\beta\le 2^p. There is a logspace computable function ff from input words and natural numbers to natural numbers such that, for every input word xx and every sampling environment ss over nxn_x, |164min⁡{64,f(x,⟨s⟩)}−Φx(s)|≤132.\Bigl|\tfrac{1}{64}\min\bigl\{64,f(x,\langle s\rangle)\bigr\}-\Phi_x(s)\Bigr|\le\tfrac{1}{32}.(7)✦

In the paper, the result reads: for fixed construction constants and admissible Mtop=O(B)M_{\mathrm{top}}=O(B), the row, vector and prefix interfaces admit deterministic uniform implementations by restoring queries and cursor motions, for every master environment: queries terminate, return their defined values and restore cursor and catalyst; terminal motions give the specified endpoints; and a root request at clock tt keeps O(Mtop+t+1)O(M_{\mathrm{top}}+t+1) retained records and uses O(B+Mtop+t+1)O(B+M_{\mathrm{top}}+t+1) shared space.

What Is Checked

The claims are stated over logspace computable functions, defined through counter programs with polynomially bounded registers, over controller programs with their budgets and stack certificates, and over instances with the source machine’s space bound, admissible analytic constants, the field size nxn_x, the sampling environments, the estimator’s contract and the estimator’s value Φx(s)\Phi_x(s) at the start.

The library also proves that logspace computable functions are closed under composition✦ and pairing✦, that constant functions✦, the two projections of a pair, coding✦ and decoding✦ are logspace computable, and that so are the field size nxn_x, the power of two of the controller’s clock, the decoding of certificates✦, and the lookups, tests and step functions from which the controller programs of the estimator are built.