Chain-of-Thought Reasoning Without Prompting
Authors: Xuezhi Wang
Denny Zhou
Venue: NeurIPS 2024 poster (2024)
Keywords: Reasoning
large language models
decoding
Primary area: natural_language_processing
TL;DR: Large language models can reason without any specialized prompting, when alternative tokens are considered during the decoding stage.

Abstract: In enhancing the reasoning capabilities of large language models (LLMs), prior research primarily focuses on specific prompting techniques such as few-shot or zero-shot chain-of-thought (CoT) prompting. These methods, while effective, often involve manually intensive prompt engineering. Our study takes a novel approach by asking: Can LLMs reason effectively without any prompting? Our findings reveal that, intriguingly, CoT reasoning paths can be elicited from pre-trained LLMs by simply altering the \textit{decoding} process. Rather than conventional greedy decoding, we investigate the top-$k$ alternative tokens, uncovering that CoT paths are frequently inherent in these sequences. This approach not only bypasses the confounders of prompting but also allows us to assess the LLMs' \textit{intrinsic} reasoning abilities. Moreover, we observe that the presence of a CoT in the decoding path correlates with a higher confidence in the model's decoded answer. This confidence metric effectively differentiates between CoT and non-CoT paths. Extensive empirical studies on various reasoning benchmarks show that the proposed CoT-decoding effectively elicits reasoning capabilities from language models, which were previously obscured by standard greedy decoding.

Chain-of-Thought Reasoning without Prompting
Xuezhi Wang Google DeepMind xuezhiv@google.com
Denny Zhou Google DeepMind demnyzhou@google. com
Abstract
In enhancing the reasoning capabilities of large language models (LLMs), prior research primarily focuses on specific prompting techniques such as few-shot or zero-shot chain-of-thought (CoT) prompting. These methods, while effective, often involve manually intensive prompt engineering. Our study takes a novel approach by asking: Can LLMs reason effectively without prompting? Our findings reveal that, intriguingly, CoT reasoning paths can be elicited from pre-trained LLMs by simply altering the decoding process. Rather than conventional greedy decoding, we investigate the top-k alternative tokens, uncovering that CoT paths are frequently inherent in these sequences. This approach not only bypasses the confounders of prompting but also allows us to assess the LLMs' intrinsic reasoning abilities. Moreover, we observe that the presence of CoT in the decoding path correlates with a higher confidence in the model's decoded answer. This confidence metric effectively differentiates between CoT and non-CoT paths. Extensive empirical studies on various reasoning benchmarks show that the proposed CoT- decoding effectively elicits reasoning capabilities from language models, which were previously obscured by standard greedy decoding.
Introduction
Large language models (LL.Ms) have demonstrated remarkable performance on various complicated reasoning benchmarks (Anil et al., 2023; Brown et al., 2020; Chowdhery et al., 2023; Gemini, 2023; OpenAI, 2023; Romera-Paredes et al., 2023). These reasoning capabilities of L.MSs are typically elicited by prompting techniques (Brown et al., 2020), which can be few-shot prompting with intermediate steps augmented demonstration exemplars (Chen et al., 2023b; Gao et al., 2022; Nye et al., 2021; Wei et al., 2022; Yao et al., 2023; Zhou et al., 2023a), zero-shot prompting with specific instructions which ask for showing certain intermediate steps (Kojima et al., 2022; Yasunaga al., 2023). The other prevalent strategy for eliciting LLM reasoning is through model training or instruction tuning using a substantial amount of chain-of Slain-of-thougee of-thought (CoT) reasoning data (Chung et al., 2022; Cobbe et al., 2021; Ling et al., 2017; Nye et al., 2021).
Prompting techniques, while effective, often encode task speciffi human priors, thereby making difficult to assess language model's intrinsic reasoning abilities. Ideally, well-trained language model should capable of independent reasoning and delivering optimal responses, without requiring humans to tweak the prompts or refine repeatedly when the initial response is unsatisfactory. Model- tuning can be expensive and requires a substantial amount of supervised data. In this work, we explore different perspective and ask: Can LLMs reason effectively without prompting? And to what extent can they reason? We find that, perhaps surprisingly, there exists a task-agnostic way to elicit CoT reasoning from pre-trained LLMs by simply altering the decoding procedure. Figure I illustrates this phenomenon: given a reasoning question, the L.LM generates a wrong answer via the standard greedy decoding path, yet alternative top-k token inspection unveiled inherent CoTT paths (e.g., decoding paths 2 and 4), which accurately resolved the query. This decoding modification bypasses prompting and is entirely unsupervised without the need for model tuning.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Question in standard QA format
Decoding step
Continue greedy decoding
5 apppees
X
Q: have 3 apples, my dad has apples than how many apples do we have in total?
top-1: 5
have 3 apples, my dad has 2 more apples than me, so he has apples. 3+5=8. have apples in total.
top-2: I
top-3: We
We have aapples total. X
top-4: You
top-5: The
You have 3 apples, your dad has more apples than you, so he has apples. 3+5=8. You have apples total.
Language model
The answer 5.
uncertain
certain
Figure 1: Illustration of CoTT-deodingg Pre-trained LLMs are capable of inherent reasoning without prompting by considering alternative top-k tokens, rather than solely relying on the top-1 greedy decoding path. Moreover, these models tend to display higher confidence in decoding the final answer (indicated by a darker shaded color) when a CoT reasoning path is present.
In more details, we formulate the input using the standard question-answer (QA) format: "Q: [question]InA: ! While most existing work suggest that LLMs falter in such direct-QA scenarios on reasoning (Cobbe al., 2021; Kojima et al., 2022; Nye al., 2021; Wei et al., 2022), our findings reveal nuanced picture. We observe that LLMs indeed struggle with reasoning when relying solely on greedily decoded paths. However, when we consider alternative paths among the top-k tokens, CoT reasoning patterns emerge naturally within the decoding trajectories of L.LMs. In addition, we have observed an interesting pattern: the model demonstrates increased confidence in the final answer when CoT reasoning path is present in the decoding process. As illustrated in Figure 1, this is evident where paths and show heightened certainty in arriving at the correct answer "8", contrasting sharply with the high uncertainty in paths that lead to the incorrect "5". Leveraging this phenomenon, we develop a method to sift through the top-k decoding paths, which we refer to as Co CoT-deco,ing thereby isolating the most reliable paths for model output.
Our contributions are summarized as follows:
We present a novel finding that LLMS can reason by simple decoding changes, without the use of prompting. In contrast prior research that focuses on refining prompts to elicit reasoning from LLMs, our work, for the first time, shows that the reasoning process can be readily elicited by simple decoding changes. Moreover, we challenge the prevailing notion in the literature that LLMs are inherently incapable of effective reasoning without prompting. We show that this belief is an artifact of considering only the greedy path during decoding, and the model's reasoning paths can be revealed by traversing the alternative decoding paths.
Our method enables a better understanding of LLMs' intrinsic reasoning capabilities with- out imposing human priors. The employment of intricate prompting techniques often introduces various human priors, making it difficult to distinguish between the extent of "human teaching" and the degree which LLMs can reason independently. Our approach bypasses the confounders introduced by prompting, enabling a more truthful assessment of the models' intrinsic reason- ing abilities. Our study reveals that pre-trained language models inherently possess reasoning capabilities for many tasks including math and commonsense reasoning, and existing prompting approaches mostly serve the role of bringing those inherent reasoning paths forward as the top decoding paths. In contrast, the CoT CoT-paths are less prevalent in complex and highly synthetic tasks, where the few-shot CoT demonstrations play a "teaching" role in guiding how models solve task, with models primarily mimicing the format of these prompts to generate accurate reasoning paths.
We further propose CoT-decoding that reliably selects CoT-paths based on answer confi- dence. We find that the language model's confidence in its final answers increases when CoT is present in its decoding path. Leveraging this increased confidence, we propose CoT-decoding to select more reliable decoding paths, demonstrating significant improvements over greedy decoding across various reasoning benchmarks.
'The QA format is only needed because without it pre-trained language model will continue the question instead of answering. It is also the most basic formatting employed in existing works for pre-trained models.

---

2 Chain-of-Thought (CoT) Decoding
2.1 Pre-trained Language Models Can Reason without Prompting
We investigate whether pre-trained language models inherently possess reasoning capabilities, without explicit prompts or human intervention. In Table 1, we show example decoding paths across math (GSM8K, Cobbe al. (2021)) and commonsense reasoning (year parity, Allen-Zhu and Li (2023)). We employ the pre-trained M-LM-2 large model (Anil et al., 2023) to compare its greedy decoding path (k- 0), predominantly used in state-of-the-art LLMs for reasoning tasks, with alternative decoding paths (k > 0), where k represents the choice of the k-th token at the first decoding step.
[GSM8K] One glass costs $5, but every second glass costs only 60% of the price. Kylar wants to buy 16 glasses. How much does need pay for year?
Parity] Was Nicolas Cage born In an even or odd
Greedy path:
Greedy path:
= 0: 560.00 (0.029)
k = 0: Nicolas Cage was born in an odd year, (0. (0.117)
Alternative top-k paths:
k m 1: 60 (0.058)
Alternative top-k pathe:
= 2: Kylar noods to pay 360 for 16 glasses. (0.058)
1: Even (0,207)
k 2: Odd (0.198)
= 7: If Kylar buys 16 glasses, he will pay $60. (0.032)
À 3: 1964, un even year. (0.949)
We can caliuulate.
need milhiply the price of one glass by 16
k 4: He hom
year. (0.0)
and then subtract 40% of the price of glasses. 5 80 x 40 40 0.4 16 80
Kylar needs to pay for 16 glasses. (0.994)
7: Cage hom 1964, even year. (0.978)
Table I: Examples of greedy decoded paths and alternative top-k paths over the P-LM-2 Large model. The model's confidence over the answers (bolded) are highlighted in blue (See $2.2 for details).
LLMs indeed cannot reason if we only consider the greedy decoding path. First, we observe that models employing greedy decoding often does not contain a CoT path, opting to solve problems directly. This tendency may stem from the model's skewed perception of problem difficulty, shaped by its pre-training on predominantly simpler questions. Consequently, the model is predisposed to immediate problem-solving. This observation aligns with findings in (Cobbe et al., 2021; Kojima et al., 2022; Nye et al., 2021; Wei et al., 2022). which show that direct-answer prompts generally result in low accuracy on reasoning tasks even for large language models.
LLMs can reason if we consider the alternative decoding paths. Contrastingly, an intriguing phenomenon emerges when exploring alternative top-k (k: >> 0) tokens at the first decoding step. Continuing with greedy decoding from this point reveals natural CoT reasoning in many cases. These findings suggest that large language models possess inherent reasoning capabilities for numerous tasks following pre-training, but these abilities are obscured by the predominant use of greedy decoding. These reasoning paths can be easily uncovered by incorporating alternative decoding paths.
For instance, in the GSM8K question (Table 1), a valid CoT emerges at = 9. Similarly, in the year parity task, greedy decoding attempts directly answer the parity question k O. leading to a random choice between "even" and "odd" which often results in an incorrect answer. However, when exploring A: O, the model naturally generates CoT paths at k- = 3 and k 7, where it first determines the year before resolving the parity.
2.2 CoT-Decoding for Extracting CoT Paths
In this section, we further show how we can reliably extract those CoT-paths during the decoding process. We observe that CoT paths do not consistently outrank non-CoT ones in the model's s probability assessment. Moreover, they often do not represent the predominant answer among all paths, rendering methods like self-consistency (Wang et al., 2023a) inapplicable. For instance, in the GSM8K question, the prevalent answer "60", which aligns with the greedy decoding result, fails to serve reliable indicator for identifying the correct path.
Interestingly, upon examining the model's logits, we found that the presence of a CoT path typically leads to more confident decoding of the final answer, characterized by a significant probability disparity between the top and secondary tokens:
Σ Eanswer
p(at x<e) - ppa? x<))-
h answer
Janswer|
3

---

