Skip to content
nonconvexcard

Exactness of speculative sampling with a modified acceptance rule

ProofAdvanced⏱ 1 hourLLM Opsrejection samplingexactnessproof

Problem

Suppose an implementer changes the acceptance probability from min⁡(1,p(x)/q(x))\min(1, p(x)/q(x)) to min⁡(1,κ p(x)/q(x))\min(1, \kappa\,p(x)/q(x)) for a constant κ>1\kappa > 1, hoping to accept more often, and keeps the residual distribution p′(x)∝max⁡(0,p(x)−q(x))p'(x)\propto\max(0, p(x)-q(x)) unchanged.

  1. Prove that the resulting sampler is no longer exact, by computing the output distribution.
  2. Determine the total variation distance between the output and pp for the two-point example p=(0.6,0.4)p = (0.6, 0.4), q=(0.5,0.5)q = (0.5, 0.5), κ=1.5\kappa = 1.5.
  3. 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
SolvedProblemFieldTypeDifficultyTime
Choosing the draft lengthLLM OpsNumericalAdvanced30 min