Code-MUE: Measuring Code LLMs’ Uncertainty through Execution-based Semantic Interaction Graphs

As code LLMs become integral to software engineering, their inherent stochasticity poses significant risks. Traditional uncertainty metrics, such as token-level entropy or embedding-based similarity, often fail to capture the unique fragility of code, where minor syntactic changes can lead to major functional divergence. This paper asks: how can we reliably measure the uncertainty of black-box code LLMs without relying on internal model states or superficial textual metrics?

To bridge the gap between syntax and semantics, the authors introduce Code-MUE, a framework that treats code as an executable artifact rather than mere text. The process involves three main steps:

1. Monte Carlo Sampling: The model generates multiple candidate programs for a given prompt.
2. Execution-based Interaction: These programs are executed against a test suite to observe their runtime behavior.
3. Semantic Interaction Graph: The samples are organized into a graph where nodes represent programs and edges represent functional consensus. The authors then calculate the Von Neumann entropy of this graph to quantify the global semantic diversity of the solution space.

The authors evaluated Code-MUE across eight state-of-the-art LLMs on four software engineering tasks: code completion, program synthesis, program repair, and code translation. The study demonstrates that Code-MUE significantly outperforms traditional lexical and embedding-based baselines, showing a strong negative correlation with functional correctness (Spearman’s correlation up to -0.98). Furthermore, the framework proves effective for risk detection and selective prediction, achieving AUROC scores exceeding 0.85, which allows systems to reliably abstain from using low-confidence code generations.