PaperlayerView exact revision on arXiv

Source-linked AI summary

MuSR: Testing the Limits of Chain-of-thought with Multistep Soft Reasoning

Zayne Sprague, Xi Ye, Kaj Bostrom, Swarat Chaudhuri, Greg Durrett

arXiv:2310.16049v2cs.CL

TL;DR

LLMs still struggle with robust reasoning in complex natural-language settings, while existing benchmarks inadequately combine sophisticated language and multistep commonsense reasoning. MuSR introduces a scalable neurosymbolic narrative-generation method and evaluates models on the resulting benchmark, finding that GPT-4 remains below human performance.

  • Problem

    Existing reasoning benchmarks often lack sophisticated natural language, multistep reasoning, commonsense, or resistance to rule-based solutions, making combined evaluation difficult.

  • Method

    MuSR constructs narrative reasoning problems by generating gold facts, recursively expanding reasoning trees with an LLM, and embedding validated scenario facts into stories.

  • Results

    LLMs are currently unable to match human performance on specific multistep and commonsense reasoning types across MuSR’s three domains.

  • Takeaways & Limitations

    MuSR provides a benchmark for evaluating LLM reasoning and for testing generation and reasoning approaches on complex narrative tasks.

  • Takeaways & Limitations

    The paper does not formally evaluate the fluency, coherence, or intrinsic commonsense sensibility of generated stories, instead using end-to-end human reasoning accuracy.

Abstract

from arXiv · show

While large language models (LLMs) equipped with techniques like chain-of-thought prompting have demonstrated impressive capabilities, they still fall short in their ability to reason robustly in complex settings. However, evaluating LLM reasoning is challenging because system capabilities continue to grow while benchmark datasets for tasks like logical deduction have remained static. We introduce MuSR, a dataset for evaluating language models on multistep soft reasoning tasks specified in a natural language narrative. This dataset has two crucial features. First, it is created through a novel neurosymbolic synthetic-to-natural generation algorithm, enabling the construction of complex reasoning instances that challenge GPT-4 (e.g., murder mysteries roughly 1000 words in length) and which can be scaled further as more capable LLMs are released. Second, our dataset instances are free text narratives corresponding to real-world domains of reasoning; this makes it simultaneously much more challenging than other synthetically-crafted benchmarks while remaining realistic and tractable for human annotators to solve with high accuracy. We evaluate a range of LLMs and prompting techniques on this dataset and characterize the gaps that remain for techniques like chain-of-thought to perform robust reasoning.

1 INTRODUCTION

MuSR addresses the lack of benchmarks combining sophisticated natural language with sophisticated multistep reasoning by introducing a neurosymbolic, narrative-based dataset and generation procedure.

  • The benchmark targets a gap left by datasets that are either formally solvable, structurally simple, or lacking sophisticated natural language.Existing math, rule-based, and commonsense benchmarks do not jointly provide sophisticated language and sophisticated reasoning.
  • MuSR evaluates reasoning over long text narratives requiring commonsense interpretation and domain-specific System 2-style deliberation.Its domains include murder mysteries, object placement, and team assignment, involving physical and social reasoning and theory of mind.
  • MuSR automatically generates narratives by combining gold facts, LLM-produced reasoning trees, and iterative fact-consistent story generation.The procedure uses supporting logic to elicit examples that the generating LLMs cannot reliably solve.
  • 756 total examples across three domains form a benchmark designed to challenge GPT-4, Llama 2, and Vicuna while analyzing chain-of-thought and neurosymbolic approaches.The stated contributions include the dataset, its reasoning-tree-grounded narrative-generation algorithm, and evaluations of prompting and neurosymbolic methods.

2 BACKGROUND AND MOTIVATION

MuSR is motivated by the absence of a benchmark that combines natural narratives, commonsense, multistep reasoning, and intermediate structure while resisting simple rule-based solutions.

  • Prior reasoning datasets often use artificial or isolated facts, omit commonsense reasoning, or remain solvable with rule-based methods.These limitations affect datasets including bAbI, BigTOM, ToMi, RuleTakers, ProntoQA, CLUTRR, and related benchmarks.
  • Table 1 compares reasoning datasets across qualities including natural text, commonsense, multistep reasoning, intermediate structure, and rule-based solvability.The caption states that no previous dataset encompasses all listed qualities and that ∼ denotes partial qualification.
  • Existing systems commonly target specific reasoning axes and struggle with natural contexts where relevant facts are distributed across long narratives.Search-loop systems enumerate facts and conclusions, but the cited discussion distinguishes this from reasoning over natural narrative contexts.
  • End-to-end prompting approaches require systems to extract facts, apply commonsense, and perform multistep reasoning before answering.The paper positions MuSR as a test of these combined requirements rather than isolated step-by-step deduction.
  • Synthetic benchmarks are presented as scalable and renewable as more capable language models emerge.The paper contrasts this with the cost and difficulty of collecting new human-authored datasets when existing mysteries become solvable.

