Scheherazade: Evaluating Chain-of-Thought Math Reasoning in LLMs with Chain-of-Problems

1 Introduction

• As advanced models exceed 94% accuracy on GSM8K, benchmark scores converge, while creating new high-quality benchmarks often requires costly manual work.The introduction also notes data-contamination concerns and limits in existing synthetic benchmark methods.Source: §1 · p. 1
• Scheherazade logically chains existing benchmark problems to create larger, more complex tests of mathematical and logical Chain-of-Thought reasoning.The paper motivates longer chains as a way to test whether models can parse and discard irrelevant statements.Source: §1 · pp. 1–2
• Forward chaining links problems for sequential solving, whereas backward chaining makes earlier problems depend on later context and requires reverse reasoning.Conditional branches and randomness are used to discourage memorizing the format; the methods support chains of any length and ordering.Source: §1 · p. 2
• Only o1-preview shows a gradual backward-chaining accuracy decline; GPT-4o and other evaluated models fall steeply as backward chains lengthen.For forward chaining, both GPT-4o and o1-preview show a gradual decline as chains grow.Source: §1 · p. 2

2.1 Chain of Thought Prompting

• Chain-of-thought prompting elicits intermediate reasoning steps; Self-Consistency samples multiple paths, while Tree-of-Thoughts explores branching trajectories.The cited work describes applications to arithmetic, commonsense, and logical reasoning.Source: §2.1 · p. 2

2.2 Synthetic math reasoning benchmark creation

• With GSM8K scores above 94%, benchmark differentiation has weakened, while alternatives such as MATH and large-scale automated generation address the need for harder evaluation.The passage notes that alternative datasets often require costly manual curation.Source: §2.2 · p. 2
• Prior synthetic methods shuffle premises, use templates, add irrelevant context, or mutate numbers, but their generated benchmarks have limited complexity and diversity.The cited examples include Chen et al. (2024), Zhang et al. (2024b), Li et al. (2024), Shi et al. (2023), Anonymous (2024), and Gao et al. (2023).Source: §2.2 · pp. 2–3
• Scheherazade creates nested dependencies through forward and backward chaining; unlike Hosseini et al. (2024), it is not limited to forward chains of two problems.The passage situates automated chaining within synthetic data augmentation and scalable evaluation methods.Source: §2.2 · p. 3

3.1 Forward Chaining

• Forward chaining links problems sequentially through randomly selected if-then-else structures, and taking the wrong branch leads to an incorrect conclusion.The chaining methods generalize to arbitrary lengths and allow permutations of component problems.Source: §3.1 · p. 3

3.2 Backward Chaining

• Backward chaining requires information from later problems to resolve earlier premises, while the final question asks for the solution to the first problem in the chain.As the chain grows, solving the first premise requires resolving successive later problems.Source: §3.2 · p. 4

3.3 Generation Power

• With 50 starting benchmark problems, Scheherazade can generate approximately 5.64 × 10^79 different problems.The generation space draws on problem orderings, randomized branching, and both chaining methods.Source: §3.3 · p. 5

4 Evaluation

• The evaluation covers four models on lengths 2–10 in both chaining directions; three models receive 1,000 problems per length and technique, while o1-preview receives 200.The three-model evaluation totals 54,000 cases; o1-preview's evaluation totals 3,600.Source: §4 · p. 5
• Normalized backward accuracy plummets by lengths 2–3 for every model except o1-preview, which maintains relatively strong accuracy over longer chains.Source: §4 · p. 5, Figure 2 · p. 6
• Raw accuracy declines as chain length rises for every model in both directions; by length 10, every model except o1-preview fails on almost every backward problem.GPT-4o reaches 0.5 raw correctness accuracy on forward chaining at length 10.Source: §4 · p. 5, Table 1 · p. 6
• GPT-4o has the largest forward–backward accuracy disparity: its forward accuracy stays relatively high across lengths while backward accuracy sharply declines.Source: §4 · p. 6
• Normalized forward accuracy remains similar across chain lengths for o1-preview, while GPT-4o declines more gradually than the other models.Source: §4 · p. 6
• For shorter chains, all models have higher backward than forward accuracy, but forward accuracy generally overtakes it by length 6; o1-preview remains higher on backward chains.Source: §4 · p. 6

