OctoInform Beta

OpenAI preprint, September 2026 · §4. Recursive procedures and unconditional termination · §4

§4 (setting): Procedure 4.3 [The solver]: The raw solver's cases: endpoint vector, basic run, tightening by Ask, OrientPlus, and the capped solve combined by coordinatewise minimum or maximum

The solver’s steps as cases of a call-stack machine.

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 GG be a mean-payoff game on a vertex set VV of nn vertices with edge weights w(e)w(e), transformed weights t(e)=(n+1)w(e)+1t(e)=(n+1)w(e)+1, weight bound W=max⁡{1,max⁡e|t(e)|}W=\max\{1,\max_e|t(e)|\} and top width B*=8nWB_*=8nW. Procedure 4.3 is the solver of the recursion of Section 4 of the paper on randomized quasipolynomial-time mean-payoff games. It takes a solver input (a,b;B,α,β,k,m)(a,b;B,\alpha,\beta,k,m): 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. It returns a vector of ℤV\mathbb{Z}^V. On the way it calls two other procedures, Ask, which returns a vector for a box and a budget, and OrientPlus, which returns an orientation, a choice of YY or ZZ with a list of exception sets of vertices, and it calls itself on a box capped in width. Its thresholds are set by the global parameter ss of (4.1), a power of two.

The solver is a machine with an explicit call stack and one case for each step of the recursion; its arithmetic, done on raw data, computes the paper’s quantities.

Raw Data and Frames

The solver works on raw data, bit strings and unary counters. A raw vector is a list of binary words that represents a vector of ℤV\mathbb{Z}^V, and we write x≃vx\simeq v when the raw vector xx represents vv. A list of raw vectors represents a list v1,…,vℓv_1,\dots,v_\ell of integer vectors when it has length ℓ\ell and its jj-th entry represents vjv_j.✦ A raw box is a raw encoding of a box (a,b;B)(a,b;B) and a raw budget is a raw encoding of a budget (α,β,k,m)(\alpha,\beta,k,m); each is written with the letters of what it represents.

An environment is the raw arena of the game together with four unary counters.✦ An environment represents GG at top width B*B_* when its arena encodes GG with each edge ee labelled by a binary word of value t(e)t(e), its first three counters have lengths log⁡2s\log_2 s, ss and JJ, where JJ is the global parameter of (4.1) beside ss, and its fourth counter, the step budget of the run of the basic solver, Basic(I)\mathrm{Basic}(I) in (4), has length at least 128ns128ns.✦

A frame is the record of one call: a budget π=(α,β,k,m)\pi=(\alpha,\beta,k,m), a box II, a counter of remaining trials, two vectors, a list VV of vectors, an orientation and a list of orientations, kept under a tag that names the job the frame runs or the step at which it resumes.✦ An orientation is a choice χ\chi of YY or ZZ together with a list ℋ=(H1,…,Hℓ)\mathcal{H}=(H_1,\dots,H_\ell) of exception sets of vertices, the sets on which the reweighted budgets halve a support weight. A raw orientation is a bit, true when the choice is YY, together with a list of bit strings, each marking a set of vertices. A control state is a nonempty call stack: the frame being run, on top of the frames waiting below it.✦ We write it F⋅σF\cdot\sigma, with FF on top and σ\sigma the frames below, and show of each frame only the fields its case reads.

A step of the machine reads the environment, a unary counter that gives the sample index used in that step, an index in {0,…,s−1}\{0,\dots,s-1\}, and the control state, and replaces the top frame. A job returns a value xx by leaving the return frame 𝖱𝖾𝗍(x)\mathsf{Ret}(x) in its place, or calls another job by leaving that job’s frame above a frame that waits for the answer; a return frame resting on a waiting frame is handled by the waiting frame’s case. The jobs are 𝖲𝗈𝗅𝗏𝖾(I;π)\mathsf{Solve}(I;\pi), 𝖠𝗌𝗄(I;π)\mathsf{Ask}(I;\pi), 𝖮𝗋𝗂𝖾𝗇𝗍𝖯𝗅𝗎𝗌(I;π)\mathsf{OrientPlus}(I;\pi) and the solver’s own 𝖳𝗂𝗀𝗁𝗍𝖾𝗇(I;π)\mathsf{Tighten}(I;\pi) and 𝖱𝖾𝗐𝖾𝗂𝗀𝗁𝗍(I;π;χ,ℋ)\mathsf{Reweight}(I;\pi;\chi,\mathcal{H}).