Object Placements

Figure 2 depicts partial reasoning trees for three domains, separating gold, story, and commonsense facts and showing the structure of sampled deductions.

  • The trees distinguish gold facts F, story facts S(T), and commonsense facts C(T) across all three domains.Dotted lines indicate incomplete trees.
  • Each LLM-sampled deduction produces two scenario facts and one commonsense fact in the illustrated setup.

3 CREATING MUSR

MuSR instances are constructed by defining gold facts and questions, expanding them into validated multistep reasoning trees, and embedding scenario facts into narratives.

  • The three-stage construction method comprises Tree Template Construction, Reasoning Tree Completion, and Story Generation.These stages respectively establish the reasoning strategy and gold facts, expand intermediate reasoning, and embed facts in a natural narrative.
  • The generated instance contains gold facts, a reasoning tree, a narrative, questions, and answers, while the gold structure is generally withheld at test time.The task is to predict answers from the narrative and question.
  • Tree Template Construction: Each domain begins with a high-level fact set F and question-answer pairs, such as suspect facts supporting a murder-mystery answer.
  • Tree Template Construction: The structured fact set must support a program that maps each question to its answer, while additional facts G increase diversity and help expand later stories.
  • Reasoning Tree Completion: For every gold fact, recursively sampled reasoning trees represent statements entailed by supporting statements and incorporate facts from G for diversity.
  • Reasoning Tree Completion: The trees are expanded to a specified depth, producing scenario-specific leaves required in the narrative and unstated commonsense leaves expected to be generally accepted.
  • Reasoning Tree Completion: Validators control tree depth and shape and prevent vacuous transitions or reasoning shortcuts during generation.Invalid samples are retried up to three times; unsuccessful branches are pruned as leaf nodes.
  • Story Generation: Story generation partitions scenario facts into answer-related chunks, produces chapters from smaller fact lists, and concatenates them into one narrative.Additional prompts may smooth the final narrative when necessary.

4 MUSR DOMAINS

MuSR covers murder mysteries, object placement, and team assignment as multistep reasoning domains grounded in social, physical, spatial, and assignment constraints. Each domain defines a structured answer function and expands underlying facts or observations into reasoning trees and narratives.

  • Murder Mysteries: Murder mysteries require physical, social, and temporal reasoning about motives, social norms, and opportunities to commit a crime.The domain is designed around complex social scenarios and temporal opportunity reasoning.
  • Murder Mysteries: The murderer is the suspect whose facts establish means, motive, and opportunity.The answer function identifies the suspect satisfying all three conditions.
  • Object Placements: Object Placements tests spatial reasoning and theory of mind by asking where people believe items are based on the moves they observed.A person’s answer is the last location where they saw the item move, or its original location if they saw no move.
  • Object Placements: Reasoning trees explain why individuals did or did not observe item movements, incorporating commonsense situations such as a distracted barista.Each move records whether each person observed it, and the tree supplies reasons for those observations.
  • Team Allocation: Team Allocation selects the highest-scoring assignment of three people to two tasks using skill levels and pairwise teamwork scores.Because there are fewer tasks than people, one task has two people, introducing a social component to the assignment.
  • Team Allocation: Team Allocation reasoning trees describe factors underlying individual skills and relationships.The domain connects assignment quality to inferred past experiences and personal preferences.

5 EXPERIMENTS

