Aligning two sentences means deciding which words and multi-word phrases in one correspond to which in the other. It underlies paraphrase detection, textual entailment, and the phrase tables of classical translation systems. The best such aligners use dependency trees, which are parser-produced graphs linking each word to the word it modifies. They use these trees to rule out implausible matches, such as a stray "the" pairing with a distant noun. They also use exact integer linear programming (ILP) solvers to find the single best alignment. Both choices have costs. The tree is fixed before alignment starts, so any parser error becomes a hard error in the alignment. And exact solvers limit how long a sentence can be and how many times the decoder can run inside training.
We propose a two-phase decoder. It first builds a cheap global alignment from word similarity alone. It then repairs that alignment with local moves: shifting a phrase boundary, merging or splitting phrases, swapping the partners of two aligned phrases, and re-attaching a word to a different head in the dependency tree. The repair is guided by one objective that adds three terms: alignment evidence, a soft penalty for each dependency-cohesion violation, and the parser's own score for the current tree. The central claim is that alignment and parse can correct each other in this way. Starting from a structured initialization, the search should match the exact solver's alignment quality on short sentences, run in near-linear time on long ones, and recover alignments that a fixed 1-best parse makes impossible.
Where the gap is
Three bodies of work meet here.
Joint phrasal aligners segment and align phrases at the same time.
- Thadani and McKeown (2011) replaced MANLI's simulated annealing with an exact ILP that includes hard modifier and lineage constraints. Decoding dropped from roughly 62 to 2.5 seconds per pair.
- Thadani, Martin, and White (2012) added aligned dependency arcs to the ILP objective.
Both works take a single 1-best parse as given, and both handle structure through a solver rather than through search. They motivate this proposal and supply its strongest baselines.
DeNero and Klein (2008) constrains the design in two ways:
- They proved exact phrase alignment NP-hard.
- They found that greedy hill-climbing loses badly to ILP.
That hill-climbing, however, started unguided. Our design is shaped by that negative result.
The refinement literature explains why initialization matters. In network community detection, Scarlett et al. show that neighborhood refinement drives error to zero once the initial error falls below a threshold. Chin et al. warn that refinement reinforces early mistakes when it re-scores the same evidence the initialization used. Two further works show the same pattern elsewhere:
- In protein-interaction network alignment, PISwap starts from a Hungarian bipartite matching and applies 2-Opt swaps, which exchange the partners of two matched pairs. Conserved edges on Fly–Yeast rose from 272 to 398.
- In dependency parsing, Levi et al. (2016) repair an undirected spanning tree with greedy head swaps. They come within 0.97% attachment accuracy of full directed MST parsing.
We borrow the method of these works (global initialization plus local repair) and apply it to text alignment. We also move parse repair inside the alignment loop.
The dependency-constraint literature explains why constraints must be soft and why the parse must be revisable.
- The cohesion constraint of Lin and Cherry (2003) says that phrases disjoint in the source tree must map to non-overlapping target spans. It cut Hansard alignment error rate from 13.6% to 8.7%. The same paper notes widespread structural divergence between translations.
- Cherry and Lin (2006) show that dependency-restricted search spaces lose oracle recall, falling from 96.3% to 94.8%.
- Arase and Tsujii (2017) and Arase and Tsujii (2023) avoid 1-best parse errors by aligning packed parse forests with dynamic programming. Replacing the forest with a 1-best tree cost more than 3.5 recall points.
Their forests are constituency or HPSG structures, searched by CKY dynamic programming. We instead revise a dependency tree inside the search, so parse ambiguity is explored where the alignment needs it rather than enumerated up front.
Core Claim
A phrase alignment can be decoded jointly with its dependency trees by bounded local search. The search must meet two conditions:
- It starts from a structure-free global matching.
- Cohesion enters the objective only as a soft penalty evaluated against a revisable tree.
Under these conditions it reaches ILP-level accuracy with far better scaling. The split in evidence is deliberate and mirrors the sample-splitting remedy of Chin et al.: lexical evidence builds the starting point, and syntactic evidence drives the repair, so the repair does not merely re-confirm the start.
Research Program
The search state has three parts: a phrase alignment $A$, a source dependency tree $T_s$, and a target dependency tree $T_t$. The decoder climbs the objective
$$ S(A, T_s, T_t) = \sum_{(p,q)\in A} w^\top \phi(p,q) \;-\; \lambda\, V(A; T_s, T_t) \;+\; \mu \big[\log P(T_s) + \log P(T_t)\big] $$
The symbols are as follows:
- $\phi(p,q)$ is the feature vector of an aligned phrase pair.
- $w$ holds the learned weights.
- $V$ counts cohesion violations in the sense of Lin and Cherry (2003): head–modifier and modifier–modifier overlaps, together with the modifier and lineage conditions of Thadani and McKeown (2011), each counted as a violation rather than forbidden.
- $P(T)$ is the parser's score for a tree.
- $\lambda$ and $\mu$ trade off the three terms.
Initialization. Phase one runs Hungarian matching on lexical and embedding similarity, grouping contiguous matched tokens into phrases. The trees start as the parser's 1-best output.
Local moves. Phase two applies the best-improving move from five families until no move improves the score:
- shifting a phrase boundary by one token;
- merging adjacent phrases or splitting a phrase;
- a 2-Opt swap of the partners of two aligned phrases;
- deleting or adding a link;
- re-attaching one word to a new head, restricted to the parser's top-$k$ candidate heads.
The head re-attachment move is the new ingredient. It lets strong alignment evidence overturn a parser attachment when the parser was nearly indifferent between heads, instead of paying a cohesion penalty forever. Each move changes only a constant number of phrases and arcs, so its score change can be computed incrementally. For bounded phrase length and top-$k$ heads, one pass over all moves costs time roughly linear in sentence length times $k$.
Training. The weights $w$ are learned with a structured perceptron, as in Thadani, Martin, and White (2012), with our decoder inside the training loop.
Analysis. We measure how often the search reaches the ILP optimum, and how recovery depends on initial error. To do the latter, we corrupt the initial matching at controlled rates and trace whether the refined error collapses below some threshold, as the community-detection results predict.
Baselines
The naive reference point is the Hungarian initialization with no refinement. The file has no reported number for this exact initializer. The Meteor aligner's 62.57% F1 on the Edinburgh corpus, reported by Thadani, Martin, and White (2012), is the closest published weak reference. We will report both.
Strongest existing method. This is the joint phrasal-and-dependency ILP of Thadani, Martin, and White (2012), which reports 80.92% F1 on Sure+Possible alignments on the Edinburgh paraphrase corpus. It is the strongest competitor because it optimizes nearly the same features exactly. We will reimplement it with identical features, identical parser output, identical perceptron epochs, and the same held-out tuning of hyperparameters. Beating it means matching or exceeding 80.92% F1 while decoding faster. It also means a clear recall gain on pairs whose 1-best parse contradicts the gold alignment.
McKeown corpus. On the McKeown corpus, MANLI-Exact (Thadani and McKeown, 2011) reports 89.5% test precision, 33.0% exact matches, and under 2.5 seconds per pair. We compare at equal or lower precision cost with equal wall-clock budgets.
Hansard word alignment. For word alignment on the Canadian Hansard set, the cohesion-constrained model of Cherry and Lin (2003) reports 8.7 alignment error rate (AER). We run our decoder with phrases restricted to single words, using the same Minipar parses and the same 50,000 training pairs.
Ablations. Three ablations isolate the key ingredients:
- The first removes head re-attachment, which freezes the parse and leaves soft cohesion only.
- The second makes cohesion hard, which recovers ILP-style constraints inside the same search.
- The third starts the identical moves from a random or empty alignment. This reproduces the unguided hill-climbing that DeNero and Klein (2008) found wanting.
Why not just…?
Why not just put soft cohesion penalties into the ILP? Slack variables make this straightforward, and on short sentences such an ILP will find a better objective value than local search. This is a real threat to the speed-only argument, and it is why the proposal centers on joint parse revision. That revision is awkward in an ILP: tree well-formedness over top-$k$ heads, crossed with phrase segmentation, multiplies the variables. We will build the soft-penalty ILP with a frozen 1-best tree as a baseline. If it matches our full system in accuracy at comparable cost, the head re-attachment move is not earning its place. In that case we would report local search purely as a scaling result.
Why not just use k-best parses or parse forests? Arase and Tsujii (2017) show that forests recover recall lost to 1-best errors. A simple dependency analogue is to run the ILP on each of $k$ parses and keep the highest-scoring result, and this may work well. We will run exactly this with the same $k$ as our head candidates. Our expected advantage is that local re-attachment can combine corrections from different parses, where k-best reranking must take one whole tree. We will measure this by counting final trees that appear in no single k-best list. We will also check whether their pairs account for the accuracy gap.
Why not just use simulated annealing, as MANLI did? Thadani and McKeown (2011) report that annealing took about 62 seconds per pair and was replaced by an exact solver. The random-initialization ablation tests whether our gains come from the move set or from the structured start. We predict the start matters most, following the threshold results of Scarlett et al..
Proposed Experiments
Datasets and metrics. Monolingual phrase alignment is evaluated on three datasets:
- the Edinburgh paraphrase corpus, scored by Sure+Possible F1;
- the McKeown corpus, scored by precision, exact-match rate, and seconds per pair;
- SPADE and the NIST paraphrase set, scored with their alignment precision, recall, and F-measure against the forest aligners of Arase and Tsujii (2023).
SPADE ships gold constituency trees. We convert them to dependencies so we can measure directly whether head re-attachment moves the parse toward gold, which is the parse-repair claim. Bilingual word alignment is evaluated by AER on the 500 Hansard test pairs.
Optimality and scaling. For search quality, we compute the ILP optimum on Europarl Spanish–English sentences of up to 25 words, the setting where DeNero and Klein (2008) report reaching the exact optimum in 93.4% of cases. We report how often, and by how much, local search falls short of that optimum. We then extend to sentences above 25 words, giving the ILP a fixed time limit, and plot objective value and runtime against sentence length.
Decisive checks. Four results would settle the claims:
- Edinburgh F1 at or above 80.92% with at least an order-of-magnitude decoding speedup.
- A recall gain concentrated on pairs where the 1-best parse violates the gold alignment. This gain should come from the full system and be missing from both the frozen-tree ablation and the k-best ILP.
- A sharp recovery threshold in the corrupted-initialization curve.
- Search reaching the ILP optimum on a large majority of short sentences.
If the soft-cohesion ILP with a frozen tree matches the full system, the parse-repair hypothesis fails. The remaining result would be the narrower claim that guided local search is a fast approximate decoder.
References
- Optimal and Syntactically-Informed Decoding for Monolingual Phrase-Based Alignment
- A Joint Phrasal and Dependency Model for Paraphrase Alignment
- The Complexity of Phrase Alignment Problems
- Partial Recovery Bounds for the Sparse Stochastic Block Model
- Stochastic Block Model and Community Detection in Sparse Graphs: A spectral algorithm with optimal rate of recovery
- Local Optimization for Global Alignment of Protein Interaction Networks
- Edge-Linear First-Order Dependency Parsing with Undirected Minimum Spanning Tree Inference
- Word Alignment with Cohesion Constraint
- A Comparison of Syntactically Motivated Word Alignment Spaces
- Monolingual Phrase Alignment on Parse Forests
- Monolingual Phrase Alignment as Parse Forest Mapping
- A Probability Model to Improve Word Alignment