PaperlayerView exact revision on arXiv

Source-linked AI summary

Tree-of-Mixed-Thought: Combining Fast and Slow Thinking for Multi-hop Visual Reasoning

Pengbo Hu, Ji Qi, Xingyu Li, Hong Li, Xinqi Wang, Bing Quan, Ruiyu Wang, Yi Zhou

arXiv:2308.09658v2cs.CLcs.AIcs.CV

TL;DR

Long-range multi-hop visual reasoning remains underexplored, and plan-searching must balance accuracy with efficiency. The paper combines one-stop generation with Tree-of-thought and evaluates planning using scene-graph datasets and tools. Its ToT-One-Stop strategy matches ToT plan accuracy while saving more than half the reasoning steps across question types.

  • Problem

    Long-range multi-hop visual planning is underexplored, with one-stop generation favoring efficiency and iterative search methods requiring more steps to improve planning accuracy.

    Source: §1 · pp. 1–2

  • Method

    The paper combines one-stop generation with Tree-of-thought strategies and uses scene-graph tools to evaluate multi-hop visual planning.

    Source: §1 · p. 2

  • Results

    ToT-One-Stop matches ToT plan accuracy while saving more than half the reasoning steps across all types of questions.

    Source: §4.2 · p. 5

  • Takeaways & Limitations

    Scene-graph tools can accurately extract visual information, supporting direct evaluation of LLM capabilities on long-range multi-hop reasoning tasks.

    Source: §1 · p. 2

    Evaluation criteria can classify plans as accurate without guaranteeing correct final answers, and efficient evaluation of search nodes remains challenging.

    Source: §3.3.4 · p. 5, §5 · p. 8

Abstract

from arXiv · show

There emerges a promising trend of using large language models (LLMs) to generate code-like plans for complex inference tasks such as visual reasoning. This paradigm, known as LLM-based planning, provides flexibility in problem solving and endows better interpretability. However, current research is mostly limited to basic scenarios of simple questions that can be straightforward answered in a few inference steps. Planning for the more challenging multi-hop visual reasoning tasks remains under-explored. Specifically, under multi-hop reasoning situations, the trade-off between accuracy and the complexity of plan-searching becomes prominent. The prevailing algorithms either address the efficiency issue by employing the fast one-stop generation or adopt a complex iterative generation method to improve accuracy. Both fail to balance the need for efficiency and performance. Drawing inspiration from the dual system of cognition in the human brain, the fast and the slow think processes, we propose a hierarchical plan-searching algorithm that integrates the one-stop reasoning (fast) and the Tree-of-thought (slow). Our approach succeeds in performance while significantly saving inference steps. Moreover, we repurpose the PTR and the CLEVER datasets, developing a systematic framework for evaluating the performance and efficiency of LLMs-based plan-search algorithms under reasoning tasks at different levels of difficulty. Extensive experiments demonstrate the superiority of our proposed algorithm in terms of performance and efficiency. The dataset and code will be release soon.

1. Introduction

Long-range multi-hop visual planning exposes a trade-off: one-stop generation is efficient but may lack precision, while Tree-of-thought can search long plans at substantial cost. The paper combines these approaches and develops scene-graph tools and an evaluation dataset for assessing LLM planning.

1. Introduction

  • Tree-of-thought supports long-range plans through iterative search and backtracking, but repeated LLM visits consume time and computational resources.One-stop generation uses a single visit to produce a whole plan, but its plans may lack precision.Source: §1 · pp. 1–2
  • The dataset varies inference structures and hop counts to evaluate long-range planning across visual-reasoning questions of different difficulty.Scene graphs let the tools extract visual information for evaluating language-model capabilities directly.Source: §1 · pp. 2–3
  • The proposed strategies combine Tree-of-thought and one-stop generation, reducing LLM re-evaluation steps while maintaining accuracy.The introduction reports that experiments demonstrate the approach’s effectiveness.Source: §1 · pp. 2–3
  • The evaluation dataset uses scene-graph tools to assess LLM multi-hop reasoning without errors from a visual expert module.It covers four reasoning structures and nine question types.Source: §1 · pp. 2–3, Figure 1 · p. 2

