Elamur Research⌕
☰
home / papers / 2023 / GraphReason: Enhancing Reasoning Capabilities of Large Language Models through A Graph-Based Verification Approach

GraphReason: Enhancing Reasoning Capabilities of Large Language Models through A Graph-Based Verification Approach

Paper · 2023 · Lang Cao

Summary

LLMs prompted with chain-of-thought can solve math word problems, but a single sampled answer is often wrong. Existing output verifiers such as self-consistency voting and the step-aware DIVERSE verifier score each sampled solution on its own and ignore how steps in different solutions relate. GraphReason (Reasoning Graph Verifier) addresses this without retraining the LLM.

The method samples many step-by-step solutions and groups them by final answer. Within each group, it breaks the solutions into steps and merges steps with identical expressions into shared nodes, which produces one reasoning graph per candidate answer. A GNN classifies each graph, and its output is combined with the summed scores of a base verifier. The answer whose graph scores highest is returned.

Using gpt-3.5-turbo outputs on math word problem benchmarks including GSM8K, SVAMP and ASDiv-a, GraphReason slightly beats the strongest prior verifiers. This suggests that modelling links between candidate solutions adds useful signal.

Key points

  • On GSM8K with gpt-3.5-turbo, GraphReason scores 85.7%, compared with 72.7% for greedy decoding, 82.3% for voting, 85.4% for the voting verifier and 85.0% for DIVERSE.
  • Gains over the previous best verifier are small. In the reported per-dataset results, these include 85.1→85.4 on SVAMP and 96.9→97.0 on ASDiv-a. The authors attribute the tiny ASDiv-a gain to its simpler problems.
  • In the ablation, removing the base-verifier solution semantics hurts most (GSM8K 85.7→81.2). Dropping the score sum costs 2.9 points, and dropping the graphs costs 0.3.
  • In a transfer test on 100 GSM8K items, the verifier was still trained only on gpt-3.5-turbo samples:
    • With PaLM-2 it was the best method (78% vs. 77% for the strongest baseline).
    • With gpt-4 it reached 94%, matching plain voting but falling below the 97% of the best baselines.
  • The authors list several limitations: high LLM inference cost, noisy unlabeled chain-of-thought training data, and the restriction to arithmetic reasoning, where merging steps is easier than in other tasks.

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

🎓University of Illinois Urbana-ChampaignUrbana · United States228 works · 74,590 citations

 Fields, topics and concepts

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 19,503 worksArtificial Intelligence · 18,805 worksArts and Humanities · 17,959 worksLanguage and Linguistics · 17,789 worksComputer Vision and Pattern Recognition · 3,621 works

🧭 Topics 2Research subjects and languages the work is about.Language models & pretraining · 4,145 worksReasoning · 1,948 works

Cite

Cite as Lang Cao. 2023. GraphReason: Enhancing Reasoning Capabilities of Large Language Models through A Graph-Based Verification Approach. arXiv:2308.09267.

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

@misc{cao2023graphreason,
  title = {{GraphReason: Enhancing Reasoning Capabilities of Large Language Models through A Graph-Based Verification Approach}},
  author = {Lang Cao},
  year = {2023},
  doi = {10.48550/arxiv.2308.09267},
  eprint = {2308.09267},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2308.09267}
}

