PaperlayerView exact revision on arXiv

Source-linked AI summary

Thought Propagation: An Analogical Approach to Complex Reasoning with Large Language Models

Junchi Yu, Ran He, Rex Ying

arXiv:2310.03965v3cs.AIcs.CL

TL;DR

Existing prompting approaches reason from scratch, limiting reuse of insights from similar problems and leaving multi-step reasoning vulnerable to accumulated errors. Thought Propagation (TP) solves analogous problems and reuses their solutions to refine answers or plans; experiments report gains over baselines across three tasks.

  • Problem

    Existing LLM prompting methods cannot reuse insights from similar problems and are vulnerable to accumulated errors during multi-step reasoning.

    Source: §1 · p. 2

  • Method

    Thought Propagation proposes and solves analogous problems, then aggregates their solutions to create a new input solution or a high-level plan.

    Source: §1 · p. 2

  • Results

    TP reports superior performance over baselines across Shortest-path Reasoning, Creative Writing, and LLM-Agent Planning.

    Source: §1 · p. 2

  • Takeaways & Limitations

    TP is compatible with existing prompting methods and generalizes across optimization, writing, and agent-planning tasks.

    Source: §6 · p. 9

    Two-layer TP yields marginal gains over one layer while increasing token expenses.

    Source: §4 · p. 6

Abstract

from arXiv · show

Large Language Models (LLMs) have achieved remarkable success in reasoning tasks with the development of prompting methods. However, existing prompting approaches cannot reuse insights of solving similar problems and suffer from accumulated errors in multi-step reasoning, since they prompt LLMs to reason \textit{from scratch}. To address these issues, we propose \textbf{\textit{Thought Propagation} (TP)}, which explores the analogous problems and leverages their solutions to enhance the complex reasoning ability of LLMs. These analogous problems are related to the input one, with reusable solutions and problem-solving strategies. Thus, it is promising to propagate insights of solving previous analogous problems to inspire new problem-solving. To achieve this, TP first prompts LLMs to propose and solve a set of analogous problems that are related to the input one. Then, TP reuses the results of analogous problems to directly yield a new solution or derive a knowledge-intensive plan for execution to amend the initial solution obtained from scratch. TP is compatible with existing prompting approaches, allowing plug-and-play generalization and enhancement in a wide range of tasks without much labor in task-specific prompt engineering. Experiments across three challenging tasks demonstrate TP enjoys a substantial improvement over the baselines by an average of 12\% absolute increase in finding the optimal solutions in Shortest-path Reasoning, 13\% improvement of human preference in Creative Writing, and 15\% enhancement in the task completion rate of LLM-Agent Planning.

1 INTRODUCTION

Existing prompting methods break complex reasoning into steps but still reason from scratch, limiting reuse of insights from similar problems and leaving multi-step reasoning vulnerable to accumulated errors. Thought Propagation (TP) uses analogous problems to refine solutions or plans, and experiments report superior performance across three tasks.

1 INTRODUCTION

  • Reasoning from scratch prevents reuse of insights from similar problems and leaves multi-step reasoning vulnerable to accumulated intermediate errors.Those errors can misguide later searching and planning, eventually producing invalid reasoning outcomes.Source: §1 · p. 2
  • Analogical reasoning offers a way to draw on existing knowledge, but a general framework for using problem analogies to facilitate LLM reasoning had not been explored.The passage describes analogy as applying relationships of the form “A is to B what C is to D.”Source: §1 · p. 2
  • TP generates related analogous problems, solves them with existing prompting approaches, and aggregates their solutions to produce a new solution or high-level plan for the input.It compares a new analogical solution with an initial solution from scratch, or executes a plan to rectify intermediate reasoning steps.Source: §1 · p. 2
  • TP is compatible with existing prompting approaches and is intended to generalize across tasks without intensive task-specific prompt engineering.The described range includes optimization problems and autonomous agent planning.Source: §1 · p. 2
  • Experiments report superior TP performance across Shortest-path Reasoning, Creative Writing, and LLM-Agent Planning.These tasks involve graph-structured search, open-ended writing, and long-trial planning, respectively.Source: §1 · p. 2

2 RELATED WORK

Prior work studies graph learning and analogy in specialized applications, while prompting methods for complex LLM reasoning use multi-step decomposition or search. The paper positions its approach as general problem analogy for LLM reasoning rather than task-specific graph methods or reasoning from scratch.

