Decoding-Free Sampling Strategies for LLM Marginalization

• URL: http://arxiv.org/abs/2510.20208v1
• Date: Thu, 23 Oct 2025 04:50:14 GMT
• Title: Decoding-Free Sampling Strategies for LLM Marginalization
• Authors: David Pohl, Marco Cognetta, Junyoung Lee, Naoaki Okazaki,
• Abstract summary: Modern language models operate on subword-tokenized text in order to make a trade-off between model size, inference speed, and vocabulary coverage.<n>We investigate sampling strategies that are decoding-free, instead relying entirely on extremely cheap sampling strategies that are model and tokenizer agnostic.
• Score: 15.214953630908477
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Modern language models operate on subword-tokenized text in order to make a trade-off between model size, inference speed, and vocabulary coverage. A side effect of this is that, during inference, models are evaluated by measuring the probability of only the specific tokenization produced as the output, despite there being many possible ways to represent the same text with a subword vocabulary. Recent studies have argued instead for evaluating LLMs by marginalization - the probability mass of all tokenizations of a given text. Marginalization is difficult due to the number of possible tokenizations of a text, so often approximate marginalization is done via sampling. However, a downside of sampling is that an expensive generation step must be performed by the LLM for each sample, which limits the number of samples that can be acquired given a runtime budget, and therefore also the accuracy of the approximation. Since computing the probability of a sequence given the tokenization is relatively cheap compared to actually generating it, we investigate sampling strategies that are decoding-free - they require no generation from the LLM, instead relying entirely on extremely cheap sampling strategies that are model and tokenizer agnostic. We investigate the approximation quality and speed of decoding-free sampling strategies for a number of open models to find that they provide sufficiently accurate marginal estimates at a small fraction of the runtime cost and demonstrate its use on a set of downstream inference tasks.

Related papers

• LLM-ERM: Sample-Efficient Program Learning via LLM-Guided Search [23.97383442759484]
  LLM-ERM is a propose-and-verify framework that replaces exhaustive enumeration with an LLM-guided search over candidate programs.<n>We show that coordinate-wise online mini-batch SGD requires many samples to learn certain short programs.<n>These results indicate that language-guided program synthesis recovers much of the statistical efficiency of finite-class ERM.
  arXiv  Detail & Related papers  (2025-10-16T06:10:11Z)
• p-less Sampling: A Robust Hyperparameter-Free Approach for LLM Decoding [10.595336643423229]
  $p$-less sampling is an information-theoretic approach to sampling.<n>It dynamically sets a truncation threshold at each decoding step based on the entire token probability distribution.<n>It consistently produces high-quality outputs as temperature increases.
  arXiv  Detail & Related papers  (2025-09-27T10:33:41Z)
• Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Sampling [90.86991492288487]
  evaluating constraint on every token can be prohibitively expensive.<n> LCD can distort the global distribution over strings, sampling tokens based only on local information.<n>We show that our approach is superior to state-of-the-art baselines.
  arXiv  Detail & Related papers  (2025-04-07T18:30:18Z)
• Quasi-random Multi-Sample Inference for Large Language Models [1.647759094903376]
  Large language models (LLMs) are often equipped with multi-sample decoding strategies.<n>Traditional text generation methods, such as beam search and sampling-based techniques, have notable limitations.<n>This study explores the potential of arithmetic sampling, contrasting it with ancestral sampling.
  arXiv  Detail & Related papers  (2024-11-09T18:55:04Z)
• Balancing Diversity and Risk in LLM Sampling: How to Select Your Method and Parameter for Open-Ended Text Generation [60.493180081319785]
  We propose a systematic way to estimate the capacity of a truncation sampling method by considering the trade-off between diversity and risk at each decoding step.<n>Our work offers a comprehensive comparison of existing truncation sampling methods and serves as a practical user guideline for their parameter selection.
  arXiv  Detail & Related papers  (2024-08-24T14:14:32Z)
• Turning Up the Heat: Min-p Sampling for Creative and Coherent LLM Outputs [3.631341123338476]
  Large Language Models (LLMs) generate text by sampling the next token from a probability distribution over the vocabulary at each decoding step.<n>We propose min-p sampling, a dynamic truncation method that adjusts the sampling threshold based on the model's confidence by using the top token's probability as a scaling factor.
  arXiv  Detail & Related papers  (2024-07-01T08:37:25Z)
• Closing the Curious Case of Neural Text Degeneration [91.22954750742183]
  We provide a theoretical explanation for the effectiveness of the truncation sampling. We show that we can leverage a known source of model errors, the softmax bottleneck, to prove that certain tokens have nonzero true probability. Our evaluations show that our method outperforms its threshold-based counterparts for low-entropy text generation.
  arXiv  Detail & Related papers  (2023-10-02T23:16:25Z)
• 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)
• Arithmetic Sampling: Parallel Diverse Decoding for Large Language Models [65.52639709094963]
  Methods such as beam search and Gumbel top-k sampling can guarantee a different output for each element of the beam, but are not easy to parallelize. We present a framework for sampling according to an arithmetic code book implicitly defined by a large language model.
  arXiv  Detail & Related papers  (2022-10-18T22:19:41Z)
• A Provably Efficient Sample Collection Strategy for Reinforcement Learning [123.69175280309226]
  One of the challenges in online reinforcement learning (RL) is that the agent needs to trade off the exploration of the environment and the exploitation of the samples to optimize its behavior. We propose to tackle the exploration-exploitation problem following a decoupled approach composed of: 1) An "objective-specific" algorithm that prescribes how many samples to collect at which states, as if it has access to a generative model (i.e., sparse simulator of the environment); 2) An "objective-agnostic" sample collection responsible for generating the prescribed samples as fast as possible.
  arXiv  Detail & Related papers  (2020-07-13T15:17:35Z)

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.