# ProTuner: Tuning Programs with Monte Carlo Tree Search

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 May 2020.

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

- [Tensor Program Optimization with Probabilistic Programs](https://mlsanity.com/paper/2205.13603/) (2022)
- [TLP: A Deep Learning-based Cost Model for Tensor Program Tuning](https://mlsanity.com/paper/2211.03578/) (2022)
- [ytopt: Autotuning Scientific Applications for Energy Efficiency at Large Scales](https://mlsanity.com/paper/2303.16245/) (2023)
- [BaCO: A Fast and Portable Bayesian Compiler Optimization Framework](https://mlsanity.com/paper/2212.11142/) (2022)
- [Customized Monte Carlo Tree Search for LLVM/Polly's Composable Loop Optimization Transformations](https://mlsanity.com/paper/2105.04555/) (2021)
- [Moses: Efficient Exploitation of Cross-device Transferable Features for Tensor Program Optimization](https://mlsanity.com/paper/2201.05752/) (2022)
- [REASONING COMPILER: LLM-Guided Optimizations for Efficient Model Serving](https://mlsanity.com/paper/2506.01374/) (2025)
- [Autotuning PolyBench Benchmarks with LLVM Clang/Polly Loop Optimization Pragmas Using Bayesian Optimization (extended version)](https://mlsanity.com/paper/2104.13242/) (2021)
- [Machine Learning for CUDA+MPI Design Rules](https://mlsanity.com/paper/2203.02530/) (2022)

## Abstract (arXiv)

We explore applying the Monte Carlo Tree Search (MCTS) algorithm in a notoriously difficult task: tuning programs for high-performance deep learning and image processing. We build our framework on top of Halide and show that MCTS can outperform the state-of-the-art beam-search algorithm. Unlike beam search, which is guided by greedy intermediate performance comparisons between partial and less meaningful schedules, MCTS compares complete schedules and looks ahead before making any intermediate scheduling decision. We further explore modifications to the standard MCTS algorithm as well as combining real execution time measurements with the cost model. Our results show that MCTS can outperform beam search on a suite of 16 real benchmarks.