OctoInformBeta

OpenAI preprint, September 2026 · §8. Oracle implementation, bit bounds, and amplification · §8

Oracle ranks, fair bits and amplification: One run on fair bits is ε\varepsilon-accurate with probability at least 11/1611/16, and the median of enough runs with probability at least 1−δ1-\delta

Oracle ranks are exact and medians of fair runs accurate.

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 of equal rank on [n]={0,…,n−1}[n]=\{0,\dots,n-1\}, each with ground set all of [n][n]. A common base is a subset of [n][n] that is a base of M1M_1 and of M2M_2, and ZZ is the number of common bases.✦ A fully polynomial randomized approximation scheme (FPRAS) for ZZ reaches the matroids only through an independence oracle and gets its randomness only from fair coins. Running the annealing estimator for ZZ in this model means computing ranks from the oracle with few queries and drawing each of its random choices from fair bits; the success probability of one such run, a constant, is then lifted to 1−δ1-\delta, for a given δ>0\delta>0, by a median of independent runs.

An independence oracle OO on [n][n] takes a selector i∈{1,2}i\in\{1,2\} and the indicator vector of a subset A⊆[n]A\subseteq[n] and answers yes or no.✦ An independence oracle OO on [n][n] is exact for matroids M1M_1 and M2M_2 on [n][n] when, for i∈{1,2}i\in\{1,2\} and every A⊆[n]A\subseteq[n], O(i,A)O(i,A) answers yes precisely when AA is independent in MiM_i.✦

A rational zz is ε\varepsilon-accurate for ZZ when (1−ε)Z≤z≤(1+ε)Z(1-\varepsilon)Z\le z\le(1+\varepsilon)Z.✦ The uniform average of a real function gg on a finite set XX is 𝔼x∈Xg(x)=1|X|∑x∈Xg(x),\mathbb E_{x\in X}\,g(x)=\frac{1}{|X|}\sum_{x\in X}g(x),(1)✦ and Pr⁡x∈X[E]\Pr_{x\in X}[E] is the uniform average of the indicator of an event EE. The probabilities below are taken over a finite set XX of tables of fair bits, a table being an array of bit words on which a draw tree is run.

Ranks from the Oracle

For i∈{1,2}i\in\{1,2\} and S⊆[n]S\subseteq[n], the greedy scan of SS starts from the empty set and takes the elements of SS one at a time, from the largest to the smallest, adding an element ee to the current set II when O(i,I∪{e})O(i,I\cup\{e\}) answers yes.✦ The oracle rank rˆi(S)\hat r_i(S) is the size of the set the scan ends with, and ri(S)r_i(S) is the rank of SS in MiM_i.✦

For natural numbers kk and ss, a machine with k+8k+8 registers and labels 0,…,s0,\dots,s keeps a stack of bits in each register and runs a program, which assigns to each label one of five instructions: push a bit on a register and go to a given label; pop a register and go to one of three labels according as it was empty or its top bit was 00 or 11; toss a fair coin and go to one of two labels on the outcome; query O(i,⋅)O(i,\cdot) on the word in a register, position jj marking element jj and missing positions marking nothing, and go to one of two labels on the answer; or halt. A configuration CC of the machine consists of the contents of the registers, the current label, an optional rational output, absent at first, and the numbers of oracle calls and of bit operations made so far.✦ The execution of a program PP with oracle OO from a configuration CC on coin bits β=(β0,β1,…)\beta=(\beta_0,\beta_1,\dots) is the sequence of configurations with C0=CC_0=C and Ct+1C_{t+1} obtained from CtC_t by one step of PP with βt\beta_t as the coin.✦

