Elamur Research
☰
home / papers / 2023 / Logic-LM: Empowering Large Language Models with Symbolic Solvers for Faithful Logical Reasoning

Logic-LM: Empowering Large Language Models with Symbolic Solvers for Faithful Logical Reasoning

Written for the Research library (claude-opus-5-5) from the paper text. Original — arxiv.org/pdf/2305.12295v2

Summary

Large language models can write out step-by-step explanations, but on hard logic problems their final answers often don't follow from the reasoning they produced. Nothing in the model guarantees that its reasoning is sound. Logic-LM addresses this with a neuro-symbolic pipeline that needs no training. First, an LLM uses few-shot in-context learning to translate the natural-language problem and its question into a task-specific symbolic form. Next, a deterministic solver (a logic programming engine, a first-order logic prover, a constraint solver or an SMT/SAT solver) does the actual inference. Finally, an interpreter turns the solver's output back into an answer. If the solver rejects a formulation, its error message goes back to the LLM so it can fix the formulation (self-refinement). The method was tested on five benchmarks: ProofWriter, PrOntoQA, FOLIO, LogicalDeduction and AR-LSAT. It clearly beats both plain prompting and chain-of-thought, and its advantage grows as problems need more reasoning steps. The work shows that when LLMs only translate and solvers do the reasoning, answers become more accurate and easier to check.

Key points

  • On average, Logic-LM scores 39.2% higher than standard prompting and 18.4% higher than chain-of-thought prompting over the five datasets.
  • It covers four problem types, each with a matching solver: deductive reasoning (logic programming with forward/backward chaining), FOL reasoning (FOL prover), constraint satisfaction (constraint optimization) and analytical reasoning (SAT/SMT solver).
  • The self-refinement step uses solver error messages to repair formulations the solver can't run. However, a formulation that runs can still describe the problem incorrectly.
  • In the error analysis, GPT-4 sometimes defines poor predicates, reverses relations such as "above" and "below", and writes ungrammatical FOL formulas.
  • The approach is limited by what each solver can express. Code and data are released at github.com/teacherpeterpan/Logic-LLM.

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

Fields: Mathematics & statistics

Cited by

227 papers of our library cite it (of the 140673 whose bibliographies we read); 5 of them have a page here, 222 not yet.

Cite

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

@misc{pan2023logic,
  title = {{Logic-LM: Empowering Large Language Models with Symbolic Solvers for Faithful Logical Reasoning}},
  author = {Pan, Liangming and Albalak, Alon and Wang, Xinyi and Wang, William Yang},
  year = {2023},
  doi = {10.48550/arxiv.2305.12295},
  eprint = {2305.12295},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2305.12295}
}

