Many practical text-comparison tasks do not ask "how similar are these two passages?" They ask "exactly where do they differ?" A provincial building code copies a national clause but changes "10 mm" to "12 mm". A caption says "a red car" when the reference says "a blue car". A headline drops a "not". Dense sentence embeddings rate these pairs as nearly identical. Plain string diffs flag every harmless rewording. We propose a simple two-role design. First, decide which words correspond using meaning: exact lexical matches serve as fixed anchors, and a globally optimal one-to-one assignment over contextual embeddings pairs up the remaining words. Second, check each matched pair using surface form, and only for word classes where the exact form carries the fact: numbers, units, names, negation, quantifiers, and modal verbs. A matched pair that agrees in meaning but disagrees in form is a localized difference. An unmatched word in one of those classes is an inserted or deleted fact.
Here "optimal bipartite alignment" means pairing words of text A with words of text B so that each word is used at most once and the total similarity of the pairs is as large as possible. The Hungarian algorithm solves this exactly. "Hybrid lexical-semantic similarity" is the family of methods that combine surface overlap with embedding similarity. The claim is that these two signals should play different roles, correspondence versus verification, rather than being averaged into one score. We also claim that the global, one-to-one nature of the assignment is what makes the verification step reliable when repeated or competing tokens are present.
Core Claim and How It Differs From Prior Work
The obvious idea at this intersection is to build a mixed edge-weight matrix, embedding cosine plus a lexical-overlap bonus, and run the Hungarian algorithm on it. That idea is not new. Sultan et al.'s two-stage aligner already scores word pairs with embeddings, a paraphrase dictionary, and context features before global matching, and reaches 92.1% F1 on the MSR alignment corpus. The UBC interpretable-STS system runs Hungarian-Munkres chunk alignment over a matrix built from GloVe vectors and lemma overlap. The file's claim that no one fuses lexical and dense evidence at the edge level is therefore too strong, and we do not build on it.
What these systems share is that fusion is used to decide what aligns. They then either score similarity or classify relations with a separate model; UBC uses an SVM over 21 features. Our observation is that fusion actively hurts difference localization. A lexical bonus pulls "10 mm" toward another "10 mm" elsewhere in the text, and away from the "12 mm" that sits in its structural role. The fused score also collapses "harmless paraphrase with low overlap" and "changed fact" into the same low number.
We keep the channels apart. Dense contextual similarity, with exact matches as hard anchors, decides the correspondence. A gated lexical check then decides whether a corresponding pair states the same fact.
This builds on SimAlign, which showed that the Hungarian "Match" step over middle-layer mBERT similarities gives strong alignments without parallel data. SimAlign stops at alignment and has no lexical channel.
It also borrows the anchoring idea from Local-Similarity Scoring. That method restricts contextual comparison to exactly shared tokens and picks matches greedily. We use shared tokens as anchors but hand the non-shared residue to a global assignment.
Three papers define the target failures:
- ALOHa matches LLM-extracted objects by S-BERT cosine with the Hungarian algorithm, which leaves it blind to attribute binding.
- SentSim fixes negation blindness in token metrics only by adding a global sentence score, so the local alignment still cannot see "not".
- Chikati et al. align regulatory sentences with sparse bipartite matching but cannot localize intra-sentence variations. They also report that contrastive fine-tuning of the embedding model made things worse.
That last result constrains the design: we avoid training the embedding model and keep learning to a small gate.
Research Program
Let $A$ and $B$ be the tokenized texts. Words with identical normalized form and mutually highest contextual similarity are fixed as anchor pairs. Let $R_A$ and $R_B$ be the unanchored residue, and let $s_{ij}$ be the cosine similarity of middle-layer contextual embeddings for $i \in R_A$, $j \in R_B$. We solve
$$ M^* = \arg\max_{M} \sum_{(i,j) \in M} s_{ij} \quad \text{s.t. } M \text{ is one-to-one and } s_{ij} \ge \tau \text{ for all } (i,j)\in M, $$
where $\tau$ is a threshold, tuned on development data, below which a word is left unmatched. The discrepancy of the pair is
$$ D(A,B) = \sum_{(i,j)\in M^*} g(i)\,\big[f(i) \ne f(j)\big] \;+\; \sum_{k \in U} g(k), $$
where:
- $f(\cdot)$ is a normalized surface form (the digit string with its unit, the entity string, negation polarity, or the quantifier or modal lemma);
- $g(\cdot) \in [0,1]$ is a gate giving how much the exact form of a word matters;
- $U$ is the set of unmatched residue words.
Each nonzero term is a localized difference that can be reported to a user. Anchoring also shrinks the matrix the cubic-time solver sees, which partly addresses the cost limit of the Hungarian algorithm on long passages.
We build three versions of the gate $g$:
- Rule-based: 1 for numerals, units, proper nouns, negation cues, quantifiers, and modals; 0 otherwise.
- Learned: a logistic model on part-of-speech, entity type, and IDF, trained on iSTS alignments labeled OPPO or with low scores.
- Ungated: $g \equiv 1$, as an ablation.
For multi-word units we align chunks rather than words where gold chunks exist, as in iSTS. Everywhere else we stay at the word level and accept the one-to-one restriction as a known limitation. We also report how often gold alignments in the evaluation sets are many-to-one, so readers can judge how much that limitation costs.
Baselines
Naive reference. The do-nothing reference is surface diffing. On iSTS this is the official naive baseline, whose Type+Score F1 on Images is 0.4326 (Agirre et al.). On hallucination it is exact-match CHAIR, which reaches localization accuracy 6.70 on HAT (ALOHa). We also run a word-level monotonic diff, Needleman-Wunsch, on every dataset. Within a sentence, reordering is rarer than across sections, so this is a stronger naive reference than it first appears.
Strongest existing interpretable-STS systems. On iSTS these are the UBC Hungarian-plus-SVM system, with Type+Score F1 0.6934 on Images (Agirre et al.), and the FULL pipeline, with alignment F1 0.77 and Type+Score F1 0.53 on Headlines (Lopez-Gazpio et al.). No reported result was found on Lacuna for the neural iUBC system on Answer-Students, so we rerun it where code allows. For these systems we report their published numbers and use the same gold-chunk and system-chunk splits. Beating them means higher Type+Score F1 in the same chunk condition, with the gain concentrated in the OPPO and low-score types.
Strongest existing hallucination system. On HAT this is ALOHa, at localization accuracy 20.30. We keep its LLM object extraction unchanged and replace only the matching and verification step, so any gain is attributable to our change.
Dense-only matching with a threshold. This is SimAlign Match with the same encoder, layer, and threshold search. It isolates the lexical verification channel.
Fused matrix. Hungarian matching over $\alpha s_{ij} + (1-\alpha)\ell_{ij}$, where $\ell_{ij}$ is character n-gram overlap, with the fused score thresholded to flag differences. This is the most direct competitor to our "separate roles" claim. It gets an equal grid-search budget over $\alpha$ and the threshold on the same development split.
Ablations.
- Greedy argmax in place of the Hungarian step, as in MaxSim-style late interaction. This tests whether global competition matters.
- No anchors. This tests the anchoring step.
- Ungated verification ($g \equiv 1$). This tests whether verification must be restricted to form-critical word classes.
All systems use the same frozen encoder, the same tokenization, and one shared development split for every threshold.
Why not just…?
Why not just add a lexical bonus to the similarity matrix and run Hungarian once? This is the fused-matrix baseline, and it is a real threat on pure alignment F1. It may match or beat our method on the MSR corpus, where Sultan et al.'s feature-fused aligner already reaches 92.1%. Our claim is narrower: fusion is worse at localizing differences. We will show this with a controlled test set in which a changed number or entity also appears unchanged elsewhere in the passage. If the fused matrix matches our method on difference-localization F1 there, we will conclude that role separation is unnecessary and report that.
Why not just ask an LLM or an NLI cross-encoder to list the differences? Both are strong. ALOHa itself relies on an LLM for extraction, and a cross-encoder sees both texts jointly. We will run both zero-shot, with the same inputs, on the iSTS and controlled sets. They have two known costs. They are non-deterministic and expensive, a cost ALOHa acknowledges. And a sentence-level contradiction label does not say which span changed. If a prompted LLM matches our span-level F1, the remaining case for our method is cost, determinism, and inspectability. We would state that plainly rather than claim an accuracy win.
Why not just use greedy matching followed by a string diff on matched pairs? Greedy is cheaper. Sultan et al. attribute part of their recall to modeling global competition, and Iida and Okazaki needed pooling to stabilize greedy MaxSim on long documents. The greedy ablation measures the gap directly. We expect it to appear mainly on inputs with repeated tokens, and we will report the gap separately for inputs with and without repeats.
Why not just a monotonic word diff? Within a single sentence this may be competitive. Chikati et al.'s catastrophic Vecalign result (test AER 0.4568 versus 0.1339 for bipartite matching) concerns reordered sentences, not words within a sentence. We therefore report results stratified by the amount of reordering in each pair, measured as the fraction of crossing gold alignment edges. We expect our method's advantage over the diff to grow with reordering, and the stratified results will show whether it does.
Proposed Experiments
iSTS (SemEval 2015 and 2016, Headlines, Images, Answer-Students). Relation types are assigned by rule from the output: an anchor pair or a verified match is EQUI, a gated form mismatch is OPPO or low-score SIMI, and an unmatched word is NOALI. A light classifier over the same outputs covers SPE and REL. Metrics are the official alignment F1 and Type+Score F1.
HAT and nocaps-FOIL. Object phrases with their modifiers are verified by the gate, targeting attribute-binding errors. The metric is localization accuracy against ALOHa's 20.30.
Canadian building codes. We keep Chikati et al.'s sentence alignment (GIST plus LAPJVsp, test AER 0.1339) and annotate a few hundred aligned sentence pairs for intra-sentence variations. This is new annotation, because no reported result was found on Lacuna for intra-sentence variation detection. The metric is span-level precision and recall.
Controlled contrast set. We derive a contrast set from STS pairs by editing numbers, entities, negations, and modals, with and without distractor repeats of the edited token. This set is the decisive test of fused versus separate roles and of greedy versus global matching.
Sanity check. MSR alignment F1 confirms that anchoring does not hurt plain alignment quality.
The proposal succeeds if three things hold. The separate-roles method must beat the fused matrix on span-level difference F1 on the contrast set and the building-code annotations. The greedy ablation must lose specifically on inputs with repeated tokens. And the method must exceed the reported iSTS OPPO-heavy Type+Score F1 and ALOHa's localization accuracy with a frozen encoder. If any of these fails, that result is informative in its own right, and we will report it rather than tune it away.
References
- Feature-Rich Two-Stage Logistic Regression for Monolingual Alignment
- UBC: Cubes for English Semantic Textual Similarity and Supervised Approaches for Interpretable STS
- SimAlign: High Quality Word Alignments without Parallel Training Data using Static and Contextualized Embeddings
- Incorporating Semantic Textual Similarity and Lexical Matching for Information Retrieval
- ALOHa: A New Measure for Hallucination in Captioning Models
- SentSim: Crosslingual Semantic Evaluation of Machine Translation
- Challenges in Technical Regulatory Text Variation Detection
- Interpretable semantic textual similarity: Finding and explaining differences between sentences
- iUBC at SemEval-2016 Task 2: RNNs and LSTMs for interpretable STS