1 Introduction↩︎

Large language models (LLMs) have demonstrated remarkable capabilities in complex reasoning tasks, from mathematical problem-solving to scientific analysis [1]–[3]. The quality of generated outputs critically depends on the decoding strategy—how the model selects tokens from its predicted probability distributions. However, existing decoding methods exhibit fundamental limitations in exploring the model’s decision space.

Traditional decoding methods have limitations. Deterministic methods such as greedy decoding [4] always select the highest-probability token, leading to myopic decisions that often produce repetitive or suboptimal outputs. Beam search [5] maintains multiple candidate sequences but remains a pruned greedy strategy with limited diversity, biased toward “safe” high-probability responses. Stochastic methods including top-k [6] and top-p (nucleus) sampling [7] introduce randomness to enhance diversity, yet their exploration is blind—uniformly applied across all positions regardless of the model’s actual uncertainty at each step.

When faced with more challenging reasoning tasks, multiple samples may be needed to find the correct answer. Self-Consistency [8] addresses reasoning tasks by generating multiple independent samples and selecting the most frequent answer through majority voting. While effective, this approach suffers from computational redundancy: independent samples do not share prefix computations, and the exploration is undirected, potentially wasting resources on semantically redundant paths while missing critical decision points.

Moreover, traditional LLM uncertainty quantification methods are also based on multiple random sampling, using information such as output log probabilities or semantic similarity for uncertainty assessment. The randomness of sampling imposes limitations on the quantification of uncertainty.

Recent work by Wang et al. [9] reveals a striking pattern in chain-of-thought reasoning: token entropy distributions are highly non-uniform. Approximately 80% of tokens exhibit low entropy—the model generates them with high confidence, primarily for syntactic coherence or continuing the current reasoning thread. The remaining 20% of high-entropy tokens serve as “decision forks” that steer the reasoning trajectory toward different directions. These high-entropy positions often correspond to semantically significant tokens such as logical connectives (“thus”, “however”) and question words (“how”, “what”). This observation suggests a principled approach: rather than exploring uniformly or randomly, we should concentrate computational resources on these high-entropy decision points where the model genuinely hesitates among alternatives.

We propose Entropy-Tree, a decoding strategy that utilizes high-entropy token information for tree-structured decoding. Entropy-Tree dynamically monitors the entropy of each token during the decoding process to assess the model’s confidence, and branches at points where the model hesitates and where there is semantic importance, allowing the model to efficiently explore different reasoning paths. As shown in Figure 1, whenever a high entropy token is encountered, which indicates a point of hesitation in the model’s inference, Entropy-Tree will actively branch out, creating multiple inference paths. This allows the model to explore various possible subsequent outcomes.. Specifically, our contributions are as follows:

• Novel Decoding Framework: We propose Entropy-Tree, which constructs tree-structured outputs by branching at high-entropy positions with prefix sharing, enabling structured exploration of the model’s decision space.

• Improved reasoning Accuracy: Entropy-Tree demonstrated superior pass@k performance compared to random multiple sampling across the models and datasets we tested, which proves the contribution of our method to enhancing the accuracy of models in reasoning tasks.

• Tree-Derived Uncertainty Quantification: The predictive entropy calculated from the leaf nodes generated by Entropy-Tree exhibits better calibration, showing a significant improvement in AUROC compared to other metrics.

2 Preliminary↩︎

Let \(\mathcal{V}\) denote a vocabulary of size \(V\). An autoregressive language model parameterized by \(\theta\) defines a probability distribution over sequences: \[P_\theta(\mathbf{y} | \mathbf{x}) = \prod_{t=1}^{T} P_\theta(y_t | \mathbf{x}, \mathbf{y}_{<t})\] where \(\mathbf{x} = (x_1, \ldots, x_n)\) is the input prompt and \(\mathbf{y} = (y_1, \ldots, y_T)\) is the generated sequence. At each timestep \(t\), the model outputs a distribution \(P_\theta(y_t | \mathbf{x},\mathbf{y}_{<t})\) over the vocabulary conditioned on the prompt and previously generated tokens.

The decoding strategy refers to the method of selecting tokens from the probability distribution output by the model. Greedy decoding [4] directly selects the token with the highest probability: \[y_{greedy} = \arg\max_{i\in V}P_\theta(i)\]

This method, although simple to implement, can lead to a lack of diversity in the model’s generated results and is prone to getting stuck in local optima. To introduce randomness and diversity in the model generation process, researchers have proposed top-k and top-p sampling,

