Chopping Trees: Semantic Similarity Based Dynamic Pruning for Tree-of-Thought Reasoning

• URL: http://arxiv.org/abs/2511.08595v1
• Date: Thu, 30 Oct 2025 17:18:45 GMT
• Title: Chopping Trees: Semantic Similarity Based Dynamic Pruning for Tree-of-Thought Reasoning
• Authors: Joongho Kim, Xirui Huang, Zarreen Reza, Gabriel Grand, Kevin Zhu, Ryan Lagasse,
• Abstract summary: Tree-of-Thought (ToT) reasoning boosts the problem-solving abilities of Large Language Models (LLMs)<n>We introduce Semantic Similarity-Based Dynamic Pruning (SSDP), a lightweight method that integrates online semantic merging into parallelized tree search.<n>SSDP achieves up to a 2.3x speedup over state-of-the-art tree-search baselines while maintaining competitive accuracy.
• Score: 5.347273439141959
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Tree-of-Thought (ToT) reasoning boosts the problem-solving abilities of Large Language Models (LLMs) but is computationally expensive due to semantic redundancy, where distinct branches explore equivalent reasoning paths. We introduce Semantic Similarity-Based Dynamic Pruning (SSDP), a lightweight method that, to the best of our knowledge, is the first framework to integrate online semantic merging into parallelized tree search, enabling the clustering and pruning of redundant steps in real time. Across reasoning benchmarks, including GSM8K and MATH500, SSDP achieves up to a 2.3x speedup over state-of-the-art tree-search baselines while maintaining competitive accuracy (typically within 5% of the strongest baseline) and reducing the number of explored nodes by 85-90%, demonstrating a practical approach to efficient, scalable LLM reasoning. The implementation of SSDP is publicly available at https://github.com/kimjoonghokim/SSDP.

Related papers

• TreePS-RAG: Tree-based Process Supervision for Reinforcement Learning in Agentic RAG [71.06073770344732]
  Agentic retrieval-augmented generation (RAG) formulates question answering as a multi-step interaction between reasoning and information retrieval.<n>We present TreePS-RAG, an online, tree-based RL framework for agentic RAG that enables step-wise credit assignment while retaining outcome-only rewards.
  arXiv  Detail & Related papers  (2026-01-11T14:07:30Z)
• MITS: Enhanced Tree Search Reasoning for LLMs via Pointwise Mutual Information [32.43291637979958]
  We propose Mutual Information Tree Search (MITS), a novel framework that guides reasoning with information-theoretic principles.<n>MITS introduces an effective scoring function based on pointwise mutual information (PMI), which enables step-wise evaluation of reasoning paths and search tree expansion.<n>For final prediction, MITS employs a weighted voting scheme that combines PMI scores with prediction consensus.
  arXiv  Detail & Related papers  (2025-10-04T02:30:40Z)
• Chain-in-Tree: Back to Sequential Reasoning in LLM Tree Search [4.12237459236889]
  Chain-in-Tree (CiT) is a framework that decides when to branch during search rather than expanding at every step.<n>It achieves 75-85% reductions in token generation, model calls, and runtime on GSM8K and Math500.
  arXiv  Detail & Related papers  (2025-09-30T06:18:44Z)
• TreePO: Bridging the Gap of Policy Optimization and Efficacy and Inference Efficiency with Heuristic Tree-based Modeling [65.46347858249295]
  TreePO is a self-guided rollout algorithm that views sequence generation as a tree-structured searching process.<n>TreePO essentially reduces the per-update compute burden while preserving or enhancing exploration diversity.
  arXiv  Detail & Related papers  (2025-08-24T16:52:37Z)
• TreeRPO: Tree Relative Policy Optimization [65.51935468270916]
  name is a novel method that estimates the mathematical expectations of rewards at various reasoning steps using tree sampling.<n>Building on the group-relative reward training mechanism of GRPO, name innovatively computes rewards based on step-level groups generated during tree sampling.
  arXiv  Detail & Related papers  (2025-06-05T15:56:38Z)
• Dynamic Parallel Tree Search for Efficient LLM Reasoning [102.16694475391665]
  Tree of Thoughts (ToT) enhances Large Language Model (LLM) reasoning by structuring problem-solving as a spanning tree.<n>We propose Dynamic Parallel Tree Search (DPTS), a novel parallelism framework that aims to dynamically optimize the reasoning path in inference.<n> Experiments on Qwen-2.5 and Llama-3 with Math500 and GSM8K datasets show that DPTS significantly improves efficiency by 2-4x on average.
  arXiv  Detail & Related papers  (2025-02-22T14:13:37Z)
• Don't Get Lost in the Trees: Streamlining LLM Reasoning by Overcoming Tree Search Exploration Pitfalls [83.89771461061903]
  Recent advancements in tree search algorithms guided by verifiers have significantly enhanced the reasoning capabilities of large language models (LLMs)<n>Recent advancements in tree search algorithms guided by verifiers have significantly enhanced the reasoning capabilities of large language models (LLMs)<n>We identify two key challenges contributing to this inefficiency: $textitover-exploration$ due to redundant states with semantically equivalent content, and $textitunder-exploration$ caused by high variance in verifier scoring.<n>We propose FETCH, a flexible, plug-and-play system compatible with various tree search algorithms.
  arXiv  Detail & Related papers  (2025-02-16T16:12:01Z)
• LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
  This study introduces a novel guided tree search algorithm with dynamic node selection and node-level exploration budget. Experiments conducted on the GSM8K and TabMWP datasets demonstrate that our approach enjoys significantly lower computational costs compared to baseline methods.
  arXiv  Detail & Related papers  (2024-06-29T05:14:04Z)
• Parallel Tree Kernel Computation [0.0]
  We devise a parallel implementation of the sequential algorithm for the computation of some tree kernels of two finite sets of trees. Results show that the proposed parallel algorithm outperforms the sequential one in terms of latency.
  arXiv  Detail & Related papers  (2023-05-12T18:16:45Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.