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

Existing benchmarks often lack both sophisticated natural language and sophisticated multistep reasoning. MuSR introduces narrative-based reasoning tasks generated with a neurosymbolic procedure, and shows that current LLMs remain below human performance on the evaluated reasoning domains.

  • Problem

    Existing benchmarks lack tasks combining sophisticated natural language with sophisticated multistep reasoning, limiting evaluation of robust LLM reasoning.

    Source: §1 · p. 1
  • Method

    MuSR uses a neurosymbolic dataset-generation method to create long natural-language narratives requiring domain-specific multistep reasoning across three domains.

    Source: §1 · pp. 1–2
  • Results

    LLMs, including GPT-4, remain unable to match human performance on multistep and commonsense reasoning across MuSR’s three domains.

    Source: §5.2 · p. 8, §6 · p. 9
  • Takeaways & Limitations

    MuSR provides a benchmark for evaluating LLM reasoning on complex natural-language narratives that challenge both larger and smaller models.

    Source: §1 · p. 2, §6 · p. 9

    The paper does not formally evaluate the fluency, coherence, or intrinsic commonsense sensibility of its generated stories.

    Source: §5.1 · p. 7

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 reasoning by introducing a 756-example dataset of narrative tasks across three domains. Its neurosymbolic generation procedure grounds natural narratives in reasoning trees, producing instances that challenge state-of-the-art models and support analysis of prompting and neurosymbolic methods.

Motivation

  • MuSR fills a benchmark gap by combining sophisticated natural language with multistep reasoning, unlike datasets that are formally solvable or structurally limited to one or two reasoning steps.Existing math and rule-based datasets can be approached with formal tools, while commonsense datasets such as SocialIQA and StrategyQA are often structurally simple.Source: §1 · p. 1

Dataset construction

  • The proposed neurosymbolic generation algorithm first constructs gold facts and reasoning trees, then iteratively generates and validates narrative chunks for fact consistency and recall.The resulting narratives preserve congruence between the reasoning and the text while using LLMs to generate natural-language instances.Source: Figure 1 · p. 2, §1 · p. 2

Benchmark challenge

  • Recovering the reasoning from MuSR narratives is solvable by humans but not by GPT-4 across the tested prompting and neurosymbolic approaches, whereas single-shot narrative generation produces unnatural, homogeneous, and sometimes inconsistent stories.This difficulty motivates using supporting logic during generation rather than relying on basic prompting alone.Source: §1 · p. 2

Dataset and task scope

  • MuSR provides 756 examples across murder mysteries, object placement, and team assignment, requiring commonsense, theory-of-mind, and System 2-style deliberation over narrative evidence.The narratives are hundreds of words long, and each domain requires a different form of deliberation to reach the final answer.Source: §1 · pp. 1–2

Evaluation

  • The paper evaluates LLM performance on MuSR, emphasizing chain-of-thought variants and existing neurosymbolic approaches for the three narrative reasoning problems.The benchmark is designed to challenge models including GPT-4, Llama 2, and Vicuna.Source: §1 · p. 2

2 BACKGROUND AND MOTIVATION

Existing reasoning benchmarks often lack natural narratives, commonsense and multistep reasoning, or resistance to rule-based solutions. MuSR is motivated as a scalable, regenerable benchmark that tests extracting distributed facts, applying commonsense, and performing multistep reasoning in complex stories.

Motivation

  • Prior datasets are often artificial, omit commonsense reasoning, or remain solvable with rule-based methods, motivating a benchmark with natural text and hidden intermediate structure.Examples include bAbI, BigTOM (Gandhi et al., 2023), ToMi, RuleTakers (Clark et al., 2020), ProntoQA (Saparov & He, 2023; Saparov et al., 2023), and CLUTRR (Sinha et al., 2019).Source: §2 · p. 2

Related work

  • Existing multistep datasets use isolated facts or explicit deduction, whereas commonsense datasets often lack multistep reasoning and complex narrative grounding.EntailmentBank (Dalvi et al., 2021), Everyday Norms: Why Not (Sprague et al., 2022), and BoardgameQA (Kazemi et al., 2023b) are described as insufficiently narrative-grounded, while commonsense datasets omit multistep reasoning.Source: §2 · pp. 2–3

