Context and approach

Edit distance originates in the study of errors in transmitted strings, including Levenshtein’s binary codes for insertions, deletions and bit flips (Levenshtein 1966). The dynamic program of Wagner and Fischer (Wagner and Fischer 1974) computes the minimum cost of insertions, deletions and substitutions in quadratic time. Masek and Paterson (Masek and Paterson 1980) applied block tabulation to obtain a logarithmic speedup for fixed alphabets and suitable fixed costs. Distance-sensitive exact algorithms offer another route when few edits are needed: Ukkonen (Ukkonen 1985) developed bounded-distance methods, and Landau and Vishkin (Landau and Vishkin 1988, 1989) combined furthest-reaching states with fast matching queries. Myers’s related difference algorithm (Myers 1986) treats insertion–deletion scripts. For unrestricted exact computation, Backurs and Indyk (Backurs and Indyk 2018) showed that a strongly subquadratic deterministic algorithm would refute the Strong Exponential Time Hypothesis. That lower bound does not rule out fixed-factor approximation.

Approximation algorithms progressively improved the accuracy available with substantially less work. In the following historical comparisons, write \(n\) for a common upper bound on the string lengths. Batu and coauthors (Batu et al. 2003) gave sublinear tests for fixed alphabets that distinguish sufficiently small distance from linear distance. For general pairs, Bar-Yossef, Jayram, Krauthgamer and Kumar (Bar-Yossef et al. 2004) obtained an \(n^{3/7}\) approximation in quasi-linear time; Batu, Ergün and Sahinalp (Batu et al. 2006) improved the factor to \(n^{1/3+o(1)}\). For binary strings, Ostrovsky and Rabani (Ostrovsky and Rabani 2007) constructed a low-distortion embedding into \(\ell_1\), and Andoni and Onak (Andoni and Onak 2012) obtained an efficiently computable \(2^{\widetilde O(\sqrt{\log n})}\) approximation in \(n^{1+o(1)}\) time. Andoni, Krauthgamer and Onak (Andoni et al. 2010) then achieved a \((\log n)^{O(1/\xi)}\) factor in \(n^{1+\xi}\) time for each fixed \(\xi>0\), using a hierarchical alignment representation and nonuniformly allocated precisions.

The next advances reached constant factors. Chakraborty, Das, Goldenberg, Koucký and Saks (Chakraborty et al. 2020) gave a constant-factor approximation in \(\widetilde O(n^{12/7})\) time. Brakensiek and Rubinstein (Brakensiek and Rubinstein 2020) and Koucký and Saks (Koucký and Saks 2020) independently obtained near-linear exponents for sufficiently far input pairs, with a material additive error on general pairs. Andoni and Nosatzki (Andoni and Nosatzki 2020) removed that restriction: for every fixed \(\xi>0\), their algorithm gives an approximation factor depending only on \(\xi\) in \(O(n^{1+\xi})\) time. The factor depends on the exponent parameter; this is not an approximation scheme with error tending to zero. For accuracy arbitrarily close to one, Mao and Rubinstein (Mao and Rubinstein 2026, Theorem 6.1) recently obtained a randomized \((1+\varepsilon)\) approximation in \(n^2/2^{\log^{\Omega(1)}n}\) time for every fixed positive \(\varepsilon\).

The issue addressed here is how to retain fixed \((1+\varepsilon)\) accuracy while reducing the expected total work to \(N^{1+o(1)}\). Recursive interval decompositions, economical evaluation of local distances, and accounting along an optimal alignment have substantial precedent in the algorithms above. In our refinement, unrestricted recursive evaluation of child distances would consume the available time even if the resulting numerical error were small. We therefore need both a narrow family that contains a suitable comparison alignment and a bound on the number of child distances actually evaluated.

For the initial estimates we adapt the shift tree and precision sampling of Andoni, Krauthgamer and Onak (Andoni et al. 2010, 2011). The refinement is related to Mao and Rubinstein’s use of multiscale deviation to constrain alignment paths before sampling (Mao and Rubinstein 2026). Here we measure the alignment’s changes in relative position using preliminary cost estimates as weights. A telescoping bound on their variation controls the total cost of places where the prediction fails. An entropy-regularized prediction rule, within the framework of Rakhlin and Sridharan (Rakhlin and Sridharan 2013), then controls the accumulated error where the predictions can be used. We implement its optimization by a finite Frank–Wolfe procedure (Frank and Wolfe 1956; Jaggi 2013). The specialized geometric, probabilistic and numerical guarantees are proved in this paper.

Two related comparisons concern different requirements on the output or the edit costs. A single \(\ell_1\) embedding of all binary strings up to a length bound must incur growing distortion (OpenAI 2026, Theorem 1.1). Our algorithm estimates the distance of the supplied pair and does not construct such a common embedding. Recent algorithms for metric-weighted edit costs obtain \((3+\varepsilon)\) approximation in strongly subquadratic time (Mader et al. 2026; Das et al. 2026); their cost model is broader than the unit-cost model treated here.

Proof overview

Recursively partition the first string into a tree of intervals, ending at intervals of length at most one. An interval state consists of a source interval \(I\) and a target interval in the second string; its true cost is the edit distance between the two substrings. An action at a nonleaf assigns one target interval to each source child. We charge the sum of the child estimates together with penalties for gaps or overlaps between successive target endpoints and at the two outer endpoints. These penalties let us compare nearby actions without requiring their target intervals to join exactly.

Paths, states and connection costs

Index string boundaries starting at zero. An alignment path has steps \((1,0),(0,1),(1,1)\), of cost one, one, and the indicator that the two characters on a diagonal step differ. Such a path gives an edit sequence. Conversely, the original characters that survive an edit sequence occur in the final string in their original order. Deleting other original characters, inserting the remaining output characters and changing each surviving character whose label differs gives an alignment of no greater cost. Thus minimum alignment cost equals edit distance.

For an interval \(I=(l,u]\) of the first string, an interval state is \((I,q)\), where \(q=(q^-,q^+)\) is an integer pair with \(0\le q^-\le q^+\le |y|\). When \(I\) is fixed, we also call \(q\) a state. Set \[c(I,q)=\operatorname{ED}\bigl(x_{(l,u]},y_{(q^-,q^+]}\bigr),\qquad z(I,q)=(q^+-q^-)-(u-l).\] An endpoint’s shift is its target index minus its first-string index. In particular, \(z\) is the change in shift between the two endpoints. For pairs use \(|q-r|_1=|q^--r^-|+|q^+-r^+|\).

Figure 1 illustrates why the connection term permits both gaps and overlaps between consecutive child targets.

Uniform access to the accuracy input

The rational accuracy is supplied in a fixed canonical binary encoding of its positive numerator and denominator in lowest terms, on a separate read-only input. For example, encode a positive integer by its binary length in unary, a delimiter, and its binary digits, and concatenate the two encodings. The input is promised to specify \(0<\varepsilon<1\). Prefix inspection is ordinary input access; no numerical operation on the rational is free.

The algorithm first handles equality, empty strings and \(|x|\le1\) exactly. These cases require \(O(N+1)\) string work. On other inputs define \(H\) as the least power of two at least \(\lceil\log_2(N+2)\rceil\), and \(\ell\) as the least power of two at least \(\max(1,\log_2 H)\). Inspect at most \(H^2+O(1)\) bits of the accuracy input. If its complete encoding has not been obtained, use exact alignment dynamic programming. The unread suffix is neither copied nor addressed. All addresses actually used for this prefix have \(O(\log(N+2))\) bits. If the encoding is obtained, its integers have \(O(H^2)\) bits, and exact arithmetic decides the test \(\ell\varepsilon\ge10\) with polynomial work in \(H\).