Here z and 2i represent the top two tokens at the t-th decoding step in the k-th decoding path, chosen for their maximum post-softmax probabilities from the vocabulary, given x, being part of the answer tokens. This uncertainty measure is similar to the minimum-mayy 2019) and in our case, the model's overall confidence decoding the final answer is approximated by averaging these probability differences for all relevant answer tokens zy.- For example, for the GSM8K question in Table 1, given the answer "60", we average the probability differences for all tokens in that answer, i.e., "6" and "0".2
approach in (Jiang and Gupta,
This method, referred as CoT-decoding, extracts such CoT paths among the decoded paths from the model. As illustrated in Table 1, each decoding path is marked with its corresponding A value in blue (the answer tokens are bolded). It is evident that paths with CoT component exhibit a significantly higher A, highlighting the model's 's increased confidence, as opposed to paths without COT. We also did quantitative analysis by manually examining the first 100 questions in GSM8K, and among those, if we take the decoding path with the highest answer confidence among the top- decoding paths, 88% of them contain CoT paths. This shows an overwhelmingly high correlation between the model's answer confidence and the CoT paths.
Comparing different CoT-path extraction approaches. In Table 2, we compare different ways to extract the CoT-paths out of the top- 10 decoded paths. is easy to see that the model's own probability measure does not serve probability (since an intuition could be a CoT-path should usually be a longer decoding path, which is not always the case, e.g., the year parity task). In contrast, CoT-decoding can reliably extract the CoT-paths, yielding a significant boost on the model's 's reasoning performance.
reliable indicator, nor does the model's length-normalizen normalized
GSM8K (top-100)
Year Parity
Greedy decoding
44.0%
57.0%
Decode 10 paths, rank by model's highest log-prob Decode paths, rank by model's highest length-normalizer log- log-prob
37.0%
55.0%
51.0%
57.0%
CoT-dccoding (decode 10 paths, rank by model's 's answer confidence)
72.0%
95.0%
Table 2: CoT--ecoding reliably extracts the CoTT-paths compared other methods (on PaL L...
Identify the answer spans. Computing A requires identifying the answer spans in a model's response. One common approach used for public models is to extract the last numerical value in math reasoning tasks, or the final option in set-based reasoning tasks, as the answer, following the Tülu evaluation (Ivison et al., 2023; Liu et al., 2024; Wang et al., 2023b). Alternatively, similarly to the method used in Kojima et al. (2022), we can extend the model's s output with the prompt "So the answer is", and then align these continuations with spans in the model's 's decoding path the answer.
Sampling under the stan- dard QA format. CoT- decoding explores alternative tokens at the first decoding step. A natural question arises: can sampling achieve a similar effect and unveil the CoT reasoning paths? We found that, although sampling works well under few-shot CoT prompting (Wang et al., 2023a), does not exhibit the desired behaviour without the prompts. In Table 3, we show that when no CoT prompt is used, CoT-decoding much more sample-efficient than sampling-
Table 3: CoT-decoding and self-consistency w/o prompts on GSMSK.
Mistral-7B PaLM-2 L
Greedy decoding Self-consistnncy without CoT-prompt (10 paths) CoT-decoding (10 paths)
9.9%
34.8%
12.9%
40.6%
25.1 1%
63.2%
approaches like self-consistency. The ineffectiveness of sampling stems from the model's ss skewed distribution towards the direct answer tokens, hence the first token tends to have less diversity compared to CoT-decoding. In contrast, CoT-decoding works by explicitly encouraging diversity at the first decoding step.
Branching at other decoding steps. Another natural question is whether branching is viable at later decoding stages, comparing to only branching at the first decoding step. In Figure 2, we highlight
We also considered other popular choices for measuring the model's uncertainty (Settles, 2009), e.g., using the model's probability on the token itself (i.e., p(at xxee) only), which performs slightly worse compared to the min margin approach. In addition. an entropy estimate is not accurate due to the large vocabulary size in LLMs and the common use of vocabulary truncation.

---

the impact of alternative token consideration in subsequent decoding steps. It is evident that early branching, e.g.. the first decoding step, significantly enhances the diversity of potential paths. Conversely, later-stage branching is significantly influenced by previously generated tokens. For instance, initiating with the token "5" greatly decreases the likelihood of rectifying an erroneous path. Nonetheless, the optimal branching point may vary with the task; in the year parity task, for instance, mid-path branching can effectively yield correct CoT paths.
hhaee spples, my dad hes more apples then me. how many apples do we have in total?
Cage an even year?
step 0
step 1
stop 0
step1
step k
year.
top-1:
5
apples
top-1: Nicolas
was born an evan year.
Cage was born in
1964,
even year.
have apoles, my dad... We have 8 bppples in local
top-2:
know...
lop-2:
Even
have 5 apples total.
top-3: We
don't because we don't
many apples...
top-3: Odd
top-4: can't know..
have 3 apples, your dad... You have O apples tossl.
top-4:
1
984,
year. even. V
1op-5: The apples are metaphor...
top-8:
was born in an even year. old.
Figure 2: We present an analysis of the decoded paths by considering alternative tokens at various decoding steps. Task-dependent challenges arise: times, the model encounters difficulty recovering from incorrect paths when branching at later tokens. For certain tasks, multiple branching positions may exist, all leading to the correct reasoning path.
Aggregation of the decoding paths. Since we already decode the top-k paths, one natural exten- sion is to aggregate the answers over all those paths, similar to self-consistency (Wang et al., 2023a) but without the use of prompts. The rationale behind this aggregation is to mitigate sensitivity to small differences in the model's logits, particularly when relying solely on the path with the maximum A. The examples in Table 1 show that the majority answer is unlikely to be the correct one. Instead, we propose a weighted aggregation method, i.e., we take the answer that maximizes A = Ex Ar.e where A is the k-th decoding path whose answer enhances the stability of the results, and further analysis is presented in Section $3.3.
We found that adopting this approach
3 Experiments
We evaluate CoT-decoding across a range of reasoning benchmarks, demonstrating its capability to successfully recover CoT reasoning paths during decoding, all without the need for specialized prompting.
Experiment Setup. For all experiments, the defauut input to the model is the standard QA format of Q: [question//nA: where [question] is filled with the actual question depending on the task, and we ask the model to continue the generation given that prefix. During decoding, we use = 10 as default for the alternative top-k tokens at the first decoding position, and continue greedy decoding afterwards. We show ablation studies with respect to the different choice of & in Section $3.1.
Datasets. For mathematical reasoning, we use the Grade-schond math problems (GSM8K; Cobbe et al., 2021) and the multi-step arithmetic dataset from (MultiArith;; Roy and Roth, 2015). For commonsense reasoning, we investigate the "year parity" task where recent literature finds large language models still struggle with. The task is to query the model with "Was [person] born in an even or odd year?" where "[person]" is filled by random celebrity name.3 Existing work (Allen-Zhu and Li. 2023; Berglund et al., 2023) shows that even SoTA models like GPT-4 struggle with such tasks, achieving at-chance accuracy (~50%) when prompted directly. Additionally, we investigate symbolic reasoning tasks from Big-Bench Hard (bench authors, 2023; Suzgun et al., 2022).
Models. We use three public models: (1) PaLM-2 (Anil et al., 2023) with different scales, ranging from X- X-all.. Small, Medium, and Large: (2) Mistral-7B (Jiang et al., 2023), and (3) Gemma-7B
3 We curate a list of the top 100 celebrity names from (Berglund et al., 2023): httpa://github... can/ Juksebergluud/revveeell www.e/wwleeeeeeeeeeee httee///lbb//sin//eeee/ httpa/////att//eeeeittoo httpt////cceeetttterarreeeeeeeee wew.ereeeeettotoooooo http:///tooppeoiiteeeeeeeeeeeeee www.eeeiieeeeeeeee
5

---

(Team et al., 2024). Our experiments primarily focus pre-trained models, but we also include experiments with instruction-tunee models (denoted as "inst-tuned" or "IT").
3.1 CoT-Decoding Effectively Elicits Reasoning from Language Models
CoT-decoding the only decoding strat- egy that effectively elicits language model reasoning. In Table 4, we present results from popular decoding baselines on the Mistral-7B pre-trained model, includ- ing temperature sampling (Ackley al., 1985; Fieler and Goldberg, 2017), top-k sampling (Fan et al., 2018; Holtzman et al., 2018; Radford et al., 2019), nucleus sam- pling (Holtzman et al., 2020), and beam search. We can see that CoT--decodngg is
Table 4: CoT-decoding the only decoding strategy that can effectively elicit language models' reasoning.
GSM8K Acc
Top-k sampling (k:
4.9%
Top-p/ Nucleus sampling (p 0.9)
6.4%
Beam search (b 10)
6.7%
Temperature sampling (T = 0.7)
7.5%
Greedy decoding Self-consistency w/o CoT prompt (10 paths)
9.9%
12.9%
CoT-decoding (k 10)
25.1 %
the only decoding strategy that effectively
enables language models to reason, while some of the decoding methods even hurt model's reasoning ability compared to greedy decoding.
CoT-decoding effectively elicits reasoning across language models. In Figure 3, we show that across three language model families, PaLM-2, Mistral and Gemma, CoT-decoding yields consistent accuracy gains on both math and commonsense reasoning tasks, sometimes doubling or even tripling the performance compared to greedy decoding.
Greedy
CoT doT-decoding
100.0
Mistral-7B
Gemma-7B
PaLM- 1.LM-22U Large
06.7
75.0
80.8
75.0
66.0
63.2
57.0
45.7
40.0
28.0
35.0
27.5
28.2
34.8
9.9
15.2
GSV8K
MulriArth
Year Parily
GBNSK
MutriArth
Year Parily
GSMBK
MultiArtth
Year Parlly
Figure 3: CoT-decoding effectively elicits reasoning across multiple language model families includ- ing PaLM-2, Mistral and Gemma, with significant accuracy gains over three reasoning tasks.
CoT-decoding elicits reasoning across model scales. In Figure 4, we show that CoT-decoding enhances reasoning across different model scales over the PaLM-2 model family. On GSM8K, CoT-decoding consistently yields +10-30% absolute accuracy gains. On year parity, when using greedy decoding, the model's 's performance remains flat even after scaling up model sizes, consistent with the findings in KAllen-Zhu and Li, 2023). In contrast, CoT-decoding significantly boosts the performance by recovering the CoT paths, achieving almost perfect accuracy at larger model scales.
GSM8K acouracy
Year Parily accuracy
Greedy
decoding
Greedy
CoT decoding
100
100.0
95.0
81.3
89.0
67.8
80.0
39.7
25
17.7 9:0
743
21.0
60.0
61.0
55.0
57.0
0
40.0
XS
Small
Medium
Large
Inst-tuned
Small
Medium
Large
Figure 4: CoT-decoding reliably improves reasoning performance across model scales (PaLM-2), even when the task does not naturally improve by scaling only (e.g., year parity).

---

CoT--decodng partially closes the reasoning gap between pre-trained and instruction-tuned models, without using any supervised data. Intriguingly, we observe that CoT-decoding enables pre-trained model to achieve similar performance of an instruction-tuned model: in Figure 4 (left), CoT-decoding achieves 63.2% accuracy on the pre-trained PaL. Large model, close to the performance of the instruction-tuned model of the same scale at 67.8%. The results demonstrate that instruction-tuning with sufficient CoT data (Chung et al., 2022) can be partially achieved by modifying the decoding procedure within pre-trained models.
More interestingly, we observe that CoT- decoding can further improve the instruction- tuned model (Figure 4 (left) and Table 5). The instruction-ture srrnnng procedure (Chung et al., 2022) incorporated a large amount of CoT an- notations during the fine-tuning process. Con- sequently, the model is expected to inherently generate CoT paths when addressing reasoning tasks. However, upon analyzing specific exam- ples, we found that even after instruction-tuning, the model occasionally persists in attempting to directly address question. In contrast, CoT- decoding can enhance the exploration alter-
Table 5: CoT-decoding improves both pre-trained and instruction-tunet Mistral-7B models.
Pre-trained Inst-tuned
Greedy
9.9
31.2
GSMSK
CoT-decoding
25.1 (+15.2)
38.2 (+7.0)
Greedy
14.3
37,8
MultiArith
CoT-decoding
45.7 (431.4)
66.5 (428.7)
Year Parity
Greedy
35.0
62.2
CoI-decoding
66.0 (+31.0)
73.5 (+11.3)
native paths by triggering CoT first, consequently leading to more accurate answers.
Choice of k. In Figure 5, we illustrate how the choice of k, representing the number of top alternative tokens considered, influences the overall accuracy. Overall we found that higher values of k typically result in improved model performance, suggesting that in many cases, the correct CoT paths may indeed exist but are often ranked lower during model's decoding. For instruction-tunet models, the effect of k is less significant, indicating that the process of instruction-tuning effectively brings forth the majority of CoT-ppats the first few decoding paths.
Multi-step Arith
80
Accuracy
Accuracy
40
Xs
d=0, I-3
20-
d=0. l-4
d-7, 1-3
20
I-4
01
Top-k tokens for decoding paths
Top-k tokens for decoding paths
Figure 5: The effect of l reasoning accuracy w.r.t PaLM-2 model scales and task difficulty.
3.2 CoT-decoding Enables a Better Understanding of Model's Intrinsic Reasoning Abilities
Compared existing works that improve model's reasoning via better human-written prompts, key distinction of our proposed approach lies in the complete elimination of human-provided prompts. This modification enables a more truthfful assessment of a language model's intrinsic reasoning capabilities. In the previous section, show that language models inherently possess reasoning capabilities for grade-school-level math problems and simple commonsense reasoning tasks. In this section, we will systematically vary the difficulty levels of synthetic tasks to gain more comprehensive understanding of language models' inherent reasoning abilities via CoT-decoding.
We consider the following symbolic reasoning tasks: (1) the Coin Flip task from (Wei et al., 2022), with 2, 3, 4 rounds of potential flips; and two tasks from Big-Bench-Hard (bench authors, 2023; Suzgun et al., 2022): (2) Web of lies, with 3, 4,5 truth/lie statements, and (3) Multi-step arithmetic with various depth level d and length I. For each task, we produce 100 examples for each difficulty level, except for Web-of-Lies (5) we use the existing dataset from (Suzgun et al., 2022). We also
7

---

include two natural- Lang-age-ggeaee based but synthetic tasks from Big- Big-Bench, Sports Understanding and Object Counting, probe model's intrinsic abilities in solving synthetic tasks.
Sports Und.
Object
Coin Flip
Web of lies
Multi-step Arithmetic
Count
de, 4s
du: 44
d2, la
d2 4
Greedy
70.0
53.0
48.0
76.0
58.0
53.6
39.0
19.0
8.0
0.0
58.8
36.0
CoT-decoding
94.0
57.0
55.0
87.0
63.0
57.6
56.0
42.0
35.0
16.0
58.0
39.2
Table 6: The model's s intrinsic reasoning ability varies depending on the task difficulty levels.
The presence of correct CoT paths depends on the task difficulty levels and correlates with task prominence in the pre-training distribution. The results in Table 6 (on P-LM-2 L) show that despite Co CoT-decodnng helps elicit better reasoning across almost all tasks, the gains vary significantly depending on the task difficulty level: the simpler the task is, the better chance that a correct reasoning path can be found. We also looked the model's top-k decoding paths, and found that models can generate the correct CoT paths when the solution involves at most I or 2 step knowledge manipulation, and the model starts to struggle with generating the correct CoT-paths when the steps become 3 or more. See Figure 5 (right) where the model's accuracy improves only for larger k's as task complexity increases (higher d and I's). This phenomenon suggests that the correct CoT-paths become harder to find when the task becomes more synthetic. This mirrors the finding in (McCoy et al., 2023), where the authors show language models are highly influenced by the distribution they have been trained on.
CoT-deco unveils model's intrinsic vulnerabilities in reasoning. Our results also unveil the specific areas where language models still struggle with: for example, on Coin-Flip and Web-of-Lies, we observe that the model can generate CoT paths that simulate the process step-by-step. but it can easily lose track of the states, especially when the task complexity increases. This reveals model's intrinsic vulnerability in performing accurate state tracking. On Multi-step Arithmetic, we observe that the model tends to perform calculations from left to right in the CoT-decoding paths, rather than following the correct mathematical order. These observations point to future directions where should improve the models on.
In addition, over these synthetic tasks, we found that existing CoT prompts on Big- Bennc-Harrt (Suzgun et al., 2022) play a larger "teaching" role in guiding the model solve such tasks, and in most cases the model just mimics the patterns in the CoT prompts to generate the correct response: e.g., the few-shot CoT prompts teach the model to perform explicit state tracking in each step for Web-of-lies. On the Sports Understanding task, CoT-decoding can better reveal LLMs' intrinsic strategy in solving a problem (see Appendix A), without being influenced by the external prompts which could be biased by the prompt designers. In contrast, few-shot CoT prompting constrains the model to follow an artificial strategy curated through human knowledge and intervention.
3.3 Combining CoT-decoding with CoT-Prompting
Mistral-7B
P Compute
Greedy decoding
9.9%
34.8%
((1)
Methods without prompting
Self-consistency without CoT
12.9%
40.6%
O(k)
CoT-decoding (max path)
25.1%
63.2%
O(k)
CoT-decoding (age path)
25.3%
64.1%
O(k)
Zero-shot CoT prompting
17.5%
75.1%
0(1)
Methods with prompting
Self-consistency with zero-shot CoT-prompt 39.4%
85.3%
O(k)
CoT--eccding (max path) + zero-shot CoT-prompt
40.2%
78.6%
O(k)
CoT-decoding (agg path) + zero-shot COT Coo-pprompt
18.4%
87.0%
((k)
Table Adding CoT-decoding on top of zero-shot CoT-prompping can further boost the reasoning performance on both models. The accuracy number here is computed over the GSM8K test set.
We further show that CoT-decoding can be easily combined with CoT-prompping, yielding even larger reasoning gains over multiple language models (Table 7). CoT-decoding maintains strong
8

---

performance compared to self-consistency (Wang et al., 2023a) when both are combined with CoT- prompts. Since self-consistency aggregates over multiple paths, we also show the performance based on our path aggregation algorithm, which significantly improves the model's 's reasoning at a similar cost. For fair comparison, we use k 10 for all methods that require multiple decoding paths.
4 Related Work
Mlain-of-thoughh reasoning in large language models. Existing work enhancing the reasoning abilitiee in large language models predominantly involve proposing better prompting techniques to better elicit CoT reasoning paths from the model (Kojima et al., 2022; Nye et al., 2021; Wei et al., 2022; Yao et al., 2023; Yasunaga et al., 2023; Zhou et al., 2023a). Despite achieving high performance, few-shot prompting techniques are often lask-specificc requiring prompt designs tailored to each task. This limits their generalizability across tasks. Advanced prompting techniques often require manually intensive prompt engineering, and their effectiveness varies depending the choice of prompts, resulting in inconsistent performance outcomes (Wang et al., 2022: Ye and Durrett, 2022: Zhou et al., 2023b). Efforts to discover improved prompts (Yang et al., 2024; Zhou al., 2023b) further entail model-specific and task-specific tuning.
In addition, these prompting techniques can subtly alter the vocabulary's posterior distribution in ways that remain largely elusive (Min et al., 2022; Webson and Pavlick, 2022). Specifically, prompts may assist in task decomposition, induce the model to generate additional tokens, or directly "teach" the model the exact underlying procedure to solve particular problems via manually crafted few-shot demonstrations. Dissecting the distinct influence of each aspect, however, presents significant challenge. In contrast, our work explores a different perspective within the decoding stage, demonstrating that, even without explicit prompting, the model inherently holds the capability to generate chain-of-thought reasoning paths across a wide set of tasks.
Recent work proposes to improve the CoT generation process via better controlling and verifying the steps generated, e.g., step verification (Lightman et al., 2023), process- based feedback (Uesato et al., 2022), self-evaluation guided beam search (Xie et al., 2023), and PathFinder (Golovneva et al., 2023). Note all these works still require CoT prompting in order to generate the CoT reasoning paths, while our work completely removes CoT prompting. In addition, these works focus on searching and verifying the "steps" produced by the language model, while our work purely searches in the decoding space on the token-level and utilizes the confidence scores when decoding the answer.
Additionally, recent works (Feng et al., 2023; Li et al., 2023b; Prystawski al., 2023). McCoy et al. (2023); Razeghi et al. (2022) demonstrate a similar phenomenon where the pretraining distribution heavily influences the model's performance few-shot reasoning.
Instruction-tuning to elicit CoTs in language models. When supervision is allowed, techniques such as instruction-tun -tnning or distillation offer another way to elicit reasoning paths from language models without explicit prompting (Chung et al., 2022: Huang et al., 2023; Magister et al., 2023). However, these approaches typically involve resource- models and require a large set of examples annotated with CoTs, which may not be readily available.
iesource-intensvve intensive fine-tuning over large language
Liu et al. (2024) show that a language model can be tuned by a proxy. Their method requires a few additional models, and implicitly assumes that the tuned model is well-optimized, e.g., on reasoning benchmarks the model needs to be tuned with CoT paths to enable contrasting logits with respect to the base untuned model. In contrast, our approach is entirely unsupervised and examines model's intrinsic ability in generating CoT paths, without resorting to fine-tuning or any additional models.
Decoding algorithms for language models. The predominant focus in existing literature on de- coding for language models revolves around aspects such as fluency, coherence, reduction of repeti- tiveness, and diversity in responses. Popular decoding algorithms used for language models include greedy decoding, temperature sampling (Ackley et al., 1985; Ficler and Goldberg, 2017), top-k sampling (Fan et al., 2018; Holtzman et al., 2018; Radford et al., 2019), and nucleus sampling (Holtzman et al., 2020). Additionally, there exist refined algorithms such as minimum Bayes risk decoding (Fikema and Aziz, 2020), and typical decoding (Meister et al., 2022). Diverse beam search (Vijayakumar et al., 2018) is another way to explore alternative paths model's generation. However, it emphasizes generation diversity rather than accuracy.

---

There is relatively little research dedicated to enhancing decoding algorithms specifically for reasoning tasks. Wang et al. (2023a) improves upon CoT prompting by sampling and aggregating over multiple generated responses to improve reasoning. Contrastive decoding (Li et al., 2023a) is another way to improve model's generation quality by penalizing the logits from smaller models, and recent work (O'Brien and Lewis, 2023) shows that contrastive decoding can contribute to enhancing reasoning performance. Shi et al. (2023) propose context-aware decoding to improves the faithfulness of language models. These approaches typically require additional information, such as employing additional models to generate contrasting logits or incorporating additional contexts. In contrast, our work relies solely single model without the need for supplementary knowledge.
Decoding algorithms for efficiency. In addition to decoding algorithms for improving quality, there is substantial body of research dedicated improving decoding efficiency, e.g., speculative decoding (Chen et al., 2023a; Leviathan et al., 2022; Zhou et al., 2024). This line of work is orthogonal our work their primary focus on improving model's reasoning performance. However, these techniques could potentially be leveraged to improve the efficiency of CoT-decoding.
5 Conclusion and Discussion
We investigate the inherent capabilities of language models in generating CoT reasoning paths during decoding, abstaining from any specialized prompting. Our findings indicate that, contrary to the prevalent practice of exclusively employing greedy decoding, exploring alternative top-k tokens in the decoding space reveals the natural existence of reasoning paths within these models. Furthermore, our empirical observations highlight that the presence of a CoT reasoning path correlates with increased model confidence in decoding its final answer. Based on this observation, we introduce CoT-decoding to extract more reliable decoding paths from language models, thereby enhancing their overall reasoning performance.
Discussion and Limitations. The exploration of alternative decoding paths incurs additional com- putational costs. Future work could leverage the CoT-decoding paths to fine-tune the model to further enhance its reasoning capabilities. Additionally, in cases where the answers are more open-ended, utilizing the probability differences the top two tokens as an indicator how models prefer one answer over another could be less precise. While existing work (Burns et al., 2023) leverages the model's activation space to uncover latent knowledge, its applicability is restricted to answering yes-no questions. We hope that future research can address this limitation by delving deeper into the model's 's internal representation across a broader, more open-ended answer space.
Our current exploration focuses on branching at the first token, but for future work one can explore branching at any token and searching for the best possible paths during the decoding phase. The computational cost will be substantially higher though, and how to reliably identify the best token during the search will an interesting direction explore. In addition, we leverage the model's intrinsic probability of ranking the top-k tokens during the initial decoding step. For more complex or nuanced tasks, however, if the model inadequately trained, it is possible that none the top-k tokens will yield relevant paths. This limitation in turn, help identify specific areas of model weakness, indicating the need for additional data coverage during training or for explicit guidance via expert knowledge during inference to successfully address these tasks.
Acknowledgements
We would like to thank Yongchao Zhou, Yifeng Lu, Dale Schuurmans, and Ed Chi for helpful discussion and feedback on this work.
References
D. H. Ackley, G. E. Hinton, and T. J. Sejnowski. A learning algorithm for boltzmann machines. Cognitive Science, 91):1477-19, 1985. ISSN 0364-0213. URL htttpp:://wwwsscenneeeee com/science wttsssciicceeeeeeeeeeeeeeccceces /onm//cceence//tiicle///ee http:///rraaa///////0/0011660000
Z. Allen-Zhu and Y. Li. Physics of language models: Part 3.2, knowledge manipulation, 2023,
10

---

R. Anil, A. M. Dai, O. Firat, M. Johnson, D. Lepikhin, A. Passos, S. Shakeri, E. Taropa, P. Bailey, Z. Chen, et al. Palm 2 technical report. arXiv preprint arXiv:2305.10400: 2023.
B. bench authors. Beyond the imitation game: Quantifying and extrapolating the capabilities of language models. Transactions on Machine Learning Research, 2023. ISSN 2835-8856. URL https://opperrevew net httt:/fooommidduyyLLByooo
L. Berglund, M. Tong, M. Kaufmann, M. Balesni, A. C. Stickland, T. Korbak, and O. Evans. The reversal curse: Llms trained on "a is b" fail to learn "b is a", 2023.
T. Brown, B. Mann, N. Ryder, M. Subbiah, J. D. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam,
G. Sastry, A. Askell, al. Language models are few-shot learners, Advances neural information processing systems, 33: 1 877-19901, 2020.
C. Burns, H. Ye, D. Klein, and J. Steinhardt. Discovering latent knowledge in language models without supervision. In The Eleventh International Conference Learning Representations, 2023. URL
net/
C. Chen, Borgeaud, G. Irving. J.-B. Lespiau, L. Sifre, and J. M. Jumper. Accelerating large language model decoding with speculative sampling. ArXiv, abs/2302.01318, 2023a. URL https://api semanticscholas
W. Chen, X. Ma, X. Wang, and W. W. Cohen. Program of thoughts prompting: Disentangling computation from reasoning for numerical reasoning tasks. Transactions Machine Learning Research, 2023b. ISSN 2835-8856. URL attpp::/openree
net aet/f Yd-z1dd2-222sadd
A. Chowdhery, Narang, J. Devlin, M. Bosma, G. Mishra, A. Roberts, P. Barham, H. Chung, C. Sutton, S. Gehrmann, P. Schuh, K. Shi, S. Tsvyashchenko, J. Maynez, A. Rao, P. Barnes, Y. Tay, N. Shazeer, V. Prabhakaran, E. Reif, N. Du, Hutchinson, R. Pope Bradbury, Austin, M. Isard, G. Gur-Ari, P. Yin, T. Duke, A. Levskaya, S. Ghemawat, S. Dev, H. Michalewski,
X. Garcia, V. Misra, K. Robinson, L. Fedus, D. Zhou, D. Ippolito, D. Luan, H. Lim, B. Zoph, A. Spiridonov, R. Sepassi, D. Dohan, S. Agrawal, M. Omernick, A. M. Dai, T. S. Pillai, M. Pellat, A. Lewkowycz, E. Moreira, R. Child, O. Polozov, K. Lee, Z. Zhou, X. Wang, B. Saeta, M. Diaz, O. Firat, M. Catasta, J. Wei, K. Meier-Hellsterr D. Eck, J. Dean, S. Petrov, and N. Fiedel. Palm: Scaling language modeling with pathways. Journal of Machine Learning Research, 24(240):1-113, 2023. URL http: http://mmmroooorr.e org/ pttppp/app//////////// 22412244211 1114..44.htt
H. W. Chung, L. Hou, S. Longpre, B. Zoph, Y. Tay, W. Fedus, Y. Li, X. Wang, M. Dehghani, S. Brahma, A. Webson, S. Gu, Z. Dai, M. Suzgun, X. Chen, A. Chowdhery, A. Castro-Ros, M. Pellat, K. Robinson, D. Valter, S. Narang, G. Mishra, A. Yu, V. Zhao, Y. Huang, A. Dai, H. Yu, S. Petrov, E. H. Chi, J. Dean, J. Devlin, A. Roberts, D. Zhou, Q. V. Le, and J. Wei, Scaling innrucctio-finetunne language models, 2022.
K. Cobbe, V. Kosaraju, M. Bavarian, M. Chen, H. Jun, L. Kaiser, M. Plappert, J. Tworek, J. Hilton, R. Nakano, C. Hesse, and Schulman. Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14168. 2021.
B. Fikema and W. Aziz. Is MAP decoding all you need? the inadequacy of the mode in neural machine translation. In Proceedings of the 28th International Conference on Computational Linguistics, pages 1506-4520, Barcelona, Spain (Online), Dec. 2020. International Committec on Computational Linguistics. URL https: cettps://aclatthtnt /wtp///aaaanntoooo.oaaaa org/ 2020 coling wwllinggmin....mmmmm
A. Fan, M. Lewis, and Y. Dauphin. Hierarchical neural story generation. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pages 889-898, Melbourne, Australia, July 2018. Association for Computational Linguistics. doi: 10.18653/v1/P18. 1082. URL attps://aclanthoo/
org/P18- 1082.
G. Feng, B. Zhang, Y. Gu, H. Ye, D. He, and Wang. Towards revealing the mystery behind chain of thought: theoretical perspective. Thirty-sevetth Conference on Neural Information Processing Systems, 2023. URL https: httpps://ppereeeeee /ppp//eeeeeeeeeeee//eeeeee wtwpenreiew..eeefoorrrrr/ere httt:/oorrmmiiiitgHAAAAAAAAAl
11

---

J. Ficler and Y. Goldberg. Controlling linguistic style aspects in neural language generation. In Proceedings of the Workshop on Stylistic Variation, pages 94-104, Copenhagen. Denmark, Sept. 2017. Association for Computational Linguistics. doi: 10. 10.18653//1/WW1-44912. URL. https: //aclanthology... wwwpoogg..rg//////// wwt//o/-g/// Mt///W17499
L. Gao, A. Madaan, Zhou, U. Alon, P. Liu, Y. Yang, J. Callan, and G. Neubig. Pal: Program-aided language models. arXiv preprini urXiv:221 1.222211.10433 2022.
Gemini. Gemini: family of highly capable multimodal models. arXiv preprint arXiv:2312.11805, 2023.
O. Golovneva, S. O'Brien, Pasunuru, T. Wang, Zettlemoyer M. Fazel-Zarandi, and A. Celikyil- maz. Pathfinder: Guided search over multi-step reasoning paths, 2023.
A. Holtzman, J. Buys, M. Forbes, A. Bosselut, D. Golub, and Y. Choi. Learning to write with cooperative discriminators. Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1638-1649 Melbourne, Australia, July 2018. Association for Computational Linguistics. doi: 10. 10.18655//1/P11--1552 URL https: // //aclanthology. org/ PP1-112211
A. Holtzman, J. Buys, L. Du, M. Forbes, and Y. Choi. The curious case of neural text degeneration. In International Conference on Learning Representations, 2020. URL https: //ppr////////reee... net eet/foruuniddryg@@pee
J. Huang. S. Gu, L. Hou, Y. Wu, X. Wang, H. Yu, and J. Han. Large language models self- self-improve. In H. Bouamor, J. Pino, and K. Bali, editors, Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pages 1051-1063 Singapore, Dec. 2023. Association for Computational Linguistics. URL httph:ttp//// aallooollloooyyyooo org/2023 emnlp-mae p-mmann......... .emaain.67....
H. Ivison, Wang. V. Pyatkin, N. Lambert, M. Peters, P. Dasigi, J. Jang, D. Wadden, N. A. Smith, I. Beltagy, and H. Hajishirzi. Camels in a changing climate: Enhancing Im adaptation with tulu 2023.
A. Q. Jian, A. Sablayrolles, A. Mensch, C. Bamford, D. S. Chaplot, D. de las Casas, F. Bressand,
G. Lengyel, G. Lample, L. Saulnier, L. Lavaud, M.-A. Lachaux, P. Stock, T. L. Scao, T. Lavril,
T. Wang, T. Lacroix, and W. E. Sayed. Mistral 7b, 2023.
H. Jiang and M. Gupta. Minimum-margio active learning, 2019.
T. Kojima, S. S. Gu, M. Reid, Y. Matsuo, and Y. Iwasawa. Large language models are zero-shot reasoners. In Advances in Neural Information Processing Systems, volume 35, pages 22199-22213, 2022.
Y. Leviathan, M. Kalman, and Y. Matias. Fast inference from transformers via speculative decoding. In International Conference on Machine Learning, 2022. URL https://app: htt./app..mmaniiiiccmmmm semanticscholaas org/Co heg/CorpusID-.. : 254096365.
X. L. Li, A. Holtzman, D. Fried, P. Liang, J. Eisner, T. Hashimoto, L. Zettlemoyer, and M. Lewis. Contrastive decoding: Open-ended text generation as optimization. In A. Rogers, Boyd- Graber, and N. Okazaki, editors, Proceedings of the 61 Annual Meeting of the Association for Computational Linguisties (Volume Long Papers), pages 12286 12312, Toronto, Canada, July 2023a. Association for Computational Linguistics. doi: 10. 10.18653/w1/2023.aco wow.:o/2.2...l--oo.666..3333 URL org. 2023. acl 1ong. 687.
Y. Li, K. Sreenivasan, A. Giannou, D. Papailiopoulos, and S. Oymak. Dissecting chain-of-thougeee Compositionality through in-context filtering and learning. In Thirry-seentth Conference on Neural Information Processing Systems, 2023b. URL httpp::///opnreviee..eeee xEhKwsqxMa.
H. Lightman, V. Kosaraju, Y. Burda, H. Edwards, B. Baker, T. Lee, J. Leike, J. Schulman, I. Sutskever, and K. Cobbe. Let's verify step by step, 2023.
W. Ling, Yogatama, C. Dyer, and Blunsom. Program induction by rationale generation: Learning to solve and explain algebraic word problems, arXiv preprint arX1v1100..04146, 2017.
12

---

A. Liu, X. Han, Y. Wang, Y. Tsvetkov, Y. Choi, and N. A. Smith. Tuning language models by proxy. 2024.
L. C. Magister, J. Mallinson, Adamek, E. Malmi, and A. Severyn. Teaching small language models to reason, 2023.
R. T. McCoy, S. Yao, D. Friedman, M. Hardy, and T. L. Griffiths. Embers of autoregression: Understanding large language models through the problem they are trained to solve, 2023.
C. Meister, T. Pimentel, G. Wiher, and R. Cotterell. Typical decoding for natural language generation. arXiv preprint arXiv:2202.0000 00066, 2022.
Min, X. Lyu, A. Holtzman, Artetxe, M. Lewis, H. Hajishirzi, and Zetrlemoyer. Rethinking the role of demonstrations: What makes in-context learning work? In EMNLP, 2022.
M. Nasr, N. Carlini, J. Hayase, M. Jagielski, A. F. Cooper, D. Ippolito, C. A. Choquette-Choo E. Wallace, F. Tramèr, and K. Lee. Scalable extraction of training data from (production) language models, 2023.
M. Nye, A. J. Andreassen, G. Gur-Ari, H. Michalewski, J. Austin, D. Bieber, D. Dohan, A. Lewkowycz. M. Bosma, D. Luan, et al. Show your work: Scratchpads for intermediate computation with language models. arXiv preprint arXiv:2112.00114 2021.
O'Brien and M. Lewis. Contrastive decoding improves reasoning large language models, 2023.
OpenAI. Gpt-4 technical report. arXiv preprint arXiv:2303.08774. 2023.
B. Prystawski, M. Y. Li, and N. Goodman. Why think step by step? reasoning emerges from the locality of experience. In Thirty-sevents Conference on Neural Information Processing Systems, 2023. URL /tttps///peenrvviee net./oormm
A. Radford, J. Wu, R. Child, D. Luan, D. Amodei, and I. Sutskever. Language models are unsupervised multitask learners. 2019.
Y. Razeghi, R. L. Logan IV, M. Gardner, and Singh. Impact of pretraining term frequencies on few-shot numerical reasoning. In Y. Goldberg, Z. Kozareva, and Y. Zhang, editors, Findings of the Association for Computational Linguistics: EMNLP 2022, pages 840-854, Abu Dhabi, United Arab Emirates, Dec. 2022. Association for Computational Linguistics. doi: 10. 18.58v/3/v1 1/2022. findings-emnlp.59, URL https:tp/// hatp//aaaaaattoogoooooooo org/ 2022. findings-emnl] 59.
B. Romera-Paredes, M. Barekatain, A. Novikov, M. Balog, M. P. Kumar, E. Dupont, F. J. R. Ruiz, J. Ellenberg, P. Wang, O. Fawzi, P. Kohli, and A. Fawzi. Mathematical discoveries from program search with large language models. Nature, 2023. doi: 10. 10.1038/s41588 023 06924-6.
S. Roy and D. Roth. Solving general arithmetic word problems. In Proceedings the 2015 Conference on Empirical Methods in Natural Language Processing, 2015. doi: 10.18653/v I/D1S- 1202. URL https: / acl aalaa/aaaanntooyyyyoooooo
hoggD15-11 1202.
B. Settles. Active learning literature survey. 2009.
W. Shi, X. Han, M. Lewis, Y. Tsvetkov, L. Zettlemoyer, and S. W. tau Yih. Trusting your evidence: Hallucinate less with context-aware decoding, 2023.
M. Suzgun, N. Scales, N. Schärli, S. Gehrmann, Y. Tay, H. W. Chung, A. Chowdhery, Q. V. Le, E. H. Chi, D. Zhou, and Wei. Challenging big-bench tasks and whether chain-of-thought solve them. arXiv preprint arXiv:22 10.0092,, 2022.
G. Team, T. Mesnard, C. Hardin, R. Dadashi, S. Bhupatiraju, S. Pathak, L. Sifre, M. Rivière, M. S. Kale, Love, Tafti, L. Hussenot, P. G. Sessa, A. Chowdhery, A. Roberts, Barua, A. Botev, A. Castro-Ros Roor, A. Slone, A. Héliou, A. Tacchetti, A. Bulanova, A. Paterson, B. Tsai, B. Shahriari, C. L. Lan, C. A. Choquette-
C. Crepy, D. Cer. D. Ippolito, D. Reid, E. Buchatskaya, Ni, E. Noland, G. Yan, G. Tucker, G.-C. Muraru, G. Rozhdestvenskiy, H. Michalewski, I. Tenney, Grishchenko, J. Austin, Keeling, Labanowski, J.-B. Lespiau, Stanway, Brennan, Chen, J. Ferret, J. Chiu, J. Mao-Jones, K. Lee, K. Yu, K. Millican, L. L. Sjoesund, L. Lee, L. Dixon,
13

---

M. Reid, M. Mikuta, M. Wirth, M. Sharman, N. Chinaev, N. Thain, O. Bachem, O. Chang,
O. Wahltinez, P. Bailey, P. Michel, Yotov, R. Chaabouni, R. COmanescu, Jana, R. Anil, R. Mcllroy, R. Liu, R. Mullins, S. L. Smith, S. Borgeaud, S. Girgin, S. Douglas, S. Pandya, S. Shakeri, S. De, T. Klimenko, T. Hennigan, V. Feinberg, W. Stokowiec,
hui Chen, Z. Ahmed, Z. Gong. T. Warkentin, L. Peran, M. Giang, C. Farabet, O. Vinyals, J. Dean, K. Kavukcuoglu,
D. Hassabis, Z. Ghahramani, D. Eck, J. Barral, F. Pereira, E. Collins, A. Joulin, N, Fiedel, E. Senter,
A. Andreev, and K. Kenealy, Gemma: Open models based on gemini research and technology, 2024.
J. Uesato, N. Kushman, R. Kumar, Song. N. Siegel, L. Wang, A. Creswell, G. Irving, and Higgins. Solving math word problems with process- and outcome- based feedback, 2022.
A. K. Vijayakumar, M. Cogswell, R. R. Selvaraju, Q Sun, S. Lee, D. J. Crandall, and D. Batra. Diverse beam search for improved description of complex scenes. In S. A. Mcllraith and K. Q. Weinberger, editors, Proceedings of the Thirty-Secone AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018, pages 7371-7379. AAAI Press, 2018. doi: 10. (0.1609/AAALV33211.222
URL https: : / /doii/i..o//// org/10. 10. 1609//60aaa vv2i1. 12340.
X. Wang, J. Wei, D. Schuurmans, Q. Le, Chi, and D. Zhou, Rationale- aationale-augmnned ensembles in language models, 2022.
X. Wang, J. Wei, D. Schuurmans, Q. V. Le, E. H. Chi, S. Narang, A. Chowdhery, and D. Zhou. Self- consistency improves chain of thought reasoning in language models. In The Eleventh International Conference on Learning Representations, 2023a. URL https: /ttp////peeeeeeeeeeeeeeeeeeeeeee net/forum?dd= 1PL1NIMMrw.
Y. Wang, H. Ivison, P. Dasigi. J. Hessel, T. Khot, K. R. Chandu, D. Wadden, K. MacMillan, N. A. Smith, I. Beltagy, and H. Hajishirzi. How far can camels go? exploring the state of instruction tuning on open resources, 2023b.
A. Webson and E. Pavlick. Do prompt-based models really understand the meaning of their prompts? In M. Carpuat, M.-C. de Marneffe, and I. V. Meza Ruiz, editors, Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 2300-2344, Seattle, United States, July 2022. Association for Computational Linguistics. doi: 10.18653//1/0022.mmaam naacl main. 167. URL https: /tape:://allaaaaea halpa//coanntooogy...... org/ wwa.aaaallaaaaa 167.
J. Wei, X. Wang. D. Schuurmans, M. Bosma, brian ichter, F. Xia, E. H. Chi, Q. Le, and D. Zhou. Chain of thought prompting elicits reasoning in large language models. In A. H. Oh, A. Agarwal, D. Belgrave, and K. Cho, editors, Advances in Neural Information Processing Systems, 2022. URL https: //ppre////peeeeieee net/ wwwmmiddd............. _tt.iiidddviie________
Y. Xie, K. Kawaguchi, Y. Zhao, X. Zhao, M.-Y. Kan, J. He, and Q. Xie. Self-evaluation guided beam search for reasoning. In sevethh Conference on Neural Information Processing Systems, 2023. URL
C. Yang. X. Wang, Y. Lu, H. Liu, Q. Le. D. Zhou, and X. Chen. Large language models as optimizers. In The Twelfth International Conference on Learning Representations, 2024. URL hittss:/openreet
net. orum B.-BBVVWWEE.LLL...
S. Yao, D. Yu, J. Zhao, I. Shafran, T. L. Griffiths, Y. Cao, and K. R. Narasimhan. Tree of thoughts: De- liberate problem solving with large language models. In Thirty-sevent Conference on Neural Infor mation Processing Systems, 2023. URL
met/forun wew.rrmmiddxxx1exxx1111
M. Yasunaga, X. Chen, Y. Li, P. Pasupat, J. Leskovec, P. Liang, E. H. Chi, and D. Zhou. Large language models analogical reasoners. arXiv preprint arXiv:2310.01714 2023.
X. Ye and G. Durrett. The unreliability of explanations in few-shot prompting for textual rea- soning. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 30378-30392. Curran As- sociates, Inc., 2022. URL https: httel:ttt/////oeeeeeiieee neurips cttpps.ccpppaaaee sace/pppr__ffft www.ffllepppppee /22pe///////// www.erenc.eeeenneeeeeeeee pdf.
14

---

D. Zhou, N. Schärli, L. Hou, J. Wei, N. Scales, X. Wang, D. Schuurmans, C. Cui, O. Bousquet, Q. V. Le, and E. H. Chi. Least-to-most prompting enables complex reasoning in large language models. In The Eleventh International Conference on Learning Representations, 2023a. URL https: attps://openee /ttp://eee/eeeeeeeeeeeeeeee net/forum? www.rrrdddiiiie dd-rrmmgg7777
Y. Zhou, A. I. Muresanu, Z. Han, K. Paster, S. Pitis, H. Chan, and J. Ba. Large language mod- els are human- prompt engineers. In The Eleventh International Conference on Learning Representations, 2023b. URL https://openrr
net www.weewweee.weeeeeeeeeeeeeeeeee /or
Y. Zhou, K. Lyu, A. S. Rawat, A. K. Menon, A. Rostamizadeh, S. Kumar, J.-F. Kagy, and R. Agar- wal. Distillspee: Improving speculative decoding via knowledge distillation. In The Twelfth International Conference on Learning Representations, 2024. URL https: htt.httt::/ forum?2d=rsyY6332aff
pettps://operreeet http://pppeeeeeeeeeee/e
15

---

A Qualitative analysis on CoT paths elicited by CoT-decoding and existing approaches
In Table 8, present qualitative examples illustrating the distinctions in the generated CoTs for each method. Overall we observe that CoT-decoding exhibits more "free-form" CoT generation in comparison alternative CoT prompting methods. This divergence may be attributed to two factors: (1) we encourage the diversity at the initial decoding step, and (2) the absence of explicit constraints imposed by prompting.
Another noteworthy observation is that CoT-decoding can better reveal what LLMs' intrinsic strategy in solving problem, without being influenced by the external prompts which could be biased by the prompt designers. Take the last example in Table 8, we see that the few-shot CoT path is heavily influenced by the few-shot prompts. Specifically, the few-shot prompts. sourced from (Suzgun et al., 2022), consistently follow a standard analytical approach first assessing the person's profession, followed by evaluation of whether the profession aligns with the action. This aligns with the standard method of solving this particular task.* 4 In contrast, CoT-decoding reveals paths that deviate from the conventional problem-solving approach. Despite yielding incorrect final answer according to the ground truth in some cases, the CoT paths remain to be valid.
[GSM8K] Claire makes 3 egg omelet every morning for breakfast. How many dozens of eggs will she 4 weeks?
Greedy: 3
CoT-decoding: A dozen is 12. 3 eggs per day for 4 weeks is 84 eggs. 84/12 = 7. 7 dozen eggs.
Few-shot CoT: There are 7 days in week. 4 weeks is 4 * 7 28 days. She cats 3 eggs each day, in 28
eggs 84/ 12 = 7 dozen eggs. The answer is 7. Zero-shot CoT: First, how many eggs does she eat week? days in week, 3 eggs per day, eggs per week. Now, how many eggs does she eat in weeks? 4 x 21 84 eggs. Now, how many dozens of eggs is that? 84 12= dozens.
days she cats 28 3 84 eggs. dozen is 12 eggs.
3
[Year Parity] Was Nicolas Cage born in
odd year?
Greedy: Nicolas Cage was born in an odd year. CoT-decoding: Cage was born 1964, an even year.
Zero-shot CoT: I. Nicolas Cage was born in 1964.
2. 1964 is an even number.
Therefore, Nicolas Cage was born in an even year.
[Sports Understanding) Is the following sentence plausible? "Walker Buchler earned trip to the penalty box." " Greedy: No.
CoT-decoding (the top few paths):
Surc, if he's playing hockey.
In the context of baseball game, no.
I'm not sure what you mean by "plausible". It's a perfectly grammatical sentence, and it's a perfectly reasonable thing to say.
Few-shot CoT: Walker Buchler is basehall player. Penalty box is part ice hockey. So the answer is no.
Table 8: Example of generated CoTs using different approaches.
B Examples of CoT-decoding Paths on Additional Tasks
Table 9 provides example where the Mistral-7B model attempts to directly solve the question with greedy decoding. However, when considering alternative tokens for the first decoding step, CoT reasoning again emerges from the model's decoding paths. We show additional examples comparing greedy decoding with CoT-decoding on various reasoning tasks in Table 10.
In Table 11, we further show an example where CoT-decoding improves over the Mistral-7B instruction-tuned model. We found in some cases, even after instruction-tuning, the model still tends to address the question by directly providing consistent behaviours by first eliciting the CoT path before generating an answer. For this example, another interesting observation is that, the model generates CoT after initial answer "16" is
answer, while CoT-decoding can enable more
lattpp://ggatie con/ hwtpll/ceee//eeeeeeee www.gooooggo--o-oo BBIIIBBBeGG////Beeeeeeeeeee beach/ httt///teee///eeee wtteee//nii/bbbbeeccc//e www.g/gbnwnceeecearn...... taeks/ sporte, underetanding
16

---

I have 3 apples, my dad has 2 apples than me, how many apples do have in total?
Top-k paths:
k 0: 5 (0.227)
k = 1: have 3 apples, my dad has 2 more apples than me, how many apples do we have in total? (0.722)
k 2: We have apples. (0.317)
k 3: My dad has 5 apples and I have 3 apples, have apples in total. (0.956)
k 8: You have 3 apples, your dad has more apples than you, so he has 342=5 apples. Together you have
3+5-8 apples. (0.931)
Table 9: Example of the top-k paths from the Mistral-7B petrained-modde showing similar behaviour where CoT paths again exist but are ranked lower during decoding.
generated. In this case, the model's generated CoTs will be affected by the Atready-generatee answer, thus possibly leading to an incorrect CoT path afterwards.
In Table 12, we show the top-k paths for two tasks (math and year parity) on the Mistral-7B model, along with their A values in each decoding path. Again we see that high A values correlate well with the CoT paths and more correct final answers.
C Choice of k on Additional Models and Tasks
In Figure 6, we further show how the choice of i affects the performance over the Mistral-7B model. We include both the pre-trained model as well as the instruction-tung tundd model. Overall we found the improvement is highly consistent for the pre-trained model with higher value of k. However, for the instruction- tuned model, since the model is already fine-tuned with CoT data to generate CoT's for the first few decoding paths, exploring more tokens towards larger does not necessarily result in further gains.
GSMBK
MultiArith
Parity
60-
70
Accuracy
20
Accuracy
Accuracy
60-
10
20
:50
Pre trained
treetrained
Pre traineeidd Insi-tured
20
40
10
10
Top-k tokens decoding paths
tokens for decoding paths
Top-k tokens for decoding paths
Figure Accuracy with respect the choice of le over the Mistral-7B model.
In Table 13, we illustrate with a concrete example of how the path aggregation algorithm works and why it could identify the correct answer more reliably. For the correct answer 18, we see it appears
4 times, each with A 0.994 (A: 0), 0.911 (h: = 6), A 0.584 8), and A = 0.999 (k 9), so overall its Ex Axa 3.5; while all other incorrect answer options 14, 16, 20, 10 have much lower sum of A.
D Details on Experimental Settings
Experiment settings for the PaLM-2 Model family. For all the experiments on CoT-decoding. we use an input sequence length of 256 and maximum decoding step of 128, given that the input sequence direct formatting of original question. For few-shot CoT prompting, the input sequence length needs to be extended to 1024 given set of few-shot exemplars is used (Wei et al., 2022). For both few-shot CoT and zero-shot CoT prompting, the output decoding step is set to 256 because observe longer output sequences under both techniques.
17

---

[Sports Understanding]
Is the following sentence plausible? "Kawhi Leonard took turnaround jumper." Greedy: No.
CoT-decoding: Kawhi Leonard is basketball player. - yes
Is the following sentence plausible? "Neymar took backhand shot in the Stanley Cup." Greedy: No.
CoT-decoding: Neymar is a soccer player, and the Stanley Cup is a hockey tournament. -> no
the following sentence plausible? "Carson Wenfz took to ice." " Greedy: No.
CoT-decoding: Carson Wentz is quarterhack for the Philadelphia Eagles. He is not a hockey player. - no
[Coin Flip]
A coin heads up. Raymond flips the coin. Conception flips coin. the coin still heads up?
Greedy: No.
Co'--dcodiing Raymond flips the coin. The coin is now tails Conception flips the coin. The coin is now heads up. (correct state tracking)
A coin is heads up. Millie does not flip the coin. Teressa does not flip the coin. Conception flips the coin. Is the coin still heads up?
Greedy: No.
-oeoddco, Millie does not flip the coin. Teressa does not flip the coin. Conception flips the coin. The coin is still heads up. (failed state tracking)
A coin heads up. Inga flips the coin. Jamey does not flip the coin. Shalonda does not flip coin. Shaunda flips the coin. Is the coin still heads up?
Greedy: No. The coin is tails up.
CoT-decoding: Since the coin was flipped an odd number of times, it is not heads up. (flawed alternative reasoning)
[Multi-step Arithmetic]
-3 -9* 1)=
Greedy:
CoT-decoding: (((3 ((3+-3)+ (1 (correct)
=
8*3+
Greedy: 100
CoT-decoding: ((6 + 8) + 3) 5 52 47 (incorrect, the model does calculation from left
right rather than following the order of operations in math.)
(10-9 9 77 + 3) (-2
Greedy: -1
CoT-decoding: - 7
+ ((-----7))) ( ((0-))))))))))))))))) -0 (0
* +-7+3 25) (0 -63 + - 25) 3 25)=
(correct)
Table 10: Example of generated CoTs by CoT-decoding without explicit prompting.
For input format, by default we use "Q: Antesttion\nAA: for all the tasks. For multi-step arithmetic we use the original input without the QA format, as unnatural to insert Q/A given the original question (e.g., "3+5-6=").
Model ids used for all open-sourced models. We use the huggingface library for both Mistral and Gemma models, the corresponding model ids used in our experiments are:
Mistral-7B pre-trained/inst-uundd. mistralai/MMistral-BBB-00
Gemma-7B pre-trained: google/gemma-7b
Identifying the answer spans. To identify the answer spans, we extract the last numerical numbers or the available options (e.g., "even" or "odd" for the year parity task) over the Mistral and Gemma models, as this is the common protocol used in evaluating public language models (Ivison et al., 2023; Wang et al., 2023b). For PaLM-2 model families, we extend the model's 's output with the prompt "So the answer is" and align the continuations in the original decoding path as the answer.
18

