PaperlayerView exact revision on arXiv

Source-linked AI summary

Can Large Language Models Reason About Complex Execution Paths? An Empirical Study on Python

Wenhan Wang, Kaibo Liu, Zeyu Sun, An Ran Chen, Ge Li, Gang Huang, Lei Ma

arXiv:2511.18288v2cs.SE

TL;DR

Symbolic execution struggles with complex constraints and external APIs, and Python lacks mature path-reasoning tools. This study evaluates LLMs on path generation and classification, finding correct complex-path reasoning and improved real-world test coverage, with important limitations.

  • Problem

    SMT-based symbolic execution struggles with complex data structures and external APIs, while Python’s flexible syntax and dynamic typing limit mature path-reasoning tools.

    Source: §1 · p. 2

  • Method

    The study evaluates LLMs and reasoning models on Python execution-path test generation and classification using benchmarks from competition programs and real-world repositories.

    Source: §1 · pp. 2–3

  • Results

    LLMs generated correct inputs for more than 65% of challenging paths and improved real-world test coverage, although reasoning models sometimes made erroneous predictions.

    Source: §1 · p. 3

  • Takeaways & Limitations

    LLMs show potential as a complementary heuristic for path-aware reasoning, especially in languages lacking mature symbolic-execution tools.

    Source: §1 · p. 3

    The study does not directly compare against traditional symbolic-execution tools, which cannot support the evaluated solve-a-given-path tasks in Python.

    Source: §6 · p. 23

Abstract

from arXiv · show

Execution path reasoning is a key step towards program semantics understanding. It is crucial for generating test cases that cover certain branches/paths, or detecting bugs that are triggered by some paths without actually executing the program. Traditionally, execution path reasoning can be achieved by symbolic execution techniques, but existing SMT-based symbolic execution approaches struggle with complex data structures and external API calls. This challenge is even more pronounced in languages with highly flexible syntax, such as Python, resulting in a lack of widely adopted tools for reasoning on execution paths. Therefore, reasoning execution paths with AI-based approaches become a promising direction. In this paper, we investigate the feasibility of adopting large language models (LLMs) for execution path reasoning on Python, where traditional path-based symbolic execution tools are unavailable. We conduct an empirical study on two types of path reasoning tasks: generation tasks for test case generation and classification tasks for bug detection. We build new evaluation pipelines and benchmarks from both competition-level programs and real-world repositories. Our results show that state-of-the-art LLMs can perform correct reasoning on execution paths and improve test coverage on real-world software, though models with stronger reasoning abilities do not always outperform weaker ones. These findings highlight the potential of utilizing LLMs as a complementary heuristic for path-aware code reasoning, especially in program languages lacking mature symbolic execution tools. We have released our benchmark and evaluation scripts at https://github.com/jacobwwh/llm-path-study.

1 Introduction

The study evaluates LLMs on Python execution-path reasoning, addressing challenges that limit symbolic execution and assessing test generation and path classification. It finds that state-of-the-art LLMs can reason about complex paths, but stronger reasoning does not guarantee better predictions.

1 Introduction

  • Symbolic execution struggles to encode complex data structures and handle external APIs, leaving execution-path reasoning difficult in many languages and application scenarios.It typically explores paths with symbolic inputs, gathers path constraints, and uses an SMT solver to test satisfiability.Source: §1 · p. 2
  • Python is the study target because its flexible grammar and dynamic typing limit mature analysis tools, while recognized symbolic-execution support is lacking.The cited Python tools are deprecated or maintained only by independent developers.Source: §1 · p. 2
  • The study evaluates test-case generation for specified paths and path classification for feasibility or bug-triggering behavior across competition programs and real-world repositories.Classification includes valid, infeasible, and bug-triggering paths; the real-world task asks whether path-guided generation improves test coverage.Source: §1 · pp. 2–3
  • State-of-the-art LLMs generated correct test inputs for more than 65% of challenging execution paths, while LRMs could still make erroneous predictions.The study also reports improved test coverage in real-world repositories, though test pass rate remains a bottleneck.Source: §1 · p. 3
  • The paper presents a systematic study of LLM path reasoning and benchmarks spanning test generation, path feasibility, and bug detection.It analyzes both non-reasoning LLMs and large reasoning models.Source: §1 · pp. 2–3

2 Background and Related Work

