Technical Summary: Novelty-based Tree-of-Thought Search for LLM Reasoning and Planning

Problem Statement

While Large Language Models (LLMs) have demonstrated significant capabilities in language-based tasks, they remain brittle in complex reasoning and long-term planning. Naive prompting often fails, and structured approaches like Tree-of-Thought (ToT) suffer from exponential runtime and token costs due to unpruned branching search. Conversely, classical planning algorithms, specifically width-based planners like Iterative Width (IW), achieve efficiency by pruning states based on a "novelty" measure, but they require rigid, formalized problem structures (e.g., PDDL) that do not translate well to natural language settings. The core challenge addressed by this work is defining an analogous notion of novelty within the unstructured language domain to enable efficient pruning in ToT without sacrificing the flexibility of LLMs.

Methodology

The authors propose a planning algorithm that integrates novelty-based pruning into the ToT framework. The approach decomposes the planning process into four sub-tasks:

1. Action Generation: The LLM proposes possible next actions from a current state.
2. Successor State Mapping: The LLM maps actions to resulting states.
3. Plan Verification: The model determines if a state sequence satisfies the goal.
4. Novelty Estimation: The novel contribution, where the LLM acts as a novelty estimator.

Novelty Estimation and Pruning

Unlike classical planners that calculate novelty as an integer based on boolean feature subsets, this method adapts novelty to natural language. The LLM is queried with a binary "yes/no" question to determine if a new state is novel compared to a list of previously visited states. This leverages the model's pre-trained general knowledge and semantic understanding to identify unique states without requiring explicit atom definitions or few-shot examples.

The search tree can be traversed using either Breadth-First Search (BFS) or Depth-First Search (DFS). While classical IW typically uses BFS, the authors note that in LLM contexts, BFS can lead to exponential cost growth; thus, the trade-offs between BFS and DFS are evaluated. The method is designed to be domain-agnostic, relying only on a hand-crafted context prompt explaining domain rules, avoiding domain-specific prompt engineering for the novelty estimator itself.

Key Contributions

1. Novelty Adaptation for LLMs: The paper proposes a measurable concept of novelty for language domains, utilizing the LLM's internalized semantic knowledge to prune search branches based on state uniqueness rather than rigid feature matching.
2. Domain-Agnostic Framework: A general implementation is developed that allows for flexible experimentation across different domains (planning and reasoning) with minimal manual effort, requiring only a change in the context prompt for the domain rules.
3. Sub-task Evaluation: The authors introduce a dedicated evaluation framework inspired by Plan-Bench to test the four sub-tasks (action generation, state mapping, verification, and novelty estimation) independently against ground truths generated by classical planners.
4. Empirical Analysis of Prompting: The work highlights the sensitivity of LLM planning to prompt design, specifically identifying recurring failure points (e.g., distinguishing between "pick-up" and "unstack" in Blocksworld) and demonstrating how targeted prompt extensions can significantly improve performance.

Experimental Results

The approach was evaluated on the Blocksworld and Logistics planning domains, as well as the MATH benchmark (Level 5 difficulty).

• Sub-task Performance: Using the Qwen3 14B model, the "Thinking Mode" (reasoning tokens) and Natural Language prompting generally yielded the best results. The model successfully performed novelty pruning in standard scenarios but struggled with a harder variant involving non-duplicate states that required strict width-based reasoning.
• Token Efficiency: In well-configured settings (specifically using "Thinking Mode" and "Direct" action/state mapping), the novelty-pruned ToT reduced token costs by up to 20 times compared to standard ToT while maintaining similar success rates. For example, in Blocksworld with DFS and Thinking Mode, the base ToT averaged 330k tokens, whereas the novelty-pruned version averaged 18k tokens.
• Generalizability: The method transferred effectively to the Logistics domain and the MATH benchmark without re-tuning the novelty estimation prompts, though optimal token efficiency in distinct reasoning domains (like MATH) appeared to require domain-specific prompt tuning.
• Limitations: In poorly configured settings, performance degraded significantly, with solve rates near zero and token costs increasing by over 100% due to the overhead of novelty queries. The method relies heavily on the base performance of the underlying ToT configuration.

Significance and Claims

The paper claims that novelty-based pruning can successfully improve the efficiency of Tree-of-Thought reasoning, making it viable for complex planning tasks by drastically reducing the search space and token consumption. The authors emphasize that while the method diverges from classical width-based planning by lacking formal guarantees on solution quality or precise novelty computation, it offers a practical, flexible alternative that leverages LLM adaptability.

However, the authors remain modest regarding the robustness of the approach. They note that the instability of recursive LLM prompting remains a fundamental challenge, making configuration laborious and unpredictable. The pruning behavior is observed to be driven largely by duplicate detection rather than true "novelty" reasoning in complex scenarios. Consequently, the work is presented as a step toward more efficient LLM planning, suggesting future directions such as goal serialization, alternative novelty estimators, or the use of larger base models to enhance state understanding.