Excision Score: Evaluating Edits with Surgical Precision

AI summary

Overview

• Research area: Machine learning evaluation metrics for document editing tasks, spanning both natural language processing (NLP) and AI-for-code (AI4Code).
• Technical level: Intermediate. The paper mixes formal definitions (three-way alignment, divergent regions, equivalence relations) with an empirical correlation study, but the core idea is stated in plain terms: strip out the shared text, then compare only the edits.
• Scope in one sentence: The paper formalizes the "revision similarity problem," proposes five adequacy criteria that such measures should satisfy, and introduces Excision Score (ES), a static measure that excises the longest common subsequence shared by an original document and two of its revisions before applying SARI to the divergent remainder.

What This Paper Is About

Many machine learning tasks — from code repair to text simplification — amount to editing an existing document rather than writing a new one, and evaluating those edits requires a similarity measure that agrees with human judgment. The authors show that popular metrics such as BLEU, ROUGE, METEOR, chrF, and normalized edit similarity fail here because their scores are dominated by the text the original and the revisions already share, so they hand out near-perfect scores even when an assistant edited the wrong location entirely. The paper's goal is to define what a good revision-similarity measure must do and to build one that ignores shared context and scores only the changes.

Key Contributions

1. A unifying problem formulation. The authors introduce the umbrella term "revision similarity" to cover every ML evaluation task expressible as three sequences: an original document, a golden reference revision, and a hypothesis revision to be scored.
2. Five adequacy criteria. They state five properties a revision-similarity measure should satisfy — rewarding agreement on edits, penalizing disagreement, invariance to shared context, origin-variance, and obliviousness to semantically equivalent syntactic variances — and demonstrate that popular pairwise measures fail them.
3. Excision Score (ES). They propose a static, task-agnostic, interpretable, lightweight measure that computes a longest common subsequence (LCS) across the three documents, excises it, and applies SARI to the remaining divergent regions — analogous to a surgeon creating a sterile field.
4. An execution-proxy evaluation. They correlate ES against binary test-pass outcomes on two code-editing datasets, in both unperturbed form and with artificially inflated shared context, and compare it against exact match, unnormalized Levenshtein distance (ED), NES, chrF, BLEU, CodeBLEU, DiffBLEU, and SARI.

Main Findings

