OctoInformBeta

OpenAI preprint, September 2026 · §12. Derandomization and quantitative consequences · §12

Lemma 12.2 [Conditioning on one start]: Given that the start is retained, a function’s mean is at most NN times its fourth-root norm, and pointwise bounds of 1/321/32 survive averaging

Errors at the retained start are at most 1/321/32..

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 probabilistic machine that runs in logarithmic space within a polynomial clock, and let xx be an input. In the configuration graph of PP on xx each coin flip is an edge of weight 1/21/2, and the acceptance probability is a value at the initial configuration. The derandomization builds a hierarchy of BB levels over this graph, in which every vertex has MM copies at the next level, and its estimators depend on a random environment of three channels, each an affine line in (ℤ/n)4(\mathbb{Z}/n)^4 for a prime nn. The size of a function of environment and vertex is measured by its fourth-root norm, a fourth moment averaged over the vertices that a random channel retains, each weighted by the inverse of the retention rate. The question is what this norm says at a single vertex, the copy of the start at level BB among the NN vertices of that level, given that this vertex is retained, and what follows there for the estimator and for the truncation of the hierarchy at level BB.

The Machine and Its Start

A source machine PP is a probabilistic Turing machine with q+1q+1 states, ww binary work tapes and hh input heads, whose transition reads one coin bit per step, together with a space coefficient csc_s and a polynomial clock c(|x|+2)kc\,(|x|+2)^k on inputs xx.✦ A source machine PP keeps its space bound when, on every input xx, with every coin tape and up to every time tt, the number of distinct work cells visited, summed over the tapes, is at most cs⌈log⁡2(|x|+2)⌉c_s\lceil\log_2(|x|+2)\rceil.✦

