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.
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:
- 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:
- 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.
- 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.
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.
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.
- input: source \(x\), beam width \(k\), length penalty \(\alpha\), maximum length \(L\)
- alive \(\leftarrow\) [(empty output, log-prob 0)]; finished \(\leftarrow\) [ ]
- for \(t = 1, \dots, L\) while alive is not empty:
- 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
- sort candidates by log-prob, best first; alive \(\leftarrow\) [ ]
- 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
- 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):
- 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.
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]
- 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:
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.
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.
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]
- input: problems (prompt, hidden tests), model, \(n\), temperature \(\tau\), time limit
- for each problem:
- draw \(n\) completions from the model at temperature \(\tau\); stop each at the end of the function
- for each completion: run prompt + completion + tests in a fresh sandboxed process with the time limit; pass = (exit code 0)
- \(c \leftarrow\) number of passing completions; compute pass@k with formula (148.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:
“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:
Without any caching, each turn processes its whole input again, so over \(T\) turns the total number of prompt tokens is
- 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.
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.
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.
- input: system prompt (rules + persona), stored history, long-term memory store, new user message, budget \(C\), reply reserve \(r\)
- facts \(\leftarrow\) retrieve from the memory store the items most related to the new message
- messages \(\leftarrow\) [system + facts] + history + [new message]
- 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
- reply \(\leftarrow\) generate from render(messages) with the generation prompt, up to \(r\) tokens
- append (new message, reply) to history; extract new facts (“user lives in Porto”) and write them to the memory store
- 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
| Translation | Code generation | Dialogue | |
|---|---|---|---|
| How many correct outputs? | Many: paraphrases, word order, register | Many programs, but correctness is checkable | Very many; depends on the whole history and on user taste |
| Automatic metric | BLEU, chrF (overlap); COMET (learned) | pass@k from unit tests in a sandbox | Weak: no reference reply fits; LLM-as-a-judge is common |
| Gold standard | Expert MQM error annotation | Strong hidden tests, real repositories (SWE-bench) | Human preference between two replies (Chatbot Arena) |
| Typical failure the metric misses | Dropped negation, wrong entity, omitted clause | Bugs not covered by the tests, insecure code | Forgetting earlier facts, inconsistent persona, flattery |
| Contamination risk | Medium (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
| Application | Model and decoding | How it is checked |
|---|---|---|
| Web and document translation | Dedicated encoder–decoders (NLLB-style) with beam search, or LLMs with document context | COMET or chrF on test sets, MQM reviews by translators |
| Video subtitles and dubbing scripts | Speech recognition (for example Whisper), then MT with timing and line-length limits | Human review; reading-speed limits per subtitle line |
| Code completion in the editor | Small, fast code LLM; greedy or low temperature; fill-in-the-middle prompts | Acceptance 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 tests | SWE-bench-style: the repository’s own tests must pass |
| Chat assistants and customer support | Chat-tuned LLM, sampling, system prompt with persona and rules, memory | Human preference, LLM-as-a-judge, task success rate |
| Video question answering in many turns | Video-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 search | Translate queries or captions to one language, or use a multilingual embedding model | Retrieval 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 Truestalls the whole evaluation; onermdamages 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
Why does beam search need a length penalty?core
Encoder–decoder vs decoder-only LLM for translation: what are the trade-offs?core
What is back-translation and why does it work?core
Give an example where BLEU ranks a wrong translation above a correct one.core
Define pass@k and its unbiased estimator. Why not \(1 - (1 - \hat p)^k\)?core
Why does the best sampling temperature depend on k?advanced
How would you design a safe execution harness for evaluating generated code?advanced
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
How do chat assistants keep a persona and remember facts over a long conversation?core
Why is dialogue the hardest of the three to evaluate, and what do people use?advanced
Exercises
- 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.
- 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.
- One problem: \(n = 20\) samples, \(c = 4\) correct. Compute pass@5 with formula (148.5) and the naive estimate.
- 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.
- Explain why beam search with \(k = 5\) is rarely used for an open-ended chat reply, even though it helps translation.
- 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
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
References for this session
- Raffel et al. (2019). Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer
- Chen et al. (2021). Evaluating Large Language Models Trained on Code
- Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, chapter 8: Post-training
- Vaswani et al. (2017). Attention Is All You Need
- Wu et al. (2016). Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translation
- Sennrich, Haddow and Birch (2016). Improving Neural Machine Translation Models with Monolingual Data
- NLLB Team (2022). No Language Left Behind: Scaling Human-Centered Machine Translation
- Papineni et al. (2002). BLEU: a Method for Automatic Evaluation of Machine Translation
- Popović (2015). chrF: character n-gram F-score for automatic MT evaluation
- Rei et al. (2020). COMET: A Neural Framework for MT Evaluation
- Freitag et al. (2021). Experts, Errors, and Context: A Large-Scale Study of Human Evaluation for Machine Translation
- Austin et al. (2021). Program Synthesis with Large Language Models
- Liu et al. (2023). Is Your Code Generated by ChatGPT Really Correct? Rigorous Evaluation of Large Language Models for Code Generation
- Jimenez et al. (2023). SWE-bench: Can Language Models Resolve Real-World GitHub Issues?
- Jain et al. (2024). LiveCodeBench: Holistic and Contamination Free Evaluation of Large Language Models for Code
- Zhang et al. (2018). Personalizing Dialogue Agents: I have a dog, do you have pets too?
- Packer et al. (2023). MemGPT: Towards LLMs as Operating Systems
- Liu et al. (2023). Lost in the Middle: How Language Models Use Long Contexts
- Zheng et al. (2023). Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena
- Chiang et al. (2024). Chatbot Arena: An Open Platform for Evaluating LLMs by Human Preference