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

Xueyan Li, Johannes Zenn, Ekaterina Fadeeva, Guinan Su, [0.1em] Mrinmaya Sachan Jonas Geiping, [0.5em] Max Planck Institute for Intelligent Systems · 2026

Read Efficient Test-Time Inference via Deterministic Exploration of Truncated Decoding Trees by Xueyan Li, Johannes Zenn, Ekaterina Fadeeva, Guinan Su, [0.1em] Mrinmaya Sachan Jonas Geiping, [0.5em] Max Planck Institute for Intelligent Systems (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-20500.txt.

Introduction

Li and five colleagues propose Distinct Leaf Enumeration, a deterministic decoding method that stops language models wasting effort on repeated paths. Standard self-consistency samples traces and votes, but in math and code it revisits the same prefixes and duplicate answers. Their method treats truncated sampling as walking a pruned tree and lists distinct leaves in order. That raises coverage under a fixed budget while reusing shared prefixes and cutting duplicate tokens. Tests show it finds better traces than stochastic self-consistency across math, coding, and general reasoning tasks.

Catalog record

CREATORXueyan Li, Johannes Zenn, Ekaterina Fadeeva, Guinan Su, [0.1em] Mrinmaya Sachan Jonas Geiping, [0.5em] Max Planck Institute for Intelligent Systems
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE62011
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.20500

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Efficient Test-Time Inference via Deterministic Exploration of Truncated Decoding Trees Xueyan Li, Johannes Zenn, Ekaterina Fadeeva, Guinan Su, [0.1em] Mrinmaya Sachan Jonas Geiping, [0.5em] Max Planck Institute for Intelligent Systems Abstract 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. Self-consistency Q: A has 9 books. B has twice as many, so B has 16 books. Q: A has 9 books. B has twice as many, so B has 16 books. Q: A has 9 books. B has twice as many, so B has 16 books. Q: A has 9 books. B has twice as that, so 9\times 2=18 . Q: B has twice the number of A’s books. 9\times 2=18 . Total tokens generated: 84 Distinct Leaf Enumeration (DLE) Q: A has 9 books. B has twice as B has twice many, so that, so 9\times 2=18 . B has 16 books. 9\times 2=18 books. the number of A’s books. 9\times 2=18 , as many books as A, so B has 9\times 2=18 books. ✗ ✗ ✗ ✓ ✓ 17 17 17 18 15 ✗ ✓ ✓ ✓ ✓ 17 7 9 15 16 Total tokens generated: 64 new tokens Figure 1: Distinct Leaf Enumeration (DLE) avoids recomputing the same prefixes, explores the generation space systematically, and generates fewer new tokens. 1 Introduction Parallel test-time computation has emerged as a principled way of scaling the performance of large language models (LLMs) ( 30 ; 25 ) . By sampling multiple solution traces for the same prompt and aggregating them via majority voting or answer-weighted selection ( 37 ; 33 ; 39 ) , additional inference time compute can be used for performance gains. However, naive stochastic sampling of multiple solutions is inefficient. For constrained domains like math and coding where problems are only solved by a narrow set of viable solutions, similar reasoning steps are repeatedly generated ( 47 ; 10 ; 14 ) . Figure 1 (top) shows this redundancy where three out of five generations are the same (first three rows), and four out of five generations share a prefix. Figure 2 makes this more concrete by showing the repetition rate among prefixes: we find that for code generation, 20\% of all prefix tokens are repeated across generated traces. Thinking of generated sequences in terms of a tree structure, this means that early branches are repeatedly traversed. At the same time, the number of possible continuations grows exponentially per generated token. This makes search efficiency critical. Classical search methods such as beam search ( 26 ; 32 ) make this tree structure explicit and control the traversed range with their number of branches (beams). However, beam search results in degenerate repetitions ( 35 ; 7 ) , quality deterioration with larger beams ( 17 ; 42 ) and a lack of diversity ( 31 ) . Figure 2: The repetition rate of prefix tokens increases as more sequences are sampled for \varepsilon -sampling. For code generation, the rate increases from \approx 11\% to \approx 17\% . Details of calculation can be found in Appendix A . In this work, we argue that effective tree-based generation for modern LLMs requires two practical ingredients, a principled way to truncate the exponentially large tree of possible completions, and a good heuristic for partial exploration under a limited compute budget. Since the full decoding tree is intractable, the tree size can be reduced by a truncated next-token distribution. Common truncated samplers such as top- k ( 8 ) , top- p (nucleus sampling) ( 13 ) , min- p ( 27 ) and \varepsilon -sampling ( 12 ) , are widely used to stabilize generation with a restricted set of candidate tokens at each decoding step ( 23 ) . Unlike beam search, which considers alternatives at every position, truncation-based sampling branches only when multiple valid tokens survive the truncation rule. Modern post-trained models are overconfident ( 34 ; 21 ) , often exhibiting sharpened output distributions. Thus, only a few tokens survive truncation at each step which reduces the effective tree size. Motivated by these observations, we propose Distinct Leaf Enumeration (DLE) , an alternative to (sampled) self-consistency that minimizes repetitions via tree search. DLE enumerates distinct leaves in the truncated generation tree by choosing deterministically which tokens to explore instead of sampling from the vocabulary probability distribution. The output is a set of distinct reasoning chains that never generate duplicate traces. This makes DLE a natural replacement for self-consistency in settings where repeated sampling is especially wasteful, such as in code synthesis and tightly specified math problems. DLE differs from prior decoding and search methods in both objective and mechanism. Unlike beam-style methods ( 32 ; 35 ) , it does not maintain diverse partial beams at each step. Unlike sampling-without-replacement methods ( 18 ; 29 ) , it is not designed to preserve a target sampling distribution. Unlike tree-of-thought ( 44 ; 41 ) style branching, it requires no additional deliberation or evaluation calls. Instead, DLE deterministically enumerates distinct leaves of a truncated decoding tree to improve coverage under a fixed compute budget. Further, DLE is able to reuse generated prefixes . Since it expands a pruned tree, it never re-generates the same prefix and lowers the number of newly generated tokens for the same number of sequences compared to self-consistency. In this paper, we propose DLE, as a deterministic enumeration method independent of the truncated sampling distribution . Empirically, at equal token budgets, DLE covers more probability space than self-consistency, translating to better performance. This also results in reduced inference time especially in memory-constrained conditions. Our main contributions are: • We propose Distinct Leaf Enumeration (DLE), a repetition-free decoding method as a deterministic drop-in replacement for stochastic sampling. It applies broadly to samplers such as top- p , min- p and \varepsilon -sampling. • Algorithmic benefit: Empirically, we show that higher coverage of the truncated search space is associated with better downstream performance. DLE achieves higher coverage than stochastic self-consistency by systematically exploring previously unvisited high-probability branches, leading to stronger reasoning performance. • Systems benefit: We show empirically that DLE is more token-efficient than self-consistency. By avoiding redundant generations, DLE produces more complete sequences under a fixed token budget, which translates into practical latency improvements on modern inference systems, especially in memory-constrained settings. 2 Related Work Our work targets a specific inefficiency in test-time scaling for constrained reasoning: repeated sampling produces many duplicate prefixes and often re-discovers the same high-probability traces. DLE addresses this by (i) enumerating distinct leaves in

Read the complete text