LP-SMC: Improving Diffusion Language Model Inference with Lineage-Preserving Resampling

Diffusion LLMs' reasoning capabilities can often be enhanced through inference-time search strategies without relying on additional post-training. Among these, Sequential Monte Carlo (SMC) decoding is a promising approach: it maintains a set of partially generated sequences, resamples based on reward signals, and thereby concentrates computational resources on more promising candidates. However, the core of this mechanism—the resampling step—has an easily overlooked pitfall: while multinomial resampling amplifies high-weight particles, it may completely discard "lineages" that currently score low but could still lead to correct answers. A new study proposes LP-SMC (Lineage-Preserving SMC), which preserves these lineages by improving the resampling strategy, achieving consistent gains on mathematical reasoning and code generation tasks.

The Diversity Dilemma of SMC Decoding

SMC decoding works in a straightforward way: starting from a set of randomly initialized partial generations, at each step particles are resampled according to rewards, allowing high-weight candidates to obtain more descendants before decoding continues. Rewards can be internal—the decoder's confidence in the committed prefix—or external—a process reward model (PRM) scoring that prefix. Ideally, resampling should direct computation toward promising reasoning paths while preserving enough diversity to explore other possible solutions.

The problem lies in multinomial resampling. It replicates particles in proportion to their weights: high-weight particles are sampled repeatedly, while low-weight particles may be eliminated entirely. Once a particle receives a low score early on due to chance factors, its entire lineage—all possible paths extending from that prefix—disappears. Even if a branch leading to the correct answer originally existed within that lineage, it cannot be recovered.

More subtly, the commonly used effective sample size (ESS) metric cannot reflect this loss. Multinomial resampling resets ESS to its maximum value, making it appear that "diversity is sufficient," while in reality the number of distinct lineages may have already shrunk substantially. In other words, ESS measures the concentration of weights, not the richness of lineages.

Process Reward Model (PRM) is a model that scores partially generated reasoning steps (prefixes) at inference time, unlike an Outcome Reward Model (ORM) that scores only the final answer. PRMs are typically trained on data with step-level annotations, learning to judge whether the current reasoning prefix is on the right track, and can thus provide denser reward signals during decoding. In SMC decoding, the PRM serves as an external reward source alongside the decoder's own confidence (internal reward) for weighting and resampling particles. The quality of the PRM directly determines the direction of search guidance, but it is not responsible for diversity maintenance—which is precisely the complementary dimension that LP-SMC addresses.

Effective Sample Size (ESS) is a commonly used metric in sequential Monte Carlo for measuring the concentration of particle weights, defined as (1/\sum_i w_i^2) (after weight normalization), with values ranging from 1 to the total number of particles. A smaller ESS indicates that weights are more concentrated on a few particles, and the risk of diversity loss after resampling is greater. However, ESS only characterizes the distribution of weights, not the number of distinct ancestral lineages represented by particles. Multinomial resampling resets weights to uniform after each step, bringing ESS back to its maximum, but by then many lineages may have been permanently discarded. Thus, ESS has a blind spot as a diversity diagnostic, which is one motivation for LP-SMC's emphasis on lineage preservation.

Two Key Designs of LP-SMC

To address the above issues, researchers propose LP-SMC, whose core consists of two modifications: Chopthin resampling and an input weight floor.

The idea behind Chopthin resampling differs from multinomial resampling. Rather than striving to "flatten" all weights to equality, it constrains the ratio between the maximum and minimum values in the returned weights. In other words, after resampling, weights among particles can still be unequal, but the degree of inequality is bounded within a controllable range. This way, lower-weight particles are not completely erased by a single resampling step, and their lineages continue.

The input weight floor is another safeguard. It specifies that before resampling, a particle's weight can be at most a certain amount below the maximum weight; weights below this floor are raised. The intent is clear—to give lineages with low early weights a chance to recover. A low early score does not necessarily mean an eventual error; the value of a reasoning path often only becomes apparent later.

Working together, the two designs allow resampling to achieve a better balance between "concentrating computation" and "preserving diversity." In the paper's words, Chopthin constrains the weight ratio, and the weight floor constrains the lower bound of weights; together they prevent lineages from being prematurely eliminated during resampling.

