# Approximate edit comparison for long documents

Edition: 8 October 2026. Initial decision: **Conditional engineering**. The product interpretation and pricing are hypotheses; independent proof and buyer validation remain open.

## Research finding

Family 121 claims a randomized 1+epsilon approximation to unit-cost edit distance in near-linear expected time at fixed accuracy. It estimates distance; the selected statement does not produce an alignment. Family 099 warns that embedding edit distance into L1 necessarily incurs growing worst-case distortion.

## Problem and buyer

Document archives and duplicated-text pipelines can spend substantial work comparing long candidate pairs. Exact unit-cost edit distance can be an expensive final filter even after candidate retrieval.

## What the finding could enable

An approximate comparison service could triage long pairs and defer expensive exact work. It could support archive deduplication or change magnitude summaries while retaining a separate exact alignment step for user-facing diffs.

## Technical and commercial limits

The guarantee is asymptotic, randomized and tied to fixed epsilon and explicit integer strings. It does not establish semantic equivalence, a diff, arbitrary weighted edits, or cheap approximate-nearest-neighbor indexing. Tokenization changes the problem.

## Minimal architecture

Canonical tokenization -> exact equality test -> approximate distance backend -> confidence-aware threshold policy -> exact fallback. Persist preprocessing and confidence metadata to make comparisons reproducible.

## Existing alternatives and differentiation

RapidFuzz already supplies optimized Levenshtein routines. Compare directly on the buyer's actual string lengths and edit regimes; a theoretical exponent is insufficient differentiation.

## Monetization hypothesis

Hypothesis: usage pricing only after measurable compute savings, or AUD 2,000-8,000 for a document-pipeline integration. Short-string matching is likely too well served for an attractive new product.

## Validation experiment

Measure runtime and error across identical, near-identical, repetitive and unrelated strings. Use exact distances as ground truth wherever feasible and test threshold false positives and false negatives independently.

## Conditions to reject or defer

Reject if the crossover exceeds realistic document sizes, approximation causes unacceptable threshold mistakes, or buyers need alignments that dominate total cost.

## Next concrete action

Extract finite numerical routines and parameter schedules, then estimate their overhead before writing a full backend.

## Source evidence

Repository sources are pinned to revision `fd4aeeb2ee4fc729c18d98444fed42fd0529eeeb`. Selected scope notes and manuscript statements have been reviewed to the extent described above; these links do not represent successful kernel checks.

### Family 121

Subject: Almost-linear approximation of edit distance.

- [An Almost-Linear Approximation Scheme for Edit Distance](https://github.com/openai/math/blob/fd4aeeb2ee4fc729c18d98444fed42fd0529eeeb/preprints/An-Almost-Linear-Approximation-Scheme-for-Edit-Distance-September-24-2026/paper.pdf)
- [Formal scope notes](https://github.com/openai/math/blob/fd4aeeb2ee4fc729c18d98444fed42fd0529eeeb/lean/docs/121.md)

### Family 099

Subject: The sharp exponential scale of edit-distance distortion.

- [Edit Distance in l1: Matching Bounds up to Constants in the Exponent](https://github.com/openai/math/blob/fd4aeeb2ee4fc729c18d98444fed42fd0529eeeb/preprints/Edit-Distance-in-l1-Matching-Bounds-up-to-Constants-in-the-Exponent-September-27-2026/paper.pdf)
- [Finite-Circle Obstructions, Binary Codes, and Histogram Embeddings for Edit Distance](https://github.com/openai/math/blob/fd4aeeb2ee4fc729c18d98444fed42fd0529eeeb/preprints/Finite-Circle-Obstructions-Binary-Codes-and-Histogram-Embeddings-for-Edit-Distance-September-27-2026/paper.pdf)
- [Tree Constructions for the l1 Distortion of Binary Edit Distance](https://github.com/openai/math/blob/fd4aeeb2ee4fc729c18d98444fed42fd0529eeeb/preprints/Tree-Constructions-for-the-l1-Distortion-of-Binary-Edit-Distance-September-27-2026/paper.pdf)
- [Formal scope notes](https://github.com/openai/math/blob/fd4aeeb2ee4fc729c18d98444fed42fd0529eeeb/lean/docs/099.md)

## Current alternative sources

Primary documentation reviewed on 8 October 2026. Product availability demonstrates alternatives, not demand or willingness to pay for this proposal.

- [RapidFuzz Levenshtein implementations](https://rapidfuzz.github.io/RapidFuzz/Usage/distance/Levenshtein.html)