BLEU

BLEU (bilingual evaluation understudy) scores a generated sentence by how many of its word n-grams also occur in one or more human reference sentences. It is a clipped n-gram precision, averaged geometrically over $n = 1, \dots, 4$ and multiplied by a brevity penalty that stands in for recall. Papineni et al. (2002) proposed it at IBM for machine translation, as a cheap automatic stand-in for human judges. Image captioning borrowed it, and captioning papers report BLEU-1 to BLEU-4 beside other metrics. “BLEU” is not one number, though. Post (2018) calls it a parameterized metric, whose value depends on the number of references, the reference length rule, smoothing, case and tokenization. This article gives the definition as the paper states it, the parameters and the main implementations, and an example that scores one fixed set of captions under many of those choices.

Formula

Modified n-gram precision. For each candidate sentence, every n-gram is counted, and each count is clipped at the largest number of times that n-gram occurs in any single reference: $\text{Count}_{\text{clip}} = \min(\text{Count}, \text{Max Ref Count})$. Over a test corpus the clipped counts and the candidate n-gram counts are summed separately before dividing:

$$p_n = \frac{\sum_{C \in \text{Candidates}} \sum_{g \in C} \text{Count}_{\text{clip}}(g)}{\sum_{C \in \text{Candidates}} \sum_{g \in C} \text{Count}(g)}.$$

Papineni et al.’s own examples show the clipping. The candidate “the the the the the the the” against the references “The cat is on the mat” and “There is a cat on the mat” has standard unigram precision 7/7 but modified unigram precision 2/7, because “the” occurs at most twice in one reference. In their Example 1, a good candidate has modified unigram precision 17/18 and bigram precision 10/17, against 8/14 and 1/13 for a poor one.

Brevity penalty. Let $c$ be the total length of the candidate corpus and $r$ the effective reference length: the sum, over candidates, of the “best match length”, the reference length closest to that candidate’s. Then

$$\text{BP} = \begin{cases} 1 & \text{if } c > r, \\ e^{\,1 - r/c} & \text{if } c \le r, \end{cases} \qquad \text{BLEU} = \text{BP} \cdot \exp\Big(\sum_{n=1}^{N} w_n \log p_n\Big),$$

with $N = 4$ and uniform weights $w_n = 1/N$ in the paper’s baseline. In the log domain, $\log \text{BLEU} = \min(1 - r/c, 0) + \sum_n w_n \log p_n$. The paper does not say which reference to choose when two are equally close to the candidate; coco-caption, sacreBLEU and NLTK all take the shorter one (read in their code). “BLEU-$k$” in captioning tables is this cumulative score with $N = k$, the geometric mean of $p_1, \dots, p_k$, not the $k$-gram precision alone.

Range. BLEU lies between 0 and 1. Papineni et al. note that few translations reach 1 unless they are identical to a reference, so even a human translator will not necessarily score 1. sacreBLEU reports the same quantity multiplied by 100; coco-caption and NLTK report it on the 0–1 scale, and captioning results tables such as Image Captioning’s print it ×100.

Intuition

Precision rewards a candidate for using the words and phrases the references use; the longer n-grams reward getting their order right, which the authors associate with fluency and the unigrams with adequacy. Clipping stops a system from gaining precision by repeating a safe word.

Precision alone rewards saying little: Papineni et al.‘s Example 3, the candidate “of the”, has modified unigram and bigram precisions of 2/2 and 1/1. The obvious fix, recall, does not work with several references. A good translation uses one of the references’ word choices, not all of them, so in their Example 4 “I always invariably perpetually do” recalls more reference words than “I always do” and is the worse sentence. The brevity penalty is the substitute: candidates longer than the references are already penalized by precision, so only candidates shorter than their best-matching reference are penalized again.

The geometric mean takes into account that modified precision decays roughly exponentially with $n$. The authors chose $N = 4$ because it gave the best correlation with monolingual judgments, though 3-grams and 5-grams gave comparable results. A footnote warns that the geometric mean is harsh when any $p_n$ vanishes, which they expected to be extremely rare on test corpora of reasonable size.

Interpretation

BLEU is designed for a corpus, not a sentence. Papineni et al. compute the brevity penalty over the whole corpus because averaging per-sentence penalties would punish length deviations on short sentences harshly, and another footnote says BLEU only needs to match human judgment when averaged over a test corpus. A single sentence can score 0 when it shares no 4-gram with any reference, however many words it gets right.

Scores are comparable only under the same references. In the paper’s experiments, on a test corpus of about 500 sentences (40 news stories), the same human translator scored 0.3468 against four references and 0.2571 against two. Post (2018) gives a later instance: the WMT 2017 system online-B scored 22.04 BLEU on English–Finnish with one reference and 25.25 with two.

The original evaluation. The paper scored five Chinese–English “systems” (three commercial machine translation systems S1–S3 and two human translators H1, H2) on that 500-sentence corpus with two references. Table 1 gives 0.0527, 0.0829, 0.0930, 0.1934 and 0.2571. To ask whether the close pair S2 and S3 differ reliably, the authors split the corpus into 20 blocks of 25 sentences and computed paired t-statistics between neighbouring systems: 6, 3.4, 24 and 11 (Table 2). They took 1.7 as the 95% level, so they called every difference significant. Simulating a single reference per story (one of the four, chosen at random) kept the same rank order. Ten monolingual English speakers and ten bilingual Chinese speakers rated 250 sentence–translation pairs. A linear regression of the monolingual group’s scores on BLEU over the five systems had correlation coefficient 0.99, and the bilingual group’s 0.96. In our reading, five systems are a small sample for a correlation, and the result is about ranking those five. Significance tests for such comparisons are covered in statistical significance in evaluation.

