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

Translation, code generation and dialogue

Translation, code generation and dialogue all use one model that writes an output conditioned on an input. They differ in what counts as a correct answer. A translation can be right in many forms. Code is right only if it runs and passes tests. A conversation must stay consistent over many turns. This session shows how each task is modeled, decoded and evaluated, with beam search, pass@k and the token cost of long chats worked out in numbers.

Time: 3 hours (reading 2 hours, exercises 1 hour)Level: BeginnerBefore this: Sessions 9 (chat templates), 24 (encoder–decoders), 78 and 79 (generation and decoding). Session 149 goes deeper into BLEU and pass@k

What you will learn

  • How machine translation is modeled with encoder–decoders (the Transformer, T5) and with decoder-only LLMs through a prompt
  • Why greedy decoding misses good translations, and how beam search with a length penalty fixes this, step by step
  • Why BLEU can give a wrong translation a higher score than a correct one, and what chrF, COMET and human MQM ratings add
  • Execution-based testing for code: unit tests, a sandbox, the unbiased pass@k estimator, and why harder tests change rankings
  • Multi-turn dialogue: how the whole history is sent each turn, why the total cost grows with the square of the number of turns, and how windows, summaries and memory keep it bounded
  • Persona and memory in chat assistants, and why every one of these three tasks is hard to evaluate

Why this matters

Three of the most used LLM products are a translator, a coding assistant and a chat assistant. Inside, all three are the same thing: a model that writes an output one token at a time, conditioned on an input. What makes them different is the answer to one question: what counts as a correct output?

For translation, there are many correct outputs, and a single wrong word ("not" dropped) can flip the meaning. For code, there is a strict test: the program must run and give the right result, so we can check it automatically by executing it. For dialogue, the output must fit not only the last message but the whole conversation, the persona the assistant was given, and facts the user said twenty turns ago. These differences decide how we decode (greedy, beam search, sampling), how we build the input (a prompt, a chat template, a memory), and how we evaluate.

Real systems in this space: Google Translate (whose 2016 neural system, GNMT, made beam search with a length penalty standard), Meta’s NLLB-200 (one model for 200 languages), GitHub Copilot (first powered by descendants of OpenAI’s Codex), and every chat assistant. This session follows session 147, which used the same encoder–decoder and decoding tools for one more task.

One frame for three tasks: conditional generation

In all three tasks we have an input \(x\) (a German sentence, a function description, a conversation so far) and we want an output \(y = (y_1, \dots, y_T)\) (an English sentence, a function body, the next reply). The model gives a probability to each next token, given the input and the tokens it has already written. The probability of the whole output is the product:

\[ p_\theta(y \mid x) = \prod_{t=1}^{T} p_\theta(y_t \mid y_{\lt t},\, x), \qquad \mathcal{L}(\theta) = -\sum_{t=1}^{T} \log p_\theta(y_t \mid y_{\lt t},\, x) \tag{148.1} \]
Read the symbols
\(x\)
the input: source sentence, task description, or the conversation so far
\(y_t\)
the output token at position \(t\); \(y_{\lt t}\) are the tokens before it
\(T\)
the length of the output, including the final end token
\(\mathcal{L}\)
the training loss for one example: cross-entropy on the output tokens only

There are two ways to build such a model. An encoder–decoder reads \(x\) with a bidirectional encoder and writes \(y\) with a decoder that looks at the encoder through cross-attention (session 24). A decoder-only LLM puts \(x\) and \(y\) into one sequence: a prompt, then the answer. It computes the same formula (148.1), but \(x\) is part of the text it reads from left to right, and during fine-tuning the loss is masked so that only the tokens of \(y\) count:

\[ \mathcal{L}(\theta) = -\sum_{i=1}^{|s|} m_i \log p_\theta(s_i \mid s_{\lt i}), \qquad s = [\,\text{prompt}(x);\ y\,], \quad m_i = \begin{cases} 1 & s_i \in y \\ 0 & \text{otherwise} \end{cases} \tag{148.2} \]
Read the symbols
\(s\)
one token sequence: the prompt built from \(x\) (with instructions and template tokens), followed by \(y\)
\(m_i\)
the loss mask: 1 on output tokens, 0 on prompt tokens (the model is not trained to write the prompt)

Machine translation

Encoder–decoders: the original home of the Transformer

Machine translation (MT) is the task the Transformer was invented for. The 2017 paper trained an encoder–decoder on the WMT 2014 English–German and English–French news data and reported 28.4 BLEU on English–German. [Certain] Before it, RNN encoder–decoders with attention (Bahdanau et al.) did the same job more slowly. The data is parallel text: pairs of sentences that say the same thing in two languages.

T5 showed that translation can be one task among many in a text-to-text model: the input is the string translate English to German: That is good. and the target is Das ist gut. [Certain] The task prefix is plain text, so the same weights also summarize and classify. A useful lesson from T5: it did not reach the best published translation scores, and the authors say this may be partly because its pretraining data (C4) was English only, while the best systems used back-translation. [Certain]

Back-translation (Sennrich et al., 2016) turns monolingual text into extra training pairs: take real sentences in the target language, translate them into the source language with a reverse model, and train on (synthetic source, real target). The target side, which the model must learn to write, is always real human text. This matters most for low-resource languages, where parallel text is rare. NLLB-200 used such methods, plus large mined parallel data, to cover 200 languages in one model, and reported a 44% relative BLEU gain over the previous best on its benchmark. [Certain]

Decoding: why greedy is not enough

