Source-linked AI summary
Complexity-Aware Evaluation of LLM Comprehension
Ali Mohammadi Esfahani, Nafiseh Kahani, Samuel A. Ajila
TL;DR
Aggregate benchmark accuracy may conceal how LLM code-comprehension reliability changes as code becomes structurally more complex. This paper evaluates code comprehension with complexity metrics and automatic and manual tasks, finding accuracy declines as complexity increases.
Problem
Aggregate accuracy can conceal the conditions under which comprehension of structurally complex code becomes difficult.
Source: §I · p. 1Method
The evaluation annotates Python functions with four structural-complexity metrics and assesses them through automatic input–output prediction and manual semantic questions.
Source: §III · p. 2, C. RQ3: Manual Semantic Comprehension · p. 7Results
Across automatic and manual tasks, both models became less accurate as complexity rose; DeepSeek-Coder-V2’s automatic accuracy fell from 93.52% on Low-complexity functions to 52.78% on High-complexity functions.
Source: §VII · p. 9Takeaways & Limitations
Complexity-aware evaluation provides a more diagnostic view of model reliability than aggregate accuracy alone.
Source: §VII · p. 9Benchmark scores may reflect the structural-complexity distribution of evaluated code, so they cannot always be attributed only to model capability.
Source: §VI · p. 8
Abstract
from arXiv · showhide
Large language models (LLMs) are increasingly used for software engineering tasks that require understanding existing source code, including behavior prediction, function explanation, debugging, and code review. However, aggregate benchmark accuracy can conceal how model reliability changes as source code becomes structurally more complex. This paper presents a complexity-aware framework for evaluating LLM code comprehension using cyclomatic complexity, nesting depth, branching factor, and Halstead volume. We evaluate DeepSeek-Coder-V2 and Llama through two complementary tasks: automatic input-output prediction over 300 Python functions and manually assessed semantic comprehension over a balanced subset of 60 functions. The functions are grouped into Low-, Medium-, and High-complexity bands. DeepSeek-Coder-V2 achieves an overall automatic accuracy of 78.33%, compared with 70.33% for Llama. However, accuracy decreases substantially from Low to High complexity, from 93.52% to 52.78% for DeepSeek-Coder-V2 and from 87.04% to 47.22% for Llama. Incorrect predictions are consistently associated with higher values of all four complexity metrics, and correlation and logistic-regression analyses confirm broadly comparable negative associations between structural complexity and correctness. Manual semantic comprehension shows the same degradation pattern, with accuracy decreasing from 100.00% to 75.00% for DeepSeek-Coder-V2 and from 90.00% to 60.00% for Llama. These findings demonstrate that complexity-aware evaluation provides a more diagnostic assessment of LLM code-comprehension reliability than aggregate accuracy alone.
I. INTRODUCTION
Understanding existing code requires models to interpret behavior, control flow, and internal state, yet aggregate scores can obscure how structural complexity affects reliability. The paper addresses this gap by connecting benchmark composition and structural-complexity analysis with complementary code-comprehension tasks.
I. INTRODUCTION
- Code-comprehension reliability matters because developers use LLMs to explain functions, predict behavior, reason about edge cases, debug, and review code.Code-generation performance alone does not fully characterize reliability in these workflows.Source: §I · p. 1
- Models must track control-flow decisions, intermediate states, boundary conditions, and symbolic operations to understand structurally complex code.Aggregate accuracy can conceal the conditions under which comprehension begins to fail.Source: §I · p. 1
II. RELATED WORK
- Benchmark scores may overstate reliability when evaluated functions are mostly simple, because benchmark composition often goes unreported.Prior work also emphasizes generation, broad capability assessment, or contextual scale rather than how comprehension varies with an individual function’s structure.Source: §I · p. 1, §II · p. 2
- Prior work leaves structural complexity in comprehension less directly investigated than generated-code quality and prompt-based improvement.Existing comprehension studies often characterize difficulty through task design, broad capability assessment, contextual scale, a single difficulty label, or one evaluation modality.Source: §I · p. 1, §II · p. 2
I. INTRODUCTION
- The study groups functions by four structural metrics and combines exact input–output prediction with manual questions about function purpose, variable roles, and edge cases.Its research questions address benchmark complexity distribution, metric associations with incorrect predictions, and whether manual comprehension shows similar degradation.Source: §I · pp. 1–2, §II · p. 2
III. COMPLEXITY-AWARE EVALUATION METHOD
The evaluation assesses models’ predictions about existing Python functions across structural-complexity bands. It combines automatic and manual tasks, with a 300-function benchmark and a balanced manual subset.
III. COMPLEXITY-AWARE EVALUATION METHOD
- Each instance pairs a source function and query with a ground-truth answer, a four-metric complexity vector, and a task type.The metrics are cyclomatic complexity, nesting depth, branching factor, and Halstead volume; predictions are compared with ground truth for correctness.Source: §III · p. 2
- The evaluation analyzes performance across complexity bands, dataset sources, task types, and failure patterns after dataset construction, annotation, and model evaluation.The method applies a zero-shot protocol to both evaluated models.Source: §III · pp. 2–3
A. Dataset Construction
- The benchmark contains 300 Python functions from five sources, with most High-complexity samples drawn from LeetCode and BigCodeBench-Hard.HumanEval, MBPP-sanitized, and CRUXEval mainly contribute Low- and Medium-complexity functions; Table I summarizes composition by source and band.Source: A. Dataset Construction · p. 3, Table I · p. 3
- Functions were retained only when self-contained, deterministic, executable with the standard library, and independent of hidden state or external behavior.Functions that failed, timed out, produced ambiguous outputs, or required undocumented assumptions were excluded.Source: A. Dataset Construction · p. 3
- The manual subset contains 60 functions, with 20 sampled from each complexity band and one semantic question per function.The stratified design supports comparisons across bands while keeping manual annotation manageable.Source: A. Dataset Construction · p. 3
B. Automatic Comprehension Tasks
Automatic comprehension tests exact output prediction for concrete calls, while manual semantic comprehension asks about a function’s meaning. Both tasks use standardized prompts for the evaluated models.
B. Automatic Comprehension Tasks
- Automatic comprehension supplies the complete function and a concrete call, then evaluates whether the model predicts the exact return value.Ground-truth outputs come from controlled execution; the task supports deterministic, objective evaluation at scale.Source: B. Automatic Comprehension Tasks · p. 3, Figure 1 · p. 3
- Both tasks use the same zero-shot prompt for the two models, without few-shot examples, Chain-of-Thought instructions, or task-specific hints in the automatic task.Automatic predictions are scored by normalized exact match; empty, incorrect, or explanatory responses are marked wrong without partial credit.Source: B. Automatic Comprehension Tasks · p. 3, C. Manual Comprehension Tasks · p. 3
C. Manual Comprehension Tasks
- Manual comprehension uses 60 functions balanced across complexity bands and asks about purpose, an intermediate variable’s role, or edge-case behavior.Canonical answers define required semantic elements; responses receive no partial credit, and 20% are independently scored before disagreements are resolved.Source: C. Manual Comprehension Tasks · pp. 3–4, Figure 2 · p. 3
IV. STUDY DESIGN
The study annotates functions with static structural metrics to analyze comprehension across complexity levels. The measures capture execution paths, nesting, decision density, and symbolic processing load.
A. Complexity Annotation
- Cyclomatic complexity, nesting depth, branching factor, and Halstead volume capture complementary aspects of code structure.They are selected as properties known to affect program comprehension.Source: A. Complexity Annotation · p. 4, 1) Complexity Metrics · p. 4
1) Complexity Metrics:
- Cyclomatic complexity counts independent execution paths, nesting depth measures the deepest nested control structure, and branching factor counts decision points.Cyclomatic complexity reflects execution-path diversity; branching factor reflects how frequently control flow diverges.Source: 1) Complexity Metrics · p. 4
- Halstead volume measures lexical and operational complexity from operators and operands, reflecting the symbolic information a model must interpret.Higher volume indicates a larger and more varied set of program tokens, variables, and operations.Source: 1) Complexity Metrics · p. 4
A. Complexity Annotation
- The four metrics are computed statically from parsed Python source, and raw values are retained for statistical analysis alongside categorical complexity bands.Cyclomatic complexity, nesting depth, and branching factor use Python’s ast module; Halstead volume uses extracted operators and operands.Source: 1) Complexity Metrics · p. 4
2) Complexity Bands:
Functions are grouped into complexity bands using cyclomatic complexity and nesting depth, with the higher band chosen when they disagree. Two models are evaluated under identical zero-shot conditions, and accuracy is reported across models, bands, sources, and task types.
2) Complexity Bands:
- Cyclomatic complexity and nesting depth assign each function to a band; when they disagree, the higher band is selected.Branching factor and Halstead volume are retained for descriptive and metric-level analyses rather than primary band assignment.Source: 2) Complexity Bands · p. 4
B. Model Evaluation Protocol
- Both models are evaluated once per instance under identical zero-shot conditions, without few-shot examples, Chain-of-Thought instructions, or task-specific hints.Temperature is set to 0.Source: B. Model Evaluation Protocol · p. 4
C. Evaluation Metric
- Accuracy is reported by model, complexity band, dataset source, and task type.Automatic responses are checked against executed ground truth after normalizing formatting differences; manual responses require all essential canonical-answer elements and receive no partial credit.Source: C. Evaluation Metric · p. 4
D. Complexity-Aware Analysis
The analysis examines performance by complexity band and dataset source, compares raw complexity metrics between correct and incorrect predictions, and tests associations between complexity and correctness. For manual comprehension, it also compares bands and question types and assesses statistical association and annotation reliability.
D. Complexity-Aware Analysis
- Accuracy is compared across complexity bands and dataset sources, while raw values of four complexity metrics are compared between correct and incorrect automatic predictions.The analysis also estimates the joint relationship between those metrics and automatic prediction correctness using multivariate logistic regression.Source: D. Complexity-Aware Analysis · p. 5
- For the manual subset, accuracy is compared across complexity bands and question types to assess whether automatic-task degradation also appears in semantic comprehension.Source: D. Complexity-Aware Analysis · p. 5
E. Statistical Analysis
- Spearman correlation examines monotonic metric–correctness associations, while logistic-regression coefficients are interpreted as conditional associations because predictors may be correlated.For the manual task, a chi-square test evaluates association between band and correctness, Cramér’s V reports effect size, and Cohen’s κ assesses annotation reliability.Source: E. Statistical Analysis · p. 5
V. RESULTS
Automatic comprehension accuracy varies with the structural complexity represented in the benchmark: both models perform substantially worse on high-complexity functions. Benchmarks concentrated in low- and medium-complexity functions yield higher accuracy than those containing most high-complexity samples.
A. RQ1: Effect of Benchmark Complexity Distribution
- HumanEval, MBPP-sanitized, and CRUXEval mainly contributed Low- and Medium-complexity functions, while LeetCode and BigCodeBench-Hard supplied most High-complexity samples.The automatic benchmark contained 108 Low-, 120 Medium-, and 72 High-complexity functions.Source: A. RQ1: Effect of Benchmark Complexity… · p. 5, Table IV · p. 6
- 78.33% overall accuracy for DeepSeek-Coder-V2 exceeded CodeLlama-7b-Instruct-hf’s 70.33% across 300 instances.Both models’ accuracy declined substantially across complexity bands.Source: A. RQ1: Effect of Benchmark Complexity… · p. 5
- DeepSeek-Coder-V2 fell from 93.52% accuracy on Low-complexity functions to 52.78% on High-complexity functions; CodeLlama-7b-Instruct-hf fell from 87.04% to 47.22%.DeepSeek-Coder-V2 remained more accurate in every band.Source: A. RQ1: Effect of Benchmark Complexity… · p. 5
- Both models achieved their highest dataset accuracies on HumanEval, MBPP-sanitized, and CRUXEval, and substantially lower accuracy on LeetCode and BigCodeBench-Hard.Benchmark-level accuracy depends strongly on the complexity distribution of the evaluated functions.Source: A. RQ1: Effect of Benchmark Complexity… · pp. 5–6
B. RQ2: Structural Characteristics of Incorrect Predictions
Incorrect automatic predictions were associated with higher values of all four structural-complexity metrics. Manual semantic comprehension also declined with complexity, and question-type results varied with the semantic demands being assessed.
B. RQ2: Structural Characteristics of Incorrect Predictions
- For both models, incorrect predictions were associated with higher cyclomatic complexity, nesting depth, branching factor, and Halstead volume.For DeepSeek-Coder-V2, for example, average cyclomatic complexity rose from 3.84 for correct predictions to 7.42 for incorrect predictions.Source: B. RQ2: Structural Characteristics of… · p. 6
C. RQ3: Manual Semantic Comprehension
- Manual questions assessed function purpose, intermediate variable roles, and edge-case behavior, including whether the model could explain a variable’s role in a two-pass allocation algorithm.The example contrasts explaining internal state with predicting a concrete function-call output.Source: C. RQ3: Manual Semantic Comprehension · pp. 6–7
- Question types were approximately balanced across complexity bands, so the accuracy ordering by question type was not simply caused by complexity-band composition.Purpose questions draw on overall algorithmic patterns, while variable-role and edge-case questions require state tracking and boundary reasoning.Source: C. RQ3: Manual Semantic Comprehension · p. 7
- Purpose questions were easiest, with accuracy of 95.00% for DeepSeek-Coder-V2 and 85.00% for CodeLlama-7b-Instruct-hf; edge-case questions were hardest, at 80.00% and 65.00%.Variable-role accuracy was 90.00% and 80.00%, respectively.Source: C. RQ3: Manual Semantic Comprehension · p. 7, Table VIII · p. 7
- Manual accuracy declined from 100.00% on Low-complexity functions to 75.00% on High-complexity functions for DeepSeek-Coder-V2, and from 90.00% to 60.00% for CodeLlama-7b-Instruct-hf.The pattern shows that complexity-related failure extends beyond exact-match output evaluation to semantic comprehension.Source: C. RQ3: Manual Semantic Comprehension · p. 7
D. Statistical Significance of Complexity Effects
Joint regression and manual-task testing provide statistical evidence of complexity-related associations, while the results do not identify a single dominant metric. Agreement between manual scorers was strong.
D. Statistical Significance of Complexity Effects
- For both models, all four complexity coefficients were negative and statistically significant in the joint logistic regression for automatic prediction correctness.For DeepSeek-Coder-V2, odds ratios were 0.66 for a one-unit increase in cyclomatic complexity and 0.76 for a 100-unit increase in Halstead volume.Source: D. Statistical Significance of… · p. 7, Table XI · p. 8
- The regression, descriptive comparisons, and correlations support broadly comparable negative associations across the four metrics, not a statistically stronger single predictor.Confidence intervals overlapped substantially, and the correlation coefficients spanned a narrow range.Source: D. Statistical Significance of… · p. 7
- Complexity band was significantly associated with manual correctness for DeepSeek-Coder-V2, χ2(2) = 6.15, p = 0.046; CodeLlama-7b-Instruct-hf’s association did not reach the conventional threshold, p = 0.074.The manual sample contained only 20 functions per complexity band.Source: D. Statistical Significance of… · p. 8, Table XII · p. 8
- Independent scoring of the manual-response subset showed strong inter-rater agreement, with Cohen’s κ = 0.86.The paper reports this as support for the reliability of the manual correctness labels.Source: D. Statistical Significance of… · p. 8
VI. DISCUSSION AND THREATS TO VALIDITY
Benchmark composition affects how code-comprehension accuracy should be interpreted, and multiple complexity measures capture related reasoning demands. Automatic prediction declined more sharply with complexity than manual comprehension, while both tasks showed degradation.
VI. DISCUSSION AND THREATS TO VALIDITY
- Benchmarks with only Low- and Medium-complexity functions produced higher accuracy, whereas those containing most High-complexity functions exposed lower reliability.Benchmark-score differences may reflect the structural-complexity distribution of evaluated code as well as model capability.Source: §VI · p. 8
- Cyclomatic complexity, nesting depth, branching factor, and Halstead volume were all negatively associated with correctness, but the results did not establish one dominant measure.The metrics represent execution-path diversity, hierarchical control flow, decision density, and symbolic processing load, respectively.Source: §VI · p. 8
- Automatic input-output prediction showed a larger Low-to-High accuracy decline than manual semantic comprehension.Exact prediction requires tracking a specific execution path and intermediate states; manual questions may sometimes be answered through recognition of an overall algorithmic pattern.Source: §VI · p. 8
- Structural metrics could help identify functions for additional execution, testing, warnings, or human review before accepting model output.The paper suggests this as a lightweight complexity-aware verification approach for LLM-assisted software engineering.Source: §VI · p. 8
- The evaluation covers Python functions and two code-oriented models under zero-shot deterministic prompting; results may differ with other languages, models, prompts, or tool use.The three complexity bands also do not capture semantic factors such as unfamiliar APIs, recursion, or domain-specific logic.Source: §VI · pp. 8–9
VII. CONCLUSION
The evaluation finds that both models become less accurate as structural complexity increases, with the same degradation pattern in manual semantic comprehension. Complexity-aware evaluation and reporting provide a more diagnostic view of reliability than aggregate accuracy alone.
VII. CONCLUSION
- DeepSeek-Coder-V2 accuracy fell from 93.52% on Low-complexity functions to 52.78% on High-complexity functions, while CodeLlama-7b-Instruct-hf fell from 87.04% to 47.22%.These results are from the automatic input-output prediction evaluation.Source: §VII · p. 9
- Incorrect predictions were associated with higher values of all four complexity metrics, while overlapping effect estimates and confidence intervals support treating the metrics as complementary risk indicators, not a strict predictor ranking.Correlation and multivariate logistic-regression analyses also found negative associations between structural complexity and correctness.Source: §VII · p. 9
- Manual semantic comprehension showed the same Low-to-High complexity decline, with models performing best on purpose questions and worst on edge-case questions.The pattern spans exact execution reasoning and higher-level semantic understanding.Source: §VII · p. 9
- Report complexity distributions alongside aggregate accuracy, and verify predictions, explanations, and review suggestions more carefully for code with deep nesting, many execution paths, dense branching, or high symbolic complexity.Future work should extend evaluation to other languages, larger model families, repository-level code, and tool-assisted comprehension.Source: §VII · p. 9