2. Related work

Prior LLM planning approaches include one-stop, iterative, and tree-of-thought generation, with tree search enabling backtracking but requiring more LLM visits. Visual-reasoning work has largely addressed questions needing only a few plan-generation steps, while this paper emphasizes long-range multi-hop tasks.

2.1. Plan Generation with LLMs.

  • Tree-of-thought adds backtracking and iterative search over plan trajectories, but usually requires more LLM visits than one-stop or iterative generation.The paper’s hybrid approach aims to preserve tree-of-thought’s backtracking and iteration while saving inference steps.Source: §2.1 · p. 3

2.2. Visual Reasoning with LLMs

  • Prior code-like visual-reasoning approaches use iterative plan generation and focus on relatively straightforward questions requiring only a few steps.This study emphasizes challenging long-range multi-hop visual reasoning.Source: §2.2 · p. 3

3. Method

The method evaluates long-range visual planning with scene-graph tools and combines one-stop generation with Tree-of-Thought search. Its ToMT variants reduce search steps by generating either all remaining plans at a selected node or a multi-step block at each node.

3.1. Dataset and Evaluation

  • PTR and CLEVR provide varied multi-hop questions and complete scene graphs, enabling evaluation through tools that access visual information directly.The dataset design considers question hop counts and reasoning structures; scene-graph interaction avoids reliance on visual expert models.Source: §3.1 · p. 3

3.2. Baseline

  • The baselines are one-stop generation and Tree-of-Thought, the two approaches that ToMT integrates.The paper describes one-stop generation as producing a complete plan in one LLM reasoning step and ToT as searching among atomic-plan trajectories.Source: §3.2 · p. 3, §3.2.1 · p. 3, §3.2.2 · p. 4

3.2.1. ONE-STOP

  • One-stop generation produces the complete plan in one LLM reasoning step, while its accuracy is limited by next-token prediction.Source: §3.2.1 · pp. 3–4

3.2.2. TREE-OF-THOUGHT(TOT)

  • Tree-of-Thought searches for a plan trajectory by generating alternative atomic plans and evaluating them against set rules.The method uses depth-first search.Source: §3.2.2 · p. 4

3.3. Tree-of-Mixed-Thought(ToMT)

  • ToMT combines one-stop generation with Tree-of-Thought search to reduce search steps while retaining search over plans.ToT-One-Stop generates the remaining plans when a suitable plan is found; ToT-Block generates multiple plans at each node.Source: §3.3 · p. 4, §3.3.1 · p. 4, §3.3.2 · p. 4

3.3.1. TOT-ONE-STOP(TOT-OS)

  • ToT-One-Stop greedily generates all remaining plans from a suitable ToT node, continuing search if those plans fail predefined rules.The search stops at the maximum step or when a stop sign is detected.Source: §3.3.1 · p. 4

3.3.2. TOT-BLOCK

  • ToT-Block generates multiple plans per node, shortening the search path; a four-hop question may take two iterations with block size two instead of at least four.Source: §3.3.2 · p. 4

3.3.3. GENERATOR

  • The generator uses prior steps as prompt guidance, samples demonstrations to diversify search paths, and generates either a single plan, all remaining plans, or the next k plans.ToT-Block generates the next k-plan sequence at each generation.Source: §3.3.3 · p. 4

4. Experiments and discussion

Across question structures and hop lengths, ToT-OS retains ToT-level plan accuracy while using fewer reasoning steps; ToT-Block offers a more structured alternative. Results also expose challenges in chained, spatial, and semantic reasoning, alongside efficiency–accuracy trade-offs in the ablations.