2 RELATED WORK

  • GNNs are described as expressive deep-graph-learning backbones because of their inductive bias on graph-structured data.The supplied passage begins to discuss task-related expressiveness but does not provide the rest of that discussion.Source: §2 · p. 2
  • Parameterized GNNs have been combined with LLMs for graph-related tasks including graph explainability, classification, and question answering.The paper distinguishes those applications from its aim of improving general LLM reasoning through problem analogy without fine-tuning.Source: Figure 2 · p. 3
  • Earlier analogical-reasoning methods target particular applications, and some rely on large external knowledge bases to represent entity relationships.The passage characterizes those knowledge bases as expensive for general reasoning tasks.Source: §2 · p. 3
  • Prior LLM reasoning methods use multi-step prompting, recursive decomposition, or search, but still solve each problem from scratch.The paper identifies inability to reuse insights from similar problems and accumulated intermediate-step errors as limitations of these approaches.Source: §2 · p. 3

3 PRELIMINARIES

The preliminaries distinguish one-step IO prompting from multi-step Chain-of-Thought (CoT) and search-based Tree-of-Thought (ToT). These methods still reason from scratch, which the paper links to missed prior knowledge and accumulated errors in optimization and multi-step search.

3 PRELIMINARIES

  • IO prompting maps an input problem directly to a solution in one step, which the paper says is insufficient for complex problems requiring multi-step reasoning.It uses task descriptions and few-shot input-output demonstrations.Source: §3 · p. 3
  • CoT prompting decomposes reasoning into intermediate thoughts before producing a final solution.The passage also describes sequential generation of each intermediate step conditioned on earlier ones.Source: §3 · p. 3
  • ToT formulates reasoning as a search through the solution space, using heuristics such as breadth-first or depth-first search.The supplied ToT passages describe proposing candidate sub-solutions and selecting one to continue the search.Source: §3 · pp. 3–4
  • IO, CoT, and ToT reason from scratch, whereas TP explores analogous problems to improve the input-problem solution.The figure comparison depicts the approaches as distinct reasoning paths from an input problem to its solution.Source: Figure 3 · p. 4
  • Reasoning from scratch cannot reuse prior problem-solving knowledge and can accumulate intermediate errors, leaving these methods short on optimization and multi-step search tasks.In the illustrated simple graph, the methods miss the optimal path 0 → 3 → 4; ToT also searches backward and revisits Node 3.Source: §3 · p. 4

4 METHODOLOGY

Thought Propagation generates analogous problems, solves them alongside the input, and aggregates their solutions to refine an answer or create a plan. It supports one- or multi-layer refinement and can use existing prompting methods, with deeper propagation trading additional token expense for marginal gains.

4 METHODOLOGY

  • Thought Propagation generates related analogous problems without external knowledge bases, solves them, and combines their solutions to update the input solution or formulate a high-level plan.The framework comprises LLM Propose, LLM Solve, and LLM Aggregate modules.Source: §4 · p. 4
  • LLM Propose creates analogies for either transferring their solutions to the input or generating high-level plans that can rectify errors during multi-step reasoning.The two ways of generating analogies use few-shot exemplars or zero-shot prompting.Source: §4 · p. 4
  • LLM Solve produces an initial input solution and solves proposed analogous problems; LLM Aggregate assesses their results and uses promising ones.The passage notes that analogous-problem solutions need not be expert-level and describes a multi-layer implementation to improve them.Source: §4 · pp. 4–5
  • Aggregation can derive a new input solution from analogous results or form a knowledge-intensive plan for repeated decision-making, then evaluate outputs and choose the best.For shortest paths, known paths to neighboring nodes can make deriving a path to the target a one-step reasoning task.Source: §4 · p. 5
  • Stacking K TP layers uses K-hop analogies for hierarchical refinement; existing IO, CoT, and ToT approaches are the K = 0 case.At K ≥ 2, each layer refines the solutions in the preceding layer until the input solution is refined.Source: §4 · p. 5
  • TP can use existing prompting methods to instantiate LLM Solve, with ReAct suggested for autonomous planning and exploration tasks.The paper reports that two-layer gains over one layer are marginal despite greater token expense, while one-layer TP has competitive performance without a significant token-expense increase.Source: §4 · pp. 5–6
  • TP complexity grows exponentially with layer count, and longer-range analogies yield only marginal performance gains, motivating implementation of at most two layers.The paper also notes that five-shot LLM Solve is more expensive than zero-shot because it adds prompting exemplars.Source: §4 · pp. 5–6

5 EXPERIMENTS

Across Shortest-path Reasoning, Creative Writing, and LLM-Agent Planning, Thought Propagation achieves the strongest reported outcomes among the compared methods.

