1 Introduction↩︎

Uncertainty is a fundamental quantity that characterizes the degree of unknownness in stochastic systems [1]. Code Large Language Models (LLMs), which are increasingly integrated into next-generation Software Engineering (SE) workflows, are inherently stochastic due to their probabilistic generation mechanisms [2]. Quantifying their uncertainty is therefore a critical problem for reliable SE with LLMs. In code-related tasks, correctness is often discrete, and even minor errors can lead to severe functional, security, or safety consequences [3]. As a result, dependable automation requires the ability to distinguish between well-supported predictions and stochastic guessing. Beyond risk assessment, prior work has also shown that uncertainty estimates provide a valuable signal throughout the model lifecycle, including guiding alignment during fine-tuning [4], [5], selecting the best model among multiple candidates through routing [6], and enabling test-time scaling strategies [7], [8] in which models adapt their computation and execution paths to improve the ultimate performance.

To operationalize uncertainty measurement in practice, prior work has primarily relied on white-box [9], [10] or grey-box [11], [12] signals derived from the model’s internal states. Standard baselines typically exploit token-level predictive distributions (e.g., logits) to compute metrics such as entropy or perplexity, or analyze internal hidden representations to capture epistemic uncertainty. In some domains, these intrinsic signals often correlate strongly with correctness, enabling systems to flag potentially erroneous outputs. However, applying these traditional measurement techniques to the modern landscape of Code LLMs presents several fundamental challenges:

(1) The Black-Box Accessibility Barrier: The most capable models for code (e.g., GPT-5, Gemini 3 Pro) are increasingly deployed as closed-source services. These systems typically restrict access to internal weights, hidden states, and often even output logits. Consequently, white-box methods that rely on token entropy or internal activation analysis are rendered inapplicable in many real-world, API-driven environments.

(2) The “Token vs. Problem” Granularity Mismatch: Even when internal signals are accessible, the inference paradigm of LLM auto-regressive generation complicates uncertainty estimation. LLMs generate responses token-by-token, optimizing for local probability at each step. While standard metrics like perplexity or mean log-probability capture uncertainty at this syntactic, token-level distribution, they may fail to represent the problem-level distribution. A model may be highly confident in predicting the next keyword while remaining “uncertain” about the global logic. Consequently, aggregating local token probabilities can often be insufficient to quantify the semantic uncertainty of the entire program.

Attempting to overcome these limitations, a line of research adopts black-box multi-sample consistency measures, which estimate uncertainty by generating multiple outputs for the same input and assessing how much they agree with each other. The core idea is that confident models produce stable outputs, while large variation across samples signals higher uncertainty. This principle is closely related to Monte Carlo (MC) dropout [13], [14], which approximates uncertainty by sampling the model repeatedly. In natural language processing, this idea is effectively realized through semantic entropy [15], which goes beyond surface string matching and evaluates outputs based on their meaning, allowing different phrasings with the same intent to be treated as consistent. However, this leads to the third challenge:

(3) The Syntax–Semantics Gap: Unlike natural language, where meaning changes gradually, code is discrete and fragile: a single token difference can fundamentally change program behavior, even when embeddings appear similar. As a result, semantic entropy metrics developed for natural language often fail to distinguish harmless syntactic variation from critical logic errors in code.

To address these challenges, we propose a method grounded in a lightweight, black-box design philosophy. We observe that code possesses a unique, actionable property: executability. Even without access to model internals or ground-truth test cases, we can leverage the execution behavior of generated code to approximate semantic uncertainty. By sampling multiple programs and executing them against generated inputs, we can cluster solutions based on their runtime behavior rather than their textual surface form.

In this paper, we propose Code-MUE, a purely black-box, execution-based framework for quantifying uncertainty in Code LLMs. Unlike prior approaches that rely on inaccessible internal signals or superficial textual similarity, Code-MUE grounds uncertainty estimation in the observable runtime behavior of generated programs. Specifically, it first exposes a model’s latent uncertainty via Monte Carlo sampling and probes the resulting programs using an oracle-free hybrid test suite. It then organizes the resulting execution traces into a Semantic Interaction Graph, in which nodes represent programs and edges encode functional consensus. Finally, by interpreting this graph as a statistical density matrix, Code-MUE computes the Von Neumann entropy of its spectrum. This entropy-based measure captures the global structural diversity of the semantic solution space, enabling Code-MUE to distinguish between benign syntactic variation and substantive semantic ambiguity.

This paper makes the following contributions:

• New Perspective & Metric: We introduce a novel uncertainty metric tailored for Code LLMs that relies solely on execution feedback, validating our lightweight black-box philosophy by bypassing the need for model internals (logits)

• Large-Scale Empirical Study: We conduct a large-scale empirical study evaluating eight SOTA LLMs across four distinct SE tasks: code completion, program synthesis, program repair, and code translation. Our results demonstrate that Code-MUE achieves a strong negative correlation with functional correctness (Spearman’s \(\rho\) up to -0.98), significantly outperforming traditional lexical and embedding-based uncertainty baselines.

• Practical Implications for AI Safety and Reliability: We demonstrate the practical utility of Code-MUE as a robust mechanism for risk detection and selective prediction in SE tasks. By effectively discriminating between reliable and unreliable code generations (e.g., achieving AUROC scores exceeding 0.85 on multiple benchmarks), our framework enables systems to “abstain” or request human intervention when confidence is low.

In addition to our quantitative evaluation, we conduct in-depth qualitative case studies to diagnose specific failure modes, such as overconfidence and efficiency gaps, and discuss the theoretical properties of our metric in greater detail.

2 Related Work↩︎

2.1 LLM Uncertainty Measurement and Calibration↩︎

Uncertainty is a fundamental, objective quantity that characterizes the degree of unknownness inherent in a stochastic system. As modern LLMs are inherently stochastic due to both data uncertainty and probabilistic generation, uncertainty becomes an intrinsic property of LLM behavior and a critical signal throughout the LLM lifecycle. Prior work has demonstrated its importance in guiding model pre-training and fine-tuning [16], [17], supporting risk and error detection during inference [11], [18], enhancing reasoning and deliberation processes [19], and enabling selective prediction and abstention mechanisms [15].

In well-defined mathematical settings, such as a coin-flipping process, uncertainty admits a unique ground-truth value determined by the underlying probability distribution. In contrast, for complex real-world systems, and in particular for LLM inference, this ground-truth uncertainty is generally inaccessible. As a result, practical methods must rely on uncertainty estimation to approximate this latent quantity [20]. Existing approaches to uncertainty estimation in LLMs generally fall into three categories based on the information source they use:

(1) Grey-box Methods (Logit-based): These utilize output distributions (e.g., token entropy) [11], [21]. While computationally efficient, intrinsic signals may fail to capture semantic correctness, particularly in code, where high token probability does not guarantee functional accuracy [11], [12]. Furthermore, logit access is frequently restricted in commercial LLMs.

