Research map / Large language models / Reasoning and chain of thought
Generating Chain-of-Thoughts with a Pairwise-Comparison Approach to Searching for the Most Promising Intermediate Thought
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes C-ToT, a tree-of-thoughts variant that replaces LLM point-wise scoring with randomized pairwise comparisons (plus ensemble and dueling-bandit variants) to select promising intermediate thoughts under noisy LLM feedback.
Problem
LLM point-wise scores for intermediate thoughts in score-based tree-of-thoughts are noisy and unreliable, misleading the selection of promising reasoning steps during chain-of-thought generation.
Approach
Randomly pair candidate intermediate thoughts and ask the LLM to pick the better one in each pair, iteratively halving the set; include previously unselected thoughts in later comparisons so they can be revisited; two variants add majority-vote ensembling (Standard) or knockout-based dueling-bandit comparisons (Duel.) to handle comparison noise.
Key results
- On the Sudoku puzzle task, C-ToT (Stand.) and C-ToT (Duel.) achieve the highest average accuracy across 3x3, 4x4, and 5x5 puzzles, with C-ToT (Stand.) matching C-ToT (Duel.).
- Comp-SToT (pairwise comparison replacing scoring in SToT) achieves higher average accuracy than SToT on AQuA and Game of 24 at comparable token cost.
- On AQuA, Comp-SToT predicts more problems correctly than S-ToT when S-ToT is wrong, supporting the pairwise comparison mechanism.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace point-wise LLM scoring with pairwise comparison (Comp-SToT) | SToT · AQuA, Game of 24 | average accuracy | Helped |
| replace point-wise LLM scoring with pairwise comparison (Comp-SToT) | SToT · Sudoku puzzle | token cost | Helped |
| add self-consistency (majority vote over repeated LLM scoring) to SToT | SToT · AQuA, Game of 24, Sudoku | average accuracy | Mixed |
| keep previously unselected thoughts in comparisons each round (backtracking via comparison) | SToT (Back-SToT) · AQuA | average accuracy | Helped |
| use dueling-bandit comparison noise modeling (C-ToT Duel.) rather than standard mode | C-ToT · Sudoku puzzle | average accuracy | No clear effect |
| increase number of comparisons per pair (ablation) | C-ToT · AQuA | accuracy | Helped |
| generate more thoughts per round with fixed selection (ablation) | C-ToT · AQuA | accuracy | Helped |
| select more thoughts per round with fixed generation (ablation) | C-ToT · AQuA | accuracy | No clear effect |
| comparison-count threshold for removing thoughts from tree (ablation) | C-ToT · AQuA | accuracy | No clear effect |
Surprising findings
- Pairwise comparison by the LLM succeeds on Sudoku cases where the LLM assigns incorrect point-wise scores to the same thoughts.
Limitations
- Keeping all previous thoughts for comparison increases token cost and storage.
- Token cost comparisons across methods are task-specific and not directly comparable.
- Evaluated only with GPT-3.5-turbo-1106 and on relatively small test sets (e.g., 100 Game of 24 problems).
Experimental setup
Datasets: AQuA Game of 24 (4nums.com questions 401-500) Sudoku Dataset (3x3, 4x4, 5x5) GSM8K Coin Flip BBH
Benchmarks: AQuA Game of 24 Sudoku GSM8K Coin Flip BBH
Metrics: accuracy token cost
Baselines: Direct CoT SC-CoT ToT (S-ToT) SC-SToT PoT Self-Refine GoT
Builds on: tree-of-thoughts self-consistency chain-of-thought knockout tournament dueling bandits
Closest papers by meaning
- Algorithm of Thoughts: Enhancing Exploration of Ideas in Large Language Models (ICML 2024 · similarity 0.90)
- Boosting of Thoughts: Trial-and-Error Problem Solving with Large Language Models (ICLR 2024 · similarity 0.89)
- Mind the Gap: Bridging Thought Leap for Improved Chain-of-Thought Tuning (NeurIPS 2025 · similarity 0.89)
- Chain of Preference Optimization: Improving Chain-of-Thought Reasoning in LLMs (NeurIPS 2024 · similarity 0.89)
- C3oT: Generating Shorter Chain-of-Thought Without Compromising Effectiveness (AAAI 2025 · similarity 0.89)
- OCEAN: Offline Chain-of-thought Evaluation and Alignment in Large Language Models (ICLR 2025 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.