OctoInformBeta

OpenAI preprint, September 2026 · §4. Random routing and independent tests

Lemma 4.3 [The fixed-scale estimate]: On a center-exposure atom, each nondefault child contributes its full window of tests

Local misses have an exact fixed-scale mass.

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

For a real center xx and a fixed normalized scale t∈[1,2]t\in[1,2], the points x+t2−nx+t2^{-n}, with natural n≥1n\ge1, test random selectors and terminal labels in a finite router. The estimate concerns their simultaneous local misses after all selector values at xx have been prescribed.

Fix natural numbers M,d,g,r0M,d,g,r_0. The children are 0,…,M0,\ldots,M, with MM the default child and MM nondefault children.✦ A decision node PP is a child sequence of length |P|<d|P|<d✦; a terminal path LL is a child sequence of length dd.✦ Write PiPi for the edge obtained by appending child ii to PP, and E≼FE\preceq F for the prefix relation. An admissible edge is a nonempty path of length at most dd.✦

Separated window data WW consist of a length function r:ℕ→ℕr:\mathbb N\to\mathbb N and natural-valued path functions a,b,b*a,b,b^* satisfying (1). For an admissible edge EE, put hE=d+1−|E|h_E=d+1-|E| and let WE={a(E),…,b(E)}W_E=\{a(E),\ldots,b(E)\} be its window. The conditions involving two edges apply when both are admissible; TT denotes an arbitrary continuation in the last line. r(hE)≥max⁡{1,r0},a(E)≥3,b(E)+1=a(E)+r(hE),b*(E)+1≤a(E)+2r(hE),b(E)≤b(F)≤b*(E)(E≼F),b(E)+g<a(F)(E≺F),b(Pi)+g<a(PjT)(i<j).\begin{aligned} r(h_E)&\ge \max\{1,r_0\}, & a(E)&\ge3,\\ b(E)+1&=a(E)+r(h_E), & b^*(E)+1&\le a(E)+2r(h_E),\\ b(E)&\le b(F)\le b^*(E) &&(E\preceq F),\\ b(E)+g&<a(F) &&&(E\prec F),\\ b(Pi)+g&<a(PjT) &&&(i<j). \end{aligned}(1)✦

For a real mesh parameter qq, the periodic cell index κq(y)\kappa_q(y) is the floor of qq times the fractional part {y}\{y\}.✦ For a natural level bb and a real point yy, the dyadic cell index kb(y)k_b(y) is the periodic cell index at mesh 2b+22^{b+2}, as in (2). Its cells are half-open and include their left endpoints. κq(y)=⌊q{y}⌋,kb(y)=κ2b+2(y)∈{0,…,2b+2−1}.\kappa_q(y)=\lfloor q\{y\}\rfloor, \qquad k_b(y)=\kappa_{2^{b+2}}(y)\in\{0,\ldots,2^{b+2}-1\}.(2)

The selector resolution is bS(P,i)=b(Pi)b_S(P,i)=b(Pi) for i<Mi<M✦, and the terminal resolution is bT(L)=b(L)b_T(L)=b(L).✦ A selector address is a triple (P,i,k)(P,i,k) with 0≤k<2bS(P,i)+20\le k<2^{b_S(P,i)+2}✦; a terminal address is a pair (L,k)(L,k) with 0≤k<2bT(L)+20\le k<2^{b_T(L)+2}, where kk is an integer.✦ The selector address set 𝒜S\mathcal A_S is the finite set of selector addresses, and the terminal address set 𝒜T\mathcal A_T is the finite set of terminal addresses. The selector table space 𝒮\mathcal S is the set of all Boolean assignments to 𝒜S\mathcal A_S, and the terminal table space 𝒯\mathcal T is the set of all Boolean assignments to 𝒜T\mathcal A_T; their elements are the selector tables σ\sigma and terminal tables τ\tau, respectively. The queried addresses are (3). α(P,i,y)=(P,i,kbS(P,i)(y)),β(L,y)=(L,kbT(L)(y)).\alpha(P,i,y)=(P,i,k_{b_S(P,i)}(y)), \qquad \beta(L,y)=(L,k_{b_T(L)}(y)).(3)

The Bernoulli bit law νp\nu_p, for 0≤p≤10\le p\le1, assigns masses pp and 1−p1-p to 11 and 00✦; the fair bit law is ν1/2\nu_{1/2}.✦ The independent selector and terminal laws, and their joint outcome law, are the product measures in (4). μS=ν1/2⊗𝒜S,μT,p=νp⊗𝒜T,ℙp=μS⊗μT,p.\mu_S=\nu_{1/2}^{\otimes\mathcal A_S},\qquad \mu_{T,p}=\nu_p^{\otimes\mathcal A_T},\qquad \mathbb P_p=\mu_S\otimes\mu_{T,p}.(4)

Local Routing and Trials

The extended selector value at (P,i,y)(P,i,y) is σ(α(P,i,y))\sigma(\alpha(P,i,y)) when |P|<d|P|<d, and is zero otherwise.✦ For any list of nondefault bits, the first successful child is the least index with value one, or the default child when all values are zero.✦ For a selector table σ\sigma, a path PP, and a real point yy, the pointwise first-success choice χσ(P,y)\chi_\sigma(P,y) is the least nondefault child whose extended selector value at PP and yy is one, or the default child when all these values are zero.✦

