Chain-of-Thought Reasoning Without Prompting

In plain words

Language models are usually asked a question and they answer it in one go, which often goes wrong on reasoning tasks. The usual fix is to write a careful prompt that asks the model to show its steps. This paper asks a different question: does the model already know how to reason, and only hide it?

The answer it gives is that the reasoning is often there, just not on the path a model takes by default. The default takes the single most likely word at every step. If you instead look at a few alternative first words and let the model continue from each, some of those continuations write out the steps before answering. The paper also finds that when a step-by-step answer shows up, the model tends to be more sure of its final answer. That gives a way to pick the good continuations without any prompt, and without training the model.

TL;DR

• CoT-decoding replaces the greedy first token with the top-k alternatives, continues each branch greedily, and ranks the branches by how confident the model is in the answer §2.2 §3.
• No prompt is used beyond a bare "Q: [question] / A:" format, and no model is tuned §2.1 §2.2.
• Author-reported: GSM8K accuracy rises from 9.9% to 25.1% on Mistral-7B and from 34.8% to 63.2% on PaLM-2 L, both over greedy decoding tab. 4 tab. 7.
• Read "Paper vs code" and "Pitfalls" before reimplementing. The official code is not public, and the answer-span rules, the answer filters and the aggregation step are underspecified in the paper.

Problem

Most evaluations of LLM reasoning use greedy decoding on a direct question, and these show low accuracy. The authors argue that this underestimates the model, because a model's reasoning paths can be hidden behind the top-1 choice §1 §2.1. Prompting methods such as few-shot or zero-shot chain-of-thought improve the numbers, but they bring human-chosen priors into the result. Then it is hard to separate what the model can do from what the prompt teaches it §1 §4.

Two assumptions are built in. First, the question must be in a format where a pre-trained model answers rather than continues the question; the authors use "Q: [question] / A:" and say this format is needed for that reason §2.1 footnote. Second, the method depends on the answer being identifiable in the generated text §2.2.

Method

Overview. Take the top-k tokens at the first decoding position. Greedy decoding continues from each one. This gives k decoding paths, one of which is the greedy path (k = 0) §2.1. Each path has a score, and the final answer is chosen by score §2.2. The paper also reports a variant that sums the scores of paths giving the same answer (the "agg" variant) §2.2 tab. 7.

Step 1: branch at the first token. Only the first decoding step branches. Every later step is greedy §2.2 §3. The authors also tested branching at later steps and found that early branching gives more diverse paths; later branching is strongly influenced by earlier tokens §2.2 fig. 2.

Step 2: score each path by answer confidence. For a path k with answer tokens x_t, define the mean top-1 vs top-2 margin over the answer tokens. The top two tokens are taken from the full post-softmax distribution at each step §2.2:

\Delta_{k,\text{answer}} = \frac{1}{|\text{answer}|}\sum_{x_t\in \text{answer}} p(x^1_t \mid x_{<t}) - p(x^2_t \mid x_{<t}) §2.2, unnumbered display equation

The authors chose this min-margin measure over two alternatives. Using only the top-1 probability of the answer tokens was slightly worse, and an entropy estimate was judged inaccurate for LLM-size vocabularies §2.2 footnote.

Step 3: pick the answer. Two rules are given.

• Max path: take the answer of the path with the largest Δ §2.2 tab. 2.
• Aggregated path: for each answer a, sum Δ over the paths whose answer is a, and take the a with the largest sum §2.2 tab. 7.

Step 4: find the answer span. Two ways are given §2.2 §9.

• Math and set-based tasks on public models: take the last number, or the last listed option, as the answer, following the Tülu evaluation protocol §2.2 §9.
• PaLM-2 runs: append the continuation "So the answer is" to the path and align that continuation with a span of the original path; Δ is computed on the span in the original path §2.2 §9.

Step 5: filter ill-formed paths. Empty responses, responses whose length equals the maximum decoding length, and responses ending in a question mark are dropped. For Mistral, outputs that look like training data are also dropped §9. On math tasks a path without a found continuation is ignored; on other reasoning tasks Δ is computed over the continuation instead §9. For yes/no tasks, the paper compares the probability mass on "yes/true" with that on "no/false" instead of using Δ §9.

Pseudocode. The pseudocode below is written by us from the steps above.

# CoT-decoding  [§2.1] [§2.2] [§3] [§9]
# Input:  model, prompt "Q: [question]\nA:", k (default 10)
# Output: the answer with the highest confidence, plus its paths

def cot_decoding(model, prompt, k=10):
    # Take the k most likely tokens at the first decoding step  [§2.2] [§3]
    first_tokens = top_k_tokens(model, prompt, k)

    # Continue each branch greedily; 128 steps is the PaLM-2 budget  [§9]
    paths = []
    for token in first_tokens:
        path = greedy_decode(model, prompt, first=token, max_new=128)
        paths.append(path)

    # Drop empty, truncated and question-ending responses  [§9]
    paths = [path for path in paths if is_well_formed(path)]

    # Find the answer span in each path  [§2.2] [§9]
    for path in paths:
        path.answer = find_answer_span(path)

    # Average the top-1 minus top-2 margin over the answer tokens  [§2.2]
    for path in paths:
        path.score = mean_margin(model, path, path.answer)

    # Return the answer of the path with the largest score (max path)  [§2.2]
    best = max(paths, key=lambda path: path.score)
    return best.answer

