🤖 machine learning

On the Effect of Sampling Diversity in Scaling LLM Inference

This paper provides a systematic theoretical and empirical analysis demonstrating that introducing meaningful prompt diversity during LLM inference significantly improves Best-of- $N$ scaling performance by reducing error rates, while also establishing a diversity-fidelity trade-off principle to guide effective sampling strategies.

Original authors: Tianchun Wang, Zichuan Liu, Yuanzhou Chen, Jonathan Light, Weiyang Liu, Haifeng Chen, Xiang Zhang, Wei Cheng

Published 2026-08-11

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Tianchun Wang, Zichuan Liu, Yuanzhou Chen, Jonathan Light, Weiyang Liu, Haifeng Chen, Xiang Zhang, Wei Cheng

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a really tricky puzzle, like a complex math problem or writing a piece of code. You have a super-smart robot friend (a Large Language Model) who can help you. But here's the catch: if you ask the robot the exact same question in the exact same way ten times, it might give you ten answers that all look almost identical. They might all be wrong in the same way, or they might all get stuck in the same little corner of the solution space. This is like asking a friend for directions ten times and getting the same wrong turn every time because they are thinking in a loop.

To fix this, scientists have discovered a trick called "scaling inference." Instead of just asking the robot once, you ask it many times and pick the best answer. But to make this work, you need the robot to explore different paths, not just the same one over and over. This paper dives into a specific question: How do we make the robot's answers more different from each other without making them worse? The researchers found that if you nudge the robot's thinking with slightly different, but still relevant, hints, it explores a much wider world of possibilities and finds the right answer much more often. However, they also discovered a trap: if you try to pick the "most popular" answer among all the tries, all that hard work exploring new paths might actually vanish, and you won't get any better results.

The Great Idea Hunt: Why Mixing It Up Helps Robots Think Better

So, you've got this super-smart AI robot. It's great at writing stories, solving math, and coding. But sometimes, when you ask it a hard question, it gets stuck in a rut. It's like a dog chasing its own tail; it keeps running in the same circle, generating the same kind of answer over and over. In the world of AI, this is called a lack of "diversity."

The researchers behind this paper wanted to know: What happens if we force the robot to break out of that circle? What if we ask it the same question, but we tweak the way we ask it just a little bit? Maybe we tell it, "Imagine you are a strict math teacher," or "Think like a creative writer," or even just give it a slightly different way to phrase the problem. This is called "sampling diversity."

The big idea is simple: If you ask the robot to try 100 different ways to solve a problem, and those 100 ways are all very different from each other, you have a much better chance that at least one of them will be the correct answer. This is the "Best-of-N" strategy: try many things, pick the best one. But the million-dollar question is: How do you make those 100 things different without making them silly or wrong?

The Sweet Spot: Not Too Boring, Not Too Weird

The authors went on a hunt to find the perfect "nudge." They tested different ways to shake up the robot's thinking.

First, they tried irrelevant ideas. Imagine asking a robot to solve a math problem, but you tell it to think about baking a cake first. That's just noise. It doesn't help. The robot gets confused, and its answers get worse.

Then, they tried exact repeats. Imagine asking the robot the same question ten times with the exact same words. It just gives you the same answer ten times. No new ideas, no better results.

But then, they found the Sweet Spot. They tried giving the robot "task-aligned" ideas. For a math problem, they might say, "Think about breaking the problem into smaller steps," or "Consider using a specific theorem." These hints were different enough to make the robot explore new paths, but they were still about the math problem itself.

The results were amazing. When they used these "just right" hints, the robot's success rate went up significantly. For example, on a coding test called HumanEval, using a strategy called "Dual" (where a second robot helps generate ideas) improved the success rate by 4.7% compared to just asking the robot normally. On a math test called MATH, the improvement was 8.2%. On a reasoning test called MMLU-Pro, it jumped 10.8%.

The paper suggests that there is a "diversity-fidelity trade-off." You want the hints to be different enough to create new paths (diversity), but not so different that they ruin the quality of the answer (fidelity). It's like adding spices to a soup: a little bit makes it delicious, but too much makes it inedible, and no spices at all makes it boring.

The Trap: Why "Voting" Can Kill Your Success

Here is where the story gets a twist. The researchers also looked at how we pick the final answer. Usually, when you have 100 different answers, you might think, "Let's see which answer most people agree on!" This is called majority voting. If 51 out of 100 robots say "The answer is 42," then 42 must be right, right?

The paper says: Not so fast.