Techniques

  • Prior search-loop, tool-assisted, and neurosymbolic systems struggle with long natural contexts and soft commonsense reasoning, while prompting methods require extraction, interpretation, and multistep deduction.Search-based systems enumerate facts deductively or abductively, but distributed narrative facts and soft reasoning remain difficult; MuSR is designed to test these limits.Source: §2 · p. 3

Why a synthetic benchmark

  • Synthetic generation is preferred because it scales to harder, longer instances, reduces leakage concerns through regeneration, and separates logical scaffolding from text generation.The benchmark uses GPT-4-generated narratives with hidden facts and construction scaffolding, while human-performance measurement supports their validity as reasoning test cases.Source: §2 · p. 3

Object Placements

Figure 2 depicts partial reasoning trees for three domains, distinguishing gold, story, and commonsense facts and showing how LLM-sampled deductions populate the setup.

Object Placements

  • Figure 2 shows partial reasoning trees containing gold facts F, story facts S(T), and commonsense facts C(T) across three domains.Dotted lines mark incomplete trees.Source: Figure 2 · p. 4
  • Each LLM-sampled deduction yields two scenario facts and one commonsense fact in this setup.Source: Figure 2 · p. 4

3 CREATING MUSR

MuSR instances are generated through a three-stage neurosymbolic pipeline that constructs logical facts, expands them into multistep reasoning trees, and embeds selected facts into natural-language narratives.

3 CREATING MUSR

  • MuSR generation produces tuples of facts, reasoning trees, narratives, questions, and answers, while models generally receive only the narrative and question at test time.The task is to predict each answer a_i from narrative x and question q_i; F and T support generation but are withheld during evaluation.Source: §3 · p. 4

3.1 TREE TEMPLATE CONSTRUCTION

  • Tree Template Construction defines structured facts and templated question-answer pairs, then adds diversity facts that create distinct storylines without determining the answers.The core fact set F satisfies a program Φ(F, q_i) = a_i, whereas additional facts G are sampled from curated lists or LLMs and must appear in the narrative.Source: §3.1 · p. 4

3.2 REASONING TREE COMPLETION

  • Reasoning Tree Completion recursively expands each core fact into depth-controlled trees whose scenario and commonsense leaves require multistep deduction, using validators to block explicit facts and shortcuts.GPT-4 generates the trees; scenario-specific leaves S(T) enter narratives, while commonsense leaves C(T) remain unstated but should be broadly accepted.Source: §3.2 · p. 5

3.3 STORY GENERATION

  • Story Generation uses chaptering to convert answer-specific subsets of scenario leaves into concatenated, optionally smoothed narratives, enabling MuSR stories exceeding 1000 words.Chaptering addresses fact omission in long single-pass generations by prompting GPT-4 with smaller fact lists for each chapter.Source: §3.3 · p. 5

4 MUSR DOMAINS

MuSR covers three natural-language reasoning domains: murder mysteries, object placements, and team allocation. Together, they test physical, social, temporal, observational, theory-of-mind, and constraint reasoning through synthetic reasoning structures rendered as narratives.

4.1 MURDER MYSTERIES: SOCIAL AND PHYSICAL DEDUCTIVE REASONING

  • Murder Mysteries requires identifying the suspect with means, motive, and opportunity while reasoning about social scenarios, physical circumstances, and temporal opportunity.The construction uses two suspects, assigns guilt to one, and expands three facts per suspect into narrative explanations; the innocent suspect receives two guilt-related facts plus an irrelevant suspicious fact.Source: §4.1 · pp. 5–6

4.2 OBJECT PLACEMENTS: OBSERVATIONAL AND THEORY OF MIND REASONING

  • Object Placements tests where a person believes an item is by tracking sequential moves, their observations, and the person’s resulting belief state.Each move records whether each other person saw it, with observation probability c = 0.33 in the experiments, and reasoning trees explain observations using commonsense scenarios.Source: §4.2 · p. 6

4.3 TEAM ALLOCATION: SOCIAL AND CONSTRAINT REASONING

  • Team Allocation selects the highest-scoring assignment of three people to two tasks by combining task skills with pairwise teamwork scores.Skills and relationships use values from 0 to 2, and the optimal assignment is constrained to exceed every alternative by at least 2 points.Source: §4.3 · p. 6

5 EXPERIMENTS

Experiments validate MuSR through dataset-quality checks and human annotation, then benchmark LLMs, prompting strategies, and domain-specific neurosymbolic methods. GPT-4 is the strongest tested LLM but remains below human performance, while construction components and tailored symbolic methods materially affect results.

