Predicting Program Correctness By Ensemble Semantic Entropy

1. Problem Statement

Large Language Models (LLMs) have demonstrated significant capabilities in code generation, yet ensuring the functional correctness of generated programs without external oracles (like comprehensive test suites) remains a critical challenge.

• The Limitation of Current Methods: Existing approaches rely on uncertainty estimation based on a single model. They measure the consistency of semantics or execution behaviors across multiple samples generated by that single model.
• The Core Issue: A single model can exhibit overconfidence, converging to a consistent but incorrect solution (e.g., generating multiple syntactically diverse programs that all share the same logical error). In such cases, single-model uncertainty metrics (like Semantic Entropy) yield low uncertainty scores, falsely indicating high confidence in a wrong answer (False Positives).
• Goal: Develop a method to predict program correctness that can distinguish between "confident correctness" and "confident error" without relying on external ground-truth test cases during the prediction phase.

2. Methodology: Ensemble Semantic Entropy (ESE)

The authors propose Ensemble Semantic Entropy (ESE), a novel uncertainty estimation framework that aggregates samples from multiple diverse models to capture both within-model dispersion and cross-model disagreement.

Key Concepts

• Semantic Clustering: Instead of clustering raw tokens, programs are mapped to semantic clusters based on functional equivalence. Two programs belong to the same cluster if they produce identical outputs on a set of generated test inputs ($T_{gen}$).
• Decomposition of Uncertainty: The paper frames uncertainty using Bayesian decomposition:
  • Aleatoric Uncertainty: Variance within a single model's samples.
  • Epistemic Uncertainty: Variance arising from model parameters (different models).
  • Insight: Single-model Semantic Entropy (SE) only captures Aleatoric uncertainty. If a model is consistently wrong, SE is low. ESE captures the Epistemic component by measuring disagreement between different models.

The ESE Algorithm

1. Ensemble Sampling: Sample $K$ programs from $L$ different LLMs (e.g., 3 from Model A, 3 from Model B).
2. Execution & Clustering: Execute all $L \times K$ programs on a generated test suite. Group them into semantic clusters based on their output vectors.
3. Probability Aggregation: Calculate the probability of each semantic cluster by averaging the frequencies across all models in the ensemble.
4. Entropy Calculation: Compute the Shannon entropy of this aggregated distribution.
   • Formula: $H_{ESE}(x) = -\sum p(s|x, \mathcal{M}) \log p(s|x, \mathcal{M})$
   • Interpretation: If different models converge on the same incorrect behavior, the entropy remains low. However, if models produce different incorrect behaviors (or if some are correct and others wrong), the entropy increases, correctly flagging the uncertainty.

Black-Box Variant (EDSE)

For closed-source models where token-level probabilities are unavailable, the authors propose Ensemble Discrete Semantic Entropy (EDSE), which estimates the semantic distribution using empirical frequencies of sampled outputs.

3. Key Contributions

1. Proposal of ESE: A new uncertainty metric that aggregates diverse models to detect "confident errors" that single-model metrics miss.
2. Theoretical Insight: Demonstrated that single-model consistency is a poor proxy for correctness due to overconfidence, whereas cross-model disagreement provides a robust signal for functional incorrectness.
3. Cascading Test-Time Scaling (Cas): A framework leveraging ESE as a decision signal to dynamically allocate computational resources.
   • Mechanism: Start with a lightweight ensemble of smaller models. If ESE indicates low uncertainty (high confidence), accept the solution. If uncertainty is high, escalate to a larger, more expensive model.
   • Selection: Uses majority voting within the dominant semantic cluster of the accepted layer.

4. Experimental Results

Experiments were conducted on LiveCodeBench, a rigorous benchmark of competitive programming problems.

RQ1: Correlation with Correctness

• Finding: ESE and EDSE show a significantly stronger negative correlation with program correctness compared to single-model metrics (SE, DSE, Predictive Entropy).
• Data: For cross-family ensembles (e.g., Qwen3-8B + GLM4-9B), the correlation improved from -0.67 (single model) to -0.74 (ensemble).
• Implication: Ensemble disagreement effectively captures the risk of functional failure better than single-model self-consistency.

RQ2: Clustering Methods

• Finding: Functional clustering (based on execution outputs) yields the strongest correlation with correctness.
• Comparison: Methods relying on NLI, embeddings, or BLEU scores were significantly weaker, as they fail to capture subtle functional differences that execution traces reveal.

RQ3: Selective Generation (Abstention)

• Task: The model must decide to accept or reject a generated answer based on uncertainty, strictly limiting the False Positive Rate (FPR).
• Result: Under a strict 5% FPR constraint, ESE improved prediction accuracy by 53.4% compared to single-model baselines. It successfully rejected "confidently wrong" answers that single models accepted.

Application: Cas Framework (Test-Time Scaling)

• Setup: A 2-layer cascade. Layer 1 uses a small ensemble (Qwen3-8B + Qwen3-Coder-30B). Layer 2 uses a large model (Qwen3-Coder-485B or gpt-oss-20B).
• Performance:
  • Accuracy: Cas achieved near-optimal pass rates (e.g., 86.11% vs. 87.67% for the best single-model baseline).
  • Efficiency: Cas reduced computational cost (FLOPs) by 64.9% compared to standard Best-of-$N$ scaling on the large model.
  • Ablation: Removing the ensemble from Layer 1 caused a significant drop in Pass@Exit, proving that the ensemble signal is crucial for avoiding premature acceptance of errors.

5. Significance

• Reliability: ESE addresses a fundamental flaw in current LLM code generation evaluation: the inability to detect overconfident hallucinations. It provides a more reliable "oracle-free" correctness predictor.
• Efficiency: The Cas framework offers a new paradigm for balancing parameter scaling (model size) and inference scaling (compute budget). It proves that using diverse, smaller models to filter easy problems can drastically reduce costs without sacrificing performance.
• Generalizability: The approach is model-agnostic (works with open and closed models) and relies on functional behavior, making it applicable to various code generation tasks beyond competitive programming.

In summary, this paper establishes that diversity in model ensembles is a critical, previously underutilized signal for uncertainty estimation in code generation, enabling both more accurate correctness prediction and more efficient test-time scaling.