Ensembling Language Models with Sequential Monte Carlo

This paper introduces a unified framework for ensembling diverse language models via $f$-ensemble distributions and proposes a byte-level sequential Monte Carlo algorithm to sample from these distributions, effectively overcoming challenges like mismatched vocabularies and biased approximations to improve performance on structured text generation tasks.

The Gist

Here is an explanation of the paper "Ensembling Language Models with Sequential Monte Carlo" using simple language and creative analogies.

The Big Idea: The "Super-Panel" vs. The "Average Opinion"

Imagine you are trying to solve a very difficult riddle. You could ask one smart friend for the answer, or you could ask a whole panel of experts.

• The Old Way (Local Averaging): Most current methods of combining AI models are like taking a vote. If Expert A says "The answer is 70% likely to be 'Apple'" and Expert B says "It's 30% likely to be 'Apple'," the system just averages them to get 50%. It does this word-by-word as the sentence is being built.

  • The Flaw: This is like asking a committee to vote on the first word of a story, then the second word, then the third. They might agree on the first word ("Once"), but by the time they get to the end, the story might make no sense because they never looked at the whole picture. They are "locally" agreeing but "globally" confused.

• The New Way (This Paper): The authors propose a smarter way to combine these experts. Instead of just averaging votes word-by-word, they want to create a Super-Panel that agrees on the entire story at once. They call this an "f-ensemble."

The Problem: The "Vocabulary Mismatch"

Imagine your panel of experts speaks different languages.

• Expert A speaks "Token-ese" (grouping words like "un-happy" as one unit).
• Expert B speaks "Byte-ese" (breaking everything down to individual letters like "u", "n", "h", "a").

If you try to make them vote together, they can't even agree on what the options are. Previous research spent years trying to translate their vocabularies so they could vote.

The Paper's Solution: Instead of translating, they decided to make everyone speak the most basic language possible: the alphabet (bytes/characters). They force all the models to think in terms of individual letters. This solves the vocabulary problem instantly, allowing any model to work with any other model, no matter how they were trained.

The Engine: "Sequential Monte Carlo" (The Hiker Analogy)

How do you get a group of experts to agree on a whole story without checking every single possible story (which would take forever)?

The authors use an algorithm called Sequential Monte Carlo (SMC). Here is a metaphor for how it works:

Imagine you are leading a group of 10 hikers (particles) up a mountain to find the best view (the perfect answer).

1. The Start: You send all 10 hikers up the trail.
2. The Checkpoint: Every few steps, the hikers look at the map (the AI models).
   • If a hiker is walking toward a cliff (a bad path), they get a low score.
   • If a hiker is walking toward a scenic overlook (a good path), they get a high score.
3. The Resampling (The Magic Step): This is the key. If one hiker is doing great, the group doesn't just keep walking; they clone that successful hiker. If a hiker is lost, they are sent home.
   • Result: The group naturally concentrates its energy on the paths that look most promising, rather than wasting time on dead ends.
4. The Goal: By the time they reach the top, the group has effectively "sampled" the best possible views based on the combined wisdom of all the experts.

Why Does This Matter? (The "Consensus" Effect)

The paper tested different ways to combine the experts' opinions. They found something surprising:

• The "Average" (Sum): If you just average the experts, the result is often mediocre. It's like a committee that tries to please everyone but ends up with a boring, safe answer.
• The "Consensus" (Product): If you require the experts to agree (multiplying their probabilities), the result is much sharper.
  • Analogy: Imagine a security system. If one guard says "This looks safe" and another says "This looks suspicious," an average system might let them both in. A consensus system says, "If anyone is suspicious, we stop." This filters out the "hallucinations" (made-up facts) and toxic outputs, leaving only the answers the experts truly agree on.

The Results: Better Answers, But Slower

The researchers tested this on tasks like:

• Writing code that fits a specific format (JSON).
• Sorting words alphabetically.
• Translating questions into database queries (SQL).

The Findings:

1. Synergy: Two mediocre models working together can beat a single great model, if they are combined correctly.
2. Better Approximations = Better Results: The more "hikers" (particles) you use in the SMC algorithm, the closer you get to the perfect answer. The paper shows that if you improve the quality of your sampling (get a better approximation of the "true" answer), your actual task performance goes up.
3. The Trade-off: This method is slower than just asking one model. It takes more computer power because it's running many simulations at once. However, for high-stakes tasks (like medical advice or legal coding), the extra accuracy is worth the wait.

Summary in One Sentence

This paper teaches us how to combine multiple AI models into a single, super-smart "Super-Panel" by forcing them to speak the same basic language (letters) and using a smart "hiker" algorithm to find the best answers that all the experts agree on, rather than just averaging their guesses.

Technical Summary

Here is a detailed technical summary of the paper "Ensembling Language Models with Sequential Monte Carlo".

1. Problem Statement

While practitioners have access to numerous language models (LMs) and prompting strategies, performance is highly sensitive to these choices. Classical machine learning suggests that ensembling (aggregating predictions from multiple sources) can yield better performance than any single model. However, applying ensembling to LMs during decoding presents two critical challenges:

1. Vocabulary Misalignment: Different models often use different tokenizers and vocabularies, making direct probability aggregation difficult.
2. Local vs. Global Bias: Existing methods typically aggregate next-token probabilities at each step (local ensembling). This results in sampling from a locally normalized, biased approximation of the true global ensemble distribution over strings.
   • Key Insight: A locally normalized product of token probabilities favors generic continuations that are probable at every single step, rather than complete strings that are globally probable under the intersection of constraints. This leads to a mismatch between the intended ensemble behavior (e.g., finding the intersection of two prompts) and the actual generated output.

