OctoInformBeta

OpenAI preprint, September 2026 · §4. The exact correction and copy hierarchy · §4

Lemma 4.3 [The detector bounds overloaded columns]: For a bounded support matrix and large KK, an overloaded column has detector at least 9/109/10; a positive multiplier caps a column’s heavy rows

Heavy rows raise the detector and light rows bound it.

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

The exact correction works on a matrix of transition weights between vertices, at a level ℓ\ell of the copy hierarchy, a hierarchy of levels in which level ℓ\ell has retention rate f=2−4ℓf = 2^{-4\ell}. A column of such a matrix is overloaded when too many of its rows carry a large entry, large meaning a fixed multiple of ff. The library tests a column yy for overload with a randomized detector over (ℤ/n)4(\mathbb{Z}/n)^4, for a prime nn. The question is what the detector’s value says about the number of rows at yy with a large entry, and what a positive multiplier of the correction, defined below for a stage, says about that number.

Channels, Boxes and Retained Vertices

Let Vn=(ℤ/n)4V_n = (\mathbb{Z}/n)^4.✦ A rank channel s=(a,b)s = (a, b) over nn is a pair of a nonzero vector a∈Vna \in V_n, its direction, and a vector b∈Vnb \in V_n, its offset✦; its point at a residue uu modulo nn is s(u)=b+uas(u) = b + u\,a✦.

The box side length at level ℓ\ell is m=⌊(n−1)/2ℓ⌋+1m = \lfloor (n-1)/2^\ell \rfloor + 1✦, and the box of level ℓ\ell is the set BℓB_\ell of vectors of VnV_n whose four coordinates have least nonnegative representatives below mm.✦ The hit probability pℓ=(m/n)4p_\ell = (m/n)^4 is the probability that a uniformly random vector of VnV_n lies in BℓB_\ell.✦

A finite set SS of natural numbers, the vertices, is legal for nn when S⊆{0,…,n−1}S \subseteq \{0, \dots, n-1\}; a vertex xx is read as a residue modulo nn.✦ For a channel ss, the retained vertices of SS at level ℓ\ell are those whose point on ss lies in the box: Rℓ(s)={x∈S:s(x)∈Bℓ}.R_\ell(s) = \{x \in S : s(x) \in B_\ell\}.(1)✦

Averages are plain means: 𝔼s\mathbb{E}_s is the mean over all rank channels ss.✦ A padded channel of level ℓ\ell is a pair (a,w)(a, w) of a nonzero direction a∈Vna \in V_n and a short offset w∈(ℤ/m)4w \in (\mathbb{Z}/m)^4, whose widening wˆ∈Vn\hat w \in V_n has as coordinates the least nonnegative representatives of those of ww.✦ For a column yy, the conditional average 𝔼t[φ(t)∣t(y)∈Bℓ]\mathbb{E}_t[\varphi(t) \mid t(y) \in B_\ell] of a real function φ\varphi of channels is the mean of φ(a,wˆ−ya)\varphi(a, \hat w - y\,a) over the padded channels (a,w)(a, w) of level ℓ\ell.✦

Heavy Rows and the Detector

The constants are A=1/4096A = 1/4096✦, δ=A/400\delta = A/400✦ and η(z)=z/1000\eta(z) = z/1000✦. For a real matrix GG on the vertices, the heavy rows and the light rows of SS at a column yy are HG(y)={x∈S:G(x,y)≥2δf},LG(y)={x∈S:G(x,y)>δf},H_G(y) = \{x \in S : G(x, y) \ge 2\delta f\}, \qquad L_G(y) = \{x \in S : G(x, y) > \delta f\},(2) and the overload threshold of a natural number JJ is ΛJ=128+4(J+1)\Lambda_J = 128 + 4(J+1).✦ The column yy is overloaded when |HG(y)|f≥ΛJ|H_G(y)|\,f \ge \Lambda_J.