Top-k sampling [6] is shown in equation 1 . \(\mathcal{K}\) denotes the collection of the top-k tokens with the highest probability. \[\label{equa:top95k} P_{top-k}(i)= \begin{cases} \frac{P(i)}{\sum_{j\in\mathcal{K}}P(j)}, i\in\mathcal{K} \\ 0, otherwise \end{cases}\tag{1}\] Top-p sampling [7] sort the tokens in descending order according to P(i) to obtain the sequence \([i_1, i_2, ..., i_\mathcal{V}]\). Then, starting from the first element of the sequence, gradually accumulate the probabilities until \(\sum_{j=1}^{m}P(i_j)\ge p\). At this point, denote the set of these m tokens as \(\mathcal{P}\). \[\label{equa:top95p} P_{top-p}(i)= \begin{cases} \frac{P(i)}{\sum_{j\in\mathcal{P}}P(j)}, i\in\mathcal{P} \\ 0, otherwise \end{cases}\tag{2}\]

Top-k and top-p sampling do not simply select the token with the highest probability as the result; instead, they perform random sampling from the updated probability distribution. These methods introduce a certain level of diversity into the decoding process, but this diversity is indiscriminate, meaning that the model’s performance on a single instance of a problem remains limited.

To improve the accuracy of model inference and reduce the randomness of a single sampling, Self-Consistency [8] samples \(N\) independent reasoning paths \(\{\mathbf{y}^{(1)}, \ldots, \mathbf{y}^{(N)}\}\) from the model, extracts answers \(\{a^{(1)}, \ldots, a^{(N)}\}\), and selects the most frequent answer: \[\hat{a} = \arg\max_{a} \sum_{j=1}^{N} \mathbb{1}[a^{(j)} = a]\]

3 Entropy-Tree Decoding↩︎

In this section, we will provide a detailed explanation of the Entropy-Tree decoding strategy, including the branch point filtering introduced in Section 3.1 and the expansion and size control described in Section 3.2. We will also explain in Section 3.3 how to use the Entropy-Tree for uncertainty quantification. The complete process of the Entropy-Tree is shown in Figure 2.

3.1 Branch Point Filtering↩︎

During the LLM decoding process, we calculate the token-wise entropy based on the token probability distribution \(P_{\theta,t}(i)\) as follows: \[H_t=-\sum_{i\in\mathcal{V}}p_{\theta,t}(i)\log{p_{\theta,t}(i)}\]

Based on 80/20 rule [9], we hypothesize that branching at high-entropy tokens can generate more exploratory and semantically diverse reasoning paths. We set an entropy threshold \(\tau\). For token \(y_t\) at timestep \(t\), if \(H_t<\tau\), a standard random sampling strategy is used (top-k and top-p sampling). If \(H_t\ge\tau\), we designate this token as a candidate branching token.

Although previous research suggests that high-entropy tokens may play a decisive role in the model’s reasoning process, there are also tokens with relatively low semantic importance (such as "the" and "it"). The model exhibits high entropy on these tokens due to indecision about syntactic structure, rather than encountering a critical point in the semantic or reasoning path [10]. Thus, we further filter the candidate branching tokens based on self-attention.

DRAGIN [11] uses the maximum attention value to represent the importance of a token. We adopt a similar approach, and the attention matrix is calculated as follows: \[A=softmax(mask(\frac{QK^T}{\sqrt{d_k}}))\] \(Q\) is the query matrix, \(K\) is the key matrix, \(d_k\) denotes the dimensionality of a key vector. The importance score for token \(y_t\) is identified by the highest \(A_{t,j}\) for all \(j<t\): \[I_t=\max_{j=1,\ldots,t-1}A_{t,j}\]

For the candidate branching tokens previously selected based on token-wise entropy, since the specific token to choose has not yet been determined, we calculate the importance value \(I_t\) of the token \(y_t\) with the highest probability. Here, we also set an importance threshold \(\delta\). If \(I_t<\delta\), no branching is performed; if \(I_t\ge\delta\), it is determined to branch at the current token.

3.2 Tree Expansion and Size Control↩︎

Once a token is identified as a branching token, random sampling is no longer used to generate a single token. Instead, the top \(b\) tokens with the highest probabilities are selected as new branches. Sub-branches continue to be generated following the same process, and whenever a branch token is detected, branching will continue. We use a breadth-first search algorithm to expand the tree, ensuring that nodes with lower depth are prioritized for expansion. This ensures that all leaf nodes are completed after a certain number of branching steps.

As the number of branch nodes increases, the size of the tree grows exponentially. To prevent scale explosion, we limit the total number of leaf nodes in the tree to \(N_{tree}\). Once the number of leaf nodes equals \(N_{tree}\), branching will cease. The remaining branches will revert to sampling mode until an EOS token is encountered.

3.3 Uncertainty Quantification in Entropy-Tree↩︎

For inference tasks, we extract the answers from all the leaf nodes and calculate the probability distribution \(p(a | x)\) of the answers. We then compute the predictive entropy using the following formula: \[H=-\sum_{i=1}^{N}p(a_i|x)\log p(a_i|x)\]