(2) White-box Methods (Internal States): These approaches derive uncertainty from internal activations, which can enhance quantification accuracy [9], [10], [22]–[24]. However, reliance on internal states makes them computationally expensive and often infeasible for closed-source models (e.g., GPT-4) where such access is blocked.

(3) Black-box Methods (Output Analysis): Essential for proprietary models, these methods infer uncertainty externally. Strategies include verbalized confidence, which is intuitive but prone to overconfidence bias [25]–[28]. Alternatively, sampling-based disagreement [13], [29] based on hidden space embedding representation is widely used in NLP [15], [30], [31] but struggles with code, where syntactic diversity often does not imply semantic divergence [11], [32]. While recent work explores symbolic execution to assess functional equivalence [32], such methods are often too computationally heavy or language-specific for general deployment.

Different from these prior approaches, our method estimates semantic uncertainty based on execution consensus across multiple generated programs. This design is motivated by a broader tradition in software engineering, where program executions provide quantitative evidence of program behavior. Classical fault localization leverages passing and failing executions together with coverage spectra to assign suspiciousness scores to program elements [33], [34]. Statistical debugging models predicate observations [35] and execution path profiles [36] collected during program execution to identify behaviors correlated with failures. Subsequent work has further analyzed spectrum-based suspiciousness formulas as measures of failure risk [37]. Beyond fault localization, dynamic anomaly detection infers runtime invariants to identify behavioral deviations [38], while metamorphic testing exploits relations among outputs from multiple executions when reliable test oracles are unavailable [39]. In a similar spirit, our approach treats execution agreement among independently generated programs as a signal for estimating semantic uncertainty.

Finally, another line of research focuses on uncertainty calibration [12], [40], which attempts to link raw uncertainty scores directly to prediction risk. In this setting, the ultimate goal is to transform an uncertainty score (e.g., entropy or variance) into a calibrated probability that serves as a faithful indicator of the model’s correctness, where such a mapping is often post-hoc (e.g., through machine learning). Representative techniques include Temperature Scaling [41], Platt Scaling [42], or Isotonic Regression [43], [44]. While uncertainty calibration and measurement are closely tied together, we emphasize that they are still distinct research directions. Calibration aims to regularize an existing signal, but its effectiveness is fundamentally limited by the quality of that signal. Our work focuses on the former challenge: developing a more robust methodology to measure uncertainty itself, specifically by leveraging execution-based multi-inference to capture semantic (rather than just textual) dispersion.

2.2 Risk Assessment of LLMs↩︎

Risk assessment for LLM-driven SE has drawn inspiration from metamorphic testing, employing tools like Drowzee [45] and MetaQA [46] to detect behavioral inconsistencies. However, these NLP-centric methods may struggle to address the structural constraints of code. While some approaches utilize LLM-as-a-Judge paradigms (e.g., CodeMirage [47]) or define hallucination taxonomies [48], recent findings such as CodeJudge [49] demonstrate that LLMs are often unreliable at detecting subtle logical errors in their own output. Alternatively, test oracle synthesis [50]–[52] offers a validation pathway but relies heavily on high-quality specifications that are frequently unavailable in real-world settings. To address this limitation, Allamanis et al. [53] introduce an unsupervised behavioral evaluation approach. The method estimates the correctness of code generated by LLMs by verifying whether semantic equivalence is maintained across code-to-description and description-to-code round-trip transformations. Another line of research examines internal model signals, such as hidden states or attention patterns [54]–[57], which correlate strongly with defects. Despite their effectiveness, these white-box methods incur high computational overhead and are inapplicable to closed-source models.

3 Background and Motivating Example↩︎

Uncertainty signals derived solely from a model’s internal predictive probabilities, such as perplexity or token-level log-likelihood, have been shown to correlate only weakly with LLM correctness in certain scenarios [11], [26], [58]. This limitation exposes a fundamental challenge in uncertainty estimation for LLMs: a pronounced gap between token-level uncertainty, which reflects confidence in local syntactic choices, and problem-level uncertainty, which captures confidence in the correctness of the global logical solution. To bridge this gap, a complementary line of work seeks to estimate uncertainty directly at the problem level, often from a Bayesian perspective.

More specifically, the LLM can be viewed as a parametric model \(P(Y|X, \theta)\) where the parameters \(\theta\) are treated as random variables. The central problem in uncertainty measurement is to obtain the conditional probability \(\eta(x) = P(Y|X=x)\), where \(x\) is the model input (e.g., LLM prompt) and \(Y\) is the output (e.g., generated answers instead of the next token). This \(\eta(x)\) is the foundation of DNN risk assessment and has a wide range of applications [18]. However, its true value is computationally intractable. Instead, it can be estimated through:

\[\label{eq:estimation} \eta(x) \approx \int P(Y|X=x, \theta) \cdot p(\theta|\mathcal{D}) d\theta\tag{1}\]

where \(\mathcal{D}\) is the training data. In the Bayesian Approximation framework, the intractable posterior distribution \(p(\theta|\mathcal{D})\) is estimated by a variational distribution \(q(\theta)\). From this distribution, multiple parametric model instances are sampled for a fixed input \(x\) [13], [14], allowing the integral to be approximated by averaging the resulting predictive distributions (i.e., Monte Carlo approximation). In traditional deep neural networks, the predictive distribution is often approximated by the classification confidence obtained from a single forward pass [13]. In contrast, the autoregressive generation mechanism of LLMs renders this approximation inadequate, as local token-level uncertainty can correlate poorly with global, answer-level correctness (as discussed earlier). To better capture global uncertainty, recent work has shifted toward estimating uncertainty in the semantic space induced by the model’s sampled generation traces [11], [15]. Multiple samples are obtained under stochastic inference. By characterizing their distribution within the semantic space, information-theoretic measures such as entropy can be used to quantify uncertainty in the model’s high-level behavior with respect to the given \(x\). Intuitively, a widely dispersed set of samples indicates high uncertainty, whereas tightly clustered samples suggest confident, stable behavior. Despite its theoretical appeal, a central open challenge remains: how to construct a semantic space that faithfully captures meaningful divergence among sampled outputs.