Prior work explores LLMs for code-execution reasoning and symbolic-execution-related tasks. This study focuses on whether LLMs can directly reason about complex paths without relying on existing symbolic-execution tools.

2.1 Large Language Models for Program Execution Reasoning

  • Program-execution reasoning research includes benchmarks for input, output, coverage, and state prediction, plus methods using execution traces or external memory.Examples include CRUXEval [13], REval [5], NEXT [28], SemCoder [10], and the dynamic scratchpad mechanism [1].Source: §2.1 · p. 4

2.2 LLM-integrated Symbolic Execution

  • LLM-integrated symbolic-execution work includes solving path constraints, generating tests, and augmenting existing concolic or symbolic executors.These approaches include Symprompt, LLM-Sym [41], AutoBug [24], PALM [44], Cottontail [38], NexusSym, WARP [21], and SESpec [48].Source: §2.2 · p. 4
  • The study targets direct LLM reasoning on complex execution paths, unlike prior work focused on simpler paths, other tasks, or extending symbolic-execution tools.Its evaluation spans multiple tasks and fields, including complex control flow and real-world repositories.Source: §2.2 · p. 4

3 Methodology

The evaluation framework centers on test-case generation and path classification. It uses competition problems for controlled complex-path assessment and a repository-level benchmark for real-world test generation.

3 Methodology

  • The evaluation framework comprises test-case generation and path classification.Figure 1 is described as an overview of the empirical study.Source: §3 · p. 4, Figure 1 · p. 5
  • Competition-problem benchmarks provide a controlled setting for evaluating LLM performance on complex execution paths.The passages identify competition problems as a source for constructing benchmarks and extracting path constraints.Source: §3 · p. 5
  • A repository-level test-case generation benchmark evaluates LLMs’ handling of execution-path constraints in real-world software.The study uses it to examine path reasoning beyond standalone programs without external dependencies.Source: §3 · p. 5

3.1 Test Case Generation (competition-level)

The competition-level task asks an LLM to generate a test case that reproduces a specified execution path. The benchmark uses complete traced paths from complex TestEval programs and evaluates generated cases by replaying them against ground truth.

3.1 Test Case Generation (competition-level)

  • Given a program and a sequence of code blocks with branch outcomes, the task is to generate a test case that reproduces that execution path.Each path is represented as pairs of code blocks and the branch conditions taken at their ends.Source: §3.1.1 · p. 5

3.1.1 Benchmark Construction.

  • The customized trace records branch outcomes and annotates for-loop iterations so the path representation retains information needed to reason about execution.Branch outcome is inferred from the next executed statement; loop annotations record iteration numbers starting at 1.Source: §3.1.1 · pp. 5–6
  • TestEval contributes 210 complex Python programs, and the constructed dataset contains 509 paths averaging 233 statements and 103 branch statements.Paths come from example tests, are limited to 1,000 statements, and the source programs average cyclomatic complexity 13.35.Source: §3.1.1 · pp. 5–6

3.1.2 Evaluation Pipeline.

  • Generated outputs are reformatted when needed, executed on the program, and compared with the ground-truth path recorded by the customized trace module.A rule-based processor extracts variable values, with a lightweight LLM fallback when extraction fails or leaves arguments unresolved.Source: §3.1.2 · p. 6
  • Path accuracy requires an exact path match, while node accuracy measures shared-prefix progress at statement and basic-block granularities.The two node-accuracy levels treat a node as either a statement or a block ending in a branch or program termination.Source: §3.1.2 · p. 6

3.2 Path Classification

The path-classification benchmark uses CFG traversal to produce feasible and infeasible paths, then evaluates LLMs on path labels and bug detection. Its dataset combines automatically extracted and manually added paths, which are annotated as Valid, Invalid, or ZeroDivision.

3.2.1 Benchmark Construction.

  • CFG traversal uses depth-first search and records branch conditions and loop iterations, stopping at coverage or preset path limits.The limits are 50 paths, 100 basic blocks per path, and two loop iterations.Source: §3.2.1 · pp. 7–8
  • Paths are manually labeled Valid, Invalid, or ZeroDivision; two annotators resolved disagreements, with Cohen’s Kappa of 0.82.Valid paths do not trigger division by zero, Invalid paths are infeasible, and ZeroDivision paths reach a possible division-by-zero bug.Source: §3.2.1 · p. 8
  • The dataset contains 2,010 execution paths from 120 programs, with only 79 paths manually generated.Programs without control-flow branches were pruned; the authors report that manual additions do not significantly bias the distribution of path types.Source: §3.2.1 · pp. 7, 9
  • LLMs predict one of the three path labels, and a program is counted as buggy if any path is classified ZeroDivision.Evaluation reports accuracy, balanced accuracy, and per-class and macro precision, recall, and F1.Source: §3.2.1 · p. 8, §3.2.2 · p. 9