Let c(x)=min⁡(1,max⁡(0,x))c(x) = \min(1, \max(0, x)) be the clamp of a real number to [0,1][0,1].✦ The fade function and the ramp from aa to bb are Φ(x)=12(c(2x)4+1−c(2−2x)4),Φa,b(x)=Φ(x−ab−a).\Phi(x) = \tfrac12\bigl(c(2x)^4 + 1 - c(2 - 2x)^4\bigr), \qquad \Phi_{a,b}(x) = \Phi\Bigl(\frac{x-a}{b-a}\Bigr).(3) The light ramp is λ=Φδ,2δ\lambda = \Phi_{\delta, 2\delta}✦, and the gate is g=1−Φη(δ),2η(δ)g = 1 - \Phi_{\eta(\delta), 2\eta(\delta)}.✦

The padded rank at depth KK of a real function φ\varphi on a finite set RR is its (K+1)(K+1)-st largest value, padded with 00: rk⁡K(φ;R)=max⁡({0}∪{φ(r):r∈R,|{r′∈R:φ(r′)≥φ(r)}|>K}).\operatorname{rk}_K(\varphi; R) = \max\Bigl(\{0\} \cup \bigl\{\varphi(r) : r \in R,\ |\{r' \in R : \varphi(r') \ge \varphi(r)\}| > K\bigr\}\Bigr).(4)✦

Fix natural numbers KK and JJ. The panel rank of a row xx under a channel tt is ρx(t)=rk⁡K(y′↦G(x,y′)/f;Rℓ(t))\rho_x(t) = \operatorname{rk}_K\bigl(y' \mapsto G(x, y')/f;\ R_\ell(t)\bigr)✦, and the throttle of the row is g(ρx(t))g(\rho_x(t)).✦ The mark of the entry (x,y)(x, y) under tt, and the score of the column yy under a pair of channels ss and tt, are μy(x,t)=λ(G(x,y)/f)g(ρx(t)),σy(s,t)=rk⁡J(x↦μy(x,t);Rℓ(s)).\mu_y(x, t) = \lambda\bigl(G(x, y)/f\bigr)\, g\bigl(\rho_x(t)\bigr), \qquad \sigma_y(s, t) = \operatorname{rk}_J\bigl(x \mapsto \mu_y(x, t);\ R_\ell(s)\bigr).(5)

The detector at a column yy is the mean score over a uniformly random channel ss and a channel tt conditioned on its point at yy lying in BℓB_\ell: UG(y)=𝔼t[𝔼sσy(s,t)|t(y)∈Bℓ].U_G(y) = \mathbb{E}_t\Bigl[\,\mathbb{E}_s\, \sigma_y(s, t) \mathrel{\Big|} t(y) \in B_\ell\Bigr].(6)✦ It depends also on nn, SS, ℓ\ell, KK and JJ.

Stages and Their Matrices

For finite sets SS and S′S' of vertices and reals ff and κ\kappa, a matrix CC is a bounded support matrix on SS with active set S′S', rate ff and bound κ\kappa when 0≤C(x,y)≤κf0 \le C(x, y) \le \kappa f for all xx and yy, every row weight ∑y∈SC(x,y)\sum_{y \in S} C(x, y) is at most κ\kappa, and C(x,y)>0C(x, y) > 0 only for xx and yy in S′S' with x<yx < y.✦ A stochastic step matrix on SS at rate ff is a bounded support matrix on SS with active set SS, rate ff and bound 11.✦

An iteration count TT is admissible when T>0T > 0 and (5/A)T/T!≤1/1024(5/A)^T/T! \le 1/1024.✦ Parameter constants are natural numbers TT, KK, JJ and MM, with TT an admissible iteration count, 128(1+32(T+1)/η(δ))≤K+1128\,(1 + 32(T+1)/\eta(\delta)) \le K + 1, a number of copies M>16(T+1)M > 16(T+1), and 64M(T+1)2≤δ(J+1)64\,M\,(T+1)^2 \le \delta\,(J+1).✦ A stage consists of parameter constants, a level ℓ\ell, a finite set SS of vertices and a matrix CC of transition weights✦; its rate is the rate ff of the level.

For matrices FF and CC on SS, the combined matrix of FF and CC is C+FCC + FC, where the product is taken over SS: (FC)(x,y)=∑z∈SF(x,z)C(z,y)(FC)(x, y) = \sum_{z \in S} F(x, z)\,C(z, y).✦