Error Analysis

• A manual review of 40 incorrect answers identified four error categories, with semantic misunderstandings making up the largest share; Fig. 3 shows their distribution.The sample included 20 forward-chaining and 20 backward-chaining errors.Source: §5 · p. 7, Figure 3 · p. 8

Semantic Understanding Errors

• Semantic misunderstandings include misreading a question or its conditions, sometimes by assuming the stated conclusion and reasoning backward to fit it.The authors describe this condition-statement error as a flaw in reasoning about logical control flows.Source: §5 · p. 7

Wrong Path Errors

• Wrong-path errors arise when models take the wrong conditional branch, skip an intermediate step, or invent an alternative path.In an “Alternative Exploration,” a model may alter numbers in its proof to fit the answer it has calculated is desired.Source: §5 · p. 7

False Negatives

• False negatives occur when answer extraction misses a correct response, including when refuting a conditional leaves an intermediate answer unstated.The evaluator looks for answers to each intermediate question.Source: §5 · p. 7

Infinite Loops

• GPT-4o sometimes repeated an incorrect calculation until reaching the output limit, producing exceptionally long outputs of around 100,000 characters.The authors report observing this behavior only for GPT-4o, outside their random error sample.Source: §5 · p. 7

Error Analysis

• In a randomized subset of errors, GPT-4o showed semantic errors while o1-preview showed a wider mix; the authors offer greater logical-question understanding as one unconfirmed explanation.They state that more work is needed to determine whether this explanation is correct.Source: §5 · pp. 7–8

6 Conclusion and Future Work

• Scheherazade chains problems forward or backward to create composite benchmarks; applying it to GSM8K produced GSM8K-Scheherazade and notable evaluation differences from native GSM8K.The authors say the framework can use any starting benchmark set.Source: §6 · p. 8
• Future work could apply Scheherazade to benchmarks such as MATH, combine conjunctions or disjunctions with implications, and sum numerical solutions.The authors also suggest finer-grained question ordering, hybrid chaining, and within-question mutations.Source: §6 · p. 8
• The authors see hybrid chaining and within-question mutations as ways to further explore o1-preview’s reasoning scope and expand benchmark generation difficulty.They identify these as avenues for future work, not evaluated results.Source: §6 · p. 8

• 3.75% of errors were false negatives from answer extraction, potentially underestimating model performance.Source: §7 · p. 9
• Starting benchmarks must avoid pronouns and use unique names and variables across benchmarks to prevent ambiguity.Source: §7 · p. 9
• Each starting problem needs an incorrect conclusion for random branch selection, and some datasets may need manual cleanup, adding overhead.Source: §7 · p. 9

• The example gives ages and age relationships for Amy, Jackson, Corey, and Jason.Source: §A.1 · p. 10
• A condition on Jackson’s age selects whether Joseph cares for 12 or 10 dogs.Source: §A.1 · p. 10
• The final question asks for weekly dog-care hours, given a daily care time of 0.5 hours per dog.Source: §A.1 · p. 10

• The chain uses raspberry totals and clothing expenditure as conditions that determine subsequent problem statements.Source: §A.2 · p. 10
• Polly’s javelin range relative to the dragon’s flames determines whether Toulouse has two or three times Charleston’s sheep.Source: §A.2 · pp. 10–11
• The final question asks for the combined sheep count of Toulouse, Charleston, and Seattle; the listed solutions are [187, 243, 200, 260].Source: §A.2 · p. 11

A.3 Length 6

• A length-6 example links Jim’s TV and reading time, a dragon-range condition, rose-planting, article-writing, and dog-care questions.Source: §A.3 · p. 11

B.1 Length 2

• The length-2 example uses gift-bag spending to select a pet-count relationship, then asks for the combined pets owned by Jan, Marcia, and Cindy.Source: §B.1 · p. 11

B.2 Length 4

• The length-4 example chains treasure, DVD-sale, and Lego-set conditions before asking how far James runs weekly; its listed solutions are [2, 7, 595, 540].Source: §B.2 · pp. 11–12

B.3 Length 6

• The length-6 example links egg sales, raspberry counts, sandcastle area, treasure, gift bags, and chicken feeding before asking about weekly egg income.Source: §B.3 · p. 12