Chopthin resampling is a resampling algorithm that constrains weight ratios, first proposed by Gerber et al. Unlike multinomial resampling, Chopthin does not force all particles to have equal weights after resampling; instead, it ensures that the ratio between the maximum and minimum values in the returned weights does not exceed a preset threshold (typically controlled by a parameter). Its implementation first truncates and rescales the weights, then combines multinomial sampling with deterministic replication, so that the weight distribution is neither too concentrated nor too flat. In SMC decoding, this property means that low-weight particles can still be retained with nonzero probability, preventing lineages from being entirely eliminated in a single resampling step. Chopthin's computational cost is of the same order as multinomial resampling, making it easy to integrate into existing decoding pipelines.

Experimental Results: Gains in Both Coverage and End-to-End Accuracy

Researchers applied LP-SMC to two base models and evaluated it on mathematical reasoning and code generation benchmarks. Results show improvements across multiple dimensions.

The most direct metric is oracle coverage, i.e., the proportion of problems for which at least one particle produces the correct answer. Across all experimental settings, LP-SMC improved this metric, with gains ranging from 1.8 to 25.6 percentage points. This improvement indicates that lineage preservation indeed gives more problems a "chance" to be solved—even if the final selector does not pick the correct particle, the correct answer at least exists within the particle population.

In terms of end-to-end accuracy, when using a general reward model selector, LP-SMC achieved improvements in eleven of twelve settings. Specifically, it improved by up to 7.9 percentage points on LLaDA-1.5 and up to 18.3 percentage points on Dream-7B. Such magnitudes are considerable for inference-time methods, especially considering that no additional training is required.

A notable detail is that coverage gains persist when using external reward models. This means that diversity-preserving resampling and guidance signals each contribute independently to inference-time search effectiveness, rather than substituting for each other. In other words, even when the reward model provides strong guidance, preserving lineages still has additional value.

Implications for Inference-Time Search

The value of LP-SMC lies not only in numerical improvements but also in revealing an easily overlooked principle: the effectiveness of inference-time search depends not only on the quality of reward signals but also on whether the search process maintains sufficient candidate diversity. Multinomial resampling may appear to be standard practice, but its damage to lineages can be hidden and undetectable by conventional metrics such as ESS.

From an engineering perspective, LP-SMC's modifications are concentrated in the resampling step, requiring no changes to the model itself and no additional training, making it highly portable. For researchers and engineers looking to improve reasoning performance on existing diffusion language models, this is a low-cost direction worth trying. Of course, both Chopthin resampling and the weight floor introduce hyperparameters, which need to be tuned for specific tasks in practical deployment.

The paper's conclusions also point to a broader question: in sampling-based inference methods, how to define and measure "diversity" remains an open topic. ESS is insufficient; the number of lineages may be a more practical perspective. Following this line of thinking, more diagnostic metrics and improvement methods targeting the search process itself may emerge in the future.

One-line Summary

LP-SMC improves inference-time search for diffusion language models by preserving low-weight lineages, consistently boosting coverage and accuracy on math and code tasks.

Paragraph Summary

Diffusion language models' reasoning capabilities can be enhanced through inference-time search, and Sequential Monte Carlo (SMC) decoding is a promising approach that maintains a set of partially generated sequences and resamples based on reward signals. However, standard multinomial resampling discards lineages that score low early but remain promising, and the commonly used effective sample size (ESS) metric cannot reflect this lineage loss. To address this, researchers propose LP-SMC, introducing two designs: Chopthin resampling (constraining weight ratios after resampling rather than forcing equal weights) and an input weight floor (raising overly low weights to preserve recovery opportunities). On two base models, LLaDA-1.5 and Dream-7B, LP-SMC improves oracle coverage by 1.8 to 25.6 percentage points and achieves end-to-end accuracy gains in eleven of twelve settings, with maximum improvements of 7.9 and 18.3 percentage points respectively. Coverage gains persist under external reward models, indicating that diversity preservation and guidance signals contribute independently to search.