{"id":"784f092c-80b8-44e0-85cd-ee08c41c1092","arxiv_id":"1908.10090","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Beam search misses the global best translation for over half of sentences; under exact search, neural MT models prefer the empty translation for more than 50% of inputs.","lead":"Neural machine translation models often score the empty translation as their best output, and standard beam search misses the true best translation most of the time, which accidentally hides this flaw. The authors built an exact search procedure to measure these search and model errors precisely.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Exact search termination is asserted, not proven: an infinite branch with convergent score above gamma would invalidate the global-best claim.","rationale":"The reader's weakest assumption is exactly the termination and exactness of the depth-first search in Algorithm 2, and the paper's own language in the Related Work ('often converges in practice') plus the unproven footnote 6 supports that worry. This is load-bearing because the paper's main quantitative results — 51.8% empty global bests and 57.7% beam search errors — are only meaningful if the exact search truly explores the entire infinite search space and returns the global maximum for all 2,169 sentences. The concern is not that monotonicity is false, but that monotonicity alone is insufficient to guarantee termination: log-probabilities can approach zero without a uniform negative lower bound, so an infinite path with summably small penalties could keep its score above the current gamma and cause DFS to recurse forever. The proposed concrete test directly checks the empirical termination claim by instrumenting the released decoder; if every sentence returns, the practical concern is resolved for the reported test set, while the theoretical gap remains but no longer affects the Table 1 numbers. Therefore the reader's CONDITIONAL verdict is appropriate and unchanged.","tokens_in":7634,"tokens_out":11404,"duration_ms":132247,"concrete_test":"Install the released SGNMT decoder, load the WMT15 Transformer base model, and rerun the `simpledfs` exact search on all 2,169 sentences with a per-sentence node counter and no wall-clock limit; record the maximum node count and whether every sentence returns a hypothesis. If any sentence exceeds a generous finite bound (or fails to return), the Table 1 percentages are incomplete; if all return, the termination concern is empirically addressed for this test set.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central empirical claim (Table 1) is that unconstrained exact search finds the true global-best model score for every one of the 2,169 WMT15 sentences. That claim rests on Algorithm 2 terminating and returning a maximum, not merely a supremum. Monotonicity (Eq. 3) only guarantees that extending a prefix lowers the score; it does not bound the number of prefixes with score above a fixed gamma. Since softmax probabilities can be arbitrarily close to 1, per-token log-probabilities can be arbitrarily close to 0, so an infinite branch can have a convergent total score that never falls below gamma. In that case DFS recurses forever and no global best may exist. The paper asserts in footnote 6 that unconstrained exact search 'does not need maximum execution time limits,' and in Related Work concedes that the DFS 'often converges in practice.' No termination proof or convergence certificate is given. If the released decoder relied on any implicit stopping condition for any sentence, or if its stack simply ran out, the 51.8% empty-translation and 57.7% search-error percentages would be computed over incomplete search and the headline claim would fail.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents an exact decoding algorithm for neural machine translation that combines beam search with depth-first search, exploiting the monotonicity of locally normalized log-probability scores to prune partial hypotheses. Using this algorithm on the WMT15 English-German test set with a Transformer base model, the authors report that beam search with beam size 10 fails to find the global best model score on 57.7% of sentences, and that for 51.8% of sentences the model assigns the global best score to the empty translation (a single end-of-sentence token). They further show that larger beams reduce search errors but degrade BLEU because translations become too short, and they use length-constrained exact search and length normalization experiments to argue that the empty-translation phenomenon reflects an inherent model bias toward shorter translations.","tokens_in":7812,"tokens_out":8437,"duration_ms":100356,"significance":"If the empirical claims are correct, this is a valuable and striking quantification of the interplay between search errors and model errors in NMT, and it provides concrete evidence for the previously suspected length bias of locally normalized sequence models. The paper's strengths include an open-source implementation in the SGNMT decoder, replication of the main finding across four architectures, and a simple, parameter-free pruning criterion whose monotonicity argument is mathematically sound. The beam-derived lower bound is a legitimate lower bound rather than a circular constraint. However, the exactness of the headline result depends on a termination guarantee that is asserted but not proved, and the length-constrained experiments are run on tractability-based subsets, so the secondary conclusions are less secure.","major_comments":[{"comment":"The central exactness claim for Table 1 is not backed by a termination guarantee. Monotonicity (Eq. 3) only tells us that extending a prefix lowers the score; it does not rule out an infinite branch whose scores converge to a limit strictly above the current lower bound γ. On such a branch, the condition p′ ≥ γ in line 7 of Algorithm 2 remains true forever, so the DFS would not terminate and the global maximum over the finite-string search space may not exist. The paper's own Related Work says the DFS 'often converges in practice,' and footnote 6 asserts unconstrained exact search 'does not need maximum execution time limits' without proof. Please supply a termination theorem under explicit model assumptions or an empirical certificate (e.g., maximum visited depth and search time for every one of the 2,169 sentences), and state how the 51.8% empty-translation and 57.7% search-error percentages would be affected if any sentence required a stopping heuristic.","section":"Section 3, Algorithm 2, footnote 6"},{"comment":"The length-constrained experiments cover only subsets (73.0% and 48.3%) of the test set, yet the abstract and discussion draw conclusions about length bias and length normalization from them. Because footnote 6 says decoding was stopped after one day, the subsets may be selected by tractability, which would bias the comparison between Beam-10 and exact search. Please describe how the subsets were selected, report the source-length and difficulty statistics of included versus excluded sentences, and state which conclusions are claimed only for the feasible subset.","section":"Section 4, footnote 6, Tables 3 and 4"},{"comment":"The generalized exact search under length normalization is not specified in sufficient detail to verify the claim of finding global best translations for each length k. Equation (4) gives only the initial lower bounds; the length-dependent pruning rule, the range of k, and the termination condition are left to the cited SGNMT implementation. Please provide a formal algorithm or pseudocode for this variant, or restrict the claim to the unconstrained exact search.","section":"Section 4, exact inference under length constraints"}],"minor_comments":[{"comment":"Please state the beam size used to compute the initial lower bound γ for the exact search; the exactness of Algorithm 2 does not depend on it, but reproducibility does.","section":"Section 3, Table 1"},{"comment":"The row label 'Exact for Beam-10 length' should define whether the constraint fixes the exact target length to the length of the best Beam-10 hypothesis or imposes an inequality; the text suggests the former, but the table is ambiguous.","section":"Section 4, Table 3"},{"comment":"The sentence 'Comparable with http://matrix.statmt.org/' is incomplete; please specify which BLEU score is comparable and under what tokenization.","section":"Footnote 3"},{"comment":"The histograms would benefit from labeled bin edges and counts so that the peak in [0.0, 0.1] and the subset size in Figure 5 (73.0%) are directly readable.","section":"Figures 3 and 5"}],"recommendation":"major_revision","confidential_remarks":"The termination gap is the main risk to the headline claim. If the authors can provide a formal termination proof or an empirical certificate covering all test sentences, the paper is likely acceptable after the subset-selection issues in Section 4 are addressed. I recommend major revision rather than rejection because the core monotonicity argument and the empirical pattern across architectures are sound and the fixes are within the manuscript's scope."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe one thing to know: this paper reports the first exact search over an unconstrained NMT model and finds that for 51.8% of WMT15 sentences the model's global best is the empty translation, while beam-10 misses the global best 57.7% of the time. That reframes the known length-bias observation as a model error hidden by search errors. It's a real contribution, and the exact-inference scheme is clever: DFS with monotonicity-based pruning, initialized with a beam lower bound.\n\nWhat's solid: the algorithm is formally correct given monotonicity; results replicate across Transformer base/big, LSTM, and SliceNet; the SGNMT implementation is open source; and the empty-translation result is quantified in a way prior work didn't achieve. The paper deserves credit for that.\n\nThe main soft spot is termination. The stress-test is right: monotonicity doesn't bound the depth of a branch, and softmax probabilities can be arbitrarily close to 1, so an infinite branch with convergent score above gamma is possible. The paper asserts in footnote 6 that unconstrained exact search needs no time limits, but gives no proof; the related work concedes the DFS 'often converges in practice.' That's not the same as always. If any of the 2,169 sentences did not terminate, the Table 1 percentages would be computed over incomplete search. I don't think this is fatal—the empirical results likely stand—but a rigorous paper should either prove termination under the model's conditions or report the pruning depth and any fallen-back sentences.\n\nSecondary: the length-constrained experiments in Section 4 run on 73% and 48% subsets of the test set, so those conclusions are less secure. That's minor relative to the central claim.\n\nWho's this for: anyone working on NMT decoding, model calibration, or sequence modeling. It's the kind of paper that should go through peer review, with a request to tighten the termination argument. I'd cite it.\n\nCandidly, I'd send it to review rather than desk reject.","headline":"First exact search reveals NMT models often prefer empty translations while beam search hides it; read this for the result, brace for the unproven termination.","tokens_in":8306,"tokens_out":2492,"would_cite":true,"duration_ms":27136,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Beam search fails to find the model's best-scoring translation on most sentences, and the model often scores the empty translation highest.","keywords":["neural machine translation","exact inference","beam search","depth-first search","search errors","model errors","empty translation","length bias"],"falsifier":"Recompute the global best scores with an independent exact method, such as dynamic programming over length-bounded hypotheses, and compare on a random subset of the 2,169 WMT15 sentences; any disagreement, or any DFS run that fails to terminate within a fixed node budget, would invalidate the reported exact search-error and empty-translation rates.","tokens_in":7409,"feed_emoji":"🈳","tokens_out":8217,"duration_ms":74481,"temperature":0.7,"pith_summary":"This paper sets out to separate two sources of error in neural machine translation: search errors, where the decoder fails to find the translation the model scores highest, and model errors, where the model itself scores a bad translation highest. The authors construct an exact inference procedure that combines beam search with depth-first search and returns the global best model score for the monotone scoring function of vanilla NMT. Applied to the full WMT15 English-German test set with a Transformer base model, exact search reveals that beam search misses the global best score on most sentences, and that for 51.8% of sentences the model's global best translation is empty, a single end-of-sentence token. The authors conclude that beam search errors are partly masking a severe model bias toward shorter translations, and that simply improving search would make translation quality worse unless the model's adequacy failure is fixed.","feed_headline":"Exact search shows NMT often prefers an empty translation","feed_subtitle":"Removing beam-search errors drops BLEU from 30.3 to 2.1 because over half of global bests are one-token empty outputs.","key_machinery":"The load-bearing mechanism is the monotonicity of NMT log-scores: because every conditional log-probability in the chain-rule factorization is negative, the score of any partial hypothesis is strictly lower than the score of any of its prefixes. The exact search takes the beam search result to initialize a lower bound $\\gamma$, then explores the translation space depth-first and prunes any branch whose accumulated score falls below $\\gamma$; whenever a better complete hypothesis is found, the bound is raised. Placing the end-of-sentence token first in the vocabulary order raises $\\gamma$ early and sharpens pruning. For length-constrained decoding, the scheme is generalized to length-dependent lower bounds $\\gamma_k$, which is what allows exact search under length normalization.","core_discovery":"The paper's central discovery is a quantitative separation of search and model errors in NMT under exact inference. For the Transformer base model on WMT15 English-German, greedy decoding has a 73.6% search-error rate and beam-10 has 57.7%, yet beam-10 achieves BLEU 30.3; exact search achieves BLEU 2.1 with length ratio 0.06 because 51.8% of the time the global best model score belongs to the empty translation. The authors show the bias is not an artifact of one architecture: an LSTM baseline has 47.7% empty global bests and SliceNet 41.2%, and even a strong Transformer-Big system has 25.8%. They further show that constraining exact search to a minimum length does not remove the model's preference for very short translations, while length normalization restores realistic lengths but still does not match beam search BLEU. The paper's conclusion is that vanilla NMT relies on search errors to hide a model-level adequacy failure, which is unsatisfactory from a modeling perspective.","pith_inferences":["If the empty-global-best phenomenon generalizes across language pairs and domains, then reporting BLEU under beam search systematically overstates model adequacy; benchmark results should be complemented by exact-search or length-controlled diagnostics.","A natural testable extension is to apply the exact search to models trained with objectives designed to fix length bias, such as global conditioning or margin-based training, and check whether the empty-global-best rate drops; the paper does not run this experiment.","The monotonicity-based pruning could be replaced by an admissible A*-style search with a length-aware heuristic to independently verify the reported exact scores on a random subset, avoiding reliance on DFS termination in practice.","The length-constrained exact-search results suggest a practical inference-time recipe: decode with a minimum length constraint set by the source length, then compare exact scores across that constrained space; the paper's numbers hint this could restore adequacy without retuning, but they do not claim it."],"forward_implications":["Improving search quality alone, such as raising the beam size, lowers BLEU because fewer search errors means the model's short-translation bias is exposed more often.","Exact inference can serve as a diagnostic tool that quantifies, in absolute terms, how often a trained NMT model assigns its best score to degenerate translations.","Decoding fixes that only change search, such as heuristics that reward length, address symptoms: length normalization gives plausible length ratios but does not recover beam search's BLEU in the paper's experiments.","The empty-translation problem worsens with source length, so models that score well on short sentences may be substantially more degraded on long inputs.","The reported rates imply that model-level adequacy, not search, is the binding constraint for these systems."],"supporting_citations":[{"why":"defines the Transformer base architecture whose model scores are the subject of the exact search experiments.","marker":"Vaswani et al. 2017"},{"why":"provides the byte-pair-encoding subword segmentation that determines the vocabulary and hence the search space.","marker":"Sennrich et al. 2016"},{"why":"supplies the strong LSTM, SliceNet, and Transformer-Big baselines used to show the empty-global-best problem is not specific to one architecture.","marker":"Stahlberg et al. 2018a"},{"why":"prior observation that larger beams produce shorter translations, which the exact search quantifies as a model error.","marker":"Koehn and Knowles 2017"},{"why":"gives the locally-normalized-training account of length bias that the paper adopts as the model-level explanation.","marker":"Sountsov and Sarawagi 2016"},{"why":"argues locally normalized models cannot reserve probability for longer translations, the mechanism the paper probes with length constraints.","marker":"Murray and Chiang 2018"},{"why":"shows the consistent best string problem for RNNs is decidable, the result the paper contrasts with its own DFS approach that often converges in practice.","marker":"Chen et al. 2018"},{"why":"offers the noisy-data uncertainty explanation for length deficiency that the paper contrasts with its own conclusion.","marker":"Ott et al. 2018"},{"why":"earlier approximation of NMT search-error rates via n-best lists, which the exact inference results replace with direct counts.","marker":"Niehues et al. 2017"}],"fun_headline_variants":["Exact NMT search finds empty translations as top scores","Beam search errors mask NMT's empty-output model bias","NMT's global best score is an empty translation half the time","Exact inference reveals NMT's adequacy failure: empty outputs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The exact depth-first search terminates on every sentence and returns the true global best model score; the paper asserts no execution time limits are needed but concedes in its discussion of related work that the algorithm often converges in practice.","fun_headline_variants_meta":{"raw":{"variants":["Exact NMT search finds empty translations as top scores","Beam search errors mask NMT's empty-output model bias","NMT's global best score is an empty translation half the time","Exact inference reveals NMT's adequacy failure: empty outputs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000652,"raw_usage":{"total_tokens":2990,"prompt_tokens":950,"completion_tokens":2040,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":566,"completion_tokens_details":{"reasoning_tokens":1969}},"tokens_in":566,"tokens_out":2040,"duration_ms":14218,"temperature":1.0,"reasoning_tokens":1969,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T10:53:26.900335+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Recompute the global best scores with an independent exact method, such as dynamic programming over length-bounded hypotheses, and compare on a random subset of the 2,169 WMT15 sentences; any disagreement, or any DFS run that fails to terminate within a fixed node budget, would invalidate the reported exact search-error and empty-translation rates.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"gives the locally-normalized-training account of length bias that the paper adopts as the model-level explanation."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"argues locally normalized models cannot reserve probability for longer translations, the mechanism the paper probes with length constraints."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"earlier approximation of NMT search-error rates via n-best lists, which the exact inference results replace with direct counts."}],"review_version":1}