Estimating Correctness Without Oracles in LLM-Based Code Generation

• URL: http://arxiv.org/abs/2507.00057v1
• Date: Thu, 26 Jun 2025 22:00:50 GMT
• Title: Estimating Correctness Without Oracles in LLM-Based Code Generation
• Authors: Thomas Valentin, Ardi Madadi, Gaetano Sapia, Marcel Böhme,
• Abstract summary: We propose a measure of incorrectness, called incoherence, that can be estimated efficiently in the absence of an oracle.<n>For the average code generation task, our incoherence-based methodology can automatically identify about two-thirds of incorrect programs.
• Score: 10.204622104311014
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• On the Effectiveness of LLM-as-a-judge for Code Generation and Summarization [54.965787768076254]
  Large Language Models have been recently exploited as judges for complex natural language processing tasks, such as Q&A.<n>We study the effectiveness of LLMs-as-a-judge for two code-related tasks, namely code generation and code summarization.
  arXiv  Detail & Related papers  (2025-07-22T13:40:26Z)
• RAC: Efficient LLM Factuality Correction with Retrieval Augmentation [8.207682890286957]
  Large Language Models (LLMs) exhibit impressive results across a wide range of natural language processing (NLP) tasks, yet they can often produce factually incorrect outputs. This paper introduces a simple but effective low-latency post-correction method, textbfRetrieval Augmented Correction (RAC), aimed at enhancing the factual performance of LLMs without requiring additional fine-tuning.
  arXiv  Detail & Related papers  (2024-10-21T06:11:38Z)
• Showing LLM-Generated Code Selectively Based on Confidence of LLMs [44.23673533981599]
  Large Language Models (LLMs) have shown impressive abilities in code generation, but they may generate erroneous programs. Showing these erroneous programs to developers will waste developers' energies and introduce security risks. We propose HonestCoder, a novel LLM-based code generation approach.
  arXiv  Detail & Related papers  (2024-10-04T08:51:31Z)
• AIME: AI System Optimization via Multiple LLM Evaluators [79.03422337674664]
  AIME is an evaluation protocol that utilizes multiple LLMs that each independently generate an evaluation on separate criteria and then combine them via concatenation. We show AIME outperforming baseline methods in code generation tasks, with up to $62%$ higher error detection rate and up to $16%$ higher success rate than a single LLM evaluation protocol on LeetCodeHard and HumanEval datasets.
  arXiv  Detail & Related papers  (2024-10-04T04:03:24Z)
• AI-Oracle Machines for Intelligent Computing [2.6839986755082728]
  We introduce the concept of AI-oracle machines for intelligent computing and outline several applications to demonstrate their potential. We advocate for the development of a comprehensive platform to streamline the implementation of AI-oracle machines.
  arXiv  Detail & Related papers  (2024-06-18T02:25:33Z)
• Reasoning Runtime Behavior of a Program with LLM: How Far Are We? [25.451857140926943]
  Large language models for code (i.e., code LLMs) have shown strong code understanding and generation capabilities. Code reasoning is one of the most essential abilities of code LLMs. We propose a framework, namely REval, for evaluating code reasoning abilities and consistency of code LLMs with program execution.
  arXiv  Detail & Related papers  (2024-03-25T05:37:16Z)
• Assured LLM-Based Software Engineering [51.003878077888686]
  This paper is an outline of the content of the keynote by Mark Harman at the International Workshop on Interpretability, Robustness, and Benchmarking in Neural Software Engineering, Monday 15th April 2024, Lisbon, Portugal.
  arXiv  Detail & Related papers  (2024-02-06T20:38:46Z)
• Learning From Mistakes Makes LLM Better Reasoner [106.48571828587728]
  Large language models (LLMs) recently exhibited remarkable reasoning capabilities on solving math problems. This work explores whether LLMs can LEarn from MistAkes (LEMA), akin to the human learning process.
  arXiv  Detail & Related papers  (2023-10-31T17:52:22Z)
• ALGO: Synthesizing Algorithmic Programs with LLM-Generated Oracle Verifiers [60.6418431624873]
  Large language models (LLMs) excel at implementing code from functionality descriptions but struggle with algorithmic problems. We propose ALGO, a framework that synthesizes Algorithmic programs with LLM-Generated Oracles to guide the generation and verify their correctness. Experiments show that when equipped with ALGO, we achieve an 8x better one-submission pass rate over the Codex model and a 2.6x better one-submission pass rate over CodeT.
  arXiv  Detail & Related papers  (2023-05-24T00:10:15Z)
• LEVER: Learning to Verify Language-to-Code Generation with Execution [64.36459105535]
  We propose LEVER, a simple approach to improve language-to-code generation by learning to verify the generated programs with their execution results. Specifically, we train verifiers to determine whether a program sampled from the LLMs is correct or not based on the natural language input, the program itself and its execution results. LEVER consistently improves over the base code LLMs(4.6% to 10.9% with code-davinci) and achieves new state-of-the-art results on all of them.
  arXiv  Detail & Related papers  (2023-02-16T18:23:22Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.