CoChat
Sign Up
PreprintCited by 556Topic ModelingNatural Language Processing TechniquesAI-based Problem Solving and Planning

Graph of Thoughts: Solving Elaborate Problems with Large Language Models

Open access
Besta, Maciej, Blach, Nils, Kubicek, Ales, Gerstenberger, Robert, Podstawski, Michal, Gianinazzi, Lukas, Gajda, Joanna, Lehmann, Tomasz +3 more·2023·arXiv
DOI 10.48550/arxiv.2308.09687arXiv 2308.09687
Open this paper in CoChat — free accountOpen PDF

Abstract

We introduce Graph of Thoughts (GoT): a framework that advances prompting capabilities in large language models (LLMs) beyond those offered by paradigms such as Chain-of-Thought or Tree of Thoughts (ToT). The key idea and primary advantage of GoT is the ability to model the information generated by an LLM as an arbitrary graph, where units of information ("LLM thoughts") are vertices, and edges correspond to dependencies between these vertices. This approach enables combining arbitrary LLM thoughts into synergistic outcomes, distilling the essence of whole networks of thoughts, or enhancing thoughts using feedback loops. We illustrate that GoT offers advantages over state of the art on different tasks, for example increasing the quality of sorting by 62% over ToT, while simultaneously reducing costs by >31%. We ensure that GoT is extensible with new thought transformations and thus can be used to spearhead new prompting schemes. This work brings the LLM reasoning closer to human thinking or brain mechanisms such as recurrence, both of which form complex networks.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.2308.09687

Cites

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Besta et al. (2023) introduced LLM-based problem-solving with graphs; however, the approach only encompasses LLM prompting schemes without modeling other fundamental capabilities of language agents, such as use of external tools.

    “Besta et al. (2023) introduced LLM-based problem-solving with graphs; however, the approach only encompasses LLM prompting schemes without modeling other fundamental capabilities of language agents, such as use of external tools.”

    From Language Agents as Optimizable Graphs (2024) · cites this paper as Besta et al. (2023)

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

The citation lists haven’t been fetched yet

References 63 · Cited by 556