Experiments validate MuSR’s data quality and benchmark the limits of current LLM reasoning. GPT-4 performs best among tested models, but remains below humans even with enhanced prompting.

  • Dataset validation: MuSR contains three GPT-4-generated datasets, while fluency, coherence, and commonsense sensibility are assessed indirectly through end-to-end answer accuracy.The authors do not formally evaluate these intrinsic story properties.
  • Dataset validation: Rule-based baselines for Murder Mystery and Object Placements perform near random chance, providing a sanity check that these domains are not solved by simple frequency heuristics.The Murder Mystery baseline selects the suspect with the longest chapter, while Object Placements selects the most-mentioned location.
  • Dataset validation: Human evaluation used seven annotators and triply annotated over 100 instances per domain; majority voting exceeded average annotator performance and was judged to represent a very high human ceiling.The evaluation included four authors and three undergraduate students unfamiliar with dataset construction.
  • Dataset validation: Ablations show that chaptering increases fact recall and nearly doubles story length while preserving diversity, whereas removing chaptering or validators lowers narrative quality and accuracy.Direct generation from reasoning trees entailed only 62% of original murder-mystery facts; low GPT-4 performance can indicate ambiguity or unsolvability.
  • Benchmarking with MuSR: The benchmark compares single-shot, chain-of-thought, CoT+, and neurosymbolic methods, with CoT+ adding an engineered textual description of each domain’s reasoning strategy.The neurosymbolic systems are tailored to domains matching their designed capabilities.
  • Benchmarking with MuSR: GPT-4 performs best among tested LLMs but remains below humans, while 1-shot and few-shot CoT+ generally improve performance without closing the human gap.Adding more examples is not always better, and the domain-specific Murder Mystery decomposition performs worse than end-to-end GPT-4 prompting.

6 CONCLUSION

MuSR is a natural-narrative reasoning dataset designed to evaluate complex, multistep reasoning across three domains. The authors report that current LLMs remain below human performance on these reasoning tasks.

  • MuSR presents natural narratives describing complex reasoning scenarios across varied reasoning strategies.The dataset targets murder mysteries, object placement, and team assignment.
  • Its neurosymbolic generation method constructs instances whose complexity can scale as more powerful models emerge.The construction method is supported by human evaluation and other intrinsic validations for sufficiently large models.
  • Current LLMs do not match human performance on multistep and commonsense reasoning in MuSR’s three domains.
  • MuSR is proposed as a benchmark for LLMs, neurosymbolic approaches over language, and challenging dataset generation as models improve.

7 REPRODUCIBILITY OF MUSR

The paper provides detailed construction and implementation information for reproducing MuSR, while noting that shallow reasoning trees currently produce the best narratives.

  • Reproduction materials include construction details, domain reasoning strategies, algorithms, verbatim prompts, hyperparameters, and model design choices.
  • Reasoning trees of depth one or two produced the best level of detail for narrative construction.GPT-4 often failed to create sufficiently complex facts for recursive decomposition at greater depths.
  • Increasing acceptable deduction depth remains an area for future work through improved prompting and more capable language models.

A.2 HUMAN EVALUATION

The authors’ Mechanical Turk validation experiment encountered substantial concerns about worker judgment quality and the provenance of collected justifications.

  • Many Mechanical Turk workers performed very poorly during qualification rounds.
  • Collected justifications included many responses suspected to have been written by ChatGPT.

B DATASET FEATURES EXPLAINED

MuSR combines natural contexts with commonsense and multistep reasoning, explicit intermediate structures, and resistance to simple rule-based solutions. Its feature definitions distinguish these properties from those of prior datasets.

  • Natural text means organically constructed language rather than template-filled text; MuSR uses LLM-prompted natural contexts without templating.
  • Commonsense datasets require knowledge beyond the facts explicitly supplied, and MuSR intentionally omits certain commonsense facts during construction.
  • Multistep datasets require layered inference in which intermediate conclusions contribute to the final answer; MuSR is designed to recreate its underlying reasoning tree.
  • Intermediate structures are underlying fact chains or related structures that can assist deduction; MuSR provides the reasoning trees used to create each example.
  • Not solvable with rules means resisting systematic solutions based only on reverse-engineered textual patterns; MuSR lacks easily identifiable patterns.
  • Table 8 reports prompting results on 50 murder mysteries generated by GPT-3.5-turbo, using a GPT-4-created and human-solved mystery as the one-shot example.

C CREATING MUSR WITH OTHER MODELS