To translate, we want the most likely output \(\hat y = \argmax_y p(y \mid x)\). We cannot try every sentence: with a vocabulary of 32,000 tokens there are \(32{,}000^{T}\) sequences of length \(T\). Greedy decoding picks the most likely token at each step. It is fast but short-sighted: a good first word can lead to a bad sentence, and a slightly less likely first word can lead to a much better one.

Beam search keeps the \(k\) best partial outputs (the beam) at every step. Each step, it extends every beam entry by every possible next token, scores all candidates by their total log-probability, and keeps the best \(k\). A candidate that ends with the end token is moved to a list of finished outputs. At the end, it picks the best finished output.

One more problem: every extra token multiplies the probability by a number below 1, so shorter outputs always have higher probability. Pure beam search therefore likes translations that stop early and drop part of the source. The fix is a length penalty: divide the log-probability by a power of the length.

\[ \text{score}(y) = \frac{\log p_\theta(y \mid x)}{|y|^{\alpha}}, \qquad \hat y = \argmax_{y \,\in\, \text{finished}} \ \text{score}(y) \tag{148.3} \]
Read the symbols
\(|y|\)
the number of tokens in the output, here including the final period, which works as the end token
\(\alpha\)
the strength of the length penalty: 0 means no correction (raw probability), 1 means average log-probability per token
finished
the outputs that beam search completed with an end token

This is the form used by Hugging Face generate (its length_penalty argument is \(\alpha\)). GNMT used a smoothed version, \(\big((5 + |y|)/6\big)^{\alpha}\), and also a coverage penalty that rewards outputs that attend to every source word. [Certain] Try it on a toy model in Figure 1.

Beam width \(k\)
kept in the beamfinished (ends with the period)dropped
Figure 1. Beam search for the German source “Das Haus ist klein .” (“The house is small .”) with a hand-made toy model. Each column is one decoding step. Every candidate shows its total probability \(p(y_{\le t} \mid x)\). The last step ranks the finished outputs by formula (148.3); each bar has length \(e^{\text{score}}\), so the longest bar wins.
How to read Figure 1

Start with \(k = 1\): greedy takes “The” (0.5), then “home” (0.45), and ends with “The home is little .”, probability 0.0702. Switch to \(k = 3\) with \(\alpha = 0\): beam search now finds outputs with higher probability, but the winner is “A house .” (0.12), which drops “klein”. Move \(\alpha\) to 1: the full translation “The house is small .” wins. With \(k = 2\) the correct output was dropped at step 3, so no length penalty can bring it back.

Worked example: the numbers in Figure 1

Greedy: \(0.5 \times 0.45 \times 0.6 \times 0.52 \times 1 = 0.0702\), so \(\log p = -2.656\).

Beam with \(k = 3\) finishes four outputs. The two that matter: “A house .” with \(p = 0.3 \times 0.8 \times 0.5 = 0.12\) (\(\log p = -2.120\), 3 tokens), and “The house is small .” with \(p = 0.5 \times 0.4 \times 0.55 \times 0.85 = 0.0935\) (\(\log p = -2.370\), 5 tokens).

With \(\alpha = 0\) the scores are the raw log-probabilities, and \(-2.120 \gt -2.370\): the short, wrong output wins. With \(\alpha = 1\): \(-2.120/3 = -0.707\) and \(-2.370/5 = -0.474\), so the full translation wins. The two scores are equal when \(2.120 \cdot 5^{\alpha} = 2.370 \cdot 3^{\alpha}\), that is \(\alpha = \ln(2.370/2.120) / \ln(5/3) = 0.218\). Above that, the correct translation wins.

Algorithm 1: beam search with a length penalty
  1. input: source \(x\), beam width \(k\), length penalty \(\alpha\), maximum length \(L\)
  2. alive \(\leftarrow\) [(empty output, log-prob 0)]; finished \(\leftarrow\) [ ]
  3. for \(t = 1, \dots, L\) while alive is not empty:
  4.   candidates \(\leftarrow\) every \((y + w,\ \ell + \log p(w \mid y, x))\) for each \((y, \ell)\) in alive and each token \(w\) // in practice only the top \(k\) tokens per entry
  5.   sort candidates by log-prob, best first; alive \(\leftarrow\) [ ]
  6.   for each candidate, in order, until alive has \(k\) entries: if it ends with the end token, add it to finished; else add it to alive
  7. return the finished output with the best \(\log p / |y|^{\alpha}\) // formula (148.3)

Translation with decoder-only LLMs

A general LLM translates with a prompt such as “Translate the following German text into English. Keep the formatting.” followed by the text. Nothing in its architecture is special for translation: it learned from the multilingual text in its pretraining data and from translation examples in its instruction data. Compared with a dedicated encoder–decoder, an LLM brings:

  • Document context. It can translate a whole document, so pronouns, terms and formal vs informal “you” stay consistent across sentences. Classic MT systems translated one sentence at a time.
  • Control by instruction. “Use this glossary”, “keep the HTML tags”, “use British spelling”, or a few example pairs in the prompt (session 143).
  • Weaknesses. Quality falls for low-resource languages, where pretraining saw little text, and those languages also cost more tokens per sentence (session 9). [Likely] LLMs can also answer instead of translate (when the source is a question), add explanations, or write in the wrong language (“off-target” output). [Likely]

Beam search is still common for dedicated MT models. For chat LLMs, translation is usually done with greedy decoding or low-temperature sampling, because beam search is expensive with long outputs and large models. [Likely]

Evaluating translation: why it is hard

A German sentence has many correct English translations. The standard automatic metric, BLEU (Papineni et al., 2002), compares the output with one or more human reference translations by counting shared word sequences (n-grams):

