CoCoNUT: Structural Code Understanding does not fall out of a tree

Claas Beger, Saikat Dutta · 2025

Read CoCoNUT: Structural Code Understanding does not fall out of a tree by Claas Beger, Saikat Dutta (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-2501-16456.txt.

Introduction

Claas Beger and Saikat Dutta probe a gap in what large language models understand about code, in this 2025 paper. The models score well on tests of writing, fixing, and completing programs. High scores suggest skill close to human programmers. Yet writing code and grasping how code runs are two different things. The authors test the second skill directly.

They took model-written solutions from a known coding benchmark and traced the true path each program follows when run. They then asked seven top models to match that path, function call by function call. The models stumbled on this structural task despite their strong coding scores. The paper argues that control flow, the order in which code steps run, does not come free with good benchmark results.

Catalog record

CREATORClaas Beger, Saikat Dutta
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE37 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-16456

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

CoCoNUT: Structural Code Understanding does not fall out of a tree Claas Beger, Saikat Dutta Abstract Large Language Models (LLMs) have shown impressive performance across a wide array of tasks involving both structured and unstructured textual data. More recently, LLMs have demonstrated remarkable abilities to generate code across different programming languages. Recent results on various benchmarks for code generation, repair, or completion suggest that certain models have programming abilities comparable to or even surpass humans. In this work, we demonstrate that the high performance on such benchmarks does not correlate to humans’ innate ability to understand the structural control flow of code. For this purpose, we extract code solutions from the HumanEval benchmark, which the relevant models perform very strongly on, and trace their execution path using function calls sampled from the respective test set. Using this dataset, we investigate the ability of 7 state-of-the-art LLMs to match the execution trace and find that, despite the model’s abilities to generate semantically identical code, they possess only limited ability to trace the execution path, especially for longer traces and specific control structures. We find that even the top-performing model, Gemini 1.5 Pro can only fully correctly generate the trace of 47% of HumanEval tasks. In addition, we introduce a subset for three key structures not, or only contained to a limited extent in HumanEval: Recursion, Parallel Processing, and Object Oriented Programming principles, including concepts like Inheritance and Polymorphism. Besides OOP, we show that none of the investigated models achieve an average accuracy of over 5% on the relevant traces. Aggregating these specialized parts with the ubiquitous HumanEval tasks, we present the Benchmark CoCoNUT: Co de Co ntrol Flow for N avigation U nderstanding and T esting, which measures a models ability to trace the execution of code upon relevant calls, including advanced structural components. We conclude that the current generation LLMs still need to significantly improve to enhance their code reasoning abilities. We hope our dataset can help researchers bridge this gap in the near future. [email protected] I Introduction Large Language Models (LLMs), such as GPT-4 and Llama, have demonstrated remarkable progress across diverse tasks and are now widely used in applications like code generation (e.g., GitHub Copilot [ 1 ] ), healthcare [ 2 ] , and finance [ 3 ] . In programming, LLMs show great promise by automating tasks such as generating code, authoring tests, detecting bugs, and repairing programs. However, achieving true success in these tasks requires LLMs to not only generate code but also reason about its behavior. To develop such capabilities, robust benchmarks that evaluate code reasoning are essential. Current benchmarks like HumanEval [ 4 ] and MBPP [ 5 ] primarily assess code generation for simple tasks and are already saturating, with GPT4 achieving over 90% accuracy [ 6 ] . While newer benchmarks include execution reasoning tasks (e.g. CruxEval [ 7 ] , LiveCodeBench [ 8 ] ), they do not test the understanding of control flows. Thus, a more structurally focused code reasoning benchmark is needed. Our Work. To address this, we introduce CoCoNUT– a novel benchmark for evaluating LLMs’ ability to trace complex control flows. Each task in CoCoNUT includes a program and test input, requiring the model to generate a trace of line numbers executed by the program. This challenging task necessitates handling long-term dependencies, control structures, and nested expressions, as shown in Figure 1 . We argue that tracing execution is a natural test of a model’s understanding of code. Currently, CoCoNUT includes 161 tasks and 1083 traces derived from HumanEval ( HumanEval-Trace ), and 124 tasks with 620 traces focusing on advanced programming structures such as recursion, parallel processing, and object-oriented principles ( Advanced-Trace ) – totaling 285 tasks and 1703 traces. Fig. 1: Tracing the execution flow requires a diverse understanding of code structures, even for shorter sequences like HumanEval Tasks. We list a couple of examples for Task ID 10. Results. We evaluate 7 state-of-the-art LLMs, including proprietary models (GPT-4o, Gemini 1.5 Pro, and Claude 3.5 Sonnet) and open-source models (e.g., LLama3.1, Qwen2.5Coder, Mistral Codestral 22B, and CodeLLama 7B). While LLMs excel at tracing simple programs, their performance on advanced control flows lags far behind their code generation abilities. For instance, the top-performing model, Gemini 1.5 Pro, traces only 47% of HumanEval tasks, and accuracy sharply declines for traces longer than 25 lines. Surprisingly, advanced prompts like Chain-of-Thought offer limited benefits and sometimes degrade the performance on complex tasks. We provide a detailed discussion of results in § IV . Our code and dataset are available here . II CoCoNUT Framework II-A Tasks We utilize the HumanEval dataset proposed by [ 9 ] , which consists of 164 Python programming tasks and serves as a suitable benchmark for structural understanding. These tasks are frequently used to evaluate LLMs, ensuring a correlation between control flow understanding and task-solving performance. To adapt the dataset, we merge the function signature (including docstring examples) with the canonical solution. Using an abstract syntax tree, we parse the testing code to identify all calls to the candidate function and extract their arguments. HumanEval tasks are concise, with function bodies ranging from 1 to 28 lines and an average of 7.7 tests per function, resulting in approximately 1250 potential execution traces. We employ the Python tracer provided by the sys library to analyze execution for each argument set provided by a test call, filtering out sets requiring more than 1024 consecutive tokens, yielding 1083 argument sets across 161 tasks. Additionally, Liu et al. introduced EvalPlus [ 10 ] , which expands the number of tests for HumanEval tasks, revealing that model performance was previously overestimated. While we generate an additional dataset based on EvalPlus (over 120,000 traces without trace length filtering), we limit our scope to a preliminary evaluation on the base HumanEval tests. II-B Evaluation Metrics We employ two main evaluation metrics: Exact Match and Similarity . Exact Match provides a straightforward measure of whether a model can fully trace the relevant execution. To avoid bias from tasks with varying numbers of tests, we compute task-level accuracy first, then aggregate it as an overall Accuracy Mean . Note that this metric does not apply when evaluating traces of different lengths, as trace lengths can vary significantly and are not always tied to code line numbers. While accuracy is intuitive, it does not capture the diversity of errors. A trace that deviates by only one line is better than a completely incorrect prediction. To address this, we use a Similarity metric based on the Gestalt-pattern matching algorithm [ 11 ] . This metric focuses on matching contiguous subsequences, emphasizing longer matches over distributed ones. The similarity between two sequences A and B is computed as: S(A,B)=\frac{2\cdot M}{|A|+|B|} (1) where M is the total number of matching characters in contiguous blocks, and |A| and |B| are the lengths of the sequences. The metric ranges from 0 to 1 and complements the accuracy by quantifying partial matches. For incorrectly generated traces, we also report False Similarity . Further, we distinguish the hard accuracy ( Acc Hard ), as the fraction of tasks that the models solve completely, meaning they are able to reproduce the trace

Read the complete text