The pilot pairs (Vk,Ek)(V_k, E_k) of a stage, each a real vector and a matrix, start from the zero vector and the zero matrix and are advanced step by step by the update rule of the stage; VkV_k is the probed vector of step kk.✦ With the cutoff γ=1−Φ1/2,4/5\gamma = 1 - \Phi_{1/2, 4/5}✦, the pilot multiplier of step kk at a vertex yy is γ(Vk(y))\gamma(V_k(y)), and the actual multiplier is γ(VT(y))\gamma(V_T(y)). The correction matrices FkF_k start from F0=0F_0 = 0, and Fk+1F_{k+1} is the entrywise correction at scale ff of the combined matrix C+FkCC + F_k C with weights γ(VT(⋅))\gamma(V_T(\cdot)). The test matrix and the next matrix of step kk are Gk′=C+EkC,Gk=C+FkC.G'_k = C + E_k C, \qquad G_k = C + F_k C.(7)

The Claim

Theorem 1. Let nn be a prime, SS a finite set of vertices, GG a real matrix, ℓ\ell a level with rate f=2−4ℓf = 2^{-4\ell}, KK and JJ natural numbers, and yy a column. Suppose that SS is legal for nn, that 2ℓ≤n2^\ell \le n and y∈Sy \in S, and that GG is a bounded support matrix on SS, with some active set, at rate ff and with bound κ\kappa. If 128(1+32κ/η(δ))≤K+1128\,(1 + 32\kappa/\eta(\delta)) \le K + 1 and the column yy is overloaded, then UG(y)≥910.U_G(y) \ge \frac{9}{10}.(8)✦ Without any of these hypotheses, (J+1)UG(y)≤|LG(y)|pℓ.(J+1)\,U_G(y) \le |L_G(y)|\,p_\ell.(9)✦ Now let a stage have constants TT, KK, JJ, MM, level ℓ\ell, a legal set SS with 2ℓ≤n2^\ell \le n, and a stochastic step matrix CC on SS at rate ff, and let k<Tk < T and y∈Sy \in S. If the pilot multiplier γ(Vk+1(y))\gamma(V_{k+1}(y)) is positive, then |HGk′(y)|f≤ΛJ,|H_{G'_k}(y)|\,f \le \Lambda_J,(10)✦ and if the actual multiplier γ(VT(y))\gamma(V_T(y)) is positive, then |HGk(y)|f≤ΛJ.|H_{G_k}(y)|\,f \le \Lambda_J.(11)✦

In the paper, the result reads: with Drow=1+CpairT/η−D_{\mathrm{row}} = 1 + C_{\mathrm{pair}}\,T/\eta_-, K≥160DrowK \ge 160\,D_{\mathrm{row}} and R*≥cπ−1max⁡(4J,40Cvar)R_* \ge c_\pi^{-1}\max(4J, 40\,C_{\mathrm{var}}), if more than R*/fR_*/f rows xx have Gi(x,y)≥δ1fG_i(x, y) \ge \delta_1 f then Ui(y)≥19/20U_i(y) \ge 19/20, if Ui(y)>1/4U_i(y) > 1/4 then more than J/(4Cπf)J/(4C_\pi f) rows xx have Gi(x,y)>δ0fG_i(x, y) > \delta_0 f, and a positive pilot or actual multiplier at yy leaves at most R*/fR_*/f rows xx with Gi(x,y)≥δ1fG_i(x, y) \ge \delta_1 f, respectively with Gi′(x,y)≥δ1fG'_i(x, y) \ge \delta_1 f, where TT stands for the paper’s k*k_*; UiU_i, GiG_i and Gi′G'_i are its detector and matrices; δ0f\delta_0 f and δ1f\delta_1 f are its two thresholds; R*R_* is its row bound and DrowD_{\mathrm{row}} the quantity defined above; and CpairC_{\mathrm{pair}}, η−\eta_-, cπc_\pi, CvarC_{\mathrm{var}} and CπC_\pi are its constants.

What Is Checked

The four statements (8), (9), (10) and (11) are stated over the detector (6), built from rank channels over (ℤ/n)4(\mathbb{Z}/n)^4, the retained vertices, padded ranks, marks and scores; over the heavy and light rows (2) of a column; over bounded support and stochastic step matrices; and over the test and next matrices (7) of a stage with its pilot and actual multipliers.