The talk given by Maciej Besta in KUIS AI Talks on December 12, 2023.

Title: Chains, Trees, and Graphs of Thoughts: Demystifying Structured-Enhanced Prompting

Abstract
The field of natural language processing has witnessed significant progress in recent years, with a notable focus on improving language models’ performance through innovative prompting techniques. Among these, structure-enhanced prompting has emerged as a promising paradigm, with designs such as Chain-of-Thought (CoT) or Tree of Thoughts (ToT), in which the LLM reasoning is guided by a structure such as a tree. In the first part of the talk, we overview this recent field, focusing on fundamental classes of harnessed structures, the representations of these structures, algorithms executed with these structures, relationships to other parts of the generative AI pipeline such as knowledge bases, and others. Second, we introduce Graph of Thoughts (GoT): a framework that advances prompting capabilities in LLMs beyond those offered by CoT or 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 such as keyword counting while simultaneously reducing costs. We finalize with outlining research challenges in this fast-growing field.

Short Bio
Maciej Besta leads research on graph computations, large language models, and network topologies at the Scalable Parallel Computing Lab at ETH Zurich. Maciej published around 50 top conference and journal papers. He won, among others, the competition for the Best Student of Poland (2012), the first Google Fellowship in Parallel Computing (2013), the ACM/IEEE-CS High-Performance Computing Fellowship (2015), The Explorers Club Fellowship (2022), and the IEEE TCSC Award for Excellence in Scalable Computing (Early Career). His doctoral dissertation on irregular computations received the ETH Medal for outstanding doctoral thesis (2021), and awards from IEEE (2021), SPEC (2022), and ACM (2022). He received Best Paper awards and nominations at ACM/IEEE Supercomputing 2013, 2014, 2019, 2022, and 2023; at ACM HPDC 2015 and 2016, ACM Research Highlights 2018, and others.
More detailed information on his personal website: https://people.inf.ethz.ch/bestam/ .