They proved mathematically that if you use majority voting, all that hard work you did to make the answers different might be wasted. Why? Because majority voting only works if the most common answer is the right one. But if you make the answers diverse, you might spread the votes out. The right answer might be unique and brilliant, but if it only appears 5 times out of 100, and a wrong answer appears 20 times, majority voting will pick the wrong one.

In their experiments on the MATH dataset, they found that when they used majority voting, the fancy diversity tricks did not help and sometimes even made things worse. The paper explicitly rules out majority voting as a good strategy when you are trying to use diversity to find a single correct answer. It's like a jury where everyone is trying to be unique; if they all vote for different things, you never reach a verdict.

When Does This Magic Work?

The researchers didn't just stop at finding the trick; they tested it everywhere to see if it holds up.

Temperature: They tested the robot when it was "hot" (very random) and "cold" (very strict). The diversity tricks worked in both cases, giving extra boosts on top of whatever the temperature was doing.
Thinking Steps: They tried it with "Chain-of-Thought," where the robot talks through its steps. The tricks still worked, giving a 7.4% boost on a hard coding test.
Who is the "Thinker"? They used different robots to generate the ideas. They found that a smarter "thinker" robot made the whole system better.
How many ideas? The more unique ideas they injected, the better the results. Using 100 different ideas was better than using just 1.

However, they also noticed that this trick works best for weaker robots. If the robot is already super smart (like the biggest, most powerful models), the extra boost is smaller. It's like giving a genius a map; they probably already knew the way. But for a smart-but-not-genius robot, the map helps a lot.

The Bottom Line

This paper is a guidebook for anyone trying to get the most out of AI robots. It tells us that:

Diversity is good: Making the robot try different approaches helps it find the right answer.
Be careful with the nudge: The hints you give must be relevant. Too weird, and it fails. Too boring, and it doesn't help.
Don't just vote: If you want to find a single correct answer, don't just pick the most popular one. Pick the single best one from all the diverse attempts.
It's a tool, not a magic wand: It works best when you have a budget for computing power and when you use it on models that aren't already perfect.

The authors didn't just guess; they ran hundreds of experiments and built a mathematical theory to back it up. They showed that by carefully mixing up how we ask questions, we can make AI smarter, faster, and more reliable, without needing to build a bigger, more expensive robot. It's a reminder that sometimes, the best way to find the right answer is to ask the question in a hundred different ways.

Technical Summary: On the Effect of Sampling Diversity in Scaling LLM Inference

Problem Statement

Large Language Model (LLM) scaling inference aims to improve performance by increasing computational resources at test time (e.g., generating multiple candidate solutions and selecting the best one) rather than increasing model parameters. While non-determinism in LLMs (arising from stochastic decoding, precision limits, and concurrency) is often viewed as a nuisance to be eliminated, this paper posits that such variability is a critical asset for test-time scaling.

The core problem addressed is the "local cluster" trap in standard Best-of-N sampling. When an LLM is repeatedly sampled using the same prompt, the outputs often converge to a narrow set of similar solutions due to post-training objectives that prioritize a single correct answer. This concentration limits the exploration of the solution space, preventing the model from discovering correct answers that lie outside the immediate local cluster. The paper investigates how to systematically introduce sampling diversity to break these clusters and improve the probability of finding a correct solution, while avoiding the degradation of solution quality (fidelity).

Methodology

Theoretical Framework

The authors establish a theoretical perspective to explain why solution diversity improves Best-of-N performance. They formalize the sampling process using a hybrid diversity policy where each attempt is configured by a base decoding mode $\eta$ (e.g., temperature, seed) and an auxiliary diversity source $\xi$ (e.g., prompt perturbation).

Two key hypotheses are posited:

Dispersion (Variation): Auxiliary diversity (like prompt perturbation) induces variation in the success probability of solutions. If the auxiliary source is varied, the failure log-probability of attempts should exhibit significant variation (measured by the first absolute central moment).
Fidelity: The auxiliary diversity source must not globally degrade the quality of generation. A perturbed prompt should perform nearly as well as the baseline prompt in terms of single-attempt success rates.

Based on these hypotheses, the authors derive Theorem 3.5, which demonstrates that introducing auxiliary diversity leads to:

Lower Asymptotic Error: The set of unsolvable instances (blind spots) shrinks as $N \to \infty$ .
Faster Convergence: The error reduction factor improves with richer diversity, leading to steeper gains in Best-of-N performance.

Diversity-Fidelity Trade-off Principle

The theory leads to a design principle: effective perturbations must strike a balance. They must be different enough to create exploration (boosting the dispersion metric $\hat{\mu}_1$ ) but faithful enough to avoid harming the quality of individual attempts (keeping the fidelity loss $\epsilon$ low).

