LLM with Beam Search and Nucleus Sampling (Meta MSL)

Question

LLM Evaluation with Beam Search and Nucleus Sampling (Meta MSL)

## Background

You are working on a large language model that will be deployed in a real user-facing product. The team wants to evaluate different decoding strategies and understand how decoding affects output quality, diversity, reliability, and serving efficiency.

Two decoding methods are under consideration:

- Beam search decoding
- Nucleus sampling

Your task is to analyze these methods from both an algorithmic and production perspective.

---

## Problem

Design an evaluation and implementation plan to compare **beam search** and **nucleus sampling** for LLM generation.

Your answer should cover both:

1. **algorithmic understanding**
2. **practical production deployment considerations**

---

## Part 1: Explain the decoding methods

### 1. Beam Search

Explain:

- how beam search works step by step
- what the beam size means
- how cumulative log-probability is used to rank candidate sequences
- why beam search is often considered an approximate search procedure for high-likelihood decoding

Discuss:

- why beam search can improve likelihood
- why it may still produce poor user experience in open-ended generati

Accepted Answer

A detailed reference solution is available to Crack ML Interview members.