L L 0-Reasoning Bench: Evaluating Procedural Correctness in Language Models via Simple Program Execution
Simeng Sun, Cheng-Ping Hsieh, Faisal Ladhak, Erik Arakelyan · 2025
Read L L 0-Reasoning Bench: Evaluating Procedural Correctness in Language Models via Simple Program Execution by Simeng Sun, Cheng-Ping Hsieh, Faisal Ladhak, Erik Arakelyan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-22832.txt.
Introduction
Simeng Sun and co-authors test whether language models can run simple programs step by step without error, in a paper from two thousand twenty-five. Their bench, L0-Bench, grades full execution traces on made-up Python functions with plain steps. Made-up tasks let step count and other axes scale at will.
All tested models, closed and open, slipped more as trace length grew. Larger models and reasoning-tuned models held accuracy longer across steps. Extra context, voting over many tries, and longer thinking were also probed as test-time levers. Much room stays to lift this base skill, the authors find. Readers get a clean ruler for step-faithful reasoning, apart from final answers.
Catalog record
| CREATOR | Simeng Sun, Cheng-Ping Hsieh, Faisal Ladhak, Erik Arakelyan |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 68 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-22832
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
L L 0-Reasoning Bench: Evaluating Procedural Correctness in Language Models via Simple Program Execution Simeng Sun, Cheng-Ping Hsieh, Faisal Ladhak, Erik Arakelyan Abstract Complex reasoning tasks often rely on the ability to consistently and accurately apply simple rules across incremental steps, a foundational capability which we term “level-0” reasoning. To systematically evaluate this capability, we introduce L 0 L0 -Bench, a language model benchmark for testing procedural correctness – the ability to generate correct reasoning processes, complementing existing benchmarks that primarily focus on outcome correctness. Given synthetic Python functions with simple operations, L 0 L0 -Bench grades models on their ability to generate step-by-step, error-free execution traces. The synthetic nature of L 0 L0 -Bench enables systematic and scalable generation of test programs along various axes (e.g., number of trace steps). We evaluate a diverse array of recent closed-source and open-weight models on a baseline test set. All models exhibit degradation as the number of target trace steps increases, while larger models and reasoning-enhanced models better maintain correctness over multiple steps. Additionally, we use L 0 L0 -Bench to explore test-time scaling along three dimensions: input context length, number of solutions for majority voting, and inference steps. Our results suggest substantial room to improve “level-0” reasoning and potential directions to build more reliable reasoning systems. 1 Introduction Reasoning systems, by default, assume a fundamental prerequisite – the consistent and accurate execution of simple rules. Whether performing multi-digit arithmetic or following a legal procedure, the ability to reliably execute predefined rules is essential, as even a small error can derail the process from an expected trajectory, regardless of how sophisticated the system might be in other respects. We consider the ability to reliably execute simple rules across incremental steps as the “level-0” reasoning ability, or a crucial form of sub-intelligence ( Morris et al., 2023 ) . This view also aligns with the recent discussion by Shalev-Shwartz et al. (2024) who formalize error-bounded precise reasoning in multi-step problem solving. However, modern neural language models are trained to approximate statistical patterns. Can these probabilistic models consistently and reliably execute discrete rules with guaranteed correctness? To answer this question, we introduce L0 -Bench, a synthetic benchmark to explore the feasibility of a language model functioning as a neural language computer . Specifically, given a simple program, a language model is graded on its ability to generate an execution trace step by step infallibly. Focusing on programming languages offers several advantages. With precisely defined programs, L0 -Bench removes the inherent ambiguity of natural languages and isolates the reliable execution of simple rules from other reasoning processes (e.g., inferring general algorithms from observations). The callable functions also automatically produce execution traces, which allow for the evaluation of procedural correctness (i.e., maintaining correctness across reasoning processes), an aspect often overshadowed by the simpler evaluation of outcome correctness. Moreover, programs are easy to generate and can be systematically controlled. In L0 -Bench, we use generative grammar to construct simplified Python programs. By imposing multiple constraints on the grammar, we reduce the difficulty of executing each line of code, thereby avoiding unnecessary evaluation of operations specific to Python or arithmetic. The rule-based generation also enables flexible control of various axes (e.g., number of trace steps, program length) while being significantly more cost-effective than LM-based data curation. Furthermore, the synthetic nature mitigates concerns about data leakage/memorization and allows for scalable generation of test instances. L0 -Bench relates to prior studies on algorithmic tasks ( Lee et al., 2024 ; Markeeva et al., 2024 ) , such as large-number multiplication ( Deng et al., 2024 ) . However, L0 -Bench differs in providing a general framework where the input program is not limited to a single predefined routine; instead, L0 -Bench is able to admit any task that can be formulated as a program. While external tools naturally excel at executing discrete rules, we argue that the ability to perform simple operations step-by-step like a Turing Machine, without external tools, is still critical. It is essential not only for reasoning tasks that rely on basic deduction, but also for facilitating robustness, interpretability, and faithful alignment with human intents. We evaluate 20 models with L0 -Bench, including closed-source models, open-weight general-instruct models (ranging from 7B to 405B), and reasoning-enhanced models that generate “think” patterns, such as DeepSeek-R1. Experimental results demonstrate the advantages of larger model sizes and reasoning enhancements in achieving better procedural correctness. However, all models exhibit degradation as the target number of trace steps increases. We further leverage L0 -Bench as a constrained environment to explore test-time scaling along three dimensions: (1) scaling input context by increasing step-by-step demonstrations, (2) scaling width by increasing the number of solutions for majority voting, and (3) scaling inference steps by enabling long chain-of-thought. While each dimension independently improves performance, our results reveal key limitations: scaling many-shot demonstrations yields diminishing returns, and sometimes degrades performance even for long-context models; majority voting plateaus as the number of voter grows; and long chain-of-thought reasoning increases latency without consistently benefiting all model sizes. Nonetheless, our scaling analysis demonstrates the benefits of scaling alone all three scaling dimensions and suggests ample room for improvement in current models. Our contributions are as follows: • We introduce L0 -Bench, a synthetic benchmark for evaluating procedural correctness in neural language models via program execution. L0 -Bench isolates step-by-step rule-execution from other reasoning processes (e.g., induction and search) and provides a controlled, verifiable evaluation framework. • By evaluating 20 recent language models, we reveal their limitations in maintaining correctness across simple multi-step procedures, and show the benefits of larger model sizes and reasoning enhancements with long chain-of-thought. • We further demonstrate the benefits of test-time scaling along three dimensions (input demonstrations, majority voting, and inference steps) and discuss the trade-off between performance and efficiency. Overall, our findings reveal key limitations of current LLMs in long step-by-step rule- execution and suggest potential directions toward more reliable reasoning systems. 1 1 1 We release code at https://github.com/SimengSun/L0-reasoning-bench . 2 L-0 Benchmark 2.1 Benchmark construction Program execution can be viewed as a special form of deduction. During execution time, simple predefined rules are applied step-by-step, moving the execution process from one state to the next deterministically. For instance, list.pop() requires applying the general rule of “popping an item” to a list instance , such as list = [1,2,3,4] . Evaluating a model’s ability to execute simple programs therefore can serve as a test of its deductive capability – a necessary but not sufficient condition for complex reasoning processes. We introduce L0 -Bench to test the deductive capability in neural language models via program execution, i.e., the ability to follow unambiguously defined routines step-by-step without deviation, akin to a neural language computer. In L0 -Bench, we construct synthetic Python programs using generative grammar. To avoid testing Python-specific operations or evaluations of complex expressions, we impose multiple constraints on the generative grammar, while preserving fundamental elements of conventional programming languages: (a) simple arithmetic and comparison operations, (b) control (conditional branch and loops), and (c) memory access and operations. The grammar hence covers diverse procedures that require modifying execution states (e.g., append an item to a list) and strictly adhering to the control