Mid-level interview questionAsked at Microsoft · interview write-up
Write beam search that returns each sentence with its probability. How does it differ from greedy decoding?
Model answer
Keep the k best partial sentences. Each step, extend every one with its likely next tokens, score by the sum of log-probabilities, and keep the top k. A sentence's probability is the exponent of that sum.
Scroll sideways to see the whole diagram
Step 1: score the next token. With beam width 2, keep the two best, “cat” and “dog”, and drop the rest.
Text version
- Step 1: score the next token. With beam width 2, keep the two best, “cat” and “dog”, and drop the rest.
- Step 2: extend each kept sentence and multiply the probabilities. In code, add log-probabilities instead, so long products don't underflow.
- Keep the best two again. “dog barked” wins at 0.36, although “dog” was only the second-best first word.
Illustrative probabilities.
Greedy is beam width 1, so it misses sequences whose first token wasn't the best. Longer sentences collect more negative terms, so normalise by length when comparing finished beams.
Practise the rest
9 Sampling questions, 492 in all, each with a model answer. Free.
More from Microsoft interview questions.
More Sampling interview questions
- What are logits, and how does a model go from them to a whole sentence of output?
- Explain temperature, top-k and top-p. Why would you usually reach for top-p rather than a fixed k?
- Greedy decoding on a small model gives fluent text that soon repeats itself word for word. Why does that happen?
- Your integration tests call a hosted model at temperature 0 and compare the output with an exact string. They fail now and then. What's going on, and what do you change?
- A PM wants to show users a 'confidence' percentage computed from the answer's token probabilities. What's your position, and what would you build instead?
- Build a bigram next-word predictor that samples the next word in proportion to how often it followed.