5.1 DATASET VALIDATION

  • Dataset validation prioritizes end-to-end human solvability over separate fluency, coherence, and commonsense sensibility evaluations.The authors report that GPT-4 stories appear strong on these attributes by inspection but do not formally evaluate them.Source: §5.1 · p. 7
  • The rule-based sanity checks for Murder Mystery and Object Placements perform near random chance, supporting that simple narrative-frequency heuristics do not solve the datasets.The Murder Mystery baseline selects the suspect with the longest chapter, while Object Placements selects the most-mentioned location.Source: §5.1 · p. 7, Table 2 · p. 7
  • Human majority annotation exceeds average individual performance, indicating that three-annotator voting reaches a very high effective ceiling for dataset answers.The evaluation used seven annotators, including authors and unfamiliar undergraduate students, and triply annotated more than 100 instances per domain in aggregate.Source: §5.1 · p. 7, Table 3 · p. 7
  • Chaptering and tree validators improve narrative quality by increasing fact recall, story length, and—especially for Murder Mystery—GPT-4 accuracy, whereas simpler prompting yields short, repetitive, often unsolvable stories.Without chaptering, only 62% of original Murder Mystery reasoning-tree facts are entailed; Team Allocation did not require chaptering or validators.Source: §5.1 · pp. 7–8, Table 4 · p. 8

5.2 BENCHMARKING WITH MUSR

  • GPT-4 performs best among tested LLMs but still underperforms humans on all three MuSR domains.Llama 2 and Vicuna models exceed chance only slightly, and Vicuna surpasses GPT-3.5 on only Team Allocation.Source: Table 5 · p. 8, §5.2 · p. 8
  • The best prompting results use 1-shot or few-shot CoT+, although additional examples are not consistently beneficial and remain below human majority performance.CoT+ augments chain-of-thought with an engineered textual description of the domain reasoning strategy; Few-shot CoT+ uses three examples but reaches GPT-4’s token limit.Source: §5.2 · p. 8, Table 7 · p. 9
  • Domain-specific neurosymbolic methods have mixed results: PAL outperforms end-to-end models on Team Allocation, while decomposed prompting underperforms GPT-4 and SymbolicTOM struggles with natural cross-paragraph references.PAL still falls short of aggregate human performance; SymbolicTOM’s low accuracy is attributed to difficulty selecting entities and actions from less-templated contexts.Source: §5.2 · p. 9, Table 6 · p. 9

6 CONCLUSION

The paper introduces MuSR, a scalable neurosymbolic dataset of natural-language narratives for evaluating complex reasoning, where LLMs remain below human performance on multi-step and commonsense reasoning.

Contributions

  • MuSR combines natural narrative scenarios with a neurosymbolic generation method that scales instance complexity as models improve.Human evaluation and intrinsic validations support the construction method for sufficiently large models.Source: §6 · p. 9

Findings

  • LLMs currently fail to match human performance on multi-step and commonsense reasoning across MuSR’s three domains.The dataset challenges both the largest and smaller language models.Source: §6 · p. 9

Applications

  • MuSR is proposed as a benchmark for LLMs, a benchmark for general neurosymbolic approaches over language, and a procedure for generating harder datasets.Source: §6 · p. 9

7 REPRODUCIBILITY OF MUSR · A MUSR LIMITATIONS · A.1 TREE CONSTRUCTION

MuSR supports reproduction through documented construction procedures, implementation details, and planned public release of data and code. However, its narrative-generation method currently works best with shallow reasoning trees because GPT-4 struggles to produce recursively decomposable facts.

7 REPRODUCIBILITY OF MUSR

  • Sections 3 and 4 provide high-level construction details for reproducing MuSR datasets across domains.Source: §7 · p. 10
  • Appendix G gives each domain’s reasoning strategies, algorithms, and construction prompts verbatim.Source: §7 · p. 10
  • Appendix H documents implementation details, including hyperparameters and model design choices.Source: §7 · p. 10
  • Neurosymbolic evaluation implementations are described in Section 5.2 and further detailed in Appendix E.Source: §7 · p. 10
  • The authors plan to make all data and dataset-generation and evaluation code publicly available in future paper versions.Source: §7 · p. 10

A.1 TREE CONSTRUCTION

  • Shallow reasoning trees of depth one or two produce the best narrative detail because GPT-4 often fails to generate sufficiently complex recursively decomposable facts.Source: §A.1 · p. 15
  • The authors identify prompting and stronger LLMs as potential ways to increase acceptable deduction depth in future work.Source: §A.1 · p. 15

