LLM & VLM courseBlog
149Track 6: LLM applications · session 7 of 20

Metrics for text generation: perplexity, BLEU, ROUGE, METEOR, BERTScore, pass@k

When a model writes text, how do we give that text a number? This session builds the classic automatic metrics from scratch: perplexity for the model itself, BLEU and ROUGE for word overlap, METEOR for synonyms and word order, BERTScore for meaning through embeddings, and pass@k for code that must run. For each one you will see what it rewards, where it fails, and how it is computed in real tools.

Time: 3 hours (reading 2 hours, exercises 1 hour)Level: BeginnerBefore this: Session 3 (perplexity) and Sessions 147 to 148 help

What you will learn

  • Why perplexity measures the model, not a generated text, and why low perplexity can mean dull, repetitive text
  • BLEU step by step: clipped n-gram precision, the geometric mean, the brevity penalty, corpus vs sentence level, and smoothing
  • ROUGE-N and ROUGE-L, and how the longest common subsequence is computed with dynamic programming
  • METEOR: matching by exact word, stem and synonym, recall-weighted F-mean, and the fragmentation penalty
  • BERTScore: greedy matching of contextual token embeddings, idf weighting and baseline rescaling
  • pass@k for code, why the simple estimate is biased, and the unbiased estimator with its stable form
  • Which metric to use for which task, and why all of them need a check against human judgment

Why this matters

A classifier is easy to score: the label is right or wrong. A model that writes text is hard to score. There are many good translations of one sentence, many good summaries of one article, and many correct programs for one task. We still need a number, because we compare hundreds of checkpoints, and we cannot ask humans to read them all.

This session builds the classic automatic metrics. Each one turns “how good is this text?” into a number, and each one does it with a different trade-off:

  • Perplexity scores the model on human text. It does not score a generated text at all.
  • BLEU and ROUGE count shared words and word sequences (n-grams) between the output and a human reference.
  • METEOR also accepts word stems and synonyms, and punishes broken word order.
  • BERTScore compares meanings through embeddings, so a paraphrase can score well.
  • pass@k runs code against unit tests: the output either works or it does not.

You will meet these metrics everywhere: BLEU in machine translation papers, ROUGE in every summarization table (session 147), METEOR and CIDEr in image and video captioning (session 192, session 213), and pass@k on code benchmarks such as HumanEval (session 148). Knowing exactly how they are computed lets you read those tables critically and spot the many ways the numbers can mislead.

Two kinds of metric

Before any formula, sort the metrics into two groups:

  • Intrinsic metrics look at the model’s probabilities. Perplexity is the main one. It needs no reference output, only test text.
  • Reference-based metrics compare one generated output \(\hat y\) (the candidate, also called the hypothesis) with one or more human outputs \(y\) (the references). BLEU, ROUGE, METEOR and BERTScore are of this kind.

pass@k is a third kind: an execution-based metric. The “reference” is a set of unit tests, and the candidate is judged by what it does, not by what it looks like. Later, in session 155, we add a fourth kind: asking another LLM to judge the output.

Perplexity: scoring the model, not the text

We met perplexity in session 3 and session 40. A short recap: give the model a human text of \(T\) tokens, take the probability it gave to each true next token, and average the negative log-probabilities. Perplexity is the exponential of that average:

\[ \mathrm{PPL} = \exp\!\left( -\frac{1}{T} \sum_{t=1}^{T} \log p_\theta(x_t \mid x_{\lt t}) \right) \tag{149.1} \]

It is the geometric mean of \(1/p\): a perplexity of 10 means the model was, on average, as unsure as if it picked uniformly among 10 tokens. Because it is “per token”, it depends on the tokenizer. To compare models with different tokenizers, divide the total loss by the number of bytes of text instead, and use base 2:

\[ \mathrm{BPB} = \frac{1}{\ln 2 \cdot N_{\text{bytes}}} \sum_{t=1}^{T} -\ln p_\theta(x_t \mid x_{\lt t}) \tag{149.2} \]
Read the symbols
\(x_t\)
the true token at position \(t\) of the test text
\(p_\theta(x_t \mid x_{\lt t})\)
the probability the model with weights \(\theta\) gave to that token, after seeing all earlier tokens
\(N_{\text{bytes}}\)
the length of the same text in UTF-8 bytes; it does not depend on the tokenizer
BPB
bits per byte: how many bits the model needs, on average, to encode one byte of the text
Worked example: four tokens

The model gives the four true tokens the probabilities 0.5, 0.25, 0.8 and 0.1. The losses are \(0.693, 1.386, 0.223, 2.303\) nats, with mean \(1.151\). So \(\mathrm{PPL} = e^{1.151} = 3.16\) (exactly \(\sqrt{10}\), the geometric mean of \(2, 4, 1.25, 10\)). If the last probability drops from 0.1 to 0.01, the perplexity jumps to 5.62: one confident mistake raises the score of the whole text. If these four tokens cover 18 bytes, \(\mathrm{BPB} = 4.605 / (0.693 \times 18) = 0.369\).

Why perplexity cannot grade a generated text

It is tempting to generate text with model A and score it with model B: “low perplexity under B means fluent text”. This is a trap. The text with the lowest perplexity is usually dull and repetitive: “I don’t know. I don’t know. I don’t know.” Holtzman et al. showed that beam search produces text whose per-token probabilities are much higher than those of human text, and that human text is surprising in a way that maximum-probability decoding is not [Certain]. So:

  • Perplexity on held-out human text is a good metric for the model (lower is better, same tokenizer, same data).
  • Perplexity of a generated text is at best one weak signal of fluency. It must be combined with a diversity measure, or replaced with a distribution-level metric such as MAUVE, which compares the cloud of generated texts with the cloud of human texts in embedding space.

BLEU: clipped n-gram precision

BLEU (Papineni et al., 2002) was built for machine translation. The idea: a good translation shares many words and short word sequences with a human translation. An n-gram is a run of \(n\) consecutive tokens. “the cat sat” has three unigrams (1-grams), two bigrams (“the cat”, “cat sat”) and one trigram.

Step 1: precision, with clipping