\[ \text{BLEU} = \text{BP} \cdot \exp\!\Big( \tfrac14 \sum_{n=1}^{4} \log p_n \Big), \qquad p_n = \frac{\sum_{g \,\in\, \text{n-grams}(y)} \min\!\big(\text{count}_y(g),\ \max_{r} \text{count}_{r}(g)\big)}{\text{number of n-grams in } y}, \qquad \text{BP} = \min\!\big(1,\ e^{\,1 - \rho/c}\big) \tag{148.4} \]
Read the symbols
\(p_n\)
clipped n-gram precision: the share of the output’s n-grams that also appear in a reference, each counted at most as often as in the reference that has it most
\(r\)
one of the reference translations
BP
brevity penalty: below 1 when the output length \(c\) is shorter than the reference length \(\rho\) (the closest reference length)

Real BLEU is computed over a whole test set (corpus level), not per sentence, and tools such as SacreBLEU fix the tokenization so scores are comparable. Session 149 covers the details. Here we only look at its blind spot. In Figure 2, click each candidate.

meaning correct (a human would accept it)meaning wrong or incomplete
Figure 2. Sentence-level BLEU (formula 148.4, no smoothing) for six English candidates for “Die Katze sitzt nicht auf der Matte.” Two references: “the cat is not sitting on the mat” and “the cat does not sit on the mat”. Click a row to see its n-gram counts.
How to read Figure 2

The wrong-animal translation (“the dog …”) scores 0.707, higher than the correct “the cat is not on the mat” at 0.515. The candidate that drops “not” and says the opposite of the source scores exactly the same 0.515. The correct paraphrase “there is no cat on the mat” scores 0, because it shares no 4-gram with either reference, and one zero precision makes the geometric mean zero. BLEU counts surface overlap; it does not read meaning.

Better metrics exist. chrF counts character n-grams instead of words, so it gives partial credit for word forms (“sitzt” vs “sitzen”), which matters for languages with rich morphology. COMET is a neural model trained to predict human quality scores from the source, the output and the reference; it rewards correct paraphrases. The most trusted signal is human rating with MQM (Multidimensional Quality Metrics): trained translators mark each error with a type (accuracy, fluency, terminology…) and a severity. Freitag et al. (2021) found that such expert ratings can rank systems quite differently from crowd ratings, and that learned metrics agree with experts better than BLEU does. [Likely]

Code generation: let the computer check the answer

Code has a property that translation lacks: we can run it. Codex (Chen et al., 2021) is a GPT model fine-tuned on public GitHub code. To evaluate it, the authors wrote HumanEval: 164 hand-written Python problems, each a function signature with a docstring, with on average 7.7 unit tests per problem. [Certain] A generated function counts as correct only if it passes all the tests. This is functional correctness, and it replaces the question “does it look like the reference?” with “does it work?”.

The Codex paper also showed why a text metric fails here: functionally wrong programs often had higher BLEU scores than correct ones. [Certain] Two programs can share almost all tokens and differ by one < vs <=; two correct programs can share almost nothing.

Running untrusted code safely

Generated code is untrusted: it can delete files, open network connections, or loop forever. The evaluation harness runs each sample in a separate process with a time limit, inside a sandbox that blocks the network and the host file system. Codex used the gVisor container runtime for this. [Certain] A sample that times out, crashes, or fails any assertion counts as wrong.

pass@k

Code models are often used with sampling: generate several programs and keep one that passes the tests. pass@k is the probability that at least one of \(k\) samples passes. Computing it by drawing exactly \(k\) samples per problem has high variance. Instead, the Codex paper draws \(n \ge k\) samples (they used \(n = 200\)), counts the \(c\) correct ones, and uses an unbiased estimator: one minus the chance that a random subset of \(k\) of the \(n\) samples contains no correct one. [Certain]

\[ \text{pass@}k = \E_{\text{problems}}\left[ 1 - \frac{\binom{n - c}{k}}{\binom{n}{k}} \right] \tag{148.5} \]
Read the symbols
\(n\)
samples generated for one problem
\(c\)
how many of them pass all tests
\(\binom{n-c}{k} / \binom{n}{k}\)
the probability that \(k\) samples, drawn without replacement from the \(n\), are all wrong
\(\E_{\text{problems}}\)
the average over all problems in the benchmark

The binomials become huge (\(\binom{200}{100}\) has 59 digits), so we compute the ratio as a product of small terms, as in the paper’s code:

\[ \frac{\binom{n - c}{k}}{\binom{n}{k}} = \prod_{i = n - c + 1}^{n} \left( 1 - \frac{k}{i} \right) \quad (\text{and pass@}k = 1 \text{ if } n - c \lt k) \tag{148.6} \]

Why not just use \(1 - (1 - \hat p)^k\) with \(\hat p = c/n\)? That formula treats the samples as drawn with replacement from an infinite pool, and because \(1 - (1-p)^k\) is a concave function of \(p\), plugging in a noisy estimate \(\hat p\) gives a biased answer on average. The Codex paper proves this in its appendix. [Certain] Compare the two in Figure 3.

unbiased estimator (148.5)naive \(1 - (1 - c/n)^k\)
Figure 3. pass@k for one problem with \(n\) samples of which \(c\) pass. The curve shows every \(k\) from 1 to \(n\); the dot marks the chosen \(k\). The benchmark score is the average of this number over all problems.
How to read Figure 3

With \(n = 200\) and \(c = 10\), pass@1 is exactly \(c/n = 0.05\) for both formulas. They separate as \(k\) grows: at \(k = 100\) the unbiased value is 0.9992 and the naive one 0.9941. Now set \(n = 10\), \(c = 3\), \(k = 5\): unbiased 0.917, naive 0.832. When \(k\) reaches \(n - c + 1\), the unbiased estimator is exactly 1, because any \(k\) samples must include a correct one.