Use exact dynamic programming also if \(\ell<2^{1000}\) or \(\ell\varepsilon<10\). It uses \(O((N+1)^2)\) word operations and can store only two rows. Together with the bounded parameter inspection, this charges every operation in these branches. For each fixed rational encoding, the inspection bound eventually exceeds its length, and both numeric tests eventually pass as \(N\) grows. Thus the exact branches affect only a bounded range of \(N\) for each fixed \(\varepsilon\). They preserve the uniform algorithm and its approximation guarantee on that range. No assertion about efficient joint dependence on encoding length or \(1/\varepsilon\) is needed.

Parameters and the fixed interval tree

All remaining arguments concern the large-input branch. Logarithms with subscript two are binary, and \(\ln\) denotes the natural logarithm. The coarse estimator and interval tree use the branching factors \(B\) and \(M\) below. The factor \(A_{\rm init}\) is the initial seed accuracy, \(F\) controls its reduction across passes, and \(P\) controls endpoint-grid resolution: \[\begin{align*} p_*&=\left\lfloor(\log_2\ell)^{1/4}\right\rfloor, &B&=H^{p_*},&A_{\rm init}&=H^{p_*+4},\\ M&=2^{\lfloor(\log_2 H)/20\rfloor}, &P&=H^{p_*+20},&F&=\ell. \end{align*}\] The counts \(T\) and \(S\) govern preliminary propagation and refinement iterations, respectively. The slopes \(L_0\) and \(L\) penalize changes in target endpoints: \[T=2^{\lceil(3/4)\log_2H\rceil},\qquad S=H/\ell^2, \qquad L_0=32F,\qquad L=128F.\] Finally, fix the error tolerances and the sampling and optimization parameters. Their roles are specified at the corresponding constructions: \[\begin{align*} \delta&=\ell^{-10},&\kappa&=\tau=\ell^{-4}, &\theta&=\ell^{-40},\\ \gamma&=\ell^{-20},&\eta&=\ell^5,&Q_1&=\ell^{80}. \end{align*}\] The essential separation is between \(H=\Theta(\log(N+2))\) and \(\ell=\Theta(\log H)\): the branching factors and grid resolutions are powers of \(H\), while the tolerances are powers of \(\ell\). The inequalities below quantify the slack available between these scales.

Every integer parameter here is computable using bit lengths and integer tests. For example, \(p_*\) is the largest integer whose fourth power is at most the integer \(\log_2\ell\). The displayed fractional powers and logarithms require no real-arithmetic oracle. All parameters used as dyadic grid spacings are powers of two, and \(S\) is a positive integer in this branch.

We will repeatedly use the generous bounds \[ H\ge2^{\ell/2},\qquad \ell^{200}\le H^{1/100},\qquad p_*+21\le\sqrt\ell. \tag{3}\] The first follows from the definition of \(\ell\); the other two follow at \(\ell\ge2^{1000}\) and become stronger as \(\ell\) increases. More explicitly, \(200\log_2\ell\le\ell/200\) and \((\log_2\ell)^{1/4}+21\le\sqrt\ell\) hold at this cutoff, and their right sides thereafter grow faster. Factors polynomial in \(\ell\) and \(p_*\) will consequently be much smaller than any fixed positive power of \(H\) needed below.

Partition \(x\) into a complete \(M\)-ary tree of height \[J=\left\lceil\log_M\max(1,|x|)\right\rceil.\] At a node \((l,u]\) use cuts \(l_i=l+\lfloor i(u-l)/M\rfloor\), \(0\le i\le M\). Empty intervals are allowed, and node labels distinguish repeated intervals. Nodes need only be generated when requested. At depth \(j\) the width is at most \(\lceil|x|/M^j\rceil\), and leaves have width at most one. The parameters give \[ J\le100H/\ell,\qquad M^J\le M\max(1,|x|). \tag{4}\] Indeed \(\log_2M\ge (\log_2H)/20-1\) and \(\log_2H\ge\ell/2\), whereas \(\log_2|x|\le H\). The second bound follows directly from the ceiling defining \(J\).

At a leaf of width zero the exact cost is the target length. At a leaf containing one character, the cost is one for an empty target, and otherwise is the target length minus the indicator that this character occurs there. Sort the pairs (symbol, position) of \(y\) lexicographically by comparison sorting. A binary search then tests occurrence in any target interval in \(O(\log(N+2))\) time, with \(O(N\log(N+2))\) preprocessing work and linear storage. The word-label assumption makes each comparison a bounded number of word operations. Fresh padding symbols used later can be represented by a tag together with a label; no search for an unused alphabet value is needed.

All subsequent tables are indexed by this fixed tree and valid endpoint pairs. The total domain is polynomial in \(N+2\): there are at most \(2M^J\) nodes and at most \((|y|+1)^2\) pairs per node. A simultaneous probability guarantee over this domain is meaningful even though the algorithm will evaluate only a small part of it.

A deterministic shift tree

The hierarchical representation below is an adaptation of the E-distance of Andoni, Krauthgamer and Onak (Andoni et al. 2010, Definition 3.2 and Theorem 3.3). We prove its precise bounds here, including the treatment of unequal lengths, empty intervals and bounded integer shifts.

Fix one state and write \(n_x=|I|\), \(n_y=q^+-q^-\), and \(c=c(I,q)\). If \(n_y>2n_x\), return \(n_y\): the bounds \(n_y-n_x\le c\le n_y\) give the required factor two. Otherwise test equality directly and return zero when the strings agree. These steps cost \(O(1+n_x)\), since in the branch requiring character comparisons \(n_y\le2n_x\). They include the case \(n_x=0\).

For the remaining case, pad the shorter string at its right end with a fresh tagged symbol to obtain two strings of the same length \(n\le2n_x\). Denote their distance by \(d\). The length gap is at most \(c\), so \(d\le2c\). Conversely, remove padding from any padded alignment. A diagonal joining padding to a real character has cost one and can be replaced by an insertion or deletion of the same cost; other operations consuming padding can be removed. Hence \[ 1\le c\le d\le2c,\qquad 1\le n\le N,\qquad d\le n. \tag{6}\] The last bound follows by substituting characters position by position.

