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

Problem Statement

Execution path reasoning is a fundamental capability for software engineering tasks such as testing, bug finding, and verification. Traditionally, this is achieved through symbolic execution, which uses SMT solvers to determine the satisfiability of path constraints. However, existing SMT-based approaches struggle with complex data structures, external API calls, and the highly flexible syntax of dynamically typed languages like Python. Consequently, there is a lack of widely adopted, mature symbolic execution tools for Python. While Large Language Models (LLMs) have demonstrated strong capabilities in code generation and understanding, it remains an open question whether they can effectively reason about complex execution paths without relying on traditional constraint solvers.

Methodology

The authors conduct a systematic empirical study on the efficacy of LLMs in reasoning about execution paths in Python. The study focuses on two primary tasks: Test Case Generation (a generation task) and Path Classification (a classification task).

Benchmarks and Data Construction

1. Competition-Level Test Case Generation: Using the TestEval benchmark (210 Python programs from LeetCode with high cyclomatic complexity), the authors extracted 509 execution paths by running example test cases. They modified the Python trace library to capture branch conditions and loop iteration counts, creating a dataset with an average of 233 statements and 103 branch statements per path.
2. Path Classification: Using the Google runtime error dataset (derived from CodeNet), the authors filtered for programs with "division by zero" errors. They employed a Control Flow Graph (CFG) traversal algorithm to extract both feasible and infeasible paths. The dataset was manually annotated into three classes: Valid (satisfiable, no bugs), Invalid (infeasible), and ZeroDivision (valid until a bug is triggered). This resulted in 2,010 execution paths.
3. Real-World Repository Testing: Using the TestGenEval dataset (11 public Python repositories), the authors identified 255 partially covered functions. They extracted execution paths to evaluate whether providing path information improves test coverage in real-world software containing external dependencies.

Experimental Setup

The study evaluated 14 LLMs, categorized into Non-reasoning LLMs (e.g., GPT-4.1 series, DeepSeek-V3, Qwen3, Gemma3) and Large Reasoning Models (LRMs) (e.g., o3-mini, o4-mini, DeepSeek-R1, Qwen3-thinking).

• Test Case Generation: LLMs were prompted to generate test inputs that reproduce a given execution path. Metrics included Path Accuracy (exact match) and Node Accuracy (prefix match).
• Path Classification: LLMs were prompted to classify paths as Valid, Invalid, or ZeroDivision. Metrics included Accuracy, Balanced Accuracy, and Macro F1 scores.
• Real-World Evaluation: LLMs were prompted to generate unit tests covering specific paths. Metrics included Pass@1 (test executability) and Line Coverage.

Key Results

1. Test Case Generation (RQ1)

• Performance: State-of-the-art LLMs, particularly LRMs, demonstrated the ability to generate correct test cases for complex execution paths. The best-performing model, o4-mini, achieved a 65.6% Path Accuracy on the challenging competition-level benchmark.
• Reasoning vs. Non-Reasoning: LRMs consistently outperformed non-reasoning LLMs. The advantage was most pronounced on medium-length paths (10–50 branch conditions). For very long paths (>50 branches), performance degraded for all models.
• Ablation Study: Removing explicit loop iteration counters or branch condition tags caused significant performance drops, indicating that LLMs rely heavily on these explicit symbolic states to track execution flow.
• Error Analysis: Human evaluation of reasoning traces (CoT) from DeepSeek-R1 revealed that the most common failure modes were misunderstanding APIs (especially complex data structures) and loop/ternary operator logic, rather than pure logical deduction errors.

2. Path Classification (RQ2)

• Performance: LLMs achieved up to 82.9% accuracy in classifying paths. Qwen3-235B was the top performer, successfully identifying all 120 division-by-zero bugs in the dataset.
• LRM Limitations: Contrary to the generation task, LRMs did not consistently outperform non-reasoning models in classification. In fact, some LRMs (e.g., DeepSeek-R1, o4-mini) performed worse.
• Overthinking Phenomenon: The study identified a negative correlation between the length of the reasoning Chain-of-Thought (CoT) and classification accuracy. LRMs often engaged in "overthinking," where excessive reasoning steps led to incorrect conclusions (e.g., misclassifying a ZeroDivision path as Invalid due to contradictory logic about branch conditions).

3. Real-World Repositories (RQ3)

• Coverage Improvement: Providing execution path information to LLMs consistently improved test coverage in real-world repositories compared to baseline prompts.
• Executability Bottleneck: While coverage improved, the Pass@1 rate (the ability to generate executable tests) remained the primary bottleneck, with the best model achieving only 53.7%.
• Model Parity: In real-world scenarios, state-of-the-art non-reasoning LLMs exhibited test coverage capabilities comparable to LRMs, suggesting that for complex, dependency-heavy code, the specific "reasoning" architecture of LRMs offers diminishing returns compared to their performance on isolated algorithmic problems.

Significance and Contributions

The paper makes the following contributions:

1. First Systematic Study: It presents the first comprehensive empirical study on LLMs' ability to reason about execution path constraints in the dynamically typed language Python, a domain where traditional symbolic execution tools are largely ineffective.
2. New Benchmarks: The authors constructed new benchmarks encompassing competition-level problems and real-world repositories, covering downstream tasks like test case generation, path feasibility analysis, and bug detection.
3. Insights into LLM Capabilities: The study reveals that while LLMs (especially LRMs) can solve complex path constraints, their effectiveness is task-dependent. They excel at generating test inputs for medium-length paths but struggle with classification tasks due to "overthinking" and have limited ability to distinguish infeasible paths reliably.
4. Practical Implications: The findings suggest that LLMs can serve as a valuable complementary heuristic or potential replacement for symbolic execution in languages lacking mature tools. However, challenges regarding API understanding, loop reasoning, and inference efficiency (particularly for open-source LRMs) remain.

Limitations and Future Directions

The authors acknowledge that their study did not employ advanced prompting techniques or fine-tuning, focusing instead on the inherent capabilities of pre-trained models. They note that the time efficiency of open-source LRMs is currently inferior to traditional solvers due to long reasoning traces. Future work is suggested to focus on efficient reasoning strategies, reinforcement learning with verifiable rewards (RLVR), and hybrid approaches that integrate LLMs with traditional symbolic execution tools to prune infeasible paths.