For a box I=(a,b;B)I=(a,b;B) and a vector rr, the boxes (r,b;B)(r,b;B) and (a,r;B)(a,r;B) replace one corner by rr, and for a width CC the two capped boxes are I↑=(max⁡(a,b−C),b;C),I↓=(a,min⁡(b,a+C);C).I^{\uparrow}=(\max(a,b-C),\,b;\,C),\qquad I^{\downarrow}=(a,\,\min(b,a+C);\,C).(1) For a budget π\pi, the budgets πηk\pi_{\eta k} and πηm\pi_{\eta m} reduce kk to ηk\eta k or mm to ηm\eta m, with the reduction factor η=4/5\eta=4/5. For a set HH of vertices, the reweighted budgets are πZH=(αH,β,3k/5,m)\pi^{H}_{Z}=(\alpha^{H},\beta,3k/5,m) and πYH=(α,βH,k,3m/5)\pi^{H}_{Y}=(\alpha,\beta^{H},k,3m/5), where αH\alpha^{H} and βH\beta^{H} halve α\alpha and β\beta on HH.

The Claim

Definition 1 (Procedure 4.3, the solver). Let an environment represent GG at top width B*B_*, and let I=(a,b;B)I=(a,b;B) be a box of the game and π=(α,β,k,m)\pi=(\alpha,\beta,k,m) a budget. A frame running 𝖲𝗈𝗅𝗏𝖾(I;π)\mathsf{Solve}(I;\pi) answers at once when the parameter R=km∑i∈V1/(αiβi)R=k\,m\sum_{i\in V}1/(\alpha_i\beta_i) of π\pi (formula (3.2) of the paper) is below 11 or when the width test ν(I)\nu(I) of (3) passes; otherwise it starts the tightening and waits in the frame 𝖶solve(I;π)\mathsf{W}_{\mathrm{solve}}(I;\pi): 𝖲𝗈𝗅𝗏𝖾(I;π)⋅σ→{𝖱𝖾𝗍(e)⋅σ,R<1,𝖱𝖾𝗍(Basic(I))⋅σ,R≥1 and ν(I)=1,𝖳𝗂𝗀𝗁𝗍𝖾𝗇(I;π)⋅𝖶solve(I;π)⋅σ,otherwise,\mathsf{Solve}(I;\pi)\cdot\sigma\;\longrightarrow\; \begin{cases} \mathsf{Ret}(e)\cdot\sigma, & R<1,\\ \mathsf{Ret}(\mathrm{Basic}(I))\cdot\sigma, & R\ge 1\text{ and }\nu(I)=1,\\ \mathsf{Tighten}(I;\pi)\cdot\mathsf{W}_{\mathrm{solve}}(I;\pi)\cdot\sigma, & \text{otherwise}, \end{cases}(2)✦ where ee is the endpoint vector, with ei=bie_i=b_i when βi>m\beta_i>m and ei=aie_i=a_i otherwise. The width test is the truth value, 11 or 00, of a comparison of the reference width with 128s128s: ν(I)=[B≤128s].\nu(I)=[\,B\le 128s\,].(3)✦ The basic run Basic(I)\mathrm{Basic}(I) runs the basic solver on the arena and the box for the environment’s step budget.✦ When B≤128sB\le 128s, the basic run returns the box solution, the exact vector xG*(I)x^{\ast}_{G}(I) of the game GG on the box II: Basic(I)≃xG*(I).\mathrm{Basic}(I)\simeq x^{\ast}_{G}(I).(4)✦ The tightening job asks with the reduced budget πηk\pi_{\eta k} and waits in 𝖶floor(I;π)\mathsf{W}_{\mathrm{floor}}(I;\pi): 𝖳𝗂𝗀𝗁𝗍𝖾𝗇(I;π)⋅σ→𝖠𝗌𝗄(I;πηk)⋅𝖶floor(I;π)⋅σ.\mathsf{Tighten}(I;\pi)\cdot\sigma\;\longrightarrow\; \mathsf{Ask}(I;\pi_{\eta k})\cdot\mathsf{W}_{\mathrm{floor}}(I;\pi)\cdot\sigma.(5)✦ The grid width δI\delta_I of a box I=(a,b;B)I=(a,b;B) is BB shifted right by log⁡2s+2\log_2 s+2 places, and the moves of the tightening job are measured against it: δI=⌊B/(4s)⌋.\delta_I=\lfloor B/(4s)\rfloor.(6)✦ An answer rr that raises a coordinate of the lower corner by δI\delta_I restarts the tightening on (r,b;B)(r,b;B) and leaves the frame 𝖶pass(I;r)\mathsf{W}_{\mathrm{pass}}(I;r); any other answer is followed by a second ask, with πηm\pi_{\eta m}: 𝖱𝖾𝗍(r)⋅𝖶floor(I;π)⋅σ→{𝖳𝗂𝗀𝗁𝗍𝖾𝗇((r,b;B);π)⋅𝖶pass(I;r)⋅σ,ri−ai≥δI for some i,𝖠𝗌𝗄(I;πηm)⋅𝖶ceil(I;π)⋅σ,otherwise.\mathsf{Ret}(r)\cdot\mathsf{W}_{\mathrm{floor}}(I;\pi)\cdot\sigma\;\longrightarrow\; \begin{cases} \mathsf{Tighten}((r,b;B);\pi)\cdot\mathsf{W}_{\mathrm{pass}}(I;r)\cdot\sigma, & r_i-a_i\ge\delta_I\text{ for some }i,\\ \mathsf{Ask}(I;\pi_{\eta m})\cdot\mathsf{W}_{\mathrm{ceil}}(I;\pi)\cdot\sigma, & \text{otherwise}. \end{cases}(7)✦ The second answer restarts the tightening on (a,r;B)(a,r;B) when it lowers a coordinate of the upper corner by δI\delta_I; otherwise the job returns the box II: 𝖱𝖾𝗍(r)⋅𝖶ceil(I;π)⋅σ→{𝖳𝗂𝗀𝗁𝗍𝖾𝗇((a,r;B);π)⋅𝖶pass(I;r)⋅σ,bi−ri≥δI for some i,𝖱𝖾𝗍(I)⋅σ,otherwise.\mathsf{Ret}(r)\cdot\mathsf{W}_{\mathrm{ceil}}(I;\pi)\cdot\sigma\;\longrightarrow\; \begin{cases} \mathsf{Tighten}((a,r;B);\pi)\cdot\mathsf{W}_{\mathrm{pass}}(I;r)\cdot\sigma, & b_i-r_i\ge\delta_I\text{ for some }i,\\ \mathsf{Ret}(I)\cdot\sigma, & \text{otherwise}. \end{cases}(8)✦ A frame left by a restart passes the returned box JJ on: 𝖱𝖾𝗍(J)⋅𝖶pass(I;r)⋅σ→𝖱𝖾𝗍(J)⋅σ.\mathsf{Ret}(J)\cdot\mathsf{W}_{\mathrm{pass}}(I;r)\cdot\sigma\;\longrightarrow\; \mathsf{Ret}(J)\cdot\sigma.(9)✦ With the final box JJ back, the solver frame calls OrientPlus with its budget and leaves the frame 𝖶orient(J;π)\mathsf{W}_{\mathrm{orient}}(J;\pi) above an empty frame 𝖶out\mathsf{W}_{\mathrm{out}}: 𝖱𝖾𝗍(J)⋅𝖶solve(I;π)⋅σ→𝖮𝗋𝗂𝖾𝗇𝗍𝖯𝗅𝗎𝗌(J;π)⋅𝖶orient(J;π)⋅𝖶out⋅σ.\mathsf{Ret}(J)\cdot\mathsf{W}_{\mathrm{solve}}(I;\pi)\cdot\sigma\;\longrightarrow\; \mathsf{OrientPlus}(J;\pi)\cdot\mathsf{W}_{\mathrm{orient}}(J;\pi)\cdot\mathsf{W}_{\mathrm{out}} \cdot\sigma.(10)✦ The orientation (χ,ℋ)(\chi,\mathcal{H}) that comes back starts the reweighting job on JJ, and the choice χ\chi is kept in 𝖶cap(J;π;χ)\mathsf{W}_{\mathrm{cap}}(J;\pi;\chi): 𝖱𝖾𝗍(χ,ℋ)⋅𝖶orient(J;π)⋅σ→𝖱𝖾𝗐𝖾𝗂𝗀𝗁𝗍(J;π;χ,ℋ)⋅𝖶cap(J;π;χ)⋅σ.\mathsf{Ret}(\chi,\mathcal{H})\cdot\mathsf{W}_{\mathrm{orient}}(J;\pi)\cdot\sigma\;\longrightarrow\; \mathsf{Reweight}(J;\pi;\chi,\mathcal{H})\cdot\mathsf{W}_{\mathrm{cap}}(J;\pi;\chi)\cdot\sigma.(11)✦ The reweighting job returns the empty list [][\,] when ℋ\mathcal{H} is empty. Otherwise it asks on JJ with the budget reweighted on the first set H1H_1 and keeps the remaining sets ℋ′\mathcal{H}' in 𝖶next\mathsf{W}_{\mathrm{next}}: 𝖱𝖾𝗐𝖾𝗂𝗀𝗁𝗍(J;π;χ,ℋ)⋅σ→{𝖱𝖾𝗍([])⋅σ,ℋ=(),𝖠𝗌𝗄(J;πχH1)⋅𝖶next(J;π;χ,ℋ′)⋅σ,ℋ=(H1,ℋ′).\mathsf{Reweight}(J;\pi;\chi,\mathcal{H})\cdot\sigma\;\longrightarrow\; \begin{cases} \mathsf{Ret}([\,])\cdot\sigma, & \mathcal{H}=(\,),\\ \mathsf{Ask}(J;\pi^{H_1}_{\chi})\cdot\mathsf{W}_{\mathrm{next}}(J;\pi;\chi,\mathcal{H}')\cdot\sigma, & \mathcal{H}=(H_1,\mathcal{H}'). \end{cases}(12)✦ Each answer rr waits in a frame 𝖶keep(r)\mathsf{W}_{\mathrm{keep}}(r) while the job runs on the remaining sets: 𝖱𝖾𝗍(r)⋅𝖶next(J;π;χ,ℋ′)⋅σ→𝖱𝖾𝗐𝖾𝗂𝗀𝗁𝗍(J;π;χ,ℋ′)⋅𝖶keep(r)⋅σ.\mathsf{Ret}(r)\cdot\mathsf{W}_{\mathrm{next}}(J;\pi;\chi,\mathcal{H}')\cdot\sigma\;\longrightarrow\; \mathsf{Reweight}(J;\pi;\chi,\mathcal{H}')\cdot\mathsf{W}_{\mathrm{keep}}(r)\cdot\sigma.(13)✦ The cap width CJC_J of a box J=(a,b;B)J=(a,b;B) is obtained by subtracting δJ\delta_J from BB: CJ=B−⌊B/(4s)⌋.C_J=B-\lfloor B/(4s)\rfloor.(14)✦ When the list VV of answers reaches 𝖶cap\mathsf{W}_{\mathrm{cap}}, the solver is called on the box JJ capped at width CJC_J, by (1), from above when χ=Y\chi=Y and from below when χ=Z\chi=Z: 𝖱𝖾𝗍(V)⋅𝖶cap(J;π;χ)⋅σ→{𝖲𝗈𝗅𝗏𝖾(J↑;π)⋅𝖶min(J;V)⋅σ,χ=Y,𝖲𝗈𝗅𝗏𝖾(J↓;π)⋅𝖶max(J;V)⋅σ,χ=Z.\mathsf{Ret}(V)\cdot\mathsf{W}_{\mathrm{cap}}(J;\pi;\chi)\cdot\sigma\;\longrightarrow\; \begin{cases} \mathsf{Solve}(J^{\uparrow};\pi)\cdot\mathsf{W}_{\min}(J;V)\cdot\sigma, & \chi=Y,\\ \mathsf{Solve}(J^{\downarrow};\pi)\cdot\mathsf{W}_{\max}(J;V)\cdot\sigma, & \chi=Z. \end{cases}(15)✦ The minimum fold foldmin\mathrm{fold}_{\min} and the maximum fold foldmax\mathrm{fold}_{\max} take a raw vector xx and raw vectors x1,…,xℓx_1,\dots,x_\ell, and when x≃vx\simeq v and xj≃vjx_j\simeq v_j for vectors v,v1,…,vℓv,v_1,\dots,v_\ell of one box, they compute the coordinatewise minimum and maximum: foldmin(x;x1,…,xℓ)≃min⁡(v,v1,…,vℓ),\mathrm{fold}_{\min}(x;x_1,\dots,x_\ell)\simeq\min(v,v_1,\dots,v_\ell),(16)✦ foldmax(x;x1,…,xℓ)≃max⁡(v,v1,…,vℓ).\mathrm{fold}_{\max}(x;x_1,\dots,x_\ell)\simeq\max(v,v_1,\dots,v_\ell).(17)✦ The solution pp of the capped box is folded with the answers, by the minimum when χ=Y\chi=Y and by the maximum when χ=Z\chi=Z: 𝖱𝖾𝗍(p)⋅𝖶min(J;V)⋅σ→𝖱𝖾𝗍(foldmin(p;V))⋅σ,\mathsf{Ret}(p)\cdot\mathsf{W}_{\min}(J;V)\cdot\sigma\;\longrightarrow\; \mathsf{Ret}(\mathrm{fold}_{\min}(p;V))\cdot\sigma,(18)✦ 𝖱𝖾𝗍(p)⋅𝖶max(J;V)⋅σ→𝖱𝖾𝗍(foldmax(p;V))⋅σ,\mathsf{Ret}(p)\cdot\mathsf{W}_{\max}(J;V)\cdot\sigma\;\longrightarrow\; \mathsf{Ret}(\mathrm{fold}_{\max}(p;V))\cdot\sigma,(19)✦ and the empty frame passes the result xx on: 𝖱𝖾𝗍(x)⋅𝖶out⋅σ→𝖱𝖾𝗍(x)⋅σ.\mathsf{Ret}(x)\cdot\mathsf{W}_{\mathrm{out}}\cdot\sigma\;\longrightarrow\;\mathsf{Ret}(x)\cdot\sigma.(20)✦

In the paper, the result reads, in steps S1 to S5: given (a,b;B,α,β,k,m)(a,b;B,\alpha,\beta,k,m), compute RR and μ\mu from (3.2); in S1, if R<1R<1, return the vector with coordinate bib_i when βi>m\beta_i>m and aia_i otherwise, and if R≥1R\ge 1 but B≤128sB\le 128s, return Basic(a,b)\mathrm{Basic}(a,b); in S2, with δ=⌊B/(4s)⌋\delta=\lfloor B/(4s)\rfloor and C=B−δC=B-\delta, loop with changing bounds, taking r=Ask(a,b;B,α,β,ηk,m)r=\mathrm{Ask}(a,b;B,\alpha,\beta,\eta k,m) and, if ri−ai≥δr_i-a_i\ge\delta for some ii, replacing aa by rr and restarting, otherwise taking r=Ask(a,b;B,α,β,k,ηm)r=\mathrm{Ask}(a,b;B,\alpha,\beta,k,\eta m) and, if bi−ri≥δb_i-r_i\ge\delta for some ii, replacing bb by rr and restarting, otherwise stopping; in S3, on the final tightening box, (χ,ℋ)=OrientPlus(a,b;B,α,β,k,m)(\chi,\mathcal{H})=\mathrm{OrientPlus}(a,b;B,\alpha,\beta,k,m); in S4, when χ=Z\chi=Z, take rH=Ask(a,b;B,αH,β,3k/5,m)r_H=\mathrm{Ask}(a,b;B,\alpha^{H},\beta,3k/5,m) for every entry HH of the list and p=Solve(a,min⁡(b,a+C);C,α,β,k,m)p=\mathrm{Solve}(a,\min(b,a+C);C,\alpha,\beta,k,m), and return the coordinatewise maximum of pp and all rHr_H; in S5, when χ=Y\chi=Y, take rH=Ask(a,b;B,α,βH,k,3m/5)r_H=\mathrm{Ask}(a,b;B,\alpha,\beta^{H},k,3m/5) and p=Solve(max⁡(a,b−C),b;C,α,β,k,m)p=\mathrm{Solve}(\max(a,b-C),b;C,\alpha,\beta,k,m), and return the coordinatewise minimum of pp and all rHr_H.

What Is Checked

The cases of the machine are stated over its control states, stacks of frames holding raw budgets, raw boxes, vectors and orientations; the width test, δI\delta_I, CJC_J and the basic run are stated for an environment that represents GG at top width B*B_* and a raw box that represents a box of the game, and the folds for raw vectors that represent vectors of one box.

Each fold keeps, coordinate by coordinate, one of the two words it compares, and the library bounds its running result: after any prefix of the list has been folded in, the running vector has encoded size at most 20(S+1)220(S+1)^2, where SS is the encoded size of the input.✦