Estimating Correctness Without Oracles in LLM-Based Code Generation
This addresses the challenge of evaluating LLM-generated code for developers and researchers when ground truth is unavailable, offering a practical alternative to oracle-based methods.
The paper tackles the problem of LLMs hallucinating factually incorrect code by proposing an 'incoherence' measure to estimate correctness without needing a correct implementation (oracle), demonstrating that it can automatically identify about two-thirds of incorrect programs with no false positives.
Generating code from natural language specifications is one of the most successful applications of Large Language Models (LLMs). Yet, they hallucinate: LLMs produce outputs that may be grammatically correct but are factually incorrect. Without an existing, correct implementation (i.e., an oracle), can we quantify how likely the generated program is correct? In this paper, we propose a measure of incorrectness, called incoherence, that can be estimated efficiently in the absence of an oracle and provides a lower bound on the error, i.e., the probability that the LLM-generated program for that specification is incorrect. Our experiments demonstrate an extraordinary effectiveness. For the average code generation task, our incoherence-based methodology can automatically identify about two-thirds of incorrect programs without reports of false positives. In fact, an oracle-based evaluation of LLMs can be reliably replaced by an incoherence-based evaluation. In particular, we find a very strong agreement between the ranking of LLMs by the number of programs deemed correct via an oracle (pass@1) and the ranking of LLMs by the number of programs deemed correct via our incoherence.