QuasiMoTTo: Quasi-Monte Carlo Test-Time Scaling

• URL: http://arxiv.org/abs/2607.01179v1
• Date: Wed, 01 Jul 2026 17:10:08 GMT
• Title: QuasiMoTTo: Quasi-Monte Carlo Test-Time Scaling
• Abstract summary: Scaling inference compute, by generating many parallel attempts per problem, is a costly but reliable lever for improving language model capabilities.<n>We introduce QuasiMoTTo, which uses correlated samples as a drop-in replacement for i.i.d. samples.<n>Our empirical analysis focuses on understanding how efficiently QuasiMoTTo can turn compute into performance.
• Score: 35.00824891749274
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Scaling inference compute, by generating many parallel attempts per problem, is a costly but reliable lever for improving language model capabilities. By default these attempts are generated independently, wasting inference compute on redundant solutions. This waste seems unavoidable. After all, independence is what makes parallel sampling trivial to scale. However, this tradeoff is not fundamental: there is a rich design space of samplers that generate correlated but exact samples entirely in parallel. We explore this design space as an avenue for improving sample efficiency in scaling inference compute and reinforcement learning (RL). Concretely, we introduce QuasiMoTTo, which uses correlated samples as a drop-in replacement for i.i.d. samples. To generate these samples, QuasiMoTTo uses a reparameterization of autoregressive sampling as inverse-CDF sampling and draws the underlying uniforms with quasi-Monte Carlo (QMC); because QMC spreads the uniforms out more evenly than i.i.d., the resulting samples cover the output space with far less redundancy. Even though the batch is correlated, each sample is marginally distributed according to the language model, so we can use the batch for policy-gradient training. Our empirical analysis focuses on understanding how efficiently QuasiMoTTo can turn compute into performance. To evaluate correlated samplers, whose dependence breaks standard pass@k estimators, we first develop an unbiased bootstrap estimator. Across four reasoning benchmarks, QuasiMoTTo matches i.i.d. pass@k accuracy with 25-47% fewer samples. Strikingly, QuasiMoTTo often saturates an upper bound on pass@k that holds for any marginal-preserving sampler. We also apply QuasiMoTTo to policy-gradient RL (GRPO) where it matches i.i.d. performance with 50% fewer training steps. These gains come from higher coverage, which yields a stronger learning signal per batch.

Related papers

• UnpredictaBench: A Benchmark for Evaluating Distributional Randomness in LLMs [21.05820098186702]
  We introduce UnpredictaBench, an evaluation that tests the ability of large language models to capture true underlying distributions.<n>We find that even simple distributional simulation remains challenging, making it a necessary first step toward using LLMs as stand-ins for complex systems.
  arXiv  Detail & Related papers  (2026-06-04T18:18:02Z)
• Test-Time Scaling with Diffusion Language Models via Reward-Guided Stitching [66.39914384073145]
  We propose a self-consistency framework that turns cheap diffusion-sampled reasoning into a reusable pool of step-level candidates.<n>We find that step-level recombination is most beneficial on harder problems.<n>Our training-free framework improves average accuracy by up to 2 across six math and coding tasks.
  arXiv  Detail & Related papers  (2026-02-26T11:08:39Z)
• Self-Rewarding Sequential Monte Carlo for Masked Diffusion Language Models [58.946955321428845]
  This work presents self-rewarding sequential Monte Carlo (SMC)<n>Our algorithm stems from the observation that most existing MDLMs rely on a confidence-based sampling strategy.<n>We introduce the trajectory-level confidence as a self-rewarding signal for assigning particle importance weights.
  arXiv  Detail & Related papers  (2026-02-02T09:21:45Z)
• Score-based sampling without diffusions: Guidance from a simple and modular scheme [0.0]
  We show how to design forward trajectories that both (a) the terminal distribution, and (b) each of the backward conditional distribution is defined by a strongly log concave (SLC) distribution.<n>This modular reduction allows us to exploit emphany SLC sampling algorithm in order to traverse the backwards path.<n>The use of high-accuracy routines yields $varepsilon$-accurate answers, in either KL or Wasserstein distances.
  arXiv  Detail & Related papers  (2025-12-30T11:34:59Z)
• Learning to Reason Across Parallel Samples for LLM Reasoning [48.41933431325965]
  Scaling test-time compute brings substantial performance gains for large language models (LLMs)<n>In this paper, we propose a new way to leverage such multiple sample set.<n> Experiments on five reasoning datasets demonstrate both the efficacy and efficiency of SSA.
  arXiv  Detail & Related papers  (2025-06-10T17:42:35Z)
• Self-Refining Diffusion Samplers: Enabling Parallelization via Parareal Iterations [53.180374639531145]
  Self-Refining Diffusion Samplers (SRDS) retain sample quality and can improve latency at the cost of additional parallel compute.<n>We take inspiration from the Parareal algorithm, a popular numerical method for parallel-in-time integration of differential equations.
  arXiv  Detail & Related papers  (2024-12-11T11:08:09Z)
• Large Language Monkeys: Scaling Inference Compute with Repeated Sampling [81.34900892130929]
  We explore inference compute as another axis for scaling, using the simple technique of repeatedly sampling candidate solutions from a model.<n>Across multiple tasks and models, we observe that coverage scales with the number of samples over four orders of magnitude.<n>In domains like coding and formal proofs, where answers can be automatically verified, these increases in coverage directly translate into improved performance.
  arXiv  Detail & Related papers  (2024-07-31T17:57:25Z)
• Mini-batch Submodular Maximization [5.439020425819001]
  We present the first mini-batch algorithm for maximizing a monotone decomposable submodular function, $F=sum_i=1N fi$, under a set of constraints. We consider two sampling approaches: uniform and weighted. Surprisingly, our experimental results show that uniform sampling is superior to weighted sampling.
  arXiv  Detail & Related papers  (2024-01-23T04:16:58Z)
• Low-variance estimation in the Plackett-Luce model via quasi-Monte Carlo sampling [58.14878401145309]
  We develop a novel approach to producing more sample-efficient estimators of expectations in the PL model. We illustrate our findings both theoretically and empirically using real-world recommendation data from Amazon Music and the Yahoo learning-to-rank challenge.
  arXiv  Detail & Related papers  (2022-05-12T11:15:47Z)
• Unrolling Particles: Unsupervised Learning of Sampling Distributions [102.72972137287728]
  Particle filtering is used to compute good nonlinear estimates of complex systems. We show in simulations that the resulting particle filter yields good estimates in a wide range of scenarios.
  arXiv  Detail & Related papers  (2021-10-06T16:58:34Z)

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.