# Entropy-Tree: Tree-Based Decoding with Entropy-Guided Exploration

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 27 of its 34 references that are in the map.
- First posted on arXiv 2 Jan 2026.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

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

- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [On Calibration of Modern Neural Networks](https://mlsanity.com/paper/1706.04599/) (2017)
- [Dropout as a Bayesian Approximation: Representing Model Uncertainty in Deep Learning](https://mlsanity.com/paper/1506.02142/) (2015)
- [Simple and Scalable Predictive Uncertainty Estimation using Deep Ensembles](https://mlsanity.com/paper/1612.01474/) (2016)
- [The Curious Case of Neural Text Degeneration](https://mlsanity.com/paper/1904.09751/) (2019)
- [Fast Inference from Transformers via Speculative Decoding](https://mlsanity.com/paper/2211.17192/) (2022)
- [Can LLMs Express Their Uncertainty? An Empirical Evaluation of Confidence Elicitation in LLMs](https://mlsanity.com/paper/2306.13063/) (2023)
- [Are NLP Models really able to Solve Simple Math Word Problems?](https://mlsanity.com/paper/2103.07191/) (2021)
- [Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads](https://mlsanity.com/paper/2401.10774/) (2024)
- [Semantic Uncertainty: Linguistic Invariances for Uncertainty Estimation in Natural Language Generation](https://mlsanity.com/paper/2302.09664/) (2023)
- [SelfCheckGPT: Zero-Resource Black-Box Hallucination Detection for Generative Large Language Models](https://mlsanity.com/paper/2303.08896/) (2023)
- [Teaching Models to Express Their Uncertainty in Words](https://mlsanity.com/paper/2205.14334/) (2022)
- [Beyond the 80/20 Rule: High-Entropy Minority Tokens Drive Effective Reinforcement Learning for LLM Reasoning](https://mlsanity.com/paper/2506.01939/) (2025)
- [Weight Uncertainty in Neural Networks](https://mlsanity.com/paper/1505.05424/) (2015)
- [Diverse Beam Search: Decoding Diverse Solutions from Neural Sequence Models](https://mlsanity.com/paper/1610.02424/) (2016)
- [Break the Sequential Dependency of LLM Inference Using Lookahead Decoding](https://mlsanity.com/paper/2402.02057/) (2024)
- [Generating with Confidence: Uncertainty Quantification for Black-box Large Language Models](https://mlsanity.com/paper/2305.19187/) (2023)
- [Unsupervised Quality Estimation for Neural Machine Translation](https://mlsanity.com/paper/2005.10608/) (2020)
- [NeuroLogic A*esque Decoding: Constrained Text Generation with Lookahead Heuristics](https://mlsanity.com/paper/2112.08726/) (2021)
- [Language Models with Conformal Factuality Guarantees](https://mlsanity.com/paper/2402.10978/) (2024)
- [Large language model validity via enhanced conformal prediction methods](https://mlsanity.com/paper/2406.09714/) (2024)
- [TreeRL: LLM Reinforcement Learning with On-Policy Tree Search](https://mlsanity.com/paper/2506.11902/) (2025)
- [DRAGIN: Dynamic Retrieval Augmented Generation based on the Information Needs of Large Language Models](https://mlsanity.com/paper/2403.10081/) (2024)
- [TreePO: Bridging the Gap of Policy Optimization and Efficacy and Inference Efficiency with Heuristic Tree-based Modeling](https://mlsanity.com/paper/2508.17445/) (2025)
- [Detecting Hallucinations in Large Language Model Generation: A Token Probability Approach](https://mlsanity.com/paper/2405.19648/) (2024)

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

- [Optimizing What Policies Learn From: Recoverability-aware Rollout Intervention Learning](https://mlsanity.com/paper/2608.05080/) (2026)
- [Where Rollouts Begin: Low-Load, High-Leverage First-Token Diversification for RLVR](https://mlsanity.com/paper/2605.28295/) (2026)
- [Uncertainty-Aware Simulation-Based Inference for Operations Research with Large Language Models](https://mlsanity.com/paper/2608.00019/) (2026)

## Abstract (arXiv)

Large language models achieve strong reasoning performance, yet existing decoding strategies either explore blindly (random sampling) or redundantly (independent multi-sampling). We propose Entropy-Tree, a tree-based decoding method that exploits entropy as a signal for branching decisions--expanding the search tree only at positions where the model exhibits genuine uncertainty. Entropy-Tree shows superior accuracy and calibration in reasoning tasks: it achieves better pass@k than Multi-chain across multiple models and datasets, and its predictive entropy demonstrates better AUROC compared to several traditional metrics. Entropy-Tree unifies efficient structured exploration and reliable uncertainty estimation within a single decoding procedure.