GuidedSampling: Steering LLMs Towards Diverse Candidate Solutions at Inference-Time
Authors: Divij Handa
Mihir Parmar
Aswin RRV
Md Nayem Uddin
Hamid Palangi
Chitta Baral
Venue: ICLR 2026 Poster (2026)
Keywords: Inference-time algorithms
LLMs
Primary area: generative models

Abstract: Repeated Sampling (RS) is a simple inference-time algorithm that has been shown to improve model performance on complex tasks. Although it is an effective way of scaling inference time, it often struggles to generate diverse solution candidates, frequently relying on the same underlying approach to solve the problem and thus producing redundant samples. To address this limitation, we propose a new inference algorithm, GuidedSampling, which decouples the exploration and generation phases during inference, increasing diversity of generated candidate solutions. The exploration phase identifies multiple concepts that can be utilized to solve the problem, while the generation phase applies a specific concept to provide final solution candidates. We first define the theoretical bounds of GuidedSampling and then empirically demonstrate that it improves the performance of base model at pass@50 by on an average $\sim21.6$% across various benchmarks compared to RS. Furthermore, models trained on trajectories of GuidedSampling exhibit substantial performance improvements at pass@5 by on an average $\sim9.7$%, compared to models trained on traditional RS. Additionally, models trained with GuidedSampling increases the average number of concepts per instance ($1.67 \to 3.03$), yielding a diverse set of candidates than traditional RS.