In captioning, BLEU-4 has agreed poorly with human judgments of whole systems. Image Captioning reports a system-level correlation of 0.05 for BLEU-4 over the 2015 COCO challenge entries, and Show and Tell’s captions outscoring human captions on BLEU-4 while raters judged them worse.

When to Use It

The metric’s critics give its appropriate uses. Callison-Burch, Osborne and Koehn (2006) list tracking broad, incremental changes to a single system, comparing systems that use similar translation strategies, and use as an objective for tuning parameters. Inappropriate uses, in their list, include comparing systems that use radically different strategies, measuring improvements in aspects of output that BLEU models badly, and monitoring improvements that occur infrequently within a test corpus. For captioning benchmarks such as COCO and Flickr30k, BLEU is reported beside METEOR, ROUGE-L, CIDEr and SPICE rather than alone.

A reported BLEU should name its configuration. Post proposed that every score come from metric-internal tokenization of untouched references, and that the tool print a version string recording the parameters. His example signature BLEU+c.mixed+l.en-de+#.1+s.exp+t.wmt14+tok.13a+v.1.2.10 records mixed case, the language pair, one reference, exponential smoothing, the test set, the 13a tokenizer and the sacreBLEU version. Captioning results are instead computed with the coco-caption code, whose conventions Video Captioning documents.

Failure Cases

• Many different outputs, one score. Callison-Burch et al. (2006) count the reorderings BLEU cannot see. Phrases bracketed by bigram mismatches can be permuted without losing any matched n-gram, giving at least $(k - b)!$ similarly scored variants of a $k$-word hypothesis with $b$ bigram matches. Their 18-token example has at least 40,320 permutations, and for some translations of a 2005 NIST system the count exceeds $10^{73}$. Words that match nothing can be replaced by arbitrary words at no cost, and content words carry no more weight than function words.
• Systems of different kinds. In the 2005 NIST Arabic–English evaluation, the entry ranked first by human judges was ranked sixth by BLEU. It was not fully automatic: monolingual English speakers chose among alternative phrase translations and post-edited the result. Over the seven entries, the $R^2$ between BLEU and human adequacy was 0.14 with that entry and 0.87 without it (for fluency, 0.002 and 0.742). In the authors’ own experiment, BLEU greatly underestimated the rule-based Systran system against two phrase-based statistical systems trained on Europarl. They conclude that a higher BLEU score is neither necessary nor sufficient for better translation.
• Sentence-level use. Unsmoothed sentence BLEU is 0 whenever a 4-gram precision is 0, which is why the smoothing methods below exist. For image descriptions, Elliott and Keller (2014) measured sentence-level Spearman correlations with expert judgments on Flickr8K: 0.345 for unigram BLEU without brevity penalty, 0.429 for smoothed BLEU-4, 0.435 for ROUGE-SU4 and 0.524 for METEOR. On their own 2013 dataset the values were 0.097, 0.177, 0.188 and 0.233. Their Table 1 gives that dataset’s size as $n = 2{,}040$ pairs, while their text and Figure 2 give 2,042.
• Length gaming. The penalty is computed on corpus totals, so a system can write some captions too short and others too long and keep $\text{BP} = 1$. The example below builds such a system.
• Unreported preprocessing. Scores computed with different reference tokenization are not comparable (next section).

Variants

BLEU as a parameterized family

Post (2018) lists the parameters hidden behind “BLEU”: the number of references, the brevity penalty’s handling of multiple references, the maximum n-gram order and the smoothing of zero counts. Preprocessing, meaning tokenization, normalization, compound splitting and case, applied to the references by the user, is the main source of incomparable numbers. In his Table 1, varying only these schemes for one WMT 2017 system moved BLEU by up to 1.8 points (German–English, cased), about 1.0 on average. He names case as the biggest single effect. His Table 2 could not tell, for several widely cited papers including Vaswani et al. (2017), which configuration they had used.

Papineni et al. folded case and did no other normalization. sacreBLEU’s v2.6.0 defaults differ in the other direction: lowercase=False, the 13a tokenizer (a re-implementation of the WMT script mteval-v13a’s tokenization), smooth_method='exp', and effective_order=False, which its sentence-level function recommends turning on. Its score is returned as 0.0 at once when no n-gram of any order matches. The 13a tokenizer splits off most punctuation, splitting periods and commas except between digits; by its code it also unescapes ", &, < and >.

Smoothing for single sentences

Chen and Cherry (2014) compared seven smoothing methods for sentence-level BLEU, writing $m_n$ for matched and $l_n$ for total n-grams:

1. Replace $m_n = 0$ by a small $\varepsilon$ (0.1 after tuning).
2. Add 1 to $m_n$ and $l_n$ for $n \ge 2$. Lin and Och’s ORANGE paper (COLING 2004) defined this smoothed BLEU, “BLEUS”, so that a sentence still scores when it has matches of shorter n-grams. Chen and Cherry attribute it to the other 2004 paper by Lin and Och, on longest common subsequence and skip-bigram statistics, which we did not read.
3. The geometric sequence of NIST’s mteval-v13a: the $k$-th order with no match gets the count $1/2^k$.
4. Method 3 with larger divisors for shorter sentences ($K = 5$), new in the paper.
5. Average each order’s count with its neighbours’, also new.
6. Interpolation with a prior extrapolated from lower orders (from Gao and He, 2013; $\alpha = 5$).
7. Methods 4 and 5 combined, also new.