The authors investigate whether models other than GPT-4 can generate MuSR examples that satisfy the dataset’s reasoning-tree construction requirements. Smaller models required prompt modifications and still produced substantial reasoning flaws, while GPT-3.5-generated mysteries had similar downstream performance to the main dataset.

  • Alternative generation models: GPT-3.5-turbo, Llama2-70B-Chat, and Mixtral were evaluated as alternative models for creating MuSR examples.The section examines whether these models can follow the construction prompts and complete the required deductions.
  • Alternative generation models: Weaker models required prompt edits, detailed self-refinement, iterative temperature increases, and more retries to approach GPT-4’s example quality.The generation workflow was adjusted across retries rather than using the original GPT-4 setup unchanged.
  • GPT-3.5-turbo generation: The 50 murder mysteries created with GPT-3.5-turbo yielded overall LLM performance similar to that on the main MuSR dataset.The comparison was reported for the CoT+ and 1-Shot CoT+ systems.
  • GPT-3.5-turbo generation: GPT-3.5-turbo produced some high-quality examples, but many reasoning trees contained major flaws that failed inspection.The reported errors included hallucination and invalid deductions that the workflow had erroneously accepted as valid.
  • Alternative generation models: Llama2-70B-Chat and Mixtral could not follow the construction instructions or complete the deductions needed to create MuSR examples.This remained true despite significant edits to the prompt format.

D QUALITATIVE ERROR ANALYSIS

The qualitative analysis identifies recurring reasoning failures in GPT models solving MuSR problems. These include premature answer commitment, instruction violations, hallucinations, and unsupported or inconsistent deductions.

  • Pre-committing to an answer: Many responses committed to an answer before reasoning, biasing subsequent reasoning and selectively presenting evidence for only one option.The subtler form omitted important facts relevant to the alternative answer.
  • Ignoring instructions: Many responses ignored prompt instructions, such as choosing a murderer from a strong motive without establishing motive, means, and opportunity.Team-allocation responses also allowed people assigned to different jobs to work together despite the prompt’s constraint.
  • Hallucination and invalid logic: Hallucinations included invented locations or actions and confusion about pronouns and entity relations.The analysis also reports unsupported deductions and contradictions between reasoning traces and final answers.

E STRUCTURED BASELINE IMPLEMENTATION DETAILS

The structured baselines adapt existing methods to MuSR’s three domains. Each baseline uses domain-specific decomposition, state querying, or executable program generation to produce answers.

  • Decomposed Prompting: Decomposed Prompting solves Murder Mysteries with fixed subtasks that identify each suspect’s means, motive, and opportunity.The Decomposer Prompt stage is omitted because all murder mysteries share this high-level logical procedure, and subtask results are aggregated.
  • SymbolicTOM: SymbolicTOM is evaluated on Object Placements with states queried on the fly using GPT-3.5 rather than precomputed.When the model abstains, the implementation randomly samples an answer choice.
  • Program-aided language models: Program-aided language models solve Team Allocation by generating a Python program and executing it with a Python interpreter.PAL is tested in both zero-shot and one-shot settings.
  • Program-aided language models: The zero-shot Team Allocation prompt organizes the program around assigning skills, assigning pairwise collaboration values, and computing option scores.The final scores combine individual skill-level and teamwork-related terms.

F DATASET EXAMPLES

The murder-mystery examples present narrative evidence about suspects, locations, relationships, weapons, and behavior before asking which suspect is most likely responsible. The accompanying reasoning tree formalizes the answer through means, motive, and opportunity.

  • F.1 MURDER MYSTERIES: The examples use a detective narrative in which a victim’s death at a bungee-jumping site prompts interviews with suspects.The narrative includes dialogue, witness information, suspect behavior, and physical evidence such as a weapon matching the forensics report.
  • F.1 MURDER MYSTERIES: Ana’s account places her and Mack together in a car headed to the site, while her cleaning behavior and nervousness provide additional suspicious evidence.She says she signed up to jump but did not go through with it, and she cleans the shared car after use.
  • F.1 MURDER MYSTERIES: Mackenzie’s evidence includes presence at the site, martial-arts training with nunchaku, jealousy toward Mack, and prior arguments.A matching nunchaku is later found among his belongings, while witnesses repeatedly point to the bungee-jumping scaffolding.
  • F.1 MURDER MYSTERIES: The question requires selecting one murderer and explaining the reasoning step by step before producing a final answer.The prompt defines a murderer as a suspect with an established means, motive, and opportunity, with a preference for the suspect for whom these are best established.
  • F.1 MURDER MYSTERIES: The example reasoning tree concludes that Mackenzie is the murderer by organizing deductions about his means and the suspects’ opportunities and evidence.The tree links story facts and commonsense knowledge into a deduced root conclusion.

F.2 OBJECT PLACEMENTS