A.2 HUMAN EVALUATION

Human evaluation via Amazon Mechanical Turk was difficult to validate because many workers performed poorly in qualification rounds, and some justifications appeared to be ChatGPT-generated.

A.2 HUMAN EVALUATION

  • Amazon Mechanical Turk validation was unreliable: many workers performed very badly in qualification rounds, while collected justifications were suspected to be written by ChatGPT.These issues undermined confidence in the quality of workers’ judgments.Source: §A.2 · p. 15

B DATASET FEATURES EXPLAINED

MuSR is characterized by natural LLM-prompted contexts, omitted commonsense facts, multistep reasoning, explicit reasoning trees, and resistance to template-based solutions.

Natural Text

  • MuSR produces natural contexts from LLM-prompted language without templating, unlike datasets built from predefined templates or specialized premises.EntailmentBank and ENWN use specialized “premises,” while SocialIQA’s questions and answers may not always reflect natural English.Source: B DATASET FEATURES EXPLAINED · p. 15

Commonsense

  • MuSR omits selected commonsense facts, requiring users to draw on inherent knowledge to solve its problems.This contrasts with EntailmentBank and RuleTakers, which provide all necessary facts in the input.Source: B DATASET FEATURES EXPLAINED · p. 15

Multistep

  • MuSR requires multistep reasoning in which combined premises yield intermediate conclusions that support the final inference.Its design requires users to recreate, or approximate, the reasoning tree used to construct each question.Source: B DATASET FEATURES EXPLAINED · p. 15

Intermediate Structures

  • MuSR provides the reasoning trees underlying each example, giving questions explicit intermediate structures that can assist deduction.True Detective, by contrast, was human-written and lacks such an intermediate structure.Source: B DATASET FEATURES EXPLAINED · p. 15

Not solvable with rules

  • MuSR lacks easily identifiable textual patterns, making it resistant to oversimplified rule-based or template-based solutions.This contrasts with templated datasets such as bAbI and ToMi, whose patterns may be reverse-engineered.Source: B DATASET FEATURES EXPLAINED · p. 15

C CREATING MUSR WITH OTHER MODELS

The authors test whether models weaker than GPT-4 can generate MuSR examples, finding that GPT-3.5-turbo can produce usable mysteries with substantial prompting support, whereas Llama2-70B-Chat and Mixtral cannot complete the required deductions. Persistent reasoning flaws in GPT-3.5-turbo outputs motivate using the strongest available LLMs for dataset construction.

GPT-3.5-turbo generation

  • For weaker models to create examples approaching GPT-4’s quality, researchers had to make minor prompt edits, add detailed self-refinement prompts, iteratively increase temperature, and increase retries.Source: C CREATING MUSR WITH OTHER MODELS · p. 16
  • GPT-3.5-turbo generated 50 murder mysteries whose CoT+ and 1-Shot CoT+ performance was similar to the main MuSR dataset.The comparison is reported for the 50 generated mysteries in Table 8.Source: C CREATING MUSR WITH OTHER MODELS · p. 16

GPT-3.5-turbo limitations

  • Despite using GPT-4’s workflow, many GPT-3.5-turbo examples contained major reasoning-tree flaws, including hallucinated or invalid deductions judged valid by the workflow.Source: C CREATING MUSR WITH OTHER MODELS · p. 16

Conclusion

  • The authors therefore consider using the strongest available LLMs best practice for generating datasets like MuSR, while stronger validation models or further prompt engineering may help smaller models.Source: C CREATING MUSR WITH OTHER MODELS · p. 17

D QUALITATIVE ERROR ANALYSIS

A hand-annotated review of GPT-4 and GPT-3.5-turbo reasoning traces on MuSR problems identified recurring failures in answer formation, instruction adherence, and logical validity. These errors included biased evidence selection, contradictions with prompt constraints, hallucinations, and unsupported deductions.

  • The analysis examined five examples from each domain by manually annotating GPT-4 and GPT-3.5-turbo chains-of-thought for errors.The examples were used to identify major error categories in GPT models solving MuSR problems.Source: D QUALITATIVE ERROR ANALYSIS · p. 17
  • Models frequently pre-committed to answers, either stating them before reasoning or silently selecting only evidence supporting one option.This biased subsequent reasoning and omitted relevant facts for alternatives.Source: D QUALITATIVE ERROR ANALYSIS · p. 17
  • Models often ignored prompt instructions by choosing suspects based only on motive or allowing collaboration between people assigned different jobs.These responses violated the stated definitions and allocation constraints.Source: D QUALITATIVE ERROR ANALYSIS · p. 17
  • Hallucinations and invalid logic included invented locations or actions, confused entity relations, and unsupported deductions that sometimes contradicted the model’s earlier reasoning.Such inconsistencies could produce answers that did not align with the reasoning trace.Source: D QUALITATIVE ERROR ANALYSIS · p. 17

