GuidedSampling: Steering LLMs Towards Diverse Candidate Solutions at Inference-Time

The problem with repeated sampling

Repeated Sampling (RS) is the simplest way to spend inference-time compute: sample the model n times and keep the best answer. It works — but the samples are far from independent tries. In practice the model tends to commit to the same underlying approach over and over, so most of the budget buys near-duplicates of one idea. When that idea is wrong, no amount of resampling saves you: measured across benchmarks, RS produces only ~2.7–6.7 genuinely distinct solution concepts per problem even at 100 samples.

How GuidedSampling works

GuidedSampling splits inference into two explicit phases, so that what approach to try and how to execute it are sampled separately:

Exploration phase

Given a question x, the model iteratively proposes high-level concepts, theorems, or strategies that could crack the problem: the k-th concept is sampled as c_k ~ p(· | x, c_1:(k-1)) — conditioned on all previous concepts. Seeing its own earlier ideas discourages repetition and encourages coverage. The loop stops at K concepts, or early once the model decides nothing genuinely new remains.

Generation phase

For every concept c_k, the model generates M full solutions conditioned on the question and that specific concept: s ~ p(s | x, c_k). The final candidate pool is the union over all concepts. Unlike Tree-of-Thoughts, exploration happens exactly once, up front — no per-step branching, so the overhead over plain RS is just the handful of concept-generation calls.

What the theory says

The paper derives bounds on when this decomposition beats direct sampling. The gist: performance hinges on the probability of surfacing at least one relevant concept, P(C_r | x) — a model that explores well converts extra compute into genuinely new attempts instead of duplicates. Two properties matter in practice:

• Recovery from irrelevant concepts. A bad guide doesn't sink the pool — an off-topic concept sometimes still lands on a correct solution (the appendix documents a case study of exactly this), and other concepts' budgets are unaffected.
• Compounding with compute. The gap over RS widens as k grows in pass@k: the more samples you can afford, the more the structured diversity pays off.

Inference results

Evaluated on Llama-3.2-3B-Instruct, Qwen2.5-3B-Instruct and Gemma-3-27b-it with n = 100 samples per problem, against plain repeated sampling:

Averaged over every model–benchmark pair the improvement is +16.01%; with the best-performing base model it averages +21.6% across benchmarks, peaking at +34.6%. Measured directly, candidate diversity rises ~17.6% (e.g. 3.87 vs 2.66 distinct concepts on HumanEval).

One honest failure mode: gains depend on the model being able to propose varied concepts. Qwen2.5-3B averages just 1.13 distinct concepts per HumanEval problem (Llama-3.2-3B manages 7.58), and there GuidedSampling actually underperforms RS — every sample gets funneled through the same idea. Swapping in Llama's concepts while letting Qwen write the code flips the result to +3.65% over RS (83.53 pass@50): the bottleneck is concept generation, not execution.

From inference trick to training signal

Because each trajectory carries an explicit concept, GuidedSampling doubles as a synthetic-data generator. From 10k OpenMathInstruct-2 problems, verified-correct trajectories were used to fine-tune Llama-3.2-3B-Instruct in two flavors: FA (final answer only) and CAA (concept + answer). Against models trained on RS, STaR, and ToT data:

Fine-tuning on GuidedSampling trajectories lifts pass@5 by ~9.7% on average over RS-trained models, and the trained models keep the diversity habit: distinct concepts per instance rise from 1.67 (RS) to 2.58 (FA) and 3.03 (CAA). Notably the biggest diversity gain shows up on GPQA-Diamond — a domain shift from the math-only training data — suggesting the exploration behavior itself generalizes.

Spending a fixed budget: K versus M

With a fixed total of 100 calls, how many concepts (K) should you explore versus how many solutions per concept (M = 100/K)? More exploration helps at first, then hurts once each concept's generation budget gets too thin — and at K = 0 the method degrades exactly to repeated sampling. The sweet spot is task- and model-specific; adaptive allocation is left as future work.

Limitations

• Main study covers three open-source models (plus a limited GPT-4o-mini / Phi-4-mini study); frontier proprietary models remain unexplored due to inference cost and lack of training access.
• The exploration-vs-generation trade-off has no universal setting — picking K adaptively per task is open.
• Weak concept generators can underperform plain RS (the Qwen-on-HumanEval case above).

Resources

Paper: ICLR 2026 — OpenReview · Code & data: github.com/DivijH/sampling_inference