LLM sampling stunts

I’ve noticed a number of interesting sampling tricks for LLMs that 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 it should look reminiscent of particle filtering except the likelihood is often a bit 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 comes 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 be a different model entirely).
3. Give each continuation an incremental weight based on how well it performs 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 doesn’t wait until the entire response is finished to discover failure. We 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:

• Strict JSON: incremental parses can bail early from impossible prefixes
• Prompt intersection: Likelihood or task score under each of several prompts
• Other stuff that doesn’t seem very practical to me.

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

The original SMC-steering formulation interprets 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 us from repeatedly counting the same “goodness” evidence at every token. In practice, this is never 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, as discussed above.
• 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 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.
• 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) of (in the model’s opinion) higher likelihood completions.