Elamur Research⌕
☰
home / papers / 2023 / MuSR: Testing the Limits of Chain-of-thought with Multistep Soft Reasoning

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

Paper · 2023 · Zayne Sprague, Xi Ye, Kaj Bostrom et al.

Summary

Existing reasoning benchmarks for LLMs tend to fall into two camps. Some use artificial text that rule-based solvers can crack. Others involve commonsense but only one or two inference steps. MuSR (Multistep Soft Reasoning) targets the gap between them: long natural-language narratives whose solution requires both commonsense interpretation and multi-step deliberation.

The authors build the data with a neurosymbolic pipeline in three stages:

  • sample a set of gold facts that determine the answer;
  • have an LLM recursively expand them into a reasoning tree of story facts plus commonsense rules;
  • write the narrative chunk by chunk with GPT-4, re-generating until each chunk is checked to contain its assigned facts.

The resulting stories, such as murder mysteries of about 1000 words, defeat GPT-4 across many chain-of-thought variants and neurosymbolic solvers, while human annotators solve them with high accuracy. Because reasoning structure is separated from text generation, the benchmark can be regenerated at higher difficulty as models improve, which also reduces test-set leakage concerns.

Key points

  • MuSR has 756 examples across three domains:
    • murder mysteries: who has means, motive and opportunity;
    • object placement: theory-of-mind questions about where a character believes an item is;
    • team allocation: assigning people to tasks to maximize efficiency.
  • Each instance comes with ground-truth intermediate structure, a tree linking gold facts, story facts and commonsense facts. Unlike RuleTakers, CLUTRR or ProntoQA, it cannot be solved by rules.
  • Asking GPT-4 to write a mystery in one shot produced homogeneous, sometimes inconsistent stories. This motivated the tree-grounded, validated generation loop.
  • Evaluated models include GPT-4, Llama 2 and Vicuna, tested with several chain-of-thought prompting variants and existing neurosymbolic methods. Clear gaps to human performance remain.
  • Compared with the human-authored True Detective dataset, the synthetic design is scalable, renewable and less prone to contamination. Code and data: github.com/Zayne-Sprague/MuSR (ICLR 2024 Spotlight).

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓The University of Texas at AustinAustin · United States119 works · 57,950 citations

 Fields, topics and concepts

📚 Shelves 6The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksArtificial Intelligence · 17,965 worksArts and Humanities · 17,450 worksLanguage and Linguistics · 17,296 worksSocial Sciences · 1,954 worksPolitical Science and International Relations · 206 works

🧭 Topics 1Research subjects and languages the work is about.Reasoning · 1,685 works

Cite

Cite as Zayne Sprague, Xi Ye, Kaj Bostrom, Swarat Chaudhuri and Greg Durrett. 2023. MuSR: Testing the Limits of Chain-of-thought with Multistep Soft Reasoning. arXiv:2310.16049 · ICLR 2024 (Spotlight).

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.2310.16049 · arXiv 2310.16049

@misc{sprague2023musr,
  title = {{MuSR: Testing the Limits of Chain-of-thought with Multistep Soft Reasoning}},
  author = {Zayne Sprague, Xi Ye, Kaj Bostrom, Swarat Chaudhuri and Greg Durrett},
  year = {2023},
  doi = {10.48550/arxiv.2310.16049},
  eprint = {2310.16049},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2310.16049}
}

References

