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

1. Problem Statement

Large Language Models (LLMs) often employ Self-Consistency, a technique where multiple reasoning traces are sampled in parallel and aggregated (e.g., via majority voting) to improve accuracy. However, this approach suffers from significant computational inefficiency, particularly in constrained domains like mathematics and coding:

• Redundant Sampling: Standard stochastic sampling (with replacement) frequently revisits the same high-probability prefixes and generates duplicate completions.
• Inefficient Search: In constrained domains, viable solutions are narrow. Stochastic sampling wastes compute budget on duplicate paths rather than exploring diverse, high-quality branches.
• Systemic Overhead: Generating independent sequences forces the inference engine to recompute shared prefixes, failing to leverage KV-cache reuse mechanisms available in modern serving stacks (e.g., vLLM, SGLang).

2. Methodology: Distinct Leaf Enumeration (DLE)

The authors propose Distinct Leaf Enumeration (DLE), a deterministic decoding strategy that treats truncated sampling as a traversal of a pruned decoding tree. Instead of sampling with replacement, DLE systematically enumerates distinct leaves to maximize coverage of the search space under a fixed compute budget.

Core Mechanism

1. Truncated Tree Construction: DLE operates on a "pruned tree" defined by standard truncation rules (e.g., Top-k, Top-p, Min-p, $\epsilon$-sampling). At each step, only tokens satisfying the truncation criterion form the "active set."
2. Deterministic Expansion:
   • Greedy Initialization: DLE starts with a greedy generation (highest probability token) until an End-of-Sequence (EOS) token is reached.
   • Branching: It identifies branching points where the active set size $|A| > 1$.
   • Selection Strategy (PROBFIRST): DLE selects the next branch to explore based on the highest path probability mass ($Q(x)$) seen so far. It expands the most promising unexplored branch deterministically.
   • Greedy Completion: Once a branch point is chosen, the rest of the sequence is generated greedily until EOS.
3. Early Stopping: To prevent generating semantically identical continuations that diverge only slightly before merging, DLE employs an early-stopping heuristic. If a new branch matches $n$ consecutive tokens of a previously generated sibling's suffix, that branch is terminated, and the budget is reallocated.
4. Prefix Reuse: Because DLE explores a tree structure, shared prefixes are computed only once. This allows inference engines to reuse KV caches for common branches, significantly reducing memory bandwidth and latency.

Key Distinctions from Prior Work

• vs. Beam Search: DLE does not maintain diverse partial beams at every step (which causes degeneration) but focuses on enumerating distinct leaves (complete sequences).
• vs. Sampling-without-Replacement: DLE is not designed to preserve a specific target distribution but to maximize coverage of high-probability regions.
• vs. Tree-of-Thought (ToT): DLE requires no additional model calls for deliberation or evaluation; it relies solely on next-token probabilities.

3. Key Contributions

1. Algorithmic Innovation: Introduction of DLE, a repetition-free, deterministic decoding method compatible with various samplers (Top-p, Min-p, $\epsilon$-sampling).
2. Theoretical Insight: Demonstration that coverage (the probability mass captured by the set of generated sequences) is positively correlated with downstream performance. DLE achieves higher coverage than stochastic self-consistency for the same token budget by avoiding duplicate paths.
3. Systemic Efficiency: Proof that DLE's tree-structured exploration enables massive KV-cache reuse. This reduces the number of new tokens generated and lowers inference latency, especially in memory-constrained environments.
4. Empirical Validation: Extensive experiments showing DLE outperforms state-of-the-art baselines across math, coding, and general reasoning tasks.

4. Experimental Results

The authors evaluated DLE on GSM8K (Math), HumanEval (Code), and MMLU-Pro (General Reasoning) using Qwen and Llama model families.

• Performance Gains:
  • Math (GSM8K): DLE improved accuracy by 3–9% over standard self-consistency (e.g., 44.43% vs. 38.74% for Qwen2.5-0.5B with Top-p).
  • Code (HumanEval): DLE showed 4–7% improvements (e.g., 51.22% vs. 45.73% for Top-p).
  • General Reasoning: Consistent gains on MMLU-Pro.
• Token Efficiency:
  • To achieve similar accuracy, DLE required far fewer new tokens than stochastic sampling. For example, in $\epsilon$-sampling, DLE needed <20 new tokens per sequence to match the performance of stochastic sampling which generated >150 tokens.
  • Coverage: DLE consistently covered more probability mass than stochastic baselines at equal sequence budgets ($k$).
• Inference Speed:
  • Using SGLang (optimized for tree-based generation), DLE achieved significantly lower runtime, particularly at small batch sizes and high $\epsilon$ values where prefix reuse is maximized.
  • Cache hit rates for DLE were much higher than baselines, approaching theoretical maximums.

5. Significance and Conclusion

This paper challenges the prevailing notion that "more sampling" is the only way to scale LLM performance. It argues that efficient allocation of compute is more critical than raw volume.

• Paradigm Shift: Moves test-time scaling from stochastic sampling (which wastes resources on duplicates) to deterministic tree exploration.
• Practical Impact: DLE offers a "drop-in" replacement for self-consistency that improves both accuracy (by finding better reasoning traces) and latency/cost (by reusing prefixes).
• Future Directions: The authors suggest that the tree perspective could bridge decoding and training, allowing for finer-grained credit assignment at branch points, and propose adaptive hybrids combining deterministic exploration with stochastic sampling for low-probability tails.

In summary, Distinct Leaf Enumeration provides a principled, efficient, and high-performing alternative to standard self-consistency, making it particularly valuable for constrained reasoning tasks where computational resources are limited and solution spaces are narrow.