Worked example: pass@k by hand

One problem, \(n = 10\) samples, \(c = 3\) pass. For \(k = 5\): \(\binom{7}{5} = 21\) and \(\binom{10}{5} = 252\), so pass@5 \(= 1 - 21/252 = 0.917\). The naive estimate \(1 - 0.7^5 = 0.832\) is quite different.

A benchmark with three problems, each with \(n = 10\) samples and \(c = 0, 5, 10\) correct: pass@1 is the mean of \(0, 0.5, 1\), which is \(0.5\). pass@5 is the mean of \(0,\ 1 - 1/252 = 0.996,\ 1\), which is \(0.665\). Sampling more helps only on problems where the model is sometimes right.

Real numbers from the Codex paper (Table 1, HumanEval): Codex-12B reached pass@1 = 28.8%, pass@10 = 46.8% and pass@100 = 72.3%; GPT-J 6B reached 11.6%, 15.7% and 27.7%. The best sampling temperature was 0.2 for pass@1 and 0.8 for pass@100. [Certain] Low temperature makes the single best guess more likely; high temperature makes the \(k\) samples more different, so at least one is more likely to be right. Choosing among many samples needs a judge: with tests that the user provides, the system can pick a passing one. Without tests, Codex picked the sample with the highest mean log-probability, which solved 44.5% of problems with 100 samples, versus 77.5% for an oracle that uses the hidden tests. [Certain]

Algorithm 2: execution-based evaluation of a code model
  1. input: problems (prompt, hidden tests), model, \(n\), temperature \(\tau\), time limit
  2. for each problem:
  3.   draw \(n\) completions from the model at temperature \(\tau\); stop each at the end of the function
  4.   for each completion: run prompt + completion + tests in a fresh sandboxed process with the time limit; pass = (exit code 0)
  5.   \(c \leftarrow\) number of passing completions; compute pass@k with formula (148.6)
  6. return the mean of pass@k over problems // report \(n\), \(\tau\) and the test suite version too

Why code evaluation is still hard

  • Weak tests. 7.7 tests per problem miss many wrong programs. EvalPlus extended the HumanEval tests 80 times (HumanEval+), and the pass@k of 26 LLMs dropped by 19.3% to 28.9%. [Certain]
  • Contamination. HumanEval and MBPP (974 short Python problems, Austin et al.) are on the public web, so newer models may have seen them in training. LiveCodeBench collects new contest problems over time and evaluates each model only on problems published after its training cut-off. [Certain]
  • Toy vs real tasks. Writing one function is far from real software work. SWE-bench gives 2,294 real GitHub issues from 12 Python repositories; the model must edit the repository so that the project’s own tests pass. [Certain] This turns code generation into an agent task (session 154).
  • Correct is not enough. Tests do not check readability, security, or speed. A passing solution can still contain an injection bug or run in quadratic time.

Dialogue: many turns, one context

How a conversation reaches the model

An LLM has no memory between calls. A chat assistant works because, at every turn, the whole conversation so far is rendered with the model’s chat template into one token sequence and sent again: system message, then each user and assistant message with role tokens around it, then the start of a new assistant message (the “generation prompt”). Session 9 shows real templates. A simplified one:

<|system|> You are Mina, a friendly travel guide. Answer in short sentences.<|end|> <|user|> I land in Lisbon on Friday. What should I see first?<|end|> <|assistant|> Start with the Alfama district and the castle.<|end|> <|user|> And on Saturday?<|end|> <|assistant|>

“And on Saturday?” means nothing alone. The model can answer only because turn 1 is still in the input. This is why dialogue is hard: the reply depends on a context that keeps growing.

Suppose the system prompt has \(s\) tokens, each user message \(u\) tokens, and each assistant reply \(a\) tokens (template tokens included). Before the model writes reply \(t\), its input holds the system prompt, \(t\) user messages and \(t - 1\) replies:

\[ n_t = s + t\,u + (t - 1)\,a \tag{148.7} \]

Without any caching, each turn processes its whole input again, so over \(T\) turns the total number of prompt tokens is

\[ \sum_{t=1}^{T} n_t = T s + u\,\frac{T(T+1)}{2} + a\,\frac{T(T-1)}{2} \tag{148.8} \]
Read the symbols
\(n_t\)
input (prompt) tokens at turn \(t\); it grows linearly with \(t\)
\(T\)
number of turns in the conversation
\(\sum n_t\)
total prompt tokens processed; it grows with \(T^2\)

Two ways out. Prefix caching keeps the KV cache of the conversation between turns, so only new tokens are processed (session 134). And when \(n_t\) plus the reply would exceed the context window \(C\), something must be removed. The common memory strategies:

  • Sliding window: keep the system prompt and only the last \(W\) turns. Simple, but the assistant forgets the user’s name from turn 1.
  • Summary + window: keep a running summary of the dropped turns (written by the model itself, at the cost of an extra call now and then) plus the last \(W\) turns.
  • Long-term memory: store facts (“the user is vegetarian”) or old turns outside the prompt and retrieve the relevant ones each turn, as in retrieval-augmented generation. MemGPT treats the context window like main memory and an external store like disk, and lets the model move information between them with function calls. [Certain]

Always keep the system prompt: it holds the rules and the persona. Figure 4 shows what each strategy does to the input size.

prompt fitsprompt plus a 512-token reply does not fitsummary tokens
Figure 4. Input tokens \(n_t\) at each turn of a conversation (formula 148.7), with 512 tokens reserved for the reply. The dashed line is the context window. The summary is fixed at 300 tokens once old turns have been dropped.
How to read Figure 4

