OctoInformBeta

OpenAI preprint, September 2026 · §5. Switching leaves and completing the proof

§5 (setting): finite descendant blocks and switch vectors: Normalized leaf switches and their weighted sums under successive root evaluation

Root increments over descendant blocks.

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 family of leaf values can be changed one leaf at a time while the root output is recorded. The quantities of interest are the root increments associated with one leaf and with all descendants of a fixed node.

Let XX be a real normed space and K⊆XK\subseteq X a nonempty convex set. The closed difference subspace Y⊆XY\subseteq X and its closed unit ball BYB_Y, viewed as a subset of XX, are defined by (1); every norm is the ambient norm. Y=span⁡(K−K)¯,BY={x∈Y:∥x∥≤1}.Y=\overline{\operatorname{span}(K-K)}, \qquad B_Y=\{x\in Y:\|x\|\leq 1\}.(1)

An ordered rooted tree TT is a family of finite levels Tk={0,…,mk−1}T_k=\{0,\ldots,m_k-1\}, where mk>0m_k>0 and m0=1m_0=1, with an order-preserving surjective parent map pk:Tk+1→Tkp_k:T_{k+1}\to T_k at every level.✦ Its root is the sole member of T0T_0.

A weighted ordered tree (T,ω)(T,\omega) is an ordered rooted tree with positive real edge weights ωk(c)\omega_k(c) whose sum over the children of each parent is one.✦ The root path weight πk(s)\pi_k(s) of a node s∈Tks\in T_k is the product of the edge weights along its path from the root, specified by (2).✦ π0(0)=1,πk+1(c)=πk(pk(c))ωk(c).\pi_0(0)=1, \qquad \pi_{k+1}(c)=\pi_k(p_k(c))\,\omega_k(c).(2)

A tree of nonexpansive maps EE on (T,ω)(T,\omega) and KK is a family of selfmaps Fk,v:K→KF_{k,v}:K\to K, one for each v∈Tkv\in T_k, all nonexpansive in the ambient norm.✦ For a natural cutoff NN, the cutoff evaluation ℰN:KTN→K\mathcal E_N:K^{T_N}\to K of the tree EE is the root output obtained by repeated weighted child averaging and application of node maps at levels strictly less than NN.✦ At cutoff zero, evaluation reads the assigned value at the root.

Blocks and Switches

Fix a terminal depth NN. For k≤Nk\leq N, the ancestor map ak,N:TN→Tka_{k,N}:T_N\to T_k is the composition of the parent maps between these levels, with ak,ka_{k,k} the identity.✦ The level-NN descendant block BN(v)B_N(v) of a node v∈Tkv\in T_k is the finite set in (3). The first and last descendants sv−s_v^- and sv+s_v^+ of the node vv and the lower and exclusive upper endpoints ℓv\ell_v and hvh_v of the block BN(v)B_N(v) are the indices defined in (3). BN(v)={s∈TN:ak,N(s)=v},sv−=min⁡BN(v),sv+=max⁡BN(v),ℓv=sv−,hv=sv++1.\begin{gathered} B_N(v)=\{s\in T_N:a_{k,N}(s)=v\},\\ s_v^-=\min B_N(v),\qquad s_v^+=\max B_N(v),\\ \ell_v=s_v^-,\qquad h_v=s_v^++1. \end{gathered}(3)

Let y:TN→Ky:T_N\to K be a leaf assignment and b∈Kb\in K a common replacement value. For a threshold t∈ℕt\in\mathbb N, the switched leaf assignment y(t):TN→Ky^{(t)}:T_N\to K and its evaluated root rt∈Kr_t\in K are defined by (4). Decreasing the threshold performs the leaf switches from right to left. y(t)(s)={ys,s<t,b,s≥t,rt=ℰN(y(t)).y^{(t)}(s)= \begin{cases} y_s,&s<t,\\ b,&s\geq t, \end{cases} \qquad r_t=\mathcal E_N(y^{(t)}).(4)

Write Ws=πN(s)W_s=\pi_N(s) for the terminal path weight. The root outputs immediately before and after switching the block BN(v)B_N(v) are UvU_v and VvV_v, respectively, as defined in (5). The normalized leaf switch vector ds∈Xd_s\in X at s∈TNs\in T_N is defined in the same display. Uv=rhv,Vv=rℓv,ds=Ws−1(rs+1−rs).U_v=r_{h_v},\qquad V_v=r_{\ell_v},\qquad d_s=W_s^{-1}(r_{s+1}-r_s).(5)

The Claim

Theorem 1. For the leaf assignment y:TN→Ky:T_N\to K and replacement b∈Kb\in K, the following hold.

  1. Let L⊆XL\subseteq X be a linear subspace containing K−KK-K, and suppose that ∥a−c∥≤1\|a-c\|\leq 1 for all a,c∈Ka,c\in K. For every s∈TNs\in T_N, ds∈L,∥ds∥≤1,Wsds=rs+1−rs.d_s\in L,\qquad \|d_s\|\leq 1,\qquad W_s d_s=r_{s+1}-r_s.(6)✦

  2. For every k≤Nk\leq N and v∈Tkv\in T_k, ∑s∈BN(v)Wsds=Uv−Vv.\sum_{s\in B_N(v)}W_s d_s=U_v-V_v.(7)✦

In the paper, the result reads: for N≥1N\geq 1, let BN(v)B_N(v) be the consecutive block of depth-NN descendants of vv, switch leaves from right to left from ysy_s to a common bb, evaluate the actual root after each switch, and, writing Uv,VvU_v,V_v for the root outputs immediately before and after switching BN(v)B_N(v) and ds=Ws−1(Us−Vs)d_s=W_s^{-1}(U_s-V_s) for the individual leaf increments, one has ds∈BYd_s\in B_Y and ∑s∈BN(v)Wsds=Uv−Vv\sum_{s\in B_N(v)}W_s d_s=U_v-V_v.

What Is Checked

The statements (6) and (7) concern finite cutoff evaluations of a tree of nonexpansive selfmaps of a convex set on a weighted ordered tree, with the subspace and diameter hypotheses in the first part. Every descendant block (3) is nonempty.✦