An iterated routing path from a path PP at a fixed point yy is a path obtained by starting at PP and repeatedly appending the child chosen at the current path and at yy.✦ After zero steps it is PP. Given a rule χ\chi assigning a child to each path and real point, a path PP, a real point yy and a natural number kk with |P|+k=d|P|+k=d, the local routed leaf is the terminal path obtained by following χ\chi for kk steps from PP at yy. For a decision node UU and i<Mi<M, let Lσ(U,i,y)L_\sigma(U,i,y) be the local routed leaf starting at UiUi and taking d−(|U|+1)d-(|U|+1) further steps with choice χσ\chi_\sigma. The local selector-terminal test Qiσ,τ(y)Q_i^{\sigma,\tau}(y) is the Boolean conjunction in (5). Qiσ,τ(y)=σ(α(U,i,y))τ(β(Lσ(U,i,y),y)).Q_i^{\sigma,\tau}(y)= \sigma(\alpha(U,i,y))\,\tau(\beta(L_\sigma(U,i,y),y)).(5)✦

A child window trial of length ℓ\ell is a pair (i,j)(i,j) with i<Mi<M and 0≤j<ℓ0\le j<\ell✦; for starting indices cic_i, its index is ci+jc_i+j.✦ At UU, the local starts are ai=a(Ui)a_i=a(Ui)✦ and the common length is r=r(d−|U|)r=r(d-|U|). The local trial set, its indices, shifted points, and queried selector addresses are given in (6); in particular, its indices are at least three. ℐU={(i,j):0≤i<M,0≤j<r},nij=ai+j,yij=x+t2−nij,Aij=α(U,i,yij).\begin{gathered} \mathcal I_U=\{(i,j):0\le i<M,\ 0\le j<r\},\qquad n_{ij}=a_i+j,\\ y_{ij}=x+t2^{-n_{ij}},\qquad A_{ij}=\alpha(U,i,y_{ij}). \end{gathered}(6)

The center selector exposure Xx(σ)X_x(\sigma) is the Boolean assignment (P,i)↦σ(α(P,i,x))(P,i)\mapsto\sigma(\alpha(P,i,x)) over all decision nodes and nondefault children.✦ For a Boolean assignment ξ\xi to the pairs of decision nodes and nondefault children, the selector exposure atom Cˆξ\widehat C_\xi is the fiber in 𝒮\mathcal S and the center-exposure atom CξC_\xi is the fiber in 𝒮×𝒯\mathcal S\times\mathcal T specified in (7). For a center selector assignment ξ\xi, the local miss event FξF_\xi is the subset of CξC_\xi on which all local selector-terminal tests vanish, as specified in (7). Cˆξ={σ:Xx(σ)=ξ},Cξ=Cˆξ×𝒯,Fξ={(σ,τ)∈Cξ:Qiσ,τ(yij)=0 for every (i,j)∈ℐU}.\begin{gathered} \widehat C_\xi=\{\sigma:X_x(\sigma)=\xi\},\qquad C_\xi=\widehat C_\xi\times\mathcal T,\\ F_\xi=\{(\sigma,\tau)\in C_\xi: Q_i^{\sigma,\tau}(y_{ij})=0\text{ for every }(i,j)\in\mathcal I_U\}. \end{gathered}(7)

For each selector table σ\sigma, let ℓσ(i,j)\ell_\sigma(i,j) be a terminal path beginning with UiUi. For a center selector assignment ξ\xi and a terminal-path assignment ℓσ(i,j)\ell_\sigma(i,j) beginning with UiUi, the miss event Eξ(ℓ)E_\xi(\ell) is the subset of CξC_\xi defined in (8). Eξ(ℓ)={(σ,τ)∈Cξ:τ(β(ℓσ(i,j),yij))=0 whenever σ(Aij)=1,(i,j)∈ℐU}.E_\xi(\ell)=\{(\sigma,\tau)\in C_\xi: \tau(\beta(\ell_\sigma(i,j),y_{ij}))=0 \text{ whenever }\sigma(A_{ij})=1,\ (i,j)\in\mathcal I_U\}.(8)

The Claim

Theorem 1. Let WW be separated window data, UU a decision node, and x∈ℝx\in\mathbb R. Fix t∈[1,2]t\in[1,2], p∈[0,1]p\in[0,1], and a full center selector assignment ξ\xi. For any terminal-path assignment ℓσ(i,j)\ell_\sigma(i,j) depending on the selector table and beginning with UiUi, the event in (8) satisfies ℙp(Eξ(ℓ))=μS(Cˆξ)(1−p2)Mr.\mathbb P_p(E_\xi(\ell))= \mu_S(\widehat C_\xi)\left(1-\frac p2\right)^{Mr}.(9)✦ For the routed local tests in (5), the event in (7) satisfies ℙp(Fξ)=(1−p2)Mrℙp(Cξ).\mathbb P_p(F_\xi)= \left(1-\frac p2\right)^{Mr}\mathbb P_p(C_\xi).(10)✦

In the paper, the result reads: for a stable center xx and a full center-exposure atom ξ\xi whose first default node UU has height hh, putting r=rhr=r_h, with rhr_h denoting the window length at height hh, every fixed t∈[1,2]t\in[1,2] gives conditional probability (1−p/2)Mr(1-p/2)^{Mr}, given ξ\xi, that Qi(x+t2−n)=0Q_i(x+t2^{-n})=0 for every i<Mi<M and n∈WUin\in W_{Ui}, where M+1M+1 is the paper’s total number of children.

What Is Checked

The statements (9) and (10) are over separated window data and finite independent table laws, for arbitrary decision nodes and real centers, with normalized scale t∈[1,2]t\in[1,2] and terminal parameter p∈[0,1]p\in[0,1]. The leaf assignments in (9) may depend on the entire selector table, subject to the prescribed child prefix.

For every decision node UU and nondefault child ii, the local routing depth identity is (11). |Ui|+(d−(|U|+1))=d.|Ui|+\bigl(d-(|U|+1)\bigr)=d.(11)✦