With the defaults (500-token system prompt, 50-token questions, 250-token answers, 8K window), full history fits until turn 24; turn 25 needs 7,750 + 512 tokens and overflows. At turn 40 the input would be 12,250 tokens, and the 40 turns together process 256,000 prompt tokens without caching. The sliding window stays flat at 2,350 tokens, but at turn 40 the model can see only turns 34 to 40.

Worked example: the cost of a 40-turn chat

With \(s = 500\), \(u = 50\), \(a = 250\) and \(T = 40\): the last input is \(n_{40} = 500 + 40 \cdot 50 + 39 \cdot 250 = 12{,}250\) tokens. The total over all turns, formula (148.8), is \(40 \cdot 500 + 50 \cdot 820 + 250 \cdot 780 = 20{,}000 + 41{,}000 + 195{,}000 = 256{,}000\) tokens.

With prefix caching, each turn processes only its new tokens, and the total equals the final input length, 12,250: about 21 times less prefill work. (Attention still reads the whole cached history at every step, so long chats stay more expensive per token.)

The context window limits the turns with full history: the largest \(t\) with \(n_t + 512 \le C\) is 24 for \(C = 8{,}192\), 106 for 32,768 and 434 for 131,072.

Algorithm 3: one turn of a chat assistant with memory
  1. input: system prompt (rules + persona), stored history, long-term memory store, new user message, budget \(C\), reply reserve \(r\)
  2. facts \(\leftarrow\) retrieve from the memory store the items most related to the new message
  3. messages \(\leftarrow\) [system + facts] + history + [new message]
  4. while \(\text{tokens}(\text{render}(\text{messages})) + r \gt C\): drop the oldest user–assistant pair (never the system message); optionally fold it into a summary
  5. reply \(\leftarrow\) generate from render(messages) with the generation prompt, up to \(r\) tokens
  6. append (new message, reply) to history; extract new facts (“user lives in Porto”) and write them to the memory store
  7. return reply

Persona and consistency

A persona is the character the assistant plays: a name, a tone, things it knows about itself. In modern assistants it is written into the system prompt. Before chat LLMs, the PersonaChat dataset (Zhang et al., 2018) gave each speaker a short profile of facts (“I have a dog”) and trained models to stay in character; conditioning on the profile made the dialogue more engaging. [Certain] Today the same problems appear in new forms: the assistant forgets its instructions after many turns, contradicts what it said earlier, or loses a fact placed in the middle of a long context (“lost in the middle”, Liu et al.). [Likely] Fine-tuning data for chat models therefore contains multi-turn conversations, and the loss of formula (148.2) is applied to every assistant turn, not only the last one (session 54).

What makes each task hard to evaluate

TranslationCode generationDialogue
How many correct outputs?Many: paraphrases, word order, registerMany programs, but correctness is checkableVery many; depends on the whole history and on user taste
Automatic metricBLEU, chrF (overlap); COMET (learned)pass@k from unit tests in a sandboxWeak: no reference reply fits; LLM-as-a-judge is common
Gold standardExpert MQM error annotationStrong hidden tests, real repositories (SWE-bench)Human preference between two replies (Chatbot Arena)
Typical failure the metric missesDropped negation, wrong entity, omitted clauseBugs not covered by the tests, insecure codeForgetting earlier facts, inconsistent persona, flattery
Contamination riskMedium (public test sets)High (HumanEval, MBPP online)High for fixed question sets

For dialogue, there is no single right answer, so most evaluation compares replies. MT-Bench asks a strong LLM to grade answers to 80 multi-turn questions, and Chatbot Arena collects human votes between two anonymous models; Zheng et al. found that a GPT-4 judge agreed with humans about as often as humans agreed with each other, but also showed position bias, length bias and self-preference in judges. [Certain] Session 155 goes deeper.

In code: beam search, a test harness and a chat budget

The script below is deterministic and runs on a CPU in under a second. Part 1 is Algorithm 1 on the toy model of Figure 1. Part 2 runs four generated programs against hidden tests in separate processes with a time limit (Algorithm 2) and computes pass@k with formula (148.6). Part 3 renders a chat with a template and keeps the newest messages that fit a budget (step 4 of Algorithm 3).

import math, subprocess, sys, torch

# ---- 1) beam search with a length penalty, formula (148.3) ----
# A toy "translation model" for the source "Das Haus ist klein .": next-token probabilities per prefix.
P = {"": {"The": .5, "A": .3, "It": .2},
     "The": {"home": .45, "house": .4, "building": .15}, "A": {"house": .8, "home": .2}, "It": {"is": .9, "was": .1},
     "The home": {"is": .6, ".": .4}, "The house": {"is": .55, ".": .45}, "The building": {"is": 1.0},
     "A house": {".": .5, "is": .5}, "A home": {"is": 1.0}, "It is": {"small": .6, "little": .4},
     "The home is": {"little": .52, "small": .48}, "The house is": {"small": .85, "little": .15},
     "The building is": {"small": 1.0}, "A house is": {"small": .6, "little": .4}, "A home is": {"small": 1.0}}
def next_logprobs(prefix):                       # a real model would run the decoder here
    d = P.get(prefix, {".": 1.0})
    return list(d), torch.log(torch.tensor(list(d.values())))

