Efficient Calibration via Rejection Sampling

Exponential Tilting (ET) is a classical technique for model calibration, alignment and reward maximization. For a given statistic (reward) function $f$, ET transforms a base model distribiution $Q$ via the multiplicative update rule $Q^{\alpha }\propto Q\cdot \exp (\alpha \cdot f)$. Braverman et al. (ICML 2020) showed that fitting $\alpha$ to minimize cross-entropy loss against some reference distribution, ensures the tilted model does not lose quality, while maximizing the average value of $f$. Unfortunately, ET has a prohibitive computational cost of computing the normalizing partition function, requiring multiple foward passes to evaluate $f$ on the full support of tokens, which renders this technique impreactical in the autoregressive LLM setup. We propose a natural, highly efficient algorithm for implicitly sampling from the tilted distribution via rejection-sampling, which dramatically reduces the query access to the tilted model and avoids computing the normalizing partition function altogether. We demonstrate the efficiency of our technique in theory and practice, by analyzing the expected query count and upper bounding it in terms of the cross-entropy distance to the base model and the “variance" of $f$. We then corroborate our bounds on small-size LLMs (Qwen2.5, Qwen3 and SmolLM3), applying our approach to the substantive case study of entropy calibration of LLMs (Cao et al., NIPS 2025). Our experiments show improvement in entropy miscalibration in base models, while incurring 15–25% additional sampling attempts due to rejections. We expect this overhead to improve when moving to more capable and larger models.