On an input xx, the configurations of PP are numbered as nodes below the node count ν\nu of PP on xx, each node encoding a time, a state, the input head positions and the work tapes; the initial node x0x_0 is the number of the start configuration. The halved edge weight C(j,j′)C(j,j') is the probability that one fair coin leads from node jj to node j′j' within the clock.✦ The accepting reward r(j)r(j) is 11 when node jj is a legal encoding of a configuration with time equal to the clock and output accept, and 00 otherwise.✦ The acceptance potential pacc(j)p_{\mathrm{acc}}(j) is the potential of jj at depth equal to the clock, where the potential at depth 00 is rr and each further unit of depth adds to rr the coin average, over the successors of jj, of the potential one unit shallower.✦

A stage consists of parameter constants pp (an iteration count TT, rank parameters KK and JJ and a number MM of copies of each vertex), a level, a finite domain of nodes and a matrix of transition weights.✦ A prize triple consists of a stage, a real vector WW of rewards paid at the nodes and a real vector vv meant to be the true acceptance probability at the nodes.✦ The parameter constants satisfy T≥1T\ge 1, 20480T/T!≤2−1020480^T/T!\le 2^{-10} and M>16(T+1)M>16(T+1), and KK and JJ are bounded below in terms of TT and MM. The raw prize HH of PP on xx under pp is the prize triple whose stage has level 00, domain {0,…,ν−1}\{0,\dots,\nu-1\} and matrix CC, whose rewards are rr and whose values are paccp_{\mathrm{acc}}.✦

A matter record mm over a prime nn consists of a source machine PP, analytic constants w0w_0, an input word xx and a bit budget BB✦; the analytic constants are parameter constants pp together with two natural numbers A0A_0 and ℓ\ell.✦ The copies of a vertex yy at the next level are z+Myz+My for z<Mz<M, and its child is the copy MyMy of index 00. The start of mm is the child of the initial node at depth BB, i=MBx0.i=M^B x_0 .(1)✦

The Hierarchy and Readiness

The matter scene of mm is the structure on the raw prize HH, whose recursive rolls compute the ticks used below, with NN levels, height BB, roof ρB\rho_B, gap A0A_0 and walk length ℓ\ell, where, with τB\tau_B the matter top, N=2(1+M)B,τB=8((7+M)B+A0(1+(50+8T)B)),ρB=τB+(2+M)B+1.N=2^{(1+M)B},\qquad \tau_B=8\bigl((7+M)B+A_0(1+(50+8T)B)\bigr),\qquad \rho_B=\tau_B+(2+M)B+1 .(2) The frame stage of the matter scene of mm at level kk is the iterate HkH_k, obtained from HH by kk steps of the scene’s recursion on prize triples; WkW_k denotes the reward vector of HkH_k and SkS_k the domain of its stage.

A wares proof ee for w0w_0 is a certificate that the analytic constants w0w_0 meet a list of technical conditions: bounds on the parameter constants pp, a constant R≥1R\ge 1 bounding the test shapes and the Lipschitz constants of the algorithm’s ramp functions, a budget for these bounds that meets the budget requirement at A0A_0, and the walk length condition for 1818 and ℓ\ell.✦ The tonic bank of a wares proof ee is the number β(e)=4+2R3(K+cJ+1)\beta(e)=4+2R^3(K+c_J+1), with cJ=128(1+32(132+4J))c_J=128\,(1+32(132+4J)).✦ The matter record mm is ready for ee when B≥6,ν≤2B,β(e)≤2B,M<n,2ρB≤n.B\ge 6,\qquad \nu\le 2^B,\qquad \beta(e)\le 2^B,\qquad M<n,\qquad 2^{\rho_B}\le n .(3)✦

Environments and Retention

Write Vn=(ℤ/n)4V_n=(\mathbb{Z}/n)^4.✦ A rank channel over nn is a pair (a,b)(a,b) of a nonzero direction a∈Vna\in V_n and an offset b∈Vnb\in V_n✦; its evaluation X(y)=b+yaX(y)=b+ya at y∈ℤ/ny\in\mathbb{Z}/n is the point at parameter yy of its line.✦ An environment s=(X,Y,Z)s=(X,Y,Z) is a triple of rank channels over nn, the pool is the set of all environments, and 𝔼s\mathbb{E}_s denotes the average over the pool.✦ The box of level kk is Qk={0,…,mk−1}4Q_k=\{0,\dots,m_k-1\}^4 with side mk=⌊(n−1)/2k⌋+1m_k=\lfloor (n-1)/2^k\rfloor+1, a vector lying in it when the least nonnegative representatives of its coordinates do; in particular Q0=VnQ_0=V_n.✦ A vertex yy of a finite domain is retained at level kk by a channel XX when X(y)∈QkX(y)\in Q_k, with yy read modulo nn, and the retention rate of level kk is 2−4k2^{-4k}.✦ An environment ss polls the start when its first channel retains ii at level BB.✦

Means, Norms and the Estimator

A paint is a real function f(s,y)f(s,y) of an environment ss of the pool and a vertex yy.✦ The view of mm is a request for the reward vector WBW_B at level BB and source level BB; it is a vertex request, that is, a request for a paint, and it asks for no detector.✦ The vertex axis dd of the view of mm is the estimation axis with domain SBS_B, size NN, and source and destination levels BB.✦ The conditional mean vector of a paint ff along dd has at ii the conditional average 𝔼df(i)=𝔼s[f(s,i)|X(i)∈QB,Y(0)∈Q0].\mathbb{E}_d f\,(i)=\mathbb{E}_s\bigl[\,f(s,i)\mathrel{\big|}X(i)\in Q_B,\ Y(0)\in Q_0\,\bigr].(4)✦

A monotone linear meter on a set is a functional on the real functions on that set that is monotone, additive and homogeneous.✦ The vertex meter of dd is the meter on pairs of an environment and a vertex that sums over the vertices of SBS_B retained at level BB by the first channel, averages over environments and scales by 1/(N2−4B)1/(N\,2^{-4B}).✦ The vertex norm of a paint ff is the fourth root of the vertex meter of f4f^4, ∥f∥d=(1N2−4B𝔼s∑y∈SB,X(y)∈QBf(s,y)4)1/4.\|f\|_d=\Bigl(\frac{1}{N\,2^{-4B}}\;\mathbb{E}_s\!\sum_{y\in S_B,\ X(y)\in Q_B} f(s,y)^4\Bigr)^{1/4}.(5)✦

A table request asks for a family of tables and a vertex request asks for a paint, and a tick of the scene answers every request of either kind. The forecast tick at a time tt is the tick computed at tt by the scene’s recursive rolls from the ticks at earlier times.✦ The estimator Wˆ\widehat W of mm, also called its oracle view, is the paint that the forecast tick at the matter top τB\tau_B assigns to the view.✦ For a real function gg on the pool, the jury value 𝒥(g)\mathcal{J}(g) is the conditional mean (4) at ii of the paint equal to g(s)g(s) at every vertex.✦

The Claim

Theorem 1. Let mm be a matter record over a prime nn, with source machine PP, analytic constants w0w_0, input xx, bit budget BB and start ii, and let ee be a wares proof for w0w_0. If mm is ready for ee and PP keeps its space bound, then every paint ff satisfies |𝔼df(i)|≤N∥f∥d,\bigl|\mathbb{E}_d f\,(i)\bigr|\le N\,\|f\|_d ,(6)✦ and the estimator satisfies |WB(i)−𝔼dWˆ(i)|≤132.\bigl|W_B(i)-\mathbb{E}_d\widehat W\,(i)\bigr|\le \tfrac{1}{32}.(7)✦ If mm is ready for ee, then |pacc(x0)−WB(i)|≤132.\bigl|p_{\mathrm{acc}}(x_0)-W_B(i)\bigr|\le \tfrac{1}{32}.(8)✦ Every real function gg on the pool with |g(s)−Wˆ(s,i)|≤1/32|g(s)-\widehat W(s,i)|\le 1/32 at every environment ss that polls the start satisfies |𝒥(g)−𝔼dWˆ(i)|≤132.\bigl|\mathcal{J}(g)-\mathbb{E}_d\widehat W\,(i)\bigr|\le \tfrac{1}{32}.(9)✦

In the paper, the result reads: for W∈[0,1]VW\in[0,1]^V with 1N𝔼∑vXf(v)f|W¯(v)−W(v)|8≤Cb82−8p\frac{1}{N}\,\mathbb{E}\sum_v\frac{X_f(v)}{f}\,|\overline W(v)-W(v)|^8\le C_b^8\,2^{-8p}, every specified z∈Vz\in V and every η>0\eta>0 satisfy 𝔼[|W¯(z)−W(z)|8|Xf(z)=1]≤NfπfCb82−8p\mathbb{E}\bigl[|\overline W(z)-W(z)|^8\mathrel{\big|}X_f(z)=1\bigr]\le N\,\frac{f}{\pi_f}\,C_b^8\,2^{-8p} and Pr⁡[|W¯(z)−W(z)|>η|Xf(z)=1]≤NfπfCb82−8pη−8\Pr\bigl[|\overline W(z)-W(z)|>\eta\mathrel{\big|}X_f(z)=1\bigr]\le N\,\frac{f}{\pi_f}\,C_b^8\,2^{-8p}\,\eta^{-8}, with WW, W¯\overline W and VV in the roles of WBW_B, Wˆ\widehat W and SBS_B, zz in the role of the start ii and Xf(z)=1X_f(z)=1 in that of its retention. Here XfX_f is the paper’s retention indicator, and ff, πf\pi_f, CbC_b and pp are the paper’s own symbols, not those of the page.

What Is Checked

The claim is stated over a matter record mm with its source machine PP and the space bound of PP, a wares proof ee with the readiness conditions (3), the start (1), the conditional mean (4) and the vertex norm (5) along the vertex axis of the view, the reward vector WBW_B of the iterate HBH_B, the acceptance potential paccp_{\mathrm{acc}} of the raw prize, the estimator Wˆ\widehat W and the jury value 𝒥\mathcal{J}. The library also proves that the finite average is monotone, additive and homogeneous, which makes the average over environments a monotone linear meter.