PaperlayerView exact revision on arXiv

Source-linked AI summary

THOUGHTSCULPT: Reasoning with Intermediate Revision and Search

Yizhou Chi, Kevin Yang, Dan Klein

arXiv:2404.05966v2cs.CLcs.AI

TL;DR

Tree- and graph-based reasoning methods may be limited on tasks requiring frequent revision because they cannot continuously edit earlier answers in later steps. THOUGHTSCULPT uses MCTS to search interconnected thought nodes and lets language models revise outputs iteratively using evaluator feedback. THOUGHTSCULPT reports up to 16% word success rate increase in Mini-Crossword Solving and up to 10% concept coverage improvement in Constrained Generation.

  • Problem

    Tree- and graph-based reasoning methods may be limited on tasks requiring frequent revision because they cannot continuously edit earlier answers in later steps.

    Source: §1 · p. 1

  • Method

    THOUGHTSCULPT uses MCTS to search interconnected thought nodes and lets language models revise outputs iteratively using evaluator feedback.

    Source: §1 · p. 1

  • Results

    THOUGHTSCULPT reports up to 16% word success rate increase in Mini-Crossword Solving and up to 10% concept coverage improvement in Constrained Generation.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The method is presented as applicable to tasks requiring continuous thought iteration, including open-ended generation, multi-step reasoning, and creative ideation.

    Source: §5 · p. 8

    Multiple calls to the base language model incur higher computational cost than most sampling methods, so THOUGHTSCULPT may not be advisable when the base model already performs satisfactorily.

    Source: Limitations · p. 9

Abstract

from arXiv · show

We present THOUGHTSCULPT, a general reasoning and search method for tasks with outputs that can be decomposed into components. THOUGHTSCULPT explores a search tree of potential solutions using Monte Carlo Tree Search (MCTS), building solutions one action at a time and evaluating according to any domain-specific heuristic, which in practice is often simply an LLM evaluator. Critically, our action space includes revision actions: THOUGHTSCULPT may choose to revise part of its previous output rather than continuing to build the rest of its output. Empirically, THOUGHTSCULPT outperforms state-of-the-art reasoning methods across three challenging tasks: Story Outline Improvement (up to +30% interestingness), Mini-Crosswords Solving (up to +16% word success rate), and Constrained Generation (up to +10% concept coverage).

1 Introduction

THOUGHTSCULPT addresses the difficulty of revising earlier outputs in existing tree- and graph-based reasoning methods. It uses MCTS and self-revision to explore solutions, with reported gains across three tasks.

1 Introduction

  • Prompting strategies and instructional guidance can affect LLM performance on the same task, motivating methods that shape intermediate reasoning.Chain-of-Thought produces intermediate reasoning steps, while CoT-SC generates multiple chains and selects an outcome.Source: §1 · p. 1
  • Tree- and graph-based reasoning methods may struggle when tasks require frequent revision because they cannot continuously edit original answers in later steps.Their reasoning is often limited by candidates generated earlier.Source: §1 · p. 1
  • THOUGHTSCULPT combines MCTS with self-revision, using an evaluator, generator, and decision simulator to explore and refine interconnected thought nodes.Figure 1 illustrates selection, expansion, simulation, and backpropagation for Constrained Generation.Source: §1 · p. 1, Figure 1 · p. 2
  • THOUGHTSCULPT improves Mini-Crossword Solving word success rate by up to 16% and Constrained Generation concept coverage by up to 10%, underscoring efficacy across diverse tasks.Source: §1 · p. 3

2 Related Works

Related work addresses feedback-guided generation, graph reasoning, and language-model planning. THOUGHTSCULPT distinguishes itself through revisable intermediate nodes and inference-time search without training or external feedback.

Feedback Guided Generation

LM Planning

3 Method

THOUGHTSCULPT treats formal language-model outputs as thought nodes and uses evaluation feedback to generate and search candidate revisions. Its method combines thought evaluation, candidate generation, and MCTS-based simulation.

3 Method

  • Each formal language-model output is a thought node, ranging from outline items to crossword words or a sentence, and the method processes nodes with three modules.Those modules are the thought evaluator, thought generator, and decision simulator.Source: §3 · p. 3

