# Efficient Test-Time Inference via Deterministic Exploration of Truncated Decoding Trees

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

## Key facts

- Cited by 1 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 39 of its 46 references that are in the map.
- First posted on arXiv 22 Apr 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, 30 of 39)

- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [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)
- [Qwen2.5 Technical Report](https://mlsanity.com/paper/2412.15115/) (2024)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [Sequence to Sequence Learning with Neural Networks](https://mlsanity.com/paper/1409.3215/) (2014)
- [The Curious Case of Neural Text Degeneration](https://mlsanity.com/paper/1904.09751/) (2019)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [MMLU-Pro: A More Robust and Challenging Multi-Task Language Understanding Benchmark](https://mlsanity.com/paper/2406.01574/) (2024)
- [Hierarchical Neural Story Generation](https://mlsanity.com/paper/1805.04833/) (2018)
- [SGLang: Efficient Execution of Structured Language Model Programs](https://mlsanity.com/paper/2312.07104/) (2023)
- [A Diversity-Promoting Objective Function for Neural Conversation Models](https://mlsanity.com/paper/1510.03055/) (2015)
- [Just Ask for Calibration: Strategies for Eliciting Calibrated Confidence Scores from Language Models Fine-Tuned with Human Feedback](https://mlsanity.com/paper/2305.14975/) (2023)
- [Six Challenges for Neural Machine Translation](https://mlsanity.com/paper/1706.03872/) (2017)
- [Diverse Beam Search: Decoding Diverse Solutions from Neural Sequence Models](https://mlsanity.com/paper/1610.02424/) (2016)
- [A Contrastive Framework for Neural Text Generation](https://mlsanity.com/paper/2202.06417/) (2022)
- [Stochastic Beams and Where to Find Them: The Gumbel-Top-k Trick for Sampling Sequences Without Replacement](https://mlsanity.com/paper/1903.06059/) (2019)
- [Deep Think with Confidence](https://mlsanity.com/paper/2508.15260/) (2025)
- [Scalable Best-of-N Selection for Large Language Models via Self-Certainty](https://mlsanity.com/paper/2502.18581/) (2025)
- [Turning Up the Heat: Min-p Sampling for Creative and Coherent LLM Outputs](https://mlsanity.com/paper/2407.01082/) (2024)
- [Truncation Sampling as Language Model Desmoothing](https://mlsanity.com/paper/2210.15191/) (2022)
- [Let's Sample Step by Step: Adaptive-Consistency for Efficient Reasoning and Coding with LLMs](https://mlsanity.com/paper/2305.11860/) (2023)
- [Confidence Improves Self-Consistency in LLMs](https://mlsanity.com/paper/2502.06233/) (2025)
- [Taming Overconfidence in LLMs: Reward Calibration in RLHF](https://mlsanity.com/paper/2410.09724/) (2024)
- [Escape Sky-high Cost: Early-stopping Self-Consistency for Multi-step Reasoning](https://mlsanity.com/paper/2401.10480/) (2024)
- [Hydragen: High-Throughput LLM Inference with Shared Prefixes](https://mlsanity.com/paper/2402.05099/) (2024)
- [Breaking the Beam Search Curse: A Study of (Re-)Scoring Methods and Stopping Criteria for Neural Machine Translation](https://mlsanity.com/paper/1808.09582/) (2018)
- [Entropy-based Exploration Conduction for Multi-step Reasoning](https://mlsanity.com/paper/2503.15848/) (2025)

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

- [Multi-Stream LLMs: Unblocking Language Models with Parallel Streams of Thoughts, Inputs and Outputs](https://mlsanity.com/paper/2605.12460/) (2026)

## Abstract (arXiv)

Self-consistency boosts inference-time performance by sampling multiple reasoning traces in parallel and voting. However, in constrained domains like math and code, this strategy is compute-inefficient because it samples with replacement, repeatedly revisiting the same high-probability prefixes and duplicate completions. We propose Distinct Leaf Enumeration (DLE), a deterministic decoding method that treats truncated sampling as traversal of a pruned decoding tree and systematically enumerates distinct leaves instead of sampling with replacement. This strategy improves inference efficiency in two ways. Algorithmically, it increases coverage of the truncated search space under a fixed budget by exploring previously unvisited high-probability branches. Systemically, it reuses shared prefixes and reduces redundant token generation. Empirically, DLE explores higher-quality reasoning traces than stochastic self-consistency, yielding better performance on math, coding, and general reasoning tasks.