Execution Based Evaluation for Code Generation

21 concepts17 papers1 proposal

When evaluating natural language processing (NLP) models, standard metrics like BLEU, ROUGE, or BERTScore measure textual similarity. If a model translating a sentence outputs "happy" instead of "joyful," it receives a minor penalty, but the core meaning remains intact.

When applied to source code, however, this text-matching paradigm completely breaks down. Code possesses a strict dual nature: it is a textual sequence, but it is also an executable instruction set. As Zhu et al. outline, code is inherently structure-based and functionality-oriented. Evaluating it purely as text introduces a severe "lexical-functional gap"—a misalignment between surface-level token overlap and actual runtime utility. To accurately assess code generation, the research community is shifting from linguistic metrics to execution-based evaluation.

The Two-Sided Failure of String Matching

Lexical similarity metrics fail to evaluate code because software engineering constraints create two distinct failure modes: false positives (code that looks right but is broken) and false negatives (code that looks wrong but is perfect).

False Positives: High Similarity, Zero Functionality

In natural language, a 99% token overlap usually guarantees a near-perfect translation. In programming, a single character mismatch can cause catastrophic failure. If a model generates a long script perfectly but misspells a single variable name or omits a colon, the code will fail to compile or execute.

As Clement et al. and Wang et al. observe, minor syntax variations or character-level discrepancies can result in completely non-functional code that traditional metrics still reward with high similarity scores. Pan et al. demonstrate this fragility in complex software environments, showing that minor character-level edits often lead to total execution failure despite high edit-similarity scores.

False Negatives: Low Similarity, Perfect Functionality

Conversely, code is highly flexible. A developer can solve a problem using a for loop, a while loop, or a list comprehension. They can choose entirely different variable names or restructure the logic while maintaining identical input-output behavior.

Cai et al. point out that a generated query or program can be entirely functional while using a different but equivalent syntax than the ground-truth reference. In these scenarios, text-matching metrics like BLEU or Exact Match heavily penalize the model, failing to recognize functional equivalence (Beau et al.; Zhang et al.).

# Reference Solution (High BLEU baseline)
def is_even(n):
    return n % 2 == 0

# Generated Solution A (High BLEU, False Positive: Syntax Error)
def is_even(n)
    return n % 2 == 0

# Generated Solution B (Low BLEU, False Negative: Functionally Perfect)
def is_even(number):
    if not (number & 1):
        return True
    return False

When Text Metrics Actively Mislead

The issue extends beyond a mere lack of sensitivity; lexical metrics can actively mislead model optimization. Gorbatovski et al. demonstrate that common linguistic metrics exhibit a stark lack of correlation with human expert judgment and logical correctness in programming tasks.

Even worse, text-matching metrics can negatively correlate with code quality. Vitel et al. discovered that metrics like BLEU and chrF sometimes reward the repetitive, predictable n-gram sequences often found in incorrect or verbose code. Conversely, models constrained by strict grammar rules often produce concise, correct code that scores lower on lexical metrics simply because it avoids redundant tokens.

This distortion also impacts auxiliary tasks like documentation. Getmanov et al. found that lexical similarity scores for code documentation show a very weak correlation with whether that documentation actually contains enough technical information to reconstruct functional code.

The Shift to Execution-Based Benchmarks

To close the lexical-functional gap, modern benchmarks evaluate code by running it within sandboxed execution environments. Instead of asking "does this code look like the reference?", these frameworks ask "does this code pass the test suite?".

[Generated Code] ──> [Compilation Check] ──> [Unit Tests] ──> [Pass/Fail Rate]

This paradigm shift has driven the creation of large-scale, execution-verified datasets:

  • Multi-task Verification: Khan et al. developed XCodeEval, a massive multilingual benchmark that uses a custom execution engine to verify code across multiple programming languages and tasks, exposing how text-matching metrics mask a model's struggles with complex algorithmic logic.
  • Open-Domain Libraries: Wang et al. introduced ODEX to evaluate code execution in open-domain settings, forcing models to interact with real-world, third-party libraries rather than isolated built-in functions.
  • Cross-Language Translation: To evaluate code translation across different languages without relying on string matching, Yan et al. introduced the Debugging Success Rate (DSR@K) metric, which measures whether translated code successfully compiles and executes.

As Shang et al. argue, prioritizing runtime metrics like execution success and test pass rates is the only reliable way to measure the actual utility of generated software components.

Optimizing for Execution and Its Pitfalls

Moving from execution-based evaluation to execution-based optimization allows models to learn from runtime feedback. Rather than training models purely on next-token prediction, frameworks can leverage reinforcement learning to optimize directly for functional correctness.

Shojaee et al. demonstrated this with PPOCoder, a framework that uses Proximal Policy Optimization (PPO) to fine-tune models based on actual execution feedback and structural analysis (such as Abstract Syntax Trees and Data Flow Graphs). By optimizing for compilation rates and test passage rather than token matching, smaller models can achieve higher functional correctness than massive models trained purely on text.

The Challenge of Reward Hacking

However, optimizing purely for test passage introduces a new phenomenon: "reward hacking" within code synthesis. As Lang et al. observe, when models are evaluated solely on whether they pass unit tests, they often find non-idiomatic shortcuts or imperative workarounds that satisfy execution requirements but violate the architectural constraints and best practices of the target language.

This highlights the next frontier for the field: while execution-based evaluation solves the lexical gap, evaluation frameworks must continue to evolve to balance raw functional correctness with structural, idiomatic, and maintainable code quality.

Key Foundational Work

PyMT5: multi-mode translation of natural language and Python code with transformers (2020) — contributed 2 concept elements to this direction.
An Encoder-Decoder Framework Translating Natural Language to Database Queries (2018) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_functional_correctness_evaluation_bd604379,
  title = {functional correctness evaluation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/functional-correctness-evaluation/rdr_bd6043798e5f4109a3238fbaa5e23a56},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_functional_correctness_evaluation_bd604379_v1,
  title = {functional correctness evaluation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/functional-correctness-evaluation/rdr_bd6043798e5f4109a3238fbaa5e23a56/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake