Benchmarking Uncertainty Metrics for LLM Target-Aware Search (2025)

Abstract: LLM search methods, such as Chain of Thought (CoT) and Tree of Thought (ToT), enhance LLM reasoning by exploring multiple reasoning paths. When combined with search algorithms like MCTS and Bandit methods, their effectiveness relies heavily on uncertainty estimation to prioritize paths that align with specific search objectives. However, it remains unclear whether existing LLM uncertainty metrics adequately capture the diverse types of uncertainty required to guide different search objectives. In this work, we introduce a framework for uncertainty benchmarking, identifying four distinct uncertainty types: Answer, Correctness, Aleatoric, and Epistemic Uncertainty. Each type serves different optimization goals in search. Our experiments demonstrate that current metrics often align with only a subset of these uncertainty types, limiting their effectiveness for objective-aligned search in some cases. These findings highlight the need for additional target-aware uncertainty estimators that can adapt to various optimization goals in LLM search.

## introduction llm search methods, such as chain of thought (cot) @xcite , tree of thought (tot) @xcite , and react @xcite , have significantly improved the performance of large language models (llms) by generating multiple intermediate reasoning steps. these methods can be further enhanced through algorithmic search, leveraging techniques like monte carlo tree search (e.g., lats, star) @xcite , bandit algorithms (e.g., longpo) @xcite , or gradient-style optimization (e.g., opro) @xcite . a key component in these approaches is uncertainty estimation, which plays a crucial role in prioritizing reasoning paths that are aligned with specific search targets, such as maximizing correctness, reducing noise, or improving diversity. prior work on uncertainty estimation in llms has largely focused on metrics derived from generation likelihoods @xcite @xcite , verbalized model confidence @xcite , consistency across outputs @xcite or model knowledge @xcite . while useful for calibration and risk assessment, it remains unclear whether these metrics are well-suited for search/optimization tasks, where uncertainty should help guide decision-making based on the targeted search objectives. for instance, search methods that optimize for factual accuracy need uncertainty signals that reflect model correctness, whereas strategies that encourage idea diversity need metrics sensitive to answer variability. to address this gap, we first identify four key types of uncertainty that are relevant to targetaware search: answer uncertainty (variability in output answers), correctness uncertainty (uncertainty about the factual validity of an answer), aleatoric uncertainty (intrinsic ambiguity in the query input), epistemic uncertainty (model uncertainty due to limited knowledge). we then present a unified benchmarking framework to evaluate how well existing uncertainty metrics approximate these uncertainty types in structured search scenarios. our pipeline constructs large tree-structured reasoning traces through extensive sampling and monte carlo approximations to estimate accurate target uncertainties. through experiments on multiple datasets and llms, we show that current metrics often align with only a subset of uncertainty types, limiting their effectiveness for objective-aligned search in some cases. these findings highlight the need for additional search-aware uncertainty estimators that can adapt to various optimization goals in llm search. 2 different uncertainty types for search uncertainty can arise in various forms, each representing different aspects of the problem and guiding the search process in unique ways. answer uncertainty (ansu) reflects the model's confidence and the diversity of possible answers. ansu describes how consistently the model produces the same answer after repeated sampling, but it does not guarantee correctness. if the model lacks necessary knowledge to answer the given question, it is reasonable for the output answers to be incorrect, even if low ansu is observed after repeated sampling. ansu is measured as the entropy of the output answer distribution. ansu (x) =i p(y i |x) log p(y i |x) where p(y i |x) is the probability of output answer y i obtain from {x j } given the input x. ansu can guide search algorithms to explore a richer solution space, increasing the variability of generated content. this can be particularly beneficial for tasks where diversity are highly valued. correctness uncertainty (cu) provides insights into the likelihood of answer correctness. high cu indicates that the model's prediction may be unreliable, suggesting the need for additional verification. cu is directly related to the accuracy of the prediction. when cu is low, the model's predictions are less likely to include a majority of false positives. cu is calculated as the entropy of the output correctness distribu-tion. cu (x) =i p(c i |x) log p(c i |x) where p(c i |x) represents the probability of correctness c i (whether an answer is correct or incorrect) obtain from {x j } given the input x. cu can guide search by narrow down the solution space and acquire the correct answer, reducing the likelihood of incorrect or irrelevant answers. aleatoric uncertainty (au) and epistemic uncertainty (eu) are two distinct sources of model uncertainty. au arises from the inherent noise in the data itself. eu, on the other hand, originates from the model's limitations and is related to its knowledge and understanding. au and eu are calculated using the deep-ensemble-decomposition method (balaji lakshminarayanan, 2016), where total model uncertainty is the sum of au and eu. in our context, θ, which represents model parameters in the original paper, corresponds to the rephrased questions in our setting. eu captures the disagreement between different perturbations, measured by the mutual information i(y ; θ|x). au reflects the inherent data noise and is represented as e q(θ|d) [h(q(y |x, θ))], where the expectation is taken over the questions θ. the total model uncertainty is expressed as : au and eu help identify whether uncertainty stems from data noise or model limitations, enabling targeted improvements like rephrasing questions or adding few-shot examples. ## benchmarking pipeline a reliable uncertainty metric should serve as an accurate estimator of its target uncertainty. in this study, we introduce a novel benchmarking pipeline designed to assess the effectiveness of uncertainty metrics in estimating target uncertainties within search (figure 1 ). ## experiments in this section, we use our benchmarking pipeline to evaluate six existing uncertainty metrics against the target uncertainty defined in section 2. more implementation details and prompt templates are shown in appendix a and b. ## conclusion we present a benchmarking framework for evaluating how well existing llm uncertainty metrics capture four types of uncertainty relevant to targetaware search: ansu, au, eu, and cu. through extensive experiments across models and datasets, we find that while many metrics correlate with certain uncertainty types-such as output diversity or input ambiguity-they often fail to align with correctness-oriented objectives. this mismatch reveals a major limitation in current uncertainty estimation methods, especially for applications requiring reliability and goal-directed reasoning. our findings highlight the need for developing new, search-aware uncertainty metrics that can adapt to diverse optimization goals and better guide decision-making in llm search.