THOUGHT PROPAGATION: AN ANALOGICAL APPROACH TO COMPLEX REASONING WITH LARGE LANGUAGE MODELS

Thank you for acknowledging the novelty and contributions of our work! And we indeed appreciate the valuable feedback from Reviewer 39VY. We hope the following responses could address your concerns.

Q1: Combining TP with CoT to achieve further performance improvements.

A1: Thanks very much for the valuable suggestion! And we have added an additional section in Appendix H.1 for detailed analysis. We adopt CoT to instantiate the $`LLM Solve`$ module of TP and test the obtained model, namely TP+CoT, on the Shortest-path Reasoning Task. In addition, we implement one and two layers of TP propagation for TP+CoT, leading to two variant models: TP (1-layer)+CoT and TP (2-layer)+CoT. We rerun CoT with GPT-3.5-turbo to ensure a fair comparison with two variant models due to the changing behavior of the GPT model [1]. Thus, the obtained performance of CoT is slightly different from that in our manuscript. We use the 3 metrics, namely Optimal Rate (OR↑), Feasible Rate (FR↑), and Over-Length Rate (OLR↓), as introduced in Section 5.1 for evaluation. We run all the models under 0-shot, 1-shot, and 5-shot settings.

[Table 1: Comparison between IO, CoT, CoT-SC, TP+IO, and TP+CoT in the Shortest-path Reasoning task.]

As shown in Table 1 above, TP (1 Layer)+CoT and TP (2 Layer)+CoT outperform CoT with significant performance gains, especially under the 0-shot setting. This indicates that TP enjoys plug-and-play enhancement for different prompting methods. Moreover, we find CoT and TP+CoT could not beat their IO prompting counterparts in the Shortest-path Reasoning task under 0-shot and few-shot settings, which is consistent with our findings and analysis in Section 5.1.

Q2: Increased complexity when compared with training methods and chain-of-thought (CoT) prompting.

A2: Thanks for your valuable comments! As TP is a prompting method, it is free from the burdensome of collecting additional data and training parameters of neural nets. Thus, it is efficient, generalizable, and eco-friendly when compared with training methods.

