Assessing Coherency and Consistency of Code Execution Reasoning by Large Language Models

1. Problem Statement

While Large Language Models (LLMs) have demonstrated impressive capabilities in code generation, completion, and bug repair, their ability to reason about code execution remains under-investigated. Existing evaluation methods (e.g., CruxEval, CodeMind, REval) suffer from critical limitations:

• Lack of Coherency Checks: They often focus solely on input/output prediction or isolated statement predictions without verifying if the intermediate reasoning steps are logically consistent with the program's execution flow. This allows models to produce "suspiciously correct" outputs via hallucinations, data leakage, or natural language shortcuts (guessing the answer based on function names) despite incorrect internal reasoning.
• Lack of Consistency Metrics: Prior works evaluate reasoning on a per-test basis, failing to assess whether a model can consistently simulate different execution paths (prime paths) of the same program.
• Fragmented Evaluation: Methods like REval prompt models separately for different statements, making it difficult to track the propagation of errors or determine the exact point where reasoning diverges from ground truth.

2. Methodology: Code Execution Simulation (CES)

The authors propose CES, a novel task and framework designed to evaluate LLMs' ability to simulate program execution flow-sensitively.

Core Mechanism

CES unifies output prediction and intermediate state prediction into a single prompt. Instead of asking for the final answer only, CES requires the LLM to predict essential decision points throughout the execution:

1. Looping Properties: Loop variables and loop iterables (e.g., values in a zip or range).
2. Branching Properties: Conditional predicates (sub-predicates and the whole predicate) and the resulting branch taken.
3. Return Properties: The final output or return values.

The framework uses static analysis to annotate code with placeholders for these properties and employs adaptive in-context learning (selecting examples based on the program's structure) to guide the model.

Key Concepts

• Reasoning Coherency: CES defines three rules to determine if a simulation is "coherent" (logically consistent with itself), regardless of whether the final answer is correct:
  1. Rule 1 (Composition): Sub-property predictions must logically combine to match the compound property prediction (e.g., if a and b are predicted, a+b must match).
  2. Rule 2 (Logic): Conditional predicate predictions must be consistent with the predicted branch taken.
  3. Rule 3 (Suspicious Correctness): If the final output is correct but any intermediate state prediction is incorrect, the reasoning is marked as incoherent. This flags "lucky" guesses or data leakage.
• Reasoning Consistency: CES introduces a spectrum to measure consistency across multiple test cases for the same program:
  • Strong Consistency: The model correctly simulates execution across tests with different prime path coverages.
  • Weak Consistency: The model is consistent only across tests with the same prime path coverage but fails on different paths.
  • Random: The model shows no consistent pattern.

Diagnostic Capabilities

CES automatically identifies the Simulation Divergence Point—the exact statement where the model's reasoning first deviates from the ground truth. This allows for granular analysis of why a model fails (e.g., mispredicting a loop iterable vs. a conditional predicate).

3. Key Contributions

1. CES Framework: A flow-sensitive, scalable, and diagnostic task that evaluates code reasoning by unifying state and output prediction.
2. Coherency & Consistency Metrics: Novel definitions and metrics to detect "suspiciously correct" outputs (hallucinations/shortcuts) and measure the robustness of reasoning across different execution paths.
3. Systematic Vetting of Bug Tasks: A method to cross-reference code reasoning with bug prediction, localization, and repair tasks, revealing whether success in these tasks is due to genuine execution reasoning or pattern matching.
4. Comprehensive Empirical Evaluation: Evaluation of 16 LLMs (including frontier models like GPT-4, DeepSeek-R1, and reasoning models like o4-mini) on the HumanEval benchmark.

4. Results

The evaluation of 16 LLMs on 164 HumanEval programs (with 3 tests per program) yielded the following findings:

• Coherency vs. Correctness:

  • On average, 81.42% of simulations were coherent (logically consistent).
  • However, only 46.92% of these coherent simulations resulted in correct output predictions.
  • 53.08% of coherent simulations resulted in incorrect outputs, indicating that even when models reason logically, they often get the logic wrong.
  • Incoherent Reasoning: Frontier models like GPT-4 and DeepSeek-R1 exhibited high rates of incoherent reasoning (approx. 25% of cases), often due to natural language shortcuts overriding code logic.

• Reasoning Consistency:

  • LLMs struggle significantly with consistency across different execution paths.
  • 48.87% of reasoning was Random.
  • 45.37% was Weak (consistent only on same paths).
  • Only 5.76% achieved Strong Consistency (correctly simulating different paths). This explains their failure in path-sensitive program analysis tasks.

• Root Causes of Failure:

  • Loops: The most common divergence point is mispredicting loop iterables (e.g., zip or range values).
  • Conditionals: Models often fail to correctly evaluate compound predicates.
  • Suspicious Success: CES detected 361 cases of "suspiciously correct" outputs. Analysis revealed these were often due to:
    • Natural Language Shortcuts: Guessing the answer based on function names (e.g., assuming string_xor performs XOR without simulating the loop).
    • Hallucinations: Correctly predicting the output despite incorrect intermediate states (often seen in boolean return types).

• Bug-Related Tasks (Prediction, Localization, Repair):

  • There is a significant overlap between bug task success and CES success for top models, but the overlap is minimal for weaker models.
  • Crucial Finding: Even when LLMs successfully predict, localize, or repair bugs, they rarely incorporate actual execution reasoning into their Chain-of-Thought (CoT).
  • In many "successful" bug repair cases, the model's CES simulation diverged before the bug location, yet the model still "fixed" the bug. This suggests success is driven by pattern matching or memorization rather than understanding the execution flow.

5. Significance and Implications

• Redefining "Success": The paper argues that high accuracy on benchmarks like HumanEval is often inflated by "suspiciously correct" predictions. CES provides a mechanism to filter these out, offering a more realistic view of an LLM's reasoning capabilities.
• Trustworthiness: By identifying reasoning shortcuts and hallucinations, CES helps build more trustworthy Code LLMs. It highlights that current models often rely on statistical patterns rather than true program analysis.
• Future Directions: The findings suggest that simply scaling models or using natural language instructions is insufficient for robust code reasoning. Future training strategies must explicitly focus on execution-aware fine-tuning and path-sensitive reasoning to improve generalization to unseen code and complex debugging scenarios.
• Tooling: CES is the first tool to systematically connect code reasoning with other programming tasks (bug fixing), providing a diagnostic lens to understand how LLMs succeed or fail.

In conclusion, while LLMs can simulate code execution to a degree, their reasoning is frequently incoherent (logically flawed) or inconsistent (unreliable across paths). The paper calls for a paradigm shift in evaluation to prioritize coherency and consistency over simple output accuracy.