Complexity of Finding the BLEU-optimal Hypothesis in a Confusion Network

Gregor Leusch, Evgeny Matusov, Hermann NeyEMNLP 2008

Abstract

This study explores the computational challenges of identifying the optimal translation hypothesis within a confusion network according to the BLEU metric. We demonstrate that finding the BLEU-optimal path is NP-hard for $n$-gram lengths greater than one. Conversely, we show that the unigram case can be solved in polynomial time using bipartite matching. For practical use, we introduce a multi-stack decoder that provides high-quality approximations.

Introduction

In Machine Translation (MT), systems often produce a "confusion network" (CN)—a compact directed acyclic graph representing a vast space of potential sentence hypotheses. Selecting the "best" translation from this network typically involves maximizing an evaluation metric like BLEU (Bilingual Evaluation Understudy).

Example of a confusion network $\mathcal{C}$ and a set of reference translations $R$.

While finding a path that minimizes Word Error Rate (WER) is computationally efficient (linear time), BLEU presents a significant challenge. Because BLEU accounts for $n$-gram overlaps (sequences of 1 to 4 words), a word choice at one position influences the validity of matches elsewhere in the sentence. This paper investigates whether an efficient global optimization algorithm exists for BLEU search.

Theoretical Complexity

The authors establish the formal complexity of this search problem through two primary findings:

1. The NP-Hardness of $n$-gram BLEU ($n \ge 2$)

The core of the paper is a proof that finding the best 2-gram BLEU score is NP-hard. This is achieved via a reduction from the 3-Satisfiability (3SAT) problem. The authors demonstrate that a logic formula can be encoded into a confusion network such that a path achieving a perfect BLEU score exists if and only if the original formula is satisfiable.

Reduction from 3SAT to the BLEU-optimal path problem, showing the construction of networks $\mathcal{A}$ for clauses and $\mathcal{B}$ for variables.

This "bigram barrier" signifies that as soon as local decisions have non-local scoring consequences, the problem loses its tractable structure.

2. The Unigram Exception

Interestingly, the problem simplifies significantly when considering only unigrams (1-gram BLEU). The authors show this can be mapped to finding a Maximum Bipartite Matching. By utilizing the Hopcroft-Karp algorithm, the unigram optimum can be found in $O((C+n)^{5/2})$ time, where $C$ is the number of edges and $n$ is the hypothesis length.

Practical Approximation: Multi-Stack Decoding

Given the intractability of the general case, the authors propose a multi-stack decoder. This algorithm performs a sophisticated beam search by:

  • Traversing the network from left to right.
  • Grouping hypotheses into stacks based on length and position to ensure equitable comparison.
  • Employing a "modified BLEUS" score—a smoothed version of BLEU—to provide meaningful gradients for partial paths before they complete a full 4-gram match.

Experimental Evaluation

The approximation algorithm was tested on real-world translation data from the NIST 2003 and 2006 Chinese-English MT tasks. These datasets provided confusion networks from four different MT systems, with four human reference translations per sentence.

Key results include:

  • Search Efficiency: The multi-stack decoder significantly outperformed greedy search methods.
  • Convergence: BLEU scores stabilized rapidly as stack size increased. Experiments showed that maintaining approximately 15 hypotheses per node was sufficient to reach near-optimal performance, with diminishing returns thereafter.

Conclusion

This work clarifies the computational landscape of MT evaluation. It proves that while unigram optimization is "easy," the standard 4-gram BLEU search is fundamentally hard. However, the success of the multi-stack decoder suggests that in practice, highly effective approximations are reachable with limited computational overhead. Future work remains in extending these sentence-level optimizations to corpus-level BLEU, which introduces further combinatorial complexity.

Summary updated

BibTeX
@inproceedings{leusch2008complexity,
  author = {Gregor Leusch and Evgeny Matusov and Hermann Ney},
  title = {{Complexity of Finding the BLEU-optimal Hypothesis in a Confusion Network}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2008},
}
Figure