Complexity-Based Prompting for Multi-Step Reasoning

In plain words

Large language models can work through a multi-step word problem better when they first see a few worked examples. The open question is which examples to show. This paper's answer is to pick the examples whose worked solutions are the longest, meaning the ones that spell out the most intermediate steps.

The same idea is then applied to the answers. The model is asked for many solutions to a new problem, and the final answer is decided by a majority vote that counts only the solutions with the most steps. The authors report better accuracy on math word problems than with the usual hand-picked examples, using GPT-3 and Codex. No model is retrained. The catch is that the examples need written-out solution steps, which the paper notes are costly to produce; question length can stand in for step count when they are missing.

TL;DR

• Few-shot prompts built from training cases with more reasoning steps score higher than prompts built from simpler cases, on the paper's math and some non-math tasks §4.2.
• Self-consistency is changed to majority-vote only over the K most complex of N = 50 sampled chains, with K typically 30–40 §3.2.
• Reported gains are author-measured on text-davinci-002 and code-davinci-002 (both 175B), using prompting only §4.1 tab. 1.
• Only a few-shot annotation budget (8 cases) is needed, whereas retrieval-based selection needs a full annotated training set tab. 4.

Problem

Chain-of-thought (CoT) prompting shows the model a few cases, each a question, a reasoning chain and an answer, before the test question §3.1 fig. 1. Results depend on which cases are chosen. Existing selection schemes use manual trials, heuristic rules, search, or retrieval from a large training set §1. For CoT, the reasoning chains themselves must be annotated, which makes selection costly §1. The paper asks whether the number of reasoning steps in the chosen examples predicts accuracy §3.1.

Method

Prompt selection (complexity-based prompting). The paper defines a complex instance as one with more reasoning steps, and a step as one line of the chain, split on line breaks §3.1. For datasets with annotated chains, the method takes the training cases with the most steps and uses them as the prompt §4.2. Each math prompt has 8 cases §4.1. When chains are not annotated, question length is used as the complexity proxy, and only the selected cases are annotated by hand §3.1 §4.1. Formula length is a second proxy the paper tests for MathQA §4.3 tab. 6.

Complexity-based consistency (output selection). The method follows self-consistency: sample N chains for each test question and take the majority answer §3.2. Instead of voting over all N, it keeps the K chains with the most steps and votes over those only §3.2 fig. 6. K = N recovers ordinary self-consistency §3.2. Sampling settings are not stated in the text.

# Complexity-based prompt selection  [§3.1] [§4.1]
# Input:  train: list of (question, chain, answer) with annotated chains
# Output: prompt: the num_cases most complex cases

def select_complex_prompt(train, num_cases=8):
    # Rank all cases by step count, most steps first  [§3.1]
    ranked = sorted(train, key=count_steps, reverse=True)
    # The prompt is the top cases  [§4.1]
    return ranked[:num_cases]


def count_steps(case):
    # One step per line of the reasoning chain  [§3.1]
    return len(case.chain.split("\n"))

# Complexity-based consistency  [§3.2] [§4.3]
# Input:  prompt (cases), question, N samples, K <= N
# Output: predicted answer

def complexity_consistency(model, prompt, question, N, K):
    # Sample N reasoning chains for the question  [§3.2] [§4.1]
    chains = [model.sample(prompt, question) for _ in range(N)]
    # Rank the chains by step count, most steps first  [§3.2]
    ranked = sorted(chains, key=count_steps, reverse=True)
    # Keep the K most complex chains  [§3.2]
    kept = ranked[:K]
    # Majority vote over the final answers of the kept chains  [§3.2]
    return majority_vote([chain.answer for chain in kept])

Prompt format. Every prompting scheme in the main experiments prefixes the cases with the phrase "Let's think step by step" before each chain §4.1 prompt_complex.txt.

Comparison schemes. Handcrafted CoT is the fixed prompt of Wei et al. §4.2. Random CoT draws 8 training cases at random §4.2. For MultiArith, which has no annotated chains, the complex prompt uses the 8 longest questions and the authors annotate their chains by hand §4.2. For MultiArith, a transfer setting also uses prompts from the GSM8K training data §4.2 fig. 2. Centroid selection takes the questions closest to the others in sentence-embedding space; retrieval takes the nearest training questions per test question §4.2 tab. 4.

Hyperparameters

Results

Author-reported. Setup: test sets with greedy decoding (one chain) or majority vote (50 sampled chains) on GPT-3 text-davinci-002 and Codex code-davinci-002, both 175B. Baseline is the handcrafted CoT prompt of Wei et al. Hardware is not stated §4.1.

Table 1: test accuracy, math datasets tab. 1. Gains over handcrafted CoT in blue in the source are given in parentheses.

The caption reports average gains of +5.3 on GPT-3 and +6.2 on Codex. These match the mean of the six gain values in each model block of Table 1 (for GPT-3, 5.35; for Codex, 6.17) tab. 1. The † rows are not publicly accessible; their numbers are copied from the original papers tab. 1.

Table 2: StrategyQA, Date Understanding, Penguins, greedy decoding tab. 2. "Simple" prompts are not defined further in the text.

Table 3: GSM8K validation breakdown tab. 3. Stepwise changes; the paper attributes most of the gain to complex prompts and complex-chain voting.

Table 4: prompt selection schemes, validation accuracy tab. 4.

Table 5: smaller models, complex prompts, change against handcrafted tab. 5. Column values are accuracy.

Table 6: alternative complexity proxies, validation tab. 6. Left: question length (GSM8K); right: formula length (MathQA). Cited as Table 4 in the text, see Pitfalls.

Table 7: sensitivity to step separator, validation tab. 7.