Programs are put together by concatenation: a program with labels 0,…,s0,\dots,s followed by one with labels 0,…,t0,\dots,t gives a program with labels 0,…,s+t0,\dots,s+t that runs the first below ss and, from ss on, the second with its jump targets shifted up by ss.✦ The rank program PiP_i is the concatenation of a greedy program, built around two register copies, and a counting program, built around a binary increment.✦ It reads the indicator word x∈{0,1}nx\in\{0,1\}^n of SS from an input register and uses four further registers as work space. The greedy program runs the greedy scan on words: for each 11 of xx it queries O(i,⋅)O(i,\cdot) on that element together with the elements accepted so far, and it writes the answers, with a 00 for each 00 of xx, into an acceptance word ai(x)a_i(x). The counting program writes the number of 11s of ai(x)a_i(x) in binary, least significant bit first, as the word bin⁡i(x)\operatorname{bin}_i(x); the binary value of a word ww is val⁡(w)=∑jwj2j\operatorname{val}(w)=\sum_j w_j2^j.✦ The rank time Ti(x)T_i(x) and the rank work Wi(x)W_i(x) of xx are Ti(x)=1+∑j(3+(6n+2)xj)+τ(ai(x)),Wi(x)=1+∑j(3+(8n+2)xj)+τ(ai(x)),T_i(x)=1+\sum_{j}\bigl(3+(6n+2)x_j\bigr)+\tau\bigl(a_i(x)\bigr),\qquad W_i(x)=1+\sum_{j}\bigl(3+(8n+2)x_j\bigr)+\tau\bigl(a_i(x)\bigr),(2) where τ(a)=1+n+∑(4ℓ+3)\tau(a)=1+n+\sum(4\ell+3), the sum running over the 11s of aa, with ℓ\ell the number of low-order ones of the binary counter of the counting program that the 11 increments.✦

Draws from Fair Bits

A random draw tree with outcomes in a set AA is either a leaf holding an outcome a∈Aa\in A, or a draw node with a bound vv that picks a number among 0,…,v0,\dots,v uniformly at random and continues with the subtree attached to that number.✦ The binding of a tree tt with outcomes in AA and a function kk that gives each a∈Aa\in A a tree is the tree obtained from tt by replacing each leaf aa by the tree k(a)k(a).✦ The mapping of tt by a function hh is the tree that relabels each outcome aa as h(a)h(a).✦ The optional binding of a tree tt with optional outcomes and a function kk that gives each nonempty outcome aa a tree is the tree obtained from tt by replacing each leaf with a nonempty outcome aa by the tree k(a)k(a), an empty outcome being a failure that is kept.✦

The rational coin with parameters α\alpha and vv is a single draw node with bound vv whose leaf for each u∈{0,…,v}u\in\{0,\dots,v\} shows whether u<αu<\alpha.✦ The Bernoulli tree of a rational pp is the rational coin with α\alpha the absolute value of the numerator of pp and vv its denominator minus one, a coin of bias pp when 0≤p≤10\le p\le1.✦ The uniform choice on a nonempty finite set AA is a single draw node with bound |A|−1|A|-1 whose leaves enumerate AA.✦ For repeated draws, the chain sample tree of a kernel, which gives for each state a tree of the next state, runs kk steps from a state xx and returns the trajectory (x0,…,xk)(x_0,\dots,x_k) with x0=xx_0=x✦; the history tree of a kernel on lists runs kk rounds, each drawing a value from the kernel at the list built so far and appending it, and fails as soon as one round fails.✦

A tree is run on a table of bit words of one length, with one row per draw and a fixed number of attempts in each row. A leaf returns its outcome. A draw node with bound vv reads the first ⌈log⁡2(v+1)⌉\lceil\log_2(v+1)\rceil bits of each word of the current row as rejection-sampling attempts, takes the first accepted value and continues with its subtree on the remaining rows. The run gives no value when the rows run out, the words are too short, or every attempt of a row is rejected.

The Estimator

The estimator works on the paired ground set V=[n]⊔[n]V=[n]\sqcup[n], with ii and i′i' the two copies of i∈[n]i\in[n] and the slot pairs {i,i′}\{i,i'\} listed for i=0,…,n−1i=0,\dots,n-1✦, and on the paired matroid K=M1⊕M2*K=M_1\oplus M_2^{*}, the direct sum of M1M_1 on the first copy and the dual of M2M_2 on the second✦; rKr_K is the rank of KK.