3.3 Test Case Generation (real-world)

The real-world task evaluates whether execution-path context helps LLMs generate tests for partially covered functions in Python repositories. The pipeline compares path-guided test completion with gold tests and a prompt that omits paths.

3.3 Test Case Generation (real-world)

  • CrossHair requires explicit input type annotations, while PyExSMT struggles with external calls, classes, exceptions, and complex structures common in repositories.These limitations make the cited symbolic-execution tools unsuitable for aspects of real-world repository testing described here.Source: §3.3.1 · p. 9

3.3.1 Benchmark Construction.

  • The study uses TestGenEval, built from 11 public Python repositories, and selects 255 partially covered functions across 82 files for path-guided testing.The selection comes from TestGenEvallite; private functions and functions blocked by Git or Docker errors are excluded.Source: §3.3.1 · pp. 9–10

3.3.2 Evaluation Pipeline.

  • For each function, the prompt includes extracted CFG paths alongside the code and test files, and evaluation measures Pass@1 and function line coverage.Generated tests are compared with the original gold test files and with tests prompted without execution paths.Source: §3.3.2 · p. 10

3.4 Experiment Settings

The study selects 14 models spanning non-reasoning LLMs and large reasoning models, including proprietary and open-source systems. It also specifies model access and reasoning settings for reproducibility.

3.4.1 Selection of LLMs.

  • The evaluation selects 14 LLMs, including non-reasoning models and large reasoning models from proprietary and open-source families.The selected set includes GPT-4.1 variants, DeepSeek, Qwen3, Gemma3, Qwen3-coder, o3-mini, o4-mini, and GPT-oss.Source: §3.4.1 · p. 10
  • The non-reasoning comparison includes proprietary GPT-4.1 variants and open-source models with different parameter sizes, alongside Qwen3-coder.The reasoning-model group includes proprietary o3-mini and o4-mini and open-source DeepSeek-R1, Qwen3-thinking, and GPT-oss.Source: §3.4.1 · p. 10
  • DeepSeek models use their official API, other open-source models run through OpenRouter, and supported temperature settings are set to 0.The OpenAI reasoning models o3-mini and o4-mini use medium reasoning effort.Source: §3.4.2 · p. 10

4 Study Results

Across competition programs, path classification, and real-world repositories, LLMs show useful execution-path reasoning, but performance depends on task and path complexity. Reasoning models lead on test generation, while classification and test executability remain important constraints.

4.1 RQ1: Results on Test Case Generation

  • 65.6% path accuracy: o4-mini leads test generation on paths averaging over 100 branches, and all five LRMs outperform every non-reasoning model.The coding model Qwen3-coder also trails Qwen3-235B despite its larger parameter size.Source: §4.1 · pp. 10–11, Table 2 · p. 11
  • Removing loop counters moderately degrades path accuracy, while removing branch-condition tags drives every model below 25% path accuracy.Non-reasoning models lose 4–11 percentage points when loop counters are removed; LRMs are more affected, though they remain ahead of non-reasoning models.Source: Table 3 · p. 11, §4.1 · p. 12
  • For 10–50-branch paths, LRMs maintain accuracy above 0.6 while non-reasoning models fall below 0.4 beyond 30 branches; on paths over 50 branches, both groups are unstable and mostly below 0.4.On paths with fewer than 10 branches, non-reasoning models perform comparably to reasoning models.Source: §4.1 · p. 12, Figure 3 · p. 13
  • LRMs use multi-stage constraint solving, but common test-generation errors include misunderstanding APIs and loops and making mistakes in program logic.The described process includes simulating the path, solving constraints, and re-simulating to check the generated input.Source: §4.1 · pp. 12–15

