Almost-linear edit distance?

0:00Edit distance

Edit distance counts the fewest single-character insertions, deletions and substitutions that turn one string into another. Kitten becomes sitting in three: change the k to an s and the e to an i, then add a g. The Wagner–Fischer dynamic program fills a table with one entry for every pair of prefixes, so two strings of length n take about n squared steps. If you knew roughly where the best alignment runs, you could fill only a narrow band. In our check, two strings of about 3,000 symbols differ by 60 planted edits. Keeping only cells within 20 of the diagonal gave the exact distance, 60, from about 1/74 of the table. Within 10, it overestimated, at 123, and within 5, it could not even reach the end, because the second string is 9 symbols longer. The hard part is knowing where the band should go. Exact computation seems stuck near quadratic time: Backurs and Indyk showed that a strongly subquadratic exact algorithm would refute the Strong Exponential Time Hypothesis. Ukkonen, and Landau and Vishkin, gave exact methods that are fast when the distance is small. Approximation had long offered another route. Early factors grew with n, from Bar-Yossef, Jayram, Krauthgamer and Kumar, and from Batu, Ergün and Sahinalp. Andoni, Krauthgamer and Onak reached a polylogarithmic factor in time n to any fixed power above one. Chakraborty, Das, Goldenberg, Koucký and Saks reached a constant factor in truly subquadratic time, and Andoni and Nosatzki a constant factor in time n to any fixed power above one, with the constant depending on that power. For accuracy 1 + ε, Mao and Rubinstein’s recent algorithm beats quadratic time, though not by any fixed power of n.

1:51The claim

Result 121 is one OpenAI preprint, 46 pages, dated September 24. It claims one uniform randomized algorithm that takes two strings and a rational ε between zero and one, and returns an integer that, with probability at least 2/3, lies between the edit distance and (1 + ε) times it. For every fixed ε, the worst-case expected running time on strings of total length N is N^(1+o(1)), on a logarithmic-word machine, counting all arithmetic, sampling and data structures. Equal strings always get zero, and the symbols may be integers as large as a polynomial in N. The fine print matters. The constants, and the length at which the bound applies, may depend on ε, and nothing is claimed about how the cost grows with 1/ε. Below a threshold, the algorithm simply runs the exact dynamic program, and the paper says its thresholds are very large. In our check of its parameter rule, even 10^80 symbols stay far below the cutoff, so the fast branch only starts at lengths no computer could store. OpenAI published a Lean proof of the full statement, about a thousand files and 137,000 lines with its imports, not counting Mathlib. The statement alone runs to 19,000 lines, because it defines the algorithm and counts its work step by step. We have not run the Lean check ourselves.

3:23How the algorithm works

The algorithm cuts the first string into a tree of intervals, down to single characters. An interval state pairs a source interval with a target interval in the second string, and its true cost is the edit distance between those two pieces. An action at a node assigns a target interval to each child, and is charged the children’s costs plus the gaps and overlaps between consecutive targets and at the two ends. These connection charges let nearby actions be compared even when their targets do not join exactly, and with true child costs the total is still an upper bound for the parent. In our check, blocks of 100 matched to back-to-back windows of the same length gave 88 against a true distance of 39; letting each window stretch or shrink by up to 3, the best choice reached the exact distance, 39. Everything starts from a seed: a table of coarse upper estimates for every interval state, adapted from the shift tree and precision sampling of Andoni, Krauthgamer and Onak. The shift tree splits a piece into a balanced tree of blocks, each allowed its own shift, paying twice each change of shift from its parent. That gives an upper bound, too large by at most a slowly growing factor. Precision sampling avoids computing all of it, by giving different blocks random, uneven precisions. The guarantee holds at every state at once, so it survives adaptive requests; entries are computed only when requested, each from its own private random stream, which keeps the expected cost of each request under control. Refinement passes then shrink the approximation factor. A refinement pass first propagates the seed through a wide family of actions and averages the results into cost proxies. At a cut in the first string, the alignment’s shift is its target position minus its source position. Spreading the total shift change in proportion to predicted cost tells how the shift should evolve, and requiring agreement with that leaves a narrow band of target positions at each cut, computed from the proxies alone. The analysis compares with optimal alignments, rounded into a comparison tree that the algorithm never computes. A cost-weighted variance of their departures from the prediction telescopes, which controls the total cost of the places where the prediction fails. In our illustration, with exact costs in place of proxies, all 31 cuts along an optimal alignment stayed within 4 of the cost-proportional line, while the shift itself strayed as far as 12 from the diagonal. Inside a band, an entropy-regularized rule, in the online-learning framework of Rakhlin and Sridharan, predicts an action from earlier child values, and a finite Frank–Wolfe procedure approximates it closely in exact rational arithmetic, and the action is then sampled exactly. Some intermediate estimates can fall below the true cost, so the analysis raises them to the true cost, and then an underestimate in one place cannot cancel an error elsewhere. Repetitions and medians turn the result into a better seed, the passes repeat, and one last refinement gives the answer. The work bound comes from reuse: searches draw on child values already gathered, only slightly more calls than the tree’s branching factor need values from the current round, and table entries are computed only on demand.

6:43Where it stands

The preprint is not peer reviewed and has not been revised. OpenAI’s Lean formalization covers the full theorem for a concrete binary algorithm, including expected work and polynomial space, with work measured by the counter defined in the statement; we have not run it. The paper is not among those OSVerify reviewed, and we have seen no expert review. If it holds, edit distance can be approximated within any fixed factor 1 + ε in almost-linear expected time. Before this, near-linear time gave only constant factors, and accuracy 1 + ε needed nearly quadratic time. The thresholds are astronomically large, so this is a statement about the limit, not a practical tool.