Source-linked AI summary
Complexity-Based Prompting for Multi-Step Reasoning
Yao Fu, Hao Peng, Ashish Sabharwal, Peter Clark, Tushar Khot
TL;DR
The paper addresses which reasoning examples best prompt large language models for multi-step reasoning. It selects examples and generated chains by reasoning complexity, reporting improved accuracy and state-of-the-art results across math and BigBenchHard benchmarks. The approach is presented as intuitive, annotation-efficient, and robust across prompting settings.
Problem
The paper studies which annotated reasoning examples make effective chain-of-thought prompts and how to improve annotation efficiency in multi-step reasoning.
Method
Complexity-based prompting selects chains with more reasoning steps for prompts, while complexity-based consistency selects outputs by voting over the most complex generated chains.
Results
The methods achieve new state-of-the-art performance on GSM8K, MultiArith, MathQA, Date Understanding, and Penguins, with consistent gains across several prompt distributions.
Takeaways & Limitations
Complexity-based selection is intuitive, annotation-efficient, and robustly effective across different in-context learning settings.
Abstract
from arXiv · showhide
We study the task of prompting large-scale language models to perform multi-step reasoning. Existing work shows that when prompted with a chain of thoughts (CoT), sequences of short sentences describing intermediate reasoning steps towards a final answer, large language models can generate new reasoning chains and predict answers for new inputs. A central question is which reasoning examples make the most effective prompts. In this work, we propose complexity-based prompting, a simple and effective example selection scheme for multi-step reasoning. We show that prompts with higher reasoning complexity, i.e., chains with more reasoning steps, achieve substantially better performance on multi-step reasoning tasks over strong baselines. We further extend our complexity-based criteria from prompting (selecting inputs) to decoding (selecting outputs), where we sample multiple reasoning chains from the model, then choose the majority of generated answers from complex reasoning chains (over simple chains). When used to prompt GPT-3 and Codex, our approach substantially improves multi-step reasoning accuracy and achieves new state-of-the-art (SOTA) performance on three math benchmarks (GSM8K, MultiArith, and MathQA) and two BigBenchHard tasks (Date Understanding and Penguins), with an average +5.3 and up to +18 accuracy improvements. Compared with existing example selection schemes like manual tuning or retrieval-based selection, selection based on reasoning complexity is intuitive, easy to implement, and annotation-efficient. Further results demonstrate the robustness of performance gains from complex prompts under format perturbation and distribution shift.
1 INTRODUCTION
The paper asks which annotated reasoning examples make effective chain-of-thought prompts and proposes selecting examples by reasoning complexity. It extends this criterion to generated chains and reports broad benchmark gains and robustness.
- Motivation: Example selection determines which annotated reasoning chains serve as prompts, making it relevant to annotation efficiency.The paper distinguishes choosing among available annotations from identifying only the cases worth annotating.
- Method: Complexity-based prompting selects examples with more reasoning steps rather than relying on manual, heuristic, optimization, or retrieval-based selection.The introduction contrasts a 9-step complex chain with a 2-step simple chain.
- Method: Complexity-based consistency samples multiple reasoning chains and votes over the answers from the K most complex chains.This extends self-consistency from voting over all generated chains to selecting the most complex outputs.
- Results: The methods achieve new state-of-the-art performance on three math benchmarks and two BigBenchHard tasks, with substantial gains over the cited baseline.The benchmarks are GSM8K, MultiArith, MathQA, Date Understanding, and Penguins.
- Robustness: Performance gains remain consistent across in-distribution, transferred, and noisily labeled prompt distributions and across alternative complexity proxies.The introduction also reports that reasoning-step count is the most prominent factor over prompt length and input-case count.
2 RELATED WORK
Related work situates this study within emergent multi-step reasoning, chain-of-thought prompting, prompt selection, and links to semantic parsing and Bayesian inference.
- Emergent Abilities and Multi-Step Reasoning: Large language models are especially relevant for multi-step reasoning because scaling improves this capability and few-shot prompting can outperform full-data fine-tuning.The paper contrasts this pattern with more limited gains on tasks such as sentiment classification.
- Chain-of-Thoughts Reasoning: Chain-of-thought prompting elicits reasoning through intermediate steps, unlike standard prompting, and self-consistency improves it by sampling and voting.The paper also notes related work on pretraining with LaTeX-formatted data.
- Example Selection for Prompting: Prompt design is unstable across prompts, tasks, datasets, and models, while large-model prompt engineering remains substantially trial and error.The related work contrasts this practice with automatic prompt searching aimed more at smaller models.
- Relation to Classical Semantic Parsing: Chain-of-thought prompting parallels semantic parsing because both generate an intermediate representation before execution or aggregation toward an answer.Sampling and voting is compared with marginalizing over semantic parses.
3 COMPLEXITY-BASED PROMPTING
The paper selects complex reasoning examples for prompts and complex generated chains for output voting, while testing alternative complexity indicators and confounders.
- 3 COMPLEXITY-BASED PROMPTING: The evaluation uses math word problems as a multi-step reasoning testbed with GPT-3 and Codex under a chain-of-thought workflow.Few-shot CoT cases precede a test question, after which the model generates an output reasoning chain.
- 3.1 SELECTING COMPLEX SAMPLES AS PROMPTS: Complexity-based prompting chooses in-context examples containing more reasoning steps than simpler alternatives.A reasoning step is operationalized as a line separated by a line break.
- 3.1 SELECTING COMPLEX SAMPLES AS PROMPTS: The study tests question length and formula length as alternative complexity indicators when annotated reasoning chains are unavailable.This supports identifying a few instances for annotation rather than annotating an entire dataset.
- 3.1 SELECTING COMPLEX SAMPLES AS PROMPTS: The analysis controls confounding from total prompt steps and prompt length by comparing prompts with matched total steps and prompts with maximal length.One example contrasts 24 three-step cases with 8 nine-step cases, both totaling 72 steps.
- 3.2 COMPLEXITY-BASED CONSISTENCY: Complexity-based consistency extends selection from prompt inputs to model outputs to discourage shortcut reasoning and spurious correlations.The method follows self-consistency but promotes complex generated chains during output selection.
- 3.2 COMPLEXITY-BASED CONSISTENCY: The output procedure samples multiple reasoning chains and selects answers by voting over the most complex chains.This output-side criterion mirrors the input-side preference for complex examples.
4 EXPERIMENTS
Experiments evaluate complexity-based prompting and output selection across reasoning tasks, prompt distributions, formats, baselines, and model scales. Complex prompts generally improve performance, while gains depend on model scale and remain robust across several experimental variations.
- Experimental setup: The evaluation covers math, temporal, commonsense, and referential reasoning tasks using prompting and fine-tuning baselines.GSM8K, MultiArith, MathQA, StrategyQA, Date Understanding, and Penguins form the testbed.
- Main results: Complexity-based prompting and complex-chain voting substantially outperform baselines, producing new state-of-the-art results across several benchmarks.The method improves over original CoT, and voting over complex chains outperforms voting over all sampled chains.
- Robustness: More complex prompts generally improve performance across clean in-distribution, noisy, and transferred prompt settings, with one exception on MultiArith.The trend is shown across the three prompt-distribution conditions.
- Comparison and efficiency: Complexity-based selection outperforms competing selection methods on GSM8K and MultiArith, while retrieval performs better on MathQA but requires substantially more annotation.Complexity can also be measured with question length or formula length, preserving the advantage of complex prompts.
- Generalization: Complex prompts perform on par with simple prompts on hard cases while showing clearer gains on cases requiring fewer reasoning steps.The generalization pattern differs across GSM8K and MathQA, especially for simple cases.
- Analysis: Complexity-based prompting does not induce meaningful gains on smaller models, suggesting that the method depends on sufficiently large model scale.Complex prompts also induce more complex generated reasoning chains, and performance remains stable under step-format perturbations.
5 CONCLUSION
The paper proposes complexity-based instance selection for multi-step reasoning and reports substantial improvements, annotation efficiency, intuitive use, and robustness across in-context settings.
- Complexity-based instance selection improves language-model performance on multi-step reasoning tasks.
- The method is annotation-efficient and intuitive compared with selecting reasoning examples without complexity criteria.
- Performance gains remain robust across different in-context learning settings.
A APPENDIX
The appendix section may contain additional material.
- Additional sections may be included in the appendix.
- The appendix can provide material beyond the main paper sections.
- This section is reserved for optional additional content.