48 references, 26 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Yonatan Bisk, Rowan Zellers, Ronan Le Bras, Jianfeng Gao, and Yejin Choi. PIQA: Reasoning about Physical Commonsense in Natural Language. In Proceedings of the Conference on Artificial Intelligence (AAAI), 2020.
  2. Kaj Bostrom, Zayne Sprague, Swarat Chaudhuri, and Greg Durrett. Natural language deduction through search over statement compositions. In Findings of the Association for Computational Linguistics: EMNLP 2022, pp. 4871–4883, Abu Dhabi, United Arab Emirates, December 2022. Association for Computationa… find
  3. Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chri… find
  4. Curran Associates, Inc., 2020. URL https://proceedings.neurips.cc/paper_files/paper/2020/ file/1457c0d6bfcb4967418bfb8ac142f64a-Paper.pdf. ↗
  5. Wei-Lin Chiang, Zhuohan Li, Zi Lin, Ying Sheng, Zhanghao Wu, Hao Zhang, Lianmin Zheng, Siyuan Zhuang, Yonghao Zhuang, Joseph E. Gonzalez, Ion Stoica, and Eric P. Xing. Vicuna: An Open-Source Chatbot Impressing GPT-4 with 90%* ChatGPT Quality, March 2023. URL https://lmsys.org/blog/2023-03-30-vicuna/… ↗
  6. Peter Clark, Oyvind Tafjord, and Kyle Richardson. Transformers as soft reasoners over language. In International Joint Conference on Artificial Intelligence, 2020. URL https://api.semanticscholar.org/CorpusID:211126663. ↗
  7. Antonia Creswell, Murray Shanahan, and Irina Higgins. Selection-inference: Exploiting large language models for interpretable logical reasoning. In The Eleventh International Conference on Learning Representations, 2023. URL https://openreview.net/forum?id= 3Pf3Wg6o-A4. ↗
  8. Bhavana Dalvi, Peter Jansen, Oyvind Tafjord, Zhengnan Xie, Hannah Smith, Leighanna Pipatanangkura, and Peter Clark. Explaining answers with entailment trees. EMNLP, 2021.
  9. Maksym Del and Mark Fishel. True Detective: A Deep Abductive Reasoning Benchmark Undoable for GPT-3 and Challenging for GPT-4. In STARSEM, 2022. URL https://api.semanticscholar.org/CorpusID:259064331. ↗
  10. Tim Dettmers, Mike Lewis, Sam Shleifer, and Luke Zettlemoyer. 8-bit optimizers via block-wise quantization. 9th International Conference on Learning Representations, ICLR, 2022.
  11. Nouha Dziri, Ximing Lu, Melanie Sclar, Xiang Lorraine Li, Liwei Jiang, Bill Yuchen Lin, Peter West, Chandra Bhagavatula, Ronan Le Bras, Jena D. Hwang, Soumya Sanyal, Sean Welleck, Xiang Ren, Allyson Ettinger, Zaid Harchaoui, and Yejin Choi. Faith and Fate: Limits of Transformers on Compositionality.…
  12. Lea Frermann, Shay B. Cohen, and Mirella Lapata. Whodunnit? crime drama as a case for natural language understanding. Transactions of the Association for Computational Linguistics, 6:1–15, 2018. doi: 10.1162/tacl a 00001. URL https://aclanthology.org/Q18-1001. ↗
  13. Kanishk Gandhi, Jan-Philipp Fränken, Tobias Gerstenberg, and Noah D Goodman. Understanding social reasoning in language models with language models. arXiv preprint arXiv:2306.15448, 2023. find
  14. Luyu Gao, Aman Madaan, Shuyan Zhou, Uri Alon, Pengfei Liu, Yiming Yang, Jamie Callan, and Graham Neubig. PAL: Program-aided Language Models. arXiv preprint arXiv:2211.10435, 2022. find
  15. Mor Geva, Daniel Khashabi, Elad Segal, Tushar Khot, Dan Roth, and Jonathan Berant. Did Aristotle use a laptop? A question answering benchmark with implicit reasoning strategies. Transactions of the Association for Computational Linguistics, 9:346–361, February 2021. ISSN 2307-387X. doi: 10.1162/tacl… find
  16. Ruixin Hong, Hongming Zhang, Xintong Yu, and Changshui Zhang. METGEN: A module-based entailment tree generation framework for answer explanation. In Findings of the Association for Computational Linguistics: NAACL 2022, pp. 1887–1905, Seattle, United States, July 2022. Association for Computational… find
  17. Albert Q. Jiang, Alexandre Sablayrolles, Antoine Roux, Arthur Mensch, Blanche Savary, Chris Bamford, Devendra Singh Chaplot, Diego de Las Casas, Emma Bou Hanna, Florian Bressand, Gianna Lengyel, Guillaume Bour, Guillaume Lample, L’elio Renard Lavaud, Lucile Saulnier, Marie-Anne Lachaux, Pierre Stock… find
  18. Jaehun Jung, Lianhui Qin, Sean Welleck, Faeze Brahman, Chandra Bhagavatula, Ronan Le Bras, and Yejin Choi. Maieutic prompting: Logically consistent reasoning with recursive explanations. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pp. 1266–1279, Abu Dha…
  19. Mehran Kazemi, Najoung Kim, Deepti Bhatia, Xin Xu, and Deepak Ramachandran. LAM-BADA: Backward chaining for automated reasoning in natural language. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 6547–6568, Toronto, Canada, Jul…
  20. Mehran Kazemi, Quan Yuan, Deepti Bhatia, Najoung Kim, Xin Xu, Vaiva Imbrasaite, and Deepak Ramachandran. BoardgameQA: A Dataset for Natural Language Reasoning with Contradictory Information. arXiv preprint arXiv:2306.07934, 2023b. — [arXiv:2306.07934](https://arxiv.org/abs/2306.07934) find
  21. Tushar Khot, Harsh Trivedi, Matthew Finlayson, Yao Fu, Kyle Richardson, Peter Clark, and Ashish Sabharwal. Decomposed prompting: A modular approach for solving complex tasks. In The Eleventh International Conference on Learning Representations, 2023. URL https://openreview.net/forum?id=_nGgzQjzaRy. ↗
  22. Matthew Le, Y-Lan Boureau, and Maximilian Nickel. Revisiting the evaluation of theory of mind through question answering. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)… find
  23. Qing Lyu, Shreya Havaldar, Adam Stein, Li Zhang, Delip Rao, Eric Wong, Marianna Apidianaki, and Chris Callison-Burch. Faithful chain-of-thought reasoning. arXiv preprint arXiv:2301.13379, 2023.
  24. OpenAI. GPT-4 Technical Report. ArXiv, abs/2303.08774, 2023. semanticscholar.org/CorpusID:257532815.
  25. URL https://api. Liangming Pan, Alon Albalak, Xinyi Wang, and William Yang Wang. Logic-LM: Empowering Large Language Models with Symbolic Solvers for Faithful Logical Reasoning. ArXiv, abs/2305.12295, 2023. URL https://api.semanticscholar.org/ CorpusID:258833332. ↗
  26. Gabriel Poesia, Kanishk Gandhi, E. Zelikman, and Noah D. Goodman. Certified Reasoning with Language Models. ArXiv, abs/2306.04031, 2023. URL https://api.semanticscholar.org/CorpusID:259095869. ↗
  27. Maarten Sap, Hannah Rashkin, Derek Chen, Ronan Le Bras, and Yejin Choi. Social IQa: Commonsense reasoning about social interactions. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EM… find
  28. Abulhair Saparov and He He. Language models are greedy reasoners: A systematic formal analysis of chain-of-thought. In The Eleventh International Conference on Learning Representations, 2023. URL https://openreview.net/forum?id=qFVVBzXxR2V. ↗
  29. Abulhair Saparov, Richard Yuanzhe Pang, Vishakh Padmakumar, Nitish Joshi, Seyed Mehran Kazemi, Najoung Kim, and He He. Testing the general deductive reasoning capacity of large language models using OOD examples. CoRR, abs/2305.15269, 2023. doi: 10.48550/arXiv. 2305.15269. URL https://doi.org/10.485…
  30. Timo Schick, Jane Dwivedi-Yu, Roberto Dessi, Roberta Raileanu, Maria Lomeli, Luke Zettlemoyer, Nicola Cancedda, and Thomas Scialom. Toolformer: Language models can teach themselves to use tools. 2023.
  31. Melanie Sclar, Sachin Kumar, Peter West, Alane Suhr, Yejin Choi, and Yulia Tsvetkov. Minding language models’ (lack of) theory of mind: A plug-and-play multi-character belief tracker. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers),… — Minding Language Models' (Lack of) Theory of Mind: A Plug-and-Play Multi-Character Belief Tracker
  32. Koustuv Sinha, Shagun Sodhani, Jin Dong, Joelle Pineau, and William L. Hamilton. CLUTRR: A Diagnostic Benchmark for Inductive Reasoning from Text. Empirical Methods of Natural Language Processing (EMNLP), 2019. find
  33. Zayne Sprague, Kaj Bostrom, Swarat Chaudhuri, and Greg Durrett. Natural language deduction with incomplete information. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pp. 8230–8258, Abu Dhabi, United Arab Emirates, December 2022. Association for Computatio… find
  34. Alon Talmor, Jonathan Herzig, Nicholas Lourie, and Jonathan Berant. CommonsenseQA: A question answering challenge targeting commonsense knowledge. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume…
  35. Alon Talmor, Ori Yoran, Ronan Le Bras, Chandra Bhagavatula, Yoav Goldberg, Yejin Choi, and Jonathan Berant. CommonsenseQA 2.0: Exposing the limits of AI through gamification. In Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 1), 2021. URL https:…
  36. Xiaojuan Tang, Zilong Zheng, Jiaqi Li, Fanxu Meng, Song-Chun Zhu, Yitao Liang, and Muhan Zhang. Large Language Models are In-Context Semantic Reasoners rather than Symbolic Reasoners. arXiv eprint 2305.14825, 2023.
  37. Hugo Touvron, Louis Martin, Kevin R. Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Daniel M. Bikel, Lukas Blecher, Cristian Cantón Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Bri… — Llama 2: Open Foundation and Fine-Tuned Chat Models
  38. Karthik Valmeekam, Alberto Olmo, Sarath Sreedharan, and Subbarao Kambhampati. Large Language Models Still Can’t Plan (A Benchmark for LLMs on Planning and Reasoning about Change). In Proceedings of the NeurIPS workshop on Foundation Models for Decision Making, 2023. find
  39. Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc V Le, Ed H. Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. In The Eleventh International Conference on Learning Representations, 2023. URL https://openreview.net/forum?id=… ↗
  40. Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. Chain-of-thought prompting elicits reasoning in large language models. Advances in Neural Information Processing Systems, 35:24824–24837, 2022.
  41. Jason Weston, Antoine Bordes, Sumit Chopra, and Tomás Mikolov. Towards AI-Complete Question Answering: A Set of Prerequisite Toy Tasks. In Yoshua Bengio and Yann LeCun (eds.), 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track…
  42. Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Remi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoe… — Transformers: State-of-the-Art Natural Language Processing
  43. Tianci Xue, Ziqi Wang, Zhenhailong Wang, Chi Han, Pengfei Yu, and Heng Ji. RCOT: Detecting and Rectifying Factual Inconsistency in Reasoning by Reversing Chain-of-Thought. ArXiv, abs/2305.11499, 2023. — [arXiv:2305.11499](https://arxiv.org/abs/2305.11499) find
  44. Kevin Yang, Yuandong Tian, Nanyun Peng, and Dan Klein. Re3: Generating longer stories with recursive reprompting and revision. In Yoav Goldberg, Zornitsa Kozareva, and Yue Zhang (eds.), Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pp. 4393–4479, Abu Dhabi,… find
  45. Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of Thoughts: Deliberate problem solving with large language models, 2023. find
  46. Xi Ye and Greg Durrett. The Unreliability of Explanations in Few-shot Prompting for Textual Reasoning. In Advances in Neural Information Processing Systems, 2022.
  47. Xi Ye, Qiaochu Chen, Isil Dillig, and Greg Durrett. Satisfiability-aided language models using declarative prompting. In Proceedings of NeurIPS, 2023. find
  48. Muru Zhang, Ofir Press, William Merrill, Alisa Liu, and Noah A Smith. How language model hallucinations can snowball. arXiv preprint arXiv:2305.13534, 2023.

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/sprague-2023-musr-testing-limits-chain-thought/