4.2. Main Results

  • ToT-Block has performance similar to ToT and ToT-OS but generally saves fewer steps than ToT-OS; on Sequence questions it matches ToT accuracy with RSSI above 1.5.Its fixed-size, multi-step blocks are more structured and conservative than ToT-OS's greedy fast-thinking use.Source: §4.2 · p. 5, Table 1 · p. 6
  • ToT-OS matches ToT plan accuracy while saving over half the reasoning steps across question types, slightly improving accuracy except on Long relation.ToT required 17.24 steps on Long relation and 12.81 on Logic, versus 9.63 and 5.50 for ToT-OS, respectively; its RSSI exceeds 1.7 throughout and peaks at 2.89 on Compare. Experiments used ChatGPT (chat-gpt-tubor-0631) at temperature 1, averaged three runs, and capped depth-first search at 30 steps; branching factors were 3 for ToT and ToT-OS and 5 for ToT-Block.Source: §4.2 · p. 5, §4.1 · p. 5, Table 1 · p. 6

4.3.1. QUESTION TYPES

  • Sequence reasoning had the lowest performance across algorithms; within Parallel questions, ToT-OS made no Sum errors but reached only 63% accuracy on Compare.Question topology generally did not determine plan accuracy, and performance varied substantially within a question type.Source: §4.3.1 · p. 6

4.3.2. HOP NUMBER

  • As hop number rises, fast-thinking plan accuracy correlates negatively—most strongly for One-Stop—while ToT and ToT-Block step counts correlate positively, unlike ToT-OS.The authors attribute the step-count contrast to ToT and ToT-Block retaining tree-search structure while greedy one-stop use in ToT-OS breaks it.Source: §4.3.2 · pp. 6–7

4.3.3. SPATIAL RELATION

  • Short Rel, Long Rel, and Logic questions challenge all methods with long spatial-reasoning sequences; the authors point to spatial understanding and long-chain inference difficulties.Source: §4.3.3 · p. 7

4.3.4. SEMANTIC ISSUE

  • Query Part errors often collapse compositional parts, while Compare errors often select the wrong branches.Adding relevant object-part knowledge may reduce fact-oriented errors; the authors suggest external knowledge bases for fact-oriented deficiencies and logic-aware systems for logic-oriented deficiencies, while noting a complete solution may require changing the next-token prediction paradigm.Source: §4.3.4 · pp. 7–8

4.3.5. BACKTRACKING AND CONSISTENCY

  • Harder, higher-hop questions rely more on backtracking; Table 4's inconsistency count measures incorrect executable plans and should not be confused with question hardness.Long Rel and Logic questions need backtracking for almost all questions, while the two types can have comparable inconsistency counts despite differing in difficulty.Source: Table 4 · p. 7, §4.3.5 · p. 8

4.4.1. WHEN TO START ONE-STOP SEARCH.; 4.4.2. BLOCK SIZE

  • ToT-OS performs best with start depth d=2; larger ToT-Block sizes consistently reduce steps but generally lower plan accuracy.Starting fast thinking too early raises the chance incorrect plans pass the sanity check; starting too deep limits its efficiency benefit.Source: Table 5 · p. 7, §4.4.1 · p. 8, §4.4.2 · p. 8

5. Conclusion

The paper combines one-stop generation with Tree-of-Thought (ToT) in two strategies that reduce search steps while preserving backtracking and iterative generation. It reports better accuracy and fewer inference steps than ToT for most test problems, while noting evaluation and real-world tool-accuracy constraints.

5. Conclusion

  • The two strategies integrate one-stop generation and ToT, reducing search steps and resource consumption while preserving ToT’s backtracking and iterative generation.Source: §5 · p. 8
  • The proposed approach outperforms ToT in accuracy and inference steps for most test problems.Source: §5 · p. 8
  • Evaluation uses scene graphs to assess LLM accuracy with accurate tools, while real-world expert modules may have uncertain accuracy.Source: §5 · p. 8
  • The authors identify the need for an efficient method to determine whether a search node meets requirements as a limitation shared with ToT.Source: §5 · p. 8

A.1. Dataset Details

The dataset details identify question types drawn from PTR and CLEVR and group them by reasoning structure.

A.1. Dataset Details

  • The repurposed dataset includes seven PTR question types and two CLEVR question types, grouped into four categories by reasoning structure.Source: §A.1 · p. 10

1. Short Sptatial Relation

The examples show questions represented as sequences of scene-graph operations, spanning spatial relations, counting, comparison, logic, and analogy. A separate note describes differences in the scene graphs used for PTR and CLEVR.