For each dyadic guess \[k\in\{1,2,4,\ldots,2^{\lceil\log_2 n\rceil}\},\] split the first padded string in a complete balanced \(B\)-ary tree of depth \(D_0=\lceil\log_B n\rceil\). Its leaves have width zero or one. Allowed shifts are the integers in \([-k,k]\). At a width-one leaf \(w\) starting at position \(j\), let \(T_w(v)\) be the mismatch indicator between its character and position \(j+1+v\) of the second padded string. A position outside the latter string has a virtual symbol that always mismatches. At a width-zero leaf put \(T_w(v)=0\). At an internal node define \[ T_w(v)=\sum_{i=1}^B\min_{v'\in[-k,k]\cap\mathbb Z} \{T_{w_i}(v')+2|v-v'|\}. \tag{7}\] Constant shifts show that \(0\le T_w(v)\le |w|\), where \(|w|\) denotes the node’s width.

The virtual symbols are chosen outside the alphabets of both padded strings. Thus every leaf value is an edit cost against a finite interval of an extended target string, to which Lemma 2 applies.

Pruning and precision sampling

Nonuniform additive precision is the sampling principle developed by Andoni, Krauthgamer and Onak (Andoni et al. 2010, Lemma 3.12) and refined in (Andoni et al. 2011, Lemma 1.2), with earlier multiscale sampling antecedents in Indyk and Woodruff (Indyk and Woodruff 2005). The reconstruction arguments of Andoni, Krauthgamer and Onak already allow estimates to depend on the sampled precisions. Here we use a finite threshold distribution and prove an event covering all potential interval states, together with the conditional cost of a first request.

Computing all of (7) would be too expensive. The guess \(k\) will also serve as an additive allowance at the root: on one event of high probability, we will obtain an estimate \(\widetilde T_o\) between \(T_o/2-k\) and \(2T_o+k\) simultaneously for every entry and guess. Then \(2(\widetilde T_o(0)+k)\) is an upper bound on \(d\) for every guess, and the guess \(d\le k<2d\) gives an \(O(1+BD_0)\) approximation. We can therefore replace a node by zero whenever its entire cost fits within its additive allowance. Larger guesses permit more pruning; their larger allowances are paid back in the returned estimate. Set \[Q_0=H^4,\qquad \lambda=\frac1{64H},\qquad a_o=k.\] At a node with allowance \(a_w\), independently for its children draw \(R_i\) uniformly from \(\{1,\ldots,B\}\) and set \[ t_i=\frac{a_wR_i}{BQ_0},\qquad a_{w_i}=\lambda t_i. \tag{8}\] All these random choices can be defined in advance, even below nodes that will be pruned. The implementation exposes only those it needs.

If \(|w|\le a_w\), use the identically zero estimate \(\widetilde T_w\). At any other leaf use its exact array. At an unpruned internal node first compute \[\widehat s_i(v)=\min_{v'\in[-k,k]\cap\mathbb Z} \{\widetilde T_{w_i}(v')+2|v-v'|\},\] and then put \[ \widetilde T_w(v)=\sum_{i=1}^B \boldsymbol 1_{\widehat s_i(v)\ge t_i} \max\{\widehat s_i(v),a_w/Q_0\}. \tag{9}\] The descendants used to compute \(\widehat s_i(v)\) depend on \(t_i\), so these child estimates cannot be treated as fixed in a concentration bound. The proof below first compares their sampled contributions with two lists formed from true child costs. It then concentrates those lists without assuming that any child estimate is accurate.

Converting the estimate to an integer seed

For the padded entry, take the ceiling of \[ \min_k 2\bigl(\widetilde T_o(0)+k\bigr) \tag{13}\] and clamp it to \([0,N]\). On the event of Lemma 5, every candidate is at least \(T_o(0)\ge d\ge c\). A listed guess satisfies \(d\le k<2d\), and its rounded candidate is at most \[4(1+2BD_0)d+4k+1 \le (25+16BH)c \le BH^4c=A_{\mathrm{init}}c.\] Clamping preserves both bounds because \(c\le N\). Together with the direct branches this proves the approximation assertion in Theorem 3.

The conditional cost of an adaptive request

We next prove the cost assertion, including executions outside the accuracy event. For an array \(E\) on \([-k,k]\cap\mathbb Z\), its penalty transform is computed by a left sweep \[L(v)=\min\{E(v),L(v-1)+2\}\] with the natural initial value, and the symmetric right sweep. Their pointwise minimum is \[\min_{v'}\{E(v')+2|v-v'|\}.\] Both sweeps take \(O(k)\) operations. An identically zero child array, whose transform is also zero, is represented by a marker without allocation. At an unpruned internal node the array work is \(O(Bk)\), including visits and thresholds for all children. An unpruned leaf costs \(O(k)\). A pruned node needs only its width test and marker.

Let \(r\) be a node’s depth in the coarse tree. From (8), along any fixed path, \[a_w=\frac{k\prod R_e}{(64BH^5)^r},\qquad \mathbb E\left[\frac{a_{\mathrm{parent}}}{a_w}\,\middle|\, a_{\mathrm{parent}}\right] =64H^5\sum_{j=1}^B\frac1j\le H^8.\] It follows that \(\mathbb E[k/a_w]\le H^{8r}\). A node can incur array work only if \(|w|>a_w\), and pointwise \[k\boldsymbol 1_{|w|>a_w}\le |w|\frac{k}{a_w}.\] Widths sum to \(n\) at each depth. Thus the expected array work for one guess, including child overhead charged to expanded parents, is at most \[ O\bigl(1+Bn(D_0+1)H^{8D_0}\bigr). \tag{14}\] This estimate uses the random allowances alone and remains valid when the estimated arrays are inaccurate.

All arithmetic and sampling can be performed with finite binary integers. The quantities in (8) are dyadic; a common denominator for their descendants and the arrays needs \(O(D_0(p_*+5)\log H+\log H)\) bits. Minima and maxima select existing dyadic values, and sums preserve this common precision. The same-shift candidate in the penalty minimum gives \[\widetilde T_w(v)\le\sum_i\widetilde T_{w_i}(v)+Ba_w/Q_0.\] Since \(a_w\le k\) and there are \(O(Bn)\) nodes, all estimate magnitudes are bounded by \(n+O(B^2nk)\). Their bit lengths, and the cost of ordinary binary arithmetic on them, fit the factor \(H^{O(D_0+p_*+1)}\). Each \(R_i\) requires exactly \(\log_2B\) fair random bits. Zero arrays are never materialized.

There are \(O(H)\) guesses, and \[D_0\le1+\frac{H}{p_*\log_2H},\qquad \log_2\bigl(H^{O(D_0+p_*+1)}\bigr) =O\left(\frac H{p_*}+(p_*+1)\log H\right)=o(H).\] Consequently (14), including the arithmetic factors, all guesses, equality tests, and padding, is \((1+|I|)2^{o(H)}\) in expectation. Even a full coarse tree with all its shift arrays uses only polynomial space: it has \(O(Bn)\) nodes, \(O(n)\) entries per array, and the bit lengths just bounded.

Finally, assign a separate random stream to every initial entry, keyed by its labeled main-tree node and endpoint pair, and cache the completed answer. Its calculation does not query other initial entries. Before its first request, none of the exposed computation can depend on its unused stream: such a dependence would already have required evaluating this entry. Conditional on the entire preceding execution and the adaptive request, the stream therefore has its original distribution. The expected cost bound applies conditionally exactly as stated; repeated requests use the cached answer and pay only lookup work. This deferred exposure realizes the same full random table used in the simultaneous probability argument and completes the proof of Theorem 3.

Cost cones and their local evaluation

The number \(a\) is an integer power of two. Define \[\widetilde U(I,q)=\max\{\lceil U(I,q)/a\rceil,\lvert z(I,q)\rvert\}.\] Since \(Fc(I,q)\) is an integer, rounding does not spoil the bounds \[ \max\{c(I,q)/a,\lvert z(I,q)\rvert\} \le\widetilde U(I,q)\le Fc(I,q). \tag{16}\] These bounds do not give endpoint regularity: neighboring seed entries can have quite different overestimates. We replace the scaled table by a lower envelope of cones. The charge \(L_0|q-r|_1\) for moving away from a center \(r\) preserves the lower bounds \(c/a\) and \(|z|\), while making the envelope Lipschitz. To evaluate it with few seed queries, we retain centers on grids at several cost scales. A grid at the scale of the true cost will provide a nearby inexpensive center; its value will then force every minimizing center to be nearby as well.

The scales \(b\) are the powers of two from \(1\) to the largest power of two at most \(N\). At scale \(b\), put \(g_b=\max\{1,b/P\}\). A grid state has both coordinates in \(g_b\mathbb Z\cap[0,|y|]\), in nondecreasing order. The state \(r_b(q)\) rounds both coordinates of \(q\) down to this grid. All these spacings are integers. If \(g_b=1\), rounding is exact; otherwise \[ \lvert q-r_b(q)\rvert_1<2b/P. \tag{17}\]

At a nonleaf \(I\), consider all cones \[q\longmapsto \widetilde U(I,r)+L_0\lvert q-r\rvert_1\] whose centers are grid states at some scale \(b\) with \(b/2\le U(I,r)\le4Ab\). Include also the cone at every state \(r\) with \(U(I,r)=0\), whether or not it occurs on one of these grids. Define \(w_0(I,q)\) to be their minimum. At a leaf set \(w_0(I,q)=c(I,q)\). The exact leaf rule will be used for every later table as well.

We use this local rule as the executable definition even when the seed is inaccurate, returning \(N\) if its nonzero branch has no candidate. Its work remains finite without any seed guarantee. Indeed, the scale interval has ratio at most \(64A^3\), and \(U(I,q)/b\le16A^2\) there. The local list therefore contains \(O((1+PA^2)^2(1+\log A))=H^{O(p_*+1)}\) raw seed queries. The returned values are nonnegative integers of magnitude \(O((L_0+1)N)\). Global cone identities and Lipschitz continuity are asserted only for a seed satisfying Theorem 6.

Wide actions and Bellman propagation

The next operator combines child estimates into a parent estimate. We first allow each child to choose its target independently, paying the connection charge for gaps and overlaps. Its minimum over earlier child tables will remain an available parent option throughout the refinement; the more restricted choices will use current child tables. Extending each action cost by an endpoint cone retains spatial regularity. Repeated propagation will also supply the average cost table used to predict child alignments.

Let a nonleaf \(I=(l,u]\) have child cuts \(l=l_0\le l_1\le\cdots\le l_M=u\), so \(I_i=(l_{i-1},l_i]\). A representative is a pair \((b,r)\) with \(r\) a grid state at scale \(b\) and \[ b/(4a)\le w_0(I,r)\le8Fb. \tag{20}\] Write \(p_0=r^--l\). The wide action set \(\mathcal A_{b,r}\) consists of lists \(\alpha=(s_1,\ldots,s_M)\) of valid child grid states satisfying \[|s_i^--l_{i-1}-p_0|\le10b, \qquad |s_i^+-l_i-p_0|\le10b.\] Consecutive target intervals need not meet. Their discrepancy is paid for by the connection charge \(\operatorname{conn}_r(\alpha)\) defined in Section 2. For child tables \(f\), put \[\begin{align*} V_r(\alpha;f)&=\operatorname{conn}_r(\alpha)+\sum_{i=1}^M f(I_i,s_i), \tag{21}\\ \mathcal B_I(f)(q) &=\min\left\{w_0(I,q),\; \min_{(b,r)}\left[L|q-r|_1+ \min_{\alpha\in\mathcal A_{b,r}}V_r(\alpha;f)\right]\right\}. \tag{22}\end{align*}\] Every minimum over an empty set is \(+\infty\).

The operator \(\mathcal B_I\) is monotone in its child tables and is \(L\)-Lipschitz in \(q\). It also preserves the lower bound \(\max\{c/a,|z|\}\). For the latter assertion, if each child satisfies the lower bound, then \[V_r(\alpha;f) \ge\frac{\operatorname{conn}_r(\alpha)+\sum_i c(I_i,s_i)}a \ge c(I,r)/a,\] while the net-change-of-shift inequality gives \(V_r(\alpha;f)\ge|z(I,r)|\). Endpoint Lipschitz continuity extends both bounds along the cone, and \(w_0\) satisfies them too.

Define the warmup tables at nonleaves by \[ w_j(I,q)=\mathcal B_I(w_{j-1})(q)\quad(1\le j\le T), \qquad m=\frac1T\sum_{j=0}^{T-1}w_j,\qquad d_0=w_T. \tag{23}\] Here the operator receives the indicated tables on children. Because \(w_1\le w_0\) and the operator is monotone, the warmup is nonincreasing. In particular, \[ \max\{c/a,|z|\}\le d_0\le m\le w_0\le2Fc, \qquad \mathcal B_I(d_0)\le d_0. \tag{24}\] The last inequality follows by one further application of the same monotonicity. The tables \(w_j\) and \(m\) are \(L\)-Lipschitz.

The average \(m\) is useful because shifting its iteration range by one changes it by only the initial-to-final drop divided by \(T\): \[\frac1T\sum_{j=1}^T w_j =m-\frac{w_0-w_T}{T}.\] For any fixed representative and wide action, average the inequalities \(w_j(I,q)\le L|q-r|_1+V_r(\alpha;w_{j-1})\) and then minimize over that action. The result is \[m(I,q)-\frac{w_0(I,q)-w_T(I,q)}T \le L|q-r|_1+\min_{\alpha\in\mathcal A_{b,r}}V_r(\alpha;m).\] Thus parent and child cost proxies satisfy the Bellman comparison up to a controlled averaging error. Section 6 will sum this error over a tree of comparison states.

Local evaluation of later cones

The Bellman minimum, and later minima containing selected action cones, admit the same local evaluation rule. This rule is also what bounds the computation when a seed is wrong. We enumerate complete cells because Section 5 will make one shared choice for every cell; that choice must be independent of which query first requests the cell.

For arbitrary local \(w_0\), the scale count in (25) is \(O(1+\log(aF))\), polynomial in \(\ell\). There are \(O((1+F/\theta)^2)\) cells per scale and \(O((1+P)^2)\) grid states per cell. Indeed \(w_0(I,q)/b\le16F\), and \(\theta b/g_b\le P\). Cells and grid points are generated by ranges of integer indices, without scanning unrelated positions. These count bounds do not assume a correct seed. Empty lists give the \(w_0\) option.

We have now obtained nonincreasing propagated estimates and the cost proxy \(m\). The next step uses \(m\) to identify narrow sets of shared child alignments. Expensive searches over the wide actions will use earlier tables; the narrow sets limit calls to current tables.

A band predicted from prefix costs

At a representative \((b,r)\) of a nonleaf, define \[Z=\min_{\alpha\in\mathcal A_{b,r}}V_r(\alpha;m).\] Skip the band computations at this representative unless \(Z\) is finite and strictly positive. Otherwise set \(\widehat v=z(I,r)/Z\), the net shift per unit of predicted cost. If shift accumulated proportionally to this cost along an alignment, a prefix of cost \(C\) would end at shift \(p_0+\widehat v C\). We use this relation to predict the shift at each child cut. We call \(|\widehat v|\le1-\tau\) the velocity test, and skip unless it holds.

For an internal cut \(1\le j<M\) and a real shift \(p\), let \(\Phi_j(p)\) be the minimum prefix cost using the first \(j\) child restrictions of the wide action set. More explicitly, minimize \[|s_1^--r^-|+\sum_{i=1}^j m(I_i,s_i) +\sum_{i<j}|s_{i+1}^--s_i^+|+|s_j^+-(l_j+p)|\] over such prefix states. The wide action family is nonempty whenever the band reaches this step, so these prefix minima are finite. Each function in the minimum is 1-Lipschitz in \(p\), hence so is \(\Phi_j\).

The prefix cost depends on its proposed ending shift. The predicted shift therefore solves the approximate fixed-point relation \(p=p_0+\widehat v\Phi_j(p)\). The velocity test keeps the Lipschitz constant of \(\widehat v\Phi_j\) below one, so all sufficiently accurate solutions lie in a short interval. The band below imposes this relation at every cut.

Let \(\mathcal C_{b,r}\) be the following set of shared-endpoint actions on the scale-\(b\) grid. The outside endpoints are exactly \(r\), consecutive child endpoints agree, all endpoint shifts are within \(6b\) of \(p_0=r^--l\), and the shift \(p\) at every internal cut satisfies \[ |p-p_0-\widehat v\Phi_j(p)|\le\tau\theta b/M. \tag{26}\] All child target states must be valid, so these shared endpoints are in nondecreasing order. Skip if \(\mathcal C_{b,r}\) is empty.

The possible shifts at any fixed cut have diameter at most \(2\theta b/M\). In fact two allowed shifts obey \[|p-p'|\le2\tau\theta b/M+ |\widehat v|\,|\Phi_j(p)-\Phi_j(p')| \le2\tau\theta b/M+(1-\tau)|p-p'|.\] No convexity of the allowed shift set is needed.

We need a uniform cost bound at each child for both action selection and rounding. For a nonempty band, let \(h_i\) be the smallest power of two at least \[\max\left\{b/M,\max_{\alpha\in\mathcal C_{b,r}} w_0(I_i,s_i(\alpha))\right\}, \qquad h_\Sigma=\sum_{i=1}^M h_i.\] Powers of two below one are allowed here. Every band state at child \(i\) has \(w_0\) value at most \(h_i\). These bounds will normalize the online costs and determine a common rounding spacing for each child scale. Skip if \(h_\Sigma>64Fb\). Choose a canonical band action in a fixed ordering and round its two coordinates separately at child \(i\) down to multiples of \(\max\{1,\theta h_i\}\). Denote the resulting action by \(\beta(b,r)\). Different children may round a shared endpoint to different positions, so \(\beta\) can have gaps or overlaps. It is used as a wide action with its connection charge, rather than as a band action. Finally, skip unless it belongs to \(\mathcal A_{b,r}\) and \[ |z(I_i,s_i(\beta))|\le2h_i\qquad(1\le i\le M). \tag{27}\] Representatives passing all these tests will be called unskipped. These tests affect only the band and rounded-action computations; they never remove an action or representative from \(\mathcal B_I\).

Under the fixed good seed, the last two guards on \(\beta\) pass whenever the \(h_\Sigma\) test passes. Indeed, \(\theta h_i\ge\theta b/M\ge b/P\). All relevant quantities are powers of two, so the rounded spacing is a multiple of \(g_b\). Rounding preserves the order of each child’s two endpoints and the range \([0,|y|]\). If its spacing is one, its error is zero; otherwise each coordinate error is less than \(\theta h_i\). Since \(|z|\le w_0\le h_i\) before rounding, \[|z(I_i,s_i(\beta))|\le h_i+2\theta h_i\le2h_i.\] The endpoint shift radius after rounding is at most \(6b+64F\theta b<10b\). Section 6 will prove the earlier \(h_\Sigma\) test on the needed comparison nodes.

The finite-mixture interface for online choices

The online rule uses child values at indices less than \(t\) to select one band action at time \(t\). Its accumulated current-index cost will be compared with that of each fixed band action in Section 7. We encode a mixture of actions by its child-state marginals, with weights chosen to recover the unnormalized sum of child costs.

Fix one unskipped band \(\mathcal C=\mathcal C_{b,r}\). Its coordinates are pairs \((i,s)\), one for each child and each state appearing at that child in a band action. Let \(d_{\mathcal C}\) be their number. Map each action \(\alpha\) to the probability vector \(\rho(\alpha)\) that places mass \(h_i/h_\Sigma\) at \((i,s_i(\alpha))\) for every child, and zero at its other coordinates. Let \(\mathcal Q=\operatorname{conv}\{\rho(\alpha):\alpha\in\mathcal C\}\). Every vector in this convex hull has the same total mass \(h_i/h_\Sigma\) on the coordinates of child \(i\).

Define coordinate vectors \[\begin{align*} \widehat g_j(i,s)&=-d_{j-1}(I_i,s)/h_i,\\ \Delta_j(i,s)&=(d_{j-1}(I_i,s)-d_j(I_i,s))/h_i,\\ u_j&=\widehat g_j+(1-2\kappa)\Delta_j. \end{align*}\] Here \(\widehat g_j\) predicts the negative normalized current cost from the preceding index, and \(\Delta_j\) is the observed correction: \[\widehat g_j(i,s)+\Delta_j(i,s)=-d_j(I_i,s)/h_i, \qquad -h_\Sigma\langle\widehat g_j,\rho(\alpha)\rangle =\sum_i d_{j-1}(I_i,s_i(\alpha)).\] The fixed mass \(h_i/h_\Sigma\) in each child block cancels the normalization by \(h_i\). The objective below uses \(\Delta_j\) only for \(j<t\) and uses \(\widehat g_t\), so its required child indices are all strictly earlier than \(t\).

With entropy \(\mathcal H(\rho)=-\sum_k\rho_k\ln\rho_k\), using \(0\ln0=0\), let \(\rho_t\) maximize \[ \mathcal H(\rho)+ \eta\left\langle\sum_{j<t}u_j+\widehat g_t,\rho\right\rangle \quad\hbox{over }\rho\in\mathcal Q. \tag{28}\] The algorithm computes a finite mixture of band actions whose vector of expected weights is within \(H^{-3}\) in \(\ell_1\) distance of \(\rho_t\), then samples that mixture exactly. Section 9 constructs this mixture using rational arithmetic and proves its stated accuracy and sampling cost. Thus (28) specifies an input-output contract for a finite algorithm, not an optimization oracle.

Only the child histories are needed for this rule, not a transcript of earlier queries at the parent. Parent draws may be keyed by \((I,q,b,t)\) in addition to pass and copy identifiers. Group choices and table values are cached on their complete keys, and every first parent draw uses a fresh source independent of the complete child tables. Section 10 makes the resulting deferred evaluation and its costs explicit.

Shared group samples and the update

For each node \(I\), scale \(b\), cell from Lemma 8, and time \(1\le t\le S\), group all unskipped representatives in that whole cell. The following procedure chooses one member of each nonempty group. It is defined from complete child tables; later we evaluate its required entries on demand.

Sampling and rounding work together here. Sharing the child draws across a cell lets all its representatives reuse the same queried child labels. Rounding then limits how many different states at one such child can occur across the group. This combination, rather than band width alone, bounds the number of current-index recursive calls.

For each power of two \(h\) in \([b/M,64Fb]\), set \[k_h=\min\{M,\lceil Q_1Mh/b\rceil\}.\] For each member \((b,r)\), we estimate the child sum in \(V_r(\beta(b,r);d_t)\) by separating the children according to their \(h_i\). If \(k_h=M\), include the contribution with \(h_i=h\) exactly. Otherwise draw \(k_h\) independent uniform child indices with replacement, using the same draws for every member of this group at this scale. For each sampled child include its \(d_t\) value if its \(h_i=h\), and zero otherwise; multiply the sampled sum by \(M/k_h\). Add the connection charge exactly. Select a member minimizing this estimate, breaking ties by a fixed ordering. Then evaluate its actual action cost using all children. Samples used for different parent groups and times are independent and are independent of descendant randomness.

For example, when \(k_h<M\), there are \(O(Q_1Mh/b)\) sampled child labels, and at most \(O(\theta^{-2}(1+b/h))\) rounded states at each label across the cell. Their product is \(M\ell^{O(1)}\). Lemma 22 proves this count and the analogous bound for exact scales, including executions with inaccurate seeds.

Let \(\Pi_t(I,q)\) be the minimum of \(\mathcal B_I(d_{t-1})(q)\) and the actual selected group costs, each extended from its selected representative by \(L|q-r|_1\). Compute this minimum by (25) and whole-cell enumeration. A group’s choice is cached for the whole cell, independent of which query first requests it. Lemma 8 shows that this local computation equals the global cone minimum for a good seed.

There is also an online action query at each scale passing (25). Put \(r=r_b(q)\) and proceed only if this is an unskipped representative. Draw one action \(\alpha_t\in\mathcal C_{b,r}\) by the rule just defined, which uses child histories with index less than \(t\). Evaluate \[L|q-r|_1+\sum_i d_t(I_i,s_i(\alpha_t)).\] Let \(Y_t(I,q)\) be the minimum of these online query values, or \(+\infty\) if there are none. At a nonleaf define \[ d_t(I,q)= \begin{cases} 0,&w_0(I,q)=0,\\[2pt] \displaystyle\min\left\{\Pi_t(I,q), \max\left\{\frac{\Pi_t(I,q)}{1+\delta},Y_t(I,q)\right\}\right\}, &w_0(I,q)>0. \end{cases} \tag{29}\] Leaves continue to use their exact values. At a positive \(w_0\) state, this update truncates \(Y_t\) to the interval \([\Pi_t/(1+\delta),\Pi_t]\): an inexpensive online action can improve the value only within this interval. The upper endpoint retains the Bellman comparison, while the lower endpoint transfers the spatial regularity of \(\Pi_t\) to \(d_t\) up to a factor \(1+\delta\). For a fixed pass, these definitions are well founded by induction on node height: current-index values are requested only at children, and at a fixed node the remaining refinement values have earlier indices. Section 10 gives the complete lazy evaluation order across passes.

Deterministic invariants

For execution on an arbitrary seed, the local construction still gives nonnegative values at most its local \(w_0\). All representative lists and skipped-band tests remain finite. We use these unconditional facts for work bounds, and do not extend the correctness invariants of Lemma 9 to inaccurate seeds.

Accuracy of one group selection

For a band action define \(x_t(\alpha)=\sum_i d_t(I_i,s_i(\alpha))\). Two band actions differ by at most \(4\theta b/M\) in each child’s endpoint-pair metric. Rounding the canonical action adds at most \(2\theta h_i\), so \(|s_i(\alpha)-s_i(\beta)|_1\le6\theta h_i\). Also \(\operatorname{conn}_r(\beta)\le2\theta h_\Sigma\), because the unrounded action has shared endpoints. It follows that \[ \begin{split} V_r(\beta;d_t)&\le(1+\delta)x_t(\alpha) +(6L+2)\theta h_\Sigma,\\ d_t(I_i,s_i(\beta))&\le2h_i. \end{split} \tag{33}\] The first inequality uses (31). For the second, use \(d_t\le w_0\) and the \(L_0\)-Lipschitz bound to obtain \(w_0(I_i,s_i(\beta))\le h_i+2L_0\theta h_i\le2h_i\).

This is a conditional statement for one whole cell and time. The accuracy proof will not require all group samples throughout the recursion to succeed together. Instead it will charge each group’s failure probability inside an expected regret bound at its comparison node.

Exact paths and rounded child states

Start at a state \((I,q)\) of true cost \(D=c(I,q)\). If \(D=0\), the good-seed bounds force all its estimates to be zero, so assume \(D>0\). Stop a branch at a leaf of the interval tree or at a state of cost zero. At each remaining node, write \(c=c(I,q)>0\), choose the dyadic scale \(b\) with \(b\le c<2b\), and put \[r=r_b(q),\qquad e=|q-r|_1\le 2b/P.\] Choose an optimal alignment for \((I,r)\) and points on this path at the child cuts, in their path order. Use its exact endpoints at the outside cuts. For repeated cuts, repeated path points are permitted; alternatively a vertical segment can be assigned to one of the intervening empty children. Round the internal target anchors down to the grid at scale \(b\). The resulting child states \(q_1,\ldots,q_M\) remain ordered and share endpoints, with outside endpoints exactly \(r\). Denote this action by \(\alpha^*\), and continue the construction at its child states.

Fix a deterministic order for all choices of optimal paths and cut points. The entire comparison tree, including its stopping states, then depends only on the input strings and its starting state. In particular it is independent of every group sample and online draw in the refinement. This tree is used only in the proof.

Mass and energy telescopes

If the warmup masses added exactly from children to parent, the energies \(z^2/m\) would telescope up to endpoint-rounding errors. The masses do not add exactly: a parent’s mass can be either larger or smaller than its children’s total. The warmup inequalities bound the total upward discrepancy, and conservation of mass over the comparison tree then bounds the total downward discrepancy as well. This is why the energy argument can use cost estimates instead of exact additive weights.

At a nonterminal use the representative and child states just constructed, and define \[m_q=m(I,q),\qquad m_i=m(I_i,q_i),\qquad W=\sum_i m_i, \qquad G=W-Z,\qquad R=m_q-W.\] Here \(Z\) is the minimum wide-action cost with child table \(m\), as in Section 5. The comparison action has zero connection cost, so \(W\ge Z\). The lower invariants and the comparison costs imply \[ 0<\max\{c(I,r)/a,|z(I,r)|\}\le Z\le W\le4Fc<8Fb. \tag{37}\] In particular, the denominator \(Z\) defining \(\widehat v\) is positive at every nonterminal comparison representative.

Write \(z_i=z(I_i,q_i)\) and \(z_r=z(I,r)\). Since the child targets share endpoints, \(\sum_i z_i=z_r\). Define the curvature quantity \[ K=\sum_i\frac{z_i^2}{m_i}-\frac{z_r^2}{W}, \tag{38}\] with \(0/0=0\). A zero \(m_i\) necessarily has \(z_i=0\) by the lower invariant. For \(v=z_r/W\), the weighted variance identity is \[ K=\sum_{i:m_i>0}\frac{(z_i-vm_i)^2}{m_i}\ge0. \tag{39}\] These weights are costs supplied by the warmup; they are not interval lengths.

Call a nonterminal bad if \(K>bH^{-1/4}\) or \(G>bH^{-1/4}\); otherwise call it non-bad. These are conditions on the deterministic comparison tree and its warmup values.

Coverage by the computed bands

The preceding estimate controls the cost of exceptional nodes. We now show that at every remaining node which passes the velocity test, the band and rounding guards retain the comparison action. This is the point where cost-weighted curvature produces a usable prediction for the algorithm.

A telescoping bound at every comparison node

An entropy inequality with fixed block masses

Exponential weighting and its potential analysis have a classical role in online learning; see Freund and Schapire (Freund and Schapire 1997). Our predicted objective has the form of optimistic regularized leader, as studied by Rakhlin and Sridharan (Rakhlin and Sridharan 2013, sec. 2). For our action vectors, each child receives a fixed total probability mass. Cost decrements may differ greatly between children, but their variation within a child is small. The following deterministic lemma isolates the reason that this weaker variation bound suffices.

Apply the lemma to an unskipped band \(\mathcal C=\mathcal C_{b,r}\), conditioning on the complete child tables, including the warmup and all indices through \(S\). The band, the scales \(h_i\), and its action hull \(\mathcal Q\) are then fixed. Take the child coordinates as blocks and set \[f_t(i,s)=d_t(I_i,s)/h_i.\] The action hull is compact and convex, and averaging its action vectors gives a positive feasible vector. Every vector has mass \(h_i/h_\Sigma\) in child block \(i\). The refinement invariants give \(0\le d_S\le\cdots\le d_0\le w_0\le h_i\) on band coordinates, so the normalized costs meet the monotonicity and unit bounds of the lemma.

Two states in a child block have endpoint-pair distance at most \(4\theta b/M\). The spatial bound (31), used in both directions and with \(d_t\le h_i\), bounds their cost difference at one index by \(\delta h_i+4L\theta b/M\); the stronger bound at index zero also suffices. Since \(h_i\ge b/M\), the within-block range of \(\Delta_t\) is at most \[ 2\delta+8L\theta\le3\delta\le\kappa/\eta. \tag{55}\] Here \(8L\theta=1024\ell^{-39}\le\ell^{-10}\) and \(3\eta\delta=3\ell^{-5}\le\kappa\). The lemma therefore applies to exactly the objective (28), with \(d=d_{\mathcal C}\). Conditioning on child tables leaves the parent group samples and online draws with their prescribed laws, since their streams are separate from descendant streams. No independence among child tables is needed.

To express the conclusion in action costs, put \[x_t(\alpha)=\sum_i d_t(I_i,s_i(\alpha)).\] The fixed coordinate weights give \[\begin{aligned} h_\Sigma\langle f_t,\rho(\alpha)\rangle&=x_t(\alpha),\\ h_\Sigma\langle f_t+\kappa\Delta_t,\rho(\alpha)\rangle &=x_t(\alpha)+\kappa\bigl(x_{t-1}(\alpha)-x_t(\alpha)\bigr). \end{aligned}\] If \(\alpha_t\) is drawn from the computed mixture, its expected action vector is that mixture’s mean. Lemma 16, with \(\zeta=H^{-3}\), thus gives every fixed band action \(\alpha^*\) and prefix \(0\le s\le S\) the conditional bound \[ \begin{split} \mathbb E\left[\sum_{t=1}^s \left\{x_t(\alpha_t) +\kappa\bigl(x_{t-1}(\alpha_t)-x_t(\alpha_t)\bigr)\right\} \,\middle|\,\text{child tables}\right] \le{}&\sum_{t=1}^s x_t(\alpha^*)\\ &+h_\Sigma\left(\frac{\ln d_{\mathcal C}}{\eta} +2\kappa+sH^{-3}\right). \end{split} \tag{56}\] The next argument shows why the decrement term on the left is enough to cover the clipping in the parent update.

Clipping before and after the first crossing

We now apply the entropy inequality at a comparison node that is not bad and satisfies \(|\widehat v|\le1-\tau\). Lemma 14 ensures that its comparison action \(\alpha^*\) belongs to the unskipped band \(\mathcal C_{b,r}\) and that all its guards pass. Write \[A_t(\alpha)=Le+x_t(\alpha).\] The entropy bound controls these action costs. The following proposition transfers that control to the clipped parent regret.

The expectation in Proposition 17 concerns one node after fixing its child tables. Integrating it and summing over the fixed comparison tree uses only linearity of expectation. No event asserting that every group in the recursive computation succeeds is required.

Summing the comparison regrets

Improving simultaneous seeds

The initial table of Theorem 3 has factor \(A_{\rm init}\). The algorithm maintains a power-of-two factor \(A\) and an integer seed \(U\in[0,N]\) on the full state domain. A seed is called good when \(c\le U\le Ac\) at every state. This is a mathematical event, not a test performed by the algorithm.

While \(A>F\), set \(a=A/F\) and use \(H^2\) independent copies of the refinement, conditional on the previous complete table. For each state, form the \(H^2\) integers \(\lceil a d_S\rceil\), take their upper middle order statistic, and clamp the result to \([0,N]\). This defines the next seed. Update \[ A\longleftarrow4a. \tag{61}\] All copies share the preceding table, but use independent new streams. Entries of each copy and of the new seed are stored on demand; their coherent full-table interpretation is justified in Section 10.

The update preserves powers of two and strictly decreases \(A\), since \(F>4\). Writing \(s_{\rm pass}\) for the number of median passes plus the single final pass below, we have \[ s_{\rm pass} =O\left(\frac{(p_*+1)\ell}{\log_2\ell}\right)<H. \tag{62}\] Indeed each median pass reduces \(\log_2 A\) by \(\log_2 F-2\), starting from \((p_*+4)\log_2 H\) and stopping by \(A\le F\). Apply Lemma 18 to the first failed transition after a good history. The total probability that any seed needed by the algorithm is not good is less than \[ 0.01+H\exp(10H-H^2)<1/10. \tag{63}\] The initial \(0.01\) is the simultaneous initial-table failure probability. This estimate covers adaptive requests because every seed guarantee is over its entire potential domain.

The final answer

When \(A\le F\), use one new refinement with \(a=1\) at the full root state \((I,q)=((0,|x|],(0,|y|))\). Clamp its value to \([0,N]\) and round down to obtain \(\widehat D\). Fix any complete good seed before exposing this final refinement’s independent randomness. For the positive cost \(D=\operatorname{ED}(x,y)\) the refinement theorem gives the deterministic lower bound \(d_S\ge D\) under this conditioning and \[\Pr[d_S>(1+\varepsilon)D\mid U\text{ fixed and good}] \le\frac{1}{\ell\varepsilon}\le\frac1{10}.\] Together with (63), the unconditional failure probability is less than \(1/5\), and thus less than \(1/3\). The lower bound is not asserted on executions with a bad seed.

Clamping preserves the lower bound because \(D\le N\). Rounding down also preserves it because \(D\) is an integer. Neither operation worsens the upper bound. The initial equality test returns zero deterministically when \(D=0\), and the exact branches of Section 2 are also correct. This establishes the accuracy assertion of Theorem 1 on every input. It remains to prove that the finite computations just specified, with all randomness and arithmetic charged, have the claimed expected running time.

Evaluation order and stored randomness

Consider an uncached request for \(d_t(I,q)\). The local cone tests and warmup data determine the representatives, bands and rounded actions that it can use. Evaluating these tests may itself discover further warmup or seed requests. Once the bands are known, the wide Bellman search and the online optimizer gather the needed earlier-index child values and reuse them throughout their action enumerations. The group samples, selected rounded actions and sampled online actions also request current-index child values. The entry is then obtained by the exact minimum and maximum in (29) and cached. The distinction between gathering inputs and repeatedly using them is what permits large local action lists with few recursive calls.

These instructions are well founded before any accuracy event is considered. Number refinement passes in their order of construction, give \(w_j\) index \(j\) and \(d_t\) index \(T+t\), and identify \(d_0=w_T\). Treat a seed median as its \(H^2\) preceding-pass refinement requests, and regard band and group calculations as auxiliary work within the table entry that requests them. Every table dependency strictly decreases the lexicographic triple \[(\text{pass},\ \text{index},\ \text{remaining tree height}).\] A current-index request descends to a child. Warmup and history requests decrease the index; seed requests enter an earlier pass, where the index may reset. Initial entries terminate this order because their estimators do not query any other initial entry. Different copy labels never reset the pass or index. Repeated and empty intervals still have distinct node labels and smaller remaining height at their children.

Fix a lexicographic order on every finite state or action list to resolve ties. Use the following keys for stored objects:

• An initial entry is keyed by its tree-node label and its two state endpoints. Its private random source supplies all guesses and thresholds in that initial-entry calculation.

• A later seed entry is keyed by its pass, node, and endpoints. Its stored value is the clamped integer median of the separately identified copies of the preceding refinement.

• A warmup or refinement entry is keyed by its table kind, pass, copy, node, index, and endpoints. The table kind distinguishes \(w_j\) from \(d_t\), with \(d_0=w_T\) identified.

• The warmup-derived data for a representative are keyed by the pass, copy, node, scale \(b\), and endpoints \(r\). These data determine its band, scale labels, and rounded action and do not depend on \(t\).

• A group result is keyed by the pass, copy, node, scale \(b\), the two integer cell indices, and \(t\). It contains the chosen member and its actual evaluated cost. Its random sources also distinguish the scale \(h\) and the sample number.

• An online draw is keyed by the pass, copy, node, queried state \(q\), scale \(b\), and \(t\). Its representative is \(r_b(q)\). Repeated requests use the stored action, whereas different queries may have independent draws even if their representatives agree.

In particular, a requested group is computed over its entire specified cell. Its result does not depend on which query first requested it. Repeated list processing and numerical iterations use dictionary lookups for previously gathered recursive inputs; their lookup costs will be included below.

Generate fresh fair random bits on the first calculation of each random object, and retain its outcome. Different copies, passes, nodes, and specified random objects have independent sources. This can be viewed equivalently as assigning independent bit streams to all keys in advance. By the dependency order above, deciding to request an object uses only already exposed streams. This equivalence is a distributional description, not an instruction to allocate all streams or tables.

For a given refinement copy, the complete child tables depend on descendant streams and earlier passes, but not on fresh streams of the current parent. Conditioning on those tables consequently leaves its group samples and online draws with their specified independent laws. This justifies the conditioning used in the accuracy analysis. The whole-domain seed guarantees are retained; adaptively requesting a seed entry does not replace such a guarantee by one for a fixed query.

For the expected running time, we use a different conditioning. Before the first request of an initial entry, none of its private random bits has been exposed. Conditional on the previous execution and its first request, the expected cost bound of Theorem 3 therefore still applies. Later requests only look up its stored answer. This argument does not condition on the initial entry being correct.

Finite local calculations on inaccurate seeds

We first bound the numbers manipulated by the implementation. These bounds concern its finite local rules, rather than the global cone identities that were proved under a good seed.

The locality bounds themselves are also unconditional. The scale range for \(w_0\) has ratio polynomial in \(A\), and radius divided by grid spacing \(O(A^2P)\). For the other local searches, the ratio of the endpoints of the scale interval is \(128aF\). It admits \(O((p_*+1)\ell)\) scales. At any such scale, \(w_0(I,q)/b\le16F\), so the square specified in the local rule meets \[O\bigl((1+F/\theta)^2\bigr)\] cells. A cell has \(O((1+P)^2)\) representative candidates. All these lists can be generated by ranges of integer multiple indices, without scanning unrelated string positions.

The current-index child budget

The following count is the reason for using rounded actions and samples shared across a cell. At a small scale \(h\), many rounded states can occur at one child, but few children are sampled. Their respective factors \(b/h\) and \(h/b\) cancel. At a large scale, the rounded list is already small enough to inspect every child. The count concerns distinct recursive inputs; repeated uses of an input are charged later as lookups.

All other recursive inputs are earlier in the evaluation order. Constructing \(w_0\) uses a previous seed. Computing bands, prefix minima, and scale labels uses warmup data. In \(\Pi_t\) the wide Bellman option uses \(d_{t-1}\) on children. The online coefficient vector uses \(d_j\) only for \(j<t\); it does not require the past transcript of actions at the parent. The numerical procedure of Section 9 therefore introduces no hidden current-index child queries.

Earlier inputs and local arithmetic

Counting the dependency paths

We now quantify the dependency order from the first subsection. After inlining seed medians and auxiliary calculations, each dependency has one of two forms. A same-pass, same-index dependency descends to a child; Lemma 22 bounds its number by \[D_{\mathrm{same}}=M\ell^{C_1}.\] Every other dependency either decreases the index in the same pass or switches to an earlier pass, and its number is bounded by \[D_{\mathrm{earlier}}=H^{C_2(p_*+1)}\] for absolute constants \(C_1,C_2\). Such dependencies stay at the same physical node or descend; they never ascend the tree. Auxiliary band and group calculations have been collapsed into these evaluations, so they create no same-index cycle at a node.

Let \(s_{\mathrm{pass}}\) be the number of refinement passes, including the final pass, and put \[K_{\mathrm{dep}}=s_{\mathrm{pass}}(T+S+1).\] A dependency path ending at depth \(j\) has at most \(j\) same-index edges, because each descends one level. It has at most \(K_{\mathrm{dep}}\) other edges: indices strictly decrease between pass switches, and passes strictly decrease at switches. Copy identities do not reset this order. These bounds hold independently of every seed or sampling accuracy event.

Unfolding the stored dependency graph only overcounts calculations. The number of paths ending at depth \(j\) is at most \[\begin{align*} &\sum_{r=0}^j\sum_{s=0}^{K_{\mathrm{dep}}} \binom{r+s}{r}D_{\mathrm{same}}^r D_{\mathrm{earlier}}^s \\ &\qquad\le (j+1)(K_{\mathrm{dep}}+1)2^{j+K_{\mathrm{dep}}} M^j\ell^{C_1j}H^{C_2(p_*+1)K_{\mathrm{dep}}}. \tag{68}\end{align*}\] Some index-decreasing edges descend too; ignoring that additional descent only enlarges this bound.

Write \(q_*=p_*+1\). The parameters and pass count give \[J=O(H/\ell),\qquad T=O(H^{3/4})=o(S),\qquad K_{\mathrm{dep}}=O\left(\frac{Hq_*}{\ell\log\ell}\right).\] Consequently \[\begin{align*} J\log\ell&=O(H\log\ell/\ell)=o(H),\\ q_*K_{\mathrm{dep}}\log H &=O\left(\frac{Hq_*^2}{\log\ell}\right)=o(H),\\ J+K_{\mathrm{dep}}&=o(H). \end{align*}\] For the second limit, use \(q_*^2=O(\sqrt{\log\ell}+1)\). All factors beyond \(M^j\) in (68) are therefore \(2^{o(H)}\), uniformly for \(0\le j\le J\). The number of expanded evaluations at depth \(j\) is bounded by \[ M^j2^{o(H)}. \tag{69}\] This is a deterministic count for the local implementation, not a count conditioned on the success of its estimates.

Expected time and logarithmic-word storage