For a list 𝒫\mathcal P of disjoint pairs in a finite set Γ\Gamma, here VV with the slot pairs, a pair is empty, single or full in a subset SS of Γ\Gamma when SS contains none, exactly one or both of its entries. A plain state of 𝒫\mathcal P is a subset of Γ\Gamma in which every pair of 𝒫\mathcal P is single✦, and a defect state for two distinct pairs pp and rr of 𝒫\mathcal P is a subset in which pp is empty, rr is full and every other pair is single.✦ The chain state space Ω\Omega consists of the plain and the defect states. An exchange choice for SS is a pair (x,y)(x,y) with x∈Sx\in S and y∉Sy\notin S✦; it exchanges SS for S−x+yS-x+y.✦

Multipliers w=(wpr)w=(w_{pr}) are numbers indexed by ordered pairs of pairs. For multipliers ww and a phase index jj, a natural number counting the annealing phases of the estimator, the anneal weight and the chain weight of S∈ΩS\in\Omega are fj(S)=ρj(n−rK(S)),πw,j(S)=μw(S)fj(S),ρ=1−12n,f_j(S)=\rho^{\,j\,(n-r_K(S))},\qquad \pi_{w,j}(S)=\mu_w(S)\,f_j(S),\qquad \rho=1-\frac{1}{2n},(3) where μw(S)=wpr\mu_w(S)=w_{pr} when SS is a defect state for pp and rr, and μw(S)=1\mu_w(S)=1 when SS is plain.✦

For a weight π\pi on Ω\Omega, the Metropolis step from S∈ΩS\in\Omega stays at SS with probability 1/21/2; otherwise it picks an exchange choice (x,y)(x,y) for SS uniformly, and when T=S−x+yT=S-x+y is a chain state it moves to TT with probability min⁡{1,π(T)/π(S)}\min\{1,\pi(T)/\pi(S)\}, staying at SS otherwise.✦

The empirical mean of a function hh on sets over a list ℓ\ell of sets is 𝔼ˆℓh=|ℓ|−1∑S∈ℓh(S)\widehat{\mathbb E}_\ell h=|\ell|^{-1}\sum_{S\in\ell}h(S), counted with multiplicity; a condition in brackets, as in [S plain][S\text{ plain}], stands for the function of SS that is 11 when the condition holds and 00 otherwise.✦ The learned update of multipliers ww along ℓ\ell is wpr′=wpr𝔼ˆℓ[S plain]𝔼ˆℓ[S a defect state for p,r]w'_{pr}=w_{pr}\,\frac{\widehat{\mathbb E}_\ell[S\text{ plain}]} {\widehat{\mathbb E}_\ell[S\text{ a defect state for }p,r]}(4) for distinct pairs p≠rp\ne r of the list, the other entries staying unchanged. The stored multipliers w(j)w^{(j)} start from wpr(0)=4w^{(0)}_{pr}=4 and are updated by (4) along the sets of the trajectories of phases 0,…,j−10,\dots,j-1 in turn.

One run of the estimator has LL phases, with NN chain states in each. Phase jj, given the trajectories σ0,…,σj−1\sigma_0,\dots,\sigma_{j-1} of the earlier phases, fails unless every stored multiplier wpr(i)w^{(i)}_{pr} with i≤ji\le j is positive; otherwise it takes a start state from the restart procedure at jj and runs N−1N-1 Metropolis steps for the weight πw(j),j\pi_{w^{(j)},j} of (3), recording the trajectory σj\sigma_j of NN states.✦ The restart procedure draws a uniform plain state at 00, and passes from jj to j+1j+1 by θ\theta capped rounds at phase j+1j+1, with cap RR✦, where θ=20n4(n(L+1)+2),R=2000(L+1)2n2θ.\theta=20n^4\bigl(n(L+1)+2\bigr),\qquad R=2000\,(L+1)^2n^2\,\theta.(5)✦ After the LL phases, with every stored multiplier positive, the restart procedure at LL gives a plain state xx. The run outputs the annealing estimate Zˆ(σ)=2n∏j=0L−1𝔼ˆσj[ρn−rK(S)[S plain]]𝔼ˆσj[S plain]\hat Z(\sigma)=2^n\prod_{j=0}^{L-1}\frac{\widehat{\mathbb E}_{\sigma_j}\bigl[\rho^{\,n-r_K(S)} [S\text{ plain}]\bigr]}{\widehat{\mathbb E}_{\sigma_j}[S\text{ plain}]}(6) when xx has rank nn in KK, and 00 otherwise.✦