This approach is no different from the traditional method of calculating predictive entropy, except that we no longer use the answer distribution obtained from multiple random samples; instead, we use the distribution from the Entropy-Tree.

4 Experiments↩︎

We found that Entropy-Tree decoding not only helps improve the accuracy of answers but also enhances calibration. Therefore, we designed experiments in these two aspects.

4.1 Experimental Setup↩︎

4.1.0.1 Evaluation Metric on Accuracy.

Pass@k is a widely used evaluation metric in machine learning, particularly for assessing the performance of generative models in tasks like code generation [12]. It measures the probability that a model produces at least one correct solution out of \(k\) independently generated samples for a given problem. This metric is especially valuable for quantifying a model’s exploratory capability, as it rewards diversity in outputs and accounts for scenarios where multiple attempts might yield a valid result, making it ideal for evaluating creativity and robustness in AI systems.

4.1.0.2 Evaluation Metric on Calibration.

The area under the receiver operator characteristic curve (AUROC) corresponds to the probability that incorrect answers have higher uncertainty scores than correct answers, and it can be used to assess the calibration of uncertainty metrics [13]. A higher AUROC score is better, with a perfect uncertainty measurement scoring 1, while a completely random uncertainty measurement scores 0.5.

4.1.0.3 Baselines for Accuracy.

We compared Entropy-Tree decoding with Multi-chain, which involves the accuracy of \(N\) random independent samples, to demonstrate that our method is superior to simple random sampling.

4.1.0.4 Baselines for Calibration.

Predictive entropy [14] refers to the uncertainty inherent in the output distribution of a model’s multiple responses. In our work, we compare the predictive entropy of the Entropy-Tree with Multi-chain. Semantic entropy [15] measures uncertainty by performing semantic clustering on the output sequences of the model, but it may become ineffective when dealing with long text responses. Length-normalized predictive entropy [16] involves dividing the joint log-probability of each sequence by the sequence length. p(True) [14] is used to measure the model’s uncertainty by asking the model again whether its previous answer was correct. Lexical Similarity [17] uses the average similarity of sequences to assess uncertainty.

4.1.0.5 Datasets.

Entropy-Tree is suitable for reasoning datasets of a certain level of difficulty. The datasets we have selected are as follows:

• SVAMP [18]: 300 elementary-level math word problems.

• MATH-500 [19]: 500 representative high school math problems with varying difficulty.

• SciBench [20]: 692 college-level science problems.

• GPQA-main/diamond [21]: 448/198 graduate-level physics, chemistry, biology questions.

• AIME24/25: 30 competition-level math problems each set.

4.1.0.6 Models.

We used models of different scales from the Qwen2.5 series [22], including Qwen2.5-7B-Instruct, Qwen2.5-14B-Instruct, and Qwen2.5-32B-Instruct.

4.1.0.7 Budget & Fairness.

For fair comparison, we control the number of leaves/samples: Entropy-Tree with \(N=20\) leaves vs. Self-Consistency with \(N=20\) independent samples. We set the threshold for determining high entropy and high importance at the 80th percentile.

4.2 Case Study↩︎

Entropy-Tree branches at key tokens, allowing for different approaches and problem-solving processes for the same issue. As shown in Figure 3, LLM identified two different methods at the first branching. In the subsequent branches corresponding to each method, different scenarios emerged, such as some leaf nodes lacking a complete calculation process and some leaf nodes having incorrect calculation results. However, because certain nodes retained the correct calculation prefix, leaf nodes that ultimately arrived at the correct answer appeared.

4.3 Main Results↩︎

The curve shown in Figure 4 represents the pass@k performance of Entropy-Tree under Qwen2.5-7B-Instruct model and MATH-500 dataset. Starting from \(k=3\), Entropy-Tree demonstrates a significant improvement compared to Multi-chain, with the enhancement becoming more pronounced as \(k\) increases. Entropy-Tree requires approximately 2/3 of the sample size (\(k=13\)) to achieve a pass@k value comparable to that of Multi-chain (\(k=20\)).

The pass@10 and pass@20 results for all models and datasets are shown in Table 1 and Table 2. In most cases, Entropy-Tree demonstrates improved accuracy compared to Multi-chain. This indicates that Entropy-Tree is suitable for reasoning tasks across different domains and varying levels of difficulty. By branching into different inference paths at high-entropy points, where the model hesitates in its decision-making, the model can significantly increase its level of exploration when faced with challenging problems. This naturally leads to an improvement in pass@k.