References

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

  1. Abien Fred Agarap. 2019. Deep learning using rectified linear units (relu). Preprint, arXiv:1803.08375. — [arXiv:1803.08375](https://arxiv.org/abs/1803.08375) find
  2. Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, Parker Schuh, Kensen Shi, Sasha Tsvyashchenko, Joshua Maynez, Abhishek Rao, Parker Barnes, Yi Tay, Noam Shazeer, Vinodkumar Prabhakaran, Emi… — PaLM: Scaling Language Modeling with Pathways
  3. Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman. 2021a. Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14168.
  4. Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman. 2021b. Training verifiers to solve math word problems. Preprint, arXiv:2110.14168.
  5. Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019. Bert: Pre-training of deep bidirectional transformers for language understanding. Preprint, arXiv:1810.04805.
  6. Mor Geva, Daniel Khashabi, Elad Segal, Tushar Khot, Dan Roth, and Jonathan Berant. 2021. Did Aristotle Use a Laptop? A Question Answering Benchmark with Implicit Reasoning Strategies. Transactions of the Association for Computational Linguistics (TACL). find
  7. Google. 2023. Palm 2 technical report. arXiv:2305.10403.
  8. Preprint, Jie Huang and Kevin Chen-Chuan Chang. 2023. Towards reasoning in large language models: A survey. Preprint, arXiv:2212.10403.
  9. Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. 2023. Large language models are zero-shot reasoners. Preprint, arXiv:2205.11916.
  10. Andrew Lampinen, Ishita Dasgupta, Stephanie Chan, Kory Mathewson, Mh Tessler, Antonia Creswell, James McClelland, Jane Wang, and Felix Hill. 2022a. Can language models learn from explanations in context? In Findings of the Association for Computational Linguistics: EMNLP 2022, pages 537–563, Abu Dha…
  11. Andrew K Lampinen, Ishita Dasgupta, Stephanie CY Chan, Kory Matthewson, Michael Henry Tessler, Antonia Creswell, James L McClelland, Jane X Wang, and Felix Hill. 2022b. Can language models learn from explanations in context? arXiv preprint arXiv:2204.02329.
  12. Yifei Li, Zeqi Lin, Shizhuo Zhang, Qiang Fu, Bei Chen, Jian-Guang Lou, and Weizhu Chen. 2023. Making language models better reasoners with step-aware verifier. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 5315–5333, Toronto…
  13. Zhongli Li, Wenxuan Zhang, Chao Yan, Qingyu Zhou, Chao Li, Hongzhi Liu, and Yunbo Cao. 2022. Seeking patterns, not just memorizing procedures: Contrastive learning for solving math word problems. In Findings of the Association for Computational Linguistics: ACL 2022, pages 2486–2496, Dublin, Ireland… find
  14. Ilya Loshchilov and Frank Hutter. 2019. Decoupled weight decay regularization. Preprint, arXiv:1711.05101. find
  15. Shen-yun Miao, Chao-Chun Liang, and Keh-Yih Su. 2020. A diverse corpus for evaluating and developing english math word problem solvers. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 975–984. find
  16. OpenAI. 2023. Gpt-4 technical report. arXiv:2303.08774.
  17. Preprint, Arkil Patel, Satwik Bhattamishra, and Navin Goyal. 2021. Are NLP models really able to solve simple math word problems? In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 2080–2094, Online…
  18. Siddhant Jayakumar, Elena Buchatskaya, David Budden, Esme Sutherland, Karen Simonyan, Michela Paganini, Laurent Sifre, Lena Martens, Xiang Lorraine Li, Adhiguna Kuncoro, Aida Nematzadeh, Elena Gribovskaya, Domenic Donato, Angeliki Lazaridou, Arthur Mensch, Jean-Baptiste Lespiau, Maria Tsimpoukelli,… find
  19. Koustuv Sinha, Shagun Sodhani, Jin Dong, Joelle Pineau, and William L. Hamilton. 2019. CLUTRR: A diagnostic benchmark for inductive reasoning from text. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Lan… find
  20. Alon Talmor, Jonathan Herzig, Nicholas Lourie, and Jonathan Berant. 2019. 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,…
  21. Karthik Valmeekam, Alberto Olmo, Sarath Sreedharan, and Subbarao Kambhampati. 2023. Large language models still can’t plan (a benchmark for llms on planning and reasoning about change). Preprint, arXiv:2206.10498.
  22. Xinyu Pi, Qian Liu, Bei Chen, Morteza Ziyadi, Zeqi Lin, Qiang Fu, Yan Gao, Jian-Guang Lou, and Weizhu Chen. 2022. Reasoning like program executors. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 761– 779, Abu Dhabi, United Arab Emirates. Association… find
  23. Siyuan Wang, Wanjun Zhong, Duyu Tang, Zhongyu Wei, Zhihao Fan, Daxin Jiang, Ming Zhou, and Nan Duan. 2022. Logic-driven context extension and data augmentation for logical reasoning of text. In Findings of the Association for Computational Linguistics: ACL 2022, pages 1619–1629, Dublin, Ireland. Ass… find
  24. Jack W. Rae, Sebastian Borgeaud, Trevor Cai, Katie Millican, Jordan Hoffmann, Francis Song, John Aslanides, Sarah Henderson, Roman Ring, Susannah Young, Eliza Rutherford, Tom Hennigan, Jacob Menick, Albin Cassirer, Richard Powell, George van den Driessche, Lisa Anne Hendricks, Maribeth Rauh, Po-Sen… — Self-Consistency Improves Chain of Thought Reasoning in Language Models
  25. Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Ed Chi, Quoc Le, and Denny Zhou. 2022. Chain of thought prompting elicits reasoning in large language models. arXiv preprint arXiv:2201.11903.
  26. Zhipeng Xie and Shichao Sun. 2019. A goal-driven tree-structured neural model for math word problems. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19, pages 5299–5305. International Joint Conferences on Artificial Intelligence Organization. find
  27. Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2019. How powerful are graph neural networks? In International Conference on Learning Representations.
  28. Ori Yoran, Alon Talmor, and Jonathan Berant. 2022. Turning tables: Generating examples from semi-structured tables for endowing language models with reasoning skills. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 6016–6031,… find
  29. Dongxiang Zhang, Lei Wang, Luming Zhang, Bing Tian Dai, and Heng Tao Shen. 2019. The gap of semantic parsing: A survey on automatic math word problem solvers. Preprint, arXiv:1808.07290. find
  30. Jipeng Zhang, Lei Wang, Roy Ka-Wei Lee, Yi Bin, Yan Wang, Jie Shao, and Ee-Peng Lim. 2020. Graph-to-tree learning for solving math word problems. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 3928– 3937, Online. Association for Computational Lingui… find
  31. Wayne Xin Zhao, Kun Zhou, Junyi Li, Tianyi Tang, Xiaolei Wang, Yupeng Hou, Yingqian Min, Beichen Zhang, Junjie Zhang, Zican Dong, Yifan Du, Chen Yang, Yushuo Chen, Zhipeng Chen, Jinhao Jiang, Ruiyang Ren, Yifan Li, Xinyu Tang, Zikang Liu, Peiyu Liu, Jian-Yun Nie, and Ji-Rong Wen. 2023. A survey of l…
  32. Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Claire Cui, Olivier Bousquet, Quoc Le, and Ed Chi. 2023. Least-to-most prompting enables complex reasoning in large language models. Preprint, arXiv:2205.10625.

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/cao-2023-graphreason-enhancing-reasoning-capabilities-large/