def beam_search(k, alpha, max_len=6):
    alive, done = [("", 0.0)], []
    for _ in range(max_len):
        cand = []
        for prefix, lp in alive:
            words, logp = next_logprobs(prefix)
            cand += [((prefix + " " + w).strip(), lp + logp[i].item()) for i, w in enumerate(words)]
        cand.sort(key=lambda h: -h[1])
        alive = []
        for h in cand:                           # finished hypotheses leave the beam
            (done if h[0].endswith(".") else alive).append(h)
            if len(alive) == k: break
        if not alive: break
    score = lambda h: h[1] / len(h[0].split()) ** alpha
    best = max(done, key=score)
    return best[0], round(math.exp(best[1]), 4), round(score(best), 3)

for k, alpha in [(1, 0.0), (3, 0.0), (3, 1.0)]:
    print(k, alpha, beam_search(k, alpha))
# 1 0.0 ('The home is little .', 0.0702, -2.656)   greedy
# 3 0.0 ('A house .', 0.12, -2.12)                 too short: "klein" is lost
# 3 1.0 ('The house is small .', 0.0935, -0.474)   the full translation

# ---- 2) execution-based testing and pass@k, formulas (148.5) and (148.6) ----
tests = "assert f('Abba') is True\nassert f('a b a') is True\nassert f('abc') is False\n"
samples = ["def f(s):\n    t = s.lower().replace(' ', '')\n    return t == t[::-1]\n",   # correct
           "def f(s):\n    return s == s[::-1]\n",                                       # ignores case
           "def f(s):\n    while True: pass\n",                                          # never ends
           "def f(s)\n    return True\n"]                                                # syntax error
def passes(code, timeout=2.0):
    try:   # a separate process with a time limit; real systems add a sandbox (no network, no files)
        r = subprocess.run([sys.executable, "-I", "-c", code + tests], capture_output=True, timeout=timeout)
        return r.returncode == 0
    except subprocess.TimeoutExpired:
        return False
results = [passes(s) for s in samples]
print(results)                                   # [True, False, False, False]

def pass_at_k(n, c, k):                          # the stable product form from the Codex paper
    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()
n, c = len(results), sum(results)
print([round(pass_at_k(n, c, k), 4) for k in (1, 2, 3)])        # [0.25, 0.5, 0.75]
print(round(pass_at_k(10, 3, 5), 4), round(1 - (1 - 0.3) ** 5, 4))  # 0.9167 0.8319

# ---- 3) multi-turn dialogue: render a chat and keep it inside a token budget ----
def render(msgs):
    return "".join(f"<|{m['role']}|>\n{m['content']}<|end|>\n" for m in msgs) + "<|assistant|>\n"
def n_tokens(text): return len(text.split())   # stand-in for a real tokenizer
def fit(system, turns, budget):
    """Keep the system prompt and the newest messages that fit; drop the oldest first."""
    kept = []
    for m in reversed(turns):
        if n_tokens(render([system] + [m] + kept)) > budget: break
        kept.insert(0, m)
    return [system] + kept
system = {"role": "system", "content": "You are Mina, a friendly travel guide. Answer in short sentences."}
turns = []
for i in range(1, 6):
    turns += [{"role": "user", "content": f"question {i} " + "word " * 8},
              {"role": "assistant", "content": f"answer {i} " + "word " * 20}]
kept = fit(system, turns[:-1], budget=80)        # the last user message is new; the reply is not written yet
print(len(turns[:-1]), len(kept) - 1, [m["content"].split()[:2] for m in kept[1:]])
# 9 3 [['question', '4'], ['answer', '4'], ['question', '5']]
print(n_tokens(render(kept)))                    # 61: adding "answer 3" would pass the budget of 80

In a real system, part 1 is model.generate(num_beams=k, length_penalty=alpha), part 2 runs inside a container with no network, and part 3 uses tokenizer.apply_chat_template and the real tokenizer to count tokens. Note that fit drops single messages; production code usually drops whole user–assistant pairs, so the kept history never starts with an assistant reply.

Where this is used

ApplicationModel and decodingHow it is checked
Web and document translationDedicated encoder–decoders (NLLB-style) with beam search, or LLMs with document contextCOMET or chrF on test sets, MQM reviews by translators
Video subtitles and dubbing scriptsSpeech recognition (for example Whisper), then MT with timing and line-length limitsHuman review; reading-speed limits per subtitle line
Code completion in the editorSmall, fast code LLM; greedy or low temperature; fill-in-the-middle promptsAcceptance rate of suggestions; pass@1 offline
Coding agents (fix an issue, write a feature)Large LLM in a loop with tools: read files, edit, run testsSWE-bench-style: the repository’s own tests must pass
Chat assistants and customer supportChat-tuned LLM, sampling, system prompt with persona and rules, memoryHuman preference, LLM-as-a-judge, task success rate
Video question answering in many turnsVideo-LLM: the video tokens stay in the context and the user asks follow-ups (“and what happens after the goal?”) (session 210)Accuracy on video QA benchmarks; consistency across turns
Multilingual video retrieval and key-moment searchTranslate queries or captions to one language, or use a multilingual embedding modelRetrieval recall per language

Common mistakes

  • Beam search without a length penalty. Outputs become too short and drop parts of the source (Figure 1, \(\alpha = 0\)). Always check the length ratio of outputs vs references.
  • Comparing BLEU across different tokenizations or test sets. BLEU depends on tokenization and on the references. Use SacreBLEU with its signature, and compare only on the same data.
  • Trusting sentence-level BLEU. One zero n-gram precision makes it 0 (Figure 2). It is meant for corpus-level comparison.
  • Estimating pass@k with \(1 - (1 - c/n)^k\), or with exactly \(k\) samples per problem. Use formula (148.6) with \(n \gt k\), and report \(n\) and the temperature.
  • Running generated code without a sandbox or a time limit. One while True stalls the whole evaluation; one rm damages the machine.
  • Dropping the system prompt when truncating a chat. The assistant suddenly loses its rules and persona. Truncate from the oldest user–assistant pair, never the system message.
  • Forgetting the template at inference time. Sending raw text instead of the chat template, or omitting the generation prompt, makes a chat model continue the user’s message instead of replying.
  • Training on the whole multi-turn conversation without a loss mask. The model learns to write user messages too. Mask everything except assistant turns (formula 148.2).

