Long-document edit comparison: source backend deferred

Edition 9 October 2026 v2. Defer a product based on the literal new approximation algorithm. The selected source contains an explicit activation barrier far beyond practical document sizes. A separate conventional integration is possible, but no novel performance or buyer advantage has been established.

Research finding

Family 121 claims one uniform randomized algorithm for unit insertion, deletion and substitution costs on explicitly stored integer strings. For each fixed rational accuracy 0 < epsilon < 1, its distance estimate lies between the exact distance and (1+epsilon) times that distance with probability at least 2/3. Equal strings return zero on every execution. Expected work is N^(1+o(1)) for fixed accuracy as total length N tends to infinity, with polynomially bounded integer symbols.

The claim is a distance estimate, not an edit script, semantic duplicate classifier, common embedding or retrieval index. Runtime is an expectation over internal randomness, not a latency limit. Constants and thresholds depend on fixed epsilon; the paper disclaims a joint efficient inverse-accuracy bound. On bad random executions even the lower inequality need not hold, as section 8.3 explicitly states. Therefore the estimate is not an unconditional upper bound, and neither kind of threshold mistake can be ruled out just by that guarantee.

The approach combines adaptive coarse estimates, predicted alignment bands, cost-weighted comparison geometry, finite entropy-regularized optimization, shared samples and lazy evaluation. These are research directions for a future practically justified variant. Their full implementation and proof were not reconstructed here. Family 099's earlier embedding assessment remains relevant but received no new manuscript review in this edition.

Problem and buyer

Archive and document-platform engineers may need to compare long candidate pairs after retrieval, measure literal change, or reconstruct edits. Their inputs, normalization rules and required output determine the computation. Literal edit distance alone does not decide whether a revised contract or duplicated article means the same thing.

This is a plausible engineering job, not a demonstrated buying opportunity. No customer corpus, workload measurements, interviews, purchase commitments or integration requests exist. A generic comparison API faces mature open-source alternatives.

What the finding could enable

If independently accepted and made practical through new parameter work, the result could support high-accuracy distance estimation on long supplied pairs. It does not currently justify a fast production backend. Reducing the source's constants without a new correctness and runtime argument would create a heuristic, not an implementation inheriting the claimed guarantee.

An ordinary integration can already preserve exact input bytes, declare symbol units and normalization, run exact threshold queries, and request alignments only when needed. Useful workflow packaging would have to beat existing integration effort on a real recurring task. This review does not rename that incumbent functionality as a new mathematical invention.

Technical and commercial limits

Let h = ceil(log2(ceil(log2(N+2)))), H = 2^h, and ell = 2^ceil(log2(max(1,h))). The paper's large-input branch requires ell >= 2^1000 and ell * epsilon >= 10, with exact dynamic-programming fallback below the guards and for incomplete accuracy input. The paper also gives direct handling of equality, empty strings and very short source strings.

From those integer definitions, the least N satisfying the first guard alone is 2^(2^(2^999)) - 1. This symbolic boundary is a derivation from the selected definitions, not an observed runtime. The comparison script verifies adjacent boundaries for toy exponents 1 through 4 and never constructs the actual tower. At N=10^12, H=64 and ell=8; even N=10^100 has ell=16. Both fail the first guard.

The Lean physicalLargeInput additionally requires successful accuracy inspection and a local-mass bit-width bound. Its accuracyCutoff of 2^(2^max(2^1000,ceil(10/epsilon))) is sufficient for the two numeric guards, not a complete physical eligibility certificate. Failing the ell guard is enough to exclude its large branch; passing that guard alone is not enough to accept it. integerBinaryAnswerRawBand selects an exact suffix answer on the failed physical guard. No Lean program or kernel was run, and no source fallback performance was measured.

The eventual formal storage upper bound (N+2)^(C+65564) is a very loose bound, not an allocation instruction or memory lower bound. None of these asymptotic statements provides a realistic crossover. Using a padded formal length bound cannot make the total computation cheap.