For each \(n\) from 1 to 4, BLEU asks: what fraction of the candidate’s n-grams also appear in the reference? That is a precision. But plain precision is easy to cheat. The candidate “the the the the the the the” has 7 unigrams, and every one of them (“the”) is in the reference “the cat is on the mat”, so plain unigram precision is 7/7. BLEU fixes this with clipping: an n-gram can be counted as matched at most as many times as it appears in the reference. “the” appears twice in the reference, so only 2 of the 7 count:

\[ p_n = \frac{\displaystyle\sum_{g \in \text{n-grams}(\hat y)} \min\big(\mathrm{Count}_{\hat y}(g),\ \max_{r} \mathrm{Count}_{y_r}(g)\big)}{\displaystyle\sum_{g \in \text{n-grams}(\hat y)} \mathrm{Count}_{\hat y}(g)} \tag{149.3} \]
Read the symbols
\(g\)
one distinct n-gram of the candidate \(\hat y\)
\(\mathrm{Count}_{\hat y}(g)\)
how many times \(g\) occurs in the candidate
\(\max_r \mathrm{Count}_{y_r}(g)\)
the largest number of times \(g\) occurs in any single reference \(y_r\) (BLEU allows several references)
\(p_n\)
the clipped (or “modified”) n-gram precision, between 0 and 1

Step 2: the brevity penalty

Precision alone rewards short outputs. The candidate “the cat” has \(p_1 = p_2 = 1\): everything it says is in the reference, it just says almost nothing. BLEU has no recall term (with several references, recall is hard to define), so it adds a brevity penalty instead. Let \(c\) be the candidate length and \(r\) the reference length:

\[ \mathrm{BP} = \begin{cases} 1 & \text{if } c \gt r \\ e^{\,1 - r/c} & \text{if } c \le r \end{cases} \tag{149.4} \]

For “the cat”, \(c = 2\) and \(r = 6\), so \(\mathrm{BP} = e^{1-3} = 0.135\). Outputs longer than the reference are not penalized by BP; they are already punished by lower precision.

Step 3: combine with a geometric mean

\[ \mathrm{BLEU} = \mathrm{BP} \cdot \exp\!\left( \sum_{n=1}^{N} w_n \log p_n \right), \qquad N = 4,\ \ w_n = \tfrac14 \tag{149.5} \]

The weighted sum of logs is a geometric mean of \(p_1, \dots, p_4\). Unigram precision checks the words (adequacy); 3- and 4-gram precision check that the words come in a fluent order. A geometric mean has a sharp edge: if any \(p_n = 0\), BLEU is 0. Scores are usually reported times 100.

Worked example: “the cat sat on the mat”

Reference: “the cat is on the mat” (6 tokens). Candidate: “the cat sat on the mat” (6 tokens).

Unigrams: 5 of 6 match (only “sat” is missing), \(p_1 = 5/6\). Bigrams: “the cat”, “on the”, “the mat” match, “cat sat” and “sat on” do not: \(p_2 = 3/5\). Trigrams: only “on the mat”: \(p_3 = 1/4\). 4-grams: none of the 3 match: \(p_4 = 0/3\). \(c = r\), so \(\mathrm{BP} = 1\).

Because \(p_4 = 0\), plain BLEU is 0 for a sentence a human would call nearly perfect. This is why BLEU is defined at the corpus level. Pool the counts of this sentence with “there is a cat on the mat” and the exact copy “the cat is on the mat” (same reference): the pooled precisions are \(16/19, 10/16, 6/13, 3/10\), the lengths are 19 and 18, and corpus BLEU = \(\exp\big(\tfrac14(\ln 0.842 + \ln 0.625 + \ln 0.462 + \ln 0.3)\big) = 51.96\). The mean of the three smoothed sentence scores (below) is 55.26, a different number. Corpus BLEU is not the average of sentence BLEUs.

Sentence-level BLEU needs smoothing

To score single sentences (for example, as a reward or to compare two outputs), we must avoid the zero. Smoothing replaces a zero precision with a small number. SacreBLEU’s default “exp” method replaces the \(k\)-th zero precision with \(1/(2^k \cdot \text{total}_n)\). For our sentence, \(p_4\) becomes \(1/(2 \cdot 3) = 1/6\), and BLEU becomes 37.99. The three sentences above score 37.99, 27.78 and 100. Try your own in Figure 1.

Show matches for
Figure 1. BLEU, ROUGE and METEOR for one candidate against one reference, computed live. Edit either sentence or pick a preset. The chips are the candidate’s n-grams (each chip is the n-gram that starts at that word); green chips match the reference, red ones would match but are clipped.
How to read Figure 1

Start with “near miss”: plain BLEU is 0 because no 4-gram matches, but the smoothed sentence BLEU is 37.99. “Repeat the” shows clipping: 7 chips, only 2 green, 5 red. “Too short” shows the brevity penalty (0.135). “Word salad” has every word right but in a random order: ROUGE-1 is a perfect 1.0, while 2-gram precision is 0 and METEOR’s fragmentation penalty reaches its maximum of 0.5. “Negation” adds one word that reverses the meaning and still scores higher than “near miss” on every metric. Tokens are lower-cased and split on spaces and punctuation; this demo uses single references and no stemming for BLEU and ROUGE.

BLEU in practice: tokenization and SacreBLEU

BLEU counts tokens, so the score depends on how the text is split into tokens, on lower-casing, and on how many references there are. For years, papers reported BLEU numbers that were not comparable for exactly this reason. Post (2018) showed that tokenization choices alone can change BLEU by more than a point, and released SacreBLEU, which takes raw (detokenized) text, applies one fixed tokenizer, and prints a signature such as nrefs:1|case:mixed|eff:no|tok:13a|smooth:exp|version:2.x so readers know exactly what was computed. [Likely] Always report BLEU with its signature.

For languages without spaces (Chinese, Japanese) or with rich word forms (Finnish, Turkish), word-level n-grams work poorly. chrF uses character n-grams and an F-score instead, and is a common companion to BLEU. Learned metrics such as COMET and BLEURT (models trained to predict human ratings) correlate better with human judgment of modern translation systems, and large studies now recommend them over BLEU for deciding between systems. [Likely]

ROUGE: recall for summaries

