Complexity-Based Prompting: Why Harder Examples Make Better Chain-of-Thought Prompts

When building few-shot prompts with chain-of-thought reasoning, the conventional advice is to pick representative examples or use retrieval to find ones similar to the test input. Fu et al. 2022 asked a simpler question: what if you just picked examples with the most reasoning steps? The paper 'Complexity-Based Prompting for Multi-Step Reasoning' (arXiv:2210.00720), by Yao Fu, Hao Peng, Ashish Sabharwal, Peter Clark, and Tushar Khot, submitted October 3, 2022 and revised January 30, 2023, showed that this simple criterion outperforms both manual prompt tuning and retrieval-based selection on a range of multi-step reasoning benchmarks. Selecting exemplars by step count rather than topical similarity to the test input improved average accuracy by +5.3 points, with gains of up to +18 points on individual benchmarks, when applied to GPT-3 and Codex.

The selection problem in chain-of-thought prompting

Since Wei et al. showed that chain-of-thought prompting improves reasoning in large language models, practitioners have faced a practical design question: which examples should go into the few-shot prompt? Standard few-shot prompting uses a small, fixed set of handpicked demonstrations. Retrieval-based methods select examples semantically similar to each test input at inference time. Both approaches assume that the content or topic of the example is what matters most. Complexity-based prompting proposes a different assumption: the structural complexity of the reasoning chain matters more than its topical relevance. Specifically, examples with longer chains (more distinct intermediate steps) teach the model to generate longer, more careful reasoning, which in turn leads to more accurate final answers. This reframes exemplar selection from a semantic matching problem to a structural measurement problem.

Measuring complexity and selecting exemplars

The paper operationalizes 'complexity' as the number of reasoning steps in a chain-of-thought example. This is easy to compute: count the distinct inferential steps in the annotated reasoning chain and rank candidate examples by that count. At prompt construction time, you select the top-k examples by step count rather than by relevance to the current input. This selection happens once per dataset rather than once per test instance, so it adds no per-query latency compared to fixed few-shot prompts. The authors point out that the approach is annotation-efficient: you do not need labeled similarity judgments between examples and test inputs, and you do not need to run a retrieval model at inference time. You sort by step count and take the top examples. An important distinction: verbosity is not complexity. An example that restates the problem at length before jumping to an answer is not high-complexity in the relevant sense. High complexity means many distinct inferential moves, each advancing the solution to the final answer.

Extending complexity to the decoding stage

The paper extends the complexity criterion from input selection (choosing which examples to include in the prompt) to output selection (choosing which generated reasoning chain to trust). In self-consistency prompting, the model samples multiple reasoning chains for the same input and takes a majority vote over the final answers. Fu et al. apply a complexity filter before the vote: they retain only generated chains that exceed a step-count threshold, then compute the majority vote over that filtered subset. Short, potentially shallow chains are excluded from the vote even if they agree on an answer. The intuition is that longer generated chains reflect more deliberate reasoning and are more likely to reach the correct answer. Combining complexity-based input selection with complexity-based decoding produced the strongest results in the paper, outperforming each strategy applied in isolation.

Results on math and reasoning benchmarks

Applied to GPT-3 and Codex, complexity-based prompting set new state-of-the-art results on five benchmarks at the time of publication. On three math word-problem benchmarks, GSM8K, MultiArith, and MathQA, it achieved record accuracy. On two BigBenchHard tasks, Date Understanding and Penguins in a Table, it also reached new highs. The average improvement across these five tasks was +5.3 accuracy points over a strong baseline, with a peak gain of up to +18 points on individual tasks. The paper also ran robustness checks: the performance gains held up under format perturbation (changing the surface phrasing of the exemplars) and under distribution shift (using complexity-selected exemplars from one dataset to prompt on a different but related dataset). This stability matters in practice because it suggests the gains come from genuine improvements in how the model reasons, not from superficial pattern matching to prompt format.

• Paper: 'Complexity-Based Prompting for Multi-Step Reasoning,' Yao Fu, Hao Peng, Ashish Sabharwal, Peter Clark, Tushar Khot. arXiv:2210.00720, submitted October 3, 2022; v2 January 30, 2023.
• Core idea: rank chain-of-thought exemplars by number of reasoning steps; select the highest-complexity examples for the few-shot prompt.
• Complexity-based decoding: filter sampled reasoning chains by step count before majority voting, excluding low-complexity outputs from self-consistency.
• Results on GPT-3 and Codex: +5.3 average accuracy improvement over strong baselines, up to +18 improvement on individual benchmarks.
• SOTA at publication on GSM8K, MultiArith, MathQA (math), and Date Understanding and Penguins (BigBenchHard).
• Gains are robust to format perturbation and cross-dataset distribution shift.
• No added inference latency for input selection: exemplar ranking is done once per dataset, not per query.

How to apply complexity-based prompting in practice

Complexity-based prompting converts a fuzzy design choice into a measurable criterion. When building a few-shot CoT prompt, annotate your candidate examples with step counts before choosing which ones to include. Prefer examples with explicit, numbered inferential moves over examples that compress reasoning into a single paragraph. When using self-consistency decoding, apply a step-count filter to the sampled outputs before voting: set a threshold based on the median or top quartile of chain lengths in your sample and exclude anything below it. The technique is most valuable on tasks that genuinely require multi-step reasoning: arithmetic word problems, symbolic manipulation, multi-hop question answering, and structured reasoning over tables or calendars. On simpler tasks where one or two steps suffice, selecting the longest exemplar adds little beyond what any reasonable example would provide. PromptingIndex covers related reasoning strategies including self-consistency, active prompting, contrastive chain-of-thought, and plan-and-solve prompting.