• Shared context breaks pairwise measures. In the general case where an original is XY, a prediction is XW, and the reference is XZ with l = |Y| = |W| = |Z|, BLEU approaches 1 as |X| grows, even though the model replaced the wrong span. Normalized edit similarity, ROUGE, METEOR, and chrF fail in the same way.
• SARI also has a gap. SARI accounts for the origin but is not invariant to shared context: its F_keep term can exceed 1 - ε when shared context dominates, narrowing its effective range to [1/3 - ε, 1] and letting it award up to 1/3 on a "do-nothing" baseline where B = O ≠ A.
• SansLCS loses deletion information. Stripping the LCS and applying a pairwise measure is invariant to shared context, but it cannot reward agreement on deletions (it returns 0 in the paper's deletion-agreement example) and it manufactures n-grams at junctions that existed in neither revision.
• DiffBLEU mixes operation types. Concatenating deleted and inserted lines lets a word inserted by one revision match a word deleted by the other, and it over-rewards matching left-hand sides of replacements at the expense of mismatching right-hand sides.
• ES leads on HumanEvalFix. ES-Token reaches r = 0.643 (95% bootstrap CI [0.636, 0.651]), followed by ES-Line at r = 0.599 (CI [0.592, 0.607]) and SARI at r = 0.572 (CI [0.564, 0.58]). Both ES variants give statistically significant improvement over SARI.
• Headline improvements reported in the abstract. When aligned with test execution on HumanEvalFix, ES improves over SARI by 12% in Pearson correlation and by more than 21% over standard measures like BLEU; under the shared-context perturbation the margin over SARI rises to 20% and to more than 30% over standard measures.
• Perturbation reduces reference coverage. Prepending a shared random prefix of 2000–3000 characters drops reference-solution coverage from 21% to 7% in CanItEdit and from 5% to 0.5% in HumanEvalFix. The prefix is sampled uniformly from the characters abcdef, a whitespace, and a newline, with a different prefix per sample.
• ES handles corner cases other measures miss. It correctly aligns moved code blocks and appropriately rewards matching insertions or deletions, partially satisfying the semantic-variance criterion.
• Complexity is reduced by approximation. Exact LCS implies O(l³) time for l = |O|; the implementation computes LCS(LCS(O,A), LCS(O,B)) — three two-way LCS computations — bringing it down to O(l²).
• Execution-based evaluation is expensive. The paper cites reports that evaluation on some 300 samples of a SWE-Bench-like dataset took two days, and that this was later reduced to one hour per 500 dataset samples with powerful hardware and containerized environments.

Methodology in Plain English

The authors start by identifying that a revision touches only a small part of a document, so the original and its revisions mostly overlap. They formalize what "shared" and "changed" mean using a three-way alignment: a table with three rows (reference revision, hypothesis revision, original) where columns containing identical entries are "conserved" and the rest are "divergent." A "divergent region" is a maximal run of adjacent divergent columns.

With that vocabulary they state five properties a good measure should have, then audit existing metrics against them on constructed examples where human intuition is unambiguous. They find the main failure mode is that these metrics reward conserved columns.

Their fix, Excision Score, deletes a longest common subsequence across all three documents, then feeds the three remaining residuals to SARI, which has separate terms for added, kept, and deleted n-grams and therefore can credit agreement on deletions. N-grams spanning different divergent regions are discarded. Because exact three-way LCS is cubic, they approximate it with three two-way LCS computations.

For evaluation they use code-editing tasks where a cheap static proxy for test execution is valuable. They collect three LLM outputs per item across nine models — claude-sonnet-4, gemini-2.5-flash, gpt-4o-2024-11-20, gpt-4o-mini-2024-07-18, gpt-4.1-nano-2025-04-14, Qwen2.5-Coder Instruct 1B and 5B, and DeepSeek Coder Instruct 1.3B and 6.7B — running the open models through vLLM with default sampling and the proprietary models at temperature 0.2 and top_p 0.95. This yields 26,568 samples (3 × 9 × 984) from HumanEvalFix and 2,835 samples (3 × 9 × 105) from CanItEdit. They execute tests for each output and record binary pass or fail: 45% pass on HumanEvalFix and 40% on CanItEdit. They then compute Pearson correlation between the pass/fail indicator and each static measure, including two ES variants — ES-Line, which excises shared lines, and ES-Token, which uses tree-sitter to excise tokens common to all three strings. Comments that do not affect execution are removed before scoring. Finally, they repeat the correlation analysis after prepending the large random shared prefix.

Why This Matters

The paper argues that static measures remain indispensable because dynamic, execution-based measures are crippled by non-executable tasks (code summarization, commit message generation), nontestable code, incomplete codebases, under-approximation of program behavior, and prohibitive cost. If a static measure is going to stand in for test execution, it needs to correlate with execution — and the authors show the popular ones largely do not when revisions share most of their content.

Real-world applications:

• AI coding assistant evaluation. Teams shipping next-edit suggestion, automated program repair, refactoring, or code-commenting features need a cheap, interpretable score that reflects whether the assistant actually fixed the right place.
• Document and text revision. Grammatical error correction, text simplification, factual updating, and style transfer all fit the revision-similarity framing, and any of them can be scored with a symmetric measure that tolerates noisy references.
• Code review triage. A symmetric revision-similarity measure can cluster patches so that a maintainer of a large subsystem, such as a Linux kernel subsystem, reviews representative patches instead of every one.
• Annotation-light benchmarking. Because ES is task-agnostic and does not require golden references to be exhaustively enumerated, it offers a cheaper signal for tasks where building reference sets is expensive.

Industry relevance is direct: the work comes from JetBrains Research (with a co-author at University College London), the failure modes described are ones that AI coding-assistant vendors face when measuring edit quality, and the method is designed to be lightweight enough to run at scale rather than in containerized test harnesses.

Future Directions

• Concretizing the semantics-preserving equivalence relation. Property 5 depends on a relation ≡_L that is undecidable in general and must be under-approximated; the paper leaves open how to instantiate it for specific languages and tasks beyond matching misplaced insertions.
• Better LCS approximation. The current O(l²) implementation uses three two-way LCS computations rather than the true three-way LCS; whether tighter approximations improve correlation is untested here.
• Extending evidence beyond code. The reported numbers come from HumanEvalFix (and the paper describes CanItEdit perturbations), so behavior on NLP revision tasks such as GEC or text simplification is not established in the presented results.
• Reconciling static and dynamic views. The authors note that ES's under-approximation captures a different subspace of program behavior than execution-based measures, and formalize this variability in Section 3.2; how to combine the two signals remains an open question.

Target Audience

Researchers and practitioners working on LLM-based editing systems — particularly AI4Code and NLP evaluation — who need to choose or design a static similarity metric that tracks human and execution-based judgment. It is also relevant to benchmark authors who currently apply BLEU, ROUGE, or SARI to revision-style tasks, and to engineers building evaluation pipelines for coding assistants who want a lightweight proxy when running tests is infeasible. Some background in similarity metrics and edit distance helps, but the central argument is accessible without deep formal methods training.

Authors’ abstract

Many tasks revolve around editing a document, whether code or text. We formulate the revision similarity problem to unify a wide range of machine learning evaluation problems whose goal is to assess a revision to an existing document. We observe that revisions usually change only a small portion of an existing document, so the existing document and its immediate revisions share a majority of their content. We formulate five adequacy criteria for revision similarity measures, designed to align them with human judgement. We show that popular pairwise measures, like BLEU, fail to meet these criteria, because their scores are dominated by the shared content. They report high similarity between two revisions when humans would assess them as quite different. This is a fundamental flaw we address. We propose a novel static measure, Excision Score (ES), which computes longest common subsequence (LCS) to remove content shared by an existing document with the ground truth and predicted revisions, before comparing only the remaining divergent regions. This is analogous to a surgeon creating a sterile field to focus on the work area. We use approximation to speed the standard cubic LCS computation to quadratic. In code-editing evaluation, where static measures are often used as a cheap proxy for passing tests, we demonstrate that ES surpasses existing measures. When aligned with test execution on HumanEvalFix, ES improves over its nearest competitor, SARI, by 12% Pearson correlation and by >21% over standard measures like BLEU. The key criterion is invariance to shared context; when we perturb HumanEvalFix with increased shared context, ES' improvement over SARI increases to 20% and >30% over standard measures. ES also handles other corner cases that other measures do not, such as correctly aligning moved code blocks, and appropriately rewarding matching insertions or deletions.