The object-placement task asks models to track what each person believes about an object's location as events unfold. The example requires distinguishing observed moves from unobserved moves using visibility and attention.

  • Object Placement Example: Danny initially keeps the earphones in the recording booth while managing the studio.The narrative establishes the earphones’ starting location before later movement.
  • Object Placement Example: Emma moves the earphones to the producer’s desk while Danny is distracted by a visiting sound engineer.Danny’s attention is diverted, and the visitor blocks his general view of the studio.
  • Object Placement Example: Because Danny does not observe the move, he continues to believe the earphones are in the recording booth.The task’s reasoning rule preserves the last location a person observed when they miss a subsequent move.
  • Task Reasoning Rule: Solving object placement requires tracking each person’s beliefs and whether they could see a move without excessive distraction.A person must see the destination and remain sufficiently attentive to update their belief about the object’s location.
  • Task Output: The example asks which location Danny would search, with the recording booth among the three answer choices.The prompt requires one choice and a step-by-step explanation before the final answer format.

H.1 IMPLEMENTATION DETAILS: CREATING AND EVALUATING MUSR

MuSR is generated and evaluated with fixed prompting and domain-specific reasoning-tree settings. The implementation also reports hardware, quantization, and GPT-4-based evaluation cost and runtime estimates.

  • Dataset Creation: GPT-4 generates MuSR examples with default parameters, including temperature and top-p both set to 1.0.The creation process does not change GPT-4’s default prompting parameters.
  • Domain Settings: Murder Mystery generation uses reasoning trees of maximum depth 4 and only two suspects, while sampling diverse story facts.Sampled attributes include victims, weapons, crime scenes, suspects, motives, roles, and suspicious facts.
  • Domain Settings: Object Placement generation uses depth 3, three allowed moves, two items, and a 33% chance that a person observes a move.The constraints force one item to be moved twice and support diversity through sampled scenarios, names, moves, and motivations.
  • Domain Settings: Team Allocation generation uses maximum reasoning depth 2 and samples scenarios, tasks, and people’s names.Its generation settings are simpler than those specified for the other two domains.
  • Evaluation Setup: Evaluation uses GPT-4 and GPT-3.5 chat endpoints, Hugging Face implementations for Llama 2 and Vicuna, and four RTX A6000 GPUs for local models.Local-model inference uses bitsandbytes quantization without changing sampling parameters.
  • Evaluation Cost: Table 9 estimates the time and cost of running each dataset domain with GPT-4 and the CoT+ 1-Shot prompt.The reported estimates are tied specifically to that model and prompting configuration.

I EVALUATION PROMPTS AND OUTPUTS

The evaluation prompts turn each narrative domain into a constrained multiple-choice reasoning task with explicit instructions for step-by-step explanations. An included GPT-4 error example illustrates that even the evaluated reasoning can fail.

  • I.1 EVAL PROMPTS: Murder Mystery prompts ask which suspect is most likely the murderer and require checking means, motive, and opportunity.A suspect may be suspicious with two factors established, but the prompt treats all three as the decisive combination.
  • I.1 EVAL PROMPTS: Across the prompts, models must select one option, explain their reasoning step by step, and end with a specified ANSWER format.This output structure is repeated for the evaluated task prompts.
  • I.1 EVAL PROMPTS: If both suspects appear to satisfy the criteria, the prompt directs the model to choose the suspect whose evidence is best established.If neither fully qualifies, it selects the suspect with the clearest support.
  • I.1 EVAL PROMPTS: Object Placement prompts ask where a person believes an object is at the story’s end.The reasoning requires updating beliefs only when a move is observed, with visibility and distraction determining observation.
  • I.1 EVAL PROMPTS: Team Allocation prompts seek a unique assignment that completes two tasks efficiently while accounting for individual skills and teamwork.One task requires two people, and a strong individual may not compensate for poor cooperation.
  • I.2 INCORRECT EVALUATIONS FROM GPT-4: The GPT-4 error example presents a murder mystery involving a grenade death, an empty crime scene, and a suspect with bomb-related expertise and explosives.The example’s narrative supplies contextual clues before the model’s evaluation output.
  • I.2 INCORRECT EVALUATIONS FROM GPT-4: In the object-placement example, Danny would search the recording booth because he missed Emma’s move of the earphones to the producer’s desk.The stated reasoning relies on Danny’s initial placement, distraction, and lack of visual access to the move.
Loading 2310.16049v2…