Power-SMC: Low-Latency Sequence-Level Power Sampling for Training-Free LLM Reasoning

Abstract

Reasoning ability in large language models is often attributed to \emph{distribution sharpening}: concentrating output probability on high-likelihood sequences. Recent works show that this sharpening effect can be obtained at inference time, without modifying model parameters, and can elicit strong reasoning performance. A natural formalization is the \emph{sequence-level power distribution}, which is proportional to the model's probability raised to an exponent $\alpha>1$. Prior work leveraged Metropolis--Hastings (MH) sampling to draw samples from this distribution and achieves strong results, however, at order-of-magnitude inference slowdowns. We introduce \textbf{Power-SMC}, a \textit{`training-free'} sampling method that targets the same power distribution yielding close to standard decoding latency. Power-SMC maintains multiple candidate sequences in parallel. Each candidate sequence is assigned a score, namely the \emph{importance weight}, that measures how well it matches the power distribution. It then periodically prunes low-scoring candidate sequences in favor of high-scoring ones. We further provide a theoretical justification for the design choices in Power-SMC. Among all next-token sampling strategies that do not rely on future tokens, we prove that sampling temperature $\tau{=}1/\alpha$ uniquely eliminates per-step weight variance. Finally, we characterize the remaining source of weight instability and introduce a gradual sharpening schedule to reduce weight collapse, while targeting the same power distribution. Extensive evaluations on MATH500, GSM8K, GPQA, and HumanEval show that Power-SMC matches or exceeds MH sampling in accuracy, preserves output diversity unlike RL-finetuned models, while \textbf{accelerating inference speed by up to} {$\mathbf{17.6}\times$}. The code is available at https://github.com/ArminAzizi98/Power-SMC.