Tree Search

Follow this topic Ask about this topic

Tree search represents possible decisions as branches and allocates effort among them to find a path to a goal or a strong strategy. Methods include A* and best-first search with heuristics, Monte Carlo tree search with value estimates, bidirectional search, and learned policies that guide which branches to expand or prune. These approaches are used in motion and classical planning, games, optimization, and language-model agents that reason, use tools, or generate code. A central challenge is balancing broad exploration against costly evaluation and rollout budgets, while ensuring that pruning does not discard useful solutions or undermine guarantees.

Latest papers

57 papers6 papers in the last four weeks, up 20% on the four weeks before. 0.0% of all new papers.

Solving Flood-It Puzzles: A Comparison of Tailored A* Search with Declarative Solver Approaches
Oct 22, 2026Philipp von Manteuffel, Benjamin BlankertzTree Search Constraint Programming
Chair for Neurotechnology Technische Universität Berlin
AtomSearch: Evidence-Grounded Tree Search for Agent Skill Optimization
Oct 14, 2026Jia Tong, Senyou Deng, Min Peng +1LLM Agent Skill Learning LLM Agent Self-Improvement
Security Technology Inc. Beijing, China
KNN Implementation Details Can Dramatically Change Performance: An Example from Cover Trees
Oct 12, 2026Amol Khanna, Edward RaffExact Nearest Neighbor Search k-Nearest Neighbors
CrowdStrike · University of Maryland, Baltimore County · Syracuse University
nanoflann: A Header-Only KD-Tree Library for Exact Nearest-Neighbor Search on Compile-Time Product Manifolds
Oct 10, 2026José Luis Blanco-ClaracoExact Nearest Neighbor Search Tree Search
the Department of Engineering, CIESOL, CeiA3. University of Almería, 04120, Almería, Spain
TreeHCA: Hindsight-Guided Exploration and Credit Assignment for Multi-Turn LLM Agents
Oct 9, 2026Debajoy Mukherjee, Jeremy Carleton, Sushil Vemuri +2LLM Agent Training RL for LLM Agents
Department of Electrical and Computer Engineering, Texas A&M University, College Station, Texas, USA
OPTS-TTPO: Enhancing Finite-Sample Policy-Gradient Learning with Tree Search
Sep 30, 2026Junyu Lu, Shichao Weng, Zhiqiang Wang +10Tree Search Policy Gradient Methods
Dobot Robotics · Independent Researcher · Zhejiang University +2
Expansion Counts under Standard A* Tie-Breaking Strategies on the Final Plateau
Sep 20, 2026Alex FukunagaTree Search
The University of Tokyo
Literati: Towards Anytime Optimal Shape Generalized Trees via AO*
Sep 8, 2026Nakul Upadhya, Eldan CohenTree Search Decision Tree Learning
Department of Mechanical and Industrial Engineering University of Toronto, Toronto, Canada
LATS: Levy Adaptive Tree Sampling for Feedback-Driven Diverse Target Discovery
Sep 6, 2026Binglin Ji, Anindya Sarkar, Hengchang Lu +3Adaptive Sampling Diffusion Sampling
Department of CSE, Washington University in St.Louis, USA
Probabilistic Focal Search: Accelerating Bounded-Suboptimal Search via Lower-Bound Advancement
Sep 6, 2026Minh Vu Duc, Trung Le Huu, Hà Minh Hoàng +3Tree Search
SLSCM Lab, National Economics University · University of Warwick · DataOpt Lab, National Economics University +2
AIBuildAI-2.5: Efficient Autonomous AI Model Development Through LLM-Guided Tree Search
Sep 6, 2026Peijia Qin, Ruiyi Zhang, Qi Cao +3Language Model-Guided Search Heuristics Automated Machine Learning
Department of Electrical and Computer Engineering, University of California San Diego, La Jolla, CA 92093, USA · Department of Medicine, University of California San Diego, La Jolla, CA 92093, USA
Dispersive Forward Tree Search for Optimal Control: Coverage, Complexity, and Computation
Aug 26, 2026Shashank A. Deshpande, Jonathan P. HowDifferential Flatness Kinodynamic Motion Planning
Department of Aeronautics and Astronautics, Massachusetts Institute of Technology, Cambridge, MA, USA
ParallelWorld: Test-Time Scaling for Agentic Embodied Reasoning
Aug 24, 2026Min Chen, Shengjun Zhang, Yuxin Li +4Embodied Reasoning Test-Time Scaling
Tsinghua University · National University of Singapore
Class-Based Heuristic Selection for Solving the Flying Block Puzzle
Aug 20, 2026Sanyar Ahmadi, Pedram Asadzadeh, Amanj KhorramianTree Search Constraint Satisfaction
Faculty of Computer Engineering University of Tehran Tehran, Iran · Faculty of Computer Engineering K. N. Toosi University of Technology Tehran, Iran · Department of Electrical and Computer Engineering University of Kurdistan Sanandaj, Iran
CEDAR: Agent-Orchestrated Tree Search for Goal-Directed Optimization of Complex Systems
Aug 7, 2026Yingtao TianLanguage Model-Guided Search Heuristics Artificial Life
Sakana AI, Tokyo, Japan
Approximate Multi-Objective Search Under Rulebooks
Aug 5, 2026Omar Muhammetkulyyev, Oren Salzman, Tichakorn WongpiromsarnTree Search Multi-Objective Optimization
Iowa State University, Ames IA 50010, USA · Technion - Israel Institute of Technology, Haifa 3200003, Israel
Learning Lookahead Lemmas for Neural Network Verification
Jul 31, 2026Liam Davis, Haoze WuNeural Network Verification ReLU Neural Networks
Amherst College
TreeThink: A Modular Tree Search Library for Mathematical Reasoning with LLMs
Jul 13, 2026Burak S. Akbudak, Zeynel A. Uluşan, Can S. Erer +1Automated Theorem Proving Tree Search
Computer Engineering Department, Bogazici University, Istanbul, Turkey · Computer Engineering Department, Koç University, Istanbul, Turkey · Codeway Studios, Istanbul, Turkey +2
GATS: Graph-Augmented Tree Search with Layered World Models for Efficient Agent Planning
Jul 9, 2026Maureese Williams, Dymitr NowickiTree Search World Model-Based Planning
Institute for Cybernetics of NAS of Ukraine
Offline Nash Solvers Meet Online Tree Search in Multi-Agent Games on Graphs
Jul 9, 2026Mukesh Kumar, Yue Guan, Panagiotis TsiotrasNash Equilibrium Tree Search
School of Aerospace Engineering, Georgia Institute of Technology, Atlanta, GA, USA
Search, Fail, Recover: A Training Framework for Correction-Aware Reasoning
Jul 8, 2026Dmitry Beresnev, Vladimir Makharev, Roman Khalikov +2LLM Self-Correction Inference-Time Search
Innopolis University, Innopolis, Russia · AXXX, Moscow, Russia · Lomonosov Moscow State University, Moscow, Russia
Information Gain-based Rollout Policy Optimization: An Adaptive Tree-Structured Rollout Approach for Multi-Turn Search Agents
Jul 7, 2026Yijun Zhang, Fan Xu, Jiaxin Ding +3Tree Search RL for Language Model Reasoning
Shanghai Jiao Tong University
Dual-Informed Vertical Expansion for Multi-Objective Node Selection in Anytime Conflict-Based Search
Jun 30, 2026Willem van Osselaer, Jiarui Li, Meshal Alharbi +1Branch and Bound Tree Search
Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, MA, USA
LLM-Aided A* Search in Non-Geometric Network Graphs
Jun 22, 2026Nouf Alabbasi, Esraa Ghourab, Omar AlhusseinLanguage Model-Guided Search Heuristics Tree Search
KU 6G Research Centre, Department of Computer Science, Khalifa University, Abu Dhabi, UAE
CLARITree: Cholesky and Lookahead Accelerations for Regression with Interpretable Piecewise Linear Trees
Jun 11, 2026Yixiao Wang, Hayden McTavish, Varun Babbar +2Tree Search Interpretable ML
Department of Computer Science, Duke University, Durham, USA · Department of Computer Science, University of British Columbia, Vancouver, Canada
TreeSeeker: Tree-Structured Trial, Error, and Return in Deep Search
Jun 10, 2026Zhuofan Shi, Mingzhe Ma, Lu Wang +8Inference-Time Search Exploration-Exploitation Tradeoff
1Microsoft · 2East China Normal University
Front-to-Attractors: Modifying the Front-to-Front Heuristic in Bidirectional Search
Jun 5, 2026Alvin Zou, Muhammad Suhail Saleem, Maxim LikhachevTree Search
Carnegie Mellon University
Bidirectional Search for Longest Paths: Case for Front-to-Front Heuristics
Jun 4, 2026Tzur Shubi, Ariel Felner, Solomon Eyal Shimony +1Branch and Bound Tree Search
Stein Faculty of Computer and Information Science, Ben-Gurion University of the Negev, Israel
Evaluation of Baseline Methods for IDD-based SSD External Memory Search
Jun 1, 2026Yuki Suzuki, Alex FukunagaTree Search Hierarchical Memory
The University of Tokyo
Efficient Test-time Inference for Generative Planning Models with OCL Search
May 30, 2026Robert Gieselmann, Mihai Samson, Federico Pecora +1Inference-Time Search Efficient Inference
1Amazon · 2Work done while at Amazon.