E STRUCTURED BASELINE IMPLEMENTATION DETAILS … E.3 PAL

The structured baselines adapt Decomposed Prompting, SymbolicTOM, and PAL to the Murder Mystery, Object Placements, and Team Allocation domains, respectively. PAL is evaluated in zero-shot and one-shot settings, with one-shot demonstrations improving performance over zero-shot prompting.

E.1 DECOMPOSED PROMPTING

  • Decomposed Prompting targets Murder Mystery by using fixed prompts for means, motive, and opportunity, whose outputs are aggregated into the final answer.The Decomposer Prompt stage is omitted because all mysteries share this high-level logical procedure.Source: §E.1 · p. 17
  • When both suspects satisfy the same number of criteria, Decomposed Prompting randomly guesses between them.Source: §E.1 · p. 17

E.2 SYMBOLICTOM

  • SymbolicTOM is evaluated on Object Placements using the authors’ implementation, with graph states queried on-the-fly through GPT-3.5 rather than precomputed.Source: §E.2 · p. 18
  • For SymbolicTOM, abstentions are resolved by randomly sampling an answer choice, and the dataset is converted to its expected ToMI format through simple manipulation.Source: §E.2 · p. 18

E.3 PAL

  • PAL evaluates Team Allocation by prompting LLMs to generate Python programs, executing them with the Python interpreter, and testing both zero-shot and one-shot settings.Source: §E.3 · p. 18
  • The zero-shot PAL prompt specifies variable assignment for individual skills, pairwise teamwork, and option-score computation, while one-shot adds a demonstration and performs better.Source: §E.3 · p. 18

F DATASET EXAMPLES · F.1 MURDER MYSTERIES

This section presents murder-mystery examples as narrative reasoning tasks requiring suspects to be evaluated by their means, motive, and opportunity. Their reasoning trees illustrate how story facts and commonsense knowledge support step-by-step conclusions and a final selected answer.

F.1 MURDER MYSTERIES

  • The first murder-mystery narrative supplies the evidence used by the tree: Mack is killed by nunchaku at a bungee-jumping site, while Ana and Mackenzie each display suspicious links to the victim and location.Ana traveled with Mack and had a conflict over religion; Mackenzie was seen at the site, had nunchaku-related evidence, and resented Mack’s promotion.Source: §F.1 · pp. 18–19
  • The task requires selecting one murderer and explaining the reasoning step by step using means, motive, and opportunity, ending with a formatted answer.Suspects may have two criteria without being guilty, while the preferred choice is the suspect for whom all three are most clearly established.Source: §F.1 · pp. 19–20
  • Example 1 identifies Mackenzie as the murderer because the reasoning tree establishes his nunchaku access and proficiency, presence at the crime scene, and jealousy-driven motive.The tree combines story facts with commonsense deductions linking martial-arts training and weapon possession to means, attendance and prior altercations to opportunity, and the lost promotion to motive.Source: §F.1 · p. 20
  • The same reasoning tree gives Ana an opportunity and a possible motive through traveling with Mack, shared access to the bungee-jumping site, religious conflict, and Mack’s ridicule of her faith.Ana’s obsessive car cleaning is additionally marked as suspicious and connected to the possibility of hiding or removing evidence.Source: §F.1 · pp. 20–21
  • Example 2 shifts to a casino murder in which Timothy is killed with a sai and Detective Winston investigates Rosemary and Harry.Rosemary has relevant kitchen and antique-weapon experience plus hostility toward Timothy, while Harry has sai training, gambling debts to Timothy, casino presence, and a recent argument with him.Source: §F.1 · pp. 21–22
  • The task requires selecting one murderer and explaining the reasoning step by step using motive, means, and opportunity, with a final formatted answer.If both suspects satisfy all three criteria, choose the one for whom they are best established; otherwise choose the suspect with the clearest case.Source: §F.1 · p. 23
  • Harry’s reasoning tree establishes motive, means, and opportunity through his weapon expertise, casino access, presence near the crime, gambling debt, and fear of exposure.The tree concludes that Harry is the murderer based on martial-arts proficiency with a sai, familiarity with the casino, and financial pressure from Timothy’s threatened disclosure.Source: §F.1 · pp. 23–24
  • Rosemary’s reasoning tree establishes motive and means through ethnic hostility toward Timothy, threats, access to sais and other blades, and professional knife skills.Her unexplained anger, refusal to answer questions, and unprovoked violent behavior are additionally presented as suspicious.Source: §F.1 · p. 24

