OctoInform Beta

OpenAI preprint, September 2026 · §7. Bit complexity · §7

§7 (proof of Theorem 7.1): counting the calls (7.3) to (7.5): The root call’s rank is at most 225000⌈log⁡2(L+2)⌉22^{25000\lceil\log_2(L+2)\rceil^2}, the step count the preparation writes in unary for the control loop

A quasipolynomial bound on the control steps of the root call.

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

Take a mean-payoff game on a set VV of nn vertices, given by an input code of length LL. The library’s solver is recursive: a call on a box with corners a≤ba\le b in ℤV\mathbb Z^V and reference width B≥b−aB\ge b-a, positive rational support weights α,β\alpha,\beta and budgets k,mk,m answers small instances directly, and otherwise calls itself many times over, to take medians and majorities of random trials. For its bit complexity on a Turing machine with a random tape, the question is how many steps the root call can need, as a function of LL.

The library runs the recursion on a stack machine. A step either starts a job, leaving on the stack a frame that records what to do with the answer, or hands a returned value to the frame on top of the stack. The rank of the root call is the number of steps it needs. A preparation computes a step count in unary from the input code, and the control loop runs exactly that many steps on every tape, one random sample index per step; the library bounds the rank of the root call by that count.

The Stack Machine

An environment ℰ=(𝒜,log⁡2s,s,J,T0)\mathcal E=(\mathcal A,\log_2 s,s,J,T_0) is a tuple of a raw arena 𝒜\mathcal A, the game graph encoded as bit strings with, on each edge ee, its transformed weight t(e)=(n+1)w(e)+1t(e)=(n+1)w(e)+1, where w(e)w(e) is the weight of ee, and four unary counters, lists of units in which a counter of length kk stands for kk: the sample exponent log⁡2s\log_2 s, the number ss of samples, the number JJ of trials and the step budget T0T_0 of the basic solver, the solver run directly on boxes of reference width at most 128s128s. A register pack is a record of eight registers: budgets, a box (a,b;B)(a,b;B), a counter tt, two vectors qq and rr of binary words, a list 𝑣𝑠\mathit{vs} of such vectors, an orientation oo and a list 𝑜𝑠\mathit{os} of orientations.✦ An orientation is a choice, YY or ZZ, with a list of masks, its exceptions, each a boolean list marking a set of vertices.✦ A register left unset holds zero: the zero budget, the zero box, the empty counter or list, or the orientation choosing ZZ with no masks✦; the empty pack has every register at zero.✦

A stack cell is a pair of a tag, a unary counter naming a job or a frame, and a register pack.✦ A control state σ\sigma is a pair of a current cell, which holds the job being called or the value being returned, and a stack, the list of cells holding the pending frames.✦ A control accumulator is a pair (ℰ,σ)(\mathcal E,\sigma)✦ of an environment and a control state, and a machine input is a triple (ℰ,c,σ)(\mathcal E,c,\sigma) whose unary counter cc, the random counter, is the sample index of the step.

A step runs one case. A case either returns a pack, which becomes the current cell under the return tag 1010✦, or calls a job: the job’s tag and pack become the current cell✦, and a frame, a cell recording what to do with the answer, is pushed onto the stack.✦ In the cases below the current box is (a,b;B)(a,b;B), with floor aa, ceiling bb, midpoint zz and grid width δ=B/(4s)\delta=B/(4s); the narrowed box at a vector vv is the box centered at vv of width B/(32s)B/(32s)✦, and the widened box at vv is the box centered at vv of width B/8B/8. Besides solve, the job of the root call, there are nine jobs.

  • Ask calls trials with the counter JJ and leaves a median frame✦, which returns the boxed median of the JJ answers✦: their coordinatewise median, or aa when there are none.✦

  • Trials with a counter tt calls solve tt times on its budgets and box and returns the list of answers, through trials head and vector cons frames.✦

  • Update at qq, written U(q)U(q), asks on the budgets reduced in kk and the narrowed box at qq✦; a first center frame asks on the budgets reduced in mm and the same box✦, and a second center frame returns the average of the two answers, clipped to (a,b;B)(a,b;B).✦

  • Centers with a counter tt and a vector qq returns the list q,U(q),…,Ut(q)q,U(q),\dots,U^t(q), through centers head and vector cons frames.✦

  • Orient on a box with B≤128sB\le 128s returns the base orientation of the basic solver’s output vv✦: with MM the mask of the vertices ii such that B≤2(vi−ai)B\le 2(v_i-a_i), it chooses YY with the complement of MM as exception when MM has measure above one half under the budgets, and ZZ with MM as exception otherwise.✦ On a wider box it calls centers with the counter ss from zz and leaves an orient loop frame.✦

  • Orientation trials with a counter tt collects tt orientations by calls of orient, through orient head and orient cons frames.✦

  • Orientation plus calls orientation trials with the counter JJ and leaves a combine frame✦, which returns the majority✦: the choice YY when more than half of the orientations choose YY, with all their masks concatenated.✦

  • Tighten asks on the budgets reduced in kk.✦ When the answer moves the floor of the box, relative to δ\delta, a first tightening frame tightens the box with its floor at the answer; otherwise it asks on the budgets reduced in mm✦, and a second tightening frame does the same with the ceiling and returns the box when the ceiling does not move.✦ Two box passing frames, for the floor and the ceiling, pass up the box a nested tightening returns.✦

  • Reweight with an orientation asks once for each of its masks, in order, on the budgets reweighted by that mask for the orientation’s choice, and returns the list of answers, through reweight head and vector cons frames.✦