Figure 5 shows the AUROC comparison for the Qwen2.5 series models on GPQA-diamond. Across models of different scales, the predictive entropy sampled by Entropy-Tree consistently demonstrates optimal performance. Additionally, semantic entropy becomes noticeably ineffective when dealing with long inference texts, whereas our method still holds an advantage over traditional predictive entropy. The results on all models and datasets are shown in Table 3, ET-PE (predictive entropy derived from Entropy-Tree results) demonstrates optimal calibration performance across various models and datasets. Although Entropy-Tree does not inherently propose a new uncertainty quantification metric, the model benefits from a more thorough exploration of ideas within the inference space due to the high-entropy-guided decoding strategy. As a result, the distribution of answers aligns better with the correctness of the model’s responses.

4.4 Ablation Studies↩︎

We conducted two ablation studies on the experimental performance of Qwen2.5-7B-Instruct on MATH-500, with the results shown in Figure 6.

4.4.0.1 Effect of Branching Position.

Moving the entropy threshold from 80th to 90th percentile shifts branching points later in generation, resulting in performance degradation. This suggests that branching early in the decoding process may be more effective in improving decoding quality.

4.4.0.2 Effect of High-Entropy guided Branching.

Random branching (without entropy guidance) at matched probability shows significantly worse performance than branching at high-entropy tokens, confirming the importance of high-entropy positions as “decision forks”.

5 Related Work↩︎

5.1 Decoding Strategies for Language Models↩︎

5.1.0.1 Tree-based decoding strategies.

Traditional tree-based decoding methods have been widely used in sequence generation tasks to explore and select optimal paths in a search tree. Beam search [5], for instance, maintains a fixed number of promising hypotheses at each step, effectively pruning the search space while expanding nodes in a breadth-first manner. Monte Carlo Tree Search (MCTS) [23] extends this by incorporating probabilistic simulations and value estimations to guide exploration, balancing exploitation and exploration in complex decision spaces. Other approaches include variants like diverse beam search [24], which introduces diversity penalties to encourage varied outputs, and A*-inspired heuristics [25] that prioritize nodes based on estimated costs to the goal.

Recent advancements have introduced novel tree-based decoding strategies tailored for large language models (LLMs). TreeRL [26] leverages reinforcement learning to optimize tree exploration policies, enabling adaptive sampling and reward-based pruning. Similarly, TreePO [27] employs policy optimization techniques within a tree structure to refine decoding paths, focusing on long-term sequence quality.

5.1.0.2 Other decoding strategies.

Traditional methods include greedy decoding [4], which selects the highest-probability token at each step for simplicity and speed, though it often leads to repetitive or suboptimal outputs. Sampling-based techniques, such as top-k sampling [6] and nucleus (top-p) sampling [7], introduce randomness by restricting the selection to a subset of high-probability tokens, promoting diversity and creativity in generated text.

Recent innovations focus on accelerating inference. Speculative decoding [28], for example, employs a smaller draft model to predict multiple tokens ahead, which are then verified in parallel by the main LLM, significantly reducing latency in autoregressive generation. Lookahead decoding [29] builds on this by anticipating future tokens through heuristic approximations, enabling faster decoding while maintaining output quality. Other methods, like Medusa [30], utilize multiple decoding heads to generate speculative branches, further optimizing for throughput in real-time applications.

5.2 Uncertainty Quantification↩︎

Classical approaches include Bayesian neural networks [31], which place distributions over weights but suffer from computational intractability; MC dropout [32], which approximates Bayesian inference but requires many forward passes; and deep ensembles [33], which train multiple models at significant cost. Guo et al. [34] showed modern networks are poorly calibrated despite high accuracy.

For LLMs, classical methods face fundamental limitations due to model scale. Kuhn et al. [15] introduced semantic entropy, computing entropy over semantic equivalence classes. This was extended to hallucination detection [35]. Kadavath et al. [14] and Lin et al. [36] explored querying models for confidence. However, Xiong et al. [37] demonstrated systematic overconfidence in verbalized uncertainty. For Black-box scenarios, SelfCheckGPT [38] detects hallucinations through sampling consistency. Lin et al. [39] introduced semantic dispersion in embedding space. Conformal prediction methods [40], [41] provide statistical guarantees but require calibration data.

6 Conclusion↩︎

In this paper, we point out that traditional decoding strategies are blind in diversity exploration. We propose Entropy-Tree decoding, which focuses on tokens with high entropy and certain semantic importance during the decoding process, branching out from these tokens to allow the model to actively explore new methods and strategies. Our experiments demonstrate that Entropy-Tree exhibits outstanding performance in improving the accuracy and calibration of multiple sampling.

7 Limitations and Future Work↩︎

We acknowledge that the current approach has some limitations. Our method requires access to token logits and self-attention scores, which can introduce additional latency. Moreover, some APIs do not support access to model logits or self-attention scores, potentially limiting the application of our method in black-box scenarios.

In the future, we plan to further expand upon the existing approach by integrating it into current LLM inference engines (such as vLLM [42]) and investigating the impact of our method on improving the efficiency and convergence speed of reinforcement learning sampling.

References↩︎