OctoInformBeta

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

Lemma 4.2 [Preservation of the route]: Local success at a first default yields a routed terminal hit

Earlier test agreement preserves route prefixes.

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

A finite dyadic router assigns a real point to a terminal path by testing ordered selector bits. Membership in the resulting set is decided by one terminal bit. For a center x∈ℝx\in\mathbb R, write yn(t)=x+t2−ny_n(t)=x+t2^{-n}, where n∈ℕn\in\mathbb N and t∈[1,2]t\in[1,2]. The question is which selector values at xx and yn(t)y_n(t) must agree before a local test can determine membership.

Fix M,d∈ℕM,d\in\mathbb N. The children are 0,…,M0,\ldots,M, with nondefault children i<Mi<M and default child MM.✦ Thus the paper’s total number of children is M+1M+1 in this notation. A decision node PP is a finite sequence of children of length |P|<d|P|<d, and a terminal path LL is a finite sequence of children of length dd. Write Pi=P⌢(i)Pi=P\frown(i) for the child edge obtained by appending ii, and ∅\emptyset for the root.

Ordered Routes

Let XX be a set of states and let S(P,z,i)∈{0,1}S(P,z,i)\in\{0,1\} be a selector value for each path PP, state z∈Xz\in X and nondefault child ii. The first-success routing choice cSc_S and the iterated route RSR_S are defined by (1), where ℓ∈ℕ\ell\in\mathbb N counts routing steps. cS(P,z)=min⁡({i<M:S(P,z,i)=1}∪{M}),RS0(P,z)=P,RSℓ+1(P,z)=RSℓ(P,z)⌢(cS(RSℓ(P,z),z)).\begin{aligned} c_S(P,z)&=\min\bigl(\{i<M:S(P,z,i)=1\}\cup\{M\}\bigr),\\ R_S^0(P,z)&=P,\\ R_S^{\ell+1}(P,z)&=R_S^\ell(P,z)\frown \bigl(c_S(R_S^\ell(P,z),z)\bigr). \end{aligned}(1)

Window Tables

An admissible window edge PP is a nonempty path of length at most dd. Separated window data WW with gap gg and minimum length r0r_0 consist of a length function ℓ:ℕ→ℕ\ell:\mathbb N\to\mathbb N and natural-valued functions a,b,b*a,b,b^* on paths, satisfying (2). Here h(P)=d+1−|P|h(P)=d+1-|P|, P≼QP\preceq Q means that PP is a prefix of QQ, and P≺QP\prec Q means a proper prefix; all displayed edge paths are admissible, and VV is any continuation. ℓ(h(P))≥max⁡{1,r0},a(P)≥3,b(P)+1=a(P)+ℓ(h(P)),b*(P)+1≤a(P)+2ℓ(h(P)),P≼Q:b(P)≤b(Q)≤b*(P),P≺Q:b(P)+g<a(Q),i<j:b(Pi)+g<a(PjV).\begin{aligned} \ell(h(P))&\ge\max\{1,r_0\},& a(P)&\ge3,\\ b(P)+1&=a(P)+\ell(h(P)),& b^*(P)+1&\le a(P)+2\ell(h(P)),\\ P\preceq Q&:\quad b(P)\le b(Q)\le b^*(P),\\ P\prec Q&:\quad b(P)+g<a(Q),\\ i<j&:\quad b(Pi)+g<a(PjV). \end{aligned}(2)✦ The window of an edge PP is the integer interval [a(P),b(P)][a(P),b(P)]. The selector and terminal endpoint assignments are respectively those in (3). bS(P,i)=b(Pi),bT(L)=b(L).b_S(P,i)=b(Pi),\qquad b_T(L)=b(L).(3)

For natural numbers qq and bb, the periodic mesh key kqk_q and the finite dyadic grid key κb\kappa_b are the integer-valued functions on ℝ\mathbb R given by (4), where {z}\{z\} denotes the fractional part of zz. The dyadic cells are half-open and include their left endpoints. kq(z)=⌊q{z}⌋,κb(z)=k2b+2(z)∈{0,…,2b+2−1}.k_q(z)=\lfloor q\{z\}\rfloor,\qquad \kappa_b(z)=k_{2^{b+2}}(z)\in\{0,\ldots,2^{b+2}-1\}.(4)

