In an X thread, Meta FAIR scientist François Fleuret praises speculative decoding as near-free inference acceleration yet doubts rejection sampling can extend straightforwardly to massive models, while Lucas Beyer counters that the label hides practical speed gains and Danilo Rezende notes the method thrives when log-prob evaluation outpaces direct sampling.
@DaniloJRezende I know!
But it is such a simple and beautiful "trick" that I'd expect it cannot be so easily used for real with huge models.
Rejection sampling TL;DR: you want to sample ~mu on interval I, but you can only evaluate mu pointwise.
Sample X,Y uniform on I x [0, M], for any M greater than sup(mu(I)), and reject until Y≤mu(X), you now have X,Y uniform under mu's graph, and X~mu !
Fleuret expects uniform bounding-box proposals to break down under huge-model constraints, leaving the thread without resolution on whether optimized variants close the gap.
The exchange underscores that surrogate proposals succeed mainly when target-model log-prob checks stay far cheaper than full sampling, a condition that may or may not hold as models grow.
No Digg Deeper questions have been answered for this story yet.
@DaniloJRezende @francoisfleuret Rejection sampling does not include the genius efficiency of it, imo.
@francoisfleuret It's rejection sampling.
@giffmana @francoisfleuret True it is particularly favourable with AR transformers because computing log probs is much cheaper than sampling with larger model. But that is orthogonal to the algorithm itself.
@DaniloJRezende @francoisfleuret Rejection sampling does not include the genius efficiency of it, imo.
@giffmana @francoisfleuret There are many other places where rejection sampling is used for similar reason: sampling from target is expensive but cheap to eval log-prob, so use a cheap surrogate to sample and accept/reject.
@giffmana @francoisfleuret True it is particularly favourable with AR transformers because computing log probs is much cheaper than sampling with larger model. But that is orthogonal to the algorithm itself.