References

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

  1. Stephen Bach, Matthias Broecheler, Bert Huang, and Lise Getoor. 2017. Hinge-loss markov random fields and probabilistic soft logic. Journal of Machine Learning Research (JMLR), 18(1):1–67. find
  2. Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared 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 M. Ziegler, Jeffrey Wu, Clemens Winter,… find
  3. Le-Wen Cai, Wang-Zhou Dai, Yu-Xuan Huang, Yu-Feng Li, Stephen H. Muggleton, and Yuan Jiang. 2021. Abductive learning with ground knowledge base. In Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI), pages 1815–1821. find
  4. Wenhu Chen, Xueguang Ma, Xinyi Wang, and William W. Cohen. 2022. Program of thoughts prompting: Disentangling computation from reasoning for numerical reasoning tasks. CoRR, abs/2211.12588. find our card
  5. Xinyun Chen, Maxwell Lin, Nathanael Schärli, and Denny Zhou. 2023. Teaching large language models to self-debug. CoRR, abs/2304.05128. find
  6. Peter Clark, Oyvind Tafjord, and Kyle Richardson. 2020. Transformers as soft reasoners over language. In Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI), pages 3882–3890. find our card
  7. William F Clocksin and Christopher S Mellish. 2003. Programming in PROLOG. Springer Science & Business Media. find
  8. Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman. 2021. Training verifiers to solve math word problems. CoRR, abs/2110.14168. find our card
  9. Leonardo Mendonça de Moura and Nikolaj S. Bjørner. 2008. Z3: an efficient SMT solver. In Proceedings of the 14th International Conference of Tools and Algorithms for the Construction and Analysis of Systems (TACAS), volume 4963 of Lecture Notes in Computer Science, pages 337–340. find
  10. Leonardo Mendonça de Moura, Soonho Kong, Jeremy Avigad, Floris van Doorn, and Jakob von Raumer. 2015. The lean theorem prover (system description). In Proceedings of the 25th International Conference on Automated Deduction (ICAD), volume 9195 of Lecture Notes in Computer Science, pages 378–388. find
  11. Iddo Drori, Sarah Zhang, Reece Shuttleworth, Leonard Tang, Albert Lu, Elizabeth Ke, Kevin Liu, Linda Chen, Sunny Tran, Newman Cheng, et al. 2022. A neural network solves, explains, and generates university math problems by program synthesis and few-shot learning at human level. Proceedings of the Na… find
  12. Herbert B Enderton. 2001. A mathematical introduction to logic. Elsevier. find
  13. Philipp Körner, Michael Leuschel, João Barbosa, Vítor Santos Costa, Verónica Dahl, Manuel V. Hermenegildo, José F. Morales, Jan Wielemaker, Daniel Diaz, and Salvador Abreu. 2022. Fifty years of prolog and beyond. Theory Pract. Log. Program., 22(6):776–858. find
  14. Bruce Frederiksen. 2008. Applying expert system technology to code reuse with pyke. PyCon: Chicago. find
  15. Vipin Kumar. 1992. Algorithms for constraint-satisfaction problems: A survey. AI Mag., 13(1):32– 44. find
  16. Luyu Gao, Aman Madaan, Shuyan Zhou, Uri Alon, Pengfei Liu, Yiming Yang, Jamie Callan, and Graham Neubig. 2023. PAL: program-aided language models. In Proceedings of the International Conference on Machine Learning (ICML), volume 202, pages 10764–10799. find
  17. Angeliki Lazaridou, Elena Gribovskaya, Wojciech Stokowiec, and Nikolai Grigorev. 2022. Internet-augmented language models through few-shot prompting for open-domain question answering. CoRR, abs/2203.05115. find our card
  18. Olga Golovneva, Moya Chen, Spencer Poff, Martin Corredor, Luke Zettlemoyer, Maryam Fazel-Zarandi, and Asli Celikyilmaz. 2023. ROSCOE: A suite of metrics for scoring step-by-step reasoning. In Proceedings of the 11th International Conference on Learning Representations (ICLR). find our card
  19. Nitish Gupta, Kevin Lin, Dan Roth, Sameer Singh, and Matt Gardner. 2020. Neural module networks for reasoning over text. In Proceedings of the 8th International Conference on Learning Representations (ICLR). find
  20. Simeng Han, Hailey Schoelkopf, Yilun Zhao, Zhenting Qi, Martin Riddell, Luke Benson, Lucy Sun, Ekaterina Zubova, Yujie Qiao, Matthew Burtell, David Peng, Jonathan Fan, Yixin Liu, Brian Wong, Malcolm Sailor, Ansong Ni, Linyong Nan, Jungo Kasai, Tao Yu, Rui Zhang, Shafiq R. Joty, Alexander R. Fabbri,… find our card
  21. Percy Liang, Rishi Bommasani, Tony Lee, Dimitris Tsipras, Dilara Soylu, Michihiro Yasunaga, Yian Zhang, Deepak Narayanan, Yuhuai Wu, Ananya Kumar, Benjamin Newman, Binhang Yuan, Bobby Yan, Ce Zhang, Christian Cosgrove, Christopher D. Manning, Christopher Ré, Diana Acosta-Navas, Drew A. Hudson, Eric… find
  22. Bo Liu, Yuqian Jiang, Xiaohan Zhang, Qiang Liu, Shiqi Zhang, Joydeep Biswas, and Peter Stone. 2023a. LLM+P: empowering large language models with optimal planning proficiency. CoRR, abs/2304.11477. find our card
  23. Joy He-Yueya, Gabriel Poesia, Rose E Wang, and Noah D Goodman. 2023. Solving math word problems by combining language models with symbolic solvers. CoRR, abs/2304.09102. find
  24. Hanmeng Liu, Ruoxi Ning, Zhiyang Teng, Jian Liu, Qiji Zhou, and Yue Zhang. 2023b. Evaluating the logical reasoning ability of chatgpt and GPT-4. CoRR, abs/2304.03439. find our card
  25. Jie Huang and Kevin Chen-Chuan Chang. 2023. Towards reasoning in large language models: A survey. In Findings of the 61st Annual Meeting of the Association for Computational Linguistics (ACL), pages 1049–1065. find our card
  26. Qing Lyu, Shreya Havaldar, Adam Stein, Li Zhang, Delip Rao, Eric Wong, Marianna Apidianaki, and Chris Callison-Burch. 2023. Faithful chain-of-thought reasoning. CoRR, abs/2301.13379. find our card
  27. Albert Qiaochu Jiang, Sean Welleck, Jin Peng Zhou, Timothée Lacroix, Jiacheng Liu, Wenda Li, Mateja Jamnik, Guillaume Lample, and Yuhuai Wu. 2023. Draft, sketch, and prove: Guiding formal theorem provers with informal proofs. In Proceedings of the 11th International Conference on Learning Representa… find our card
  28. Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, Sean Welleck, Bodhisattwa Prasad Majumder, Shashank Gupta, Amir Yazdanbakhsh, and Peter Clark. 2023. Self-refine: Iterative refinement with self-feedback. CoR… find
  29. Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. 2022. Large language models are zero-shot reasoners. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS). find our card
  30. Robin Manhaeve, Sebastijan Dumancic, Angelika Kimmig, Thomas Demeester, and Luc De Raedt. 2021. Neural probabilistic logic programming in deep-problog. The Journal of Artificial Intelligence (AIJ), 298:103504. find
  31. Jiayuan Mao, Chuang Gan, Pushmeet Kohli, Joshua B. Tenenbaum, and Jiajun Wu. 2019. The neuro-symbolic concept learner: Interpreting scenes, words, and sentences from natural supervision. In Proceedings of the 7th International Conference on Learning Representations (ICLR). find
  32. Kostas S. Metaxiotis, Dimitris Askounis, and John E. Psarras. 2002. Expert systems in production planning and scheduling: A state-of-the-art survey. Journal of Intelligent Manufacturing, 13(4):253–260. find
  33. Aaron Meurer, Christopher P. Smith, Mateusz Paprocki, Ondrej Certík, Sergey B. Kirpichev, Matthew Rocklin, Amit Kumar, Sergiu Ivanov, Jason Keith Moore, Sartaj Singh, Thilina Rathnayake, Sean Vig, Brian E. Granger, Richard P. Muller, Francesco Bonazzi, Harsh Gupta, Shivam Vats, Fredrik Johansson, Fa… find
  34. Reiichiro Nakano, Jacob Hilton, Suchir Balaji, Jeff Wu, Long Ouyang, Christina Kim, Christopher Hesse, Shantanu Jain, Vineet Kosaraju, William Saunders, Xu Jiang, Karl Cobbe, Tyna Eloundou, Gretchen Krueger, Kevin Button, Matthew Knight, Benjamin Chess, and John Schulman. 2021. Webgpt: Browser-assis… find our card
  35. OpenAI. 2023. GPT-4 technical report. abs/2303.08774. find our card
  36. CoRR, Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul F. Christiano, Jan Leike, and Ryan Lowe.… find
  37. Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul F. Christiano, Jan Leike, and Ryan Lowe. 2022b… find
  38. Lawrence C. Paulson. 1994. Isabelle - A Generic Theorem Prover (with a contribution by T. Nipkow), volume 828 of Lecture Notes in Computer Science. Springer. find
  39. David Poole and Alan K. Mackworth. 2010. Artificial Intelligence - Foundations of Computational Agents. Cambridge University Press. find
  40. Connor Pryor, Charles Dickens, Eriq Augustine, Alon Albalak, William Yang Wang, and Lise Getoor. 2023. Neupsl: Neural probabilistic soft logic. In Proceedings of the 32nd International Joint Conference on Artificial Intelligence (IJCAI), pages 4145–4153. find
  41. Danilo Neves Ribeiro, Shen Wang, Xiaofei Ma, Henghui Zhu, Rui Dong, Deguang Kong, Juliette Burger, Anjelica Ramos, Zhiheng Huang, William Yang Wang, George Karypis, Bing Xiang, and Dan Roth. 2023a. STREET: A multi-task structured reasoning and explanation benchmark. In Proceedings of the Eleventh In… find
  42. Danilo Neves Ribeiro, Shen Wang, Xiaofei Ma, Henry Zhu, Rui Dong, Deguang Kong, Juliette Burger, Anjelica Ramos, William Yang Wang, Zhiheng Huang, George Karypis, Bing Xiang, and Dan Roth. 2023b. STREET: A multi-task structured reasoning and explanation benchmark. In Proceedings of the 11th Internat… find
  43. Matthew Richardson and Pedro M. Domingos. 2006. Markov logic networks. Machine Learning, 62(1-2):107–136. find
  44. John Alan Robinson. 1965. A machine-oriented logic based on the resolution principle. The Journal of the ACM (JACM), 12(1):23–41. find
  45. Abulhair Saparov and He He. 2023. Language models are greedy reasoners: A systematic formal analysis of chain-of-thought. In Proceedings of the 11th International Conference on Learning Representations (ICLR). find our card
  46. Murray Shanahan. 2022. Talking about large language models. CoRR, abs/2212.03551. — [arXiv:2212.03551](https://arxiv.org/abs/2212.03551) find
  47. Yongliang Shen, Kaitao Song, Xu Tan, Dongsheng Li, Weiming Lu, and Yueting Zhuang. 2023. Hugginggpt: Solving AI tasks with chatgpt and its friends in huggingface. CoRR, abs/2303.17580. find our card
  48. Weijia Shi, Sewon Min, Michihiro Yasunaga, Minjoon Seo, Rich James, Mike Lewis, Luke Zettlemoyer, and Wen-tau Yih. 2023. REPLUG: retrieval-augmented black-box language models. CoRR, abs/2301.12652. find our card
  49. Aarohi Srivastava, Abhinav Rastogi, Abhishek Rao, Abu Awal Md Shoeb, Abubakar Abid, Adam Fisch, Adam R. Brown, Adam Santoro, Aditya Gupta, Adrià Garriga-Alonso, Agnieszka Kluska, Aitor Lewkowycz, Akshat Agarwal, Alethea Power, Alex Ray, Alex Warstadt, Alexander W. Kocurek, Ali Safaya, Ali Tazarv, Al… find our card
  50. Emma Strubell, Ananya Ganesh, and Andrew McCallum. 2019. Energy and policy considerations for deep learning in NLP. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics (ACL), pages 3645–3650. find our card
  51. Oyvind Tafjord, Bhavana Dalvi, and Peter Clark. 2021. Proofwriter: Generating implications, proofs, and abductive statements over natural language. In Findings of the 59th Annual Meeting of the Association for Computational Linguistics (ACL), pages 3621–3634. find our card
  52. Oyvind Tafjord, Bhavana Dalvi Mishra, and Peter Clark. 2022. Entailer: Answering questions with faithful and truthful chains of reasoning. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 2078– 2093. find
  53. Jidong Tian, Yitian Li, Wenqing Chen, Liqiang Xiao, Hao He, and Yaohui Jin. 2022. Weakly supervised neural symbolic learning for cognitive tasks. In Proceedings of 36th Conference on Artificial Intelligence (AAAI), pages 5888–5896. find
  54. Xingyao Wang, Sha Li, and Heng Ji. 2022. Code4struct: Code generation for few-shot structured prediction from natural language. CoRR, abs/2210.12810. — [arXiv:2210.12810](https://arxiv.org/abs/2210.12810) find
  55. Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc V. Le, Ed H. Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. 2023. Self-consistency improves chain of thought reasoning in language models. In Proceedings of the 11th International Conference on Learning Representations (ICLR). find our card
  56. Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, Ed H. Chi, Tatsunori Hashimoto, Oriol Vinyals, Percy Liang, Jeff Dean, and William Fedus. 2022a. Emergent abilities of large language models. Transactions on M… find our card
  57. Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Ed H. Chi, Quoc Le, and Denny Zhou. 2022b. Chain of thought prompting elicits reasoning in large language models. CoRR, abs/2201.11903. find our card
  58. Yuhuai Wu, Albert Qiaochu Jiang, Wenda Li, Markus N. Rabe, Charles Staats, Mateja Jamnik, and Christian Szegedy. 2022. Autoformalization with large language models. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS). find our card
  59. Kaiyu Yang, Jia Deng, and Danqi Chen. 2022. Generating natural language proofs with verifier-guided search. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 89–105. find
  60. Xi Ye, Qiaochu Chen, Isil Dillig, and Greg Durrett. 2023. Satisfiability-aided language models using declarative prompting. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS). find
  61. Wanjun Zhong, Siyuan Wang, Duyu Tang, Zenan Xu, Daya Guo, Yining Chen, Jiahai Wang, Jian Yin, Ming Zhou, and Nan Duan. 2022. Analytical reasoning of text. In Findings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (N… find
  62. Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Claire Cui, Olivier Bousquet, Quoc V. Le, and Ed H. Chi. 2023. Least-to-most prompting enables complex reasoning in large language models. In Proceedings of the 11th International Conference on Learning Re… find our card