3.1 Thought Evaluator

  • The thought evaluator supplies numerical scores for node evaluation and natural-language feedback to guide candidate generation, using holistic or itemized assessment as appropriate.Itemized evaluation targets distinct sub-units; Figure 2 illustrates its use on story outlines.Source: §3.1 · pp. 3–4, Figure 2 · p. 4

3.2 Thought Generator

  • The thought generator uses the task description, current solution, and self-evaluator’s natural-language feedback to generate candidate child nodes with a pretrained language model.The generator can produce k candidates for a thought node.Source: §3.2 · p. 4

3.3 Decision Simulator

  • The decision simulator uses MCTS selection, feedback-guided expansion, random-child rollouts to a set depth, and backpropagated rewards; the highest-average-reward node becomes the output.Selection uses UCB1, which balances node heuristic scores and visit counts; MCTS is described as balancing exploration and exploitation.Source: §3.3 · p. 5

4 Experiments

Across three reasoning tasks, THOUGHTSCULPT is evaluated against established baselines using GPT-3.5 and GPT-4, with DFS included to compare search strategies. Results favor THOUGHTSCULPT across the tasks, while the relative performance of MCTS and DFS varies by task.

4 Experiments

  • The experiments compare CoT, Self-Refine, and ToT with DFS against THOUGHTSCULPT, using GPT-3.5 and GPT-4 as base language models.The authors also test THOUGHTSCULPT with DFS as an alternative to MCTS.Source: §4 · p. 5

4.1 Story Outline Improvement

  • 89.9 and 65.0 average interestingness with THOUGHTSCULPT-MCTS for GPT-3.5 and GPT-4, respectively, accompanied by higher human preference than other baselines.All methods improved interestingness over the initial outline; annotators compared MCTS outputs with ToT or Self-Refine outputs.Source: Table 1 · p. 5, §4.1 · p. 6, Figure 3 · p. 6
  • Only THOUGHTSCULPT-MCTS shows consistent improvement in story-outline interestingness over successive steps; ToT and Self-Refine do not.The authors suggest that Self-Refine’s limited search space and ToT’s lack of revision may contribute to this difference.Source: Figure 4 · p. 6, §4.1 · p. 7

4.2 Mini crosswords

  • With 20 search steps, THOUGHTSCULPT-MCTS is best or comparable across crossword metrics, matching ToT’s reported performance using 100 steps.THOUGHTSCULPT-MCTS requires 1.2x more computation than ToT in this task.Source: Table 2 · p. 7, §4.2 · pp. 7–8

4.3 Constrained Generation

  • 79.6% (DFS, GPT-3.5) and 99.1% (DFS, GPT-4) concept coverage led; MCTS reached 77.9% and 99.0%, respectively, while MCTS was significantly favored in GPT-4 preference evaluation.CommonGen-Hard requires generating a sentence containing 20–30 concepts; both THOUGHTSCULPT and ToT used at most three child candidates per node, with a maximum depth of three.Source: Table 3 · p. 8, §4.3 · p. 8

5 Conclusion

THOUGHTSCULPT supports complex tasks requiring continuous refinement and reasoning without changing the underlying model architecture. Its experiments illustrate potential across diverse tasks that benefit from ongoing thought iteration.

5 Conclusion

  • THOUGHTSCULPT handles complex tasks requiring continuous refinement and reasoning without modifying the underlying model architecture.The framework is intended for tasks that require ongoing refinement and reasoning.Source: §5 · p. 8
  • MCTS lets THOUGHTSCULPT explore vast search spaces while managing computational costs, and the method supports iterative self-revision without extensive prompt engineering.The paper presents MCTS as a way to navigate search efficiently while refining outputs.Source: §5 · p. 8
  • Experiments illustrate THOUGHTSCULPT’s potential across open-ended generation, multi-step reasoning, and creative ideation.The conclusion identifies these as examples of tasks involving continuous thought iteration.Source: §5 · p. 8

Limitations