5 EXPERIMENTS

  • TP finds the most optimal shortest paths, generates the most coherent messages, and achieves the highest task completion rate across the three evaluated tasks.The evaluation includes 100 shortest-path problems, 100 writing problems, and 134 ALFWorld environments.Source: §5 · p. 6

5.1 SHORTEST-PATH REASONING

  • Two-layer TP achieves the best shortest-path performance, but its gain over one layer is less significant and its token cost increases.One-layer TP has token costs similar to ToT and already performs competitively.Source: Figure 5 · p. 7, §5.1 · p. 7
  • TP generates the most optimal and valid shortest paths across three LLM backends, while its valid paths have the lowest Over-Length Rate.ToT fails to find valid paths on PaLM-2 and underperforms IO on GPT-3.5 and GPT-4.Source: §5.1 · p. 7
  • Five-shot gains over one-shot are marginal or sometimes worse, with long exemplars and LLM output cutoffs offered as possible reasons.The authors leave in-depth exploration of this phenomenon to future work.Source: §5.1 · p. 7

5.3 LLM-AGENT PLANNING

  • TP variants improve ALFWorld task completion, including without a memory module for storing previous failures.The reported improvement is consistent across variants that use self-reflection and those that do not.Source: Table 3 · p. 8, Figure 6 · p. 9, §5.3 · p. 9

5.2 CREATIVE WRITING

  • For writing, TP generates five analogous problems from rephrased sentences, selects among six plans, then drafts the four-paragraph message.The evaluation uses 100 test instances and assesses coherence with a GPT-4 score and a user study.Source: §5.2 · pp. 7–8
  • TP achieves the highest coherent scores on GPT-3.5 and GPT-4 and the highest human preference in the writing user study.All methods perform better on GPT-4, according to the reported findings.Source: §5.2 · p. 8, Table 2 · p. 8

5.3 LLM-AGENT PLANNING

  • In ALFWorld, TP selects two similar tasks with successful trials, then uses their outcomes and the original task trial to formulate and evaluate plans.The evaluation covers 134 unseen environments; TP runs six trials to match Reflexion.Source: §5.3 · pp. 8–9

6 CONCLUSIONS

The conclusion presents Thought Propagation (TP) as an approach that uses analogous problems to refine solutions or create knowledge-intensive plans, and says it is compatible with existing prompts across several tasks. The related-work discussion distinguishes TP from retrieval-augmented LLMs and prior LLM-agent reflection by how it draws on information.

6 CONCLUSIONS

  • TP explores analogous problems to yield refined solutions or knowledge-intensive plans, and is compatible with existing prompting methods across Shortest-path Planning, Creative Writing, and LLM-Agent Planning.The conclusion identifies improving performance and efficiency as future directions.Source: §6 · p. 9

A MORE DISCUSSION WITH RELATED WORKS ON LLMS

  • Unlike retrieval-augmented LLMs, TP needs no external database and instead aggregates knowledge from solving analogous problems to guide reasoning.Retrieval-augmented LLMs query external databases for text used to construct answers.Source: A MORE DISCUSSION WITH RELATED WORKS… · p. 15
  • For LLM-Agent planning, TP draws on successful experience from similar tasks, whereas Reflexion stores failures from earlier attempts at the same task.The paper characterizes the LLM-based planning module as central to agents making decisions from environmental feedback.Source: A MORE DISCUSSION WITH RELATED WORKS… · p. 15

B EXAMPLES OF LONG-TRIAL LLM-AGENT PLANNING

In an ALFWorld example, a ReAct agent fails to examine a book with a desklamp, while TP uses plans from analogous tasks to guide a successful long-trial attempt. The example also contrasts this reuse of successful experience with reflection on failures from the same task.

B EXAMPLES OF LONG-TRIAL LLM-AGENT PLANNING

  • The ReAct agent fails the book-and-desklamp task, and the paper describes it as trapped in a loop.The supplied trace ends with STATUS: FAIL.Source: B EXAMPLES OF LONG-TRIAL LLM-AGENT… · pp. 15–16
  • The Reflexion example stores same-task failure memories but still loops on taking the desklamp instead of finding the book.Its described memory records repeated attempts and changing plans for the book-and-desklamp task.Source: B EXAMPLES OF LONG-TRIAL LLM-AGENT… · p. 16
  • TP proposes two analogous tasks and aggregates their prior planning trials to assist the original task.The example identifies the analogous tasks by indexes 129 and 6.Source: B EXAMPLES OF LONG-TRIAL LLM-AGENT… · p. 16
  • LLM Aggregate simulates and compares the two plans, selecting the plan summarized from task 6’s trial as the better plan.The paper says the plans are more detailed and instructive than the memory generated by Reflexion from previous failures on the same task.Source: B EXAMPLES OF LONG-TRIAL LLM-AGENT… · p. 17
  • TP’s generated plan guides the agent through a long-trial attempt that successfully completes the book-and-desklamp task.The example describes the analogous task as examining an alarmclock with the desklamp.Source: B EXAMPLES OF LONG-TRIAL LLM-AGENT… · pp. 17–18

