An almost-linear approximation scheme for edit distance

Source and verification

This article explains family 121 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Edit distance as an alignment problem

For explicitly stored strings $x$ and $y$, the unit-cost edit distance $\mathrm{ED}(x,y)$ is the fewest single-symbol insertions, deletions, and substitutions needed to transform one into the other. Each operation costs one. Let $N=|x|+|y|$.

A useful representation is the grid of prefix pairs $(i,j)$. Horizontal and vertical steps cost one, corresponding to deleting or inserting a symbol. A diagonal step costs zero when the next symbols agree and one otherwise. The shortest path from $(0,0)$ to $(|x|,|y|)$ is an optimal alignment.

The standard dynamic program writes $D_{i0}=i$, $D_{0j}=j$, and

$$D_{ij}=\min \{\begin{array}{l}{D}_{i-1,j}+1,\\ D_{i,j-1}+1,\\ D_{i-1,j-1}+1_{x_i\ne y_j}.\end{array}$$

It examines a quadratic grid. For example, transforming cat into cut needs one substitution; transforming cat into cart needs one insertion. Pure insertion–deletion distance would charge the first example two, so the operation convention matters.

Always

$$\begin{array}{c}\mathrm{ED}(x,y)\ge ||x|-|y||,\\ \mathrm{ED}(x,y)\le \max \{|x|,|y|\}.\end{array}$$

The first bound counts the net length change. For the second, substitute along the common length and insert or delete the remainder. The challenge is to approximate the optimum closely without inspecting all prefix pairs.

🏷️ The approximation and runtime contract

Symbols are integer labels of polynomial magnitude in $N+2$, stored in logarithmic-size words. The alphabet may grow with the input length. The accuracy $\epsilon \in (0,1)$ is rational.

Manuscript statement

Write $d=\mathrm{ED}(x,y)$. One uniform randomized algorithm returns a nonnegative integer $\hat{D}$ satisfying

$$\mathrm{Pr}[d\le \hat{D}\le (1+\epsilon )d]\ge \frac{2}{3}.$$

For every fixed rational $\epsilon$, its worst-case expected work is $N^{1+o(1)}$ as $N\to \infty$. Equal strings return zero deterministically. (OpenAI, 2026)

The expectation is over internal randomness, for each input; it is not an average over random strings. Input reading, preprocessing, numerical work, sampling, and data structures are charged. The output is a distance estimate, with no required edit script.

The one program accepts the accuracy as input, but the asymptotic guarantee is pointwise for each fixed accuracy. It does not assert polynomial dependence on $1/\epsilon$, or the same time bound when $\epsilon$ shrinks with $N$. The algorithm uses exact computation below very large accuracy-dependent thresholds.

The integer output makes small distances especially restrictive. On the success event, if $\mathrm{ED}=1$ and $\epsilon <1$, then $1\le \hat{D}<2$, forcing $\hat{D}=1$. A generic additive error of one would already be insufficient. The zero-distance case is handled explicitly rather than lost in an additive estimate.

🏷️ Recursive interval states

Partition the source string into a tree of intervals, ending at intervals of length at most one. A state consists of a source interval and a target interval in $y$. Its true cost is the edit distance between those substrings.

An action at an internal node chooses one target interval for each source child. If the target intervals join exactly, summing child edit scripts gives a parent script. The source permits nearby endpoints that leave gaps or overlaps, charging endpoint penalties for those discrepancies. This enlarged action space makes rounding and comparison possible while paying for inconsistencies.

The algorithm cannot enumerate all recursive child distances. The proof needs two ingredients simultaneously: a sufficiently narrow action family containing a good comparison alignment, and an accounting bound on the child values actually requested. Good numerical accuracy without the second ingredient would still cost too much time.

🏷️ Accuracy under adaptive queries

The initial seed is a table of coarse integer upper estimates for interval-state costs. The algorithm evaluates only requested entries. Nevertheless, its good accuracy event covers the whole domain, because later requests can depend on earlier random answers.

A guarantee for one fixed query does not automatically survive this adaptivity. If a caller searches many entries, it may preferentially select rare failures. A simultaneous table event prevents that selection issue.

Work uses a different probability statement. Each initial entry has a private random stream, and its expected evaluation cost is bounded conditional on the request that first exposes it. In a schematic sequence of first requests, the tower property gives

$$\mathbb{E}\sum _j{C}_j=\sum _j\mathbb{E}[\mathbb{E}(C_j\mid {\mathcal{F}}_{j-1})],$$

where ${\mathcal{F}}_{j-1}$ records the prior query history. Conditional bounds control this sum even when the identities of the requested entries depend on that history. The source implements the streams and caching needed for its actual recursion; independence should not be assumed merely because an entry was not previously printed.

🏷️ Predicting alignment shifts

Along an alignment, define the shift as target position minus source position. Matching and substitution steps leave this shift unchanged. Insertions and deletions change it by one in absolute value. Thus shift variation is tied to edit cost, rather than to the full string length.

One refinement first builds preliminary cost proxies from a wider family of actions. It predicts how shift evolves as cumulative proxy cost grows, then restricts target positions at each cut to a narrow band around that prediction. The band is computed from available estimates; the algorithm does not know an optimal alignment.

For analysis, fix optimal alignments and recursively round their endpoints. This creates a comparison tree that is never constructed by the algorithm. A cost-weighted variance measures deviations of its shifts from the predicted evolution. The variance telescopes across the decomposition, with separate charges for disagreement among the proxies.

Nodes with large discrepancy consume a controlled total cost budget. At the other nodes, either the substring-length difference already explains almost all predicted cost, or the computed band contains the comparison action. The proof therefore pays for exceptional nodes without forcing every local prediction to be accurate. (OpenAI, 2026)

🏷️ Improving a seed without hiding underestimates

Within a band, an entropy-regularized rule predicts actions using earlier child values. Shared samples compare rounded actions at nearby representatives. A finite optimization procedure implements the rule, rather than invoking an exact real-valued optimization oracle.

After conditioning on complete child tables, the parent samples still have their prescribed laws. An online comparison inequality bounds accumulated excess over the selected comparison action. This conditional setup is part of the proof: arbitrary reuse of randomness across parent and child tables would not justify the same estimate.

Some intermediate values can underestimate true costs. To prevent a negative local error from canceling a positive error elsewhere, the analysis replaces an estimate $A$ by $\max \{A,D\}$, where $D$ is the true local distance. The resulting error is $(A-D{)}_{+}$. This clipping is an analytic device; the algorithm is not given the true child distances.

Summing positive errors over the comparison tree yields a small expected error at a fixed state, together with a deterministic multiplicative lower bound. Markov’s inequality converts expected positive error into a fixed-state success probability. Independent repetitions and medians amplify that probability; rescaling and a simultaneous guarantee turn the result into a better one-sided seed. Repeating the improvement and making a final refinement yields the stated accuracy.

For orientation, if a nonnegative error $E$ satisfies $\mathbb{E}E\le \delta D$, then

$$\mathrm{Pr}[E>3\delta D]\le \frac{1}{3}$$

when $D>0$. This elementary estimate explains why positive-error control is useful. The manuscript’s complete amplification must also cover all needed states, the lower bound, and the zero case; this one-line inequality is not the whole accuracy proof.

🏷️ Charging actual recursive evaluations

A wide action search may inspect many candidate actions while reusing the same child values. Its arithmetic cost and the number of fresh recursive evaluations are therefore different quantities.

Only shared group samples, selected rounded actions, and actual online draws request child values at the current refinement index. Common rounded grids keep their number slightly above the tree’s branching factor. Along a dependency path, a call either moves downward in the interval tree at the same index or decreases a refinement index or pass.

The source counts both kinds of moves, including the work of exact random sampling and rational arithmetic. This is the recursion accounting behind the almost-linear expected bound. Treating every inspected action as a full fresh recursive call would give a much larger recurrence; treating the numerical optimization as free would undercount the runtime.

No implementation benchmark was run for this article. The result is an asymptotic algorithmic claim with substantial geometric, probabilistic, and numerical interfaces, rather than a practical runtime recommendation.

🏷️ Pairwise estimation and common embeddings

An algorithm estimating the distance of one supplied pair need not construct a single map preserving distances among all strings. Thus the claimed approximation scheme is compatible with lower bounds on distortion of common embeddings into ${\ell }_1$.

Likewise, a conditional lower bound for exact edit distance does not automatically prohibit a fixed-accuracy randomized approximation. Output requirements, randomness, accuracy dependence, and operation costs must be matched before transferring a lower bound between models.

🏷️ Key steps and proof outlines

Telescoping node regrets into one root error

The accuracy section analyzes a fixed comparison tree built from true alignments. At each state, replace an estimate $d_t$ by ${\overline{d}}_t=\max \{c,d_t\}$, where $c$ is that state’s true cost. This replacement is used only in the proof. A node regret measures the difference between its clipped value and the sum of its children’s clipped values plus endpoint penalties. Summing over the tree cancels all internal child values. (OpenAI, 2026)

The resulting identity has only terminal costs, endpoint penalties and node regrets. Average over the refinement indices $t=1,\dots ,S$. Because root estimates decrease in $t$, their final positive excess is bounded by that average. The comparison-tree geometry charges the terminal and endpoint terms to a small fraction of the true root distance. The remaining nodes are split into bad-prediction nodes, nearly extremal shift nodes and nodes whose comparison action lies in the computed band. Each class has its own budget.

The important cancellation is deterministic. Expectation enters afterward, when applying the conditional online-comparison estimate at each node. Conditional on its complete child tables, the node’s fresh sampling still has the required law. The tower property then permits summation over nodes without assuming they are mutually independent.

Median amplification produces a simultaneous next seed

Suppose the current seed is good everywhere, with $c\le U\le Ac$. One refinement gives a deterministic lower bound and an expected positive-error bound at each fixed state. Markov’s inequality implies that an individual copy exceeds twice the true cost with probability at most $1/\ell$, for the source’s large parameter $\ell$.

Run $H^2$ copies with independent new streams conditional on the old complete seed. For a fixed state, the probability that at least half fail is at most

$$2^{H^2}{\ell }^{-H^2/2}\le e^{-H^2}.$$

The first factor bounds choices of a failing subset; independence applies across copies at the same state. If the state domain has size below $e^{10H}$, a union bound gives failure probability at most $\exp (10H-H^2)$ for the entire next table. No independence between different states is needed.

The next seed is the median of appropriately scaled, rounded values. Its factor updates from $A$ to $4A/F$, with $F>4$. Thus each pass contracts the logarithm of the approximation factor by a definite amount. A first-failed-pass union bound, conditioned on the preceding good history, shows that all seeds needed by adaptive queries are simultaneously good with high probability.

Integer output and the final one-sided guarantee

Once the seed factor is at most $F$, a new root refinement has deterministic lower bound $d_S\ge D$ conditional on that good seed and expected positive excess at most $D/\ell$. Therefore

$$\mathrm{Pr}[d_S>(1+\epsilon )D]\le \frac{1}{\ell \epsilon }.$$

Choose the accuracy-dependent threshold so this is small. Clamp to $[0,N]$ and round down. Since the true edit distance $D$ is an integer, rounding down cannot cross below $D$ on the good event; it also cannot worsen the upper bound. The zero-distance case is tested directly, avoiding division by zero in the relative-error argument.

Why refinement cost does not equal action count

Many candidate alignments reuse the same child values. The work proof counts first evaluations of memoized states and the finite arithmetic required to compare actions separately. A dependency either descends in the interval tree at the same refinement index or decreases the refinement/pass index. Common rounded grids bound how many distinct children are actually requested. Private streams give conditional expected bounds on those first requests even when their identities were chosen adaptively.

This final accounting is logically independent of the simultaneous accuracy event. Accuracy requires protection over every potential state; runtime only charges states actually evaluated. Enumerating the full good table would squander the almost-linear bound, while proving accuracy only for the evaluated states after selection would risk adaptive bias.

See Also

• Edit-distance embedding obstructions treats one common map for an entire metric space, explaining the distinction from pairwise estimation.
• Almost-linear exact matching charges work on every execution, whereas this family bounds expected work for each fixed accuracy.
• Contingency-table sampling distinguishes bounded-time approximation from exact output with expected runtime, another setting where those quantifiers matter.

🏷️ Manuscripts and verification scope

• An Almost-Linear Approximation Scheme for Edit Distance — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The scope records fixed-accuracy expected work, the success probability, deterministic zero on equal inputs, and polynomial space on every execution. It does not turn expected work into an every-path almost-linear time bound. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026. An Almost-Linear Approximation Scheme for Edit Distance.