The orient loop frame takes the last center v=Us(z)v=U^s(z) and the masks M+M^+ of the vertices with s(vi−zi)>2Bs(v_i-z_i)>2B and M−M^- of those with s(vi−zi)<−2Bs(v_i-z_i)<-2B. When M+M^+ has measure above one half it returns the orientation choosing YY with the complement of M+M^+ as exception, and when M−M^- has, the one choosing ZZ with the complement of M−M^-.✦ Otherwise it calls orient on the widened box at the center of index cc, the random counter, or at zz when there is none✦, and an orient tail frame appends M+M^+ and M−M^- to the masks of the returned orientation.✦

Solve returns, when the budgets are small, the vector prescribed for small budgets on the box, and when B≤128sB\le 128s, the output of the basic solver run on 𝒜\mathcal A and the box within T0T_0 steps.✦ Otherwise it calls tighten✦, and its main chain runs through frames: a solve tight frame calls orientation plus on the tightened box✦, a solve oriented frame calls reweight with the returned orientation✦, and a solve reweighted frame calls solve on the tightened box capped high, for the choice YY, or capped low, for ZZ, by its width less its grid width.✦ A cap high frame returns the coordinatewise minimum of that answer and the reweighted answers✦, a cap low frame their coordinatewise maximum✦, and an include inner frame makes this vector the answer of the outer call.✦

The dispatch of a machine input (ℰ,c,σ)(\mathcal E,c,\sigma) is the control state obtained by reading the tag of the current cell: tags 00 to 99 run the cases of solve, ask, trials, update, centers, orient, orientation trials, orientation plus, tighten and reweight, and any other tag resumes.✦ Resuming keeps σ\sigma when the stack is empty; otherwise it runs the frame case named by the tag of the top cell, one of twenty-two, and keeps σ\sigma for a larger tag.✦ The advance step is the map taking a control accumulator (ℰ,σ)(\mathcal E,\sigma) and a random counter cc to the accumulator that keeps the environment and replaces the state by its dispatch: adv⁡((ℰ,σ),c)=(ℰ,dispatch⁡(ℰ,c,σ)).\operatorname{adv}\bigl((\mathcal E,\sigma),c\bigr) =\bigl(\mathcal E,\operatorname{dispatch}(\mathcal E,c,\sigma)\bigr).(1)✦ The control loop is the map taking a control accumulator and a list c1,…,cℓc_1,\dots,c_\ell of random counters to the result of the advance step applied once for each counter in turn: loop⁡((ℰ,σ),(c1,…,cℓ))=adv⁡(⋯adv⁡(adv⁡((ℰ,σ),c1),c2)⋯,cℓ).\operatorname{loop}\bigl((\mathcal E,\sigma),(c_1,\dots,c_\ell)\bigr) =\operatorname{adv}\Bigl(\cdots\operatorname{adv}\bigl(\operatorname{adv}((\mathcal E,\sigma),c_1), c_2\bigr)\cdots,c_\ell\Bigr).(2)✦

The Preparation

The preparation reads a binary string uu of length LL; |x||x| denotes the length of a unary counter xx, and j_\underline{j} the counter of jj units. The input logarithm is the program that takes uu to the counter of its length, adds one twice, writes the result in binary and returns its ceiling base 2 logarithm as a unary counter.✦ The preparation exponent EE is the program that multiplies the constant counter 25000_\underline{25000} by the square of the input logarithm, the square taken by the fixed power code, which raises a counter to a fixed exponent by repeated multiplication.✦ The iteration count of uu is the number I(u)=2|E(u)|.I(u)=2^{|E(u)|}.(3)✦