Minimal architecture

For a conventional integration: immutable input snapshot and stable IDs; explicit byte/codepoint/token unit; declared normalization; candidate retrieval with its own recall assessment; exact equality and length filters; exact thresholded Levenshtein query; optional full distance or edit script; and a report retaining versions, settings and unresolved semantic questions.

A cutoff response must be represented as a predicate result. With threshold K, RapidFuzz returns K+1 when the true distance exceeds K; that sentinel is not the exact distance. Record distance > K, not a fabricated numeric measurement. An approximate backend would need a separate status and error policy and has not been implemented.

Existing alternatives and differentiation

RapidFuzz's primary Levenshtein documentation, reviewed 9 October 2026, already provides unit-cost exact distance, cutoff queries and edit operations. The 3.14.6 package was installed into a fresh isolated Python 3.12 environment; the wheel URL/hash and runtime identity are preserved. Existing environments were not altered.

The new finite controls compare all 961 pairs of binary strings of length at most four with an independent dynamic program, including four cutoff values and applying each edit script. Twelve longer generated cases have independently known distances. For a generated shifted periodic pair of 65,536 symbols each, unrestricted distance took a median about 101 ms over three calls; the cutoff-16 query took about 0.13 ms and returned exact distance two. For all substitutions at that length, cutoff returned the predicate sentinel 17. These are local diagnostics, not a representative benchmark or speed comparison with the unimplemented source algorithm.

Monetization hypothesis

The earlier AUD 2,000-8,000 integration price remains an unvalidated placeholder. The present review weakens the case for charging for a novel distance engine: the source branch does not activate at usable lengths, while conventional routines already solve the elementary API job. A fee would need to reflect a specific supported document workflow, recurring maintenance or measurable engineering time saved. No revenue or margin is forecast.

Validation experiment

2,023 controls passed: 961 exact/cutoff/script pair controls; 1,025 integer-log oracle controls; 12 toy guard-boundary controls; seven representative-length guard controls; six representation/sentinel controls; and 12 generated long-pair controls. Finite agreement does not prove library correctness or accept the source theorem. Exact synthetic inputs, hashes and report.

Representation controls show that precomposed versus decomposed accented text has raw codepoint distance two but NFC-normalized distance zero; UTF-8 byte distances differ again. Case is preserved unless a processor is explicitly supplied. These distinctions must be resolved before collecting customer accuracy or cost measurements.

Only revisit commercialization with an authorized real corpus and a concrete bottleneck. Measure complete ingestion, candidate generation, threshold classification, alignment requirements and review time against the current system. Do not use these synthetic cases to infer semantic accuracy, archive recall or customer savings.

Conditions to reject or defer

Defer the literal approximation backend because its necessary activation guard is already impractical. Reconsider only after a new implementation with justified practical parameters and independent acceptance exists. Reject a standalone integration if existing exact tools meet the workflow cheaply, if candidate retrieval or rendering dominates cost, or if customers primarily need semantic comparison. A full alignment requirement needs separate algorithm and cost evidence.

Next concrete action

Keep the source on the research watchlist and retain the exact-library recipe as a baseline. Prioritize the facility-planning Optimization Assurance Workbench as the first product experiment. It has a concrete checkable deliverable, while demand and delivery economics still require validation.

Source and reading record

Pinned revision fd4aeeb2ee4fc729c18d98444fed42fd0529eeeb. Selected paper pages 1-8, 34 and 43, plus the concluding paragraph on page 44, were read. Pages 7, 8 and 34 were visually checked. Extraction of all 46 pages is not full reading. Manuscript.

The scope note, Comparator configuration, selected Comparator definitions/final theorem, selected Definitions guards/output, complete AccuracyCutoff and 32-line RawBandMain entry were inspected. The large Comparator and Definitions files were not read completely. Seven source hashes are recorded in the comparison record. Challenge sorry remains an interface placeholder, not a reported solution failure. Full imported proof, kernel acceptance and source-program execution remain incomplete.