Exactness of speculative sampling with a modified acceptance rule
ProofAdvanced⏱ 1 hourLLM Opsrejection samplingexactnessproof
Problem
Suppose an implementer changes the acceptance probability from to for a constant , hoping to accept more often, and keeps the residual distribution unchanged.
- Prove that the resulting sampler is no longer exact, by computing the output distribution.
- Determine the total variation distance between the output and for the two-point example , , .
- State the general principle the failure illustrates.
Write a complete argument. Every inequality you use should be one you could state precisely.
Hints
Hints — 0 of 2 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| Solved | Problem | Field | Type | Difficulty | Time |
|---|---|---|---|---|---|
| Choosing the draft length | LLM Ops | Numerical | 30 min |