2. Methodology

The authors propose a unified framework called $f$-ensembles combined with a Byte-Level Sequential Monte Carlo (SMC) algorithm to address these issues.

A. The $f$-Ensemble Framework

Instead of simple averaging, the paper defines a general class of ensemble distributions using a function $f: \mathbb{R}_{\ge 0}^K \to \mathbb{R}_{\ge 0}$.

• Definition: Given $K$ language models (potentials) $p_1, \dots, p_K$, the $f$-ensemble distribution $\Phi$ is defined as:
  $$\Phi(x) = \frac{1}{Z} f(p_1(x), \dots, p_K(x))$$
  where $Z$ is the normalization constant.
• Generalized Means: The authors focus on the family of generalized means parameterized by $\tau$, which unifies various aggregation strategies:
  • $\tau \to -\infty$: Minimum (Consensus-seeking, forces probability to the intersection of supports).
  • $\tau = 0$: Product (Product of Experts, concentrates mass on agreement).
  • $\tau = 1$: Sum (Mixture of Experts, standard probability averaging).
  • $\tau \to +\infty$: Maximum (Coverage-seeking, concentrates mass on the union of supports).
• Theoretical Basis: These functions are derived as the unique minimizers of weighted sums of $\alpha$-divergences between the ensemble and the base experts.

B. Byte-Level Sequential Monte Carlo (SMC)

To sample from the intractable global distribution $\Phi(x)$, the authors introduce a Sequential Monte Carlo (SMC) algorithm operating at the character/byte level.

1. Character-Level Mapping: To solve the vocabulary mismatch problem, all models are mapped to a shared character space. This allows the aggregation of probabilities for any string regardless of the underlying tokenization of the individual models.
2. Sequential Importance Sampling (SIS): The algorithm builds strings incrementally. At each step, it maintains a set of "particles" (partial strings) with associated importance weights.
3. Shaping Function: Since the target prefix probability $\vec{\phi}$ is intractable, the algorithm uses a tractable shaping function $\vec{\psi}$ (e.g., the product of prefix probabilities) to guide the proposal distribution.
4. Resampling: To prevent particle degeneracy (where most weight concentrates on a few particles), the algorithm employs a resampling step based on the effective sample size, reallocating computational resources to promising partial sequences.
5. Global Consistency: Unlike token-level averaging, SMC samples from the global distribution over strings, ensuring that the final output reflects the true ensemble distribution rather than a locally biased approximation.

3. Key Contributions

1. Unified $f$-Ensemble Framework: A theoretical generalization of model aggregation that moves beyond simple probability averaging to include consensus-seeking (product/min) and coverage-seeking (sum/max) strategies.
2. Byte-Level SMC Algorithm: A novel inference algorithm that enables consistent sampling from global ensemble distributions across models with mismatching vocabularies by operating in a shared character space.
3. Empirical Validation of Global vs. Local: Demonstration that local token-level aggregation fails to capture global constraints (e.g., prompt intersection), while global SMC sampling successfully approximates the intended distribution.
4. Synergistic Effects: Evidence that ensembling can improve performance beyond the best single model, particularly when using consensus-seeking strategies ($\tau \le 0$).

4. Experimental Results

The authors evaluated their method on three structured text generation tasks: JSON Schema Conformance, Word Sorting (Big-Bench Hard), and Text-to-SQL (SPIDER). They used models from three families: Llama 3.1, Qwen 2.5, and Phi-4.

• RQ1: Synergy: Ensembles improve performance when base models/prompts have complementary strengths (moderate performance on the same examples). Cross-model ensembles (combining different architectures) showed significant gains over single-model baselines.
• RQ2: Aggregation Strategy:
  • Consensus-seeking strategies (Product, Min) consistently outperformed traditional probability averaging (Sum/Mixture).
  • Probability averaging is theoretically bounded by the arithmetic mean of the base models' accuracies. In contrast, consensus-seeking strategies can exceed the performance of the best individual model by concentrating probability mass on the intersection of correct outputs.
• RQ3: Approximation Quality:
  • There is a strong positive correlation between the quality of the posterior approximation (measured by estimated log marginal likelihood) and task performance for consensus-seeking ensembles.
  • Better approximations (achieved via more particles in SMC) lead to measurably higher accuracy for Product and Min ensembles.
  • Conversely, coverage-seeking strategies (Sum, Max) showed weak or negative correlations, as their performance is inherently limited by the base model averages.

5. Significance and Impact

• Beyond Token Averaging: The paper challenges the standard practice of token-level probability averaging, showing it is a biased approximation that fails to capture global constraints.
• Handling Heterogeneity: By operating at the byte/character level, the method bypasses the difficult problem of token alignment, making it applicable to ensembling any combination of LMs regardless of their tokenizer.
• Controlled Generation: The framework provides a principled way to "steer" generation. For example, using a product ensemble allows for strict intersection of constraints (e.g., "physicist" AND "author"), which is crucial for controlled generation tasks.
• Trade-off: The method introduces inference-time computational overhead (due to maintaining multiple particles and resampling), but the authors argue this is justified for high-stakes tasks where output quality and constraint satisfaction are paramount.

In summary, this work establishes that global ensemble distributions sampled via Sequential Monte Carlo offer a superior alternative to local token-level aggregation, enabling more robust, synergistic, and constraint-compliant text generation.