BLEU asks “is what you said in the reference?” (precision). For summaries, the opposite question matters more: “did you cover what the reference covers?” That is recall, and it is the core of ROUGE (Recall-Oriented Understudy for Gisting Evaluation, Lin 2004).

ROUGE-N

\[ \text{ROUGE-N}_{R} = \frac{\displaystyle\sum_{g \in \text{n-grams}(y)} \min\big(\mathrm{Count}_{\hat y}(g),\ \mathrm{Count}_{y}(g)\big)}{\displaystyle\sum_{g \in \text{n-grams}(y)} \mathrm{Count}_{y}(g)} \tag{149.6} \]

The numerator is the same clipped overlap as in BLEU, but we divide by the number of n-grams in the reference. Modern tools (for example Google’s rouge-score package) report precision, recall and their harmonic mean F1; most papers quote the F1. [Certain] ROUGE-1 measures word coverage; ROUGE-2 adds a little word order.

ROUGE-L: the longest common subsequence

A subsequence keeps the order of words but may skip some. The longest common subsequence (LCS) of two texts is the longest list of words that appears, in the same order, in both. It does not have to be contiguous. For candidate “there is a cat on the mat” and reference “the cat is on the mat”, one LCS is “is on the mat” (length 4). ROUGE-L turns the LCS length into precision, recall and F:

\[ R_{\text{lcs}} = \frac{\mathrm{LCS}(\hat y, y)}{|y|}, \qquad P_{\text{lcs}} = \frac{\mathrm{LCS}(\hat y, y)}{|\hat y|}, \qquad F_{\text{lcs}} = \frac{(1 + \beta^2)\, R_{\text{lcs}} P_{\text{lcs}}}{R_{\text{lcs}} + \beta^2 P_{\text{lcs}}} \tag{149.7} \]
Read the symbols
\(|y|, |\hat y|\)
the number of tokens in the reference and in the candidate
\(\beta\)
how much more recall counts than precision; \(\beta = 1\) gives the usual F1 used by rouge-score

The LCS rewards the right order without demanding fixed-length runs, so it sits between ROUGE-1 (no order) and ROUGE-2 (strict local order). For our pair: LCS = 4, \(P = 4/7\), \(R = 4/6\), \(F_1 = 0.615\). There is also ROUGE-Lsum, which splits the summary into sentences and takes a union of LCS matches per reference sentence; it is the number most summarization papers mean by “ROUGE-L” for multi-sentence summaries. [Likely] The LCS is computed with a classic dynamic program. Step through it in Figure 2.

\[ L[i][j] = \begin{cases} L[i-1][j-1] + 1 & \text{if } \hat y_i = y_j \\ \max\big(L[i-1][j],\ L[i][j-1]\big) & \text{otherwise} \end{cases} \tag{149.8} \]

Here \(L[i][j]\) is the LCS length of the first \(i\) candidate tokens and the first \(j\) reference tokens, with \(L[0][\cdot] = L[\cdot][0] = 0\). The table has \(|\hat y| \times |y|\) cells, so the cost is \(O(|\hat y| \cdot |y|)\): fine for summaries, too slow for whole books.

cell where the two words match (diagonal + 1)backtracked LCS path
Figure 2. The LCS table for candidate “there is a cat on the mat” (rows) and reference “the cat is on the mat” (columns). Each step fills one row with formula (149.8). The last step walks back from the bottom-right corner to recover the subsequence.
How to read Figure 2

Each cell holds the LCS length of the two prefixes that end at that row and column. A green cell is a match: its value is the upper-left neighbour plus one. Other cells copy the larger of the cell above and the cell to the left. The bottom-right value is the LCS length (4). Notice that both “cat on the mat” and “is on the mat” have length 4: an LCS is not unique, but its length is, and ROUGE-L only uses the length.

Algorithm 1: corpus BLEU and ROUGE-L
  1. input: candidates \(\hat y^{(1..M)}\), references \(y^{(1..M)}\), the same tokenizer for both
  2. \(\text{match}[1..4] \leftarrow 0\), \(\text{total}[1..4] \leftarrow 0\), \(c \leftarrow 0\), \(r \leftarrow 0\)
  3. for each pair \((\hat y, y)\): \(c \mathrel{+}= |\hat y|\), \(r \mathrel{+}= |y|\)
  4.   for \(n = 1..4\): \(\text{match}[n] \mathrel{+}= \sum_g \min(\mathrm{Count}_{\hat y}(g), \mathrm{Count}_y(g))\), \(\text{total}[n] \mathrel{+}= \max(0, |\hat y| - n + 1)\) // clipping, formula (149.3)
  5. \(p_n \leftarrow \text{match}[n] / \text{total}[n]\) // pool counts first, divide once
  6. \(\mathrm{BP} \leftarrow 1\) if \(c \gt r\) else \(e^{1 - r/c}\); \(\;\mathrm{BLEU} \leftarrow 100 \cdot \mathrm{BP} \cdot \exp(\tfrac14 \sum_n \log p_n)\) // (149.4), (149.5)
  7. for each pair: fill \(L\) with formula (149.8); \(\ell \leftarrow L[|\hat y|][|y|]\); \(F \leftarrow 2 (\ell/|\hat y|)(\ell/|y|) / (\ell/|\hat y| + \ell/|y|)\)
  8. return BLEU and the mean of the per-pair ROUGE-L F1 values // ROUGE is averaged per pair; BLEU is not

METEOR: stems, synonyms and word order

BLEU and ROUGE only accept exact matches. “a feline sits on the rug” shares only “on the” with “the cat is on the mat”, so it gets a smoothed BLEU of 16.23 and a ROUGE-1 F1 of 0.333. METEOR (Banerjee and Lavie, 2005) was designed to fix three weaknesses of BLEU: no recall, only exact matches, and a weak check of word order.

METEOR first builds an alignment: a one-to-one map between candidate words and reference words. It is built in stages. Stage 1 matches identical words. Stage 2 matches words with the same stem (the word without endings: “sits” and “sit”; the original uses the Porter stemmer). Stage 3 matches synonyms from WordNet (“feline” and “cat”). Among alignments with the most matches, it picks the one with the fewest crossing links. [Certain] With \(m\) matched words, precision is \(P = m / |\hat y|\) and recall is \(R = m / |y|\). They are combined with a harmonic mean that weights recall 9 times more than precision:

