# Levin Tree Search with Context Models

arXiv: https://arxiv.org/abs/2305.16945 · HTML: https://mlsanity.com/paper/2305.16945/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 58 references that are in the map.
- First posted on arXiv 26 May 2023.

## Builds on (most cited first, 13 of 13)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Online Learning under Delayed Feedback](https://mlsanity.com/paper/1306.0686/) (2013)
- [Scale-Free Online Learning](https://mlsanity.com/paper/1601.01974/) (2016)
- [An investigation of model-free planning](https://mlsanity.com/paper/1901.03559/) (2019)
- [Gated Linear Networks](https://mlsanity.com/paper/1910.01526/) (2019)
- [Single-Agent Policy Tree Search With Guarantees](https://mlsanity.com/paper/1811.10928/) (2018)
- [Policy-Guided Heuristic Search with Guarantees](https://mlsanity.com/paper/2103.11505/) (2021)
- [Efficient Black-Box Planning Using Macro-Actions with Focused Effects](https://mlsanity.com/paper/2004.13242/) (2020)
- [Online Learning with Gated Linear Networks](https://mlsanity.com/paper/1712.01897/) (2017)
- [Gaussian Gated Linear Networks](https://mlsanity.com/paper/2006.05964/) (2020)
- [Isotuning With Applications To Scale-Free Online Learning](https://mlsanity.com/paper/2112.14586/) (2021)
- [ExPoSe: Combining State-Based Exploration with Gradient-Based Online Search](https://mlsanity.com/paper/2202.01461/) (2022)

## Built on by (most cited first, 7 of 7)

- [MindStar: Enhancing Math Reasoning in Pre-trained LLMs at Inference Time](https://mlsanity.com/paper/2405.16265/) (2024)
- [Finding Increasingly Large Extremal Graphs with AlphaZero and Tabu Search](https://mlsanity.com/paper/2311.03583/) (2023)
- [Deep Learning for Generalised Planning with Background Knowledge](https://mlsanity.com/paper/2410.07923/) (2024)
- [Learning Admissible Heuristics for A*: Theory and Practice](https://mlsanity.com/paper/2509.22626/) (2025)
- [A Training Data Recipe to Accelerate A* Search with Language Models](https://mlsanity.com/paper/2407.09985/) (2024)
- [Exponential Speedups by Rerooting Levin Tree Search](https://mlsanity.com/paper/2412.05196/) (2024)
- [UPath: Universal Planner Across Topological Heterogeneity For Grid-Based Pathfinding](https://mlsanity.com/paper/2602.23789/) (2026)

## Abstract (arXiv)

Levin Tree Search (LTS) is a search algorithm that makes use of a policy (a probability distribution over actions) and comes with a theoretical guarantee on the number of expansions before reaching a goal node, depending on the quality of the policy. This guarantee can be used as a loss function, which we call the LTS loss, to optimize neural networks representing the policy (LTS+NN). In this work we show that the neural network can be substituted with parameterized context models originating from the online compression literature (LTS+CM). We show that the LTS loss is convex under this new model, which allows for using standard convex optimization tools, and obtain convergence guarantees to the optimal parameters in an online setting for a given set of solution trajectories -- guarantees that cannot be provided for neural networks. The new LTS+CM algorithm compares favorably against LTS+NN on several benchmarks: Sokoban (Boxoban), The Witness, and the 24-Sliding Tile puzzle (STP). The difference is particularly large on STP, where LTS+NN fails to solve most of the test instances while LTS+CM solves each test instance in a fraction of a second. Furthermore, we show that LTS+CM is able to learn a policy that solves the Rubik's cube in only a few hundred expansions, which considerably improves upon previous machine learning techniques.