The run is a draw tree: the history tree of its LL phases, each a chain sample tree of Metropolis steps whose laziness and acceptance are Bernoulli trees and whose exchange choice and initial plain state are uniform choices.

For a rational ε\varepsilon with bεb_\varepsilon binary digits in the denominator of its lowest terms, the anneal length, the tolerance, the accuracy exponent and the sample count are L(n,b)=2n(n+b),η(ε,L)=ε32(L+1),e(ε)=bε+5,N(n,L,ε)=1014(L+1)3n14⌈1/ε⌉2+1.L(n,b)=2n(n+b),\quad \eta(\varepsilon,L)=\frac{\varepsilon}{32(L+1)},\quad e(\varepsilon)=b_\varepsilon+5,\quad N(n,L,\varepsilon)=10^{14}(L+1)^3n^{14}\lceil1/\varepsilon\rceil^2+1.(7) With θ\theta and RR from (5), the fair bank ℬn,N,L\mathcal B_{n,N,L} is the set of tables of DD rows, each of D+6D+6 words of HH bits, where D=(L+1)(1+3L(R+1)θ+3N),H=2(2+NL+2n2L)+n2+n+4.D=(L+1)\bigl(1+3L(R+1)\theta+3N\bigr),\qquad H=2\bigl(2+NL+2n^2L\bigr)+n^2+n+4.(8)✦ The output YN,L(ω)Y_{N,L}(\omega) of one run on ω∈ℬn,N,L\omega\in\mathcal B_{n,N,L} is the value of the run’s tree on ω\omega, with at most DD draws, and 00 when it gives no value.✦

The median med⁡(y1,…,ym)\operatorname{med}(y_1,\dots,y_m) of rationals is the entry at position ⌊m/2⌋\lfloor m/2\rfloor, counting from 00, of the list sorted in increasing order.✦ For a rational δ>0\delta>0 with bδb_\delta binary digits in the denominator of its lowest terms, the repetition count is m(δ)=64(bδ+1).m(\delta)=64\,(b_\delta+1).(9)✦ The FPRAS bank ℬn,ε,δ\mathcal B_{n,\varepsilon,\delta} is the set of m(δ)m(\delta)-tuples of tables of the fair bank ℬn,N,L\mathcal B_{n,N,L} with L=L(n,e(ε))L=L(n,e(\varepsilon)) and N=N(n,L,ε)N=N(n,L,\varepsilon).✦ The bounded output on ω=(ω1,…,ωm(δ))\omega=(\omega_1,\dots,\omega_{m(\delta)}) is the median of the runs, Zˆε,δ(ω)=med⁡(YN,L(ω1),…,YN,L(ωm(δ)))\hat Z_{\varepsilon,\delta}(\omega)=\operatorname{med}\bigl(Y_{N,L}(\omega_1),\dots, Y_{N,L}(\omega_{m(\delta)})\bigr).

The Claim

Theorem 1. Let M1M_1 and M2M_2 be matroids on [n][n], each with ground set all of [n][n], with ZZ common bases.

(a) If OO is an independence oracle exact for M1M_1 and M2M_2, then for i∈{1,2}i\in\{1,2\} and every S⊆[n]S\subseteq[n], rˆi(S)=ri(S).\hat r_i(S)=r_i(S).(10)✦

(b) Let OO be an independence oracle exact for M1M_1 and M2M_2, let S⊆[n]S\subseteq[n] have indicator word xx, and let C0C_0 be a configuration of the machine at label 00 with xx in the input register, the work registers empty, any words in the other registers, and qq oracle calls and cc bit operations on its counters. Then for i∈{1,2}i\in\{1,2\} and every sequence β\beta of coin bits, the execution of PiP_i with oracle OO from C0C_0 on β\beta satisfies, with the rank time and the rank work of (2), CTi(x) is at the halting label, with bin⁡i(x) in the input register,q+|S| oracle calls and c+Wi(x) bit operations, and val⁡(bin⁡i(x))=ri(S).\begin{aligned} &C_{T_i(x)}\text{ is at the halting label, with }\operatorname{bin}_i(x)\text{ in the input register,}\\ &q+|S|\text{ oracle calls and }c+W_i(x)\text{ bit operations, and } \operatorname{val}\bigl(\operatorname{bin}_i(x)\bigr)=r_i(S). \end{aligned}(11)✦