F.2 OBJECT PLACEMENTS … G.4 TEAM ALLOCATION

This section presents narrative reasoning tasks and their neurosymbolic generation procedures for tracking beliefs about object locations and allocating people to team tasks. It describes how structured facts, movements, observations, skills, relationships, and entailment trees are transformed into constrained natural-language stories that support logically deduced conclusions.

F.2 OBJECT PLACEMENTS

  • The studio example illustrates belief divergence: Danny sees the earphones at the producer’s desk, while his blocked view and distraction prevent him from seeing Emma move them there.The reasoning tree also distinguishes observers who see or miss notebook and earphone movements based on line of sight, location, and attention.Source: §F.2 · pp. 25–26
  • Object-placement questions require tracking each person’s beliefs over time, updating them when they observe a move and otherwise retaining the last location they observed.Observation depends on seeing the destination without being too distracted; blocked views, separate locations, and focused tasks can prevent belief updates.Source: §F.2 · p. 25

F.3 TEAM ALLOCATION

  • The team-allocation task assigns three people to Animal Caretaker and Exhibit Cleaner roles by combining task-specific skill levels with interpersonal compatibility.Each person is characterized through animal comfort, cleaning ability, fears, allergies, and relationships that affect assignment quality.Source: §F.3 · pp. 28–29
  • Because one task receives two people, the assignment must account for teamwork quality: a strong teammate does not necessarily compensate for a bad worker without effective collaboration.The objective is to choose the single assignment that completes both tasks as effectively as possible.Source: §F.3 · p. 29
  • Team-allocation instances require choosing a single assignment that maximizes individual skills and teamwork across tasks, where a weak teammate may not benefit from a strong one without effective cooperation.Examples derive task abilities and pairwise compatibility from story facts and commonsense rules, such as assigning poetry scoring based on subject knowledge and objectivity.Source: §F.3 · pp. 31–32

G.1 TREE CONSTRUCTION ALGORITHM

  • The tree-construction algorithm recursively prompts a language model to expand each child, validates the generated children, and continues until reaching the maximum depth.The tree is expanded in place through recursive calls after validation.Source: §G.1 · p. 32

G.2 MURDER MYSTERY

  • Murder-mystery trees require each deduction to follow logically from relevant story facts and commonsense rules, with means, motive, and opportunity jointly supporting a suspect conclusion.Prompts distinguish character-, place-, or object-specific story facts from generally agreed commonsense rules, while generated chapters present evidence through detective investigation without stating deductions directly.Source: §G.2 · pp. 32, 33, 35
  • Murder-mystery narratives are written from a detective’s perspective while withholding explicit deductions, suspect MMO labels, and direct murderer identification.Generation rules require clues to be presented through ordinary detective activities without stating or hinting at deduced facts, allowing readers to perform the puzzle reasoning.Source: §G.2 · pp. 35–36
  • Murder mysteries assign each suspect means, motive, and opportunity facts, contrasting one murderer with innocent suspects who receive suspicious distractor facts.The generator samples scenario and suspect information, constructs gold facts, and creates contrastive mysteries by changing the murderer while reusing most reasoning trees.Source: §G.2 · p. 37
  • Validators improve murder-mystery validity by rejecting deductions that leak other MMO concepts and checking that every scenario-specific fact is entailed by the generated story.A story is rewritten when the validator finds an unentailed fact, while suspicious facts help balance narrative length without changing the ground-truth reasoning.Source: §G.2 · p. 38