Too Irrelevant: Perturbations that are completely off-topic degrade fidelity ( $\epsilon$ increases), negating diversity gains.
Too Similar: Perturbations that are mere rephrasings or verbatim repetitions fail to induce sufficient dispersion ( $\hat{\mu}_1$ is small), resulting in no performance gain.
Sweet Spot: Moderately relevant perturbations (e.g., task-aligned ideas) maximize the effective gain.

Perturbation Strategies

Guided by the trade-off principle, the paper instantiates two categories of perturbations:

Task-Level Perturbations: Independent of specific question content.
- Role Injection: Assigning specific personas (e.g., "mentor," "optimizer") to the model.
- Strategic Instruction: Providing stepwise guidance or heuristics.
Query-Level Perturbations: Directly tied to the specific question.
- Random Idea Injection (RandIdeaInj): Using a "thinker" model to generate task-related ideas injected into the prompt. Variants include Single (one model), Dual (separate thinker), and Diverse (pool of models).
- Random Query Rephraser (RandQReph): Restating the question via rephrasing or back-translation.

Experimental Evaluation

The authors evaluate these strategies across reasoning (MMLU-Pro), mathematics (GSM-Hard, MATH), and code generation (HumanEval, MBPP, APPS) tasks. They measure performance using Pass@k (code) and EM@k (reasoning/math) and analyze solution diversity using metrics like TF-IDF, BERT similarity, and Levenshtein distance.

Key experimental conditions include:

Varying sampling temperatures.
Using different "thinker" models for query-level perturbations.
Varying the cardinality (number) of perturbations.
Testing with Chain-of-Thought (CoT) reasoning.
Comparing against different verification methods: Oracle (ground truth), LLM-as-a-Judge (Outcome Reward Models), and Majority Voting.

Key Results

Diversity Improves Best-of-N: Empirical results confirm the theoretical prediction. Strategies that increase solution diversity (e.g., RandIdeaInj, Instruction injection) consistently outperform direct sampling. For instance, on MMLU-Pro, RandIdeaInj achieved a 10.8% improvement in EM@100 over direct sampling.
Non-Linear Relevance: Performance follows a rise-then-fall pattern relative to perturbation relevance. Moderately relevant perturbations yield the highest gains, while irrelevant or overly similar perturbations fail to improve or degrade performance.
Robustness: Diversified sampling remains effective across:
- Different sampling temperatures.
- The presence of Chain-of-Thought (CoT) reasoning.
- Verification via LLM-as-a-Judge (Outcome Reward Models).
Dependence on Resources: Performance gains scale with the strength of the "thinker" model (used for query-level perturbations) and the cardinality of the perturbation set.
Failure Mode of Majority Voting: The paper identifies a critical failure mode: Majority Voting. While Best-of-N benefits from diversity (as long as at least one correct answer exists), majority voting requires the correct answer to be the most frequent outcome. Theoretical analysis (Proposition 5.1) and empirical results on MATH show that introducing diversity can actually reduce the frequency of the correct answer if it spreads probability mass across incorrect alternatives, leading to no gain or even performance degradation under majority voting.
Model Strength: Diversified sampling yields larger relative gains for weaker models compared to already strong models, suggesting diminishing returns for the latter.

Significance and Claims

The paper claims to provide the first systematic theoretical and empirical analysis of how sampling diversity affects LLM inference-time scaling. Its significance lies in:

Theoretical Foundation: It moves beyond heuristic observations to provide a mathematical justification for why diversity improves Best-of-N scaling, defining the conditions (dispersion and fidelity) under which it works.
Design Principles: It establishes the diversity-fidelity trade-off, offering a concrete guideline for practitioners to design perturbation strategies that maximize exploration without sacrificing quality.
Identification of Limitations: It explicitly identifies majority voting as a failure mode for diversity-based scaling, warning against the indiscriminate application of diversity strategies without considering the verification protocol.
Practical Protocols: The work offers actionable guidelines, such as prioritizing task-level perturbations for cost-efficiency, using stronger thinker models when budgets allow, and avoiding diversity strategies for models that are already performing near-saturation.

In summary, the paper argues that while non-determinism is often suppressed, it is a vital resource for scaling inference. By carefully managing the trade-off between exploring diverse solution spaces and maintaining solution fidelity, practitioners can significantly enhance LLM performance across reasoning, math, and coding tasks, provided the verification method (e.g., Best-of-N vs. Majority Voting) aligns with the diversity strategy.