OctoInformBeta

OpenAI preprint, September 2026 · §7. Annealing and learning the multipliers · §7

Annealing schedule, estimation and accuracy: The cooling schedule, the chance a phase fails, multipliers that stay good, and the error bounds behind a (1±ε)(1\pm\varepsilon) estimate of ZZ

Annealing schedule and error bounds for counting common bases.

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 M1M_1 and M2M_2 be matroids on [n]={1,…,n}[n]=\{1,\dots,n\} of equal rank, queried through one independence oracle, and let ZZ be the number of their common bases: the sets A⊆[n]A\subseteq[n] that are a base of M1M_1 and a base of M2M_2.✦ The approximate counter for ZZ works on the paired ground set VV, two copies of [n][n], with the paired slots: the list of the nn pairs (i,i′)(i,i') that join an element ii of the first copy to its copy i′i' in the second.✦ The paired matroid on VV is M1⊕M2*M_1\oplus M_2^{*}, the direct sum of M1M_1 on the first copy and the dual of M2M_2 on the second.✦

For a matroid MM on a finite set Γ\Gamma, a natural number nn and a real number qq, the matroid weight of a set S⊆ΓS\subseteq\Gamma is fq(S)=qn−r(S),f_q(S)=q^{\,n-r(S)},(1)✦ where rr is the rank function of MM and the exponent is 00 when r(S)>nr(S)>n. For the paired matroid, c0(q)c_0(q) is the sum of fq(S)f_q(S) over the 2n2^n sets S⊆VS\subseteq V that contain exactly one element of each pair (i,i′)(i,i').

The annealing lowers qq geometrically from 11 over LL phases. In each phase a Metropolis chain weighted by fqf_q runs for NN steps; from the averages along the run of a few functions of the state, the phase estimates one ratio and retunes the multipliers, the positive factors the chain places on its states with one pair empty and another full, for the next phase. The estimate Zˆ\widehat Z of ZZ is built from the product of the LL ratios. Below, the schedule is fixed and the errors of a run are bounded, together with a purely numerical inequality, part (a) of the theorem.

States and Weights of a Phase

A phase works over a finite set Γ\Gamma with a list 𝒫\mathcal P of nn pairs {xi,yi}\{x_i,y_i\} of elements of Γ\Gamma; for the matroid, Γ=V\Gamma=V and 𝒫\mathcal P is the paired slots. A list 𝒫\mathcal P of nn pairs of elements of Γ\Gamma is fresh when its 2n2n entries are distinct, and covers Γ\Gamma when every element of Γ\Gamma is an entry of one of its pairs.

A pair is single in a set S⊆ΓS\subseteq\Gamma when SS contains exactly one of its entries✦, full when SS contains both✦, and empty when SS contains neither✦. A plain state of 𝒫\mathcal P is a set S⊆ΓS\subseteq\Gamma in which every listed pair is single.✦ A defect type is an ordered pair (p,r)(p,r) of distinct pairs of 𝒫\mathcal P✦, and a defect state of type (p,r)(p,r) is a set S⊆ΓS\subseteq\Gamma in which pp is empty, rr is full and every other listed pair is single✦. The chain state space Ω\Omega of 𝒫\mathcal P is the set of its plain and defect states.✦

A real function ff on the subsets of Γ\Gamma is read as the multiaffine polynomial on ℝΓ\mathbb R^\Gamma whose coefficient function is ff. The slot total ∂𝒫f\partial_{\mathcal P}f of ff along 𝒫=(p1,…,pn)\mathcal P=(p_1,\dots,p_n) is the iterated derivative ∂𝒫f=D𝟏p1D𝟏p2⋯D𝟏pnf,\partial_{\mathcal P}f=D_{\mathbf 1_{p_1}}D_{\mathbf 1_{p_2}}\cdots D_{\mathbf 1_{p_n}}f,(2)✦ where DaD_a is the derivative along a vector a∈ℝΓa\in\mathbb R^\Gamma and 𝟏p\mathbf 1_{p} is the indicator vector of the two entries of the pair pp. When the pairs are disjoint and avoid a set AA, (∂𝒫f)(A)(\partial_{\mathcal P}f)(A) is the sum of ff over the sets that add to AA one entry of each pair. Write c0=(∂𝒫f)(∅)c_0=(\partial_{\mathcal P}f)(\emptyset), which is c0(q)c_0(q) for the paired slots and f=fqf=f_q. For a defect type (p,r)(p,r), the slot defect cprc_{pr} is the slot total along 𝒫\mathcal P with pp and rr removed, evaluated at the set consisting of both entries of rr.✦

The face Hessian HA(g)H_A(g) of a real function gg on the subsets of Γ\Gamma at a set A⊆ΓA\subseteq\Gamma is the symmetric matrix indexed by Γ\A\Gamma\setminus A with zero diagonal and entry g(A∪{i,j})g(A\cup\{i,j\}) at distinct ii and jj.✦ A bilinear form BB on a real vector space has one positive direction when every ee with B(e,e)>0B(e,e)>0 gives B(v,v)≤0B(v,v)\le 0 for all vv with B(v,e)=0B(v,e)=0; for a symmetric form this is the condition of at most one positive eigenvalue.✦ A function ff on the subsets of Γ\Gamma has the slot signature property when, for every list 𝒬\mathcal Q of pairs of elements of Γ\Gamma and every A⊆ΓA\subseteq\Gamma, the bilinear form of the face Hessian HA(∂𝒬f)H_A(\partial_{\mathcal Q}f) has one positive direction.✦

Multipliers are positive reals wprw_{pr}, one for each defect type. The multiplier m(S)m(S) of a set SS is wprw_{pr} when SS is a defect state of type (p,r)(p,r) and 11 otherwise✦; its chain weight and the total chain weight are ω(S)=m(S)f(S),W=∑S∈Ωω(S).\omega(S)=m(S)\,f(S),\qquad W=\sum_{S\in\Omega}\omega(S).(3) Multipliers wprw_{pr} are good for ff when they satisfy the lower half c0/(4cpr)≤wprc_0/(4c_{pr})\le w_{pr} and the upper half wpr≤4c0/cprw_{pr}\le 4c_0/c_{pr} for every defect type (p,r)(p,r).

The Metropolis Chain

A lazy reversible chain on a finite set XX is a transition matrix PP on XX, with nonnegative entries and rows summing to 11, together with a strictly positive distribution π\pi on XX, such that π(x)P(x,y)=π(y)P(y,x)\pi(x)P(x,y)=\pi(y)P(y,x) for all x,y∈Xx,y\in X and P(x,x)≥1/2P(x,x)\ge 1/2 for every xx.✦ Given a strictly positive distribution π\pi on a finite set XX and moves K(x,y)≥0K(x,y)\ge 0 on XX that satisfy π(x)K(x,y)=π(y)K(y,x)\pi(x)K(x,y)=\pi(y)K(y,x) and sum to at most 1/21/2 along each row, the chain from the moves KK is the lazy reversible chain on XX with stationary distribution π\pi that goes from xx to y≠xy\ne x with probability K(x,y)K(x,y) and stays at xx with the remaining probability.✦

Two sets S,T⊆ΓS,T\subseteq\Gamma are exchange adjacent when S=A∪{a}S=A\cup\{a\} and T=A∪{b}T=A\cup\{b\} for a set AA and distinct elements a,b∉Aa,b\notin A.✦ The Metropolis move kernel on Ω\Omega is K(S,T)={min⁡(ω(S),ω(T))2n2ω(S)if S and T are exchange adjacent,0otherwise.K(S,T)= \begin{cases} \dfrac{\min(\omega(S),\omega(T))}{2n^2\,\omega(S)} & \text{if $S$ and $T$ are exchange adjacent,}\\[1ex] 0 & \text{otherwise.} \end{cases}(4)✦ When 𝒫\mathcal P is a nonempty fresh list covering Γ\Gamma and the multipliers and ff are positive, the Metropolis chain is the chain from the moves KK on Ω\Omega with stationary distribution π(S)=ω(S)/W\pi(S)=\omega(S)/W.✦

An observable is a real function hh on Ω\Omega; its stationary mean is π(h)=∑S∈Ωπ(S)h(S)\pi(h)=\sum_{S\in\Omega}\pi(S)h(S).✦ For a real function gg on the subsets of Γ\Gamma, the phase observables are the indicator of the plain states, the defect indicator 𝟏pr\mathbf 1_{pr} of the defect states of type (p,r)(p,r) for each defect type, and the plain observable of gg, equal to gg on plain states and to 00 elsewhere.✦

Along a path of states, the path sum of hh is the sum of its values at the entries, a repeated state counted each time, and the path average h‾\bar h is the path sum over the number of entries.✦ For a nonnegative function ν\nu on Ω\Omega and an event EE on paths, the probability of EE over NN steps from ν\nu is Prν[E]=∑S∈Ων(S)𝔼S[𝟏E],\Pr_\nu[E]=\sum_{S\in\Omega}\nu(S)\,\mathbb E_S[\mathbf 1_E],(5)✦ where the path expectation 𝔼S[F]\mathbb E_S[F] of a function FF of paths is the expected value of FF on the path of the first NN steps of the chain from SS, the starting state included✦.

The Claim

Definition 1. For a positive integer nn and a natural number bb, the annealing ratio and the number of phases are ρn=1−12n,\rho_n=1-\frac{1}{2n},(6)✦ L=2n(n+b).L=2n(n+b).(7)✦ For an accuracy ε\varepsilon and a number LL of phases, the annealing tolerance is η=ε32(L+1).\eta=\frac{\varepsilon}{32(L+1)}.(8)✦ For a matroid MM on Γ\Gamma, the annealed weight of phase jj is the matroid weight (1) at q=ρnjq=\rho_n^{\,j}: f(j)=fρnj.f^{(j)}=f_{\rho_n^{\,j}}.(9)✦

Theorem 1. (a) For every positive integer nn and every natural number LL, exp⁡(−20n4(n(L+1)+2)/(18n4))2−n(L+1)≤12.\frac{\exp\bigl(-20n^4(n(L+1)+2)/(18n^4)\bigr)}{2^{-n(L+1)}}\le\frac12.(10)✦

(b) Let 𝒫\mathcal P be a nonempty fresh list of nn pairs covering Γ\Gamma, let ff be a positive function with the slot signature property, let the multipliers be positive and good for ff, and let gg satisfy 1/2≤g(S)≤11/2\le g(S)\le 1 on plain states. Let ν\nu be a nonnegative function on Ω\Omega with ν≤10n2π\nu\le 10n^2\pi, let LL be a natural number, let η>0\eta>0, and let NN be a natural number with N≥1010(L+1)n14/η2N\ge 10^{10}(L+1)\,n^{14}/\eta^2. Then the Metropolis chain run for NN steps from ν\nu satisfies, over the phase observables hh of gg, Prν[|h‾−π(h)|>ηπ(h) for some h]≤132(L+1).\Pr_\nu\bigl[\,|\bar h-\pi(h)|>\eta\,\pi(h)\text{ for some }h\,\bigr]\le\frac{1}{32(L+1)}.(11)✦

(c) Let ww, p0p_0, ptp_t and w*w^* be positive reals with wp0/pt=w*w\,p_0/p_t=w^*, let 0≤η≤1/30\le\eta\le 1/3, let (1−η)p0≤pˆ0≤(1+η)p0(1-\eta)p_0\le\hat p_0\le(1+\eta)p_0 and (1−η)pt≤pˆt≤(1+η)pt(1-\eta)p_t\le\hat p_t\le(1+\eta)p_t, and let w*/2≤w+≤2w*w^*/2\le w^+\le 2w^*. Then w+4≤wpˆ0pˆt≤4w+.\frac{w^+}{4}\le w\,\frac{\hat p_0}{\hat p_t}\le 4w^+.(12)✦

(d) Let 0<ε<10<\varepsilon<1, let LL be a natural number and η\eta the tolerance (8). If reals a0,…,aL−1a_0,\dots,a_{L-1} satisfy (1−η)/(1+η)≤aj≤(1+η)/(1−η)(1-\eta)/(1+\eta)\le a_j\le(1+\eta)/(1-\eta), then 1−ε4≤∏j=0L−1aj≤1+ε4.1-\frac{\varepsilon}{4}\le\prod_{j=0}^{L-1}a_j\le 1+\frac{\varepsilon}{4}.(13)✦

(e) Let M1M_1 and M2M_2 be matroids on [n][n] of equal rank and let 0≤q≤10\le q\le 1. Then Z≤c0(q)≤Z+2nq.Z\le c_0(q)\le Z+2^n q.(14)✦

(f) Let 0<ε<10<\varepsilon<1, and let Z≥0Z\ge 0, CC and Zˆ\widehat Z be reals with Z≤C≤(1+ε/10)ZZ\le C\le(1+\varepsilon/10)Z and (1−ε/4)C≤Zˆ≤(1+ε/4)C(1-\varepsilon/4)C\le\widehat Z\le(1+\varepsilon/4)C. Then (1−ε)Z≤Zˆ≤(1+ε)Z.(1-\varepsilon)Z\le\widehat Z\le(1+\varepsilon)Z.(15)✦

What Is Checked

The claim is stated over the schedule (6), (7), (8) and the annealed weights (9); over the plain and defect states of a list of pairs, its slot totals c0c_0 and cprc_{pr}, the slot signature property and the chain weights (3); over the Metropolis chain from the moves (4), its phase observables and the probability (5) of a path event; and over the paired matroid, the matroid weight (1) and the number ZZ of common bases.

For positive multipliers and a positive ff, the library shows that the Metropolis moves are nonnegative✦ and satisfy detailed balance, π(S)K(S,T)=π(T)K(T,S)\pi(S)K(S,T)=\pi(T)K(T,S)✦; for a nonempty fresh list covering Γ\Gamma, it shows that the moves out of any state sum to at most 1/21/2✦.