Oct 22, 2026J/K move · Enter open · S save

Solving Flood-It Puzzles: A Comparison of Tailored A* Search with Declarative Solver Approaches

Philipp von Manteuffel, Benjamin Blankertz

Chair for Neurotechnology Technische Universität Berlin

Tree Search Constraint Programming

Open paper AskPDF arXiv

We present an optimized approach for finding minimal move sequences to solve Flood-It puzzles using A* search and compare it with approaches using SAT, Integer Programming, and Constraint Programming solvers. The performance of A* search is considerably improved by using an appropriate heuristic and sophisticated equivalences of game states to limit the search space. Each aspect is systematically evaluated, providing insights that generalize to other problems. By comparing the best variant of each approach, the A* search is the fastest in finding a minimal solution in about 75 % of the Flood-It instances tested. This result is in line with our expectation since A* specifically looks for a minimum solution. In contrast, the SAT-based approach is designed to solve the decision problem of whether a solution with a given length exists. An iterative search is required to determine a minimum solution length using a SAT-based approach. However, with increasing complexity, quantified by the minimum solution length, the SAT-based approach outperforms A*. We also compared the different approaches to the decision problem, where A* again performed best for the largest number of puzzles. Here, again, SAT supersedes A* for higher complexities, albeit with a lower crossing point.