The KL divergence of best-of-n

ProofGraduate⏱ 1 hourAgentskl divergenceorder statisticsalignment

Theory: Inference-Time Search and Best-of-n →

Problem

Prove that best-of- $n$ sampling against a continuous reward satisfies $\mathrm{KL}(\pi_n\|\pi) = \log n - \frac{n-1}{n}$ .

Then: compute the value for $n = 4, 16, 64$ ; show the divergence is unbounded in $n$ ; and explain why this quantity is the right thing to compare against a KL-regularised fine-tune.

Write a complete argument. Every inequality you use should be one you could state precisely.

Hints

Hints — 0 of 3 revealed

Solution

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Related problems

All problems

Problem	Field	Type	Difficulty	Time
Maximum likelihood is KL minimisation	LLMs	Proof	Beginner	15 min
Sizing best-of-n	Agents	Numerical	Beginner	15 min
Measure fan-out amplification and the value of hedging run	AI Systems	Coding	Intermediate	1 hour
The pass@k estimator	Agents	Proof	Intermediate	30 min
Applying McDiarmid to a median	High-Dim Probability	Proof	Advanced	30 min