Phrase-based and hierarchical translation systems are built in two steps. First, a word aligner decides which source word corresponds to which target word. Then a fixed rule of thumb reads translation rules off that alignment grid. The second step is brittle. One wrong link can block a large, valid phrase. The rule of thumb also produces tables with millions of redundant entries. Joint models address this by learning alignment and translation units in one probabilistic model, and they win on BLEU and on table size. They pay for it twice, though. They are restricted to the simplest grammar shape, binary straight-or-swapped bracketing. And because exact inference over sentence pairs costs $O(n^6)$, they quietly prune their search with the same external word alignments they set out to replace.
We propose to remove both restrictions with one mechanism. A modern neural aligner such as Cross-Align does not have to supply a hard alignment. It can instead supply link probabilities, and from these we can compute in closed form how likely each candidate phrase pair is to be extractable. That quantity defines a soft, sparse search space. Inside it, a Bayesian sampler learns full hierarchical rules with gaps, the "phrases with holes" used by Chiang's Hiero system, directly as units. The output is a compact Hiero grammar that a standard decoder can use. The central question is whether learning the rules jointly still beats careful rule-of-thumb extraction once the alignments come from a strong neural aligner rather than GIZA++. That question has not been asked.
Core Claim
The two limitations of joint models have a common cause. Both the restriction to binary bracketing grammars and the dependence on external alignments for pruning come from the need to cut down the $O(n^6)$ chart of candidate bilingual spans ("bispans"). Hard alignment links are a poor way to do this, because a single spurious link removes a correct bispan with certainty. That is exactly the fragility documented in Phrase Table Training for Precision and Recall.
We instead score each bispan $b$ by its consistency marginal. Treat the aligner's link probabilities $p_{ij}$ (source word $i$, target word $j$) as independent. Let $\mathrm{in}(b)$ be the cells inside the block and $\mathrm{cross}(b)$ the cells with exactly one end inside the span. The probability that $b$ satisfies the standard extraction consistency condition is then
$$c(b) = \prod_{(i,j)\in \mathrm{cross}(b)} (1-p_{ij}) \cdot \Big(1 - \prod_{(i,j)\in \mathrm{in}(b)} (1-p_{ij})\Big).$$
The first factor says no link leaves the block. The second says at least one link lies inside it.
Bispans with non-negligible $c(b)$ form the search space. A Pitman-Yor prior then decides which of these bispans, and which gapped combinations of them, become reusable rules. The Pitman-Yor prior is a "rich get richer" distribution that favors reusing a small set of rules.
Our claim has three parts. First, the induced grammar should beat Chiang-style extraction run on the same neural alignments while being several times smaller. Second, it should beat binary-bracketing joint models because it can express gapped rules. Third, soft pruning should beat hard-link pruning, especially on long sentences and on idioms.
Relation to Prior Work
Three prior lines supply the pieces. Chiang's hierarchical phrase-based model defines the rule format and decoder we target. It obtains gapped rules by subtracting smaller consistent phrase pairs from larger ones on fixed GIZA++ alignments. We keep the format but learn the rules rather than subtracting them.
Joint models fill the second role. Neubig et al. (see also; An Unsupervised Model for Joint Phrase Alignment and Extraction) learn phrase tables with a Pitman-Yor prior over a bracketing grammar, matching GIZA++ BLEU on Japanese-English (23.23 vs. 23.20) with a table of 723,000 rather than 4.22 million entries. Cohn and Haffari do the same with a recursive prior and Metropolis-Hastings sampling. Both are restricted to binary bracketing grammars, and Cohn and Haffari state that they needed 30-word caps plus word-alignment constraints to stay tractable. We reuse their prior and sampler design, but change the grammar and the pruning.
The third line induces full synchronous grammars. Blunsom et al.'s Gibbs sampler and Blunsom and Cohn's slice sampler induce synchronous grammars from unaligned bitext and beat heuristic pipelines on IWSLT. They were demonstrated only on about 40,000 sentence pairs, with mostly phrasal rules. We borrow slice sampling to adapt the chart threshold during sampling. Bayesian Synchronous Grammar Induction acts as a constraint: learned non-terminal categories gave essentially nothing (38.8 vs. 38.7 BLEU). We therefore keep Hiero's single category and put the modeling effort into rule shape.
Two discriminative methods are closest in spirit to the "make the aligner aware of extraction" goal. DeNero and Klein predict extraction sets directly, which needs hand-aligned data. Shen et al. add a coverage reward to alignment search. Both still end in heuristic extraction, and we treat both as baselines.
On the neural side, Cross-Align reaches 10.1 AER (alignment error rate) on Chinese-English. Its authors report broken multi-word alignments, which is the failure our phrase-level stage targets. Code is available as lisasiyu/Cross-Align.
Research Program
The system has three stages, and each can be evaluated on its own.
Stage 1: candidate bispans. We run Cross-Align in both directions and average the link probabilities. We then compute $c(b)$ for all bispans up to Hiero's span limit. This is cheap with two-dimensional prefix sums over $\log(1-p_{ij})$. The bispans above a loose threshold become the candidate set. This stage alone already defines a soft extraction set.
Stage 2: the generative grammar. Rules follow Chiang's constraints: at most two gaps and at most five source symbols. They are drawn from a Pitman-Yor process. Its base distribution generates the rule shape, with gap count and Poisson-distributed terminal lengths, and the terminal strings come from neural lexical translation probabilities.
Stage 3: inference. Sampling is blocked by sentence. Inside-outside runs only over candidate bispans, and slice variables let the sampler occasionally revisit pruned cells. This keeps $c(b)$ from becoming a hard constraint through the back door.
The final grammar is scored with the usual Hiero features, plus posterior rule counts averaged over several chains as Cohn and Haffari do. It is decoded with a standard Hiero decoder.
We will analyze four things. The first is how much of the $O(n^6)$ chart survives at each threshold, as a function of sentence length. The second is whether gapped rules are actually learned or collapse into phrases. The third is rule reuse. The fourth is behavior on non-compositional pairs, where token-level alignments are erratic.
Baselines
The naive reference point is the standard pipeline. GIZA++ alignments are symmetrized with grow-diag-final-and, and Hiero rules are extracted by Chiang's subtraction heuristic. The NIST anchor for this pipeline is Chiang's reported 0.2877 BLEU on MT03, against 0.2676 for the Pharaoh phrase-based system, in the Hiero paper. We rerun it on our data rather than copying that number.
The strongest competitor is the same Hiero pipeline run on symmetrized Cross-Align alignments. It is the most dangerous baseline because it isolates whether better alignments alone erase the gains that joint models showed over GIZA++. We found no reported result on Lacuna for Hiero extraction on Cross-Align or any other neural alignments, so we must establish this number ourselves. Beating it means a statistically significant BLEU gain on at least two language pairs, with a grammar at most half the size.
The binary-bracketing joint model of Neubig et al., which reports 23.23 Japanese-English BLEU, represents joint induction without gaps. We will feed its phrase pairs into Hiero subtraction so that the decoders match. Consistency-aware search from Shen et al., which reports roughly 1.0 BLEU over generative and discriminative aligners on Chinese-English, will be applied on top of Cross-Align.
Two ablations isolate the key ingredients. The first stops after Stage 1. It extracts Hiero rules weighted by $c(b)$, with no Bayesian induction, and so tests whether the prior adds anything beyond soft consistency. The second replaces soft pruning with hard-link pruning from the same Cross-Align alignments, which tests the circularity claim directly.
Fairness rules apply to all systems. They use identical training data, language model, decoder, and tuning procedure. Each is tuned three times so that we can report variance. Training compute will be logged, and the Stage-1 ablation will also be given the equivalent compute through extra tuning runs.
Why not just…?
Why not just run Hiero extraction on Cross-Align alignments? This is the main threat. The historical gains of joint models were measured against GIZA++, which has 19.4 AER on Chinese-English versus Cross-Align's 10.1, so much of that advantage may have been alignment noise. Two things still count against the hard-link pipeline. Even very good alignments leave single wrong links that block large rules, which is the fragility documented by Deng. And subtraction still produces bloated tables, which the joint model avoids. The comparison against this baseline settles the question. If it ties us on BLEU, our remaining contribution reduces to grammar size, and we will report that plainly.
Why not just extract rules weighted by soft consistency, with no grammar induction? This baseline answers the brittleness problem cheaply, and it is exactly our Stage-1 ablation. What it cannot do is prefer one decomposition of a sentence pair over another. It counts every consistent sub-span, so bloat and spurious ambiguity remain. The FLAT-versus-HIER result in Neubig et al. suggests that modeling recursive reuse matters. If the ablation matches the full system, the honest conclusion is that the Bayesian prior is unnecessary in the neural-alignment era.
Why not just add a coverage reward to the aligner, as in consistency-aware search? Shen et al. show that this works, giving about 1.0 BLEU. However, it still commits to a single hard alignment and a heuristic extraction step, and its authors note that it is weaker for syntax-sensitive rule systems. We run it on Cross-Align alignments, so any remaining gap is attributable to joint induction rather than to the aligner.
Proposed Experiments
Development and comparison with the sampling literature use IWSLT Chinese-English. The reported points of reference there are 51.8 BLEU for the Gibbs-sampled grammar against 48.3 for the heuristic pipeline (Blunsom et al.), and 50.4 for the slice sampler against 47.3 for Moses (Blunsom and Cohn).
Scale is tested on NIST Chinese-English with FBIS training data, tuning on MT02 and testing on MT03 through MT05. Here we train on full-length sentences with no 30-word cap. We report BLEU by source-length bucket alongside training wall-clock time and the fraction of the chart that survives pruning.
Generality across reordering types is tested on Japanese-English, the hardest pair for Cross-Align at 35.4 AER, where the reported Neubig et al. table-size result also applies. Lower-resource behavior is tested on Urdu-English, where the reported point of reference is 16.97 BLEU for Cohn and Haffari against 15.65 for pialign.
Extraction quality is measured independently of the decoder. We use bispan $F_5$ on hand-aligned NIST MT02, where DeNero and Klein report 74.0 against 46.0 for GIZA++. We also use AER on the HIT Chinese-English treebank, where SCCM reports 0.255 (Duan et al.).
Four checks decide the outcome. The first is the comparison with Hiero on Cross-Align alignments, judged by BLEU and grammar size. The second is soft versus hard pruning on sentences longer than 30 words. If soft pruning shows no advantage there, the circularity argument fails. The third is the Stage-1 ablation, which shows whether the Bayesian prior is needed at all. The fourth is a manual audit of 200 learned gapped rules for reuse and correctness, compared with subtraction-derived rules covering the same spans.
References
- Phrase Table Training for Precision and Recall: What Makes a Good Phrase and a Good Phrase Pair?
- A Hierarchical Phrase-Based Model for Statistical Machine Translation
- Joint Phrase Alignment and Extraction for Statistical Machine Translation
- An Unsupervised Model for Joint Phrase Alignment and Extraction
- An Infinite Hierarchical Bayesian Model of Phrasal Translation
- A Gibbs Sampler for Phrasal Synchronous Grammar Induction
- Inducing Synchronous Grammars with Slice Sampling
- Bayesian Synchronous Grammar Induction
- Discriminative Modeling of Extraction Sets for Machine Translation
- Consistency-Aware Search for Word Alignment
- Cross-Align: Modeling Deep Cross-lingual Interactions for Word Alignment
- Synchronous Constituent Context Model for Inducing Bilingual Synchronous Structures