Interview questions

Why does greedy decoding give worse translations than beam search?basic
Greedy picks the best token at each step and never revisits the choice. The product of probabilities (148.1) can be higher for a sequence whose first token was only second-best. Beam search keeps \(k\) partial outputs, so it can recover such sequences. In Figure 1, greedy ends with probability 0.0702 while beam search with \(k = 3\) finds 0.0935 for the correct translation. It is still a heuristic: it does not guarantee the most likely output.
Why does beam search need a length penalty?core
Every token multiplies the probability by a number below 1, so the log-probability only goes down with length and short outputs win. Beam search is good at finding high-probability outputs, so it finds these too-short ones, which drop content. Dividing by \(|y|^{\alpha}\) (148.3) compares outputs by something closer to per-token quality. \(\alpha\) is tuned on a development set; too large and outputs become long and repetitive.
Encoder–decoder vs decoder-only LLM for translation: what are the trade-offs?core
An encoder–decoder encodes the source once with bidirectional attention and is usually smaller and cheaper for a fixed language set; it is the classic choice for high-volume MT with beam search. A decoder-only LLM handles translation through a prompt, can use whole-document context, glossaries and style instructions, and does many other tasks. Its weaknesses are cost, weaker low-resource languages, and new failure modes: answering instead of translating, adding text, or writing in the wrong language.
What is back-translation and why does it work?core
Train a reverse model (target to source), use it to translate real monolingual target-language text into the source language, and add the synthetic pairs to training. The source side is noisy, but the target side, which the model learns to generate, is real fluent text. It adds a lot of data for languages with little parallel text. It was a key ingredient of top WMT systems, as the T5 paper notes.
Give an example where BLEU ranks a wrong translation above a correct one.core
References “the cat is not sitting on the mat” and “the cat does not sit on the mat”. The wrong “the dog is not sitting on the mat” gets sentence BLEU 0.707; the correct “the cat is not on the mat” gets 0.515; dropping “not” (“the cat is sitting on the mat”) also gets 0.515; and the correct paraphrase “there is no cat on the mat” gets 0 because no 4-gram matches. BLEU measures n-gram overlap, not meaning. Learned metrics like COMET and expert MQM ratings catch these errors better.
Define pass@k and its unbiased estimator. Why not \(1 - (1 - \hat p)^k\)?core
pass@k is the probability that at least one of \(k\) samples passes the tests. Draw \(n \ge k\) samples, count \(c\) correct, and estimate \(1 - \binom{n-c}{k}/\binom{n}{k}\) (148.5), averaged over problems; compute it as a product (148.6) for stability. The plug-in \(1-(1-\hat p)^k\) is biased because the function is nonlinear (concave) in \(p\), so the average over the noise in \(\hat p\) is not the function of the true \(p\). Example: \(n=10\), \(c=3\), \(k=5\) gives 0.917 vs 0.832.
Why does the best sampling temperature depend on k?advanced
For pass@1 you want the single most likely program, so low temperature (Codex: 0.2) is best. For pass@100 you want the 100 samples to be diverse, so that at least one takes a correct approach; higher temperature (Codex: 0.8) spreads the samples. Too high adds syntax errors. In deployment you also need a way to choose among samples: user tests, or a heuristic like mean log-probability, which is much weaker than an oracle (44.5% vs 77.5% for Codex at 100 samples).
How would you design a safe execution harness for evaluating generated code?advanced
Run each sample in a fresh, isolated sandbox (container or gVisor-style runtime) with no network, a read-only or temporary file system, CPU-time and memory limits, and a wall-clock timeout. Feed the prompt, the completion and the hidden tests; pass means exit code 0 with all assertions passing. Treat timeouts, crashes and import errors as failures. Make it deterministic (fixed seeds, pinned library versions), log the outputs, and run many samples in parallel. Keep tests hidden from the model to avoid overfitting to them.
A chat has a 500-token system prompt, 50-token questions and 250-token answers. How many prompt tokens are processed over 40 turns, and how do you reduce it?core
The input before reply \(t\) is \(n_t = 500 + 50t + 250(t-1)\); at turn 40 that is 12,250. Summing (148.8): \(40 \cdot 500 + 50 \cdot 820 + 250 \cdot 780 = 256{,}000\) tokens, quadratic in the number of turns. Prefix caching keeps the KV cache between turns, so only new tokens are prefilled (12,250 in total). To bound the context itself, use a sliding window, a summary of old turns, or retrieval from a long-term memory, always keeping the system prompt.
How do chat assistants keep a persona and remember facts over a long conversation?core
The persona and rules live in the system prompt, which is never truncated. Recent turns stay in the context window. Older content is either summarized into the prompt or extracted as facts into an external store and retrieved when relevant (MemGPT-style memory). Fine-tuning on multi-turn conversations, with the loss on every assistant turn, teaches the model to use earlier turns. Failures to watch for: instructions fading after many turns, contradictions, and facts lost in the middle of long contexts.
Why is dialogue the hardest of the three to evaluate, and what do people use?advanced
There is no reference reply: many replies are good, quality depends on the whole history and on the user, and errors can appear many turns later. Reference metrics like BLEU correlate poorly. Practice uses pairwise human preference (Chatbot Arena), LLM-as-a-judge on fixed multi-turn question sets (MT-Bench), with care for position, length and self-preference bias, plus task success rates for goal-driven assistants and targeted tests for consistency and memory.