G.3 OBJECT PLACEMENTS

  • Object-placement scenarios generate people, tangible movable items, locations, goals, and plausible moves while adding a scene-relevant but task-irrelevant item and enforcing distinct If- and Then-persons.The narrative tracks changing object locations and supports later questions about world state and who observed events.Source: §G.3 · pp. 38, 40
  • Object-placement reasoning uses entailment trees whose facts combine without contradiction to prove whether a person saw an event, while avoiding explicit seeing claims, untracked placements, and item reuse.Trees distinguish story facts, commonsense knowledge, and recursively constructed complex facts, and constrain deductions to the relevant observer.Source: §G.3 · p. 40
  • The object-placement reasoning process uses single-step entailment templates, role- and motivation-sensitive deductions, and validation that excludes key items or locations from deductions.These constraints aim to keep deductions meaningful, prevent vacuous solutions, and preserve whether characters see or fail to see events.Source: §G.3 · pp. 41, 42, 46
  • Object-placement narratives enforce controlled generation by stating initial item locations and shared awareness, then describing movements and observations without adding unsupported information.Prompts require the story to include every listed item and location, indicate that people know the locations, and restrict event descriptions to the supplied facts.Source: §G.3 · pp. 42–43
  • Object Placements samples two items, three moves, and probabilistic observations to create fact sets in which one item moves twice.Each non-moving person has a 0.33 chance of seeing each move, and the resulting facts are grouped into the move before reasoning-tree construction.Source: §G.3 · p. 46

G.4 TEAM ALLOCATION

  • Team Allocation constructs scenarios with three people, two tasks, and two unique, orthogonal skills, with each skill associated with one task.The prompt uses settings such as assigning workers to cashier and barista roles in a coffee bar or caretakers and cleaners in a zoo.Source: §G.4 · p. 46
  • Team Allocation avoids embedding titles or task-relevant abilities in people’s names so assignments cannot be inferred directly from naming.The prompt explicitly prohibits names such as “Dr. Bob” when the title would imply responsibility for a particular task.Source: §G.4 · p. 46
  • After facts are assembled, they are passed to Reasoning Tree Construction, and Team Allocation requires no validators for either tree construction or story generation.The method models skills through personal experiences and teamwork through prior social interactions.Source: §G.4 · pp. 46, 51
  • Reasoning trees recursively combine story facts, commonsense knowledge, and complex facts so each set of premises entails its parent conclusion without contradiction.Each fact must be crucial to the deduction, and omitting one should prevent the conclusion from being entailed.Source: §G.4 · p. 47
  • Story generation includes every supplied fact in a coherent, engaging narrative that introduces the people and tasks while leaving the optimal assignment for readers to infer.The generated story describes candidates’ abilities, experiences, preferences, and interpersonal interactions rather than stating the assignment directly.Source: §G.4 · pp. 49–50
  • The Tree Template Construction stage builds matrix M from two skill-ability columns and three relationship-score columns, then converts these values into facts for reasoning.Skill labels are “bad,” “okay,” or “good,” while relationship labels are “badly,” “okay,” or “well.”Source: §G.4 · p. 51

H IMPLEMENTATION DETAILS, API COST · H.1 IMPLEMENTATION DETAILS: CREATING AND EVALUATING MUSR · H.2 API COSTS AND TIMES

MuSR is created with GPT-4 under default sampling settings and domain-specific reasoning-tree constraints that promote controlled diversity. Evaluation uses GPT-4 and GPT-3.5-turbo endpoints or quantized local models, while Table 9 estimates per-domain evaluation costs and runtimes for GPT-4 with CoT+ 1-Shot.

H.1 IMPLEMENTATION DETAILS: CREATING AND EVALUATING MUSR

  • MuSR creation uses GPT-4 with default parameters, including temperature and top-p both set to 1.0.Source: §H.1 · p. 51
  • Murder Mystery generation uses reasoning trees of maximum depth 4 with two suspects, sampling story facts and roles to diversify deductions.Source: §H.1 · p. 51
  • Object Placements uses depth-3 reasoning trees with three moves, two items, a 33% observation chance, and sampled scenarios, names, moves, and motivations.Source: §H.1 · p. 51
  • Team Allocation uses maximum reasoning depth 2 and samples scenarios, tasks, and people’s names for diversity.Source: §H.1 · p. 51
  • Evaluation uses the “gpt-4” and “gpt-3.5-turbo” chat endpoints, Hugging Face implementations for Llama2 and Vicuna, bitsandbytes quantization, unchanged inference parameters, and 4xNVIDIA RTX A6000 48GB cards for local models.The authors report no significant performance increases for some smaller models without quantization.Source: §H.1 · p. 51

