Flipping Against All Odds: Reducing LLM Coin Flip Bias via Verbalized Rejection Sampling
This addresses a reliability issue for users of LLMs in applications requiring accurate stochasticity, such as Monte Carlo simulations, but it is incremental as it adapts an existing classical method.
The paper tackled the problem of LLMs struggling to generate faithful samples from probability distributions, which limits their use in stochastic tasks, by introducing Verbalized Rejection Sampling (VRS) to reduce sampling bias in Bernoulli distributions, showing substantial improvements across models.
Large language models (LLMs) can often accurately describe probability distributions using natural language, yet they still struggle to generate faithful samples from them. This mismatch limits their use in tasks requiring reliable stochasticity, such as Monte Carlo methods, agent-based simulations, and randomized decision-making. We investigate this gap between knowledge and sampling in the context of Bernoulli distributions. We introduce Verbalized Rejection Sampling (VRS), a natural-language adaptation of classical rejection sampling that prompts the LLM to reason about and accept or reject proposed samples. Despite relying on the same Bernoulli mechanism internally, VRS substantially reduces sampling bias across models. We provide theoretical analysis showing that, under mild assumptions, VRS improves over direct sampling, with gains attributable to both the algorithm and prompt design. More broadly, our results show how classical probabilistic tools can be verbalized and embedded into LLM workflows to improve reliability, without requiring access to model internals or heavy prompt engineering.