Table 8: confounder analysis, validation tab. 8. In each pair, the first value is the alternative prompt and the second is the option the paper favours (more complex cases, most steps, or longer per-step length).

Figures (not reproduced; no images on this site). fig. 1 is the schematic of CoT prompting, a 2-step and a 9-step example, and the complexity-based consistency voting. fig. 2 plots validation accuracy against the step count of the prompt for three prompt sources: in-distribution, noisily labelled, and transferred. The text says accuracy generally rises with step count, with one exception on MultiArith §4.2. fig. 3 plots validation accuracy of complex and simple prompts against the gold step count of the test case: complex prompts match simple ones on the hardest cases and gain most on the easiest §4.3. fig. 4 shows how step count, prompt length and case count co-vary across prompts. fig. 5 shows that complex prompts make Codex produce longer chains on GSM8K and MathQA §4.3. fig. 6 plots majority-vote accuracy against K for complex and simple chains, with the best K below N = 50 for complex chains §4.3.

Paper vs code

The repository FranxYao/Complexity-Based-Prompting (commit 378f7a88fb4c6a3fdb294f0dcf8a702420f76724) is owned by the GitHub account FranxYao, which appears to be the first author's account; its README calls it the implementation of this paper README.md. It has no LICENSE file, so code_license is recorded as none, and nothing in this card is quoted from it. The README says the repository is now integrated into FranxYao/chain-of-thought-hub README.md; that newer location was not checked.

• The repository contains only prompt text for GSM8K (complex, original, mid, simple) and MathQA (complex, original, easy). It contains no code for training-set ranking, sampling, step counting or voting, so complexity-based selection and complexity-based consistency cannot be checked against code prompt_complex.txt.
• Each prompt file holds 8 Question: cases, matching the 8-case setting §4.1 prompt_complex.txt prompt_complex.txt.
• The phrase "Let's think step by step" precedes each chain, as the paper states §4.1 prompt_complex.txt prompt_complex.txt.
• The first case ends with "The answer is 4" prompt_complex.txt. The paper does not describe the answer format.
• File names differ from the paper's labels: MathQA's low-complexity prompt is prompt_easy.txt, and GSM8K has a prompt_mid.txt that the paper's tables do not name. The mapping from file to table row is not stated.
• Whether the 8 cases in each complex file are the 8 with the most steps was not checked by counting.
• The text reports prompts from code-davinci-002 and text-davinci-002 with greedy and sampled decoding. The repository has no API call or sampling code, so temperature and stop settings remain unstated.

Pitfalls

• Tie-breaking and counting rules are not stated. Several cases can tie on step count, and the text does not say how ties are broken or how prompt order is set. Blank lines and the answer line are not addressed in the step definition §3.1.
• K is not given as a number. The text says the best K is "typically 30-40" with N = 50 §3.2. The per-dataset K* is only visible as a curve in fig. 6. Pick K on validation data, not on test data.
• Sampling settings are missing. Temperature, top-p, and seed for the 50 sampled chains are not stated, and the vote outcome depends on them.
• Validation and test numbers are mixed. Tables 1 and 2 are test results; Tables 3–8 are validation results. Baselines differ between them: the original CoT GSM8K score is 48.1 on test tab. 1 and 43.5 greedy on validation tab. 3.
• No variance or significance is reported. The text does not give seeds, repeat runs, error bars or significance tests, yet it describes gains as "substantial". Treat differences of a few points as unverified.
• SOTA claims need care. The abstract claims new state of the art on MultiArith. In tab. 1 DiVeRSe reports 99.8, and the best row here is also 99.8 (Codex, complex-chain vote), so this is a tie, not a new state of the art. On Date Understanding, GPT-3 Complex (82.4) is below GPT-3 Handcrafted (82.8) tab. 2; the best listed value comes from Codex Complex (86.8).
• MultiArith is a different experiment. Its "complex" prompt was chosen by question length and then annotated by hand, not by step count §4.2. On Codex greedy, Random CoT (97.3) beats Complex CoT (95.8) on MultiArith tab. 1.
• Retrieval beats complexity on MathQA. Validation accuracy is 69.5 for retrieval and 42.5 for complexity tab. 4. The paper's argument rests on annotation cost, which retrieval needs over the full training set (≥10,000 cases) §4.2.
• Small models show no gain. Changes against handcrafted prompts are −0.5, −0.2 and +1.5 points in tab. 5. The "emergent ability" reading is an interpretation from three model rows.
• Confounder conclusions are narrow. The claim that step count is the dominant factor is drawn from two datasets and the comparisons in tab. 8. One MathQA arm uses 19 cases rather than the standard 8 tab. 8.
• Table numbering. The text cites the alternative-complexity table as "Table 4", but in source order it is the sixth table. The numbers in this card follow source order; check them against the compiled PDF.
• Appendix is empty. The source's appendix contains only placeholder text, so no extra hyperparameters are given there.
• Cost. The author estimate is 6–8 USD for greedy decoding and 12–24 USD for 50 sampled chains on a 200-instance validation set §4.1. The paper says Codex was free in November 2022 §4.1. Whether text-davinci-002 and code-davinci-002 are still available is not stated.

Lineage

• Builds on: Chain-of-thought prompting (Wei et al.), whose handcrafted prompt is the baseline §4.2; Self-consistency (Wang et al.), which this paper modifies by voting only over the most complex chains §3.2.
• Compared against: random, centroid and retrieval selection §4.2 tab. 4; DiVeRSe (Li et al., arXiv:2206.02336, per the paper's bibliography), a method with an extra trained verifier and the previous SOTA on GSM8K §4.1 tab. 1.
• Superseded by: not known from content already on this wiki.