The preparation root parses uu as a game with nn vertices and top width B*=8nWB_*=8nW, where W=max⁡{1,max⁡e|t(e)|}W=\max\{1,\max_e|t(e)|\} is the weight bound of the transformed weights t(e)t(e). It sets gg to the binary length of B*B_* plus one and the sample exponent to log⁡2s=⌈log⁡2(217(g+1))⌉\log_2 s=\lceil\log_2(2^{17}(g+1))\rceil, so that ss is the least power of two with s≥217(g+1)s\ge 2^{17}(g+1), and J=2(s(n+1))6+1,T0=128ns.J=2\bigl(s(n+1)\bigr)^6+1,\qquad T_0=128\,n\,s.(4) It returns the seed made of log⁡2s\log_2 s, ss, B*B_* and the initial accumulator (ℰ0,σ0)(\mathcal E_0,\sigma_0)✦: the environment ℰ0=(𝒜,log⁡2s,s,J,T0)\mathcal E_0=(\mathcal A,\log_2 s,s,J,T_0) holds the game’s arena✦, and σ0\sigma_0 calls solve, over an empty stack, on the budgets α=β=𝟏\alpha=\beta=\mathbf 1 and k=m=nk=m=n, where 𝟏\mathbf 1 is the all-ones vector, and the box (0,B*𝟏;B*)(0,B_*\mathbf 1;B_*).

The preparation value of uu doubles a single unit |E(u)||E(u)| times, which gives the counter κ(u)\kappa(u), and assembles it with the seed✦: it returns the counter of (log⁡2s)|κ(u)|(\log_2 s)\,|\kappa(u)| units, cut into κ(u)\kappa(u) chunks of log⁡2s\log_2 s units each, together with the chunk length log⁡2s\log_2 s, the number ss of samples, the number κ(u)\kappa(u) of chunks, the width B*B_* and the initial accumulator. As ss is a power of two, a chunk of log⁡2s\log_2 s fair bits gives a uniform sample index in {0,…,s−1}\{0,\dots,s-1\}.

The Claim

For a game GG, ⟨G⟩\langle G\rangle is its input code and NGN_G its root control bound, the natural number NG=A(n,B*)KGN_G=A(n,B_*)\,K_G, where A(n,B*)A(n,B_*) is the number of control steps the library allows for one solver invocation on a game with nn vertices and top width B*B_* (controlAllowance) and KGK_G is its bound on the number of solver invocations of the root call (rootInvocationBound); both are defined in the imported library MeanPayoff, and NGN_G is rootControlBound in MeanPayoff/ArithmeticBounds.lean. The control state σG\sigma_G of the root call calls solve on the root budgets and the root box of GG with nothing pending.

Theorem 1. Let GG be a mean-payoff game. The rank of the control state of its root call is at most its root control bound, rank⁡(σG)≤NG,\operatorname{rank}(\sigma_G)\le N_G,(5)✦ and the root control bound is at most the iteration count of its input code, NG≤I(⟨G⟩).N_G\le I(\langle G\rangle).(6)✦ For every binary string uu of length LL, the preparation exponent has length |E(u)|=25000⌈log⁡2(L+2)⌉2,|E(u)|=25000\,\lceil\log_2(L+2)\rceil^2,(7)✦ and the number of chunks of the preparation value is the counter κ(u)=2|E(u)|_.\kappa(u)=\underline{2^{|E(u)|}}.(8)✦

In the paper, the result reads: with K=8s(g+1)+1K=8s(g+1)+1 solver invocations per main chain and A0=(16ns+2)J+[2s(g+1)+2g+2]J2A_0=(16ns+2)J+[2s(g+1)+2g+2]J^2 smaller-rank descendants per chain node, the number NdN_d of solver invocations from one invocation of rank at most dd satisfies N0=1N_0=1 and Nd≤K+KA0Nd−1N_d\le K+KA_0N_{d-1}, hence ND*=2O((log⁡2x)2)N_{D_*}=2^{O((\log_2 x)^2)} with x=L+2x=L+2 and D*=d(n3)=O(log⁡x)D_*=d(n^3)=O(\log x). The library counts the control steps of the root call instead of its solver invocations.

What Is Checked

The claim is stated over mean-payoff games with their input code, the control state of the root call with its rank, the root control bound, and, for every binary string, the preparation exponent, the iteration count (3) and the preparation value.

Beyond the claim, the control loop (2) runs within a size bound: for every control accumulator (ℰ,σ)(\mathcal E,\sigma), every list c1,…,cℓc_1,\dots,c_\ell of random counters and every j≤ℓj\le\ell, ∥loop⁡((ℰ,σ),(c1,…,cj))∥≤240(S+1)12,\bigl\|\operatorname{loop}\bigl((\mathcal E,\sigma),(c_1,\dots,c_j)\bigr)\bigr\| \le 2^{40}(S+1)^{12},(9)✦ where ∥⋅∥\|\cdot\| is the encoded size and S=∥((ℰ,σ),(c1,…,cℓ))∥S=\|((\mathcal E,\sigma),(c_1,\dots,c_\ell))\|. The coordinatewise minimum and maximum of the cap frames obey a bound of the same kind: for a vector and a list of vectors of encoded size SS in all, the coordinatewise minimum, or maximum, of the vector with the first jj vectors of the list has encoded size at most 20(S+1)220(S+1)^2 for every jj.