H.2 API COSTS AND TIMES

  • Table 9 reports average per-domain evaluation costs and runtimes using GPT-4 with the CoT+ 1-Shot prompt variant.Source: Table 9 · p. 52, §H.2 · p. 52

I EVALUATION PROMPTS AND OUTPUTS

This section describes evaluation prompts requiring step-by-step reasoning and final answer choices across murder-mystery, assignment optimization, team-allocation, and object-location tasks. It also presents GPT-4’s evaluations, including an incorrect personnel assignment and a correct inference about where to search for the earphones.

I.1 EVAL PROMPTS

  • Murder Mystery CoT+ asks models to identify the most likely murderer using motive, means, and opportunity, then provide step-by-step reasoning and a final answer choice.If both suspects satisfy all three criteria, the prompt instructs choosing the suspect for whom they are best established; otherwise, choose the most clearly supported suspect.Source: §I.1 · p. 52
  • Object Placements CoT+ asks where a person would look for an object by tracking observed movements, visibility, and distraction throughout the story.If a person does not observe an object moving, they retain the belief that it remains in its last observed location.Source: §I.1 · p. 52
  • Team Allocation CoT+ asks for the unique assignment maximizing task effectiveness from individual skill levels and pairwise teamwork, with one task requiring two people.The prompt represents people as great, acceptable, or bad at tasks and notes that a strong partner does not necessarily offset a weak teammate without good cooperation.Source: §I.1 · p. 53
  • Team Allocation PAL operationalizes the assignment by encoding skills and cooperation as scores from 1 to 3, summing option scores, and returning the highest-scoring choice through a Python function.The prompt requests supporting story excerpts in comments for individual and cooperation scores.Source: §I.1 · pp. 53–54

I.2 INCORRECT EVALUATIONS FROM GPT-4

  • The murder-mystery example contrasts Andrew’s bomb-disposal expertise and active explosives with Ervin’s military demolition training, financial motive, rink presence, and reportedly inactive grenade collection.These narrative details supplied the evidence used in the competing motive, means, and opportunity assessment.Source: §I.2 · pp. 54–55
  • In a GPT-4 murder-mystery error, Andrew and Ervin were both judged to have motive, means, and opportunity, but Andrew’s case was considered better substantiated.Andrew’s evidence included explosives, knowledge of Otis’s schedule, and a lifestyle conducive to acting without witnesses, whereas Ervin’s grenades were described as inactive.Source: §I.2 · p. 55
  • A separate team-allocation example assigns Olivia, Alex, and Mia between Animal Caretaker and Exhibit Cleaner using animal comfort, cleaning ability, allergies, fears, and interpersonal compatibility.The example describes Alex’s discomfort with large animals, Mia’s cleaning strength and animal-related fears, Olivia’s allergies and wild-animal fear, and their relationship dynamics.Source: §I.2 · p. 56
  • The assignment prompt requires choosing one allocation that maximizes individual skills and teamwork across two tasks, with one task receiving two people.People are characterized as great, acceptable, or bad at tasks, while team effectiveness can also be great, acceptable, or bad.Source: §I.2 · p. 56
  • The prompt explicitly requires step-by-step reasoning followed by a final answer containing the selected choice number.This output format is specified for the personnel-allocation question.Source: §I.2 · p. 57
  • The reasoning evaluates each worker through task preferences, fears, allergies, and interpersonal relationships, including Mia’s cleanliness and conflicts with Olivia.Alex and Mia are described as having a strong relationship, while discomfort around animals and strained relationships constrain assignments.Source: §I.2 · p. 57
  • The cited response selects option 3: Mia is assigned as Animal Caretaker, while Alex and Olivia are assigned as Exhibit Cleaners; these passages do not establish that this selection is incorrect.The rationale cites Mia’s love for cleanliness, teamwork and communication, strained relationships, and limited animal interaction in exhibit-cleaning roles.Source: §I.2 · p. 57
  • The object-placement prompt asks where Danny believes the earphones are after tracking movements, visibility, and distraction through the story.If Danny does not observe a move, he retains the object’s last observed location.Source: §I.2 · p. 58
  • GPT-4 correctly concludes that Danny would search the recording booth because he placed the earphones there and did not see Emma move them to the producer’s desk.Danny’s lack of visual access to the booth supports retaining the recording booth as his belief about the earphones’ location.Source: §I.2 · p. 59
Loading 2310.16049v2…