On WMT into-English data, Kendall’s τ with human judgments of single segments rose from 0.165 without smoothing to between 0.224 and 0.236 with smoothing. Method 7 was best. At system level, an average of sentence BLEU weighted by reference length correlated better than corpus BLEU in Pearson’s γ (0.754 to 0.766 against 0.720 in Table 2, where Spearman’s ρ is 0.887 for every row), and the choice of smoothing barely mattered. Used for tuning a translation system with a small feature set, the methods gave similar test BLEU; with a large one, method 7 beat no smoothing significantly in three of four scenarios, while no smoothing beat every smoothed method on Chinese–English MT08. The authors note that ordinary document-level BLEU needs no smoothing.

Implementations

	Aggregation and scale	Reference length	Zero counts	Tokenization
Papineni et al. (2002)	corpus sums, 0–1	best match (closest); tie rule unstated	none; any $p_n = 0$ gives 0	case folding only
coco-caption (3a9afb2)	corpus BLEU-1..4 plus per-image scores, 0–1	closest forced by bleu.py; scorer also offers shortest and average	$10^{-15}$ added to matches, $10^{-9}$ to totals	PTB tokenizer, lowercased, punctuation removed
sacreBLEU (v2.6.0)	corpus, 0–100	closest, ties shorter	exp (method 3) by default; also floor, add-k, none	13a, cased by default
NLTK (3.9.2)	corpus_bleu and sentence_bleu, 0–1	closest, ties shorter	method0 by default; methods 1–7 of Chen and Cherry	none (token lists in)

Two behaviours come from the code rather than the documentation:

• NLTK. method0 does not return 0 for a missing 4-gram match. It substitutes sys.float_info.min and warns, so an unsmoothed sentence score is a tiny positive number; the result is exactly 0 only when no unigram matches. NLTK’s modified_precision also sets each sentence’s n-gram total to at least 1 (max(1, …)), so corpus_bleu counts a phantom n-gram for every candidate shorter than $n$, which departs from Papineni’s corpus sums. The example measures this difference.
• coco-caption. Its bleu_scorer.py uses average when called with no option and a single segment, closest otherwise; bleu.py passes closest. The scorer is David Chiang’s code, modified by Hao Fang and Tsung-Yi Lin, and the file carries its own restrictive notice (“Do not redistribute without permission”) beside the repository’s BSD licence. The example below therefore copies nothing from it and re-implements the guards from their behaviour. Video Captioning describes the tokenizer, the tie rule and the guards as captioning papers use them.

Example: one set of captions, many BLEUs

The script renders 200 synthetic 64×64 scenes, each with two shapes of distinct colours (red, green, blue, yellow) whose relation is left, right, above or below. The ground truth is the scene list. Each image has eight reference captions from templates that mix sentence case, full stops, commas and colons, and that phrase the relation in both directions. For each image a seeded permutation fixes the order of the references, and the 1-, 2-, 4- and 8-reference sets are its first $k$. Nesting them means that the clipping maximum of every n-gram can only grow with $k$.

Three rule-based captioners read the rendered pixels. They threshold each colour, label connected components with scikit-image, name the shape from the number of filled bounding-box corners, and read the relation from the centroids:

• S1 names colours, shapes and relation in sentence case with a full stop: “A red circle to the left of a blue square.”
• S2 names only colours and relation, in lower case without punctuation: “a red shape to the left of a blue shape”. It never names a shape.
• G games the length: on even images it writes S1’s first object only (“A red circle.”), and on odd images it appends a 13-word description of the background to S1’s caption.

The captions are fixed. Only the scoring changes, one choice at a time from a baseline of four references, closest reference length, lower case, punctuation split into tokens, corpus BLEU-4 and no smoothing. Table A varies the number of references, the reference length rule (closest, shortest, or the mean as coco-caption’s average option computes it), case, and punctuation: split into tokens, left attached to words by whitespace splitting, or removed. Table B scores the baseline under four smoothing rules, first as corpus BLEU and then as the mean of sentence BLEU. The rules are none, add-1 for $n \ge 2$, sacreBLEU’s exp (ported from v2.6.0) and coco-caption’s guards. Each row prints the ranking and the S2 − G difference, both computed from unrounded scores.

The hand implementation is checked against NLTK 3.9.2 at corpus level on every closest-length condition, and at sentence level on every baseline sentence. The script runs in about 5 seconds (Python 3.13.9, NumPy 2.3.5, scikit-image 0.25.2, NLTK 3.9.2).

"""One set of captions, many BLEUs: three rule-based captioners read 200 synthetic shape scenes,
and each fixed set of captions is scored under the configurations BLEU leaves open.
NumPy 2.3.5, scikit-image 0.25.2, NLTK 3.9.2 (used only as a cross-check)."""
import os
os.environ["OMP_NUM_THREADS"] = "1"; os.environ["OPENBLAS_NUM_THREADS"] = "1"
import math, re, warnings
from collections import Counter
import numpy as np
from skimage.draw import disk, polygon, rectangle
from skimage.measure import label, regionprops
from nltk.translate.bleu_score import corpus_bleu, sentence_bleu, SmoothingFunction

warnings.filterwarnings("ignore")             # NLTK warns on every zero n-gram count

COLOURS = {"red": (1, 0, 0), "green": (0, 1, 0), "blue": (0, 0, 1), "yellow": (1, 1, 0)}
SHAPES = ["circle", "square", "triangle"]
REL = {"left": ("to the left of", "to the right of"), "right": ("to the right of", "to the left of"),
       "above": ("above", "below"), "below": ("below", "above")}