Exercises

  1. In Figure 1 with \(k = 2\), the winner switches from “A house .” to “A house is small .” at some \(\alpha\). Compute that \(\alpha\) from \(p = 0.12\) (3 tokens) and \(p = 0.072\) (5 tokens), and check it with the slider.
  2. Compute sentence BLEU (formula 148.4, no smoothing) for “the cat sat on the mat” against the two references of Figure 2. Give \(p_1\) to \(p_4\) and BP.
  3. One problem: \(n = 20\) samples, \(c = 4\) correct. Compute pass@5 with formula (148.5) and the naive estimate.
  4. A support bot has \(s = 1{,}000\), \(u = 100\), \(a = 400\). For a 20-turn chat, compute the last input \(n_{20}\) and the total prompt tokens without caching.
  5. Explain why beam search with \(k = 5\) is rarely used for an open-ended chat reply, even though it helps translation.
  6. Write a test case that the “ignores case” sample in the code passes but the problem statement says it should fail. What does this tell you about test suites?
Answerscheck
1. \(\ln 0.12 = -2.120\), \(\ln 0.072 = -2.631\). Equal scores when \(2.120 \cdot 5^{\alpha} = 2.631 \cdot 3^{\alpha}\), so \(\alpha = \ln(2.631/2.120)/\ln(5/3) = 0.42\). Above it, the longer output wins. 2. Output length 6, closest reference length 8. \(p_1 = 5/6\) (“sat” does not match), \(p_2 = 3/5\), \(p_3 = 1/4\), \(p_4 = 0/3\). BP \(= e^{1 - 8/6} = 0.717\). Because \(p_4 = 0\), BLEU \(= 0\). 3. \(\binom{16}{5} = 4{,}368\), \(\binom{20}{5} = 15{,}504\): pass@5 \(= 1 - 4368/15504 = 0.718\). Naive: \(1 - 0.8^5 = 0.672\). 4. \(n_{20} = 1000 + 2000 + 19 \cdot 400 = 10{,}600\). Total \(= 20{,}000 + 100 \cdot 210 + 400 \cdot 190 = 117{,}000\). 5. Chat has many good replies; beam search pushes toward the single most likely, often generic and repetitive, reply, costs \(k\) times more compute and memory, and conflicts with streaming. Sampling at a moderate temperature gives more natural replies. 6. The sample s == s[::-1] fails on “Abba” (it returns False), so it is caught; but it would wrongly pass any test using only lower-case strings without spaces, such as f('aba'). If the suite had only such tests, the wrong program would count as correct: tests must cover every requirement in the specification, which is what HumanEval+ adds.

Key takeaways

  • Translation, code and dialogue are all conditional generation (148.1); decoder-only LLMs put the input in the prompt and mask the loss to the output (148.2).
  • Greedy decoding is short-sighted; beam search keeps \(k\) candidates, and a length penalty (148.3) stops it from preferring outputs that are too short.
  • BLEU (148.4) counts n-gram overlap: it can score a wrong translation above a correct one. Use chrF, COMET and expert MQM ratings as well.
  • Code is judged by execution in a sandbox. pass@k uses the unbiased estimator (148.5) in product form (148.6); weak tests and contamination inflate scores.
  • A chat resends its whole history every turn: input grows linearly (148.7) and total work quadratically (148.8). Prefix caching, windows, summaries and long-term memory keep it bounded; never drop the system prompt.

Key formulas

\[ \text{score}(y) = \frac{\log p(y \mid x)}{|y|^{\alpha}}, \qquad \text{pass@}k = 1 - \frac{\binom{n-c}{k}}{\binom{n}{k}}, \qquad n_t = s + t\,u + (t-1)\,a \]

References for this session

  1. Raffel et al. (2019). Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer
  2. Chen et al. (2021). Evaluating Large Language Models Trained on Code
  3. Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, chapter 8: Post-training
  4. Vaswani et al. (2017). Attention Is All You Need
  5. Wu et al. (2016). Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translation
  6. Sennrich, Haddow and Birch (2016). Improving Neural Machine Translation Models with Monolingual Data
  7. NLLB Team (2022). No Language Left Behind: Scaling Human-Centered Machine Translation
  8. Papineni et al. (2002). BLEU: a Method for Automatic Evaluation of Machine Translation
  9. Popović (2015). chrF: character n-gram F-score for automatic MT evaluation
  10. Rei et al. (2020). COMET: A Neural Framework for MT Evaluation
  11. Freitag et al. (2021). Experts, Errors, and Context: A Large-Scale Study of Human Evaluation for Machine Translation
  12. Austin et al. (2021). Program Synthesis with Large Language Models
  13. Liu et al. (2023). Is Your Code Generated by ChatGPT Really Correct? Rigorous Evaluation of Large Language Models for Code Generation
  14. Jimenez et al. (2023). SWE-bench: Can Language Models Resolve Real-World GitHub Issues?
  15. Jain et al. (2024). LiveCodeBench: Holistic and Contamination Free Evaluation of Large Language Models for Code
  16. Zhang et al. (2018). Personalizing Dialogue Agents: I have a dog, do you have pets too?
  17. Packer et al. (2023). MemGPT: Towards LLMs as Operating Systems
  18. Liu et al. (2023). Lost in the Middle: How Language Models Use Long Contexts
  19. Zheng et al. (2023). Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena
  20. Chiang et al. (2024). Chatbot Arena: An Open Platform for Evaluating LLMs by Human Preference