Flipping Against All Odds: Reducing LLM Coin Flip Bias via Verbalized Rejection Sampling

• URL: http://arxiv.org/abs/2506.09998v1
• Date: Wed, 11 Jun 2025 17:59:58 GMT
• Title: Flipping Against All Odds: Reducing LLM Coin Flip Bias via Verbalized Rejection Sampling
• Authors: Tim Z. Xiao, Johannes Zenn, Zhen Liu, Weiyang Liu, Robert Bamler, Bernhard Schölkopf,
• Abstract summary: Large language models (LLMs) can often accurately describe probability distributions using natural language.<n>This mismatch limits their use in tasks requiring reliableity, such as Monte Carlo methods, agent-based simulations, and randomized decision-making.<n>We introduce Verbalized Rejection Sampling (VRS), a natural-language adaptation of classical rejection sampling.
• Score: 59.133428586090226
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Is Your Diffusion Sampler Actually Correct? A Sampler-Centric Evaluation of Discrete Diffusion Language Models [14.764619905977739]
  We introduce a sampler-centric oracle framework that replaces learned denoisers with an exact Hidden Markov Model posterior derived from a ground-truth Markov chain.<n>We show that few-step discrete diffusion samplers are not distributionally correct even under an oracle denoiser, with transition-level mismatch that vanishes only as the number of steps approaches the sequence length.
  arXiv  Detail & Related papers  (2026-02-23T09:06:13Z)
• Learnable Chernoff Baselines for Inference-Time Alignment [64.81256817158851]
  We introduce Learnable Chernoff Baselines as a method for efficiently and approximately sampling from exponentially tilted kernels.<n>We establish total-variation guarantees to the ideal aligned model, and demonstrate in both continuous and discrete diffusion settings that LCB sampling closely matches ideal rejection sampling.
  arXiv  Detail & Related papers  (2026-02-08T00:09:40Z)
• Large Language Models Are Bad Dice Players: LLMs Struggle to Generate Random Numbers from Statistical Distributions [50.1404916337174]
  We present the first large-scale, statistically powered audit of native probabilistic sampling in large language models (LLMs)<n>We show that batch generation achieves only modest statistical validity, with a 13% median pass rate, while independent requests collapse almost entirely.<n>We conclude that current LLMs lack a functional internal sampler, necessitating the use of external tools for applications requiring statistical guarantees.
  arXiv  Detail & Related papers  (2026-01-08T22:33:12Z)
• Learning to Reason in LLMs by Expectation Maximization [55.721496945401846]
  We formalize reasoning as a latent variable model and derive an expectation-maximization objective for learning to reason.<n>This view connects EM and modern reward-based optimization, and shows that the main challenge lies in designing a sampling distribution that generates rationales that justify correct answers.
  arXiv  Detail & Related papers  (2025-12-23T08:56:49Z)
• Constrained Adaptive Rejection Sampling [27.579645342312674]
  Language Models (LMs) are increasingly used in applications where generated outputs must satisfy strict semantic or syntactic constraints.<n>Existing approaches to constrained generation fall along a spectrum: greedy constrained decoding methods enforce validity during decoding but distort the LM's distribution.<n>We present Constrained Adaptive Rejection Sampling (CARS), an approach that strictly improves the sample-efficiency of RS without distributional distortion.
  arXiv  Detail & Related papers  (2025-10-02T11:17:26Z)
• Mitigating Spurious Correlations in LLMs via Causality-Aware Post-Training [57.03005244917803]
  Large language models (LLMs) often fail on out-of-distribution (OOD) samples due to spurious correlations acquired during pre-training.<n>Here, we aim to mitigate such spurious correlations through causality-aware post-training (CAPT)<n> Experiments on the formal causal inference benchmark CLadder and the logical reasoning dataset PrOntoQA show that 3B-scale language models fine-tuned with CAPT can outperform both traditional SFT and larger LLMs on in-distribution (ID) and OOD tasks.
  arXiv  Detail & Related papers  (2025-06-11T06:30:28Z)
• Statistical Hypothesis Testing for Auditing Robustness in Language Models [49.1574468325115]
  We introduce distribution-based perturbation analysis, a framework that reformulates perturbation analysis as a frequentist hypothesis testing problem.<n>We construct empirical null and alternative output distributions within a low-dimensional semantic similarity space via Monte Carlo sampling.<n>We show how we can quantify response changes, measure true/false positive rates, and evaluate alignment with reference models.
  arXiv  Detail & Related papers  (2025-06-09T17:11:07Z)
• Cycles of Thought: Measuring LLM Confidence through Stable Explanations [53.15438489398938]
  Large language models (LLMs) can reach and even surpass human-level accuracy on a variety of benchmarks, but their overconfidence in incorrect responses is still a well-documented failure mode. We propose a framework for measuring an LLM's uncertainty with respect to the distribution of generated explanations for an answer.
  arXiv  Detail & Related papers  (2024-06-05T16:35:30Z)
• Do LLMs Play Dice? Exploring Probability Distribution Sampling in Large Language Models for Behavioral Simulation [73.58618024960968]
  An increasing number of studies are employing large language models (LLMs) as agents to emulate the sequential decision-making processes of humans.<n>This arouses curiosity regarding the capacity of LLM agents to comprehend probability distributions.<n>Our analysis indicates that LLM agents can understand probabilities, but they struggle with probability sampling.
  arXiv  Detail & Related papers  (2024-04-13T16:59:28Z)
• Conformal Language Modeling [61.94417935386489]
  We propose a novel approach to conformal prediction for generative language models (LMs) Standard conformal prediction produces prediction sets with rigorous, statistical guarantees. We demonstrate the promise of our approach on multiple tasks in open-domain question answering, text summarization, and radiology report generation.
  arXiv  Detail & Related papers  (2023-06-16T21:55:08Z)
• Efficient Propagation of Uncertainty via Reordering Monte Carlo Samples [0.7087237546722617]
  Uncertainty propagation is a technique to determine model output uncertainties based on the uncertainty in its input variables. In this work, we investigate the hypothesis that while all samples are useful on average, some samples must be more useful than others. We introduce a methodology to adaptively reorder MC samples and show how it results in reduction of computational expense of UP processes.
  arXiv  Detail & Related papers  (2023-02-09T21:28:15Z)
• Sampling from Discrete Energy-Based Models with Quality/Efficiency Trade-offs [3.491202838583993]
  Energy-Based Models (EBMs) allow for extremely flexible specifications of probability distributions. They do not provide a mechanism for obtaining exact samples from these distributions. We propose a new approximate sampling technique, Quasi Rejection Sampling (QRS), that allows for a trade-off between sampling efficiency and sampling quality.
  arXiv  Detail & Related papers  (2021-12-10T17:51:37Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.