Abstract
Neural surrogate models have emerged as powerful and efficient tools in data mining. Meanwhile, large language models (LLMs) have demonstrated remarkable capabilities in code-related tasks. We investigate a novel application: using LLMs as surrogate models for code execution prediction. Given LLMs' unique ability to understand and process diverse programs, they present a promising direction for building general-purpose surrogate models. To systematically investigate this capability, we introduce SURGE, a comprehensive benchmark with 1160 problems covering 8 key aspects: multi-language programming tasks, competition-level programming problems, repository-level code analysis, high-cost scientific computing, time-complexity-intensive algorithms, buggy code analysis, programs dependent on specific compilers or execution environments, and formal mathematical proof verification. Through extensive empirical analysis of 21 open-source and proprietary LLMs, we examine scaling laws, data efficiency, and predictive accuracy. Our findings reveal important insights about the feasibility of LLMs as efficient surrogates for computational processes, with implications for automated software testing, program analysis, and computational resource optimization in data mining applications.
Introduction
In fields such as scientific computing, software security, and data mining, executing code can often be computationally expensive or inherently risky. Traditionally, researchers have relied on specialized neural surrogate models to approximate these execution processes. However, the recent rise of Large Language Models (LLMs) with sophisticated code generation and understanding capabilities raises a compelling question: Can LLMs serve as general-purpose surrogate executors, predicting program outputs through "mental simulation" without actual execution?
This paper introduces SURGE, a rigorous benchmark designed to systematically evaluate the potential of LLMs in this role. By moving beyond anecdotal evidence, we provide a large-scale analysis of how current state-of-the-art models handle the complexities of code simulation across diverse programming paradigms and execution environments.
The SURGE Benchmark
To stress-test LLMs, the SURGE benchmark comprises 1,160 problems categorized into eight specialized subsets:
- Multi-lingual (ML): Fundamental tasks across seven languages (C, C++, C#, Java, Rust, Python, Julia).
- Competition-level (CL): Complex logical inference problems sourced from platforms like LeetCode.
- Repository-level (RL): Tasks involving long-range dependencies across multiple files.
- Scientific Computing (SC): Simulations of ODE solvers, signal processing, and optimization routines.
- Time-Complexity (TC): Computationally intensive algorithms like the Traveling Salesperson Problem.
- Buggy Code (BG): Predicting specific error messages and behaviors of broken code.
- Differential Results (DR): Code where outputs vary based on compiler versions or optimization levels (e.g., -O3 vs -O0).
- Formal Language (FL): Proof verification using the Lean4 formal math language.
Experimental Insights
We evaluated 21 models, including proprietary leaders like GPT-4o and Claude 3.5 Sonnet, alongside open-source models like Llama 3.1 and Qwen 2.5. Our analysis yielded several critical insights into the current state of LLM-based surrogate execution.
The "1-Second Wall"
One of the most significant findings is the existence of a "computational wall." We observed a stark correlation between the real-world CPU execution time of a program and the model's predictive accuracy. As shown in the figure below, when a program requires more than one second of CPU time, even the most advanced models like Claude 3.5 Sonnet and GPT-4o see their accuracy drop to zero. This suggests that LLMs struggle to simulate deep iterative processes or high-complexity algorithms that exceed a certain threshold of symbolic steps.
Model Performance and Scaling
Claude 3.5 Sonnet emerged as the top performer, achieving an average accuracy of approximately 59% when using Chain-of-Thought (CoT) prompting. Our study also confirmed that surrogate execution capabilities follow standard scaling laws: performance improves consistently with increases in both model parameters and the volume of training data. Interestingly, "Coder-specific" models often outperformed general-purpose models in zero-shot settings, though general chat models frequently closed the gap when allowed to use CoT reasoning.
Reasoning and Bias
While CoT generally improves performance by allowing the model to trace logic step-by-step, it can be a double-edged sword. In "Differential Results" (DR) tasks, where subtle compiler behaviors are key, the additional reasoning steps sometimes introduced errors that led the model away from the correct prediction. Furthermore, models exhibited a clear language bias, performing significantly better on Python than on lower-level languages like C++ or Rust, likely due to Python's simpler syntax and the prevalence of Python code in training corpora.
Conclusion
LLMs show significant promise as surrogate executors, particularly for short-running, logically straightforward code. However, they are currently limited by a "computational wall" and struggle with the exactness required for complex runtime behaviors. Future research should explore hybrid approaches that combine the neural intuition of LLMs with the symbolic precision of traditional program analysis tools to create more robust and reliable surrogate models.
Code and dataset are released at https://github.com/Imbernoulli/SURGE.
Summary updated