TEMPLATES = ["A {A} is {R} a {B}.", "a {A} {R} a {B}", "There is a {A} {R} a {B}.",
             "A {B} is {Q} a {A}.", "The {A} is {R} the {B}.", "Two shapes: a {A} and a {B}.",
             "On a black background, a {A} is {R} a {B}.", "A {B}, with a {A} {R} it."]
PAD = " in a small synthetic picture with a plain black background and nothing else"
N_IMG, SIZE = 200, 64

# ---------------------------------------------------------------- scenes and references
def draw(img, shape, colour, r, c, s):
    if shape == "circle":
        rr, cc = disk((r, c), s + 0.5, shape=img.shape[:2])
    elif shape == "square":
        rr, cc = rectangle((r - s, c - s), (r + s, c + s), shape=img.shape[:2])
    else:
        rr, cc = polygon([r - s, r + s, r + s], [c, c - s, c + s], shape=img.shape[:2])
    img[rr, cc] = COLOURS[colour]
    m = np.zeros(img.shape[:2], bool); m[rr, cc] = True
    return m

def make_scene(rng):
    cols = rng.choice(list(COLOURS), 2, replace=False)
    shps = rng.choice(SHAPES, 2)
    rel = ["left", "right", "above", "below"][rng.integers(4)]
    img = np.zeros((SIZE, SIZE, 3))
    sign = -1 if rel in ("left", "above") else 1          # object A is left of / above B when sign < 0
    major = [32 + sign * 16 + rng.integers(-3, 4), 32 - sign * 16 + rng.integers(-3, 4)]
    minor = [32 + rng.integers(-8, 9), 32 + rng.integers(-8, 9)]
    masks = []
    for k in range(2):
        s = int(rng.integers(6, 10))
        r, c = (minor[k], major[k]) if rel in ("left", "right") else (major[k], minor[k])
        masks.append(draw(img, shps[k], cols[k], r, c, s))
    return img, dict(cols=list(cols), shps=list(shps), rel=rel), masks

def references(scene):
    A = f"{scene['cols'][0]} {scene['shps'][0]}"; B = f"{scene['cols'][1]} {scene['shps'][1]}"
    R, Q = REL[scene["rel"]]
    return [t.format(A=A, B=B, R=R, Q=Q) for t in TEMPLATES]

# ---------------------------------------------------------------- rule-based captioners
def read_objects(img):
    """Threshold each colour, label components, classify shape by its filled bounding-box corners."""
    objs = []
    for name, rgb in COLOURS.items():
        m = np.all(np.isclose(img, rgb), axis=2)
        for p in regionprops(label(m)):
            r0, c0, r1, c1 = p.bbox
            corners = int(m[r0, c0]) + int(m[r0, c1 - 1]) + int(m[r1 - 1, c0]) + int(m[r1 - 1, c1 - 1])
            objs.append((name, {4: "square", 2: "triangle", 0: "circle"}.get(corners, "shape"), p.centroid))
    return objs

def describe(objs):
    a, b = objs
    dy, dx = b[2][0] - a[2][0], b[2][1] - a[2][1]
    if abs(dx) >= abs(dy):
        return (a, b, "to the left of") if dx > 0 else (b, a, "to the left of")
    return (a, b, "above") if dy > 0 else (b, a, "above")

def s1_caption(img):            # shape reader: sentence case and a full stop
    f, s, rel = describe(read_objects(img))
    return f"A {f[0]} {f[1]} {rel} a {s[0]} {s[1]}."

def s2_caption(img):            # colour reader: no shapes, lower case, no punctuation
    f, s, rel = describe(read_objects(img))
    return f"a {f[0]} shape {rel} a {s[0]} shape"

def g_caption(img, i):          # length gaming: truncated on even images, padded on odd ones
    f, s, rel = describe(read_objects(img))
    return f"A {f[0]} {f[1]}." if i % 2 == 0 else f"A {f[0]} {f[1]} {rel} a {s[0]} {s[1]}{PAD}."

# ---------------------------------------------------------------- BLEU and its open choices
def tokenize(text, lower=True, punct="split"):
    if lower:
        text = text.lower()
    if punct == "split":                                   # punctuation marks become tokens
        return re.findall(r"\w+|[^\w\s]", text)
    if punct == "kept":                                    # "kept": stays attached ("square.")
        return text.split()
    return [t for t in re.findall(r"\w+|[^\w\s]", text) if re.search(r"\w", t)]   # "removed"

def ngrams(toks, n):
    return Counter(tuple(toks[i:i + n]) for i in range(len(toks) - n + 1))

def stats(cand, refs, reflen="closest", N=4, floor1=False):
    """Clipped matches m_n, candidate n-gram totals t_n, candidate length c, reference length r."""
    m, t = [0] * N, [0] * N
    for n in range(1, N + 1):
        cnt = ngrams(cand, n); mx = Counter()
        for r in refs:
            for g, k in ngrams(r, n).items():
                mx[g] = max(mx[g], k)                      # clip at the count in any ONE reference
        m[n - 1] = sum(min(k, mx[g]) for g, k in cnt.items()); t[n - 1] = sum(cnt.values())
        if floor1:
            t[n - 1] = max(1, t[n - 1])                    # NLTK's modified_precision floor
    lens = [len(r) for r in refs]
    if reflen == "closest":
        rl = min(lens, key=lambda L: (abs(L - len(cand)), L))   # ties go to the shorter reference
    elif reflen == "shortest":
        rl = min(lens)
    else:
        rl = sum(lens) / len(lens)                         # "average", as coco-caption allows
    return m, t, len(cand), rl

def bp_of(c, r):
    return 1.0 if c > r else math.exp(1 - r / c)