(c) Let n>0n>0, let M1M_1 and M2M_2 have equal rank, let 0<ε<10<\varepsilon<1 be rational, let bb be a natural number with 2−b≤ε/102^{-b}\le\varepsilon/10, put L=L(n,b)L=L(n,b), and let NN be a natural number with N≥1010(L+1)n14/η(ε,L)2N\ge10^{10}(L+1)\,n^{14}/\eta(\varepsilon,L)^2. Then Prω∈ℬn,N,L[(1−ε)Z≤YN,L(ω)≤(1+ε)Z]≥1116.\Pr_{\omega\in\mathcal B_{n,N,L}}\bigl[(1-\varepsilon)Z\le Y_{N,L}(\omega)\le(1+\varepsilon)Z\bigr] \ge\frac{11}{16}.(12)✦

(d) Let XX be a nonempty finite set, g:X→ℚg\colon X\to\mathbb Q a function, y−y_- and y+y_+ rationals, and δ>0\delta>0 a rational with repetition count m(δ)m(\delta) as in (9). If Pr⁡x∈X[g(x)∉[y−,y+]]≤5/16\Pr_{x\in X}\bigl[g(x)\notin[y_-,y_+]\bigr]\le5/16, then Pr(x1,…,xm(δ))∈Xm(δ)[y−≤med⁡(g(x1),…,g(xm(δ)))≤y+]≥1−δ.\Pr_{(x_1,\dots,x_{m(\delta)})\in X^{m(\delta)}}\Bigl[y_-\le\operatorname{med}\bigl(g(x_1),\dots, g(x_{m(\delta)})\bigr)\le y_+\Bigr]\ge1-\delta.(13)✦

(e) Let n>0n>0, let M1M_1 and M2M_2 have equal rank, and let 0<ε<10<\varepsilon<1 and δ>0\delta>0 be rationals. Then Zˆε,δ(ω)≥0 for every ω∈ℬn,ε,δ, and Zˆε,δ(ω)=0 for every ω when Z=0,Prω∈ℬn,ε,δ[(1−ε)Z≤Zˆε,δ(ω)≤(1+ε)Z]≥1−δ.\begin{aligned} &\hat Z_{\varepsilon,\delta}(\omega)\ge0\text{ for every }\omega\in\mathcal B_{n,\varepsilon,\delta}, \text{ and }\hat Z_{\varepsilon,\delta}(\omega)=0\text{ for every }\omega\text{ when }Z=0,\\ &\Pr_{\omega\in\mathcal B_{n,\varepsilon,\delta}}\bigl[(1-\varepsilon)Z\le \hat Z_{\varepsilon,\delta}(\omega)\le(1+\varepsilon)Z\bigr]\ge1-\delta. \end{aligned}(14)✦

In the paper, the result reads: ranks come from the oracle by a greedy scan with at most nn queries, the exact rational choices of the algorithm come from fair bits with a bounded number of trials, and the output is the median of 10bδ+110b_\delta+1 independent bounded runs.

What Is Checked

The claims are stated over matroids M1M_1 and M2M_2 on [n][n] with ground set [n][n] and their number ZZ of common bases; over an exact independence oracle, the oracle rank and the rank program with its rank time and rank work in (10) and (11); over equal ranks, the parameters (7) and the output of one run of the estimator, with its annealing estimate (6), on the fair bank (8) in (12); over the median of m(δ)m(\delta) values on a finite set in (13); and over the bounded output on the FPRAS bank in (14), with probabilities as uniform averages (1).

Of the slot pairs, the library proves that they are fresh for the empty set✦, a list of pairs being fresh for a set BB when the entries of all its pairs are distinct and none lies in BB✦; that their support, the set of all their entries, is the whole of VV✦; and that the list is nonempty when n>0n>0.✦