Complexity-Based Prompting

What Is Complexity-Based Prompting? Complexity-based prompting is a technique for improving chain-of-thought reasoning by preferring more detailed reasoning chains, meaning chains with more reasoning steps. It applies this idea in two places:

Choosing examples: in few-shot chain-of-thought prompts, use examples whose solutions contain more reasoning steps. Choosing answers: when sampling several reasoning paths, vote only among the paths with the most reasoning steps. The technique was introduced in the paper "Complexity-Based Prompting for Multi-Step Reasoning" by Fu et al. (2022), which reported improved accuracy on multi-step math and reasoning benchmarks compared with standard example selection and standard self-consistency.

The Core Idea in One Sentence For multi-step problems, reasoning chains that work through more steps tend to be more reliable than chains that take shortcuts.

Why Would More Steps Help? Short Chains Often Skip Something Consider this problem:

A batch starts with 60 students. 15% leave in the first month. Of the remaining students, one-third choose the evening batch. How many are in the day batch? A short chain:

Day batch is two-thirds of 60 = 40. This chain is fluent but wrong: it skipped the 15% who left.

A longer chain:

15% of 60 students leave: 9. Remaining: 60 − 9 = 51. Evening: 51 ÷ 3 = 17. Day batch: 51 − 17 = 34. The longer chain processes every piece of information in the problem. Short chains are more likely to ignore a condition, merge steps incorrectly, or jump to a familiar but wrong pattern.

Complex Examples Teach Thorough Reasoning In few-shot chain-of-thought (Lesson 41), the model copies the style of reasoning shown in the examples. If the examples solve easy problems in two steps, the model learns to reason briefly. If the examples work through problems that need five or six steps, the model learns to reason thoroughly, including on new problems that need many steps.

An Important Clarification "More steps" means more genuine reasoning steps: each step processes a piece of information or computes an intermediate result. It does not mean longer sentences, repeated statements, or filler. Padding a chain with words does not make it more reliable.

Part 1: Complexity-Based Example Selection How It Works When building a few-shot CoT prompt from a pool of worked examples:

Count the reasoning steps in each example's solution. Choose the examples with the most steps. In the original paper, a simple measure was used: the number of lines in the reasoning, with each line treated as one step.

Example Pool of worked examples:

Example Steps "A course costs ₹2,000 with 10% off. Final price?" 2 "60 students, 15% leave, one-third of the rest choose evenings. Day batch?" 4 "Course ₹6,000, 15% early discount, 18% GST after discount, ₹200 coupon at the end. Final price?" 5 "3 lessons Monday, twice as many Tuesday, 4 fewer Wednesday, 20 total. Lessons left?" 5 Complexity-based selection with three examples chooses the 5-step, 5-step, and 4-step examples, rather than the 2-step one.

Practical Considerations Correctness still comes first. A complex example with a wrong step teaches a wrong method (Lesson 41). Diversity still matters. Three complex examples of the same problem type may lead to copying a fixed path (Lesson 41, Problem 1). Prefer complex examples from different types. Prompt length increases. Complex examples are longer, which raises the cost of every request. Measure whether the accuracy gain justifies it. Part 2: Complexity-Based Consistency How It Works This part extends self-consistency (Lesson 45):

Sample several reasoning chains for the same problem, as in self-consistency. Rank the chains by number of reasoning steps. Keep only the top K most complex chains. Take the majority answer among those chains. Why Not Vote Over All Chains? Standard self-consistency gives every chain one vote. If several chains take the same shortcut, they can outvote the careful chains. Complexity-based voting gives a voice only to the chains that did the most work.

Example Five sampled chains for the batch problem:

Chain Reasoning Steps Answer 1 Leaves 9 → remaining 51 → evening 17 → day 34 4 34 2 One-third of 60 is 20, so 60 − 20 = 40 1 40 3 Day batch is two-thirds of 60 = 40 1 40 4 0.15 × 60 = 9 → 51 left → 17 → 34 4 34 5 Evening 20 → day 40 2 40 Standard majority vote: 40 wins, 3 votes to 2. The answer is wrong, because three chains made the same shortcut of ignoring the students who left. Complexity-based vote (top 3): chains 1, 4, and 5 are kept; 34 wins, 2 votes to 1. The answer is correct. This example is constructed to show the mechanism clearly. In practice, the benefit is statistical: across many problems, voting among more detailed chains tends to improve accuracy, but it will not fix every case.

Implementing Complexity-Based Voting in Python The following code implements step counting and both voting methods. It runs without an API call, using the five chains from the table above.

from collections import Counter

def count_steps(reasoning: str) -> int: """Count non-empty lines as reasoning steps.""" return len([line for line in reasoning.splitlines() if line.strip()])

def majority_vote(samples: list[tuple[str, str]]) -> str: return Counter(answer for _, answer in samples).most_common(1)[0][0]

def complexity_vote(samples: list[tuple[str, str]], top_k: int = 3) -> str: ranked = sorted(samples, key=lambda s: count_steps(s[0]), reverse=True) return majority_vote(ranked[:top_k])