def bleu_none(m, t, c, r):                                 # Papineni et al.: any p_n = 0 gives 0
    if any(x == 0 for x in m) or any(x == 0 for x in t):
        return 0.0
    return bp_of(c, r) * math.exp(sum(math.log(a / b) for a, b in zip(m, t)) / len(m))

def bleu_add1(m, t, c, r):                                 # Lin & Och: add 1 for n >= 2
    return bleu_none([m[0]] + [x + 1 for x in m[1:]], [t[0]] + [x + 1 for x in t[1:]], c, r)

# --- port of sacreBLEU v2.6.0 BLEU.compute_bleu (smooth_method='exp', effective_order=False) and
# --- utils.my_log; sacreBLEU, Apache-2.0, modified (ported); the pinned files carry no copyright line;
# --- licence: https://github.com/mjpost/sacrebleu/blob/v2.6.0/LICENSE.txt
def my_log(num):
    if num == 0.0:
        return -9999999999
    return math.log(num)

def bleu_exp(correct, total, sys_len, ref_len, max_ngram_order=4):
    bp = 1.0
    if sys_len < ref_len:
        bp = math.exp(1 - ref_len / sys_len) if sys_len > 0 else 0.0
    precisions = [0.0] * max_ngram_order
    if not any(correct):
        return 0.0
    smooth_mteval = 1.
    eff_order = max_ngram_order
    for n in range(1, len(precisions) + 1):
        if total[n - 1] == 0:
            break
        if correct[n - 1] == 0:
            smooth_mteval *= 2
            precisions[n - 1] = 100. / (smooth_mteval * total[n - 1])
        else:
            precisions[n - 1] = 100. * correct[n - 1] / total[n - 1]
    score = bp * math.exp(sum([my_log(p) for p in precisions[:eff_order]]) / eff_order)
    return score / 100.0                                   # sacreBLEU reports 0-100; here 0-1
# --- end of port

def bleu_coco(m, t, c, r):
    """coco-caption's guards, re-implemented from the behaviour of its scorer (no code copied)."""
    tiny, small = 1e-15, 1e-9
    b = math.prod((a + tiny) / (g + small) for a, g in zip(m, t)) ** (1 / len(m))
    ratio = (c + tiny) / (r + small)
    return b * math.exp(1 - 1 / ratio) if ratio < 1 else b

SMOOTH = {"none": bleu_none, "add-1": bleu_add1, "exp": bleu_exp, "coco": bleu_coco}

def corpus(st, fn):                                        # sum the statistics, then one formula
    M = [sum(s[0][k] for s in st) for k in range(4)]; T = [sum(s[1][k] for s in st) for k in range(4)]
    return fn(M, T, sum(s[2] for s in st), sum(s[3] for s in st))

def ranking(scores):
    names = sorted(scores, key=lambda k: -scores[k]); out = names[0]
    for a, b in zip(names, names[1:]):
        out += (" = " if abs(scores[a] - scores[b]) < 1e-12 else " > ") + b
    return out