THOUGHTSCULPT incurs higher computational costs than most sampling methods because it makes multiple calls to the base language model. The authors describe it as most appropriate when tasks require intricate reasoning or the base model performs suboptimally.

Limitations

  • Multiple calls to the base language model make THOUGHTSCULPT more computationally costly than most sampling methods.The authors contrast its cost with that of most sampling methods.Source: Limitations · p. 9
  • When base-model performance is already satisfactory, adopting THOUGHTSCULPT may not be advisable.The authors identify this as a setting where its adoption may not be warranted.Source: Limitations · p. 9
  • The authors see benefits for intricate reasoning, continual improvement, or suboptimal base-model performance, with MCTS balancing exploration and exploitation in complex search.They also state that MCTS addresses scalability concerns and offers computational advantages over alternative search algorithms.Source: Limitations · p. 9

Ethics Statement

The ethics statement describes dataset attribution, acknowledges misuse risks associated with the base models, and notes that THOUGHTSCULPT itself does not prevent harmful content generation.

Ethics Statement

  • The datasets used in the experiments were appropriately sourced and cited.The authors state that dataset use followed academic-integrity and attribution principles.Source: Ethics Statement · p. 9
  • Experiments primarily use GPT-3.5 and GPT-4, whose misuse could involve misinformation, harmful content, or impersonation.The authors call for robust measures to prevent misuse and encourage responsible use.Source: Ethics Statement · p. 9
  • THOUGHTSCULPT has no built-in mechanism to prevent harmful outputs, so users should apply safeguards and appropriate controls.The authors advise users to exercise caution and proactively mitigate harmful-content risks.Source: Ethics Statement · p. 9

Reproducibility

The paper describes reproducibility measures and notes that reliance on the OpenAI API may affect reproducibility if the API changes.

Reproducibility

  • The experiments use publicly accessible datasets, and the story-outline content evaluator is the open-source model Flan-T5.The authors describe these choices as supporting transparency and reproducibility.Source: Reproducibility · p. 9
  • The authors state that their codebase will be made available for reference and validation upon publication.The planned code release is presented as a reproducibility measure.Source: Reproducibility · p. 9
  • Because GPT-3.5 and GPT-4 are accessed through the OpenAI API, changes to that API may affect reproducibility.The authors identify API changes as a possible source of reproducibility variation.Source: Reproducibility · p. 9

A Prompts

The appendix specifies three prompts for generating candidates, evaluating current solutions, and providing task instructions, then tailors them to outline revision, crossword solving, and constrained generation.

A Prompts

  • THOUGHTSCULPT uses TASK_DESCRIPTION, NEW_CANDIDATE, and EVALUATE_CURRENT prompts to describe the task, generate candidates from feedback and the current solution, and evaluate solutions.Evaluation can request itemized feedback, holistic feedback, or both.Source: A Prompts · p. 12

A.1 Task 1 Story Outline Improvement

  • For story-outline generation, the prompt asks for a better outline replacing feedback-suggested items, keeps the original numbered format, and requests a 1-to-100 score based on the task.Source: §A.1 · p. 12
  • For story outlines, the itemized evaluator identifies consecutive items needing revision and assigns an interestingness level from 1 to 5.The prompt asks for reasons and the indices of the items to revise.Source: §A.1 · pp. 12–13

A.2 Task 2 Mini-Crossword Solving

  • The mini-crossword prompt defines a 5 x 5 puzzle with five-letter answers and asks the model to fill the board using the clues.Evaluation feedback can propose answers or corrections for unfilled or potentially mistaken words.Source: §A.2 · pp. 13–14
  • For crossword candidates, the prompt requests possible answers for unfilled or changed words and confidence labels, reserving “certain” for answers believed 100% correct.It allows more than one possible answer.Source: §A.2 · p. 13

A.3 Task 3 Constrained Generation

  • Constrained generation asks for a natural sentence covering all required concepts and evaluates whether it covers them and describes a common daily-life scene.If either condition is unmet, the evaluator requests a reason for further improvement.Source: §A.3 · pp. 14–15
  • For constrained-generation revisions, the candidate prompt supplies the instruction, proposed sentence, and feedback, then asks for a revised solution.The evaluation prompt again judges concept coverage and whether the sentence describes a common scene.Source: §A.3 · p. 14