C PROMPT EXAMPLE FOR SHORTEST-PATH REASONING

The appendix specifies graph-task generation, baselines, and prompting implementations for shortest-path reasoning. TP proposes analogous subproblems from graph neighborhoods, solves them, and aggregates their solutions or compares a new solution with the initial one.

C.1 TASK SETUP

  • The task uses 100 connected undirected weighted graphs with 5–10 nodes, edge-generation probability p = 0.2, and edge weights from 1 to 5.Each task asks for the shortest path from Node 0 to Node N − 1.Source: §C.1 · p. 19

C.2 BASELINES AND LLM BACKENDS

  • The comparison includes IO, CoT, BaG, and ToT across zero-, one-, and five-shot settings with PaLM 2, GPT-3.5, and GPT-4.ToT is reimplemented as breadth-first search from the source, with intermediate neighbors proposed and evaluated.Source: §C.2 · p. 19

C.3 PROMPTING EXAMPLES FOR THOUGHT PROPAGATION AND BASELINES

  • Graphs are supplied as node, edge, and edge-distance lists, with source and target appended; zero-shot IO uses the input-output format without a specific path exemplar.The prompting description gives a shortest-path answer format for the task.Source: §C.3 · pp. 19–20
  • CoT decomposes pathfinding into choosing successive nodes, while its zero-shot prompt adds “Let’s think step by step” and its few-shot examples resemble IO.The example describes each step’s node transition and distance.Source: §C.3 · p. 20
  • BaG’s implementation follows its preprint because no public implementation was available, while ToT’s node-evaluation prompts use zero-, one-, and four-example settings.ToT’s neighborhood-proposing module is shared with TP and uses five-shot diverse examples.Source: §C.3 · pp. 20–21
  • TP proposes analogous shortest-path problems from neighborhood nodes and solves them before aggregating their solutions into a candidate for the original problem.Its Solve module uses zero-, one-, or five-shot IO prompting.Source: §C.3 · pp. 21–22
  • LLM Aggregate can also verify and compare the new and initial path solutions, selecting the better candidate.The prompt warns that distances in hints may be wrong and should be checked.Source: §C.3 · p. 22

D PROMPT EXAMPLE FOR CREATIVE WRITING

The creative-writing setup evaluates coherence on generated passages from four-sentence inputs using both GPT-4 scoring and a user study. The appendix details the IO, CoT, and ToT baselines and TP’s plan-generation, rephrasing, selection, and writing steps.

D.1 TASK SETUP

  • The evaluation uses 100 test instances, each containing four sentences randomly sampled from a website.Coherence is assessed with a GPT-4 score and a user study.Source: §D.1 · p. 23
  • GPT-4 scores each generated message for coherence on a 1–10 scale five times, with the average used as its coherent score.The user study uses lab members who are not paper authors and flips message order.Source: §D.1 · p. 23

D.2 BASELINES AND LLM BACKENDS

  • The zero-shot baselines are IO, CoT, and ToT; IO and CoT each generate 10 samples per instance, while ToT chooses among five plans and five resulting messages.ToT uses one intermediate thought step.Source: §D.2 · p. 23
  • TP’s LLM Solve module generates plans for writing four-paragraph passages, with one sentence describing each paragraph.The plan prompt requires each paragraph to end with one of the input sentences.Source: §D.2 · p. 23
  • LLM Propose rephrases the four input sentences without changing their order or meaning, then LLM Solve creates a plan for that analogous problem.The rephrased sentences are used to generate a new writing plan.Source: §D.2 · p. 23
  • LLM Aggregate compares the initial plan with the new writing plans and outputs the best one.The module follows the scoring prompt used in ToT.Source: §D.2 · p. 23
  • TP generates the final four-paragraph passage using the selected plan while preserving the required input sentences as paragraph endings.The writing prompt explicitly conditions passage generation on the chosen plan.Source: §D.2 · pp. 23–24

E PROMPT EXAMPLE FOR LLM-AGENT PLANNING

The LLM-Agent Planning example selects previously solved tasks as analogues, uses them to devise plans for an unsolved task, and evaluates those plans before another trial.