def run():
    rng = np.random.default_rng(0)
    data = [make_scene(rng) for _ in range(N_IMG)]
    perms = [rng.permutation(8) for _ in range(N_IMG)]     # nested reference subsets: first 1, 2, 4, 8
    imgs, scenes, masks = zip(*data)
    refs_all = [[references(sc)[j] for j in p] for sc, p in zip(scenes, perms)]
    caps = {"S1": [s1_caption(im) for im in imgs], "S2": [s2_caption(im) for im in imgs],
            "G": [g_caption(im, i) for i, im in enumerate(imgs)]}

    # checks: the data, the captioners' reading, and the implementation against NLTK
    overlap = sum(int((m[0] & m[1]).sum()) for m in masks)
    print(f"images {N_IMG}, object overlap {overlap} px, distinct references per image "
          f"{min(len(set(r)) for r in refs_all)}, objects read {dict(Counter(len(read_objects(i)) for i in imgs))}")
    def truth(sc):
        a, b = (sc["cols"][0], sc["shps"][0]), (sc["cols"][1], sc["shps"][1])
        return {"left": (a, b, "to the left of"), "right": (b, a, "to the left of"),
                "above": (a, b, "above"), "below": (b, a, "above")}[sc["rel"]]
    ok1 = ok2 = 0
    for im, sc in zip(imgs, scenes):
        f, s, rel = describe(read_objects(im)); g = truth(sc)
        ok1 += (f[0], f[1]) == g[0] and (s[0], s[1]) == g[1] and rel == g[2]
        ok2 += f[0] == g[0][0] and s[0] == g[1][0] and rel == g[2]
    texts = [x for r in refs_all for x in r] + [x for c in caps.values() for x in c]
    bad = sum(bool(re.search(r"\W", t)) for x in texts for t in tokenize(x, punct="removed"))
    att = sum(bool(re.search(r"\w", t) and re.search(r"\W", t)) for x in texts for t in tokenize(x, punct="kept"))
    print(f"punctuation check: tokens with punctuation under 'removed' {bad}; "
          f"tokens with attached punctuation under 'kept' {att}")
    print(f"S1 colours, shapes and relation correct {ok1}/{N_IMG}; S2 colours and relation correct {ok2}/{N_IMG}")

    def score(name, k=4, reflen="closest", lower=True, punct="split", floor1=False):
        C = [tokenize(x, lower, punct) for x in caps[name]]
        R = [[tokenize(x, lower, punct) for x in r[:k]] for r in refs_all]
        return C, R, [stats(c, r, reflen, floor1=floor1) for c, r in zip(C, R)]

    sm = SmoothingFunction(); nltk_fn = {"none": sm.method0, "add-1": sm.method2, "exp": sm.method3}
    d_full = d_short = d_floor = d_sent = 0.0; n_short = 0
    for k in (1, 2, 4, 8):
        for lower in (True, False):
            for punct in ("split", "kept", "removed"):
                for name in caps:
                    C, R, st = score(name, k, "closest", lower, punct)
                    stf = score(name, k, "closest", lower, punct, floor1=True)[2]
                    short = any(len(c) < 4 for c in C)
                    for sname in ("none", "add-1", "exp"):
                        ref = corpus_bleu(R, C, smoothing_function=nltk_fn[sname])
                        d = abs(corpus(st, SMOOTH[sname]) - ref)
                        if short:
                            d_short, n_short = max(d_short, d), n_short + 1
                        else:
                            d_full = max(d_full, d)
                        d_floor = max(d_floor, abs(corpus(stf, SMOOTH[sname]) - ref))
                    if k == 4 and lower and punct == "split":
                        for c, r, s in zip(C, R, st):
                            for sname in ("none", "add-1", "exp"):
                                d_sent = max(d_sent, abs(SMOOTH[sname](*s) - sentence_bleu(
                                    r, c, smoothing_function=nltk_fn[sname])))
    print(f"hand vs NLTK, corpus, no candidate under 4 tokens: max diff {d_full:.1e}")
    print(f"hand vs NLTK, corpus, {n_short} cases with a candidate under 4 tokens: max diff {d_short:.1e}; "
          f"with NLTK's denominator floor: {d_floor:.1e}")
    print(f"hand vs NLTK, sentence level (baseline): max diff {d_sent:.1e}")
    rel_c, zero_n, zero_max = 0.0, 0, 0.0
    for name in caps:
        st = score(name)[2]
        rel_c = max(rel_c, abs(corpus(st, bleu_coco) / corpus(st, bleu_none) - 1))
        for s in st:
            if bleu_none(*s) == 0.0:
                zero_n += 1; zero_max = max(zero_max, bleu_coco(*s))
    print(f"coco guards vs none, corpus: max relative diff {rel_c:.1e}; "
          f"{zero_n} sentences score 0 unsmoothed, guarded max {zero_max:.1e}")

    # Table A: corpus BLEU-4 (no smoothing), one choice changed at a time from the baseline
    configs = [("baseline: 4 refs, closest, lowercased, punct split", {}),
               ("1 reference", {"k": 1}), ("2 references", {"k": 2}), ("8 references", {"k": 8}),
               ("shortest reference length", {"reflen": "shortest"}),
               ("average reference length", {"reflen": "average"}),
               ("cased", {"lower": False}), ("punctuation kept on words", {"punct": "kept"}),
               ("punctuation removed", {"punct": "removed"})]
    print(f"\nA. corpus BLEU-4    {'configuration':52s}{'S1':>8s}{'S2':>8s}{'G':>8s}   ranking")
    tableA, base_rank, flips = {}, None, []
    for lab, kw in configs:
        sc = {n: corpus(score(n, **kw)[2], bleu_none) for n in caps}
        tableA[lab] = sc; rk = ranking(sc); base_rank = base_rank or rk
        flips += [lab] if rk != base_rank else []
        print(f"{'':19s}{lab:52s}" + "".join(f"{sc[n]:8.4f}" for n in caps)
              + f"   {rk:12s}  S2-G {sc['S2'] - sc['G']:+.2e}")
    print("spread (max - min over table A):", ", ".join(
        f"{n} {max(v[n] for v in tableA.values()) - min(v[n] for v in tableA.values()):.4f}" for n in caps))

    # Table B: corpus against mean sentence BLEU-4 under four smoothing rules (baseline set-up)
    print(f"\nB. baseline set-up  {'aggregation and smoothing':51s}{'S1':>8s}{'S2':>8s}{'G':>8s}   ranking")
    stats_base = {n: score(n)[2] for n in caps}; tableB = {}
    for agg in ("corpus", "mean sentence"):
        for sname, fn in SMOOTH.items():
            if agg == "corpus":
                sc = {n: corpus(stats_base[n], fn) for n in caps}
            else:
                sc = {n: float(np.mean([fn(*s) for s in stats_base[n]])) for n in caps}
            lab = f"{agg}, {sname}"; tableB[lab] = sc; rk = ranking(sc)
            flips += [lab] if rk != base_rank else []
            print(f"{'':19s}{lab:52s}" + "".join(f"{sc[n]:8.4f}" for n in caps)
              + f"   {rk:12s}  S2-G {sc['S2'] - sc['G']:+.2e}")
    print("mean sentence - corpus:", "; ".join(
        f"{sname} " + " ".join(f"{n} {tableB['mean sentence, ' + sname][n] - tableB['corpus, ' + sname][n]:+.4f}"
                               for n in caps) for sname in SMOOTH))

    # brevity penalty: corpus BP against the mean of sentence BPs (baseline set-up)
    print("\nBP (baseline): " + "; ".join(
        f"{n} corpus {bp_of(sum(s[2] for s in stats_base[n]), sum(s[3] for s in stats_base[n])):.4f}, "
        f"mean sentence {np.mean([bp_of(s[2], s[3]) for s in stats_base[n]]):.4f}" for n in caps))

    # references: modified precisions p_1..p_4 at 1, 2, 4, 8 references (baseline otherwise)
    print("\nmodified precisions p1..p4 by number of references:")
    for n in caps:
        rows = []
        for k in (1, 2, 4, 8):
            st = score(n, k=k)[2]
            rows.append([sum(s[0][j] for s in st) / sum(s[1][j] for s in st) for j in range(4)])
        mono = all(rows[i + 1][j] >= rows[i][j] for i in range(3) for j in range(4))
        bleu = [tableA[l][n] for l in ("1 reference", "2 references",
                                       "baseline: 4 refs, closest, lowercased, punct split", "8 references")]
        print(f"  {n:3s}" + "  ".join("/".join(f"{p:.3f}" for p in r) for r in rows)
              + f"   precisions non-decreasing {mono}, BLEU non-decreasing {all(b2 >= b1 for b1, b2 in zip(bleu, bleu[1:]))}")
    print(f"\nrows whose ranking differs from the baseline ({base_rank}): {len(flips)} of "
          f"{len(configs) + 2 * len(SMOOTH) - 1}: {flips}")