samples = [ ("15% of 60 students leave: 9\nRemaining: 60 - 9 = 51\n" "Evening: 51 / 3 = 17\nDay batch: 51 - 17 = 34", "34"), ("One-third of 60 is 20, so 60 - 20 = 40", "40"), ("Day batch is two-thirds of 60 = 40", "40"), ("Students leaving: 0.15 x 60 = 9\nStudents left: 51\n" "One-third of 51: 17\nDay batch: 34", "34"), ("Evening batch: 20\nDay batch: 40", "40"), ]

print("Majority vote:", majority_vote(samples)) print("Steps per sample:", [count_steps(r) for r, _ in samples]) print("Complexity vote (top 3):", complexity_vote(samples, top_k=3)) Output:

Majority vote: 40 Steps per sample: [4, 1, 1, 4, 2] Complexity vote (top 3): 34 Code Explanation count_steps() Splits the reasoning into lines and counts the non-empty ones. This matches the simple line-based measure used in the original research. It works only if the reasoning is written one step per line, so the prompt must request that format.

majority_vote() Standard self-consistency voting with Counter (Lesson 45).

complexity_vote()

Sorts the samples by step count, most steps first. Votes only among the top top_k samples. sorted() is stable, so samples with equal step counts keep their original order. Using It With Real Model Outputs To use complexity-based voting with real samples, the prompt should request one step per line and a clearly marked answer:

Solve the problem. Write each reasoning step on its own line. Then give only the final number inside tags. The reasoning text (everything before ) is passed to count_steps(), and the answer is extracted as in Lesson 45.

Choosing top_k Too small (for example, 1): you rely on a single chain, losing the benefit of voting. Too large (all samples): you are back to standard majority voting. A middle value, such as about half of the samples, keeps the most thorough chains while still voting. Measure on your own test set to choose. Limitations Step Count Is a Rough Measure Counting lines is simple but imperfect:

A chain can have many lines and still contain an error. A model can split one step into several lines, or combine several steps into one line. Repetitive or rambling chains can score as "complex" without being better. Not Every Problem Needs Long Reasoning For problems that genuinely require only a few steps, preferring longer chains may favor over-complicated reasoning. The technique is designed for multi-step problems (Lesson 43).

Systematic Errors Remain If the most detailed chains all share the same misunderstanding, for example because a rule in the prompt is ambiguous, complexity-based voting will select the wrong answer just as standard voting would (Lesson 46).

Cost Like self-consistency, complexity-based consistency requires several samples per problem. Complex examples also make the prompt longer.

When to Use Complexity-Based Prompting Situation Recommendation Building a few-shot CoT prompt for multi-step problems Prefer correct, diverse examples with more reasoning steps Using self-consistency on problems where shortcuts are common Try complexity-based voting and compare with majority voting Problems that need only one or two steps Standard prompting or single CoT is usually enough Open-ended output without exact answers Not applicable: voting requires comparable answers As with every technique in this section, decide based on measurement: compare majority voting and complexity-based voting on the same samples and the same test set, as shown in Lesson 46.

Common Mistakes Mistake 1: Measuring Length Instead of Steps What it is: Ranking chains by number of words or characters.

Why it happens: Text length is easy to measure.

What it causes: Verbose chains with filler are preferred over concise, thorough ones.

How to fix it: Request one step per line and count lines, or ask for numbered steps and count them.

Mistake 2: Choosing Complex but Incorrect Examples What it is: Selecting the longest examples without verifying them.

Why it happens: Complexity becomes the only selection criterion.

What it causes: The model learns detailed but flawed reasoning.

How to fix it: Verify every step of every example before selection.

Mistake 3: Complex Examples of Only One Type What it is: All selected examples come from the same kind of problem.

Why it happens: The most complex examples in a pool often share a type.

What it causes: The model applies one fixed reasoning path to all problems.

How to fix it: Select the most complex examples within different problem types.

Mistake 4: Applying It to Simple Tasks What it is: Preferring long reasoning for problems that need little.

Why it happens: The technique is applied universally.

What it causes: Higher cost and possibly over-complicated answers.

How to fix it: Use it for multi-step problems where shortcuts cause errors.

Best Practices Prefer examples that show thorough, correct reasoning. For multi-step tasks, demonstrate every step.

Request one step per line. It makes step counting possible and reasoning easier to read.

Vote among the most detailed chains when shortcuts are common. Keep top_k large enough to still vote.

Combine complexity with correctness and diversity. Complexity alone is not a quality guarantee.

Measure against standard voting. Use the same samples for a fair comparison.

Try It Yourself Exercise 1: Rank Examples by Complexity Write eight worked examples for fee or schedule calculations, with one step per line. Count the steps in each with count_steps(). Build two few-shot CoT prompts: one with the three simplest examples and one with the three most complex. Test both on ten new multi-step problems and compare accuracy.

Exercise 2: Compare Voting Methods Sample seven reasoning chains for each of ten multi-step problems, using a prompt that requests one step per line. For each problem, compute both the majority vote and the complexity vote with top_k=4. Count how often each method gives the correct answer, and inspect the problems where they disagree.

Exercise 3: Find the Weakness Construct a set of sample chains where complexity-based voting gives the wrong answer, for example, where the longest chains repeat steps or contain the same error. Explain what this shows about the limits of using step count as a quality signal.