However, TP indeed requires additional computation costs to instantiate analogical reasoning when compared with reason-from-scratch prompting methods such as chain-of-thought (CoT) prompting. As introduced in Section 4, the additional computation cost mainly comes from solving an increasing number of analogous problems when implementing $k$ layer of TP. Thus, we only set $k=1$ or $k=2$ as they already lead to significant performance gain over the baselines. One solution to decrease the computational cost of TP is to further incorporate the task-related knowledge in $`LLM Propose`$ module to propose the most `helpful' analogous problems for the input problem-solving. We leave exploration in this direction in our future work, as we focus on a general analogical reasoning approach in this work.

Additionally, we study whether CoT with self-consistency (CoT-SC [2]), which solves the input problems $n$ times and votes for the most promising solutions, can outperform TP when these two approaches share similar token costs. We set $n=10$ to ensure they share similar token costs. As shown in Table 1, 1-layer TP+IO already outperforms CoT-SC. This indicates the efficacy of the proposed TP benefits from the novel analogical reasoning approach rather than only increasing the token cost.

Q3: Typo issue in the last sentence of Section 6 on Page 9.

A3: We really appreciate your suggestions and we have corrected the quotation marks in the last sentence of section 6 on page 9.

[1]. How is ChatGPT's behavior changing over time? Arxiv 2023.
[2]. Self-consistency improves the chain of thought reasoning in language models. ICLR 2023.

Thank you for acknowledging the motivation and novelty of our work! And we really appreciate your valuable suggestions and comments. We would like to answer the questions in Weaknesses as follows:

Q1: The reasons why we evaluate LLMs on Shortest-path Reasoning Task.

A1: Thanks for this valuable comment. The reasons are as follows:

• $**The Shortest-path Reasoning Task is a good testbed for evaluating the complex reasoning ability of LLMs.**$ Although humans have invented deterministic algorithms to solve the shortest-path reasoning task, this task is suitable to test the complex reasoning ability of LLMs. Unlike the arithmetic problems in prior works requiring a few steps to solve, the shortest-path task takes many more steps to solve and requires LLMs to traverse in discrete, diverse, and irregular graphs for optimal solutions. Thus, this task poses great challenges for LLMs. Moreover, some concurrent works also start to explore the ability of LLMs to solve graph-related tasks [1,2], since LLMs have achieved great success in many applications. These works indicate that it is difficult for LLMs to solve graph-related tasks. Thus, the shortest-path task serves as a good testbed to evaluate the complex reasoning ability of LLMs.

• $**Using generated graphs for evaluation prevents data contamination.**$ Recent works highlight the risk in LLM evaluation that the testing data are used to train LLMs, which is known as data contamination [4]. However, the graph modality is different from the sequential data used to train LLMs. Moreover, we randomly generate diverse graphs for LLM evaluation with the algorithm introduced in Appendix C.1. The LLMs such as GPT-3.5/4.0 cannot use our generated graphs, which were generated in July 2023, and were never uploaded to the Internet, for parameter training. Thus, evaluating LLMs on the Shortest-path Reasoning task with generated graphs can prevent data contamination. We will clarify the motivation for evaluating LLMs with the Shortest-path Reasoning task in the Experiment part of the revision.

Q2: The impact of how graphs are encoded into prompts in natural languages may affect the performances of different methods.

A2: Thanks for this valuable comment and we have added a detailed analysis in Appendix H.2! In our work, we initially adopted the straightforward manner to encode input graphs into the collection of node lists, edge lists, and edge distance lists. We denote such graph encoding method as $**Adjacency**$.

Previous works have shown that changing the prompt exemplars can impact the reasoning performances of prompting methods. As there are multiple ways to encode the input graphs into sequential data, we further consider two additional graph encoding methods including $**Edge Description**$ [1] and $**Graph Modeling Language**$ [2,3].

For an input graph with $N$ nodes, Edge Description represents the input graph as "In an undirected graph, the nodes are numbered from 0 to $N$, and the edges are represented as: an edge between node $i$ and node $j$ with distance $LENGTH$,$\cdots$.". Graph Modeling Language converts the input graph into the following sequence "graph[comment "This is an undirected graph." node [id 0] $\cdots$ node [id $N$] edge [label "Edge between node $i$ and node $j$ with distance $LENGTH$"] $\cdots$.]"

As shown in Table 1 below, different graph encoding methods indeed impact the performances of different prompting approaches. However, the proposed TP still enjoys an over 10% absolute increase in finding the optimal shortest path when adopting Edge Description and Graph Modeling Language to encode graphs into sequences. $**This indicates the robustness of TP against different graph encoding methods.**$

Notice that we do not aim to propose the best way for LLMs to understand graphs. Instead, we aim to propose a general analogical approach to enhance the complex reasoning ability of LLMs across different tasks. As discussed in Section 5, TP achieves significant performance gains in different tasks not limited to Shortest-path reasoning.

[Table 1: The performance comparison between methods with different graph encoding. We run all the experiments using GPT-3.5.]

Q3: The Computation cost analysis on Creative writing and LLM-agent Planning tasks.

A3: Thanks for this valuable comments! We agree that TP is more computationally expensive than ToT as TP needs to explore a set of analogous problems to update the initial input problem-solving. ToT uses 790.1K tokens for Creative writing while TP uses 2869.1K tokens. For the LLM-agent Planning task, it is challenging to accurately calculate the number of tokens due to some dependency issues of ALFWORLD. However, we managed to roughly estimate that Reflexion costs around 300 USD to run 6 trails while the different variant models of TP cost 300-400 USD to run 6 trails based on the billing information from an LLM research institute/company.

To address the concerns that TP achieves better performances than baselines by simply using more tokens, we rerun CoT 10 times and max-vote the best results (CoT-SC [5]). Please refer to A2 in response to Reviewer 39VY for detailed experiment results. Our finding is that 1-layer TP+IO already outperforms CoT-SC. This indicates the efficacy of the proposed TP results from the novel analogical reasoning approach rather than only increasing the token cost. We will aim to further improve the efficacy of the proposed TP while reducing its computation cost in our future work. One solution is to incorporate the task-related knowledge in LLM Propose module. Thus, TP could propose the analogous problems that most help the input problem-solving. And we will add the above analysis to the Experiment part of the final version.

[1]. Can Language Models Solve Graph Problems in Natural Language? NeurIPS 2023.
[2]. Gml: A portable graph file format. Technical report, Universitat Passau, 1997.
[3]. Gpt4graph: Can large language models understand graph-structured data? an empirical evaluation and benchmarking. Arxiv 2023.
[4]. Data Contamination: From Memorization to Exploitation. ACL 2022.
[5]. Self-consistency improves the chain of thought reasoning in language models. ICLR 2023.

We greatly thank Reviewer VZuc for acknowledging the novelty and contribution of our work! We have carefully revised our submission according to your constructive suggestions. The responses to your questions are as follows:

Q1: Compared with self-refinement LLM reasoning methods.

A1: We thank the reviewer for bringing our attention to these works. We have added an additional section in Appendix G (Pages 25-26) to compare the proposed work (TP) with self-refined LLM reasoning in detail and highlight our contributions. The self-refined LLM reasoning, also known as self-critic, is an emerging technique to rectify the mistakes and hallucinations during the inference time of LLM reasoning [1,2]. Recent works in self-refined LLM reasoning guide LLMs to examine the correctness of their output with internal [3] or external feedback [4], and further refine their output if needed.

The $`LLM Aggregate`$ module of TP shares similar intuition with self-refined LLM reasoning methods, since it can yield strategies for improving the input problem-solving with the insights of solving $**analogous**$ problems. By analogical reasoning, $`LLM Aggregate`$ can assess a diverse set of strategies and choose the best one for refinement based on the connection between the input problem and its analogous counterparts. Instead, existing self-refined LLM reasoning methods cannot utilize the knowledge of solving analogous problems to refine the input problems as they cannot prompt LLMs to perform analogical reasoning. We will explore the application of TP in self-refined LLM reasoning in the future.

Q2: The probability of deteriorating the initial solution after Thought Propagation.

A2: Thank you very much for this question! We further divide the cases where TP changes the initial solutions to input problems by analogical reasoning into 2 categories:

• Improved: the percentage of cases where TP changes the invalid solutions to valid ones and improves the valid solutions to better ones,

• Deteriorated: the percentage of cases where TP changes the valid solutions into invalid ones and changes the valid solutions to worse (but also valid) ones.

We compute the probability of these two categories under 0-shot, 1-shot, and 5-shot in the Shortest-path Reasoning task. The results are in the following table.

As shown in the table above, TP improves more initial solutions in the Shortest-path Reasoning task rather than deteriorates them. This indicates that TP can greatly refine the initial solutions, which are obtained by reasoning from scratch, to enhance the complex reasoning ability of LLMs by analogical reasoning. Moreover, we observe that TP is more capable of improving initial solutions when deployed on more powerful LLMs such as GPT series. In our future work, we aim to further improve the efficacy of the TP framework and delve into the theoretical analysis behind analogical reasoning with LLMs.

[1]. Self-refine: Iterative refinement with self-feedback. NeurIPS 2023.
[2]. Large Language Models can self-improve. Arxiv 2022.
[3]. Reflexion: an autonomous agent with dynamic memory and self-reflection. NeurIPS 2023.
[4]. The capacity for moral self-correction in large language models. Arxiv 2023.