\[ F_{\text{mean}} = \frac{10\, P R}{R + 9 P} \tag{149.9} \]

This rewards covering the reference. It does not yet check order: a shuffled sentence would get \(F_{\text{mean}} = 1\). So METEOR groups the matched words into chunks: maximal runs that are adjacent and in the same order in both texts. Few, long chunks mean good order; many short chunks mean the words are scattered:

\[ \text{Pen} = 0.5 \left( \frac{\#\text{chunks}}{m} \right)^{3}, \qquad \mathrm{METEOR} = F_{\text{mean}} \cdot (1 - \text{Pen}) \tag{149.10} \]
Read the symbols
\(m\)
the number of aligned (matched) unigrams
\(\#\text{chunks}\)
how many contiguous, same-order groups the matches form; 1 is the best possible, \(m\) the worst
Pen
the fragmentation penalty; at most 0.5, so METEOR at least halves \(F_{\text{mean}}\) in the worst case
Worked example: METEOR on three candidates

Reference “the cat is on the mat”. “the cat sat on the mat”: 5 exact matches, \(P = R = 5/6\), so \(F_{\text{mean}} = 0.833\). The matches form 2 chunks (“the cat”, “on the mat”), \(\text{Pen} = 0.5 (2/5)^3 = 0.032\), METEOR = \(0.833 \times 0.968 = 0.807\).

“mat the on is cat the” (word salad): all 6 words match, \(F_{\text{mean}} = 1\), but every match is its own chunk: \(\text{Pen} = 0.5 (6/6)^3 = 0.5\), METEOR = 0.5.

“a feline sits on the rug”, with synonyms feline–cat and rug–mat: 4 matches, \(P = R = 4/6\), \(F_{\text{mean}} = 0.667\), 2 chunks, \(\text{Pen} = 0.5 (2/4)^3 = 0.0625\), METEOR = 0.625. Exact-match ROUGE-1 F1 for the same pair is 0.333.

In Figure 1, the “METEOR alignment” view shows the matches: green for exact, orange for synonym matches from a tiny built-in list (the real METEOR uses WordNet and a stemmer). Implementations differ in details (later METEOR versions add paraphrase tables and tuned weights, and NLTK’s version uses its own alignment), so METEOR numbers from different tools are not exactly comparable. [Likely] METEOR is still standard in image and video captioning tables, next to CIDEr.

BERTScore: matching meanings with embeddings

Synonym lists cover only single words, and only the ones in the list. “it is freezing today” and “the weather is cold today” mean nearly the same thing, but they share only “is” and “today”: smoothed BLEU is 14.79 and ROUGE-L F1 is 0.444. BERTScore (Zhang et al., 2019) compares the texts in embedding space instead.

Run both texts through a pretrained encoder (the default for English is RoBERTa-large, using one middle layer [Certain]). Each token gets a contextual embedding: a vector that depends on its neighbours, so “bank” in “river bank” and in “bank account” get different vectors. Normalize all vectors to length 1, so a dot product is a cosine similarity. Then match greedily: each reference token takes its most similar candidate token (recall), and each candidate token takes its most similar reference token (precision):

\[ R_{\text{BERT}} = \frac{1}{|y|} \sum_{y_j \in y} \max_{\hat y_i \in \hat y} \mathbf{y}_j^{\top} \hat{\mathbf{y}}_i, \qquad P_{\text{BERT}} = \frac{1}{|\hat y|} \sum_{\hat y_i \in \hat y} \max_{y_j \in y} \mathbf{y}_j^{\top} \hat{\mathbf{y}}_i, \qquad F_{\text{BERT}} = \frac{2 P R}{P + R} \tag{149.11} \]
Read the symbols
\(\mathbf{y}_j, \hat{\mathbf{y}}_i\)
unit-length contextual embeddings of reference token \(j\) and candidate token \(i\)
\(\mathbf{y}_j^\top \hat{\mathbf{y}}_i\)
their cosine similarity, between −1 and 1 (in practice mostly between 0.3 and 1)
\(\max\)
greedy matching: each token picks its best partner; two tokens may pick the same partner

Two refinements are common. Idf weighting: rare words carry more meaning than “the”, so each token’s term is weighted by its inverse document frequency, \(\mathrm{idf}(w) = -\log \frac{1}{M}\sum_{k=1}^{M} \mathbb{1}[w \in y^{(k)}]\), computed over the \(M\) reference texts. Baseline rescaling: raw scores of a large encoder sit in a narrow band near the top (unrelated sentences can still score around 0.8 with RoBERTa-large [Likely]), so the score \(s\) is mapped linearly with a baseline \(b\) measured on random sentence pairs:

\[ R_{\text{BERT}}^{\text{idf}} = \frac{\sum_{j} \mathrm{idf}(y_j) \max_i \mathbf{y}_j^{\top} \hat{\mathbf{y}}_i}{\sum_{j} \mathrm{idf}(y_j)}, \qquad \hat s = \frac{s - b}{1 - b} \tag{149.12} \]

Rescaling does not change the ranking of outputs; it only spreads the numbers out so people can read them. [Certain]

best match of a candidate token (row max → precision)best match of a reference token (column max → recall)
Figure 3. Greedy matching in BERTScore. Rows are candidate tokens, columns are reference tokens, and each cell is a cosine similarity. The similarities and idf values are made up for teaching; a real encoder gives different numbers. Click any token label to see its best partner.
How to read Figure 3

Precision is the average of the blue-outlined row maxima; recall is the average of the orange-outlined column maxima. “freezing” finds “cold” (0.83) even though the words differ: this is what n-gram metrics cannot do. The reference token “the” has no real partner, and its best similarity (0.62, to “it”) lowers recall. Turn on idf weighting: “the” gets a tiny weight, “freezing”, “cold” and “weather” get large ones, and both scores go up. Rescaling stretches the numbers but keeps their order.

Worked example: the numbers of Figure 3

Row maxima (candidate tokens “it, is, freezing, today”): 0.62, 0.92, 0.83, 0.95, so \(P = 3.32/4 = 0.830\). Column maxima (reference tokens “the, weather, is, cold, today”): 0.62, 0.66, 0.92, 0.83, 0.95, so \(R = 3.98/5 = 0.796\). \(F = 2 \cdot 0.830 \cdot 0.796 / (0.830 + 0.796) = 0.813\). With the toy idf weights, \(P = 0.849\), \(R = 0.805\), \(F = 0.826\). Rescaled with \(b = 0.5\), the plain \(F\) becomes \((0.813 - 0.5)/0.5 = 0.625\).

pass@k: does the code run?

For code, text similarity is the wrong question. Two programs can share almost no tokens and both be correct, or differ by one character (< vs <=) and one be wrong. The Codex paper (Chen et al., 2021) introduced HumanEval: 164 hand-written Python problems, each with a function signature, a docstring and on average 7.7 unit tests. [Certain] A sample is correct if it passes all the tests of its problem.

pass@k is the probability that at least one of \(k\) samples for a problem is correct, averaged over problems. It models a user who looks at \(k\) suggestions, or a system that can run tests and keep any passing sample. If one sample is correct with probability \(p\), then \(\text{pass@}k = 1 - (1 - p)^k\).

Estimating it without bias

The obvious method is: draw exactly \(k\) samples per problem and record whether any is correct. This has high variance. A better method draws \(n \ge k\) samples (the Codex paper used \(n = 200\) for \(k \le 100\) [Certain]), counts the \(c\) correct ones, and asks: if we picked \(k\) of the \(n\) samples at random, without replacement, what is the chance that at least one is correct? The chance that all \(k\) are wrong is the number of ways to pick \(k\) from the \(n - c\) wrong ones, divided by the number of ways to pick \(k\) from all \(n\):

\[ \text{pass@}k = \mathbb{E}_{\text{problems}} \left[ 1 - \frac{\binom{n - c}{k}}{\binom{n}{k}} \right] \tag{149.13} \]

This estimator is unbiased: its expected value equals the true pass@k. The tempting plug-in estimate \(1 - (1 - c/n)^k\) is biased low. The function \(x \mapsto (1 - x)^k\) is convex, so by Jensen’s inequality \(\E[(1 - \hat p)^k] \ge (1 - p)^k\), and the plug-in estimate underestimates pass@k on average. Binomial coefficients like \(\binom{200}{100} \approx 9 \times 10^{58}\) are huge, so the paper computes the ratio as a stable product:

\[ \frac{\binom{n - c}{k}}{\binom{n}{k}} = \prod_{i = n - c + 1}^{n} \left( 1 - \frac{k}{i} \right) \qquad (\text{and } \text{pass@}k = 1 \text{ if } n - c \lt k) \tag{149.14} \]
Read the symbols
\(n\)
samples generated per problem
\(c\)
how many of them pass all unit tests
\(k\)
how many samples the imagined user gets to try; \(k \le n\)
\(\binom{a}{b}\)
“a choose b”, the number of ways to pick \(b\) items from \(a\)
Worked example: \(n = 10\), \(c = 3\)

pass@1 = \(1 - \binom{7}{1}/\binom{10}{1} = 1 - 7/10 = 0.3\), the same as \(c/n\) (for \(k = 1\) both estimators agree). pass@5 = \(1 - \binom{7}{5}/\binom{10}{5} = 1 - 21/252 = 0.917\). The plug-in value is \(1 - 0.7^5 = 0.832\). pass@8 = 1 exactly: with only 7 wrong samples, any 8 must include a correct one.

The bias, measured: suppose the true per-sample success rate is \(p = 0.3\), so true pass@5 = \(1 - 0.7^5 = 0.832\). Averaged over all possible outcomes of \(n = 10\) samples, the unbiased estimator gives 0.832, but the plug-in estimator gives only 0.760.

unbiased estimator (149.13)plug-in \(1-(1-c/n)^k\)
Figure 4. pass@k for one problem as \(k\) grows from 1 to \(n\). The dot marks the chosen \(k\). The unbiased curve reaches exactly 1 at \(k = n - c + 1\); the plug-in curve stays below it.
How to read Figure 4

Set \(n = 200\), \(c = 10\): pass@1 is 0.05, but pass@100 is 0.999. A model that is right 5% of the time looks nearly perfect if it may try 100 times and a test picks the winner. This is why pass@1 and pass@100 tell different stories, and why papers sample pass@1 at a low temperature and pass@100 at a higher one (more diverse samples help when many tries are allowed). [Likely] Now set \(n = k\): this is the “draw exactly k” method, and the result jumps between 0 and 1. Drawing \(n \gg k\) samples is what makes the estimate smooth.

Two remarks on real use. First, pass@k is only as good as the tests: weak tests let wrong programs pass, so later benchmarks add many more tests per problem. [Likely] Second, “at least one of \(k\) passes” assumes someone can tell which one passed. If the user cannot run the tests, pass@1 is the honest number.

Algorithm 2: unbiased pass@k over a benchmark
  1. input: problems with unit tests, model, \(n\), list of \(k\) values (all \(\le n\)), temperature \(\tau\)
  2. for each problem \(q\):
  3.   draw \(n\) samples at temperature \(\tau\); run each one in a sandbox with a time limit // never run model code on the host
  4.   \(c_q \leftarrow\) number of samples that pass all tests
  5.   for each \(k\): if \(n - c_q \lt k\) then \(s_{q,k} \leftarrow 1\) else \(s_{q,k} \leftarrow 1 - \prod_{i=n-c_q+1}^{n} (1 - k/i)\) // (149.14)
  6. return for each \(k\): \(\text{pass@}k = \frac{1}{Q}\sum_q s_{q,k}\) // average over problems, formula (149.13)

All five in code

The code below implements every metric of this session in plain Python and PyTorch, with no metric library. It reproduces the numbers of the worked examples. In real work, use the standard packages (sacrebleu, rouge-score, bert-score, the HumanEval harness) so your numbers match other papers.

import math, collections, torch
import torch.nn.functional as F
torch.manual_seed(0)

# 1) perplexity and bits per byte from logits, formulas (149.1) and (149.2)
V, T = 50, 12
logits = torch.randn(1, T, V)                      # stand-in for model(input_ids).logits
targets = torch.randint(0, V, (1, T))              # the true next tokens
nll = F.cross_entropy(logits.view(-1, V), targets.view(-1))   # mean nats per token
n_bytes = 40                                       # bytes of raw text these 12 tokens cover
print(f"ppl {nll.exp().item():.1f}  bpb {nll.item() * T / (math.log(2) * n_bytes):.3f}")

# 2) corpus BLEU with clipping and brevity penalty, formulas (149.3)-(149.5)
def ngrams(toks, n):
    return collections.Counter(tuple(toks[i:i + n]) for i in range(len(toks) - n + 1))

def corpus_bleu(hyps, refs, N=4):
    match, total, c_len, r_len = [0] * N, [0] * N, 0, 0
    for h, r in zip(hyps, refs):
        h, r = h.split(), r.split()
        c_len, r_len = c_len + len(h), r_len + len(r)
        for n in range(1, N + 1):
            hc, rc = ngrams(h, n), ngrams(r, n)
            match[n - 1] += sum(min(cnt, rc[g]) for g, cnt in hc.items())   # clipping
            total[n - 1] += max(0, len(h) - n + 1)
    if min(match) == 0:
        return 0.0                                  # no smoothing: one empty order kills BLEU
    log_p = sum(math.log(m / t) for m, t in zip(match, total)) / N
    bp = 1.0 if c_len > r_len else math.exp(1 - r_len / c_len)
    return 100 * bp * math.exp(log_p)

ref = "the cat is on the mat"
hyps = ["the cat sat on the mat", "there is a cat on the mat", "the cat is on the mat"]
print(f"corpus BLEU {corpus_bleu(hyps, [ref] * 3):.2f}")          # counts are pooled first
print(f"one sentence {corpus_bleu(hyps[:1], [ref]):.2f}")         # no 4-gram match -> 0

# 3) ROUGE-L F1 from the longest common subsequence, formulas (149.7) and (149.8)
def lcs(a, b):
    L = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            L[i][j] = L[i-1][j-1] + 1 if a[i-1] == b[j-1] else max(L[i-1][j], L[i][j-1])
    return L[-1][-1]

def rouge_l(cand, ref):
    c, r = cand.split(), ref.split()
    l = lcs(c, r)
    p, rec = l / len(c), l / len(r)
    return 0.0 if l == 0 else 2 * p * rec / (p + rec)
print(f"ROUGE-L {rouge_l(hyps[1], ref):.4f}")

# 4) BERTScore-style greedy matching, formulas (149.11) and (149.12)
def bertscore(cand_emb, ref_emb, cand_idf=None, ref_idf=None):
    sim = F.normalize(cand_emb, dim=-1) @ F.normalize(ref_emb, dim=-1).T   # cosine matrix
    best_c, best_r = sim.max(dim=1).values, sim.max(dim=0).values
    wc = torch.ones_like(best_c) if cand_idf is None else cand_idf
    wr = torch.ones_like(best_r) if ref_idf is None else ref_idf
    P, R = (wc * best_c).sum() / wc.sum(), (wr * best_r).sum() / wr.sum()
    return P.item(), R.item(), (2 * P * R / (P + R)).item()
ref_emb = torch.randn(5, 16)                        # stand-in for 5 contextual token vectors
near = ref_emb[[0, 2, 3, 4]] + 0.5 * torch.randn(4, 16)   # a 4-token "paraphrase"
far = torch.randn(4, 16)                            # an unrelated 4-token sentence
print("near P R F", [round(x, 3) for x in bertscore(near, ref_emb)])
print("far  P R F", [round(x, 3) for x in bertscore(far, ref_emb)])

# 5) unbiased pass@k, formula (149.13), in the stable product form (149.14)
def pass_at_k(n, c, k):
    if n - c < k:
        return 1.0
    return 1.0 - torch.prod(1.0 - k / torch.arange(n - c + 1, n + 1, dtype=torch.float64)).item()
print(f"pass@1 {pass_at_k(200, 10, 1):.4f}  pass@10 {pass_at_k(200, 10, 10):.4f}"
      f"  pass@100 {pass_at_k(200, 10, 100):.4f}")

# Output (CPU, PyTorch 2.8):
# ppl 117.1  bpb 2.062
# corpus BLEU 51.96
# one sentence 0.00
# ROUGE-L 0.6154
# near P R F [0.888, 0.699, 0.782]
# far  P R F [0.261, 0.203, 0.228]
# pass@1 0.0500  pass@10 0.4085  pass@100 0.9992

Look at the “near” line: precision is high (every candidate vector has a close partner) but recall is lower, because reference token 1 was dropped from the paraphrase and has no partner. That is exactly how BERTScore notices missing content.

Which metric for which task

No metric is good everywhere. Each was designed for one task and validated by checking how well it correlates with human ratings on that task. The table summarizes the usual choices.

TaskUsual metricsWhy, and the main risk
Language model pretrainingPerplexity, bits per byte on held-out textMeasures the model directly; not comparable across tokenizers or test sets (session 40)
Machine translationSacreBLEU, chrF, COMETBLEU for history and comparability; COMET tracks human ratings better [Likely]
SummarizationROUGE-1/2/L(sum), BERTScore, plus a faithfulness checkRecall of content; blind to factual errors (session 147)
Image and video captioning (MSR-VTT, COCO)BLEU-4, METEOR, ROUGE-L, CIDErMany references per clip; CIDEr weights n-grams by how rare they are across captions [Certain]
Dense video captioning, key-moment descriptionsMETEOR or CIDEr on events matched by time overlapScores text only for events found at the right time [Likely]
Code generationpass@1, pass@k with \(n \gg k\)Functional correctness; only as good as the unit tests
Open-ended chat, Video-RAG answersLLM-as-judge, pairwise human preferenceToo many valid answers for any reference (session 155)
Open-ended generation qualityMAUVE, diversity (distinct-n), human studyCompares distributions of texts, not single outputs

Common mistakes

  • Averaging sentence BLEU and calling it corpus BLEU. Corpus BLEU pools counts first (51.96 in our example, vs 55.26 for the mean of sentence scores).
  • Reporting BLEU without the tokenizer and settings. Use SacreBLEU on detokenized text and print the signature. Never compare numbers computed with different tokenization.
  • Unsmoothed sentence BLEU. It is 0 whenever no 4-gram matches, even for very good short outputs. Use smoothing or chrF for single sentences.
  • Mixing ROUGE implementations. Stemming on or off, ROUGE-L vs ROUGE-Lsum, and F1 vs recall all change the number. State which one you used.
  • Treating a high BERTScore as “correct”. Negations and wrong numbers keep high similarity. Pair it with a faithfulness or fact check.
  • Estimating pass@k with \(1 - (1 - c/n)^k\). It is biased low. Use formula (149.13) in its product form (149.14), with \(n \ge k\), and report \(n\) and the temperature.
  • Using perplexity under another model as a quality score for generated text. Repetitive text wins. Combine it with diversity, or use a distribution metric.
  • Never checking the metric against people. Before trusting a metric on a new task, have humans rate 50 to 100 outputs and check the rank correlation.

Interview questions

Compute BLEU’s n-gram precisions for “the cat sat on the mat” against “the cat is on the mat”. Why is plain BLEU 0?basic
\(p_1 = 5/6\), \(p_2 = 3/5\) (the cat, on the, the mat), \(p_3 = 1/4\) (on the mat), \(p_4 = 0/3\). Lengths are equal, so BP = 1. BLEU is a geometric mean of the four precisions, so a single zero makes it 0. That is why BLEU is defined at corpus level (pooled counts rarely have a zero), and why sentence BLEU needs smoothing; with SacreBLEU’s exp smoothing this sentence scores 37.99.
What does clipping do in BLEU, and why is it needed?basic
Each candidate n-gram is counted as matched at most as many times as it appears in the reference (the maximum over references). Without it, “the the the the the the the” would get unigram precision 7/7 against “the cat is on the mat”. With clipping it gets 2/7, because “the” appears only twice in the reference.
Why does BLEU have a brevity penalty instead of a recall term?core
Precision alone rewards short outputs: “the cat” has perfect 1- and 2-gram precision. Recall would fix this, but BLEU supports several references, and recall against several different references is not well defined (you should not need to cover all of them). So BLEU penalizes candidates shorter than the reference length: \(\mathrm{BP} = e^{1 - r/c}\) when \(c \le r\). Over-long outputs need no penalty because extra words already lower precision.
ROUGE-1 vs ROUGE-2 vs ROUGE-L: what does each capture?core
ROUGE-1 is unigram overlap: word coverage, no order at all (a shuffled summary scores perfectly). ROUGE-2 is bigram overlap: local word order and phrases. ROUGE-L uses the longest common subsequence: global order, but gaps are allowed, so it credits the same ideas in the same order even with words in between. Papers usually report F1 of all three; for multi-sentence summaries, ROUGE-Lsum computes the LCS per sentence.
How is the LCS computed, and what is its cost?core
Dynamic programming: \(L[i][j] = L[i-1][j-1] + 1\) if the \(i\)-th candidate token equals the \(j\)-th reference token, otherwise \(\max(L[i-1][j], L[i][j-1])\), with zeros on the borders. The answer is the bottom-right cell. Time and memory are \(O(|\hat y| \cdot |y|)\); memory can be cut to one row if only the length is needed.
What does METEOR add over BLEU?core
Three things. (1) Recall, weighted 9 times more than precision in \(F_{\text{mean}} = 10PR/(R + 9P)\). (2) Matching beyond exact words: stems and WordNet synonyms. (3) An explicit word-order check: matches are grouped into chunks, and the penalty \(0.5 (\#\text{chunks}/m)^3\) removes up to half the score when the matches are scattered. It correlates better with human judgments at sentence level than BLEU did, which was its goal.
How does BERTScore work, and what are idf weighting and baseline rescaling for?core
Both texts are encoded by a pretrained transformer; each token gets a unit-length contextual embedding. Recall averages, over reference tokens, the best cosine similarity to any candidate token; precision does the same the other way; F is their harmonic mean. Idf weighting makes rare, content-bearing words count more than function words. Baseline rescaling maps raw scores, which sit in a narrow band near the top, with \((s - b)/(1 - b)\) using a baseline from random sentence pairs; it makes numbers readable and does not change rankings.
Derive the unbiased pass@k estimator. Why not use \(1 - (1 - c/n)^k\)?advanced
Generate \(n\) samples, \(c\) correct. Choose \(k\) of them uniformly without replacement; all are wrong with probability \(\binom{n-c}{k}/\binom{n}{k}\), so pass@k = \(1 - \binom{n-c}{k}/\binom{n}{k}\). Its expectation over the random samples equals the true \(1 - (1-p)^k\), so it is unbiased. The plug-in \(1 - (1 - \hat p)^k\) is biased low because \((1 - x)^k\) is convex (Jensen). Example: \(p = 0.3\), \(n = 10\), \(k = 5\): true 0.832, plug-in expectation 0.760. Compute it as \(1 - \prod_{i=n-c+1}^{n}(1 - k/i)\) to avoid huge binomials, and return 1 when \(n - c \lt k\).
Why is perplexity not a good metric for the quality of generated text?core
Perplexity measures how well a model predicts human text. Applied to generated text, it rewards the most predictable text, which is often repetitive and bland; human text has lower probability under the model than beam-search text. It also ignores correctness, instruction following and diversity. Use it on held-out human text to compare models with the same tokenizer (or bits per byte across tokenizers), and use task metrics, distribution metrics such as MAUVE, or judges for generated text.
Your summarization model improved ROUGE-L by 2 points, but users say it got worse. What could be happening?advanced
Several things can raise ROUGE while hurting users: longer summaries (recall goes up), copying more of the source verbatim, more hallucinated but fluent filler that happens to share words, or overfitting to the style of the reference set. Check output length, the share of copied n-grams, and faithfulness with an NLI- or QA-based check; then run a small human or LLM-judge comparison. Also confirm the ROUGE setup (stemming, Lsum vs L) did not change between runs.
Which metrics would you use to evaluate a video captioning model, and why several references?advanced
The standard set is BLEU-4, METEOR, ROUGE-L and CIDEr, computed against many human captions per clip (MSR-VTT has 20 per video). A clip can be described in many valid ways, and more references make overlap metrics fairer, because a good caption is more likely to match one of them. CIDEr weights n-grams by their rarity across the dataset (tf-idf), so it rewards specific content over generic words like “a man is”. For dense captioning of events, scores are computed only on events matched by time overlap. Finally, check a sample with humans or a VLM judge, since all these metrics miss factual errors.

Exercises

  1. A candidate has 12 tokens and the reference has 15. What is the brevity penalty? What if the candidate has 18 tokens?
  2. Compute the LCS length of candidate “a b c d e” and reference “a c e b d”, then ROUGE-L F1.
  3. Average loss on a test set is 2.3 nats per token. What is the perplexity? If the 1,000 test tokens cover 4,000 bytes and the average loss is 2.0 nats, what is the bits per byte?
  4. With \(n = 10\) samples and \(c = 3\) correct, compute pass@1, pass@5 and pass@8 with formula (149.13), and the plug-in value for \(k = 5\).
  5. A candidate has the same words as the reference, all 6 matched, but in an order where no two matches are adjacent. What is METEOR? What is ROUGE-1 F1?
  6. In Figure 1, find a candidate of at most 7 words that keeps a smoothed BLEU above 30 against “the cat is on the mat” but means the opposite. What does this tell you?
Answerscheck
1. \(c \le r\): \(\mathrm{BP} = e^{1 - 15/12} = e^{-0.25} = 0.779\). With 18 tokens, \(c \gt r\), so BP = 1 (the extra words lower precision instead). 2. One LCS is “a c e” (also “a b d”), length 3. \(P = R = 3/5\), so F1 = 0.6. 3. \(e^{2.3} = 9.97\). BPB = \(1000 \times 2.0 / (\ln 2 \times 4000) = 0.721\). 4. pass@1 = 0.3; pass@5 = \(1 - 21/252 = 0.917\); pass@8 = 1, because \(n - c = 7 \lt 8\); plug-in for \(k = 5\): \(1 - 0.7^5 = 0.832\). 5. \(P = R = 1\), so \(F_{\text{mean}} = 1\); 6 chunks for 6 matches gives \(\text{Pen} = 0.5\), METEOR = 0.5. ROUGE-1 F1 = 1.0, since ROUGE-1 ignores order. 6. “the cat is not on the mat” scores 41.11 smoothed BLEU, higher than the correct near miss “the cat sat on the mat” (37.99). Overlap metrics measure shared wording, not meaning or truth.

Key takeaways

  • Perplexity (149.1) and bits per byte (149.2) evaluate a model on human text. They are not quality scores for generated text, where the lowest perplexity often means repetition.
  • BLEU (149.5) is a brevity penalty (149.4) times the geometric mean of clipped n-gram precisions (149.3), defined at corpus level; sentence BLEU needs smoothing. Report it with SacreBLEU and its signature.
  • ROUGE is recall-oriented: ROUGE-N (149.6) counts reference n-grams covered, ROUGE-L (149.7) uses the longest common subsequence, computed by dynamic programming (149.8).
  • METEOR (149.9, 149.10) adds stems, synonyms, recall weighting and a fragmentation penalty for scattered matches. BERTScore (149.11, 149.12) matches contextual embeddings greedily, so paraphrases score well, but negations do too.
  • pass@k (149.13) must be estimated from \(n \ge k\) samples with the unbiased formula, computed in product form (149.14); the plug-in estimate is biased low.
  • Choose the metric by task, check it against human ratings, and add a guard for what it cannot see: facts, tests, or timing.

Key formulas

\[ \mathrm{BLEU} = \mathrm{BP}\,\exp\!\Big(\tfrac14\sum_{n=1}^{4}\log p_n\Big), \quad \mathrm{BP} = \min\!\big(1, e^{1 - r/c}\big) \]
\[ F_{\text{lcs}} = \frac{2 P_{\text{lcs}} R_{\text{lcs}}}{P_{\text{lcs}} + R_{\text{lcs}}}, \quad \mathrm{METEOR} = \frac{10PR}{R + 9P}\Big(1 - 0.5\big(\tfrac{\#\text{chunks}}{m}\big)^3\Big) \]
\[ R_{\text{BERT}} = \frac{1}{|y|}\sum_j \max_i \mathbf{y}_j^\top\hat{\mathbf{y}}_i, \quad \text{pass@}k = 1 - \frac{\binom{n-c}{k}}{\binom{n}{k}}, \quad \mathrm{PPL} = e^{\text{mean NLL}} \]

References for this session

  1. Papineni et al. (2002). BLEU: a Method for Automatic Evaluation of Machine Translation
  2. Lin (2004). ROUGE: A Package for Automatic Evaluation of Summaries
  3. Banerjee & Lavie (2005). METEOR: An Automatic Metric for MT Evaluation with Improved Correlation with Human Judgments
  4. Zhang et al. (2019). BERTScore: Evaluating Text Generation with BERT
  5. Chen et al. (2021). Evaluating Large Language Models Trained on Code
  6. Papineni et al. (2002). BLEU: a Method for Automatic Evaluation of Machine Translation
  7. Lin (2004). ROUGE: A Package for Automatic Evaluation of Summaries
  8. Banerjee & Lavie (2005). METEOR: An Automatic Metric for MT Evaluation with Improved Correlation with Human Judgments
  9. Zhang et al. (2019). BERTScore: Evaluating Text Generation with BERT
  10. Chen et al. (2021). Evaluating Large Language Models Trained on Code
  11. Post (2018). A Call for Clarity in Reporting BLEU Scores
  12. Popović (2015). chrF: character n-gram F-score for automatic MT evaluation
  13. Rei et al. (2020). COMET: A Neural Framework for MT Evaluation
  14. Sellam, Das and Parikh (2020). BLEURT: Learning Robust Metrics for Text Generation
  15. Vedantam, Zitnick and Parikh (2015). CIDEr: Consensus-based Image Description Evaluation
  16. Holtzman et al. (2019). The Curious Case of Neural Text Degeneration
  17. Pillutla et al. (2021). MAUVE: Measuring the Gap Between Neural Text and Human Text using Divergence Frontiers
  18. Liu et al. (2023). G-Eval: NLG Evaluation using GPT-4 with Better Human Alignment