if __name__ == "__main__":
    run()

images 200, object overlap 0 px, distinct references per image 8, objects read {2: 200}
punctuation check: tokens with punctuation under 'removed' 0; tokens with attached punctuation under 'kept' 2400
S1 colours, shapes and relation correct 200/200; S2 colours and relation correct 200/200
hand vs NLTK, corpus, no candidate under 4 tokens: max diff 4.4e-16
hand vs NLTK, corpus, 48 cases with a candidate under 4 tokens: max diff 5.2e-03; with NLTK's denominator floor: 4.4e-16
hand vs NLTK, sentence level (baseline): max diff 6.7e-16
coco guards vs none, corpus: max relative diff 1.3e-12; 234 sentences score 0 unsmoothed, guarded max 8.0e-05

A. corpus BLEU-4    configuration                                             S1      S2       G   ranking
                   baseline: 4 refs, closest, lowercased, punct split    0.7921  0.3483  0.3483   S1 > S2 > G   S2-G +9.73e-07
                   1 reference                                           0.4447  0.1833  0.2441   S1 > G > S2   S2-G -6.08e-02
                   2 references                                          0.6546  0.2786  0.3038   S1 > G > S2   S2-G -2.52e-02
                   8 references                                          0.8979  0.4528  0.4125   S1 > S2 > G   S2-G +4.03e-02
                   shortest reference length                             0.7921  0.3483  0.3483   S1 > S2 > G   S2-G +9.73e-07
                   average reference length                              0.6551  0.2730  0.3483   S1 > G > S2   S2-G -7.54e-02
                   cased                                                 0.7415  0.3483  0.3063   S1 > S2 > G   S2-G +4.20e-02
                   punctuation kept on words                             0.7311  0.3690  0.3042   S1 > S2 > G   S2-G +6.48e-02
                   punctuation removed                                   0.7606  0.3690  0.3325   S1 > S2 > G   S2-G +3.65e-02
spread (max - min over table A): S1 0.4532, S2 0.2695, G 0.1684

B. baseline set-up  aggregation and smoothing                                S1      S2       G   ranking
                   corpus, none                                          0.7921  0.3483  0.3483   S1 > S2 > G   S2-G +9.73e-07
                   corpus, add-1                                         0.7923  0.3489  0.3487   S1 > S2 > G   S2-G +2.60e-04
                   corpus, exp                                           0.7921  0.3483  0.3483   S1 > S2 > G   S2-G +9.73e-07
                   corpus, coco                                          0.7921  0.3483  0.3483   S1 > S2 > G   S2-G +9.73e-07
                   mean sentence, none                                   0.6503  0.1886  0.2327   S1 > G > S2   S2-G -4.41e-02
                   mean sentence, add-1                                  0.7652  0.4148  0.2962   S1 > S2 > G   S2-G +1.19e-01
                   mean sentence, exp                                    0.7342  0.3388  0.2766   S1 > S2 > G   S2-G +6.22e-02
                   mean sentence, coco                                   0.6504  0.1886  0.2327   S1 > G > S2   S2-G -4.41e-02
mean sentence - corpus: none S1 -0.1418 S2 -0.1598 G -0.1157; add-1 S1 -0.0271 S2 +0.0658 G -0.0524; exp S1 -0.0580 S2 -0.0095 G -0.0718; coco S1 -0.1418 S2 -0.1598 G -0.1157

BP (baseline): S1 corpus 1.0000, mean sentence 0.9630; S2 corpus 0.9152, mean sentence 0.9154; G corpus 1.0000, mean sentence 0.6493

modified precisions p1..p4 by number of references:
  S1 0.889/0.707/0.490/0.295  0.961/0.828/0.649/0.465  0.973/0.885/0.751/0.609  1.000/0.953/0.882/0.773   precisions non-decreasing True, BLEU non-decreasing True
  S2 0.654/0.426/0.159/0.106  0.717/0.512/0.226/0.156  0.731/0.542/0.278/0.191  0.760/0.592/0.370/0.252   precisions non-decreasing True, BLEU non-decreasing True
  G  0.481/0.337/0.211/0.104  0.537/0.391/0.266/0.153  0.586/0.429/0.297/0.197  0.697/0.493/0.339/0.248   precisions non-decreasing True, BLEU non-decreasing True

rows whose ranking differs from the baseline (S1 > S2 > G): 5 of 16: ['1 reference', '2 references', 'average reference length', 'mean sentence, none', 'mean sentence, coco']