The aggregated variant replaces the last step: sum score per distinct answer and return the answer with the largest sum §2.2 tab. 7.

Compute. Each branch is a full greedy decode, so the cost grows with k, which the paper marks as O(k) against O(1) for greedy decoding tab. 7. The authors name the extra compute as a limitation §5.

Hyperparameters

Results

Author-reported. Setups differ by table, so compare numbers only within a table.

Decoding baselines, Mistral-7B pre-trained, GSM8K tab. 4

Path selection, PaLM-2 L, top-100 items tab. 2

Greedy vs CoT-decoding, pre-trained and instruction-tuned Mistral-7B tab. 5

Symbolic and BIG-Bench tasks, PaLM-2 L, greedy vs CoT-decoding tab. 6

Combined with prompting, GSM8K test set tab. 7

Other reported results:

• Across PaLM-2 scales, CoT-decoding adds about 10–30 points on GSM8K §3.1. On year parity it reaches near-perfect accuracy at the largest scales, while greedy decoding stays flat §3.1 fig. 4.
• On the first 100 GSM8K questions, the highest-confidence path among the top 10 contains a CoT in 88% of cases; this was a manual count §2.2.
• The paper reports that CoT-decoding beat the other decoding methods it tried on Mistral-7B pre-trained GSM8K §3.1 tab. 4.

Paper vs code

No official code. The paper has no code link, and the arXiv record does not name one. Searches, all done with WebFetch: a GitHub repository search for "cot-decoding", and searches for "cot" inside the org google-deepmind and the org google-research. None returned an official repository. The hits were third-party reimplementations, which this card does not use.

Pitfalls

• The prompt is still there. The method removes instruction-style prompts, but keeps the "Q: [question] / A:" format, and the authors say the format is needed for the model to answer rather than continue the question §2.1 footnote. Reporting "no prompting" therefore means "no CoT prompt".
• Answer-span rules differ by model. Mistral uses the last number or option. PaLM-2 uses the "So the answer is" alignment §2.2 §9. A reimplementation must pick one rule; the numbers in tab. 4 to tab. 7 depend on it, and the paper gives no sensitivity analysis.
• Filters change the result. The filters in §9 are part of the method: empty, truncated, question-ending and training-data-like outputs are removed. The paper does not report results with and without them.
• The aggregation formula is compact. Δ̃ sums Δ over paths with the same answer §2.2. It is not stated how a path with no answer span is counted under aggregation; the filter rules in §9 imply it is dropped.
• Gains from aggregation are small. On Mistral-7B the aggregated path scores 25.3% against 25.1% for the max path, and on PaLM-2 L 64.1% against 63.2% tab. 7. No variance or number of seeds is reported.
• No uncertainty reported. Confidence intervals, seeds and run-to-run variance are not stated for any table.
• Different token budgets across models. PaLM-2 uses 128 decoding steps §9; Mistral uses 200 or 400 for math and 50 or 100 for year parity §9. Comparing numbers across model families needs these budgets noted.
• Year parity labels for Mistral come from Mistral. The ground-truth birth year is what Mistral-7B itself answered; names it could not answer were dropped, under 2% for the instruction-tuned model §9. This changes the evaluation set.
• Not every task improves. Sports Understanding drops slightly, from 58.8 to 58.0 tab. 6. The paper presents the task-difficulty pattern as the main finding, not as a general gain §3.2.
• Open-ended answers. Δ depends on a clear answer span. The authors say the top-two margin is less precise for open-ended answers §5.
• Cost. Each branch is a full decode. The paper calls the extra compute a limitation §5. Speculative decoding is mentioned in related work as something that could reduce the cost; no experiment tests it §4.
• PaLM-2 access. The paper calls PaLM-2 a public model §3, but it gives no access route, and PaLM-2 runs used TPU v4 §9. Use Mistral-7B or Gemma-7B §9 for reproduction with open weights.
• Other decoders. The paper's comparison covers top-k, nucleus, beam and temperature sampling and self-consistency without a CoT prompt tab. 4 tab. 3. Other decoding methods are only mentioned in related work §4.

Lineage

• Builds on: self-consistency, which samples several chains and votes §2.2 §3.3 — see the card. The paper's aggregation step is a weighted version of this vote.
• Builds on: chain-of-thought prompting §1 (Wei et al., 2022) and zero-shot chain-of-thought (Kojima et al., 2022), both cited as the prompting baselines §1 tab. 7; no cards are in this wiki for these two papers.
• Compared against: top-k, nucleus, beam and temperature sampling, and self-consistency without a prompt tab. 4 tab. 3.
• Related in spirit: instruction tuning with CoT data, which the paper compares against on Mistral §3.1 tab. 5.
• Superseded by: not stated in this wiki.