Approximating edit distance in almost-linear time
From OpenAI Aftermath
Approximating edit distance in almost-linear time asks for a (1 + ε)-approximation of the unit-cost edit distance of two strings in time close to linear in their total length. A manuscript in OpenAI's public mathematics collection (github.com/openai/math), dated 24 September 2026, claims a randomized approximation scheme with this accuracy for every fixed ε, in worst-case expected time N1+o(1) for strings of total length N. This page summarizes the published claim and lists publicly available follow-up work. Statements are the respective authors' claims; the publication of a paper or a formal proof is not presented here as independent verification.
Background
- As recounted in the introduction of the manuscript:
- The dynamic program of Wagner and Fischer computes the unit-cost edit distance in quadratic time, and Masek and Paterson saved a logarithmic factor for fixed alphabets. Backurs and Indyk showed that a strongly subquadratic exact algorithm would refute the Strong Exponential Time Hypothesis; this does not rule out approximation.
- Approximation factors improved from n3/7 in quasi-linear time (Bar-Yossef, Jayram, Krauthgamer and Kumar) and n1/3+o(1) (Batu, Ergün and Sahinalp) to a polylogarithmic factor in time n1+ξ (Andoni, Krauthgamer and Onak), a constant factor in subquadratic time (Chakraborty, Das, Goldenberg, Koucký and Saks), and a factor depending only on ξ in time O(n1+ξ) (Andoni and Nosatzki).
- For accuracy arbitrarily close to one, Mao and Rubinstein obtained a randomized (1 + ε)-approximation in time n2/2(log n)Ω(1) for every fixed ε > 0.
The original result
- Claim. Theorem 1.1 of An Almost-Linear Approximation Scheme for Edit Distance states that one uniform randomized algorithm, given strings x, y and a rational ε in (0, 1), returns an integer that lies between ED(x, y) and (1 + ε) ED(x, y) with probability at least 2/3. For every fixed rational ε, its worst-case expected running time on strings of total length N is N1+o(1) on the logarithmic-word RAM, counting all preprocessing, numerical work, sampling and data structures. Symbols may be integers of polynomial size in N, and equal strings return zero deterministically.
- The manuscript states that the constants and the length threshold may depend on ε, that no polynomial dependence on 1/ε is asserted, and that below very large thresholds the algorithm computes the distance exactly.
- Method, as described: initial estimates adapt the shift tree and precision sampling of Andoni, Krauthgamer and Onak. A refinement predicts narrow bands for the alignment from preliminary cost estimates; a telescoping bound controls where the predictions fail, and an entropy-regularized prediction rule, implemented by a finite Frank–Wolfe procedure, controls the accumulated error. Lazy evaluation bounds the number of child distances actually computed.
- Source (openai/math repository, commit
7ef5c0c): An Almost-Linear Approximation Scheme for Edit Distance, dated 24 September 2026, 46 pages. - Formalization, as described by the repository. The scope note lean/docs/121.md states that the formalization gives a randomized (1 + ε)-approximation for every fixed rational 0 < ε < 1, correct with probability at least 2/3 and returning zero on equal strings, with expected work at most (N + 2)1+η for every fixed η > 0 and all sufficiently large N and with polynomially bounded space.
Public follow-up work
| Date | Work | Relation | Public claim | Public status (checked 29 October 2026) |
|---|---|---|---|---|
| 2026-10-07 | An almost-linear approximation scheme for edit distance, an article of the Latent Seminar blog at lowrank.github.io | Reading (exposition) | Explains edit distance as a shortest path in the grid of prefix pairs, the manuscript's approximation and running-time contract for a fixed accuracy, recursive interval states, accuracy under adaptive queries, the prediction of alignment shifts, improving a seed estimate without hiding underestimates and charging only the recursive evaluations actually made, with outlines of the key steps. | Blog article; it states that its review covers statements, introductions and selected proof mechanisms and is not an independent verification of the complete proofs. |
| 2026-10-08 | J. Wang, An Almost-Linear Approximation Scheme for Metric-Weighted Edit Distance, manuscript in Jihan-Wang/metric-weighted-edit-distance (GitHub, commit f212909) |
Extension | Adapts the manuscript's refinement framework to edit costs given by an arbitrary metric on the alphabet extended by a gap symbol. For every fixed rational ε > 0 it claims a randomized estimate within a factor 1 + ε with probability at least 5/6, in expected time N to the power 1 + O[log log log N / log log N], with constant-time metric queries and exact real arithmetic. The README states that the new parameter schedule also sharpens the explicit bound for unit costs, where it reads the original schedule as giving the exponent 1 + O[[log log log N]−1/4], and that this compares analyzed upper bounds only. | GitHub repository with the manuscript, dated 7 October 2026, and reading notes; no implementation or formal proof. The README states that component-wise manual audits found no theorem-breaking defect and invites review. The manuscript states that OpenAI's Codex and Anthropic's Claude assisted with proof development, parameter calculations, literature research, drafting and proof review. |
| 2026-10-15 | B. Hu, T. Kociumaka, J. Nogler, B. Saha, Tree Edit Distance: Near-Linear-Time Approximate, Sublinear, and Dynamic, arXiv:2610.22250v1 | Related work | For tree edit distance, gives an approximation within a factor no[1] in linear time and, for every 0 < δ < 1, a factor [log n]O[1/δ] in time n1+δ, the first sublinear-time algorithm and dynamic algorithms, through a hierarchical tree decomposition that transfers ideas from string edit distance. A footnote cites the manuscript as a very recent claim of a randomized 1 + ε approximation for string edit distance in expected time n1+o[1] for fixed ε, next to Mao and Rubinstein's subquadratic scheme. | arXiv preprint, version 1; to appear in SODA 2027. |
| 2026-10-16 | AI Proved What?, episode 121 Almost-linear edit distance?, remade version of 26 October 2026 | Reading (exposition) | Video explainer of the claim that one randomized algorithm, given two strings and a rational ε between 0 and 1, returns an integer between their edit distance and 1 + ε times it with probability at least 2/3, in worst-case expected time N1+o[1] for every fixed ε, with equal strings always getting zero. The episode states that the constants and the length threshold may depend on ε, that nothing is claimed about the growth in 1/ε, and that by the paper's parameter rule the fast branch only starts at astronomically large inputs, so this is a statement about the limit, not a practical tool. | Web page and video; the site states that its scripts and animations are produced with AI assistance and that the narration is an AI-generated voice. Status record last checked 27 October 2026: posted as a preprint: OpenAI, 46 pages, dated September 24, 2026; under expert review: not yet; peer reviewed: not yet; checked in Lean: OpenAI published a Lean proof of the full theorem for a concrete algorithm, the site has not run the check. The page also states that the Lean formalization covers a concrete binary algorithm including its expected work and polynomial space, matched against a comparator statement of 19,169 lines, that the site has not run it, and that it has seen no expert review. |
Notes
- The background summarizes the manuscript's own account of earlier work.
- The follow-ups state AI assistance as recorded in the table.
- The list covers follow-ups found in public sources up to the date above; it is not a priority or completeness claim.
