The Path Not Taken: Duality in Reasoning about Program Execution

• URL: http://arxiv.org/abs/2604.20917v1
• Date: Wed, 22 Apr 2026 03:20:53 GMT
• Title: The Path Not Taken: Duality in Reasoning about Program Execution
• Abstract summary: We argue that understanding program execution requires evaluating its inherent duality through two complementary reasoning tasks.<n>We instantiate this duality in DexBench, a benchmark comprising 445 paired instances, and evaluate 13 large language models.
• Score: 6.381430350711558
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Large language models (LLMs) have shown remarkable capabilities across diverse coding tasks. However, their adoption requires a true understanding of program execution rather than relying on surface-level patterns. Existing benchmarks primarily focus on predicting program properties tied to specific inputs (e.g., code coverage, program outputs). As a result, they provide a narrow view of dynamic code reasoning and are prone to data contamination. We argue that understanding program execution requires evaluating its inherent duality through two complementary reasoning tasks: (i) predicting a program's observed behavior for a given input, and (ii) inferring how the input must be mutated toward a specific behavioral objective. Both tasks jointly probe a model's causal understanding of execution flow. We instantiate this duality in DexBench, a benchmark comprising 445 paired instances, and evaluate 13 LLMs. Our results demonstrate that dual-path reasoning provides a robust and discriminative proxy for dynamic code understanding.

Related papers

• Pseudo2CodeQA: A Benchmark for LLM-Based Structured Algorithmic Reasoning in Code Generation [0.5993567221208439]
  Large Language Models (LLMs) have achieved impressive performance in natural language-to-code generation.<n>We introduce Pseudo2Code, a benchmark designed to evaluate the impact of structured pseudocode on code generation quality and algorithmic faithfulness.
  arXiv  Detail & Related papers  (2026-08-10T03:17:08Z)
• ClarifyCodeBench: Evaluating LLMs on Clarifying Ambiguous Requirements for Code Generation [54.788849448970154]
  We introduce ClarifyCodeBench, a novel interactive benchmark for evaluating Large Language Models' capability in resolving requirement ambiguity.<n>We conduct a systematic evaluation of six state-of-the-art LLMs using ClarifyCodeBench.<n>Our empirical results yield three critical insights: 1) Capability Decoupling: Strong code generation performance does not inherently translate to effective requirement clarification; 2) The Reasoning Paradox: While increased computational thinking enhances code correctness, it yields marginal gains in identifying ambiguities.
  arXiv  Detail & Related papers  (2026-07-01T09:58:59Z)
• LLM-Based Static Verification of Code Against Natural-Language Requirements: An Industrial Experience Report [3.5867640049033054]
  This article presents a two-stage LLM-based workflow for addressing this challenge in an intelligent-vehicle cybersecurity case study.<n>In the first stage, an AI-based rule miner extracts verifiable rules from natural-language requirements.<n>In the second stage, an AI-based code auditor checks implementation evidence against the extracted rules.
  arXiv  Detail & Related papers  (2026-05-18T06:34:03Z)
• CoRE: A Fine-Grained Code Reasoning Benchmark Beyond Output Prediction [19.001016903165738]
  It remains unclear whether large language models (LLMs) genuinely reason about code execution.<n>Existing code reasoning benchmarks primarily evaluate final output correctness under a single canonical implementation.<n>We introduce textbfCoRE, a textbfCode textbfReasoning benchmark that evaluates code reasoning.
  arXiv  Detail & Related papers  (2026-04-28T09:11:29Z)
• DuET: Dual Execution for Test Output Prediction with Generated Code and Pseudocode [56.14374797825548]
  We introduce LLM-based pseudocode execution, which grounds prediction on more error-resilient pseudocode.<n>We propose DuET, a dual-execution framework that combines both approaches by functional majority voting.<n>On LiveCodeBench, DuET achieves the state-of-the-art performance, improving Pass@1 by 13.6 pp.
  arXiv  Detail & Related papers  (2026-04-13T14:18:58Z)
• Demystifying Errors in LLM Reasoning Traces: An Empirical Study of Code Execution Simulation [7.377446354867118]
  We conduct the first empirical study on runtime behavior inference with large language models (LLMs)<n>We evaluate four state-of-the-art reasoning LLMs and develop a taxonomy with nine categories of inference errors.<n>Using failures in the Computation category as a case study, our experiments show that this approach corrects 58 percent of such errors.
  arXiv  Detail & Related papers  (2025-11-28T21:29:09Z)
• BRIDGE: Building Representations In Domain Guided Program Verification [67.36686119518441]
  BRIDGE decomposes verification into three interconnected domains: Code, Specifications, and Proofs.<n>We show that this approach substantially improves both accuracy and efficiency beyond standard error feedback methods.
  arXiv  Detail & Related papers  (2025-11-26T06:39:19Z)
• Adaptive Test-Time Reasoning via Reward-Guided Dual-Phase Search [62.1546099504045]
  We propose a dual-phase test-time scaling framework that separates reasoning into planning and execution.<n>Specifically, we decompose reasoning trajectories and develop reward models for each phase, enabling the search to explore and prune plans and executions separately.<n> Experiments on both mathematical reasoning and code generation benchmarks demonstrate that our approach consistently improves accuracy while reducing computation redundant.
  arXiv  Detail & Related papers  (2025-09-29T19:27:23Z)
• EquiBench: Benchmarking Large Language Models' Reasoning about Program Semantics via Equivalence Checking [58.15568681219339]
  We introduce EquiBench, a new benchmark for evaluating large language models (LLMs)<n>This task directly tests a model's ability to reason about program semantics.<n>We evaluate 19 state-of-the-art LLMs and find that in the most challenging categories, the best accuracies are 63.8% and 76.2%, only modestly above the 50% random baseline.
  arXiv  Detail & Related papers  (2025-02-18T02:54:25Z)
• Evaluating Generative Language Models in Information Extraction as Subjective Question Correction [49.729908337372436]
  We propose a new evaluation method, SQC-Score. Inspired by the principles in subjective question correction, we propose a new evaluation method, SQC-Score. Results on three information extraction tasks show that SQC-Score is more preferred by human annotators than the baseline metrics.
  arXiv  Detail & Related papers  (2024-04-04T15:36:53Z)
• CodeMind: Evaluating Large Language Models for Code Reasoning [6.819757372634151]
  Large Language Models (LLMs) have been widely used to automate programming tasks.<n>This paper introduces CodeMind, a framework designed to gauge the code reasoning abilities of LLMs.
  arXiv  Detail & Related papers  (2024-02-15T02:24:46Z)
• Enforcing Consistency in Weakly Supervised Semantic Parsing [68.2211621631765]
  We explore the use of consistency between the output programs for related inputs to reduce the impact of spurious programs. We find that a more consistent formalism leads to improved model performance even without consistency-based training.
  arXiv  Detail & Related papers  (2021-07-13T03:48:04Z)

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.