Efficient Test-Time Inference via Deterministic Exploration of Truncated Decoding Trees
This addresses a bottleneck in inference-time performance for domains such as math and code, offering an incremental improvement over existing methods.
The paper tackles the compute inefficiency of self-consistency in constrained domains like math and code by proposing Distinct Leaf Enumeration (DLE), a deterministic decoding method that systematically enumerates distinct leaves in a pruned decoding tree, resulting in improved inference efficiency and higher-quality reasoning traces.
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.