To operationalize this semantic space, existing approaches typically approximate the distance \(d(\mathbf{y}, \mathbf{y}')\) using surface-form similarity metrics (e.g., BLEU or CodeBLEU) [11], distances in dense embedding spaces [30], [59], or discrete equivalence relations induced by latent classifiers (e.g., NLI-based Semantic Entropy [15]). Although these methods have proven effective in natural language processing, we argue that defining a robust distance metric over any of these representations faces fundamental limitations in code-related tasks. The crux of the issue is a misalignment between these proxy measures and the true objective of interest: functional divergence in program behavior.

We illustrate this limitation in Fig. 1 via a comparative analysis of two structurally isomorphic yet functionally opposite algorithms, FindMax and FindMin. As shown, the two implementations share an almost identical syntactic structure, including looping constructs, variable initialization patterns, and comparison logic. Consequently, the Lexical Similarity Heatmap indicates near-perfect overlap, and the CodeBERT Embedding Space projects these distinct traces into the same tight cluster, implying a semantic distance \(d(\mathbf{y}, \mathbf{y}') \approx 0\). However, despite this apparent convergence in the standard semantic space, the algorithms are diametrically opposed in their functional objectives. A single token variation (flipping \(>\) to \(<\)) creates a massive functional cliff that these metrics fail to register. This demonstrates that while the model’s traces may appear stable and low-uncertainty under traditional NLP metrics, the functional epistemic uncertainty remains dangerously high, as the metric cannot distinguish between the correct solution and its logical inverse.

To bridge the gap between superficial similarity and true functional equivalence, we exploit a fundamental distinction between code and natural language. Our core insight is that code is not merely text; it is a structured artifact that specifies executable behavior. As a result, code exhibits an intrinsic property: it admits execution that yields observable outputs that reflect the true meaning of the code. By shifting the measurement of sampling trace divergence from ambiguous embedding spaces to the concrete execution space, we ground Bayesian uncertainty estimation in observable behavior. Accordingly, rather than asking “Do these two traces look similar?”, we ask “Do these two traces behave identically?”, yielding a more precise and semantically aligned signal of functional uncertainty.

4 Method↩︎

4.1 Overview↩︎

The fundamental challenge addressed in this work is how to characterize the distribution of model-generated programs corresponding to a given prompt \(x\) in semantic space. Building on the observation that source code is intrinsically executable, we introduce Code-MUE, an uncertainty quantification method built upon the graph structure of code samples in semantic space. Code-MUE estimates model uncertainty through functional equivalence rather than surface-form similarity. In contrast to prior approaches targeting natural language, such as lexical overlap or embedding-based distances, the proposed approach anchors uncertainty estimation in the observable runtime behavior of generated programs.

To operationalize this principle, we organize the samples produced by a code generation model for a given query into a structured probabilistic object termed the Semantic Interaction Graph (SIG). In this graph, each node corresponds to a candidate program produced by the model, while edges encode semantic agreement derived from dynamic execution traces (e.g., input–output behaviors). Two programs are connected when their executions exhibit equivalent or sufficiently similar functional behavior under a shared execution context. This graph-based abstraction enables reasoning about uncertainty at a global level. Rather than relying on isolated pairwise comparisons, SIG captures the geometric and topological structure of the solution space induced by program semantics. Intuitively, a confident model produces a highly concentrated graph structure that has a single, densely connected semantic component. Such a structure indicates a strong consensus among generated programs. Conversely, an uncertain model can generate a fragmented graph with multiple weakly connected or disconnected components, reflecting competing semantic interpretations of the task.

As illustrated in Figure 2, Code-MUE performs semantic uncertainty estimation through a three-stage pipeline:

1. Probabilistic Sampling and Test Input Synthesis. We expose the model’s latent uncertainty by sampling a diverse ensemble of candidate programs via temperature-based stochastic decoding. Concurrently, we construct a hybrid input-only probe set combining rule-based boundary cases with LLM-generated nominal inputs to systematically probe the runtime behavior of the sampled programs.

2. Semantic Interaction Graph Construction. We execute the sampled programs against a hybrid test suite that combines nominal inputs with boundary cases, thereby exercising both typical and corner-case behaviors. Based on the resulting execution outcomes, we construct a pairwise semantic similarity matrix that captures functional consensus between programs.

3. Graph-based Uncertainty Quantification. We interpret the induced semantic interaction graph as a quantum-inspired density matrix whose spectrum reflects the global connectivity structure of the solution space. By computing the corresponding Von Neumann entropy, we obtain a robust scalar measure of semantic uncertainty without requiring expected ground truth.

4.2 Probabilistic Sampling and Test Input Synthesis↩︎

Our framework operates under a strict black-box setting, assuming no access to the model’s internal logits or gradients. The foundation of our uncertainty estimation lies in approximating the model’s system-level semantic distribution through stochastic sampling and dynamic probing.

4.2.1 Response Sampling via Temperature-based Stochastic Decoding↩︎

Given a coding prompt \(x\), the first step is to externalize the model’s uncertainty into a discrete set of observable programs. We query the LLM \(\mathcal{M}\) \(N\) times with an identical prompt, producing a response ensemble \(\mathcal{P} = \{p_1, p_2, \dots, p_N\}\). Crucially, to obtain a valid probabilistic estimate of uncertainty, this generation process should reflect variability in the model’s predictive distribution rather than repeatedly collapsing to its single most likely output. To this end, we employ stochastic decoding with a fixed sampling temperature (e.g., \(\tau=1.0\) [21]) rather than greedy decoding. Here, temperature refers only to the decoding hyperparameter that controls sampling diversity, not to post-hoc temperature scaling for calibration [12]. This ensemble \(\mathcal{P}\) thereby serves as an empirical proxy for the model’s true output distribution, enabling the quantification of variance in the subsequent semantic analysis.

4.2.2 Hybrid Input Synthesis↩︎

To quantify the functional divergence within \(\mathcal{P}\), we require a set of test inputs capable of distinguishing between semantically distinct implementations. we require only valid inputs to observe execution traces, effectively bypassing the “Oracle Problem” inherent in generating ground-truth assertions.

We construct a probe set \(\mathcal{I}\) of size \(K\) using a Hybrid Synthesis Strategy. This strategy is designed to maximize the discriminative power of our similarity metric by combining deterministic boundary probing with semantic-aware nominal testing.

4.2.2.1 1. Type-based Boundary Inputs (\(\mathcal{I}_{\text{edge}}\)).

To expose fragility in conditional logic and error handling—where subtle semantic deviations often manifest, we allocate a heuristic portion of the budget (\(K/2\)) to edge-case testing. We employ static analysis to parse the function signature of the generated code, mapping detected types to a rigorous set of “corner values” designed to trigger boundary behaviors:

• Numeric (int, float): Critical values including Zero (\(0\), to test logic boundaries), negative unity (\(-1\)), extreme bounds (e.g., sys.maxsize), and precision singularities (e.g., 1e-9).

• Sequence (str, list, tuple): Empty sequences (e.g., "", []) to expose IndexError vulnerabilities and singleton collections (targeting fencepost errors).

4.2.2.2 2. LLM-guided Semantic-Aware Nominal Inputs (\(\mathcal{I}_{\text{nom}}\)).

While edge cases capture fragility, they may fail to verify the core algorithmic logic. We allocate the remaining budget (\(K/2\)) to nominal inputs that represent “typical” usage scenarios. Leveraging the LLM’s semantic understanding of the task description \(T\), we prompt the model to synthesize representative inputs (e.g., “Generate 5 diverse input arrays for a quicksort implementation”). Notice that we never ask the LLM to generate expected outputs or assertions, and these inputs are not used to decide whether a program is correct. They are used only to induce comparable execution signatures across the sampled programs.

4.2.2.3 Final Probe Set.

We use a \(1{:}1\) split between edge-case and nominal probes by default (i.e., \(|\mathcal{I}_{\text{edge}}| = |\mathcal{I}_{\text{nom}}| = K/2\)). If the number of valid boundary inputs is insufficient (e.g., due to limited type-specific values for a given signature), we compensate by generating additional LLM-based nominal inputs to ensure that the total number of test cases remains \(K\). The final execution probe set is the union \(\mathcal{I} = \mathcal{I}_{\text{edge}} \cup \mathcal{I}_{\text{nom}}\). By broadcasting these inputs to all \(N\) responses in \(\mathcal{P}\), we obtain the raw I/O streams necessary for the subsequent similarity analysis.

4.3 Semantic Interaction Graph Construction↩︎

With the candidate ensemble \(\mathcal{P}\) and the probe set \(\mathcal{I}\) generated, we proceed to construct the latent semantic space of LLMs’ output. This phase entails two primary operations: executing the ensemble to harvest observable output traces, and determining the functional consensus among programs to construct the Semantic Interaction Graph.

4.3.1 Dynamic Feature Profiling↩︎

To characterize the semantics of each program \(p_i \in \mathcal{P}\) beyond surface-level syntax, we employ a sandboxed execution engine. We execute every generated program \(p_i\) against the full probe set \(\mathcal{I} = \{x_1, \dots, x_K\}\). For a specific input \(x_k\), the execution outcome \(o_{i,k}\) is mapped to a discrete state in the observable output space \(\Omega\). We categorize these states into three distinct behavioral modes to maximize the resolution of our uncertainty measurement:

• Return Value (\(v\)): The code executes successfully and returns a specific value (e.g., 42, a list). This represents the standard functional behavior.

• Differentiated Runtime Exception (\(E_{\text{type}}\)): The program halts due to an error. Crucially, we treat the exception type as a semantic feature (e.g., distinguishing an IndexError from a RecursionError). This distinction is vital, as different crash modes often imply distinct underlying logic faults.

• Timeout (\(T\)): The execution exceeds a predefined time limit, indicating potential infinite loops or inefficient algorithms.

Formally, for each program \(p_i\), we aggregate these outcomes into an Execution Signature Vector \(\mathbf{O}_i = [o_{i,1}, o_{i,2}, \dots, o_{i,K}]\), where \(\mathbf{O}_i \in \Omega^K\). If \(p_i\) fails an initial syntax check, it is marked as \(\text{Invalid}\) and treated as a disjoint node in the subsequent graph analysis.

4.3.2 Behavioral Similarity Calculation↩︎

We construct the pairwise similarity matrix \(\mathbf{W} \in \mathbb{R}^{N \times N}\) to represent the semantic coupling between samples. The entry \(W_{ij}\) quantifies the agreement between the execution signature vectors \(\mathbf{O}_i\) and \(\mathbf{O}_j\).

4.3.2.1 Handling Syntax Errors (The Isolation Rule).

We define syntax errors as having “null semantic value” since they cannot perform the task. Therefore, if either \(p_i\) or \(p_j\) contains a syntax error, their semantic similarity is zero (unless \(i=j\), where self-similarity is preserved as 1 for matrix stability): \[W_{ij} = 0 \quad \text{if } i \neq j \land (\text{is\_syntax\_error}(p_i) \lor \text{is\_syntax\_error}(p_j))\] In the graph view, these samples become isolated nodes, contributing to higher entropy (uncertainty).

4.3.2.2 Handling Timeouts.

Timeouts are treated separately from ordinary runtime exceptions because a timeout does not expose a comparable output value. For distinct programs, we therefore do not count matching timeouts as semantic agreement: if \(i \neq j\) and both executions exceed the sandbox time limit on input \(x_k\), the comparison for that input contributes \(0\) to \(W_{ij}\). Self-similarity is still preserved through \(W_{ii}=1\). This conservative rule avoids falsely merging programs that may time out for different reasons, such as infinite loops versus extremely slow but terminating computations.

4.3.2.3 Measuring Functional Consensus.

For any two syntactically valid programs \(p_i\) and \(p_j\), we calculate their similarity by measuring the proportion of test inputs on which they exhibit identical behavior. Let \(\mathbb{I}(\cdot)\) be the indicator function which equals 1 if the condition is true and 0 otherwise. The similarity is defined as:

\[W_{ij} = \frac{1}{K} \sum_{k=1}^{K} \mathbb{I}(o_{i,k} \equiv o_{j,k})\]

Here, the condition \(o_{i,k} \equiv o_{j,k}\) holds if:

• Both return the same numerical/string value.

• Both trigger the same type of Runtime Error (e.g., both raise ValueError).

The resulting metric \(W_{ij} \in [0, 1]\) represents the strength of the semantic link between \(p_i\) and \(p_j\). The matrix \(\mathbf{W}\) thus serves as the weighted adjacency matrix for the Semantic Interaction Graph, where dense clusters indicate strong functional consensus.

4.4 Graph-based Uncertainty Quantification↩︎

Having constructed the similarity matrix \(\mathbf{W}\) from the dynamic execution traces, we now proceed to quantify the system-level uncertainty. This step is crucial to transforming the Monte Carlo samples drawn from the posterior to a single score (as formulated in Section 3). While performing moment-based aggregation of \(\mathbf{W}\), such as computing the average pairwise agreement (\(\bar{W}\)), is straightforward, such measures capture only a first-order characterization of behavioral agreement. For instance, average pairwise agreement can be interpreted as the probability that two randomly sampled generated programs exhibit identical behavior on the probe set. Although informative, this statistic collapses the full pairwise structure into a single expectation. Consequently, it is insensitive to the internal organization of agreement within the ensemble: the same value of \(\bar{W}\) may arise when most programs form a dominant agreement cluster with a few outliers, when programs partition into several balanced behavioral groups, or when weak partial agreement is diffusely distributed across the ensemble.

This limitation is structural. The matrix \(\mathbf{W}\) encodes not only the overall extent of agreement, but also how agreement is organized across samples. To preserve this richer relational structure, we reinterpret \(\mathbf{W}\) as a graph whose nodes correspond to generated programs and whose edge weights quantify behavioral agreement. This graph representation makes it possible to characterize whether the ensemble concentrates around a single dominant consensus region, separates into several competing regions, or fragments into many isolated behaviors. We formalize this induced graph structure as follows.

4.4.1 Semantic Interaction Graph Construction↩︎

We conceptualize the set of \(N\) generated programs as a Semantic Interaction Graph, denoted as \(\mathcal{G} = (\mathcal{V}, \mathcal{E}, \mathbf{W})\).

• Nodes (\(\mathcal{V}\)): Each node \(v_i\) corresponds to a generated sample \(p_i\).

• Edges (\(\mathbf{W}\)): The graph is fully connected and weighted. Crucially, the similarity matrix \(\mathbf{W}\) derived in Section 4.3 serves as the Adjacency Matrix of this graph. The weight \(W_{ij}\) represents the functional coupling strength between program \(p_i\) and \(p_j\).

4.4.2 Spectral State and Density Matrix↩︎

Once the ensemble is represented as a weighted graph, its global organization is encoded in the spectrum of the corresponding adjacency operator. This is a standard principle in spectral graph analysis: local edge weights define a matrix operator, and the eigenvalues of this operator summarize coarse structural properties such as the number, strength, and separation of connected regions. In our setting, these regions correspond to behavioral modes among generated programs.

We therefore construct the density matrix \(\boldsymbol{\rho}\) by trace-normalizing the behavioral agreement matrix \(\mathbf{W}\) before analyzing its eigenvalue distribution. The raw matrix \(\mathbf{W}\) encodes the behavioral coupling among generated programs, but its scale depends on the number of samples. To compare ensembles through their spectral structure, we normalize \(\mathbf{W}\) so that its total spectral mass is fixed:

\[\boldsymbol{\rho} = \frac{\mathbf{W}}{\text{Tr}(\mathbf{W})} = \frac{\mathbf{W}}{N}\]

where \(\text{Tr}(\mathbf{W}) = N\) due to the reflexive property (\(W_{ii}=1\)). Thus, \(\boldsymbol{\rho}\) is the density matrix in our formulation, obtained by trace-normalizing the behavioral agreement matrix \(\mathbf{W}\). Conceptually, it describes the mixed semantic state of the LLM’s generation process. We then perform eigen-decomposition on \(\boldsymbol{\rho}\) to obtain its spectrum \(\Lambda = \{\lambda_1, \lambda_2, \dots, \lambda_N\}\), subject to \(\lambda_k \ge 0\) and \(\sum \lambda_k = 1\).

4.4.2.1 Physical Interpretation of Eigenvalues.

The eigenvalues \(\Lambda\) provide a profound insight into the model’s internal state. They represent the probability distribution over the Latent Semantic Modes (i.e., independent functional clusters) within the ensemble:

• Pure State (\(\lambda_1 \approx 1\)): Corresponds to a rank-1 matrix where all samples collapse into a single semantic consensus. The model is “purely” confident in one logic.

• Mixed State (Dispersed \(\lambda\)): Indicates that the probability mass is split among multiple conflicting modes. The model is oscillating between different functional realizations.

4.4.3 Von Neumann Entropy Calculation↩︎

Finally, given the normalized spectral state \(\boldsymbol{\rho}\), uncertainty corresponds to how concentrated or dispersed its spectral mass is across behavioral modes. We use Von Neumann entropy [60] because it is the standard entropy functional for such matrix-valued states: it measures the mixedness of \(\boldsymbol{\rho}\) rather than only the average amount of pairwise disagreement:

\[H_{\text{spec}} = - \text{Tr}(\boldsymbol{\rho} \ln \boldsymbol{\rho}) = - \sum_{k=1}^{N} \lambda_k \ln(\lambda_k)\]

\[U(\mathcal{P}) = \frac{H_{\text{spec}}}{\ln(N)}\]

where the normalization factor \(\ln(N)\) corresponds to the maximum entropy state (the identity matrix \(\mathbf{I}_N\), representing \(N\) distinct, mutually exclusive semantics).

Unlike token-level Shannon entropy, which measures uncertainty from the model’s predictive probability distribution, Von Neumann entropy quantifies uncertainty over the execution-based semantic interaction graph, providing a soft and topology-aware characterization of the generated solution space. This quantity, \(U(\mathcal{P}) \in [0, 1]\), serves as a structurally informed measure of semantic uncertainty: \(U(\mathcal{P}) \to 0\) indicates convergence toward consistent semantic behavior, while \(U(\mathcal{P}) \to 1\) signifies high semantic divergence among candidate programs.

5 Evaluation↩︎

5.1 Experimental Setup↩︎

Models. We conduct a large-scale evaluation across eight LLMs, evenly split between closed-source API-based systems and open-source instruction-tuned models. The closed-source set includes gpt-4.1-mini [61], gpt-4.1-nano [62], claude-3-haiku [63], and gemini-2.5-flash-lite [64]. These models represent widely deployed, production-grade systems that are optimized for low latency and strong instruction following, and they provide competitive reference points for uncertainty evaluation under real-world API settings. The open-source set includes Llama 3.1-8B-Instruct [65], Mistral-7B-Instruct-v0.3 [66], DeepSeek-Coder-6.7B-Instruct [67], and Qwen2.5-7B-Instruct [68]. These models cover multiple major open model families and include both general-purpose instruction-tuned models and code-specialized models (i.e., DeepSeek-Coder).

Datasets. We evaluate on four established code benchmarks, each mapped to a distinct task type, to probe uncertainty under different generation constraints. HumanEval [69] is used as a function-level code completion task, where the model completes an implementation conditioned on a provided function scaffold and natural-language specification. MBPP (Mostly Basic Python Problems) [70] is treated as program synthesis, emphasizing specification-to-code generation with comparatively weaker scaffolding than HumanEval. QuixBugs [71] is used for program fixing, where the model must repair a buggy implementation to satisfy the intended behavior. Project CodeNet [72] is used for program translation [73], where the model translates an implementation across programming languages while preserving semantics. Across all tasks, functional correctness is assessed by executing model outputs against the benchmark-provided tests or reference I/O where available. Due to the substantial computational cost associated with repeated sampling and dynamic execution¹, we evaluate MBPP and CodeNet on randomly sampled subsets of 200 tasks each, while using the full benchmark for HumanEval and QuixBugs. Under this setup, overall functional correctness results are summarized in Table 1. We use pass@k [69] to measure baseline code generation performance, estimating the probability that at least one of k generated samples passes all functional tests. Method Setup. For each problem instance, we sample \(N=100\) candidate programs and execute them on a shared probe set. For uncertainty estimation, we draw up to \(K=20\) valid probe inputs per task from a pre-generated input pool using a deterministic task-level seed. These probe inputs are used only to compare the behavior of generated programs; their expected outputs are not used when constructing the semantic similarity matrix. Each generated program is executed in a separate worker process under a restricted Python environment. The harness disables direct termination calls such as exit, quit, and sys.exit, and applies a five-second timeout to each program-input execution. This threshold follows common practice in code evaluation, where execution limits are typically set to a few seconds [69], [74]. Execution outcomes are normalized into return values, runtime exception types, timeout markers, or syntax/compile failures.

Baselines. To align with real-world deployment scenarios involving closed-source LLMs, our evaluation targets black-box uncertainty measurement. We therefore exclude white-box or grey-box approaches that rely on token-level logits or internal activation states, as such signals are frequently inaccessible in commercial API-based services. Instead, we compare Code-MUE against representative multi-sample consistency baselines that derive uncertainty solely from observable outputs: (1) Lexical Semantic Entropy: A text-based diversity metric that clusters responses using surface-form similarity (e.g., ROUGE-L overlap) to estimate entropy [11]. (2) Embedding Semantic Entropy: A consistency measure that clusters responses based on their distances in a dense embedding space to capture semantic divergence.² [15], [59] (3) Length Variance (Coefficient of Variation): A heuristic that quantifies uncertainty via the dispersion of response lengths (normalized by the mean). This metric is grounded in the intuition that a confident model should consistently produce solutions of comparable structural complexity. We are further motivated by recent findings [75] that point out the LOC of answers as critical indicators for characterizing model errors. (4) Logit-based: The classical intrinsic baseline that estimates uncertainty using token-level predictive probabilities. Concretely, for each generated program we compute the mean negative log-probability of the generated top-1 token at each step, and then average this score across the \(N\) sampled generations to obtain a single scalar per instance [21].

Research Questions. While uncertainty metrics have broad applicability across the LLM lifecycle from guiding alignment to model routing, we focus here on risk assessment as the most direct and critical application for reliable Software Engineering, leaving other use cases for future work. We structure our evaluation to answer three core questions, progressing from the metric’s fundamental validity to its practical utility and behavioral boundaries. First, we establish the baseline validity by investigating whether the estimated uncertainty serves as a reliable proxy for functional correctness (RQ1). Next, we evaluate its effectiveness in two actionable downstream scenarios: selective prediction (filtering out unreliable generations) and response selection (identifying the optimal candidate from a set) (RQ2). Finally, we diagnose the limitations of our approach through qualitative case studies of failure modes, such as overconfidence, to understand when the estimation fails (RQ3):

• RQ1 (Correctness Alignment): Can Code-MUE reliably distinguish between functionally correct and incorrect code generations?

• RQ2 (Practical Utility): Can the uncertainty signal be effectively leveraged for risk detection and candidate re-ranking?

• RQ3 (Case Studies on Uncertainty-Accuracy Misalignments): What do overconfident and underconfident outliers reveal about the limitations of Code-MUE?

5.2 RQ1: Correctness Alignment↩︎

Goal. We first validate whether Code-MUE serves as a faithful proxy for code generation quality—whether lower uncertainty scores reliably correspond to higher functional correctness.

5.2.1 Experimental Design↩︎

We first assess how well each metric aligns with correctness by computing its Spearman correlation with instance-level Pass@1, where Pass@1 is a binary indicator of whether the returned program passes all tests. Since higher uncertainty should correspond to lower Pass@1, we expect negative correlations, with larger absolute values (i.e., closer to \(-1\)) indicating stronger alignment. To further evaluate discriminative ability, we assign each instance a binary label: Solved if at least one of the \(N\) sampled candidates passes all tests, and Unsolved otherwise. We then measure how effectively each uncertainty metric separates these two groups using AUROC.

5.2.2 Results↩︎

Table 2 presents a systematic evaluation of Code-MUE against three baseline methods across four datasets and eight LLMs. The results underscore the superior capability of our method in quantifying semantic uncertainty.

5.2.2.1 Strong Alignment with Correctness.

Code-MUE exhibits the strongest negative correlation with generation accuracy across nearly all experimental settings. Notably, on the HumanEval dataset, our method achieves a near-perfect monotonic relationship with model performance, reaching Spearman correlations of \(\rho = -0.987\) (GPT-4.1-mini) and \(\rho = -0.985\) (Gemini-2.5-Flash-Lite). In contrast, the best-performing baseline (Lexical Entropy) typically yields correlations between \(-0.2\) and \(-0.5\). This significant margin suggests that our graph-based metric serves as a highly calibrated indicator: distinct from surface-level variations, low spectral entropy accurately reflects the model’s true confidence in the functional correctness of the code.

5.2.2.2 Superior Discrimination Capability.

In terms of binary error detection (AUROC), our method outperforms baselines in 26 out of 32 scenarios, consistently maintaining scores above \(0.85\) on CodeNet and MBPP. The substantial gap between our method and the Length or Embedding baselines highlights the limitation of static features. By constructing similarity graphs based on execution semantics, our approach successfully groups syntactically diverse but functionally equivalent solutions, thereby preventing false alarms caused by mere stylistic variations. We also observe that the classical logit-based baseline is generally weaker and less stable than multi-sample agreement baselines on these code tasks, highlighting the token-vs.-problem granularity mismatch.

5.2.2.3 Robustness and Outlier Analysis.

The effectiveness of our metric remains robust across diverse model architectures (from 7B open-weights models to GPT-4 class proprietary models) and problem types. A minor anomaly is observed in the QuixBugs dataset, where baselines occasionally surpass our method in AUROC (e.g., with Qwen2.5-7B). We attribute this to the dataset’s extremely small sample size (\(|\mathcal{D}| = 40\)), which introduces high statistical variance in binary classification thresholds. However, even in these cases, our method retains the highest Spearman correlation (e.g., \(-0.978\) for GPT-4.1-mini), confirming that the underlying trend of our uncertainty estimation remains the most reliable reflection of model confidence.

5.3 RQ2: Practical Utility (Rejection & Selection)↩︎

Goal. Beyond establishing a statistical correlation, the ultimate test of an uncertainty metric lies in its actionable value for downstream SE tasks. In real-world deployments, practitioners need more than just a correctness probability; they require a reliable signal to govern decision-making—specifically, to decide when to trust a model’s output and which output to trust. We therefore evaluate the utility of Code-MUE in two critical scenarios: (1) Selective Prediction (Rejection), where the system safeguards reliability by abstaining from answering when confidence is low; and (2) Response Selection (Re-ranking), where the system automatically discriminates the optimal solution from a noisy set of candidates without test oracles such as expected outputs, assertions, or reference implementations.

5.3.1 Experimental Design↩︎

Scenario I: Selective Prediction (Rejection). A lower AURC indicates a better estimator, meaning the system can significantly reduce error rates by rejecting a small fraction of uncertain predictions. We quantify the effectiveness of selective prediction using the Area Under the Risk-Coverage Curve (AURC) [76], a widely established metric in the literature [77]. Formally, we rank all dataset samples by their estimated uncertainty and compute the risk (error rate) \(r(c)\) at each coverage level \(c \in [0, 1]\), where \(c\) represents the proportion of the most confident samples retained. The AURC integrates this risk profile, where a lower value indicates a superior capability to concentrate errors within the rejected (high-uncertainty) subset.

Scenario II: Response Selection (Re-ranking). To further demonstrate the extensibility of Code-MUE to real-world workflows, we apply our framework to the unsupervised response selection task, beyond the risk assessment. Here, the goal is to identify the optimal solution \(\hat{y}\) from the sampled ensemble \(\mathcal{P}\) without access to ground-truth test cases. Our approach relies on the Semantic Consensus Hypothesis: we posit that while incorrect programs exhibit chaotic failure modes, correct programs are functionally equivalent and coalesce into a dense, highly connected cluster. To operationalize this application, we exploit the unique topological properties of the Semantic Interaction Graph constructed by Code-MUE. Unlike standard baselines that produce only scalar scores, our graph formulation allows us to propose a Centrality-based Selection strategy: \[\hat{y} = y_i \quad \text{where} \quad i = \arg\max_{j} \text{Centrality}(v_j)\] We use Eigenvector Centrality to identify the semantic “center” of the sampled distribution. We measure performance using Selection Accuracy on Solvable Tasks—defined as the percentage of tasks where the selected \(\hat{y}\) is correct, considering only tasks where at least one correct candidate exists.

5.3.2 Results↩︎

5.3.2.1 Risk-Coverage Performance.

Figure 3 presents the risk-coverage curves for HumanEval. The results demonstrate that Code-MUE (solid red line) significantly outperforms all baselines.

• Steep Descent: Our curves exhibit the steepest descent at high coverage levels. For instance, by rejecting only the top \(10\%\) to \(20\%\) most uncertain samples, the risk (error rate) drops precipitously. This indicates that our metric effectively flags the most egregious errors (e.g., hallucinations or timeouts).

• Lower AURC: The Lexical and Length-based baselines (blue and grey lines) appear flatter, closer to the diagonal (random rejection), suggesting these surface-level metrics struggle to distinguish hard failures from correct logic. In contrast, our semantic graph approach consistently achieves the lowest AURC, providing a reliable “fail-safe” mechanism for deployment.

5.3.2.2 Unsupervised Response Selection.

Figure 4 illustrates the selection utility on solvable tasks.

• High Precision Re-ranking: Across all eight models, our centrality-based method achieves impressive selection accuracy, often exceeding \(80\%\) (e.g., on CodeNet) and even reaching \(>90\%\) on strong models like GPT-4.1-mini and Gemini-2.5-Flash-Lite.

• Validation of Consensus Hypothesis: This high accuracy strongly validates our core hypothesis: correct solutions form a semantic consensus (a dense clique in the graph), leading to high eigenvector centrality. Conversely, incorrect solutions (due to logic bugs or syntax errors) tend to be isolated or form smaller, fragmented clusters.

• Practical Implication: This result suggests that generating \(N\) samples and selecting the “semantic center” can substantially improve the chance of selecting a correct answer when at least one correct candidate is present, without requiring expensive or unavailable unit tests during inference.

5.4 RQ3: Case Studies on Uncertainty-Accuracy Misalignments↩︎

While Code-MUE generally exhibits a strong negative correlation with model performance (i.e., higher uncertainty typically implies lower accuracy), we observed a distinct cluster of outliers: samples with near-zero uncertainty but zero Pass@1 accuracy. To determine whether this phenomenon arises from inaccuracies in uncertainty estimation or instead reflects cases where the model is confidently incorrect, we conduct a series of case studies and identify a representative pattern. A very common pattern is Overconfident Error. In these cases, the model does not exhibit semantic confusion or chaotic behavior; rather, it consistently converges to an incorrect solution due to systematic biases induced by the prompt. We present one representative example in the main paper and provide additional case studies in the supplementary material [78].

5.4.1 Case I: Conceptual Ambiguity (HumanEval/163)↩︎

In this task, the model is asked to generate “even digits” between two integers. The DeepSeek-Coder-6.7b-Instruct model achieved an extremely low entropy of 0.0485, indicating high internal consensus. However, the Pass@1 score was 0.0:

Analysis: As shown in Figure 5, the model consistently generated logic to find even integers (e.g., returning 10, 12) rather than even digits (which are strictly 0, 2, 4, 6, 8). While the example provided in the prompt (\(2, \dots, 8\)) satisfies both definitions, the logic fails for multi-digit inputs (e.g., 12 is an even integer, but not a digit). The model failed to distinguish the subtle semantic difference, likely because "finding even integers in a range" is a significantly more frequent pattern in the pre-training corpus than “finding even digits.” This frequency bias leads to a Confident but Wrong state, which our metric accurately characterizes as low entropy (high consensus) on the incorrect behavior.

5.4.2 Case II: The Efficiency Gap (HumanEval/83)↩︎

Next, we identify a contrasting scenario where the model exhibits High Uncertainty despite converging to a logically correct (but computationally inefficient) solution. We examine HumanEval/83, which requires counting \(n\)-digit numbers that start or end with ‘1’.

Analysis: As shown in Figure 6, the model defaulted to a brute-force simulation (\(O(10^n)\) complexity) instead of the expected combinatorial solution (\(O(1)\)). When \(n\) is large (e.g., \(n=10\)), the execution exceeds the sandbox time limit.

Method Implication: In Code-MUE, we adopt a conservative stance: execution outputs are the only ground truth for semantics. When two programs both timeout, their outputs are undefined. Unlike syntax errors (which can be statically grouped), timeouts may stem from diverse causes (e.g., infinite loops vs. massive calculations). Consequently, to avoid falsely assuming consensus, we conservatively define the semantic similarity between distinct timed-out instances as zero. This design choice results in High Entropy for this case, even though the generated codes are textually similar. We argue this provides a critical “Fail-Safe” property: a code that cannot be executed within reasonable limits is functionally equivalent to an uncertain or unreliable solution.

5.4.3 Summarization↩︎

These case studies highlight a critical property of our Uncertainty Estimation framework:

• High Uncertainty implies the model is oscillating between multiple potential solutions (a sign of ignorance).

• Low Uncertainty with Low Accuracy implies the model has collapsed into a systematic error (a sign of bias or hallucination).

Consequently, our metric serves a dual purpose even under these two apparent “failure” scenarios: it enables the automatic rejection of soft failures (i.e., high uncertainty) and facilitates the identification of hard failures (i.e., low uncertainty, systematic errors) that require external intervention, such as prompt refinement or model fine-tuning.

6 Discussion↩︎

6.1 Sensitivity to the Sample Size and the Number of Test Inputs↩︎

6.1.0.1 Sensitivity to the Sample Size.

CODE-MUE relies on sampling multiple candidate programs to approximate the model’s semantic hypothesis space, which is essential for building a consensus-aware semantic graph. Increasing the sampling budget \(N\) can capture a wider range of functional behaviors and thus improve uncertainty quality, but it also increases computational cost (primarily LLM inference). Table 3 reports the sensitivity to \(N \in \{5, 25, 50, 75, 100\}\). As expected, performance improves with larger \(N\) for both correctness alignment (more negative Spearman’s \(\rho\)) and discrimination (higher AUROC). Notably, the improvements exhibit diminishing returns beyond moderate budgets: reducing \(N\) from 100 to 25 only slightly changes \(\rho\) (from \(-0.831\) to \(-0.804\)) and AUROC (from \(0.782\) to \(0.765\)), retaining most of the full-budget effectiveness. Even under strict constraints (\(N=5\)), CODE-MUE still provides a meaningful signal, indicating robustness to reduced sampling in practical deployments.

6.1.0.2 Sensitivity to the Number of Test Inputs.

Our semantic similarity computation executes each sampled program on a probe set \(\mathcal{I}\) of size \(K\) (default \(K=20\)). A larger \(K\) increases the chance of exposing behavioral divergences, but increases execution cost approximately linearly. To quantify this trade-off, we fix \(N=100\) and vary \(K \in \{4,8,12,16,20\}\), with results in Table ¿tbl:tab:probe95budget95sensitivity?. Overall, increasing \(K\) yields more reliable uncertainty signals: both correctness alignment (more negative Spearman’s \(\rho\)) and discrimination (higher AUROC) improve as \(K\) grows. Importantly, even a small probe budget already provides useful signal (e.g., \(K=4\) still achieves \(\rho=-0.682\)), while the marginal gains diminish at higher budgets. This suggests that moderate probe sizes can preserve strong performance while reducing execution overhead.

6.2 Computational Overhead and Deployment Practicality↩︎

Discussing overhead is critical for practical adoption. The total overhead scales with the number of sampled candidates (\(n\), i.e., \(N\)) and the number of synthesized inputs (\(m\), i.e., \(K\)), and can be decoupled into four phases:

• Candidate Generation (\(O(n)\) LLM Inference): Generating multiple candidates is a standard prerequisite for modern LLM decoding and evaluation (e.g., pass@k, self-consistency). We view this as a shared baseline cost rather than a bottleneck unique to CODE-MUE.

• Test Input Synthesis (\(O(m)\) LLM Inference): We only prompt the LLM to generate raw input values (no expected outputs/assertions). This uses few tokens and can be further amortized by asking the model to synthesize multiple diverse inputs in a single call.

• Dynamic Execution (\(O(n \times m)\) CPU Compute): Executing \(n\) programs on \(m\) inputs is the primary overhead. However, execution in a local sandbox relies on cheap, highly parallelizable CPU computation, which is typically far more cost-efficient than GPU-bound LLM inference.

• Uncertainty Quantification (Negligible Compute): Computing the Von Neumann entropy uses lightweight matrix operations on a small distance matrix and typically takes milliseconds.

In practice, the total cost is dominated by the first three phases. We therefore report a quantitative breakdown in Tables ¿tbl:tab:overhead95by95N? and [tbl:tab:overhead95by95K]: we first fix \(K=20\) and vary \(N\), and then fix \(N=100\) and vary \(K\). The results confirm a clear trade-off: larger \(N\) and \(K\) generally improve uncertainty quality, but also increase cost. Importantly, the end-to-end runtime grows much more with \(N\) than with \(K\), as candidate generation (LLM inference) is the dominant contributor, whereas increasing \(K\) mainly affects input synthesis and execution with a relatively modest impact on the total time. This further supports the key practical point that, while the primary overhead scales with \(O(n \times m)\), the most scalable component (dynamic execution) is cheap and highly parallelizable CPU computation rather than expensive LLM inference. Overall, together with Tables 3 and ¿tbl:tab:probe95budget95sensitivity?, we observe that reducing \(N\) and \(K\) can substantially lower cost while preserving strong performance, providing a wide range of viable operating points for deployment; moreover, candidate generation can be accelerated via batching/parallel queries and stronger inference hardware.

6.3 Scalability to Larger Code Scenarios↩︎

While the dynamic execution overhead of CODE-MUE scales with program length, it is designed to align with modern, modular software engineering workflows, where LLMs are typically used at the function, class, or snippet level rather than generating monolithic systems end-to-end. In large codebases, LLM-generated code is naturally modular—comprising functions, classes, or patches—and is often validated in isolation via unit tests. CODE-MUE can therefore be applied at the same granularity by evaluating these isolated modules, making it compatible with repository-scale development. Moreover, both candidate generation and probe execution are embarrassingly parallel, which substantially mitigates the wall-clock overhead in practical deployments. As a concrete repository-level case study, we consider a RepoClassBench [79] task (psf__requests-6028_SESsiON). After sampling 20 candidates with GPT-4.1-nano, we decompose each generated class into method-level modules via AST parsing, and apply CODE-MUE to one representative module (gET_aDAPteR). The procedure yields a low uncertainty score (\(H=0.09\)). Manual inspection further confirms that 18 out of 20 sampled implementations exhibit the correct behavior, which aligns with the intuition that modules with a high fraction of correct implementations tend to receive low uncertainty.

7 Threats to Validity↩︎

Internal Validity. Model configuration and hyperparameter choices can distort output distributions; we mitigate this by enforcing a consistent configuration (e.g., \(T=1.0\)) across all models. Additionally, while Code-MUEavoids oracle-label bias by using inputs strictly to compare execution behavior rather than generate labels, LLM-generated inputs risk coverage bias. If inputs miss critical semantic regions, distinct behavioral modes may merge, underestimating uncertainty. We mitigate this by implementing a hybrid strategy that combines rule-based boundary inputs with LLM-generated nominal inputs; future work can consider integrating stronger fuzzing, symbolic, or domain-specific input generators.

External threats. The selection of subject LLMs presents a potential threat to the generalizability of our findings. To address this, we evaluated a diverse set of eight LLMs, evenly split between closed-source API-based systems (e.g., GPT-4.1, Gemini 2.5) and open-source models (e.g., Llama 3.1, DeepSeek-Coder). Another concern is whether our findings hold across different types of coding tasks. We mitigated this by conducting evaluations on four distinct benchmarks (HumanEval, MBPP, QuixBugs, and CodeNet), covering a broad spectrum of tasks including code completion, synthesis, program repair, and translation.

8 Conclusion↩︎

In this paper, we proposed Code-MUE, a black-box uncertainty quantification framework that grounds LLM confidence in execution-based semantic consensus rather than superficial textual similarity. Extensive evaluations demonstrate that Code-MUE serves as a highly reliable proxy for functional correctness, achieving strong negative correlations (Spearman’s \(\rho\) up to \(-0.98\)). Beyond accurate measurement, we validated the framework’s practical utility in two distinct deployment scenarios: (1) Selective Prediction, where rejecting high-uncertainty samples significantly reduces system error rates; and (2) Unsupervised Response Selection, where our centrality-based re-ranking mechanism identifies correct solutions with high precision without requiring ground-truth test oracles.

Data Availability↩︎

To facilitate reproducibility and support Open Science, we provide the code at https://github.com/hnurxn/Code-Uncertainty.

Acknowledgment↩︎

This work was supported in part by JST CRONOS Grant (No. JPMJCS24K8), JSPS KAKENHI Grant (No.JP24K02920, No.JP26KJ0789), and the project “Theoretical Research on Trustworthy Evaluation of Intelligent Software” (Grant No. E6430219G8).

References↩︎

---

1. To systematically study the effect of Monte Carlo sampling scale, we perform 100 stochastic samples per question, leading to approximately 500,000 inference calls for closed-source APIs under the current setting.↩︎

2. We adapt the original NLI-based formulation by substituting the Natural Language Inference model with a domain-specific code embedding model (CodeBERT) to better capture programming semantics.↩︎