1. Short Sptatial Relation

  • The short spatial-relation example filters for a table and its six red drawers, queries what is behind it, then counts the objects found.Source: §1 · p. 10

2. Long Spatial Relation

  • The long spatial-relation example chains relation queries and object filters to identify a yellow ball, then asks for its size.Source: §2 · p. 10

1. Sum

  • The Sum example counts drawers and doors associated with differently described tables, then sums the counts.Source: §1 · p. 10

2. Compare

  • The Compare example counts wheels and legs, then tests whether the two counts are equal.Source: §2 · pp. 10–11

3. Logic Both

  • The Logic Both example intersects objects satisfying right-of and in-front-of relations, filters for metal, and queries color.Source: §3 · p. 11

1. Query Part; 2. Exist; 3. Count

  • The Query Part, Exist, and Count examples respectively query a part by category, test for objects matching a part count, and count legs after matching seat color.Source: §1 · p. 11, §2 · p. 11, §3 · p. 11

1. Analogy

  • The Analogy example infers a positional relation between beds, applies it to an object with eight leg bars, and counts matching objects.Source: §1 · p. 12

A.2. Scene Graph Example

  • PTR scene graphs use object numbers to indicate part numbers, whereas CLEVR scene graphs include color, size, and material attributes.Source: §A.2 · p. 12

A.2.1. PTR DATASET

The PTR dataset example pairs a question and answer with a scene graph listing object attributes and spatial relationships.

A.2.1. PTR DATASET

  • The example’s scene graph lists object parts and attributes alongside pairwise spatial relations, supporting the answer “Chair” to the analogy question.Source: §A.2.1 · p. 12

A.2.2. CLEVR DATASET

The appendix illustrates CLEVR scene-graph data, describes the tool operations used for reasoning, and specifies a shared prompt format with worked code-plan examples.

A.2.2. CLEVR DATASET

  • The CLEVR example represents a question with object attributes and pairwise spatial relations in a scene graph.The example asks for an object's color based on its position relative to two reference objects.Source: §A.2.2 · pp. 12–13

A.3. Tools Details

  • The tools are grouped into Filter, Algebra, Relation, and Attribution categories to support scene-graph interaction and specific operations.The described operations include sum, comparison, and counting.Source: §A.3 · p. 13

A.3.1. FILTER

  • Filter tools select objects by category or attributes, retrieve relations, and exclude objects from a list.The listed functions include filter_object, filter_part, get_relation, exclude_object, and filter_category.Source: §A.3.1 · p. 13

A.3.2. ALGEBRA

  • Algebra tools count parts or objects, sum numbers, compare values, and intersect object lists.The listed comparisons include equality, greater-than, and less-than checks.Source: §A.3.2 · pp. 13–14

A.3.3. RELATION

  • Relation tools query what bears a relation to an object, filter a list by relation, and retrieve the relation between two objects.Source: §A.3.3 · p. 14

A.3.4. ATTRIBUTION

  • Attribution tools query an object's or part's category, a part's color or category, and an object's size.Source: §A.3.4 · p. 14

A.4. Prompt Details

  • Experiments use a prompt containing instructions, tool descriptions, examples, and a question, with four examples in the shared structure.The template places those four components in that order.Source: §A.4 · p. 14, Prompt Template · p. 14

Prompt Template

  • The prompt asks for Python code listing solution steps, with worked examples applying object and relation operations to answer questions.The examples include counting objects, testing existence, and querying a category.Source: Prompt Template · pp. 14–15

B. Experiment on Low Resource Setting

The section reports that the method generally outperforms under step limits, with a Long Rel exception at 30 steps and an advantage over naive ToT at tighter limits.

B. Experiment on Low Resource Setting

  • At max step 30, the method outperforms on most question types but is a little lower on Long Rel; at 10 or 20 steps, it significantly outperforms naive ToT.The reported comparison is framed as evidence of efficacy in low-resource scenarios.Source: Table 6 · p. 16, B. Experiment on Low Resource Setting · p. 16

Related papers

Loading 2308.09658v2…