Sampling and voting beat greedy chain-of-thought decoding

From one reasoning path to several, then to a search

Chain-of-thought prompting, described in the January 2022 paper that introduced it, has a model generate a step-by-step reasoning path before its answer, using a small number of worked examples in the prompt. That original method still takes the single reasoning path produced by greedy decoding. The self-consistency paper, submitted in March 2022, instead samples a diverse set of reasoning paths for the same question and takes the most common final answer across them, on the reasoning that a correct answer tends to be reachable by more distinct valid paths than an incorrect one. The later Tree of Thoughts paper, submitted in May 2023, goes further, letting the model generate and evaluate intermediate reasoning steps as nodes in a search tree, backtracking away from steps it judges unpromising rather than only sampling complete paths independently.

What each paper measured

The self-consistency paper reports accuracy gains over standard chain-of-thought decoding of 17.9 percentage points on GSM8K, 11.0 on SVAMP and 12.2 on AQuA, with smaller but positive gains on StrategyQA and ARC-Challenge, all measured by sampling multiple paths and taking a majority vote instead of one greedy path. The Tree of Thoughts paper reports a much larger gap on its own chosen task: GPT-4 using standard chain-of-thought prompting solved the Game of 24 arithmetic puzzle in 4 percent of its tests, while the tree-search method solved 74 percent, alongside separate tests on creative writing and mini crossword tasks that the paper says require planning or search that single-path prompting does not provide.

What the extra sampling costs

Both methods trade tokens for accuracy: self-consistency runs the model many times per question to gather a sample of paths, and Tree of Thoughts adds further model calls to generate and evaluate candidate steps during the search, so the cost in both cases is additional inference calls rather than additional training. Neither paper reports a cost-adjusted comparison against simply asking a stronger model once; the Game of 24 result in particular is a single, unusually search-shaped puzzle, and the paper does not claim the 70-point gap generalises to tasks with a less clearly defined search structure or a single accepted answer format.

• Does the task have a checkable final answer that a voting or search procedure can actually score?
• Is the added accuracy worth the multiplied token cost compared to a single stronger call?
• Does the task resemble Game of 24's narrow search structure, or is it closer to the open-ended tasks where the gap was smaller?

Both papers report genuine accuracy gains under their own token budgets and tasks; neither establishes that the same ratio of accuracy to extra compute holds outside the specific benchmarks it measured.