E.1 TASK SETUP

  • The evaluation uses 134 unseen environments, and six TP trials on the dataset cost about 300–400 dollars.The setup follows prior ALFWorld evaluations and uses an interactive text-based task suite.Source: §E.1 · p. 24

E.2 PROMPTING EXEMPLAR OF TP IN LLM-AGENT PLANNING

  • The setup follows Reflexion, uses ReAct for LLM Solve, and selects the two highest-scoring successfully solved tasks as analogues.LLM Propose evaluates the current task against successfully solved tasks from the last trial round.Source: §E.2 · p. 24
  • The similarity prompt requests an integer score from 0 to 10, with 0 least similar and 10 most similar.Source: §E.2 · p. 24
  • LLM Aggregate uses successful analogous-task planning trials to devise two plans for completing the input task.Source: §E.2 · p. 24
  • The plan prompt asks the model to use a successful case to devise a concise, mistake-aware plan for a failed case, including specific actions.Source: §E.2 · p. 24
  • LLM Aggregate selects the better of two plans and sends it to the agent for the next planning trial.The exemplar prompt asks the model to output the most promising plan for the failed task.Source: §E.2 · pp. 24–25
  • Figure 7 examines how the number of TP layers influences Shortest-path Reasoning performance.Source: Figure 7 · p. 25

F IMPACT OF LAYERS ON PERFORMANCE

The discussion contrasts TP’s reuse of analogous-task experience with self-refinement methods that handle each input separately, and notes that TP outperforms Reflexion on task completion.

F IMPACT OF LAYERS ON PERFORMANCE

G MORE DISCUSSION WITH SELF-REFINEMENT OF LLM REASONING

  • Self-refinement uses feedback to revise reasoning, either through an earlier fine-tuning approach or newer prompting methods that check and refine outputs.Feedback may come from the reasoning model itself or from other models, tools, or people.Source: G MORE DISCUSSION WITH SELF-REFINEMENT… · pp. 25–26
  • All TP variants achieve significantly higher task completion than Reflexion, and the paper reports gains over baselines on the other tasks as well.The authors attribute the broader gains to analogical reasoning that lets LLMs explore and assess strategies from analogous problems.Source: G MORE DISCUSSION WITH SELF-REFINEMENT… · p. 26
  • Unlike self-refinement methods that handle inputs separately, TP reuses experience from analogous problems to explore diverse refinement strategies.The paper illustrates this contrast with an agent-planning example in which TP yields an effective strategy while other methods produce ineffective strategies that trap the agent in a loop.Source: G MORE DISCUSSION WITH SELF-REFINEMENT… · p. 26

H MORE EMPIRICAL ANALYSIS ON SHORTEST-PATH REASONING TASKS

The paper tests TP with Chain-of-Thought prompting and reports that one- and two-layer variants outperform CoT.

H.1 IMPLEMENTING THOUGHT PROPAGATION WITH CHAIN-OF-THOUGHT

  • TP (1 Layer)+CoT and TP (2 Layer)+CoT outperform CoT with significant performance gains.Source: §H.1 · p. 26
  • The authors rerun CoT with GPT 3.5 for comparison because the model’s behavior changed.The reported CoT performance therefore differs slightly from Table 1.Source: §H.1 · p. 26
  • The comparison supports TP as a plug-and-play enhancement when the LLM Solve module uses CoT prompting.Source: §H.1 · p. 26

H.2 IMPACT OF DIFFERENT GRAPH ENCODING METHODS ON THE MODEL PERFORMANCE IN SHORTEST-PATH REASONING TASK

The analysis compares graph encodings for Shortest-path Reasoning and reports gains for TP with alternative encodings, while emphasizing that encoding optimization is not the paper’s focus.

H.2 IMPACT OF DIFFERENT GRAPH ENCODING METHODS ON THE MODEL PERFORMANCE IN SHORTEST-PATH REASONING TASK

  • Adjacency encodes graphs as node lists, edge lists, and edge-distance lists, preserving connectivity in sequential input.Edge Description and Graph Modeling Language are examined as alternative encodings.Source: §H.2 · pp. 26–27
  • Edge Description and Graph Modeling Language improve most prompting methods over Adjacency in 0-shot and few-shot settings.The paper says these encodings help LLMs better understand graph structures.Source: §H.2 · p. 27
  • Over 10% absolute increase in finding the optimal shortest path is reported for TP using Edge Description and Graph Modeling Language encodings.Table 5 compares performance across methods with different graph encodings using GPT-3.5.Source: §H.2 · p. 27, Table 5 · p. 27
  • The paper’s aim is to enhance reasoning with TP, not to identify the best graph-to-sequence encoding.Source: §H.2 · p. 27
Loading 2310.03965v3…