Published as a conference paper at ICLR 2026
GUIDEDSAMPLING, STEERING LLMs TOWARDS DI- VERSE CANDIDATE SOLUTIONS AT INFERENCE-TIME
Divij Handa'
Mihir Parmar Aswin RRVI
Md Nayem Uddin
Hamid Palangi*
Chitta Baral
Arizona State University 2 Googge
{chanda, mihirpa mihirparmar, cbaral]easu.edd
ABSTRACT
Repeated Sampling (RS) simple inference-time algorithm that has been shown to improve model performance complex tasks. Although it is an effective way of scaling inference time, it often struggles to generate diverse solution candi- dates, frequently relying on the same underlying approach to solve the problem and thus producing redundant samples. To address this limitation, we propose a new inference algorithm, GUIDEDSAMPLING which decouples the exploration and generation phases during inference, increasing diversity of generated candi- date solutions. The exploration phase identifies multiple concepts that can be uti- lized to solve the problem, while the generation phase applics a specific concept to provide final solution candidates. We first define the theoretical bounds of GUID- EDSAMPLING and then empirically demonstrate that improves the performance of base model at pass @5 by average 21.6% across various benchmarks compared to RS. Furthermore, models trained on trajectories of GUIDEDS AM- PLING exhibit substantial performance improvements pass @5 by age ~ 9.7%, compared to models trained on traditional RS. Additionally, models trained with GUIDEDSAMPLING increases the average number of concepts per instance (1.67 + 3. 3.03), yielding diverse set of candidates than traditional RS.
INTRODUCTION
Recent advances large language models (LLMs) have shown that scaling model size and training data can lead increasingly capa- ble systems across diverse domains, including mathematical reasoning, scientific analysis, and code generation (Kaplan al. 2020). How- ever, scaling models indefinitely is becoming increasingly infeasible due to the requirement of more data for training ever-larger models Villalobos al. 2024). As result, a growing body of work has shifted focus to alternative ways of boosting pot by mak- ing models larger, but by making better use of available compute during inference (Hosseini
MATH
GPOA- Diamond
HumanEval
+26.8%
Olympiad
+4.0%
Repeated Sampling GurDenSAMPL TMG
10
20
30
50
70
80 90
Pass@ Score (%)
Figure I:
Pass@50 improvements with best per- forming base model using GUIDEDSAMPLING.
et al. 2024 Kumar et al. 2024 Lightmann et al.
2023 Brown al. (024). Several studies now suggest that allocating additional compute at infer-
ence time can lead to larger performance gains than spending that compute to train bigger models
(Snell et al. al. [024 Wu 2024). This has led a fundamental shift improving the performance of inference-time algorithms (Muennighoff et al. 2025 Ghosal et al. 2025).
Recently, various inference-time algorithms have been proposed (Wang et al., 2022 Yao et al,
2023 Zhang al. 2024). Among them, repeated sampling (RS) (Cobbe al. 2021
one of
Now at Google
'The code and data available httpss///githib.ccom//////////// http:///.....ooo/oooo//aaaaaaaaa

---

Published as a conference paper at ICLR 2026
Limited Exploration
Repeated Sampling
Inconsistent Generation
Solution 1
typing import
Question (e.g. HumanEval)
000 Solution Generator
def perse music/music string: str) -> Listini]:
Ingut string representing musical notess in special ASCII
Approach
Solution
tormet.
N Generated Resporses
from typing Import List
integers corresponding to how many beets does each not last.
string and return
parpp_errseeeeeeeeeeee cevre__msso/mmsiccco stringg str) Listjinjj
Hore Iagend:
GUIDEDSAMPLING
"o' whole note, lasts four beats
"I" qu-tee note, lasts one best
'or- half note,
beats
ooo Concept Generator
Concept Trie Data Structure
Generated
Solution Generator
Responses
Exemple:
Concapt
parse_ cirra__msicoooooo | d)
Sol.
Sol.
G Concapts
2, 1.1.1.2222.211...
class TrieNode:
class TrieNode: (salf)
Concepts
(sof):
Forced Exploration Fixed Generation
Loop
seif chilcchidrann = #
seif.chidren 9
GUIDEDSAMPLIN enhances exploration during inference by first generating set of diverse concepts or theorems to guide subsequent generations of solutions. Unlike repeated sampling (RS), where the model generates the final solution, GUIDEDSAMPLING separates these phases.
Figure 2:
the most widely used inference-time algorithms, where multiple outputs are sampled for the same input prompt. Traditional RS "implicitly" combines two phases: exploration, which we define as identifying the diverse theorems concepts used in solving given question, and generation, where the LLMS use the identified concept and try to generate several candidate solutions for the problem. However, despite its simplicity, traditional RS suffers from lack of exploration (Brown et al., 2024). due to LLMs being traditionally trained to generate a single correct response for every imput (Chow ct al. 2024). This leads RS to generate solutions with the same underlying concepts rather than thorough exploration of the solution space. To address this limitation, we propose inference-time algorithm, GUUDEDSAMPLING generation of final solutions. We define theoretical bounds for GUIDEDS AMPLING ($3.3), and then empirically demonstrate how training LLMs on such trajectories shows significant pass @k gains.
designed to decouple the exploration of diverse concepts from the
AMPLING (Figure 2 first explicitly explores diverse concepts that can be used to solve a given question. For our experiments, we define concepts the names of the theorems that can be utilized for solving questions (examples in Appendix ( In the second phase, these concepts guide the generation of complete candidate solutions. This decoupling the key reason that GUIDED- SAMPLING enhances the diversity of solution candidates generated during inference, and also gives explicit control over exploration. As illustrated in Figure [ our experiments on Llama-3.2-3B. Instruct (Grattafiori et al. (024) and Qwen2.5-3B-Instre at pass @ 50 on MATH for mathematical reasoning (Hendrycks et al. 2021 GPQA-Diamon
(Yngg et al. 2024) show an improvement
for
scientific reasoning (Rein al.) 2024). HumanEval for Python code generation (Chen al. 2021),
and OlympiadBench for complex mathematical and scientific reasoning (He et al.) 2024). Further
analysis by extracting the concept present in the candidate solutions generated by base models ($3.1)
reveal that GUIDEDSAMPI AMPLING generates 17.63% more diverse candidate solutions compared to RS.
For instance, consider a problem from MATH: "Find the maximum value of + over all real
numbers and y.". For this problem, we sample 1000 solutions using traditional RS and GUIDED- SAMPLING. Our detailed analysis of concepts extracted from these candidates shows that 892/1000 uses the "AM-GM inequality" concept to solve the problem, consistently leading the incorrect solution due to over-utilizing the same theorem. In contrast, only 77 1000 candidates from GUID- EDSAMPLING use this theorem, dedicating the remaining compute exploring other theorems such as "Cauchy-Schwaat Inequality", "Trivial Inequality". and "Chebyshev' 's Inequality".
Our other contribution is to GUIDEDSAMPLING to improve LLM post-training. We demonstrate that fine-tuning LLMs on trajectories generated by GUIDEDSAMPLING outperforms models trained trajectories from traditional RS, Tree-of-Thouuht (Yao et al. 2023), and other
2

---

the other hand, works in an iterative Published as a conference paper at ICLR 2026
self-correction methods like Self-Taught Reasoner (STaR) (eelikman et al. 2022). ) We generate diverse solution trajectories using GUIDEDS OpenMathlnstruut-22 (Toshniwal et al. 2024), mathematical reasoning dataset. LLMs fine-tuned on this data exhibited a 3.43% 1 in pass @5 on the MATH benchmark. These fine-tuned models also demonstrate improved generalization, with pass gains out-of-domain benchmarks, GPQA- Diamond (6.17% 1), HumanEval (1.86% 1), and OlympiadBench (2.11% 1) compared to the strongest baseline. In summary, GUIDEDSAMPLING facilitates future research towards exploring diversity at inference- time and can effectively synthesize exploration-awes aware data for post-training.
on a random subset of 10k instances from
2 RELATED WORKS
Inference-Tinee Time Strategies Chain-of-thought (CoT) and its variants (Wei al. 2022 Kojima
et al. 2022) showed that guiding LLMs to produce intermediate reasoning steps during inference boosts performance on complex tasks such as mathematical reasoning. However, as reasoning chains become longer, CoT suffers from error propagation due to complex calculations (Chen et al. 2022)
To mitigate this, new methods have been proposed, e.g., Self-Consistency, which samples multi- ple CoT and then selects the most consistent answer through majority voting (Wang et al.) 2022)
Building upon these ideas, better search algorithms, such as the tree-of-thought (ToT) Yao et al.
2023), MCTS (Zhang al. 2024), and REBASE (Wu et al. (024), have been proposed, which enable LLMs to perform more deliberate problem-solvee solving by exploring multiple reasoning paths in tree structure. Several agentic systems (Parmar et al. 2025 Handa et al. 2025 Zhang al.. 2025
Kumbhar et al. 2025) have shown that performing multi-agen debate before generating a final solu- tion improves performance. Furthermore, recent work (Muennighoff al. (025) has extended the 'thinking' of models by introducing special tokens such as "wait" to improve performance. Finally, Ghosal al. (2025) has shown that simply sampling from model repeatedly outperforms such ap- proaches. In contrast to prior methods, GUIDEDSAMPLIE
generates a diverse set of samples with lower inference- cost than tree search Yao al., 2023). while achieving greater diversity than standard sampling approaches. Parallel to our work, Wang et al.) (2025) proposed Randldeahnjec- tion, which first generates a list of distinct ideas and then injects the generated list into the generation process to produce the final response. GUIDEDSAMPLING loop of generating concepts, adding them individually to generate the final output.
Synthetic Data w/ Inference- Time Algorithms Recent works have explored leveraging infer- ence strategies for generating high-quality synthetic training data and fine-tning models to improve their performance. For instance, Self-Taught Reasoner (STaR) (Zelikman et al., 2022) is an iterative method where an LLM is prompted to generate CoT rationales; those rationales that lead to cor- rect answers are then used as high-quality synthetic data to fine-tune the model, while those which lead to incorrect answers are passed back to model for refinement along with the correct final an- swer, effectively bootstrapping its reasoning abilities from small initial set. Similarly, RMSTRM (Singh et al.] 2023), building on principles of reinforced self-training (ReST), employs an iterative Expectation- Maximization-iiiiii framework. It uses Best-of-N (BoN) sampling to generate multiple candidate solutions for problems and then refines the model by training on this synthetically gen- crated data. Some works (Chow et al. 2024, Tang et al., 2025 Rrv al., 2025) have developed reinforcement learning methods that directly optimize for pass @k metrics, leading to significant gains in reasoning and code generation. Other methods, such as multi-agent fine-tuning (Subrama- niam et al., (025), train diverse agent models through debate and voting, while Gui et al. (2024) introduced BoNBoN Alignment, distilling the BoN distribution into a single model. While these strategies improve pass@k, they often do not explicitly manage the trade-off between exploration and generation. In contrast, our proposed GUIDEDS AMPLING method introduces a structured ex- ploration phase during training, explicitly balancing diversity and quality, and models fine-tuned with our trajectories outperform those trained using methods like BoN, STaR, or ToT.
GUIDEDSAMPLING
3.1 BACKGROUND
Traditional RS Repeated Sampling (RS) is a simple strategy to increase the inference-time per- formance of model by generating multiple samples from the model's output distribution. Let
3

---

Published as a conference paper at ICLR 2026
X {E1, D2 ................................ .N be set of input queries. For each imput X, draw & independent samples from the model-defined conditional distribution po(y z). i.e,
(e) po x), for I....,k
y
This process effectively scales the model's inference-time compute linearly with k. The theoretical appeal of RS lies in its potential achieve complete coverage of the output space as + co. For any output y" such that po(""
æ) > 0, the probability that it's sampled at least once after k samples:
Ps = po x=))*
This quantity monotonically increases with & and asymptotically approaches Thus, under the as- sumption that all valid outputs are assigned non-zero probability by the model, unlimited sampling ensures that the target output will be generated least once. This has led to several works adopting RS to generate solutions (Wang et al. 2022 Rozière et al. 2023 Li al. (022). Of course, unlim- ited sampling is impractical. The value of RS lies whether increased sampling leads to improved output quality within feasible compute budget. Also, several state that the lack of diversity in these
generated responses is the key limitation of scaling RS (Brown et al. 2024 Wang et al. 2025)
Diversity Analysis To quantify the lack of diversity in RS, we use Qwen2.5-32B-Inste Instruct Yang al., 2024) extract the core concept or theorem from each solution. We present the prompt for concept extraction in Appendix B.2 We find that solutions sampled using RS tend to rely heavily on a few underlying concepts to solve the problem, even with increasing the amount of compute. For instance, Llama-3.2- 3B-Inntt used an average of 2.75 different concepts while solving code generation ques- tions from the HumanEval benchmark, even with 100 candidate solutions. Figure 3 repre- sents the distribution of the number ques- tions for how many concepts are generated for fixed budget of 100 responses. We observe that in 64% of the questions, fewer than three concepts were used solve the questions, with 36.4% just using one concept.
4.4%
5.8%
36.4%
Number Concre
8.2%
13.1%
23.1%
Figure 3: Distribution of the number of con- cepts used by Llama-3.2-3B-Instuee didates. 37% of the questions are attempted with just one concept, while less than 36% of the ques- tions have more than two concepts.
for 100 can-
Tree-of-Thoughe (ToT) ToT represents
more sophisticated strategy for enhancing model performance in complex problem-solving tasks by explicitly exploring multiple reasoning paths Yao et al. 2023). ToT guides a language model to generate tree of "thoughts", where each thought is coherent sequence of text represent- ing an intermediate step towards solution. The model generates multiple candidate thoughts
T, = (t(.), , ( ,...,,m ....,,(()) from parent thought ty- Each of these candidate thoughts is then eval- uated, often by the LLM itself or separate verifier, ((((5) tp). to assess its promise. Search algorithms like Breadth-First Search (BFS) or Depth-First Search (DFS) are employed navigate this tree, allowing the model to look ahead, backtrack if a path seems unpromising, and explore different lines of reasoning (Long 2023). The theoretical strength of ToT lies in its potential to systematically explore a vast solution space, thereby increasing the likelihood of finding a correct or high-quality solution, especially for tasks where simpler methods like Chain of Thought (CoT) might falter due to their lincar, single-path reasoning. This structured exploration aims address issues like the lack of diversity in generated paths by deliberately generating and considering varied intermediate steps. However, this explicit generation and evaluation of numerous thought branches make tree-of-thought computationally intensive, with costs scaling with the number candidates explored at each step (m) and the depth of the tree (Yao et al. 2023).
While ToT solves the lack of diversity observed in RS (Appendix D). is significantly more com- putational explicit evaluation of each intermediate thought generated every step of the tree's
4

---

Published as a conference paper at ICLR 2026
expansion is required. To mitigate both the lack of diversity in the solutions and less computational cost, we propose GUIDEDSAMPLING, which we elaborate on the following sections.
3.2 OUR PROPOSED APPROACII
Our proposed inference algorithm, GUIDEDSAMPLING improves the diversity by separating ploration and generation into two distinct phases. This separation allows for finer control over the diversity of concepts that be used solve a problem, an aspect previous approaches like tra- ditional RS fall short of. Moreover, our method explores the concepts just once in the beginning, which leads better efficiency than the tree-of-thought strategy. Figure Saaree/hightt Llighhlgghts the differences between our strategy and RS. We describe these two phases of our strategy in detail below:
Exploration Phase The goal of the Exploration Phase to discover a diverse set of high-level ideas, concepts, or theorems that could guide the solution of a given question. We start with dataset or a set questions denoted by X, from which we sample a specific question x X work on. Given this question & and an LLM parameterized by 0, we aim to identify set of relevant concepts that could support downstream reasoning or problem-solving denoted as = {cI, C2.... CK ]. The process of constructing C' is iterative: the k-th concept is generated by conditioning on the original question x and all previously generated concepts c1,-.., Formally, this sampling process is expressed as:
Ck-1-
Ck ~ >>po- x C1:(k-1))
This iterative conditioning mechanism promotes diversity among the concepts, encouraging the model to explore different areas of the solution space rather than repeating similar concepts. The al- gorithm continues until either K concepts have been generated the model determines that more useful concepts can be produced-allowing for early stopping. The prompts used for exploration presented Appendix B.I and some concept examples are illustrated in Appendix C
Generation Phase Once the set of candidate concepts C = C1, C2,..., CK has been established during the Exploration Phase, the Generation Phase uses these concepts produce concrete solu- tions. For each concept с₁ E C, we generate M potential solutions. These solutions are sampled from the LLM, conditioned on both the original question and the specific concept cy:
Sk
(m) Sk
po(s x, ck)
M
m=1
Each completion $k represents full solution that uses the guidance provided by ck. The full set of candidate solutions thus S
(m)
U Sk.
This structured sampling strategy leverages the earlier exploration to guide the solutions more effec- tively. Instead of relying on unguided purely random repeated sampling, the model systematically explores multiple reasoning trajectories guided by diverse high-level concepts or theorems. This en- hances the diversity of candidate solutions, increasing the likelihood that least one solution will be correct. We formally define the GUIDEDSAMPLAN algorithm in Algorithm
3.3 THEORETICAL BOUNDS FOR GUIDEDSAMPLIC
Definition (Notation). Let x be the input prompt and y" be correct final solution. Let Thase (y x) be the base model's conditional probability of generating solution directly from x. the GUIDEDSAMPLING framework, we define:
c: An intermediate concept or theorem.
Cr: The set of " relevant" concepts that contain valid concept pointing towards the correct reasoning path y"
cconcepec x): The probability of generating concept c from prompt x.
ssolution x, c): Probability of generating solution given the prompt x and concept c.
I(y:c I z); sample-wise mutual information between y and c conditional on æ. This represents the additional information contributed by the concept in predicting y.
5

---

Published as a conference paper at ICLR 2026
By intuition, solving question becomes easier if we know good question. To elaborate on the performance bounds of GUIDEDSAMPLING, we make the following assumption:
"hint" for
Assumption 1. For any "relevant" concept с E Cr, conditioning on it strictly increases the proba- bility of generating a correct solution y". That is, there exists an amplification factor ke 1 such that:
Tbase 22, 2 kic Thase (y" [x)
The above assumption is based on the intuition that I(yse | x)) 0, ie.. any "relevant" concept strictly increases the probability of generating the correct final response. For "irrelevant" concepts
(c E C.-). the assumption doesn't 't hold. We also bridge the intuition to above assumption in Appendix A.1 Following the above assumption, we now state our main theorem:
Theorem 1.
Let "y | I) be the probability of generating correct solution through Repeated Sampling and Pas(y" (y' \ x)) be the probability of generating a correct solution through GUIDED-
SAMPLING. Under Assumption Pas(y" |x) > PRS(V" x.) iff the following condition holds:
(kmin P(C, 1x) 1)- Pns xx) + Σ (eoncepp(c) x² Thase (y" (..C) (2,C)>0
eEC.
where P(Cr x) kmin > 1 is the amplisication factor in accordance with the above assumption.
=x Teoncope (c x) is the probability of generating a relevant concept, and
The condition derived in Theorem provides a formal basis for when GUIDEDSAMPLING outper- forms RS. We detail the proof in Appendix A.2 In practice, this condition is satisfied if one or more of the following pathways hold:
Recovery from Irrelevant Concepts If the second term, Eeçc, Teoncepe (c (r) Those (v" 2x, c). is sufficiently large. This corresponds to the scenario where the model generates a flawed or "ir- relevant" concept but still manages to produce the correct solution, y". While this is possible, observe empirically that it is a rare event. We detail one such case study in Appendix [ Therefore, for GUIDEDSAMPLING to be reliably superior, the following condition is more critical.
Sufficient Concept Coverage If first term, (kimin P(C, x)) 1) PRS(y" x)) > 0. Since the second term is probability distribution and will always remain 2 0, for the overall sum in equation to be positive, the first term should be positive. This holds when P(C, x)) >> 1/Kmin. This can be achieved either when the underlying model's probability of generating relevant concepts high (P(C, x) > 0), or when conditioning on relevant concept provides a significant probabilistic advantage for generating the correct solution compared to direct generation (Aimin >> 1). We em- pirically observe both of these to be true for most cases in study, but some models may lack this ability on certain tasks (e.g., Doven2.5-3B-Innttree on code generation).
3.4 POST-TRAINING USING SUUDEDSAMPLING
Synthetic data has become an increasingly effective tool for enhancing the reasoning capabilities of LLMs (Gupta et al.) 2023 Mitra et al. 2024 Chaudhary et al. (002)). In particular, inference-time algorithms are valuable for generating such data when the correctness of the final solution can be
programmatically verified Zelikman et al. 2022 Arora & Zanette 2025 Shao et al., 2024). We demonstrate that also as powerful synthetic data generation mechanism.
can serve not only as an effective inference-time strategy but
Let denote an input question, and = (cI,...,ck) be the diverse set of concepts generated for using exploration phase of GUIDeDSAMPL.NE For each concept C E C, we sample solution s S. We define two distinct settings for constructing synthetic training pairs (x:,y):
1. Final-Answer Only (FA): In this setting, we discard the generated concept and only use the final verified response s as the target output. This encourages the model to learn mappings from problem statements directly to correct answers, i.e. (x., v) (x,, s). The correspond- ing training objective is the standard fine-tuning loss:
LTA ((,e)))-Di [log Po x))]

---

Published as a conference paper at ICLR 2026
where DAA is the dataset constructed under the FA regime and Pg is the model's conditional distribution parameterized by 0.
2. Concept-Augmenteed Answer (CAA): the CAA setting, we construct an enriched target sequence that includes both the conceptual diversity and the final answer. Specifically, we concatenate the concepts C with one selected solution to form the training target:
(a, y) (x, concat (C, s))
This setting encourages the model internalize multiple reasoning strategies before com- mitting to one concrete solution path. The training objective becomes:
CCAA = -aaa.C.)--eess [log Po x)]
where DCAA the dataset constructed under the CAA regime. The prompt for CAA provided in Appendix B.3
4 EXPERIMENT SETUP
Baselines We showcase GUIDEDSAMPLING against Repeated Sampling (RS) showcase the better pass @k performance. For training. we compare models trained using Self-Taught Reasoner (STaR) (Zelikman et al. 2022), RS (Brown et 2024). and Tree-of- Tree-of-Thought (Yao et al. 2023).
Dataset We use test sets of MATH (for mathematical reasoning) (Hendrycks et al. 2021 GPQA- Diamond (scientific reasoning) (Rein et al., al.] 2024), HumanEval (code generation) (Chen al. 2021). and OlympiadBench (mathematical and scientific reasoning) (He et al. 2024) to measure the effec- tiveness of GUIDEDS MPLING. For training the models, we first randomly select 10k samples from the training set of OpenMathlnsttuutt22 (Toshniwal et al. 2024), math reasoning dataset. We then create reasoning chains using corresponding inference strategies and select the reasoning chains with correct final answer since ground truth is available to create corresponding training sets. We detail the fine-tuning setup in Appendix
Models and Metrics We evaluate two open-source LLMs our main study Llama-3.2-33 3.2-33B Instruct (Grattafiori et (0.4))222))) and B---n..--B--nstruuee (Yang et al. (024). We generate 100 responses using all models and report values until = 50. For finetuned models, we generate 10 responses and report values until & 5. Since experiments involve generating up to 100 responses, we also perform a limited study of other models in Appendix E To assess the performance, we use the pass @k metric, which is defined the expected maximum reward obtained from the i sampled responses out of n, where c are correct candidates. Formally, is defined as:
pass@k = E
RESULTS AND DISCUSSION
GUIDEDSAMPLING pass @k performance As shown in Figure 4 GUIDEDSAMPLING signifi- cantly outperforms RS across the majority of models and benchmark combinations. As an edge case, only one combination of Qwwen2.5-3B-Instrrect and HumanEval shows degradation in perfor- mance due to weak concept generation. Averaging across all models, we observe pass p 550 im- provements of 21.8% on MATH, 11.87% on GPQA-Diamond, 11.28% on HumanEval, and 3.08% on OlympiadBench. These results highlight that structured exploration enables more effective use of limited compute. However, the gains from GUIDEDS AMPLING are not uniform across all tasks and models. While Siven2.5-3B-Inntte
achieves strong improvements on MATH, its performance on HumanEval worsens compared to traditional RS. Upon closer analysis, this drop stems from Qwen's limited ability to generate diverse concepts for coding during the exploration phase. As mentioned in $3.3 a weaker probability of generating good concepts, P(C, [r), results in lower performance of GUIDEDSAMPLING problem, indicating that nearly all sampled solutions are guided by the same idea. This lack of versity not only fails to leverage the core strengths of GUIDEDSAMPLING but also dilute the
On average, Qwen produces only 1.13 distinct concepts per HvmanEval

---

Published as a conference paper at ICLR 2026
MATH-500
GPQA-Diamond
HumanEval
Olympiad Bench
-6..00%
64.14%
79.27%
37.14%
60
57.00%
60
56.57%
33.53%
pass@k
52.20%
47.98%
30
60-
40
52.44%
24.73%
4.
40-
20
31.10%
10-
50
50
0
50
50
75
-7.60%%
48.99%
80
79.88%
40
39.89% 89%
38.35%
40
75.61%
pass
50
40.80%
47. 97%4
32.83%
30
24.40%
20
20
25
10.10%
47.56%
40
10-
0
50
83.80%
92.42%
94.51%
43.52%
pass@k
80-
81.00%
80.00%
80
68.18%
70.20%
90-
83.54%
40
35.27%
60
80
33.19%
30
75
40
68.29%
50
50
0
50
k (# of Attempts)
k (# of Attempts)
(# of Attempts)
k (# of Attempts)
Traditional Repeated Sampling
GUIDEOSAMPLING
Tree-ofTThought
Figure 4: GUIDEDSAMPLING forces exploration during inference-time, resulting in 16.01% aver- age pass@k improvement compared to repeated sampling. We observe an average improvement of 21.8% on MATH, 11.87% on GPQA-Diamond, 11.28% on HumanEval, and 3.08% on Olympiad- Bench. For GUIDEDS AMPLING, we choose the optimal value of K (from Fig. (5) that maximizes the performance. First row: 1lama-3.2-3B-nnstnuu Second row: Qwen2.5-3B-Inns Gemma-3-27ba
Third row:
model's 's effectiveness by forcing the model to follow a particular concept. In contrast, Llama-3.2- 3B-IIsttuct generates 7.58 unique concepts on average on HumanEval, enabling richer exploration and stronger performance. These results underscore that the successful application of GUIDEDS PLING depends critically on the model's ability generate varied and relevant high-level ideas. To validate whether the observed drop is due to poor concept generation or Qwen's 's inability to generate the correct solution from the concept, we use the concepts generated by 3.2ma-3.2-3B-mmm generating the final answer. Using stronger concept generator yields a pass @ 50 performance of 83.53%, a 3.65% improvement from RS. The smaller gains of Qwen on OlympiadBench can be at- tributed to the benchmark's high difficulty (olympiad-level problems) combined with the relatively small model size (3B). Nevertheless, GUIDEDSAMPLING still yields measurable improvements.
for
The higher performance of SRIDEDSAMPPING is due to K concepts being generated. In practice, this value is far lower than the number of samples generated (100 in our case). Moreover, as the com- pute increases (inereasing & for pass @ k), observe that the performance gap between Repeated Sampling and SUUDEDSAMPLINE
increases in most cases (Fig. 4. suggesting that GUIDEDS AM- PLING benefits more with increased compute. This leads us to believe that when computational resources are sufficient, a small overhead of sequential calls for generating concepts might be a beneficial tradeoff for better performance.
Diversity in GUIDEDSAMPLING To measure the diversity of candidate solutions, we use 10n2255-32-IIsttree (Yang et al. 2024) to extract the core concept or theorem. We then com- pute the number of distinet concepts generated. On average, RS produces 3.54, 6.72, 2.66, and 3.25 distinct concepts on MATH, GPOAADiamond, HumanEval, and OlympiadBench, respectively. GUIDEDSAMPLING produces 3.66, 7.66, 3.87, and 3.81 distinct concepts, improving the diver- sity by an average of 17.63%. We also found the diversity gains from GUIDEDSAMPIA are model-specific. We find that Llama-3.2-39 332-3BB-Instrue generates 3.7x more unique concepts on av- erage compared to Qwen2.5-3B. -I-structt with this gap ranging from 2.82x on 5.12x on HumanEval. This suggests that model architecture and pretraining influence the capacity for generating novel reasoning strategies. We show examples of generated concepts in Appendix C
to
8

---

Published as a conference paper at ICLR 2026
MATH
GPQA-Diamond
HumanEval
OlympiadBench
79.27
pass@55 (%)
64.14
75.00
37.5
55.80
55
$2.30
60
58.08
70
35.0
32.69
33.30
60
55
02
44
50
30.0
77.00
79.60
50
48.99
85
42.5
passi (96
45.45
73.98
39.80
45
42.
03
80
75.61
40
38.
37.69
40
73.78
73.05
37.5
70
35.0
0
3
12
15 18
21
9
12
15
18
21
3
6
9
15 concepts)
12
18
21
0
18 K (No. of concepts)
3
6
12 15
of concepts)
(No.
concepts)
K (No.
100
pass@60 (%)
92.42
90.91
100
94.51 94,51
41.21
43.52
42.20
86
81.00
87,87
83,60
83.80
90
40
80
83
70
3533
70
80
12 (No. of concepts)
K (No. of concepts)
K (No. of concepts)
K (No. of concepts)
Figure 5: Pass@50 performance variation with different exploration (number of concepts K) and generation (samples per idea .M) compute allocations, given fixed total compute of 100 calls (M = 100/ K). Increasing exploration iitiillly helps, but performance declines when the generation budget per idea becomes small. At K GUIDEDSAMPLING becomes traditional RS. First row: 1l-ama-.2-3B-IIntttt Second row: Qwen2.5-31 2ren2.5-3B-Instruct Third row: Gemma-33-77bit
Trade-off between Exploration and Generation A key design choice in GUIDEDSAMPLING is the allocation of the limited inference compute budget TC between the exploration phase (number of concepts K) and the generation phase (number of samples M per concept, where M = IC/ K).
The number of distinct concepts K directly controls this trade-off: a larger K encourages broader exploration of different approaches, but consequently reduces the compute available for generating solutions using each approach (i.e., smaller M)). Conversely, a smaller K allows for more gener- ations using fewer concepts. As demonstrated in Fig. 5] increasing exploration by increasing K initially boosts performance in most cases by uncovering more diverse, potentially successful strate- gies. However, beyond an optimal point, performance may decline as the generation budget M for each concept becomes insufficient thoroughly develop any single approach.
During the concept generation phase of GUIDED- SAMPLING, concepts are generated iteratively. To determine the contribution of the k-th concept across all questions that produced least & concepts, analyzed all models and benchmarks men- tioned in $ which contains total of 1772 questions. We observe a minor decline from A: = 1 to 5 (19.8% 16.2%). This observation suggests that earlier concepts suggested by the concept gener- ator are better than later ones. However, for concepts with index 2 (i.c., when more exploration needed). higher performance variance due to sharp decrease coverage is observed. E.g., only 72 out of 1772 questions reach l 9, meaning there are fewer samples with A 2 6 concepts. This results in variations in performance, with higher performance being observed for many such cases (e.g., 52.05% performance for k 14, due to just 23 instances). Thus, although the earlier concepts are beneficial, later ones (k 2 6) also contribute to increasing performance, but for a small number of instances that require significant exploration. Henee, for the overall success of GuidedSampling, even the later ones are also important, but the earlier ones play a major role. Individual performance values provided in Appendix
Performance of Earlier Later Concepts

---

Published as a conference paper at ICLR 2026
Dependence of GUIDEDSAMPLING on Well-defined Concepts Theorem states that for a "rel- evant" concept c, conditioning on с increases the probability of generating the correct solution. However, in domains such commonsense reasoning, which involve more imprecise, vague, and uncertain knowledge, defining such concepts is difficult. Hence, the condition stated in Theorem I i.e., P(C, (z) >> O, might not be satisfied. Applying GUIDEDSAMPI.NG to Qwen2.5-3BB-Instne on CommonSenseQAA (Tamorr et al., 2019), commonsense benchmark. The model is prompted to generate a general idea that could help solve the question (not task-specific concept, since those are lacking in the commonsense domain). On such domains, GUIDEDSAMPLIN
underperforms against Repeated Sampling by 3.28% (pass@50), Based on this, we believe that GUIDEDS PLING has better chance of succeeding when concepts can be formulated efficiently. More details Appendix
Final Answer Selection via Majority Voting To select final solution after sampling multiple times, we use the majority voting technique, where most common solution is selected as the final answer. AMPLING achieves an average accuracy of 35.87% compared to Repeated Sampling (32.80%) and Tree-of-Theee ofoouuhht (26.26%). Detailed accuracies in Appendix
Finetuning models on GUIDEDSAMPLING trajectories Models fine-tuned data synthesized via GUIDEDSAMPLIN significantly outperform those trained using data from other inference time algorithms, as illustrated in Table Notably, when the models asked to produce more responses (pass@5), a bigger improvement in performance is observed. On average, the CAA setting yields 7.13% pass@5 improvements compared to the RS, while FA shows 5.64% pass @5 improvements against RS. Models trained using trajectories from Tree-of-Thougee performed better than RS as well, showing 4.37% improvement, but still underperformed when compared against BUIDEDSAMPLIN FA (1.45%) and CAA (2.76%).
another explorative strategy,
Table Performance of Llama-3.2 3.i.--3..--B-iitiieee trained using different synthetic data creation strate- gies. FA: Using just the final answer for training the model. CAA: Using both the concepts and the corresponding final solution to create the training data.
Method
MATH
GPQA-Diamond
HumanEval
OlympiadBench
pass @1
p5
pass@1
pass@55
pass@1
pass @
pass@1
pass 5
Base Model
24.00%
33.20%
11.62%
28.28%
27. 27.44%
39.02%
11.32%
19.56%
RS
37.62%
44.78%
18.13%
40.08%
52.13%
55.78%
6.42%
10.83%
STaR ToT
36.60%
46.23%
16.61 %
38.41%
52.13%
57.35%
5.82%
10.62%
40.40 %
56.63%
16.77%
44.44%
35.73%
49.51%
9.19%
18.36%
FA (Ours)
29.88%
47.98%
20.20%
50.61% % 40.23%
48.17%
55.95%
11.21%
20.21
CAA (Ours)
38.00%
60.06 %
15.66%
53.05 %
59.21 %
10.76%
20.47% %
Diversity Solutions by Finetuned Models We extract the core concept or theory used in the candidate solutions and observe that diversity increases from 1.67 (RS) to 2.58 (FA) and 3.03 (CAA). rather than MATH, indicating that
Surprisingly, the largest diversity gain occurs on GPQA- diversity learned through training mathematical reasoning data can transfer other domains. This highlights the generalizability the GUIDEDSAMPLING framework across domains.
CONCLUSIONS
We propose a new inference-time algorithm, GUIDEDSAMPLING, that forces exploration can- didate solutions over repeated sampling. The paper demonstrates how performance varies with shifting compute between the exploration of diverse concepts and the generation of final solutions and shows pass @ @50 improvements of up to 34.6%. Furthermore, fine-tuning LLMs trajectories generated by PUIDEDSAMPLIE significantly boosts performance on mathematical reasoning and shows generalizability to other domains like scientifie reasoning and code generation.
10

---

Published as a conference paper at ICLR 2026
LIMITATIONS & FUTURE WORK
While our method is successful in improving the diversity of solutions generated by LLMs, it repre- sents an early step in this area and has some limitations, including but not limited to the following:
Limited model coverage While our evaluation spans three open-source models and a limited study on GPT-4o-mini and Phi-4-mini-instruet applying GUIDEDSAMPLING to proprietary models (e.g., GPT-5, Gemini-2.5-PP remains unexplored due to high inference costs and lack of training access. Extending the method to state-of-the-art models is important direction for future work.
Exploration cost vs. effectiveness trade-off Although our method improves diversity, the optimal balance between the number of concepts (K) and samples per concept (M) under fixed compute budget remains task-specific. Developing adaptive strategies for this trade-off is promising area.
Generality across domains Our work demonstrates promising results in mathematical, scientific, and code generation domains. However, further evaluation is needed to understand how well GUID- EDS AMPLING generalizes to more diverse domains such as legal reasoning, medical, or discovery.
Concept generation quality The success of GUIDEDSAMPLING depends on the quality and di- versity of the generated concepts. Although some "irrelevant" concepts can help (Appendix [ investigating techniques to improve/verify the relevance of these concepts (e.g., through external tools or feedback mechanisms) can enhance overall effectiveness.
Better Verifier GUIDEDS has an exploration phase, which forces the model to explore multiple concepts, increasing diversity. This can lead to multiple final solutions. While this increases pass @ k, building a robust verifier that can select a final solution, even if is in the minority, remains challenging future task.
REPRODUBILITY STATEMENT
To ensure the reproducibility of our results, we release the source code and data through our GitHub /tppsttts:://tthub cwm/Divi http:///ihhhbccmmm/////////a////
jH/ htt/samplll. iinninnnneenneeeeeeeeeeeeeeeeeee We also note that LLMS are
inherently probabilistic in nature, and some results may vary upon each run. We hope our code and data future research.
ETHICS STATEMENT
In accordance with ICLR policy, we disclose that AI assistants, specifically Grammarly for gram- mar correction and ChatGPT for sentence restructuring and paraphrasing, were utilized during the preparation of this manuseript. The authors have reviewed, edited, and take full responsibility for all final content presented in this paper.
ACKNOWLEDGEMEET
We thank the anonymous reviewers for their constructive suggestions. We extend our gratitude to the Research Computing (RC) and Enterprise Technology ASU for providing computing resources for experiments.
REFERENCES
Abdelrahman Abouelenin, Atabak Ashfaq. Adam Atkinson, Hany Awadalla, Nguyen Bach, Jianmin Bao, Alon Benhaim, Martin Cai, Vishrav Chaudhary, Congcong Chen, et al. Phi-4-mini technical report: Compact yet powerful multimodal language models via mixture-ou ofree--f--orss arXiv preprint 20X1422503.0/743, 2025.
11

---

Published as a conference paper at ICLR 2026
Daman Arora and Andrea Zanette. Training language models to reason efficiently. arXiv preprint arXiv:2502.04463, 2025.
Bradley Brown, Jordan Juravsky, Ryan Ehrlich, Ronald Clark, Quoc V Le, Christopher Ré, and Azalia Mirhoseini. Large language monkeys: Scaling inference compute with repeated sampling. arXiv preprint arXiv:2407.21700 2024.
Aditi Chaudhary, Karthik Raman, and Michael Bendersky. It's all relative!-a synthetic query gen- eration approach for improving zero-shot relevance prediction. arXiv preprint arXiv:231..07330, 2023.
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde De Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, et al. Evaluating large language models trained on code. arXiv preprint arXiv:2107.03372 2021.
Wenhu Chen, Xueguang Ma, Xinyi Wang, and William W Cohen. Program thoughts prompt- ing: Disentangling computation from reasoning for numerical reasoning tasks. arXiv preprint arXiv:221..12588 2022.
Yinlam Chow, Guy Tennenholtz, Izzeddin Gur, Vincent Zhuang. Bo Dai, Sridhar Thiagarajan, Craig Boutilier, Rishabh Agarwal, Aviral Kumar, and Aleksandra Faust. Inference-aware fine-tuning for best-of-n sampling in large language models. arXiv preprint arXiv:2412.15287, 2024.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, et al. Training verifiers to 2021.
solve math word problems, 2021. URL https://arxiv. org/abs/2110.144le
Matthias Gerstgrasser, Rylan Schaeffer, Apratim Dey, Rafael Rafailov, Henry Sleight, John Hughes, Tomasz Korbak, Rajashree Agrawal, Dhruv Pai, Andrey Gromov, et al. Is model collapse in- evitable? breaking the curse of recursion by accumulating real and synthetic data, arXiv preprint arXiv:2404.01413, 2024.
Soumya Suvra Ghosal, Souradip Chakraborty, Avinash Reddy, Yifu Lu, Mengdi Wang, Dinesh Manocha, Furong Huang, Mohammad Ghavamzadeh, and Amrit Singh Bedi. Does think- ing more always help? understanding test-time scaling in reasoning models. arXiv preprint arXiv:2506.044 1422,, 2025.
Aaron Grattafiori, Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Alex Vaughan, et al. The Ilama 3 herd of models. arXiv preprint arXhv:2407.21788 2024.
Lin Gui, Cristina Gârbacea, and Victor Veitch. Bonbon alignment for large language models and the sweetness of best-of-n sampling. arXiv preprint arXiv:2406.00832 2024.
Himanshu Gupta, Kevin Scaria, Ujjwala Anantheswaran. Shreyas Verma, Mihir Parmar, Saurabh Ar- jun Sawant, Chitta Baral, and Swaroop Mishra. Targen: Targeted data generation with large language models. arXiv preprint arXiv:2310. /7876, 2023.
Divij Handa, David Blincoe, Orson Adams, and Yinlin Fu. Optagent: Optimizing query rewriting for e-commerce via multi-agent simulation. arXiv preprint arXiv:2510.03771, 2025.
Chaoqun He, Renjie Luo, Yuzhuo Bai, Shengding Hu, Zhen Leng Thai, Junhao Shen, Jinyi Hu, Xu Han, Yujie Huang, Yuxiang Zhang, et al. Olympiadbench: challenging benchmark for promoting agi with olympiad-leve bilingual multimodal scientific problems. arXiv preprint arXiv:2402. 14008, 2024.
Dan Hendrycks. Collin Burns. Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. Measuring mathematical problem solving with the math dataset. arXiv preprint arXiv:2 103.03874. 2021.
Arian Hosseini, Xingdi Yuan, Nikolay Malkin, Aaron Courville, Alessandro Sordoni, and Rishabh Agarwal. V-star: Training verifiers for telf-ttught reasoners. arXiv preprint arXiv:2402.06433 2024.
12

---

Published as a conference paper at ICLR 2026
Aaron Hurst, Adam Lerer, Adam P Goucher, Adam Perelman, Aditya Ramesh, Aidan Clark, AJ Os- trow, Akila Welihinda, Alan Hayes, Alec Radford, et al. Gpt-4o system card. arXiv preprint arXiv:2410.21276, 2024.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001.0836/ 2020.
Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners. Advances in neural information processing systems, 35:22199-22221 2022.
Aviral Kumar, Vincent Zhuang, Rishabh Agarwal, Yi Su, John D Co-Reyes, Avi Singh, Kate Baumli, Shariq lybal, Colton Bishop, Rebecca Roelofs, al. Training language models to self-correct via reinforcement learning. arXiv preprint arXiv:2409. 12917, 2024.
Shrinidhi Kumbhar, Venkatesh Mishra, Kevin Coutinho, Divij Handa, Ashif lquebal, and Chitta Baral. Hypothesis generation for materials discovery and design using goal-driven and constraint- guided Ilm agents. arXiv preprint 1oxXiv:2501.132999 2025.
Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Leblond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, al. Competition-level code generation with alphacode. Science, 37866624):1092-1097 2022.
Hunter Lightman, Vincet Kosaraju, Yuri Burda, Harrison Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. Let's verify step by step. In The Twelfth International Conference Learning Representations, 2023.
Jieyi Long. Large language model guided tree-of ree-of-thought. arXiv preprint arXiv:2305.0829) 2023.
Arindam Mitra, Luciano Del Corro, Guoqing Zheng, Shweti Mahajan, Dany Rouhana, Andres Co- das, Yadong Lu, Wei-ge Chen, Olga Vrousgos, Corby Rosset, et al. Agentinstruct: Toward gen- erative teaching with agentic flows. arXiv preprint a:Xiv:2407.03502, 2024.
Niklas Muennighoff, Zitong Yang, Weijia Shi, Xiang Lisa Li, Li Fei-Fei, Hannanch Hajishirzi, Luke Zettlemoyer, Percy Liang, Emmanuel Candès, and Tatsunori Hashimoto. sl: Simple test-time scaling. arXiv preprint arXiv:250I. 19393, 2025.
Mihir Parmar, Xin Liu, Palash Goyal, Yanfci Chen, Long Le, Swaroop Mishra, Hossein Mobahi, Jindong Gu, Zifeng Wang, Hootan Nakhost, et al. Plangen: A multi-agent framework for generating planning and reasoning trajectories for complex problem solving. arXiv preprint arXiv:2502.16111 2025.
David Rein, Betty Li Hou, Asa Cooper Stickland, Jackson Petty, Richard Yuanzhe Pang, Julien Di- rani, Julian Michael, and Samuel Bowman. Gpqa: A graduate-level google-prov q&a bench- mark. In First Conference on Language Modeling, 2024.
Baptiste Rozière, Jonas Gehring, Fabian Gloeckle, Sten Sootla, Itai Gat, Xiaoqing Ellen Tan, Yossi Adi, Jingyu Liu, Romain Sauvestre, Tal Remez, et al. Code llama: Open foundation models for code, 2023. URL htps://arxiv. org/abs/2308. 12950, 2023.
Aswin Rrv, Jacob Dineen, Divij Handa, Md Nayem Uddin, Mihir Parmar, Chitta Baral, and Ben Zhou. Thinktuning: Instilling cognitive reflections without distillation. In Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing, pp. 31236-31250, 2025.
Zhihong Shao, Peiyi Wang, Qihao Zhu, Runxin Xu, Junxiao Song. Xiao Bi, Haowei Zhang, Mingchuan Zhang, YK Li, Y Wu, et al. Deepseckmath: Pushing the limits of mathematical reasoning in open language models. arXiv preprint 24iv:2402.03300 2024.
Ilia Shumailov, Zakhar Shumaylov, Yiren Zhao, Nicolas Papernot Ross Anderson, and Yarin Gal. Ai models collapse when trained on recursively generated data. Nature, 631(8022)755-753) 2024.
13

---

Published as a conference paper at ICLR 2026
Avi Singh, John D Co-Reyes, Rishabh Agarwal, Ankesh Anand, Piyush Patil, Xavier Garcia, Peter J Liu, James Harrison, Jachoon Lee, Kelvin Xu, et al. Beyond human data: Scaling self-training for problem-solving with language models. arXiv preprint arXhv:2312.06583 2023.
Charlie Snell, Jaehoon Lee, Kelvin Xu, and Aviral Kumar. Scaling Ilm test-time compute optimally can be more effective than scaling model parameters. arXiv preprint arXiv:2408.0333 033144 2024.
Vighnesh Subramaniam, Yilun Du, Joshua Tenenbaum, Antonio Torralba, Shuang Li, and Igor Mordatch. Multiagent finetuning: Self improvement with diverse reasoning chains. arXiv preprint arXiv:2501.05707, 2025.
Alon Talmor, Jonathan Herzig, Nicholas Lourie, and Jonathan Berant. Commonsenseqa: A question
answering challenge targeting commonsense knowledge. Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguisties: Human Lan- guage Technologies, Volume I (Long and Short Papers), pp.
2019.
Yunhao Tang, Kunhao Zheng, Gabriel Synnaeve, and Rémi Munos. Optimizing language models for inference time objectives using reinforcement learning. arXiv preprint arXiv:2503 19595, 2025.
Gemma Team, Aishwarya Kamath, Johan Ferret, Shreya Pathak, Nino Vieillard, Ramona Merhej, Sarah Perrin, Tatiana Matejovicova, Alexandre Ramé, Morgane Rivière, et al. Gemma 3 technical report. arXiv preprint 2mXiv:2503.19785 2025.
Shubham Toshniwal, Wei Du Ivan Moshkov, Branislav Kisacanin, Alexan Ayrapetyan, and Igor Gitman. Openmathinssructt-2 Accelerating ai for math with massive open-source instruction data. arXiv preprint arXiv:2410.01 2024.
Pablo Villalobos, Anson Ho, Jaime Sevilla, Tamay Besiroglu, Lennart Heim, and Marius Hobbhahn. Position: Will we run out of data? limits of Ilm scaling based on human-generated data. In Forty- first International Conference on Machine Learning, 2024.
Tianchun Wang, Zichuan Liu, Yuanzhou Chen, Jonathan Light, Haifeng Chen, Xiang Zhang, and Wei Cheng. Diversified sampling improves scaling Ilm inference. arXiv preprint arXiv:2502. 2025.
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, Sharan Narang, Aakanksha Chowdh- ery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. arXiv preprint arXiv:2203. 11171, 2022.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoe Le, Denny Zhou, et al. Chain-of th-thut prompting elicits reasoning in large language models. Advances in neural information processing systems, 01024844-48331 2022.
Yangzhen Wu, Zhiqing Sun, Shanda Li, Sean Welleck, and Yiming Yang. An empirical analysis of compute-optimal inference for problem-solving with language models. 2024.
An Yang, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chengyuan Li, Dayiheng Liu, Fei Huang, Haoran Wei, et al. Qwen2. 5 technical report. arXiv preprint arXiv:2412.15115. 2024.
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. Ad- vances neural information processing systems, 18:91809-1111 2023.
Eric Zelikman, Yuhuai Wu, Jesse Mu, and Noah Goodman. Star: Bootstrapping reasoning with reasoning, Advances in Neural Information Processing Systems, 15:15576-15488, 2022.
Di Zhang, Xiaoshui Huang, Dongzhan Zhou, Yuqiang Li, and Wanli Ouyang. Accessing gpt-4 level mathematical olympiad solutions via monte carlo tree self-refine with llama-3 8b. arXiv preprint arXiv:2406.0733 07394, 2024.
Zehua Zhang, Ati Priya Bajaj. Divij Handa. Siyu Liu, Arvind S Raj, Hongkai Chen, Hulin Wang, Yibo Liu, Zion Leonahenahe Basque, Souradip Nath, et al. Buildbench: Benchmarking Ilm agents compiling real-world open-source software. arXiv preprint arXiv:2509.2522 25248, 2025.
14

---

Published as a conference paper at ICLR 2026
A THEORETICAL PROOFS
A.1 FROM INTUITION TO ASSUMPTION I
Assumption D stems from the intuition that any "relevant" concept helps in answering given ques- tion, i.c., the concept adds more information which is useful. This is represented as sample-wise information between y and conditioned on æ.
Ily: c x))
log Tbase (v"
2. c) - log Thase (y" x)) >
log Tasee (y)
I, c) > log Tbase (y"
x))
Thase (
x. c) 2 ke Those (y/ x))
(3)
This is the stated assumption] 1
A.2 PROOF OF THEOREM 1
Proof. The probability of generating a correct solution via Repeated Sampling given by:
Pns(y"
2 = Tbase
| x))
(4)
For GUILEDSAMPLING, the probability of generating a correct solution:
Pasly" xx) = Σ Toonoepe (c (x) Thase (y" Ir, c)
(5)
We can partition the sum based on whether the concept is in the set of relevant concepts, C,:
Pas(y" xx) = Σ
Teoncept (c x)) Thase (y" 2, c)
+
Teoncept (cl 2) Trase (3" x) (6)
cEC,
egC,
Let's analyze the first term. By Assumption I for any informative concept E Cinfs we have Thase (v" c) = ke Thase (y* x) where kg 1. Intuitively, since relevant concepts tend to be informative, we can say that for any relevant concept c E Cy. we have Thase (y² x, c) = ke Thase (y" 1z). Let kmin min.ec, kc. It follows that kmin > 1. We can therefore lower-bound
the first term:
Reoncepe x) Thase (y" x, x) 2 Teoncept (c x)) (Kmin Tbase (y) x))
(7)
eEC,
kmin Thase (y" xx) Σ
Teoncepe x)
(8)
CEC,
kmin PRS(Y" |x) P(C,) xx)
where P(C, ax) the total probability of sampling valid concept.
Substituting this back into our expression for Pas(y" | |x) (Eq. 5 we get:
Pas(y" x) 2 kmin PRS(V" xx) P(C, 2)) + Σ Teonoepe(e x) Thase (y" [x,c) (10)
ogC,
For GUIDEDS AMPLING to be superior to repeated sampling, we require Pas(y"(a)) > Pas(v" (x). This inequality holds if:
kmin PRS (y" x) P(C, x)) + Σ
Teoncepe x)) Thase (2) [x, PRS(Y" (x) (11)
egc,
Rearranging the terms yields the condition stated in the theorem:
(kmin P(C, x) 1) PRS(V" x)) + Σ
Teonoope x) Thaoo xxC)
(12)
ogc.
15

---

Published as a conference paper at ICLR 2026
B PROMPTS USED IN OUR STUDY
B.1 EXPLORATION PROMPTS
B.1.1
MATH
The following prompts were used for GUIDEDSAMPLING for the MATH (Hendrycks et al., 2021 benchmark.
MATH Initial Concept Generation
You expert mathematician. You will be presented with mathematical question and your task is to identify and state one single, specific theorem or fundamental concept that is relevant and useful for solving the problem.
QUESTION:
{ele [ 'question']
Provide only the name of the theorem or concept, concise statement of the principle, that is most directly applicable to solving this problem. Do not attempt to solve the original problem. Only provide the theorem concept.
MATH Subsequent Concept Generation
You are an expert mathematician. You will be presented with a mathematical question and list of theorems and concepts that have already been proposed potentially useful for solving the problem. Your task is to provide a *new* and *different* theorem or concept that is most relevant and useful for solving the problem.
QUESTION:
{ele 'question'] }}
EXISTING CONCEPTS:
[ideas.text]
Provide only the name of the theorem or concept, or concise statement of the principle, that is most directly applicable to solving this problem. Do not attempt to solve the original problem. Only provide the theorem or concept. no new, distinct, and useful theorem or concept be identified, respond with "No additional concepts found."
B.1.2 GPQA-DIAMOND
The following prompts used for GUIDEDSAMPLING for the GPQA-Diamond (Rein et al. 2024) benchmark.
GGOA-Diamoon Initial Concept Generation
You are an expert scientist and problem solver. You will be presented with complex, graduate-level science question and your task is to identify and state one single, specific theorem or fundamental concept that most relevant and useful for solving the problem.
QUESTION:
(ele [ 'question' [ (options)
Provide only the name of the theorem concept, concise statement of the principle, that is most directly applicable to solving this problem. Do not attempt to solve the original problem. Only provide the theorem concept.
16

---

Published as a conference paper at ICLR 2026
GPQA-Diamond Subsequent Concept Generation
You are an expert scientist and problem solver. You will be presented with complex, graduate-level science question and list of theorems and concepts that have already been proposed as potentially useful for solving the problem. Your task is to provide a fnew* and *different* theorem concept that is most relevant and useful for solving the problem.
QUESTION:
{ele 'question' Hoptions;
EXISTING CONCEPTS: [ideas.text]
Provide only the name of the theorem or concept, or concise statement of the principle, that is most directly applicable to solving this problem. Do not attempt to solve the original problem. Only provide the theorem or concept. no new, distinct, and useful theorem or concept can be identified, respond with "No additional concepts found."
B.1.3 HUMANEVAL
The following prompts were used for GUIDEDSAMPLING for the HumanEval (Chen al. 2021 benchmark.
HumanEval Initial Concept Generation
You are an expert python programmer. You will be presented with programming question and your task is identify and state one single, specific concept that is most relevant and useful for solving the problem.
QUESTION:
{ele 'question']
Provide only the short description of the concept, that is most directly applicable to solving this problem. Do not attempt to solve the original question. Only provide the concept.
HumanEval Subsequent Concept Generation
You are an expert python programmer. You will be presented with programming question and list of concepts that have already been proposed potentially useful for solving the question. Your task is to provide *new* and *different* concept that is most relevant and useful for solving the question.
QUESTION:
(ele [ 'question']]
EXISTING CONCEPTS:
{ideas ]ext]
Provide only the name or the short description of the concept, that is most directly applicable solving this problem. Do attempt to solve the original question. Only provide the con- cept. If no new, distinct, and useful concept can be identified, respond with "No additional concepts found."
17

---

Published as a conference paper at ICLR 2026
B.1.4 OLYMPIADBENCH
The following prompts were used for GUIDEDSAMPLING for the OlympiadBench (He al. 2024) benchmark.
BeynpiadBench Initial Concept Generation
You are an expert scientist. You will be presented with question and your task is to identify and state one single, specific theorem concept that most relevant and useful for solving the problem.
QUESTION:
fele [ "question inn'
Provide only the name of the theorem concept that is most directly applicable to solving
this problem. Do not attempt to solve the original problem. Only provide single theorem or concept.
OlympiadBench Subsequent Concept Generation
You are an expert scientist. You will be presented with question and a list of theorems and concepts that have already been proposed as potentially useful for solving the problem. Your task is to provide single ne and ** differemt theorem concept that is most relevant and useful for solving the problem. Do not elaborate on the theorem or concept. If distinct, and useful theorem or concept can be identified, respond with "No additional concepts found."
QUESTION:
{ele [ 'question')] }}
EXISTING CONCEPTS:
[ideas.text]
Provide only the name of a single new and different theorem or concept that is most directly applicable to solving this problem. Do not attempt solve the original problem. If no new, distinct, and useful theorem concept can be identified, respond with "No additional concepts found."
B.2
CONCEPT EXTRACTION PROMPT
Concept Extraction Prompt
You are ConceptTagger, an expert that maps a worked-out solution final answer) to the most specific mathematical or logical concept that makes the solution possible.
or
Task: For every input consisting of reasoning explanation (a step-by-step solution, scratch-work, or short justification):
1. Read the explanation.
Decide which single mathematical concept, theorem, or canonical formula is essential for the solution.
Output that concept's standard name- nothing else.
18

---

Published as a conference paper at ICLR 2026
Choose the narrowest concept that still covers the whole solution.
Good: "Pythagorean Theorem" (precise).
Bad: "Geometry" (too broad).
If two or more concepts appear, pick the one without which the problem cannot be solved (typically the first pivotal step).
Here are two examples:
### Example
Problem: A right triangle has legs of lengths 5 cm and 12 cm. What is the length of the hypotenuse?
Step-by-step solution:
Step 1: Recognize this is a right triangle - apply the Pythagorean Theorem.
Step 2: hypotenuse = (5t + 122) = v(25 + 144) v169
13cm
Concept Used: Pythagorean Theorem
### Example
Problem: What is the area of a rectangle with length of 9 meters and width of 4 meters? Step-by-step solution:
Step 1: Identify the shape rectangle.
Step 2: Use the area formula: Area = length x width = 4 36 m2
Concept Used: Area of Rectangle
Formatting Rules:
Output exactly one line with the concept name.
Use Title Case and the singular form (e.g., "Least Common Multiple", not "LCMs").
No extra punctuation, explanation, or line breaks.
B.3
CAA PROMPT
CAA Data
have a few ideas to solve this problem.
a) {Concept 1}
k) {Concept k}
To solve the problem I will use the idea i) (Concept i}:
{Step by step solution]
**Final *s (Final Answer)
C CONCEPT EXAMPLES
In this section, detail some examples from each benchmark and the concepts generated by Re- peated Sampling and GUIDEDSAMPLING. We extract the concepts using Qwen2.5-32B-Inseee
C.1 CONCEPT EXAMPLES MATH
For the following question from the MATH benchmark, Table displays the generated concepts related to the above question.
19

---

Published as a conference paper at ICLR 2026
Convert the point (0,3) in rectangular coordinates to polar coordinates. Enter your answer in the form (r, 0), where >> and 0 < 0 < 2m.
Table Concepts generated via Repeated Sampling and GUIDEDSAMPLING on MATH instance.
Repeated Sampling
GUIDEDSAMPLING
Polar Coordinates Conversion
Distance Formula
Inverse Circular Function
Trigonometric Identity
Circular Function
Pythagorean Theorem
Polar Coordinate Transformation
C.2 CONCEPT EXAMPLES IN GPQA-DIAMOND
For the following question from the GPQA-Diamond benchmark, Table 3 displays the generated concepts related to the above question.
Two quantum states with energies El and E2 have a lifetime of 10-9 sec and 10-8 sec, respectively. We want clearly distinguish these two energy levels. Which one of the following options could be their energy difference so that they can be clearly resolved?
Table 3: Concepts generated via Repeated Sampling and GUIDEDS on GPQA-Diamond instance.
Repeated Sampling
GUIDEDSAMPLING
Heisenberg Uncertainty Principle
Heisenberg Uncertainty Principle Stark Shift
Quantum Rabi Frequency
C.3 CONCEPT EXAMPLES IN HUMANEVAL.
For the following question from the HumanEval benchmark, T displays the generated concepts related to the above question.
from typing import List
def saatrate_paree_groooeee (paren_string: str) List ..* Input to this function is a string containing multiple groups nested parentheses. Your goal to separate those group into separate strings and return the list of those.
Separate groups are balanced (each open brace is properly closed) and not nested within each other Ignore any spaces in the input string.
>>>
()) (()) (0(P)) ['()', (O)', (()))) .u.
C.4 CONCEPT EXAMPLES IN OLYM
For the following question from the OlympiadBench benchmark, Table 5 displays the generated concepts related to the above question.
20

---

Published as a conference paper at ICLR 2026
Table 4: Concepts generated via Repeated Sampling and GUIDEDSAMPLING HumanEval in-
stance.
Repeated Sampling
AMPLING
Stack
Graph-Bascr Based Approach with a Stack
Parentheses Matching
Balanced Parentheses Tree Construction
Stack Manipulation Space Ignoring
Recursive Descent Parsing
Prefix Tree Traversal
Dynamic Programming with Memoization Level Order Traversal with Queue
Suffix Tree Construction with Stack
Counter-Based Approach with Stack
Kruskal's Algorithm with a Union-Find Data Structure Nested Algorithm
Xenia and Sergey play the following game. Xenia thinks of positive integer N not ex- ceeding 5000. Then she fixes 20 distinct positive integers a1 0g..... Ogg such that, for each k .., ... 20, the numbers N and a congruent modulo k. By move, Sergey tells Xemia set S of positive integers not exceeding 20, and she tells him back the set {ax k E 8) without spelling which number corresponds which index. How many moves does Sergey need to determine for sure the number Xenia thought of?
Table 5: Concepts generated via Repeated Sampling and GUIDEDSAMPLING on a GPQA-Diamoni instance.
Repeated Sampling
AMPLING
Chinese Remainder Theorem Principle
Pigeonhole Principle Chebyshev's 's Postulate
Pick's Theorem
Frdös-Szekeres Lemma
Sperner's Lemma
Dirichlet's Box Principle
Hadamard's Lemma
König's Theorem
D DIVERSITY ANALYSIS OF INFERENCE- TIME ALGORITHMS
Here we detail the diversity analysis of Repeated Sampling (RS), Trec-of- Treo-of-Thought (ToT), and GUID- ADSAMPLING We use 2.5-222---I2Stteee to extract the concepts used in each candidate solu- tion. We observe average of 4.04 concepts in RS, while in GUIDEDS AMPLING, we observe 4.75 different concepts, with less compute budget. With ToT, on the other hand, we observe 4.25 average concepts.
E MORE RESULTS USING GUIDEDSAMPIE
E. RESULTS FOR MORE LLMS
In this section, showcase some results on additional models. As mentioned in $4 we generate 100 candidate solutions for each instance. We provide results on Phi-4-mini-nnstruct (Abouelenin al. 2025). GPT-4o-mini (Hurst et al.] 2024). and Gemma-3-27biit (Team et al.] 2025). Due to limited resource constraints, we limit the proprietary model to just the MATH (Hendrycks et al, and 7 show the pass @ 50 results for these models along with the observed diversity as extracted by Qwen-3.22 2.--332B-nnsruue
2021 benchmark. Table
(Yang et al. 2024). Diversity is measured by the average number of concepts for each instance.
21

---

Published as a conference paper at ICLR 2026
Table 6: pass@50 performance of GPT-4o-mini and Phi-4-minii-nstrruee MATH, along with diver- sity of concepts observed in candidate solutions. RS; Repeated Sampling, GS: GUIDEDSANI AMPLING
Model
Repeated Sampling
GUIDEDSAMPLING
Diversity in RS
Diversity in GS
GPT-4o-mini Phi-4-mini-instee iniii-instruct
85.71%
90.00%
3.2
5.0
71.80%
80.80%
2.1
3.4
Table pass @50 performance of Gemma-3-27b-H
Benchmark
Repeated Sampling
GUIDEDSAMPLING
MATH
81.00%
83.80%
GPQA-Diamond
70.20%
92.42%
HumanEval
83.54%
94.51%
OlympiadBench
33.19%
43.52%
E.2 RESULTS ON COMMONSENSEQA
Results for Qwen2.5-3B-Inse on CommonSenseQA are reported in Table The prompts used don't specify task-specific definition of concepts. Prompts are follows:
CommonSense@AA Initial Concept Generation
You helpful assistant. Your task is state concept that is relevant and useful for answering the question.
QUESTION:
fele [ "question']]
Provide the concept that is most directly applicable to answering the question. Do not answer the original question.
CommonSenseQA Subsequent Concept Generation
You are helpful assistant. You will be presented with question and list of concepts that have already been proposed as potentially useful for answering the question. Your task is to provide "nww and *different concept that is relevant and useful for answering the question.
QUESTION:
{ele [ 'question')] }}
EXISTING CONCEPTS:
[ideas_text)
Provide the concept that is most directly applicable to answering the question. Do not answer the original question. If no new, distinct, and useful concept can identified, respond with "No additional concepts found."
Table 8: pass@50 performance of Qwen2.5-3B 3B-nsruutt on CommonSenseQAA RS: Repeated Sam-
pling, GS: GUIDEDSAMPLING Repeated Sampling
GUIDEDSAMPLING
98. 98.94%
95.66%
22

---

Published as a conference paper at ICLR 2026
E.3 MAJORITY VOTING RESULTS
T the overall accuracies of Majority Voting applied on top of Repeated Sampling, GUID- EDSAMPLING, and Tree-of-thought. Out of the 8 different settings, GUIDEDSAMPLING achieves better accuracy in 4 of them, and a higher average performance as well.
Table 9: Accuracy of models benchmarks using majority voting.
Benchmark
Model
Repeated Sampling GUIDEDSAMPLES Tree-of-thought
MATH
Llama-3.2-3B-Ime InIstruuctt
50.40%
43.40%
45.80%
1amma-.2233B-Instii
23.23%
23.23%
19.19%
HumanEval
3ama--32-3B- --stuutntt
20. 10%
45.12%
25.61 %
OlympiadBench
(lama-3.2-3B--mm
17.47%
18.35%
12.75%
MATH
(wen2.5-3B-Inntruus
51.20%
64.20%
45.40%
GPQA-Diamond
Swen2.5-33-Instruus
20.71%
20.20%
7.07%
HumanEval
Qwen2.5- 3B-Instruct
56.71%
50.61% %
39.02%
OlympiadBench
Qwen2.5 3B
3--nn-----Innttrect Instruct
22.53%
21.87%
15.27%
Average
32.80%
35.87%
26.26%
F FINETUNING SETUP
Here we define the hyperparameters that we used for fine-tuning defined in Section 3.4
All the models were trained on A100 GPUs, with a learning rate of 5e and 3 epochs. Batch size and Gradient accumulation steps were 2, and fpl6 was used for all experiments. 20% of the data was split for evaluation (random seed as 21), and the checkpoint with the lowest evaluation loss was considered for reporting the results.
To determine whether the model trained using CAA trajectories experiences any collapse, we use common observation: collapsed model repeat tokens indefinitely without generating end-of-sequence token during inference. While model collapse has been studied to occur for several reasons (Shumailov al. 2024 Gerstgrasser et al. 2024). checking for repeated tokens can indicate whether collapse happens or not.
To validate this,
the base model and the model trained CAA trajectories HumanEval with 10 candidate solutions and check the fiimish_reasol " after generation. Both the base model and the model trained using CAA trajectories return with the finish reason of "stop". indicating that the model produced the -fd-o--seeeence token.
Moreover, our evaluation, as described in $4 requires the model to generate responses in a particular format (refer to Appendix B.3 for the prompt). Since we did see improvements in pass @k values, we can be assured that the model followed the format closely.
Based on these two insights, we can say with some evidence that model collapse occurred while training with CAA trajectories.
G CASE STUDY: CORRECT SOLUTION FROM "IRRELEVANT" CONCEPTS
As noted in $3.3 approach for GUIDEDSAMPLING to outperform repeated sampling is through "Recovery from Irrelevant Concepts".. While our empirical results (Figure 4 show that generating concepts boosts pass @k performance, observe "irrelevant" concepts generated in some instances. Below, we detail one such example where the concept is unrelated at first glance, but leads to the correct solution.
1m. output..
Compl le ontuotott Fini reason
23

---

Published as a conference paper at ICLR 2026
Question from HumanEval
from typing import List
def has_close_elemeee seementssseeeesesseeeeeeee (numbers: List (Eloat), threshold: float)
bool:
Check if given list numbers, are any two numbers closer to each other than given threshold.
>>> has_close_elementee ([1.0, 2.0, 3.01, 0.5)
False
>>> has close close_elementeee ([1.0, 2.8, 3.0, 4.0, 5.0, 2.0), 0.3)
True .'r
To solve this problem, the model suggests 4 different concepts Range Tree, K-D Tree or Octree, Bloom Filter, and Sorting. The simplest and straightforward way to solve this problem is by using sorting algorithm. While Range Tree and Octree also lead to correct solutions, they are more complex in nature. Bloom Filter, on the other hand, not correct concept for this problem. However, still see some correct solutions leading from this concept. One such solution is given below:
Response from Llama-3.2-30 Inntruct
from typing import List
def maa_eesse_elemmnts (numbers: List threshold: float) bool:
# Create set to store the numbers we' ve seen so far seen set ()
Iterate over the list numbers
for num in numbers:
# For each number, check if there's a number in the set # that's closer to it for seen num in seen:
# If we find a number that's closer to the current number than the threshold
if abs (num - seen_num) < threshold: Return True, because we' found two numbers that are close to each other return True
If we haven't found close number yet, add the # current number to the set
seen (num)
# If we' ve iterated over the entire list and haven't t found # two close numbers, return False return False
The above solution is inspired by the Bloom Filter concept, but does not use the concept as-is, mak- ing it an approach that has never been observed in RS. Instances like this make GUIDEDSAMPLING more explorative than RS.
H ALGORITHM FOR GUPPLISAMPLING
Here, present the algorithm for GUIDEDSAMPLINGG
24

---

Published as a conference paper at ICLR 2026
Algorithm GUIDEDSAMPLING
1: Input: Question prompt æ; LLM pe. maximum number of ideas K, completions per idea M
2: Output: Set of candidate solutions S
3:
4: // Exploration Phase
5: C 0
Initialize set of concepts
6: 1
7: while k S K
8:
Cj p- x, ,,, ck-1)
Sample concept B Model indicates no more useful concepts
9: if Cx = None then
10:
break end
11:
12: Cu
13: kek+1
end while
15:
// Generation Phase
17: S +0 0
b Initialize set of solutions
for each concept Cj E C do
19: S₁ k
Initialize solutions for current concept
20:
for m to do
21:
Sample solution 8 (m) pel x, cu)
P Generate solution based on concept
22: Sk S U (sk (m))
end for
24: S SUSUS
end for
26: return S
I PERFORMANCE VARIATION FOR K-TH CONCEPT
50
Avg. Correct Solutions (in
10
15
17
1.5
20
Concept Index
Figure 6: @5 performance variation for k-th concept averaged across all benchmarks and mdoels mentioned in
Here we detail the individual performance of the k-th concept across every model and benchmark. Fig. 6 ifllusttasess the performance for every concept. As discussed in [5 Since later concepts have fewer instances, we see huge variation in performance. Table 10 shows the detailed performance and number of instances for all concepts.
25

---

Published as a conference paper at ICLR 2026
Table 10: pass@ performance and the number of instances for the k-th concept generated in GUIDEDSAMPLING across all benchmarks and models, resulting in a total of 1772 instances.
Concept Index
Avg. Correct Solutions (in %) Number of Instances
19.76 %
1772 (100.00%)
19.93 %
1646 (92.89%)
18.54 %
1473 (83.13%)
4
17.57 %
1193 (67.33%%
5
16.19 %
819 (46. (4%)
18.71 %
178 (10.05%)
17.98 %
126 (7. %)
8
15.13 %
89 (5.02%)
9
22.25 %
72 (4.06%)
10
19.98 %
59 (3.33%)
18.34 %
(2.65%)
12
26.31 %
39 (2.20%)
13
18.96 %
28 (1.58%)
14
52.05 %
23 (1.30%)
15
43.12 %
16 (0.90%)
42.14 %
(0.79%)
17
35.50 %
8 (0.45%)
18
30.86 %
7 (0.40%)
19
44.80 %
5 (0.28%)
0.00
(0.06%)
LATENCY OF INFERENCE-TIME ALGORITHMS
G5
Performance (%)
50
100
110
12c
130
140
150
Average LLM Calls
Figure 7: Pass 50 performance against the number of LLM calls for different inference-time algo- rithms averaged across all models and benchmarks.
Figure 7 shows the relationship between the number of LLM calls and p performance for Repeated Sampling (RS), GUIDEDSAMPLING (GS), and averaged across all models and benchmarks. We found that GUIDEDS AMPLING (pass @ 50=60.2 with 104.75 calls) outperforms both Repeated Sampling (pass@50=48.2 with 100 calls) and Tree- of- at-ughttht (pass@ @ 50=37.1 1 with 154 calls), while being more efficient than Tree-of- Thoughht..
(ToT). All results
26


Reviews:
[{"review_id": "A8EWrZKtQM", "reviewer": "Reviewer_pMb1", "summary": "The paper introduces GuidedSampling, a straightforward and effective method that proposes high-level concepts for the LLM to follow before generating specific solutions. Experiments see performance increase as well as response variety increase with large pass@K sampling.", "questions": "Q1. I'm not sure about the utility of fine-tuning on CCA synthetic data. A naive concatenation of concept + answer may shift the model rollout distribution to exhibit unprecedented behaviors (e.g. become more verbose, suggest unnecessary things), potentially decreasing model generalizability and utiliy. Do models fine-tuned on one synthetic dataset generalize its performance (not diversity) across others? What other validations did you do to ensure no model collapse occurs with CCA fine-tuning? \n\nQ2. Do you have any results on whether the earlier concepts suggested by the concept generator are better than later ones, or vice versa? If there's a pattern there may be a better way to allocate resources than uniformly, but this is not very important so don't stress about it if results are hard to get.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1. By intuition, there is almost no doubt in my mind that the proposed method is effective, as it resembles a mini-agentic approach and directly scales up reasoning through segmentation of hard problems. It's great to see this type of approach being studied in the field, however simple they may be. \n\n2. The empirical justifications are well-discussed, and the results are significant and generalizable.", "weaknesses": "1. The theoretical Section 3.3 leaves much to be desired. \n    1. Assumption 1 (minor issue: notation $C_{inf}$ should be $C_r$) has four lines of equations, but the second and third are equivalent and both can be derived from the fourth. I suspect the authors wanted to justify the fourth assumption and introduction of $k_c$, but this is not a good way to write assumptions. Furthermore, the fourth line can be relaxed from an equation to a greater-than-inequality, which immediately relaxes the assumption to be much more reasonable, since the original version stipulates two partial probability distributions have the exact same ratio across $x$ and $y^\\*$. \n    2. Theorem 1 is misleading for using \"iff\" on Line 281/282: Equation (2) is not equivalent to $P_{GS} > P_{RS}$, but can only derive the latter. This means it is possible that Equation (2) does not hold, but the desired advantage of GS over RS still holds. Despite this, I still think there is value in the theoretical analysis, since the passage under \"Sufficient Concept Coverage\" is still perfectly valid. I would suggest addressing these problems and rephrasing the theory to be more straightforward and clear. \n\n2. The value of hyperparameter K, the number of concepts, is not clearly specified for the main result in Figure 4. \n\n3. As a motivation, the diversity analysis in Figure 3 is a great way to motivate the method. It would be helpful to do more analyses on diversity of GuidedSampling without finetuning.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uiN24nU52t", "reviewer": "Reviewer_biMm", "summary": "This paper proposes GUIDEDSAMPLING, a novel inference-time algorithm designed to address the lack of diversity in traditional Repeated Sampling (RS). GUIDEDSAMPLING resolves this limitation by decoupling the inference process into an exploration phase and a generation phase. It first iteratively generates a diverse set of high-level concepts or theorems in the exploration phase, and then generates candidate solutions for each concept in the generation phase. This method can also be used as a synthetic data generation method. Experimental results show that GUIDEDSAMPLING brings model performance improvements both as an inference-time algorithm and as a synthetic data generation method.", "questions": "See weaknesses", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. The core idea of this paper—decoupling the inference process into an exploration phase and a generation phase—is an intuitive, simple, and effective method that directly targets the weakness of RS's lack of diversity.\n\n2. The paper provides a theoretical explanation for when this method works, which is consistent with experimental observations\n\n3. In my opinion, the paper's greater contribution lies in its excellence as a synthetic data generation method. It guides the model to generate more diverse reasoning results on its own, and further allows the model to internalize diversity through training.", "weaknesses": "1. The exploration phase is an iterative process, meaning that generating the k-th concept requires waiting for the (k-1) concepts to finish generating. This implies that acquiring K concepts necessitates K serial calls. As an inference-time method, GUIDEDSAMPLING is more challenging to ensure real-time performance compared to RS when computational resources are sufficient.\n\n2. The paper lacks quantifiable comparisons of computational efficiency.\n\n3. The definition of \"concepts\" appears to be task-specific and manually designed. How can this approach be generalized to more open-ended tasks where concepts are less clearly defined (e.g., commonsense reasoning, long-form story generation)?\n\n4. Although the paper shows that the model can sometimes produce correct solutions even if flawed concepts were generated earlier, a more robust approach would be to implement a feedback loop, allowing the generation phase to inform the exploration phase. This would allow generation efforts to be focused on more promising concepts, rather than wasting compute on flawed paths.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fLxkHDoOeG", "reviewer": "Reviewer_3jyG", "summary": "This paper provides a competitor approach to Repeated Sampling for the task of inference time algorithms to improve model performance on complex tasks. Their approach utilizes an exploration phase to sample relevant concepts first and then samples varying responses conditioned on such context to have a larger scope of responses at decision time. The work provides theoretical bounds for how it improves upon RS and additionally presents results on various benchmark complex reasoning datasets demonstrating improvements over baseline methods.", "questions": "1. How is the final response selection chosen from the candidate set?\n2. How can we ensure that the concepts samples are semantically diverse? If they are not diverse enough, could we ever get worse performance than RS?\n3. How sensitive are the results to prompt changes for concept generation?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The problem of scaling inference time compute to generate better performance is interesting and well motivated especially in the context of smaller models.\n2. The proposed approach is quite simple and easy to implement, yet very compelling and intuitive to the reader of why this would work well.\n3. The theory provides crisp conditions by which GuidedSampling would be preferred to RS.\n4. The empirical results are extensive and impressive.", "weaknesses": "1. The intuition for Assumption 1 is unclear. That is, if concepts are misapplied or conflicting, the assumption could easily be violated.\n2. While the paper well established how candidate solution sets are constructed at inference time, it is still unclear how the final solution is selected from this set. Is it a majority vote?\n3. All results are on models of ~3B size. To understand the scale of the solution, their should be more results for various model sizes.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dl8YUISzgl", "reviewer": "Reviewer_xAGJ", "summary": "The paper proposes GuidedSampling, a novel inference-time algorithm designed to address the limited diversity of solutions generated by standard Repeated Sampling (RS). The core idea is to decouple inference into two phases:  \n1. Exploration: Generate a diverse set of high-level concepts (e.g., theorems, programming paradigms) relevant to solving the input problem.  \n2. Generation: For each concept, generate multiple candidate solutions conditioned on that concept.  \n\nThe authors provide a theoretical analysis showing conditions under which GuidedSampling outperforms RS (Theorem 1). Empirically, they demonstrate clear pass@50 improvements over RS across four benchmarks. Additionally, they show that fine-tuning models on GuidedSampling-generated trajectories yields clear pass@5 gains and increases solution diversity.", "questions": "1. Compared to the Tree-of-Thought (ToT) algorithm, GuidedSampling incurs lower computational overhead. However, ToT—being more expensive—should theoretically yield better performance, especially since GuidedSampling's approach appears subsumable within ToT’s framework (e.g., treating each concept as a root thought). Why then does ToT underperform relative to GuidedSampling in the experiments? Moreover, given the difference in computational cost, a direct comparison of inference-time overhead (e.g., total LLM calls, latency, or FLOPs) between the two methods is essential to contextualize their trade-offs.\n\n2. How would GuidedSampling adapt to non-STEM tasks (e.g., commonsense reasoning, dialogue)? What would “concepts” represent in such settings?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. While multi-path reasoning exists (e.g., ToT), GuidedSampling's two-phase design with iterative concept prompting shows better performance.\n\n2. The paper is well-organized and easy-to-follow. It is supported with theoretical results.", "weaknesses": "1. The paper distinguishes itself from previous works via iterative concept prompting and theoretical analysis, but the high-level idea of separating idea generation from solution generation is not entirely unprecedented.\n\n2. Theorem 1 assumes concepts amplify correctness probability (Assumption 1). However, irrelevant/misleading concepts could harm performance.\n\n3. It seems necessary to design task-specific definitions of concepts, which limits generalization.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)