Research works printed but not linked: 67

  1. Besta, M.; Fischer, M.; Kalavri, V.; Kapralov, M.; and Hoefler, T. 2023a. Practice of Streaming Processing of Dynamic Graphs: Concepts, Models, and Systems. IEEE Transactions on Parallel and Distributed Systems, 34(6): 1860-1876.
  2. Besta, M.; Gerstenberger, R.; Peter, E.; et al. 2023c. Demystifying Graph Databases: Analysis and Taxonomy of Data Organization, System Designs, and Graph Queries. ACM Comput. Surv., 56(2).
  3. Besta, M.; Grob, R.; Miglioli, C.; et al. 2022a. Motif Prediction with Graph Neural Networks. In 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD '22, 35-45.
  4. Besta, M.; Iff, P.; Scheidl, F.; Osawa, K.; Dryden, N.; Podstawski, M.; Chen, T.; and Hoefler, T. 2022b. Neural Graph Databases. In First Learning on Graphs Conference, volume 198 of Proceedings of Machine Learning Research, 31:1-31:38. PMLR.
  5. Besta, M.; Kanakagiri, R.; Kwaśniewski, G.; et al. 2021a. SISA: Set-Centric Instruction Set Architecture for Graph Mining on Processing-in-Memory Systems. In 54th Annual IEEE/ACM Inter- national Symposium on Microarchitecture, MICRO '21, 282-297.
  6. Besta, M.; et al. 2020. Communication-Efficient Jaccard Similar- ity for High-Performance Distributed Genome Comparisons. In IEEE International Parallel and Distributed Processing Sympo- sium, IPDPS '20, 1122-1132.
  7. Besta, M.; et al. 2021b. GraphMineSuite: Enabling High- Performance and Programmable Graph Mining Algorithms with Set Algebra. Proc. VLDB Endow., 14(11): 1922-1935.
  8. Besta, M.; et al. 2022c. Parallel and Distributed Graph Neural Net- works: An In-Depth Concurrency Analysis. arXiv:2205.09702. · arXiv
  9. Besta, M.; et al. 2022d. ProbGraph: High-Performance and High- Accuracy Graph Mining with Probabilistic Set Representations. In International Conference on High Performance Computing, Net- working, Storage and Analysis, SC '22. IEEE.
  10. Besta, M.; et al. 2023d. The Graph Database Interface: Scaling Online Transactional and Analytical Graph Workloads to Hun- dreds of Thousands of Cores. In International Conference for High Performance Computing, Networking, Storage and Analysis, SC '23. ACM.
  11. Bronstein, M. M.; Bruna, J.; LeCun, Y.; Szlam, A.; and Van- dergheynst, P. 2017. Geometric Deep Learning: Going beyond Euclidean data. IEEE Signal Processing Magazine, 34(4): 18-42.
  12. Brown, T.; Mann, B.; Ryder, N.; Subbiah, M.; Kaplan, J. D.; Dhariwal, P.; et al. 2020. Language Models are Few-Shot Learn- ers. In Advances in Neural Information Processing Systems (NeurIPS '20), volume 33, 1877-1901.
  13. Curran Associates. Bubeck, S.; et al. 2023. Sparks of Artificial General Intelligence: Early experiments with GPT-4. arXiv:2303.12712. · arXiv
  14. Chami, I.; et al. 2020. Machine Learning on Graphs: A Model and Comprehensive Taxonomy. arXiv:2005.03675. · arXiv
  15. Cheng, J.; Yu, J. X.; Ding, B.; Philip, S. Y.; and Wang, H. 2008. Fast Graph Pattern Matching. In 24th International Conference on Data Engineering, ICDE '08, 913-922. IEEE.
  16. Chowdhery, A.; et al. 2022. PaLM: Scaling Language Modeling with Pathways. arXiv:2204.02311. · arXiv
  17. Creswell, A.; Shanahan, M.; and Higgins, I. 2022. Selection- Inference: Exploiting Large Language Models for Interpretable Logical Reasoning. arXiv:2205.09712. · arXiv
  18. Dhulipala, L.; Blelloch, G. E.; and Shun, J. 2019. Low-Latency Graph Streaming Using Compressed Purely-Functional Trees. In 40th ACM SIGPLAN Conference on Programming Language De- sign and Implementation, PLDI '19, 918-934.
  19. Dohan, D.; Xu, W.; Lewkowycz, A.; Austin, J.; Bieber, D.; et al. 2022. Language Model Cascades. In Beyond Bayes: Paths To- wards Universal Reasoning Systems, Workshop at ICML '22.
  20. Fan, W.; Li, J.; Ma, S.; Tang, N.; Wu, Y.; and Wu, Y. 2010. Graph Pattern Matching: From Intractable to Polynomial Time. Proc. VLDB Endow., 3(1-2): 264-275.
  21. Feng, G.; Meng, X.; and Ammar, K. 2015. DISTINGER: A dis- tributed graph data structure for massive dynamic graph process- ing. In Proccedings of the IEEE International Conference on Big Data, Big Data '15, 1814-1822.
  22. Friston, K. 2008. Hierarchical Models in the Brain. PLOS Com- putational Biology, 4(11): 1-24.
  23. Fu, Y.; et al. 2022. Complexity-Based Prompting for Multi-Step Reasoning. arXiv:2210.00720. · arXiv
  24. Gianinazzi, L.; Fries, M.; Dryden, N.; et al. 2021. Learning Com- binatorial Node Labeling Algorithms. arXiv:2106.03594. · arXiv
  25. Gregor, D.; and Lumsdaine, A. 2005a. Lifting Sequential Graph Algorithms for Distributed-Memory Parallel Computation. SIG- PLAN Not., 40(10): 423-437.
  26. Hamilton, W. L.; Ying, R.; and Leskovec, J. 2017. Representation Learning on Graphs: Methods and Applications. Bulletin of the Technical Committee on Data Engineering, 40(3): 52-74.
  27. Huang, W.; Abbeel, P.; Pathak, D.; and Mordatch, I. 2022a. Language Models as Zero-Shot Planners: Extracting Actionable Knowledge for Embodied Agents. In 39th International Confer- ence on Machine Learning, volume 162 of Proceedings of Ma- chine Learning Research, 9118-9147.
  28. PMLR.
  29. Huang, W.; Xia, F.; Xiao, T.; Chan, H.; Liang, J.; et al. 2022b. In- ner Monologue: Embodied Reasoning through Planning with Lan- guage Models. arXiv:2207.05608. · arXiv
  30. Lester, B.; Al-Rfou, R.; and Constant, N. 2021. The Power of Scale for Parameter-Efficient Prompt Tuning. In Conference on Empirical Methods in Natural Language Processing, EMNLP '21, 3045-3059. Association for Computational Linguistics.
  31. Li, X. L.; and Liang, P. 2021. Prefix-Tuning: Optimizing Contin- uous Prompts for Generation. arXiv:2101.00190. · arXiv
  32. Long, J. 2023. Large Language Model Guided Tree-of-Thought. arXiv:2305.08291. · arXiv
  33. Lumsdaine, A.; Gregor, D.; Hendrickson, B.; and Berry, J. 2007. Challenges in Parallel Graph Processing. Parallel Processing Let- ters, 17(1): 5-20.
  34. Madaan, A.; et al. 2023. Self-Refine: Iterative Refinement with Self-Feedback. arXiv:2303.17651. · arXiv
  35. Malewicz, G.; Austern, M. H.; Bik, A. J.; et al. 2010. Pregel: A System for Large-Scale Graph Processing. In International Con- ference on Management of Data, SIGMOD '10, 135-146. ACM.
  36. Ning, X.; et al. 2023. Skeleton-of-Thought: Large Language Mod- els Can Do Parallel Decoding. arXiv:2307.15337. · arXiv
  37. Nye, M.; Andreassen, A. J.; Gur-Ari, G.; Michalewski, H.; Austin, J.; Bieber, D.; et al. 2021. Show Your Work: Scratchpads for Inter- mediate Computation with Language Models. arXiv:2112.00114. · arXiv
  38. Paul, D.; et al. 2023. REFINER: Reasoning Feedback on Interme- diate Representations. arXiv:2304.01904. · arXiv
  39. Qiao, S.; Ou, Y.; Zhang, N.; Chen, X.; Yao, Y.; et al. 2023. Reason- ing with Language Model Prompting: A Survey. In 61st Annual Meeting of the Association for Computational Linguistics, ACL '23, 5368-5393. Association for Computational Linguistics.
  40. Robinson, I.; et al. 2015. Graph Databases: New Opportunities for Connected Data. O'Reilly Media, 2nd edition.
  41. Sakr, S.; Bonifati, A.; Voigt, H.; Iosup, A.; Ammar, K.; Angles, R.; et al. 2021. The Future is Big Graphs: A Community View on Graph Processing Systems. Commun. ACM, 64(9): 62-71.
  42. Scarselli, F.; Gori, M.; Tsoi, A. C.; Hagenbuchner, M.; and Mon- fardini, G. 2008. The Graph Neural Network Model. IEEE Trans- actions on Neural Networks, 20(1): 61-80.
  43. Shin, T.; Razeghi, Y.; Logan IV, R. L.; Wallace, E.; and Singh, S. 2020. AutoPrompt: Eliciting Knowledge from Language Models with Automatically Generated Prompts. arXiv:2010.15980. · arXiv
  44. Shinn, N.; et al. 2023. Reflexion: Language Agents with Verbal Reinforcement Learning. arXiv:2303.11366. · arXiv
  45. Shum, K.; Diao, S.; and Zhang, T. 2023. Automatic Prompt Augmentation and Selection with Chain-of-Thought from Labeled Data. arXiv:2302.12822. · arXiv
  46. Teixeira, C. H. C.; et al. 2015. Arabesque: A System for Dis- tributed Graph Mining. In 25th Symposium on Operating Systems Principles, SOSP '15, 425-440. ACM.
  47. Touvron, H.; et al. 2023a. Llama 2: Open Foundation and Fine- Tuned Chat Models. arXiv:2307.09288. · arXiv
  48. Touvron, H.; et al. 2023b. LLaMA: Open and Efficient Foundation Language Models. arXiv:2302.13971. · arXiv
  49. Vaswani, A.; Shazeer, N.; Parmar, N.; Uszkoreit, J.; et al. 2017. Attention is All you Need. In Advances in Neural Information Processing Systems (NIPS '17), volume 30.
  50. Curran Associates. Wang, L.; Xu, W.; Lan, Y.; Hu, Z.; Lan, Y.; Lee, R. K.-W.; and Lim, E.-P. 2023a. Plan-and-Solve Prompting: Improving Zero- Shot Chain-of-Thought Reasoning by Large Language Models. In 61st Annual Meeting of the Association for Computational Lin- guistics, ACL '23, 2609-2634. Association for Computational Linguistics.
  51. Wang, X.; et al. 2023b. Self-Consistency Improves Chain of Thought Reasoning in Language Models. In Eleventh Interna- tional Conference on Learning Representations, ICLR '23.
  52. Wang, Z.; et al. 2023c. Describe, Explain, Plan and Select: Interac- tive Planning with Large Language Models Enables Open-World Multi-Task Agents. In Advances in Neural Information Processing Systems (NeurIPS '23), volume 36.
  53. Curran Associates. Wei, J.; et al. 2022. Chain-of-Thought Prompting Elicits Reason- ing in Large Language Models. arXiv:2201.11903. · arXiv
  54. Wu, T.; Jiang, E.; Donsbach, A.; Gray, J.; Molina, A.; Terry, M.; and Cai, C. J. 2022. PromptChainer: Chaining Large Language Model Prompts through Visual Programming. In Extended Ab- stracts of the Conference on Human Factors in Computing Sys- tems, CHI EA '22. ACM.
  55. Wu, T.; Terry, M.; and Cai, C. J. 2022. AI Chains: Transparent and Controllable Human-AI Interaction by Chaining Large Language Model Prompts. In Conference on Human Factors in Computing Systems, CHI '22. ACM.
  56. Wu, Z.; Pan, S.; Chen, F.; Long, G.; Zhang, C.; and Yu, P. S. 2021. A Comprehensive Survey on Graph Neural Networks. IEEE Transactions on Neural Networks and Learning Systems, 32(1): 4- 24.
  57. Xie, Y.; et al. 2023. Self-Evaluation Guided Beam Search for Rea- soning. In Advances in Neural Information Processing Systems (NeurIPS '23), volume 36.
  58. Curran Associates. Yang, S.; Nachum, O.; Du, Y.; Wei, J.; Abbeel, P.; and Schuur- mans, D. 2023. Foundation Models for Decision Making: Prob- lems, Methods, and Opportunities. arXiv:2303.04129. · arXiv
  59. Yao, S.; Yu, D.; Zhao, J.; Shafran, I.; Griffiths, T. L.; Cao, Y.; and Narasimhan, K. R. 2023a. Tree of Thoughts: Deliberate Problem Solving with Large Language Models. In Advances in Neural In- formation Processing Systems (NeurIPS '23), volume 36.
  60. Curran Associates. Yao, S.; Zhao, J.; Yu, D.; Du, N.; et al. 2023b. ReAct: Synergizing Reasoning and Acting in Language Models. In Eleventh Interna- tional Conference on Learning Representations, ICLR '23.
  61. Yao, Y.; Li, Z.; and Zhao, H. 2023. Beyond Chain-of-Thought, Ef- fective Graph-of-Thought Reasoning in Large Language Models. arXiv:2305.16582. · arXiv
  62. Zelikman, E.; et al. 2022. STaR: Bootstrapping Reasoning With Reasoning. In Advances in Neural Information Processing Sys- tems (NeurIPS '22), volume 35, 15476-15488.
  63. Zhang, S.; Chen, Z.; Shen, Y.; Ding, M.; et al. 2023. Planning with Large Language Models for Code Generation. In Eleventh International Conference on Learning Representations, ICLR '23.
  64. Zhang, Z.; Cui, P.; and Zhu, W. 2022. Deep Learning on Graphs: A Survey. IEEE Transactions on Knowledge and Data Engineering, 34(1): 249-270.
  65. Zhou, J.; Cui, G.; Hu, S.; et al. 2020. Graph neural networks: A review of methods and applications. AI Open, 1: 57-81.
  66. Zhou, Y.; et al. 2022. Large Language Models Are Human-Level Prompt Engineers. arXiv:2211.01910. · arXiv
  67. Zhu, X.; Wang, J.; Zhang, L.; Zhang, Y.; Huang, Y.; Gan, R.; Zhang, J.; and Yang, Y. 2023. Solving Math Word Problems via Cooperative Reasoning induced Language Models. In 61st An- nual Meeting of the Association for Computational Linguistics, ACL '23, 4471-4485. Association for Computational Linguistics.

Authors
Besta, M., Blach, N., Kubicek, A., Gerstenberger, R., Podstawski, M., Gianinazzi, L., Gajda, J., Lehmann, T., Niewiadomski, H., Nyczyk, P., & Hoefler, T.
Affiliations
ETH Zurich (CH)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2023
Volume
38
Issue
16
Pages
17682-17690
ISSN
2159-5399 (ISSN-L)
DOI
10.48550/arxiv.2308.09687
arXiv
2308.09687
OpenAlex
W4393160302
Cited by
556
References
63
Citations by year
2026: 201 · 2025: 235 · 2024: 111 · 2023: 9
FWCI
161.47
Type
conference paper
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • Proceedings of the AAAI Conference on Artificial Intelligence (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • AAAI Publications (The Association for the Advancement of Artificial Intelligence (AAAI)) (submittedVersion)
  • arXiv (Cornell University)
Funders
  • European High Performance Computing Joint Undertaking
  • European Commission (101070141, 955513)
  • H2020 European Research Council (101002047)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Topic Modeling
  • Physical Sciences › Computer Science › Artificial Intelligence › Natural Language Processing Techniques
  • Physical Sciences › Computer Science › Artificial Intelligence › AI-based Problem Solving and Planning
Keywords
graph-of-thought, large language models, prompting, chain-of-thought, tree-of-thought, graph reasoning, feedback loops, sorting, LLM reasoning

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review