---

[GSM8K] John invited 20 people birthday party. Each guest will eat 2 hot dogs. He already has 4 hot dogs left over from previous party. If a pack of hot dogs contains hot dogs and costs $2, how much does he need to spend on hot dogs?
Greedy (A- = 0, A = 0.56):
John needs to spend $16 on hot dogs. Here's 's the reasoning:
1. First, we need to determine how many hot dogs John has in total. He has 4 left over from previous party and 20 guests at his current party. So, he has 4 20 24 hot dogs.
2. Next, we need to figure out how many packs of hot dogs he needs buy. Each pack contains 6 hot dogs.
he' need 24 / 6 4 packs.
3. Finally, need calculate the cost of buying these packs. Each pack costs $2, 4 packs will cost 4
$2 $8.
Therefore, John needs to spend $16 on hot dogs for his party.
CoTT-Dcodiig (A:
1.0):
Let's break down the problem:
John has hot dogs left over.
He needs to provide hot dogs for each the 20 guests.
3. That means he needs to provide total of 20 x 2 ((20*2=40))40 hot dogs.
4. Since he already has hot dogs, he needs to buy 40 4= ((40-4=36))36 hot dogs.
5. pack of hot dogs contains hot dogs, he needs buy 36 6= ((3/6=6))6 )6 packs of hot dogs.
Each pack hot dogs costs $2, so needs to spend 6 x $2 == (((6+==12) on hot dogs.
Final answer: John needs to spend $12 on hot dogs.
Table 11:
Example responses to a GSM8K question from the Mistral-7B instruction-tune model using greedy decoding vs CoT-decoding.
I have 3 apples, my dad has 2 more apples than me, how many apples do we have in total? Top-k paths:
k 0: 5 (0.227)
k 1: have 3 apples. my dad has 2 more apples than me, how many apples do we have in total? (0.722)
k 2: We have apples. (0.317)
k 3: My dad has apples and have 3 apples, so have apples in total. (0.956)
k = 4: A: (0.211)
λ = 5: The answer is S. (0.313)
& 6: Five
k 7: Three apples.
8: You have apples, your dad has more apples than you, so 3+2=5 apples. Together you have
3+5=8 apples. (0.931)
= 9: $3+2=55 (0.902)
Was Daniel Portman born in even or odd year?
Top-k paths:
k = 0: 1992
k 1: Even (0.146)
k 2: He born in an even year. (0.431)
3: Odd. (0.146)
k 4: Daniel Portman was born an even year. (0.434)
k = 5: His birthday is on the 25th of March, 1992. That mcans he was born in an even year. (0.968)
k 6: An even year. (0.281)
K 7: The year Daniel Portman born an even year. (0.498)
8: don't 't know.
k 9: In an even year. (0.426)
Table 12: Example of the top-k paths from the Mistral-7B pretrained modell (Mistral- 1)
showing a similar behaviour where CoT paths again exist but are ranked lower during decoding.
Additional processing when the continuation after "So the answer is" not found in the orig- inal decoding path. For math reasoning tasks we simply ignore that decoding path; for other reasoning tasks, we compute A over the continuation (again averaged over all tokens) to handle more open-ended generation cases. This can happen in zero-shot QA because without any formatting constraint, the model can output a reasoning path without giving an explicit final answer. For symbolic reasoning tasks where the answer is choice between "yes" "no" (c.g., Coin Flip. Web of Lies),
19

---

Janet's ducks lay 16 eggs per day. She eats three for breakfast every morning and bakes muffins for her friends every day with four. She sells the remainder at the farmers' market daily for $2 per fresh duck egg. How much in dollars does she make every day at the farmers' market?
Top-k paths:
k 0: 16 16-3-4=9 eggs per day. 9 eggs per day x S2 per egg $18 per day. (0.994)
k = 1: $14 (0.095)
k 2: Janet makes $14 per day the farmers' market. (0.064)
k 3: The answer is 16. (0.162)
k 4: She makes $14 per day. (0.083)
k 5: (16 3 3-44 4) x 2= $20 (0.561)
k = 6: If Jamet cats three eggs and bakes with four, she has nine eggs left to sell. If she sells them for S2
each, she makes $18 per day. (0.911)
k 7: 16-3-4 x 2 10 (0.424)
k = 8: This is simple subtraction problem. 16 4- ==: 9. Janet makes $18 per day at the farmers' market.
(0.584)
9: To solve this problem, you need to know how many eggs Janet has left to sell. She starts with
eggs, eats 3, and uses 4 for baking. That means she has 16 16-33 - 4 9 eggs left to sell. She sells each egg for $2, so she makes 9 x S2 $18. (0.999)
Table 13: Example of the path aggregation algorithm on GSM8K question.
we compute the difference between the probabilities masses over "yes/true" and "no/false" (cases ignored). We found when the answer choices are fixed, processing the continuation in this way is slightly more accurate than computing A over the continuation directly, since sometimes the model might output invalid options like "We don't 't know" with high confidence. Despite the fact that it shows the model is uncertain about the question, this is not a valid answer option which causes difficulty in evaluation.
Remove ill-formed responses. Under zero-shot QA format and without explicit prompting, some- times the model can output ill-formed responses such as empty or repeated responses. Those responses are easy be filtered though, and we adopt simple heuristics like if the output response length is zero (meaning empty response) or the same as the maximum decoded step (meaning the response usually unfinished and repeats itself). We also filter responses that end a question mark as we found in some rare cases the model tends to repeat the input question. For Mistral models we found some cases the model outputs texts similar the training data in alternative decoded paths (similar to the findings in Nasr et al. (2023)), and we filter those as well since they do not directly address the input question.
Experiment settings for the Mistral model. For the Mistral pre-trained model, we format the question similarly as "Q: question\nA:"" For the Mistral instruction- finetunnd model, we follow Mistral's 's instruction cestruction-finetuiingg format by surrounding each question by 
 and 
 tokens, i..., "
 question //INST]" As hyperparameters, on math tasks we generate 200 new tokens for the pre-trained model and 400 new tokens for the instruction -uuned model, to make sure the responses do not get truncated in the middle. The instruction-tui tokens as we observe the Mistral model's 's responses get much longer after instruction-tume year parity task, we generate 50 new tokens for the pre-trate pre-trained model and 100 new tokens for the instruction-tuned model.
model requires a higher number of new For the
Additionally, for the year parity task, we found that due to their small model size, the Mistral-7B models cannot reliably extract the correct birth year of a celebrity in some cases. Consequently, we adjust the evaluation protocol: we first query the Mistral-7B model about the birth year for each celebrity, and use that as the ground truth to evaluate the original parity question. Names for which the Mistral-7B model cannot retrieve year information are disregarded, constituting a small portion (less than 2% on the intrucciion-tunede model).
Compute Resources. For Mistral and Gemma models, use A100 GPU with 40 GB RAM to run the decoding experiments. On average each task takes about 10-20 hours to run depending on the number of examples. On PaLM-2 models, we use TPU v4 and depending on the task and model sizes, each job could take a few hours (for smaller model scales) to a few days (for the largest model size).
http:p/://uuggggggeeo.oo///tttta htn.ssstttrrt-----t-sutt------- Instruct-v0.1
20

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We accurately describe our contributions and scope throughout the entire
paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discuss our limitations both in the methodology section and in the last section ("Conclusion and Discussion").
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model cell-specification. asymptotic approximations only holding locally). ). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
21

