Technical Summary: SURGE: On the Potential of Large Language Models as General-Purpose Surrogate Code Executors

Problem Statement

Neural surrogate models are established tools for approximating complex computational processes in data mining and scientific computing, offering efficiency over direct simulation. Concurrently, Large Language Models (LLMs) have demonstrated significant capabilities in code understanding and generation. However, a critical, underexplored question remains: Can LLMs serve as general-purpose surrogate code executors? This capability involves predicting the execution behavior, output, or errors of a program without actually running it.

The ability to predict code execution outcomes without execution holds significant potential for:

• Scientific Computing: Reducing the computational cost and time of running simulations and optimizing configurations.
• Security: Assessing the behavior of untrusted code in sensitive environments without exposing systems to vulnerabilities.
• Resource Constraints: Executing code in environments where specific compilers or dependencies are unavailable.
• AI Development: Improving code understanding, generation, and mathematical reasoning by accurately predicting potential outputs or errors. Furthermore, accurate execution prediction is vital for LLMs acting as reward models in reinforcement learning for code tasks.

Traditional approaches, such as symbolic execution or containerized environments, struggle with generalization across languages, scalability, or still require full execution. While recent studies have touched upon LLMs as code executors, they often rely on case studies rather than systematic, large-scale analysis.

Methodology: The SURGE Benchmark

To systematically investigate the feasibility of LLMs as surrogate executors, the authors introduce SURGE, a comprehensive benchmark comprising 1,160 problems across 8 distinct subsets. The dataset construction employs four methodologies: Iterative Refactor, Repository Sampling, Manual Implementation, and Inference & Verification.

The 8 subsets cover diverse dimensions of code execution:

1. Multi-language Code (ML): Fundamental programming tasks in 7 languages (C, C++, C#, Java, Rust, Python, Julia) adapted from McEval.
2. Competition-level Code (CL): High-difficulty problems from platforms like LeetCode and Luogu, categorized into 5 difficulty levels.
3. Repository-level Code (RL): Multi-file codebases (e.g., Sudoku solvers, LaTeX generators) testing long-range dependencies and file structures.
4. Scientific Computing (SC): High-cost simulations including ODE solving, optimization (gradient descent), PDE solving, and FFT.
5. Time-Consuming Algorithms (TC): Computationally intensive tasks (e.g., TSP, Hamiltonian Cycle, Monte Carlo simulations) with varying CPU execution times.
6. Buggy Code (BG): Code containing injected errors (from DebugBench) to test the prediction of runtime errors and exceptions.
7. Differential Results (DR): Code snippets that produce different outputs based on compiler versions, C++ standards, or optimization levels.
8. Formal Mathematics (FL): Lean4 theorem proofs to evaluate the ability to verify mathematical correctness via compiler feedback.

Evaluation Metrics: The benchmark utilizes tailored metrics for each subset, including Exact Match, Edit Distance, Ratcliff/Obershelp similarity, Relative Absolute Error (RAE), Rank Correlation (Spearman), and Jaccard similarity for error messages.

Experimental Setup: The authors evaluated 21 LLMs (both open-source and proprietary, ranging from 0.5B to 70B+ parameters) under three prompting strategies: Zero-shot, Zero-shot with Chain-of-Thought (CoT), and Few-shot with CoT.

Key Results

Extensive evaluation reveals that while LLMs show promise, they are currently approximators rather than exact executors.

• Model Performance: Even the strongest models (e.g., Claude-3.5-Sonnet, GPT-4o) achieve only moderate performance on SURGE, highlighting the benchmark's difficulty and discriminative power. Performance varies significantly across subsets; for instance, models excel in Python but struggle with Rust due to strict ownership rules.
• Scaling Laws: Performance consistently improves with model size and training steps. Larger models (e.g., 70B) demonstrate higher learning efficiency and performance ceilings compared to smaller counterparts (e.g., 0.5B).
• Prompting Strategies: Chain-of-Thought (CoT) and Few-shot learning generally enhance performance, though their effectiveness varies by task. Notably, CoT can sometimes degrade performance on optimization tasks by adding unnecessary complexity.
• Anomalies and Limitations:
  • Overthinking: In some cases, larger models performed worse than smaller ones by engaging in overly complex reasoning that led to critical logical errors, whereas smaller models correctly grasped core logic.
  • Execution Time Correlation: Prediction accuracy drops sharply as the actual CPU execution time of the target program increases. For tasks requiring >1 second of execution, even state-of-the-art models struggle to produce correct answers.
  • Error Prediction: In the Formal Math subset, stronger models sometimes performed worse by actively "hallucinating" errors in correct code, while smaller models assumed code was error-free, inadvertently achieving higher accuracy on balanced datasets.
• Error Analysis: The primary failure modes involve Calculation Process and Calculation Accuracy, particularly in CoT settings where the reasoning chain itself introduces errors. Models also struggle with Context Awareness in repository-level tasks.

Significance and Contributions

The paper claims the following key contributions:

1. SURGE Benchmark: The introduction of the first holistic benchmark specifically designed to evaluate LLMs as general-purpose surrogate code executors, covering 8 diverse aspects of code execution.
2. Large-Scale Evaluation: The first systematic analysis of 21 LLMs on surrogate execution tasks, providing empirical data on their capabilities and limitations.
3. Scaling Law Insights: An investigation into how model size and training data scale affect surrogate execution capabilities, finding that these tasks follow scaling laws similar to other language tasks.

The authors conclude that while LLMs possess the potential to serve as efficient surrogates for computational processes, significant room for improvement remains in grounding these models to handle edge cases, intricate runtime behaviors, and execution-dependent state changes. The work charts the current landscape and suggests that future research should focus on enhancing reasoning robustness and integrating LLMs with traditional program analysis techniques.