4.2 RQ2: Results on Path Classification

  • 82.9% accuracy: Qwen3-235B leads path classification, identifies all 120 division-by-zero bugs, and achieves F1 above 0.93 for those bugs and 0.73 for valid paths.The dataset is imbalanced, so the authors also report Macro-F1 and Balanced Accuracy; the majority-class baseline's approximately 72% accuracy masks its failure on valid and invalid paths.Source: Table 5 · p. 15, §4.2 · p. 15
  • Most models remain weak at identifying infeasible paths, and LRMs selected for weaker multi-class results also trail non-reasoning models in both binary classification settings.The authors state that additional augmentation would be needed to use LLMs to prune infeasible paths in symbolic execution.Source: §4.2 · pp. 15, 16, 18
  • Longer DeepSeek-R1 reasoning traces are negatively correlated with classification accuracy, including after grouping paths by difficulty.Accuracy is 46.8% for traces under 3,000 tokens and 26.5% for traces over 3,000 tokens; the authors suggest overthinking may contribute to weaker classification.Source: §4.2 · pp. 17–18, Table 6 · p. 17, Table 7 · p. 17

4.3 RQ3: Results on Real-World Repositories

  • On real-world repositories, o4-mini reaches 86.5% overall line coverage and 53.7% Pass@1, while execution-path prompts improve coverage more consistently than test pass rates.The authors identify test executability as the primary limitation on coverage gains; strong non-reasoning models show coverage capabilities comparable to LRMs.Source: Table 10 · p. 19, §4.3 · pp. 19–20

5 Discussion

The discussion finds that LLM efficiency varies by model type, while most remain slower than symbolic tools; it also examines future directions, possible data leakage, and prompt sensitivity.

5.1 Analysis on Efficiency

  • Most LLMs remain slower than symbolic execution tools, although they can finish some extremely complex paths where CrossHair times out.Non-reasoning LLMs and proprietary LRMs with controllable reasoning take 15 to 60 seconds per path, while DeepSeek-R1 takes more than five minutes on a single path.Source: §5.1 · pp. 20–21

5.2 Future Directions

  • Future work could shorten LRMs’ long reasoning traces, train smaller models with verifiable rewards, and use LLMs to prune infeasible or prioritize important paths.The authors note that test-case correctness can be verified against execution traces, offering a basis for reinforcement learning from verifiable rewards.Source: §5.2 · pp. 21–22

5.3 Discussion on Data Leakage

  • Post-October 2023 performance drops were attributed to longer paths rather than memorization, suggesting data leakage is not a primary concern for test-case generation.The average path length rose from 220 statements before the cutoff to 289 afterward.Source: §5.3 · p. 22

5.4 Discussion on Uncertainty

  • Across five tested models, test-case generation accuracy varied little between semantically equivalent prompt templates, indicating limited prompt-wording sensitivity in this setting.The study compared three edited prompt variants with the original template.Source: §5.4 · pp. 22–23

6 Threats to Validity

The study’s findings are bounded by the omission of LLM augmentation techniques and the lack of a direct path-solving comparison with traditional symbolic execution tools.

6 Threats to Validity

  • Advanced prompting and fine-tuning were not applied, so the study evaluates early-stage LLM ability rather than augmented systems.The authors frame the work as an exploration of LLMs’ inherent ability to solve path constraints.Source: §6 · p. 23
  • No direct path-solving comparison with traditional tools was possible because existing Python symbolic execution tools cannot solve predefined paths.The study instead compares time efficiency with CrossHair.Source: §6 · p. 23

7 Conclusion

The paper evaluates LLM reasoning about complex Python execution paths across test generation and path classification, using competition and real-world programs. It finds potential alongside distinct challenges and motivates future work on other languages and tool integration.

7 Conclusion

  • The study evaluates test-case generation and execution-path classification across programming-contest algorithms and large-scale real-world repositories.The tasks address path reasoning for test generation and bug detection.Source: §7 · p. 23
  • LLMs show potential for execution-path reasoning, with reasoning and non-reasoning models excelling in different tasks.The authors also identify API-behavior misunderstandings and overthinking-related performance degradation as remaining challenges.Source: §7 · p. 23
  • The authors conclude that LLM-powered reasoning can substitute for symbolic execution to a certain extent and propose studying other languages and integrating symbolic-analysis tools.They also identify post-training as a future direction.Source: §7 · p. 23
Loading 2511.18288v2…