The checks held. The determinism check held: two runs printed identical output. The runtime check held: the script runs in about 5 seconds, under the planned minute. The data check held: no overlapping objects, eight distinct references per image, two objects read in each. The punctuation check held: the “removed” rule leaves no token with punctuation, and “kept” leaves 2,400 tokens with punctuation attached. The reading check held: both captioners read every scene correctly (200/200), so S2’s only error is the shapes it leaves out. The NLTK checks held. Against NLTK the hand code agrees to $4.4 \times 10^{-16}$ at corpus level, and to $6.7 \times 10^{-16}$ for every baseline sentence, wherever no candidate is shorter than four tokens. In the 48 cases where one is (G’s truncated captions without punctuation tokens, “a red circle”), the two differ by up to $5.2 \times 10^{-3}$. Applying NLTK’s per-sentence floor of 1 to the hand totals brings the difference back to $4.4 \times 10^{-16}$: NLTK’s corpus score is not Papineni’s corpus sum when a candidate is shorter than $n$. coco-caption’s guards change the corpus score by a relative $1.3 \times 10^{-12}$, and they lift the 234 sentences (of the 600 baseline sentences of the three systems) that score exactly 0 unsmoothed to at most $8.0 \times 10^{-5}$; that check held. The check of the nested-reference derivation held as well: the modified precisions are non-decreasing in the number of references for all three systems.

References. The hypothesis that BLEU rises with the number of references held for all three systems. S1 went from 0.4447 with one reference to 0.8979 with eight. That is the largest effect in Table A, larger than any other single change, as Papineni et al.’s warning about reference counts leads one to expect. The rise was not guaranteed by construction, because the closest reference length moves with the reference set; the printed flags show that BLEU nevertheless rose at every step.

Corpus against sentence. The hypothesis that mean sentence BLEU differs from corpus BLEU and depends on the smoothing held in all twelve system–rule pairs, with differences from −0.1598 to +0.0658. The four mean sentence scores of each system spread by between 0.0635 (G) and 0.2262 (S2), so the dependence on smoothing held for all three systems. A planning script had printed the number of baseline sentences that score 0 unsmoothed before this hypothesis was written, but no BLEU score. Smoothing barely moves the corpus scores: add-1 raises them by less than 0.001, and the guards and exp leave them unchanged at four decimals. No corpus count is zero here, as the nonzero unsmoothed corpus scores show, so exp has nothing to replace. Without smoothing, mean sentence BLEU is 0.12 to 0.16 below corpus BLEU, in part because every sentence lacking a matching 4-gram counts as 0. coco-caption’s guards give almost the same means, since they lift those sentences to at most $8.0 \times 10^{-5}$. Add-1 pushes S2 above its corpus score. In our reading, the reason is that S2 has the lowest 4-gram precision of the three (0.191 at corpus level with four references), and adding one match to each sentence’s small n-gram totals lifts low ratios the most.

The gaming system. The hypothesis that G’s corpus brevity penalty is 1 while its mean sentence penalty is below 1 held: 1.0000 against 0.6493. This was derived before the run (truncated captions have 4 tokens and every reference at least 7, while padding adds more length than truncation removes), and a planning script confirmed the corpus totals before the pilot. It is therefore an illustration of Papineni’s argument, not a test: corpus aggregation forgives short sentences when long ones make up the length, and that freedom can be exploited.

Rankings. Whether any single change reorders the systems was computed, not predicted. S1 is first in every row, while 5 of the 16 rows swap S2 and G:

• one reference, two references and average reference length in Table A;
• mean sentence BLEU without smoothing and with coco-caption’s guards in Table B.

The baseline order itself rests on an S2 − G difference of $+9.73 \times 10^{-7}$, a tie for any practical purpose. In the swapped rows the gap is 0.025 to 0.075 in G’s favour; elsewhere it is up to 0.12 in S2’s favour. The captioner that names no shapes and the one that games its length are ordered by the scoring configuration, not by what they see. Reporting the configuration, as Post asks, is what lets a reader reproduce such a ranking.

The captioners are our rule-based analogues of captioning systems, and the references are templates, so the magnitudes test this set-up and not machine translation or COCO. Changes made during drafting:

• The “punctuation removed” rule was found broken in the pilot. It dropped only tokens with no letter or digit, and every punctuation mark in these texts is attached to a word, so it removed nothing. With the editor’s approval, before the first run, it was repaired to split punctuation off and drop it, and the printed check of both punctuation rules was added. The repair changed the “punctuation removed” row and the largest unfloored NLTK difference. It changed no check or hypothesis outcome.
• The S2 − G column was added after the same pilot, with the editor’s approval, as a print-only change.
• A first attempt at the repeated pilot ran with the repair only, because a scripting error left the new column out; it was not used, and the repeated pilot was run again with both changes. That run is final and is the output shown.
• The NLTK floor was found while planning the checks, so the check that reproduces it was designed with that difference known.

Related Metrics

• ROUGE. Lin (2004) built ROUGE for summarization as a recall-oriented counterpart. ROUGE-N divides the matched n-grams by the total n-grams in the references, so adding references enlarges the denominator. With several references, the score is the maximum over pairwise scores, and the package averages it over jackknifed subsets of $M - 1$ references. ROUGE-L replaces n-grams with the longest common subsequence, combined into an F-measure of LCS recall and precision. Image Captioning gives the β used for captions.
• METEOR, as Elliott and Keller (2014) describe it, aligns candidate and reference unigrams by exact, synonym and stem matches and combines unigram precision and recall with a penalty for fragmented alignments. In their study it correlated best with human judgments of image descriptions.
• CIDEr weights n-grams by inverse document frequency over the references of the evaluated images, and CIDEr-D adds clipping and a Gaussian length penalty; the CIDEr article defines both and describes the code’s version.
• SPICE is described, with its correlation with human judgments, in Image Captioning.
• Word error rate is the speech-recognition metric that Papineni et al. modified for multiple references and word-order variation. Character error rate is its character-level form, which optical character recognition reports.
• Benchmark use. A single captioning or translation benchmark scored with one configuration year after year is open to the selection effects described in benchmark overfitting.