LLM sampling stunts

I noticed that there are a number of interesting sampling tricks for LLMs which seem related. The category in my mind is something like sampling from LLMs in ways that resemble classic particle methods, i.e. using the kinematics of multiple hypothetical trajectories to inform the next step(s). So! A new notebook!

What do I mean? I mean the Sequential Monte Carlo (SMC) steering trick for LLMs (Lew et al. 2023): instead of decoding one continuation—or keeping a fixed beam—we keep a small population of \(N\) candidate continuations, score them against a desired constraint or reward, then repeatedly resample promising candidates as generation proceeds. This can enforce constraints or steer semantic properties at inference time without retraining the base model, and should look reminiscent of particle filtering except the likelihood is even of a dog’s breakfast.

Relatedly, LLaMPPL (Lew et al. 2023) claims to be a Probabilistic Programming Language for LLMs based on this idea. It uses Sequential Monte Carlo (SMC) methods to perform probabilistic inference over the outputs of LLMs, which seems logical for prefix sampling; I’m a bit confused about how it works for infill sampling.

• genlm/llamppl: Probabilistic programming with large language models
• LLaMPPL Docs

Basic idea: We treat a completion \(y = (y_1,\ldots,y_T)\) as a trajectory sampled from the stochastic base model \(p_\theta(y\mid x)\), assuming that it is from something similar to, but not the same as, the target distribution that we want to hit,

\[ \pi(y\mid x) \propto p_\theta(y\mid x)\,R(y) \]

where \(R(y)\) is a score—e.g. “is valid JSON,” “satisfies this regex/grammar,” “answers both prompts,” “is non-toxic,” or “meets a programmatic verifier.”

We…

1. Maintain \(N\) partial completions.
2. Sample the next token (or tokens) for each from the “base” LLM (which in SD-SMC might a different model entirely)
3. Give each continuation an incremental weight based on how well it is doing under the constraint.
4. When weights become concentrated, resample: copy high-weight trajectories and discard weak ones.
5. Continue until completion; return a high-weight sample or sample from the final weighted population.

The point of distinction from simple rejection sampling is that SMC does not wait until the entire response is finished to discover failure. It can prune bad paths early and concentrate compute on promising ones.

The “trick” is worthwhile because sometimes we can write a prefix-aware potential—a function that scores a partial answer, not merely a final answer.

Examples:

For hard constraints, a particle that makes the remaining task impossible gets weight zero. For soft preferences, the weight rises smoothly for “better” paths.

The original SMC-steering formulation frames constrained language generation as posterior inference in a discrete sequence model. It reports capabilities including infilling, syntactic constraints, and “prompt intersection,” at a computational cost comparable to beam search.

LLM vibe-coded pseudo-code example:

particles = [("", 0.0, cache_i) for i in range(N)]  # text, log_weight, KV cache

for t in range(max_new_tokens):
    proposed = []

    for text, logw, cache in particles:
        token, logp, cache2 = sample_next_token(model, prompt + text, cache)
        text2 = text + decode(token)

        # potential should assess the prefix / remaining feasibility
        delta = log_potential(text2, t + 1) - log_potential(text, t)
        proposed.append((text2, logw + delta, cache2))

    particles = proposed
    weights = softmax([logw for _, logw, _ in particles])

    if effective_sample_size(weights) < N * 0.5:
        particles = systematic_resample(particles, weights)
        particles = [(text, 0.0, cache) for text, _, cache in particles]

answer = select_or_sample_final(particles)

A common formulation uses a sequence of potentials \(\phi_t(y_{1:t})\), with the incremental correction:

\[ \log w_t = \log w_{t-1} + \log \phi_t(y_{1:t}) - \log \phi_{t-1}(y_{1:t-1}) \]

That incremental difference prevents repeatedly counting the same “goodness” evidence at every token. In practice, this is never going to be the true target potential, because that is almost always super weird in token space.

There are a few adjacent “SMC for LLMs” ideas that have a similar shape.

• SMC steering: use particle filtering to steer toward constraints or a reward at inference time—the likely thing you mean.
• Power-SMC: sample from a sharpened sequence distribution \(p_\theta(y\mid x)^\alpha\), using parallel particles and token-level importance weights/resampling. It is positioned as a low-latency, training-free alternative to serial Metropolis–Hastings-style sampling (Azizi et al. 2026).
• SMC speculative decoding (SMC-SD): draft from a cheaper model, score blocks under an expensive target model, then reweight/resample rather than reject drafts token-by-token. The reported aim is faster inference while retaining close target-model behavior (Emara et al. 2026)
• Self-consistency: sample many complete reasoning trajectories and majority-vote the answer. This is not sequential resampling, but people sometimes loosely describe it as a particle-like trick. This one has the shape of, and relevance to, Reasoning LLMs.