---

Answer: [NA]
Justification:
No theoretical result involved.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: We provide the full details of the experiment settings in both the experiment section and the appendix. We also attach our code in supplemental materials.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
22

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We use public datasets (with citations and links) and provide code in supplementary materials.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co
ittiibomissioooool111oe imPolicy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
/ /twpss.ccppubiiiie wwtpcccpppcccccpccc.cccccccccclt gwwpd//g////eeeeeeeeoooccoo.ss https//ooeSSubiisseeeeeee semeiissiooooo.o asionPolicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We provide details the experiment section as well as in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: Our results are deterministic (top-k tokens used the first decoding step. and then continue with greedy decoding), so there is no variance involved. We perform experiments over multiple public language models and the results can be easily reproduced.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
23

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for caleulating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (c.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτоr rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide details on the computer resources used in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https //tp:rr///////p///// hts//uullcc/EEeleee httpa////hhcccciieiineeesse
Answer:
[Yes]
Justification:
We adhere to the NeurIPS Code of Ethics throughout the entire paper.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We discuss in the last section on both the positive societal impacts (we can better inspect models' intrinsic reasoning capability) as well as negative societal impacts (the method incurs higher computational costs).
Guidelines:
The answer NA means that there is no societal impact of the work performed.

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our proposed method investigates the intrinsic reasoning capability in language models. It does not involve high risk of misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
We provide links and citations to each of the dataset used in this paper.
Guidelines:
The answer NA means that the paper does
existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
25

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. comddatasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
No new assets is introduced in this paper.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: No Study with Human Subjects in this paper.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: No Study with Human Subjects in this paper.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
26

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
27


Reviews:
[{"review_id": "YT2NCYGFta", "reviewer": "Reviewer_fBkE", "summary": "The paper investigates the intrinsic reasoning capabilities of LLMs without relying on prompting techniques like few-shot or zero-shot prompting. The study introduces an alternative approach by altering the decoding process, specifically by exploring the top-k alternative tokens rather than following the standard greedy decoding path. The proposed \"CoT-decoding,\" reveals that LLMs inherently possess chain-of-thought reasoning abilities that are often hidden by human-involved prompting / conventional decoding methods.", "questions": "Does the limitation of branching only at early decoding stages restrict the flexibility and applicability of CoT-decoding? Would exploring branching at later stages in the decoding process improve overall performance?", "limitations": "I do not identify any negative societal impacts in this paper.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper demonstrates that LLMs can generate CoT reasoning paths without explicit prompts by modifying the decoding process. This challenges the prevailing notion that LLMs require prompting to reason effectively. It shows that LLMs have inherent reasoning capabilities that are more accurately assessed by CoT-decoding.\n- Experimental results show that CoT-decoding naturally reveals CoT reasoning paths during the decoding process, significantly enhancing the model's reasoning capabilities and surpassing greedy decoding. It is also observed that these paths are more prevalent in tasks frequently encountered in pre-training data.\n- The paper is generally well-written and easy to follow.", "weaknesses": "- **Extra Computational Cost**: Exploring top-k alternative tokens for decoding paths requires additional computational resources. Compared to CoT/Zero-shot CoT/ComplexCoT/CoT-SC(n) where n is not a large number, CoT-decoding necessitates evaluating multiple decoding paths, which increases computational complexity and time cost, especially when dealing with complex multi-step tasks.\n- **Limitations in Open-ended Questions**: This method mainly relies on the model's confidence in specific answers during the decoding process to select reasoning paths. However, for more open-ended questions, this probability difference-based selection method may not be precise enough, making it challenging for LLMs to select the optimal path in a much larger answer space.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful review!\n\n> Does the limitation of branching only at early decoding stages restrict the flexibility and applicability of CoT-decoding? Would exploring branching at later stages in the decoding process improve overall performance?\n\nThanks for the question. We do have a study of branching at later stages in Figure 6, Appendix D due to space limit, and we show that branching at later steps is viable but incurs much higher computational cost. \nFor most tasks, we found that early branching significantly improves the diversity of potential paths, and is usually sufficient to uncover the CoT paths. With later branching, sometimes the model encounters difficulty recovering from incorrect paths (e.g., for the math question, after generating the token \"5\" the model is not able to recover from an erroneous path). \nFor some tasks though (e.g., the year parity task), mid-branching can help uncover more diverse paths, potentially leading to a better performance. We think it would be an interesting future direction to determine the optimal branching points depending on the specific task/question and efficiently search for the best possible paths.\n\n> Extra computational cost and limitation to open-ended questions.\n\nThanks for the feedback. Yes, as discussed in the limitation section, our method does incur higher computational costs and in practice, we can use the optimal paths identified from CoT-decoding to further fine-tune the language model, which can help the model directly output those paths during inference time. \n\nFor open-ended questions, we discussed that for some tasks identifying the answer could be non-trivial, and we hope this can be better addressed in future research by better learning the model’s internal representation across a broader, more open-ended answer space. Fine-tuning with CoT-decoding paths can potentially help here as well, as the model learns to output its thinking process first when it is uncertain on open-ended questions.", "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": "IwJXiU2tDF", "reviewer": "Reviewer_BrnW", "summary": "The paper investigates an innovative approach to eliciting chain-of-thought (CoT) reasoning from pre-trained large language models (LLMs) without the need for explicit prompting techniques, which typically require intensive prompt engineering and can obscure the model's inherent reasoning capabilities. Instead, this study proposes altering the decoding process by exploring alternative top-k tokens, rather than the conventional top-1 greedy decoding path. This method, termed CoT-decoding, effectively reveals natural CoT reasoning paths within the language model's outputs, leading to more accurate and confident model responses across various reasoning tasks.\nContributions:\n1. **Novel Decoding Strategy:** The paper introduces a novel decoding strategy that bypasses the need for prompt engineering by modifying the decoding process to explore alternative token paths, allowing the model to display its intrinsic reasoning capabilities.\n2. **Empirical Validation:** Extensive empirical studies demonstrate that this CoT-decoding approach not only enhances the accuracy of LLMs on reasoning tasks but also increases the confidence of the models in their answers, suggesting a higher reliability of the reasoning paths discovered.\n3. **Comparative Analysis:** The paper provides a comparative analysis of CoT-decoding against traditional methods, showing significant improvements over greedy decoding and other baseline methods across multiple benchmarks for mathematical and commonsense reasoning tasks.", "questions": "See weekness.", "limitations": "None. Good Paper~", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper introduces a novel approach to eliciting chain-of-thought (CoT) reasoning from pre-trained large language models (LLMs) without requiring explicit prompting. This method diverges from conventional prompting techniques, which involve either few-shot or zero-shot prompting, by modifying the decoding process to explore alternative token paths. This strategy is both innovative and creative as it challenges the standard practice of prompt engineering and demonstrates that CoT reasoning can be naturally elicited through decoding adjustments.\n2. The paper is supported by extensive empirical studies that validate the efficacy of the CoT-decoding method. The experiments are well-designed, covering a broad range of reasoning tasks, including mathematical and commonsense reasoning benchmarks.\n3. The paper is exceptionally clear and well-organized. The authors provide a detailed description of the CoT-decoding process, accompanied by illustrative figures and examples that help clarify how the method diverges from traditional decoding strategies.", "weaknesses": "1. The method involves generating multiple decoding paths and evaluating them to identify the most confident reasoning trajectory, which could be computationally expensive, especially when applied at scale or in real-time applications.\n2. The approach heavily relies on the selection of top-k alternative tokens, which may not always yield the most relevant or coherent paths for reasoning, especially in more complex or nuanced tasks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful review!\n\n> The method involves generating multiple decoding paths and evaluating them to identify the most confident reasoning trajectory, which could be computationally expensive, especially when applied at scale or in real-time applications.\n\nThanks for the feedback. Yes as we discussed in the limitation section, our method does incur higher computational cost when we try to identify those CoT-paths. For real-time applications, we can incorporate the “good paths” found by our CoT-decoding algorithm into model training, such that during inference the model can directly output those good paths as the top-paths. \nFor the study in this paper, we spent higher compute to get the top-k paths mainly to investigate 1) whether CoT-paths exist in the top-k paths, and 2) how large k needs to be for us to find a CoT-path. Figure 4 shows that for many tasks, simply increasing k>1 can already help uncover many of the previously-hidden CoT paths.\n\n> The approach heavily relies on the selection of top-k alternative tokens, which may not always yield the most relevant or coherent paths for reasoning, especially in more complex or nuanced tasks.\n\nThanks for this question. Yes, we rely on the model's own probability of ranking the top-k tokens during the first decoding step, and we do observe that for highly difficult tasks, if the model is not well-trained, it’s possible that none of the top-k tokens yields relevant paths. This in turn can help us identify a model's areas of weakness though, so we know that we need additional data coverage in model training, or we need to explicitly guide the model via expert knowledge during inference to solve those tasks. We will add more discussion on this point to make it more clear.", "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": "EruhHxpYkq", "reviewer": "Reviewer_C32n", "summary": "The paper explores the inherent reasoning capabilities of large language models (LLMs) without the need for explicit prompting. By altering the decoding process to consider top-k alternative tokens, the authors reveal that Chain-of-Thought (CoT) reasoning paths can emerge naturally. This approach bypasses the need for task-specific prompt engineering and demonstrates that LLMs possess intrinsic reasoning abilities. Extensive empirical evaluations across various reasoning benchmarks show significant performance improvements using CoT-decoding compared to conventional greedy decoding.", "questions": "- Can the authors provide more detailed comparisons with other state-of-the-art prompting and decoding methods?\n- How does the CoT-decoding method perform on more complex and diverse reasoning tasks not covered in the current experiments?\n- Are there any potential limitations or biases introduced by relying on top-k alternative tokens for decoding?", "limitations": "The authors have addressed some limitations of their work, such as the additional computational costs incurred by exploring alternative decoding paths. However, the paper could further discuss the potential biases introduced by this approach and its applicability to more complex, open-ended tasks.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper introduces a novel approach to reveal LLMs' reasoning capabilities without explicit prompts by altering the decoding process.\n- The paper is clearly written, with detailed explanations and illustrations of the CoT-decoding process.\n- The findings challenge the prevailing notion that LLMs require specific prompting for reasoning, highlighting the models' intrinsic abilities.", "weaknesses": "- The approach, while novel in its specific application, builds on existing concepts of decoding and model confidence. The novelty is somewhat incremental.\n- The scope of experiments could be broadened to include more diverse and complex reasoning tasks. Additional benchmarks and comparisons with state-of-the-art prompting methods would strengthen the paper.\n- The paper could benefit from a more detailed comparative analysis with other decoding and prompting strategies to contextualize its contributions better.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the feedback!\n\n> Can the authors provide more detailed comparisons with other state-of-the-art prompting and decoding methods? The paper could benefit from a more detailed comparative analysis with other decoding and prompting strategies to contextualize its contributions better.\n\n- Comparison to other decoding methods: Please see Table 4 for the detailed comparison on all popular decoding methods used by SoTA LLMs, including greedy, top-k, temperature sampling, nucleus sampling, beam search, and SoTA decoding methods like self-consistency (no prompt), and we show that CoT-decoding is the **only decoding algorithm** that significantly enhances reasoning in language models.\n- Comparison to other prompting methods: please see Table 7 for the results with CoT and self-consistency (with CoT prompt), where both are standard approaches used in major LLM reports to achieve SoTA. \nNote that CoT-decoding is a decoding algorithm which is **orthogonal** to existing prompting techniques, and (1) CoT-decoding can be easily combined with existing prompting techniques to yield further gains (see Table 7 for the results); (2) our paper aims to show that LLMs inherently possess reasoning abilities *without prompting*, hence adding more sophisticated prompting techniques is not the primary focus of this paper. \n- To contextualize our contributions better: existing literature proposing more complex prompting methods often requires adding task-specific human-prior and performing manually-intensive prompt-engineering. As a result, those methods may achieve better task-specific improvements but could be hard to scale or transfer poorly across tasks or models. In contrast, our method requires *no prompt-engineering*, *no human intervention*, is completely *task and model-agnostic* and improves reasoning across the board.\n\n> How does the CoT-decoding method perform on more complex and diverse reasoning tasks not covered in the current experiments?\n\nOur current experiments covering math, commonsense, and symbolic reasoning (with various difficulty levels) showed a *consistent trend*: CoT-decoding can effectively uncover a model's intrinsic reasoning capabilities previously obscured by greedy decoding, although the model's own reasoning ability varies depending on the task difficulty level, which can be attributed to the task prominence in its pre-training distribution. \nFor example, in Figure 4, we show that when task difficulty increases or becomes more synthetic, it becomes harder to find the correct CoT paths (like tasks that require > 3 steps of accurate state tracking). Hence for a new task, the existence of CoT paths will depend on how prominent similar data exists in pre-training, and if relevant knowledge can be retrieved and the solution can be found within a few steps of knowledge manipulation.\n\nBelow we also add results of the Llama-3-8B pre-trained model on the MATH benchmark, which is a substantially more diverse and complex reasoning dataset. We can see that CoT-decoding can still yield effective improvements over greedy decoding.\n\n|  | MATH accuracy |\n| -------- | ------- |\n| greedy decoding | 14.0% |\n| CoT-decoding (max) | 19.8% |\n| CoT-decoding (agg) | 22.6% |\n\n\n> Are there any potential limitations or biases introduced by relying on top-k alternative tokens for decoding?\n\nThanks for the question. We rely on the model’s own top-k token ranking because we want to better understand the model's intrinsic reasoning capabilities. As our study shows in Section 3.2 and Figure 4, our analysis unveils the model's intrinsic vulnerabilities in reasoning, e.g., on Big-bench tasks with controlled-difficulty levels, the model's ranking accuracy of top-k tokens becomes lower as the task complexity increases. \nHence for highly difficult tasks, if the model is not well-trained, it’s possible that none of the top-k tokens yield relevant paths. This in turn can help us identify a model's areas of weakness though, so we know that we need additional data coverage in model training, or we need to explicitly guide the model via expert knowledge during inference to solve those tasks.\n\n> The approach, while novel in its specific application, builds on existing concepts of decoding and model confidence. The novelty is somewhat incremental.\n\nNote that the detail of CoT-decoding differs substantially from existing top-k decoding or model confidence estimation, hence CoT-decoding is novel in its design and effectiveness in significantly improving LLM reasoning:\n- Existing top-k decoding is a sampling algorithm, where each token is *sampled* to enhance the diversity in the *overall sequence*. While in CoT-decoding, other than the first token, all remaining tokens are greedily generated. The reason is that we want to encourage diversity in the 1st token such that the model can escape from the local optima, while for the rest of the tokens we want the model to follow the optimal reasoning path hence they’re still greedily generated. This is also different from beam search because beam search uses the model’s sequence probability to rank the responses. In contrast, in CoT-decoding we observe that the model's sequence probability is not reliable for reasoning tasks (Table 2), while the model's final answer confidence score proves to be significantly more accurate in identifying the correct CoT paths.\n- Model confidence estimation: note that our confidence estimation is based on our novel observation that responses with a CoT first typically have a more confidently-decoded final answer. This is also very different from existing works that try to estimate the model’s confidence for the whole sequence to identify scenarios where the model is uncertain.", "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": "fBuUraN3fP", "reviewer": "Reviewer_Es5x", "summary": "The paper investigates the inherent capabilities of LLMs to generate CoT reasoning paths. This study introduces CoT-decoding, a method that explores alternative top-k tokens in the decoding space to uncover reasoning paths without any specialized prompting. The findings indicate that the presence of a CoT reasoning path correlates with increased model confidence in its final answer. The paper highlights that CoT-decoding can enhance the reasoning performance of language models by extracting more reliable decoding paths.", "questions": "NA", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The paper introduces CoT-decoding to elicit reasoning paths and provides an effective alternative to prompt engineering.\n2. The results demonstrate significant improvements over greedy decoding, showcasing the practical benefits of the proposed method.\n3. The study finds a clear correlation between the presence of CoT paths and increased model confidence, providing a useful metric for identifying reliable decoding paths.", "weaknesses": "1. The primary contribution of the paper appears to be a method for selecting a decoding path from the top-k generated paths. While this approach is useful, it lacks novelty and significant impact.\n2. The motivation behind the study is unclear to me for several reasons. Firstly, providing questions alone constitutes a form of prompting instead of no prompting. Secondly, the use of a prompt that inherently challenges the elicitation of CoT reasoning paths via greedy decoding, only to then introduce a specialized decoding method to address this, strikes me as contrived. Lastly, I question the claim that CoT-decoding effectively enhances the reasoning capabilities of language models, as it merely selects from pre-generated paths rather than uncovering new, substantive reasoning processes.\n3. The proposed method may face challenges in tasks where identifying correct answer spans is difficult, limiting its practical applicability.\n4. The comparison between CoT-decoding and greedy decoding is unfair. CoT-decoding inherently requires multiple reasoning paths to be generated first, which is not a requirement for greedy decoding. The exploration of multiple decoding paths significantly increases the computational cost, which could be a drawback for practical applications.\n5. The evidence provided in the paper is restricted to a few reasoning benchmarks and toy tasks. To convincingly demonstrate its utility, the method should be tested across a broader array of datasets, such as the MATH benchmark, and in more complex real-world scenarios.\n6. The range of models evaluated in the study is too narrow. Including mainstream models like GPT-3.5, GPT-4, and diverse open-source models like llama3 in various sizes would provide a more robust evaluation of the method's effectiveness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive feedback!\n\n> The primary contribution of the paper appears to be a method for selecting a decoding path from the top-k generated paths. While this approach is useful, it lacks novelty and significant impact.\n\nTo clarify our contribution, our first finding is that LLMs inherently possess reasoning capabilities even without any additional prompting, this is a *novel* finding in contrast to many previous papers proposing better prompting to enable LLM reasoning. Our other contribution is to propose CoT-decoding that identifies the correct CoT-path, this is also the *first decoding-only method* that effectively enables language models to reason, please see Table 4 for a detailed comparison to all existing decoding algorithms.\n\n\n> The motivation behind the study is unclear to me for several reasons. Firstly, providing questions alone constitutes a form of prompting instead of no prompting. Secondly, the use of a prompt that inherently challenges the elicitation of CoT reasoning paths via greedy decoding, only to then introduce a specialized decoding method to address this, strikes me as contrived. Lastly, I question the claim that CoT-decoding effectively enhances the reasoning capabilities of language models, as it merely selects from pre-generated paths rather than uncovering new, substantive reasoning processes.\n\nThanks for the suggestion, we will add more clarification to the motivation as below.\n\nFirst, to clarify the “prompting” part: the question has to be an input to the model, otherwise the model will have no input :) In existing literature, the “prompting” part usually refers to any additional prompts added to the question, e.g., zero-shot CoT uses “let’s think step by step” and few-shot CoT uses few-shot demonstrations before the question. We will make this point more clear in the paper.\n\nSecond, your comment is similar to what existing papers try to claim: LLMs *can’t reason* with questions only. Our study is the first to show that it is *not the case*: the observation that models can’t reason without additional prompting is due to the prevalent usage of greedy decoding, while the top-k alternative decoding paths can unveil the existence of CoTs.\n\nTo your last point, yes as we emphasized in multiple places in our paper, our method “enables a better understanding of LLMs’ intrinsic reasoning capabilities” (line 60). Our primary finding is that LLMs can already reason by themselves after pre-training, and “the reasoning process can be readily elicited by simple decoding changes” (line 56). \nWe say that the model’s reasoning performance is enhanced by CoT-decoding *when compared to greedy decoding*, and we do not claim that we enhance the inherent reasoning capabilities of LLMs, we just made those capabilities more prominent. We will make this point more clear in our paper.\n\n> The proposed method may face challenges in tasks where identifying correct answer spans is difficult, limiting its practical applicability.\n\nYes, as we discussed in our limitation section, we hope this can be better addressed in future research by better learning the model’s internal representation across a broader, more open-ended answer space.\n\n> The comparison between CoT-decoding and greedy decoding is unfair. CoT-decoding inherently requires multiple reasoning paths to be generated first, which is not a requirement for greedy decoding. The exploration of multiple decoding paths significantly increases the computational cost, which could be a drawback for practical applications.\n\nThanks for your question. We explore more decoding paths because we want to investigate whether the model inherently possesses the reasoning capability or not, which is currently masked due to the prevalent usage of greedy decoding. And yes as discussed in our limitation section, our method will incur more computational cost, and we can use the CoT paths found by our method to further train the model, such that those reasoning paths can be readily output during inference.\n\n> The evidence provided in the paper is restricted to a few reasoning benchmarks and toy tasks. To convincingly demonstrate its utility, the method should be tested across a broader array of datasets, such as the MATH benchmark, and in more complex real-world scenarios.\nThe range of models evaluated in the study is too narrow. Including mainstream models like GPT-3.5, GPT-4, and diverse open-source models like llama3 in various sizes would provide a more robust evaluation of the method's effectiveness.\n\nThanks for the suggestion. We include results on Llama-3 below, showing the robustness of our proposed approach. We also add the MATH benchmark (the MATH-500 held-out set from https://arxiv.org/pdf/2305.20050) to cover a broader range of datasets. \nFor GPT models, note that the focus of our paper is on *pre-trained* models to investigate their intrinsic reasoning capabilities, while current exposed GPT APIs are all instruction fine-tuned models, hence it is hard to distinguish whether the model can reason already after pre-training, or acquired such ability during instruction fine-tuning via a substantial amount of CoT reasoning data. Also note that in Figure 3, we already plotted the performance of CoT-decoding on models with *various sizes* (XS, Small, Medium, Large) and showed performance improvement across the board. \n\nResults on Llama-3-8B pre-trained model:\n\n| | GSM8K | MultiArith | MATH |\n|---| --- | --- | --- |\n| greedy decoding | 21.4% | 41.8% | 14.0% |\n| CoT-decoding (max) | 32.7% | 50.7% | 19.8% |\n| CoT-decoding (agg) | 47.9% | 77.8% | 22.6% |", "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:

Meta-review: This paper investigates whether LLMs can generate CoT paths without any prompting (i.e., only input a question to the model, without additional info).This is in contrast to prior work that focuses on developing different prompts (e.g., few-shot prompts, “let’s think step by step”) to elicit reasoning steps from LLMs. The findings suggest that CoT reasoning paths can be elicited from pre-trained LLMs by simply considering the alternative paths greedily decoded from the top-k tokens at decoding step 0. The authors have added a few more experiments during the rebuttal, which make the results more convincing. Most reviewers tend to agree that the paper introduces a novel approach, very well-written and easy to follow. I would recommend accepting this paper and the authors follow the suggestions and discussions during rebuttal to refine it.
Decision: Accept (poster)