B Computation Efficiency

This section examines THOUGHTSCULPT’s search variants through their computation costs and procedures, and illustrates how different reasoning strategies produce story-outline and constrained-generation outputs.

B Computation Efficiency

  • THOUGHTSCULPT with DFS has a comparable cost to ToT, while MCTS requires greater computation because it adds a decision-simulation process.Tables 4–6 report estimated input/output token use and cost per case for three tasks, but the supplied passages do not provide cell values.Source: B Computation Efficiency · p. 16, Table 4 · p. 16, Table 5 · p. 16

C Alternative Search Algorithm

  • MCTS selects a leaf using UCB1, expands it with a sampled child, propagates rewards and exploration counts, then returns the highest-reward node.The algorithm repeats this selection-and-expansion process within its search tree.Source: C Alternative Search Algorithm · p. 17
  • DFS expands candidate children, evaluates their rewards, chooses the highest-reward child, and recursively searches to a specified depth.Source: C Alternative Search Algorithm · p. 17

D.1 Story Outline Improvement

  • MCTS generally produces more complex story outlines with twists and characters, while Self Refine changes the initial outline less and ToT and DFS tend to add interesting details.MCTS’s final output may be greatly modified.Source: §D.1 · p. 18

D.1.1 Example 1

  • Example 1 includes differing plot developments, including threats from the Center and a mysterious organization that endanger Jack and Leo.Some supplied outlines culminate in Jack defying the Center to protect Leo and his father, while another introduces a new organization threatening their relationship.Source: §D.1.1 · p. 18

D.1.2 Example 2

  • For one D.1.2 outline, the Boys Club faces closure, the kids pursue a rumored treasure, and the story ends by emphasizing friendship and community.The outline moves through fundraising ideas and a local historian’s account of a lost pirate treasure.Source: §D.1.2 · p. 23

D.2.1 Example 1

  • For the first constrained-generation prompt, THOUGHTSCULPT with MCTS combines sidewalk, graffiti, pottery, bicycle, and other listed concepts in one scene.The passage also shows outputs from Refine, ToT, and THOUGHTSCULPT with DFS for the same prompt.Source: §D.2.1 · p. 24

D.2.2 Example 2

  • For the second constrained-generation prompt, THOUGHTSCULPT with MCTS combines a toddler, plant, hamburger, cowboy, singer, and other listed concepts in a single scene.The passage also shows outputs from Refine, ToT, and THOUGHTSCULPT with DFS for the same prompt.Source: §D.2.2 · p. 24

E G-Eval on Story Outline Generation

On story-outline generation, THOUGHTSCULPT with MCTS outperforms the baselines under G-Eval using either GPT-4 or GPT-3.5. On mini-crosswords, it achieves solid performance in 20 search steps, with an extended comparison using 100 steps.

E G-Eval on Story Outline Generation

F More search steps on Mini-Crosswords

G Constrained Generation LLM Evaluation

GPT-4 significantly favored THOUGHTSCULPT with MCTS in Constrained Generation, and THOUGHTSCULPT outperformed ToT on Game of 24 despite using a more general prompt. Component ablations highlight the role of a strong thought evaluator in providing revision feedback.

G Constrained Generation LLM Evaluation

H Game of 24

  • THOUGHTSCULPT outperformed ToT on Game of 24 despite using a more general prompt than ToT’s detailed few-shot examples.The task uses four numbers and basic arithmetic operations to reach 24; the prompt requests a solution in Python and asks for correctness feedback on the current solution.Source: H Game of 24 · p. 26, §H.1 · p. 26

I Effectiveness of components

  • A strong thought evaluator is critical because its revision feedback significantly enhances the generator’s effectiveness.The component ablation replaced GPT-4 with Llama3.1-8B-Instruct for either the evaluator or generator in Constrained Generation.Source: I Effectiveness of components · p. 27

Related papers

Loading 2404.05966v2…