Tree Search

Follow this topic Ask about this topic

Momentum

3 papers in the last four weeks, with none the four weeks before. 0.0% of all new papers.

Jul 13Week of Sep 28

Latest papers 35

All topics

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
Probabilistic Focal Search: Accelerating Bounded-Suboptimal Search via Lower-Bound Advancement
Sep 12, 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
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
CEDAR: Agent-Orchestrated Tree Search for Goal-Directed Optimization of Complex Systems
Aug 7, 2026Yingtao TianArtificial Life Tree Search
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 AlhusseinTree Search Graph-Based Planning
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.
TAPS: Target-Aware Prefix Tree Selection for Diffusion-Drafted Speculative Decoding
May 30, 2026Zhuoyu Wang, Junnan Huang, Xinyu ChenTree Search Speculative Decoding
The Hong Kong University of Science and Technology (Guangzhou)
Agentic Transformers Provably Learn to Search via Reinforcement Learning
May 29, 2026Tong Yang, Yu Huang, Yingbin Liang +1Policy Gradient Agentic RL
Department of Electrical and Computer Engineering, Carnegie Mellon University · Department of Statistics and Data Science, Wharton School, University of Pennsylvania · Department of Electrical and Computer Engineering, The Ohio State University +1
Structure-Induced Information for Rerooting Levin Tree Search
May 28, 2026Jake Tuero, Michael Buro, Laurent Orseau +1Inference-Time Search Tree Search
Department of Computing Science, University of Alberta, Edmonton, Canada. · Alberta Machine Intelligence Institute (Amii), Edmonton, Canada. · Google DeepMind, London, United Kingdom.
Bidirectional Incremental Generalized Hybrid A*
May 28, 2026Sidharth Talia, Oren Salzman, Siddhartha SrinivasaKinodynamic Motion Planning Tree Search
GONDOR to the Rescue: Satisficing Planning with Low Memory
May 27, 2026Yonatan Vernik, Alexander Tuisov, Alexander ShleyfmanTree Search Memory-Efficient Optimization
Computer Science Department, Bar-Ilan University · Independent Researcher
Can Transformers Learn to Verify During Backtracking Search?
May 21, 2026Yin Jun Phua, Tony Ribeiro, Tuan Nguyen +1Tree Search Transformer Attention
Institute of Science Tokyo, 2-12-1 Ookayama, Meguro-ku, Tokyo 152-8550, Japan · Centrale Nantes, CNRS, Laboratoire des Sciences du Num´erique de Nantes, LS2N, UMR 6004, F-44000 Nantes, France · National Institute of Informatics, 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo 101-8430, Japan +2
PhylaFlow: Hybrid Flow Matching in Billera-Holmes-Vogtmann Tree Space for Phylogenetic Inference
May 21, 2026Yasha Ektefaie, Leo Cui, Shrey Jain +2Flow Matching Tree Search
Eric and Wendy Schmidt Center, Broad Institute of MIT and Harvard · Department of Biomedical Informatics, Harvard Medical School · Centennial High School +1
Efficient Lookahead Encoding and Abstracted Width for Learning General Policies in Classical Planning
May 18, 2026Michael Aichmüller, Simon Ståhlberg, Martin Funkquist +1Graph Neural Networks Tree Search
RWTH Aachen University · Linköping University
Memory-Guided Tree Search with Cross-Branch Knowledge Transfer for LLM Solver Synthesis
May 17, 2026Fatemeh Haji, Javier Delarosa Quiros, Peyman NajafiradTree Search Large Language Model-Guided Optimization
Secure AI and Autonomy Lab · The University of Texas at San Antonio
LEAF-SQL: Level-wise Exploration with Adaptive Fine-graining for Text-to-SQL Skeleton Prediction
May 10, 2026Zhao Tan, Xiping Liu, Qing Shu +3Tree Search Text-to-SQL
School of Computing and Artificial Intelligence, Jiangxi University of Finance and Economics, Nanchang, China
Maximizing Rollout Informativeness under a Fixed Budget: A Submodular View of Tree Search for Tool-Use Agentic Reinforcement Learning
May 6, 2026Yuelin Hu, Zhenbo Yu, Zhengxue Cheng +2Tree Search Group Relative Policy Optimization
Shanghai Jiao Tong University · Shanghai Maritime University
Omni-o3: Deep Nested Omnimodal Deduction for Deliberative Audio-Visual Reasoning
Apr 27, 2026Zhicheng Zhang, Wentao Gu, Weicheng Wang +5Audio-Visual Understanding Tree Search
Nankai University · Kuaishou Technology · Pengcheng Laboratory +1
Study and Improvement of Search Algorithms in Multi-Player Perfect-Information Games
Apr 19, 2026Quentin Cohen-SolalGame-Playing Agents Tree Search
LAMSADE, Universit´e Paris-Dauphine, PSL, CNRS, Paris, France
PAC-CF: Calibrating Irreversible Frontier Pruning in LLM-Guided Search
Apr 15, 2026Tianhao Qian, Jiayu Chen, Zhenyu Sun +1LLM Inference Efficiency Inference-Time Search
TSR: Trajectory-Search Rollouts for Multi-Turn RL of LLM Agents
Feb 12, 2026Aladin Djuhera, Swanand Kadhe, Farhan Ahmed +3Tree Search LLM Agent Training
Technical University Munich · IBM Research
PuzzleJAX: A Benchmark for Reasoning and Learning
Aug 22, 2025Sam Earle, Graham Todd, Yuchen Li +5RL Benchmarks Game-Playing Agents
New York University · University of Malta · University of the Witwatersrand +1

Sep 30, 2026, cs.CLJ/K move · Enter open · S save

OPTS-TTPO: Enhancing Finite-Sample Policy-Gradient Learning with Tree Search

Junyu Lu, Shichao Weng, Zhiqiang Wang, Haojie Luo+9

Dobot Robotics · Independent Researcher · Zhejiang University+2

Tree Search Policy Gradient Methods Policy Learning Sample-Efficient RL

Open paper AskPDF arXiv

The policy-gradient theorem gives the exact gradient under the current policy, but finite on-policy samples may miss rare high-return trajectories. We study whether tree search improves their coverage within a fixed budget while controlling gradient bias. We introduce On-Policy Parallel Tree Search (OPTS) and Tree Trajectory Policy Optimization (TTPO) using on-policy tree trajectories, which sample new suffixes from the current policy at visited states. This needs no action-distribution correction, although branching changes state visitation. Our Branch Aggregation Lemma shows that branch-weighted tree statistics recover chain expectations when branch choices and weights are fixed before outgoing transitions are sampled. OPTS selects expansion states using estimated performance differences. Under deterministic dynamics, exact values, and max-backup advantages, the induced search policy's expected return improves monotonically with the budget. We bound the gradient bias from adaptive expansion and show that max backup assigns prefix credit to actions leading to better discovered suffixes. Against a finite chain reference, TTPG's measured bias stays near its no-branching level, while NaivePG's bias grows from 0.1251 to 0.4884. At matched budgets, reward- and value-guided OPTS improve correct-answer coverage and majority-vote accuracy over independent sampling. At matched branch counts, OPTS + TTPG gains coverage with a modest bias increase relative to Fixed-branch + TTPG. Under matched interaction or rollout budgets, OPTS-TTPO improves MuJoCo tail returns over PPO by up to 28.6%, achieves a 34-22-1 win-loss-tie record against PPO on Atari-57 under the last-100-log mean-return metric, and improves micro-averaged avg@32 and pass@32 over PPO across all four Qwen3 models.

Momentum

Related topics

Latest papers 35