A Boolean selector table σ\sigma assigns a bit to every selector address (P,i,j)(P,i,j) with |P|<d|P|<d, i<Mi<M and 0≤j<2bS(P,i)+20\le j<2^{b_S(P,i)+2}.✦ A terminal Boolean table τ\tau assigns a bit to every terminal address (L,j)(L,j) with |L|=d|L|=d and 0≤j<2bT(L)+20\le j<2^{b_T(L)+2}.✦ Their queried addresses are defined in (5). AS(P,i;z)=(P,i,κbS(P,i)(z)),AT(L;z)=(L,κbT(L)(z)).A_S(P,i;z)=(P,i,\kappa_{b_S(P,i)}(z)),\qquad A_T(L;z)=(L,\kappa_{b_T(L)}(z)).(5) The extended selector value SσS_\sigma is defined by (6); its pointwise first-success choice is cσ=cSσc_\sigma=c_{S_\sigma}. Sσ(P,z,i)={σ(AS(P,i;z)),|P|<d,0,|P|≥d.S_\sigma(P,z,i)= \begin{cases} \sigma(A_S(P,i;z)),&|P|<d,\\ 0,&|P|\ge d. \end{cases}(6)✦

Write Rσ=RSσR_\sigma=R_{S_\sigma}. The root routed leaf and the local routed leaf are respectively Lσ(z)L_\sigma(z) and Lσ(P,r;z)L_\sigma(P,r;z) in (7), with the local leaf defined when |P|+r=d|P|+r=d. Lσ(z)=Rσd(∅,z),Lσ(P,r;z)=Rσr(P,z).L_\sigma(z)=R_\sigma^d(\emptyset,z),\qquad L_\sigma(P,r;z)=R_\sigma^r(P,z).(7) For an address map α\alpha, a selector table σ\sigma and a terminal table τ\tau, the address-selected set is the subset of ℝ\mathbb R consisting of those zz whose bit τ(α(σ,z))\tau(\alpha(\sigma,z)) is 11. The routed terminal address and its selected set BωB_\omega, for ω=(σ,τ)\omega=(\sigma,\tau), are defined in (8). α(σ,z)=AT(Lσ(z);z),Bω={z∈ℝ:τ(α(σ,z))=1}.\alpha(\sigma,z)=A_T(L_\sigma(z);z),\qquad B_\omega=\{z\in\mathbb R:\tau(\alpha(\sigma,z))=1\}.(8)

A center x∈ℝx\in\mathbb R is selector-stable for WW when (9) holds for every decision node PP, nondefault child ii, natural number nn with b(Pi)+g<nb(Pi)+g<n, normalized scale t∈[1,2]t\in[1,2] and selector table σ\sigma. Sσ(P,x,i)=Sσ(P,yn(t),i).S_\sigma(P,x,i)=S_\sigma(P,y_n(t),i).(9)✦ For a decision node UU and a nondefault child ii, the local selector and terminal test QU,iω(z)Q_{U,i}^\omega(z) is the Boolean product in (10). QU,iω(z)=σ(AS(U,i;z))τ(AT(Lσ(Ui,d−|U|−1;z);z)).Q_{U,i}^\omega(z)=\sigma(A_S(U,i;z))\, \tau\!\left(A_T\!\left( L_\sigma(Ui,d-|U|-1;z);z\right)\right).(10)✦

The Claim

Theorem 1. Let SS be an ordered Boolean selector family on paths and states in XX. For the prefix assertion (11), fix a path PP, states x,y∈Xx,y\in X and a natural number kk, and put Pℓ=RSℓ(P,x)P_\ell=R_S^\ell(P,x). Suppose that for each ℓ<k\ell<k the choice cS(Pℓ,x)c_S(P_\ell,x) is nondefault and that S(Pℓ,x,j)=S(Pℓ,y,j)S(P_\ell,x,j)=S(P_\ell,y,j) for every j≤cS(Pℓ,x)j\le c_S(P_\ell,x). Then RSk(P,y)=RSk(P,x).R_S^k(P,y)=R_S^k(P,x).(11)✦

Let UU be a path and i<Mi<M. Suppose cS(U,x)=Mc_S(U,x)=M, the selector values at xx and yy agree for every j<ij<i, and S(U,y,i)=1S(U,y,i)=1. Then cS(U,y)=i.c_S(U,y)=i.(12)✦

Take a terminal predicate T(P,z)T(P,z) and r∈ℕr\in\mathbb N. Assume the hypotheses of (11), put U=RSk(P,x)U=R_S^k(P,x), and assume the hypotheses of (12) at UU and ii. If T(RSr(Ui,y),y)T(R_S^r(Ui,y),y) holds, then T(RSk+1+r(P,y),y).T\bigl(R_S^{k+1+r}(P,y),y\bigr).(13)✦

Let WW be separated window data, ω=(σ,τ)\omega=(\sigma,\tau) an outcome and xx a selector-stable center. Suppose U=Rσk(∅,x)U=R_\sigma^k(\emptyset,x) is a decision node, the choices at xx before step kk are nondefault, and cσ(U,x)=Mc_\sigma(U,x)=M. Let i<Mi<M, t∈[1,2]t\in[1,2] and n≥1n\ge1 satisfy a(Ui)≤na(Ui)\le n. If QU,iω(yn(t))=1Q_{U,i}^\omega(y_n(t))=1, then yn(t)=x+t2−n∈Bω.y_n(t)=x+t2^{-n}\in B_\omega.(14)✦

In the paper, the result reads: for a center xx in its set GG and a full center-exposure atom ξ\xi, consisting of outcomes with the same fully exposed data at xx and with first default node UU, every outcome ω∈ξ\omega\in\xi, nondefault child i<Mi<M, index n≥1n\ge1 in the window of UiUi and t∈[1,2]t\in[1,2] has its actual route at yn(t)y_n(t) reach UU and reject all earlier nondefault children there, and QU,iω(yn(t))=1Q_{U,i}^\omega(y_n(t))=1 implies yn(t)∈Bωy_n(t)\in B_\omega.

What Is Checked

The route assertions are stated over arbitrary ordered Boolean selector families; the membership assertion uses finite selector and terminal tables with separated window data and a selector-stable center. For every decision node UU and nondefault child ii, the local routing depth identity is (15). |Ui|+(d−(|U|+1))=d.|Ui|+\bigl(d-(|U|+1)\bigr)=d.(15)✦