CS Paper Radar

The Complexity Kink: A Prompt-Side Structural Complexity Index for Code-Generation Reliability

Michael Hernandez, Tian Zhao

cs.LG cs.SE ·submitted 2026-09-17 03:07 UTC · v4
top venuebenchmarkcode/data

Abstract

Measuring complexity from a model's own code is biased by failure: a hard prompt can produce a short, broken program that looks simple. We instead score each prompt's structure on six dimensions from the prompt alone, never from generated code or test results. We draw 5,000 Python prompts across six bands of a preliminary single-rater score, and four out-of-panel LLM judges rescore every prompt (composite ICC(2,1) = 0.872). Twenty-one models answer every prompt (105,000 generations), and an independent LLM auditor, checked against known-answer cases, reviews each unit-test verdict. Averaged over models, pass rate has a nonmonotone breakpoint at composite 14.0: 83.4% at or below, 90.1% above. That jump is not a law of difficulty: with task-type fixed effects the breakpoint stays at 14.0 but the adjusted jump shrinks from 6.8 to 0.4 points, and neither of the benchmark's two prompt sources reproduces it on its own. Nineteen models pass more often above their own breakpoint and two less often; one of those declines comes from API calls that returned nothing. In post hoc follow-up, Kimi K2.5 shows the clearest decline, at 14.25, under a prompt-source control and within the later source alone. Among failed generations with measurable output complexity, 25.0% pair a prompt composite above 8 with output complexity of at most 10, twice the share among passing ones. The pooled breakpoint moves to 11.25 on raw test outcomes. Human agreement with the index is moderate, paraphrase and cross-language rescoring preserve its ordering, and overidentification tests reject the six dimensions as instruments, so we make no causal claim. The contribution is a prompt-side way to locate where each model's pass rate changes and to test how much that depends on the prompt mix and on how success is scored.

Comment
Accepted at NeurIPS 2026 (Evaluations and Datasets Track). 24 pages, 6 figures. Code: https://github.com/uwm-se/ComplexityKink ; data: https://huggingface.co/datasets/uwm-software-engineering/complexity-kink-research

Closest papers

Nearest neighbours by meaning across the whole index.

How Specification Explicitness Shapes Failure in LLM-Generated Code

cs.SE cs.AI ·2026-11-15 ·Elmira Onagh, Maleknaz Nayebi
top venue similarity 0.63
Abstract · Accepted to ICSE 2026

When LLMs turn requirements into code, every underspecified constraint becomes behavior that the model must decide during generation. We test when specifications move beyond structure and begin to control generated behavior. In a controlled experiment, 72 participants implemented and revised Python tasks with an LLM under three levels of specification explicitness. The results show a clear break between lightweight structure and explicit behavioral obligations. Lightweight structure reduced hidden-test failures by only 8.7%. Requiring participants to specify constraints, invariants, negative requirements, edge cases, tie-breaking rules, and exception handling cut failures by 47.2% and reduced the number of distinct failure modes by 20.5%. The largest drops were in failure modes tied to implicit obligations. Invariant violations fell by 66.1%, and unsupported assumptions fell by 59.5%. After a requirement change, specifications with explicit behavioral obligations produced regressions in more submissions, but each affected submission lost less previously correct behavior. Explicit specifications also changed how developers judged generated code. Without explicit obligations, participants overestimated generated-code correctness by about 23 percentage points. With explicit obligations, they produced better code but judged it more cautiously. Thus, the lesson is sharper than "better specifications help." Lightweight structure barely helped, while explicit behavioral obligations nearly halved failures, made regressions shallower, and improved calibration.

0.72

Complexity-Aware Evaluation of LLM Comprehension

cs.SE cs.AI ·2026-09-29 ·Ali Mohammadi Esfahani, Nafiseh Kahani, Samuel A. Ajila
benchmark similarity 0.60
Abstract

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.

0.21

Validating the Comparison, Not Just the Scorer: Why Overall Accuracy Can Mislead in Interactive LLM Evaluation

cs.CL cs.AIcs.HC ·2026-10-01 ·Ancil Crayton
published similarity 0.60
Abstract · 14 pages, 2 figures. Accepted to the Trustworthy AI for Good (AI4GOOD) Workshop at NeurIPS 2026

Many LLM studies compare how models respond to different follow-up prompts. For example, one prompt may neutrally ask a model to reconsider, while another insists that an invented film really exists. The difference is used to measure the effect of conversational pressure. An automatic scorer then labels whether each response makes an unsupported factual claim. Researchers commonly validate the scorer with one overall accuracy or $F_1$ score. However, high overall performance can hide prompt-specific mistakes: if the scorer makes more errors after one prompt, the measured difference can be too large, too small, or point in the wrong direction. An audit containing mostly difficult responses can also misrepresent performance in the full study. We derive how such errors alter a prompt comparison and examine the problem using six models, 180 invented-entity questions, and six prompt conditions. In a balanced audit of 288 responses, overall $F_1$ was $.916$. Yet, depending on the prompt, the scorer flagged 2.6%-33.3% of responses that the primary LLM rater judged not to contain an unsupported claim; these prompt-specific estimates were uncertain. In a second audit, the scorer and two separate LLM raters evaluated the same 300 model-question cases under each prompt. An apparent 9.3-point increase from asserting certainty rather than neutrally asking the model to reconsider fell to 2.3 points under both raters. The primary-rater interval included zero, so it did not establish an increase. Two other prompt comparisons kept their direction under both raters, while an attempted prompt-specific correction remained too uncertain for a firm conclusion. Researchers should therefore validate the exact difference they plan to report, not just the scorer as a whole: audit both prompts on matching cases and include scorer and rater uncertainty in the final result.

0.37

Evaluating the effectiveness of class-level LLM-generated test suites in Python

cs.SE ·2026-09-21 ·Bilal Al-Ahmad, M. Harshvardhan, Khaled El-Fakih, Anas AlSobeh
benchmark similarity 0.59
Abstract

Context: Large language models (LLMs) can generate unit tests quickly, but high structural coverage does not establish that those tests execute reliably or detect faults. Existing evidence often treats coverage as the principal outcome and rarely compares prompt strategies and models through mutation testing at class level. Objective: This study examines how prompt strategy and model choice shape the executability, structural coverage, fault-detection effectiveness, and structural quality of LLM-generated Python test suites relative to human-written suites. Method: We evaluate multiple prompt strategies across a diverse set of current LLM configurations on the ClassEval benchmark. The evaluation combines execution outcomes, line and branch coverage, Cosmic Ray mutation scores, and structural quality indicators. Primary analyses treat successful execution as a prerequisite; paired comparisons use only classes shared by the relevant executable subsets. Results: Structural coverage is consistently near its ceiling and offers little discrimination among configurations. Executability varies substantially. The proposed prompt performs strongly for mutation score, but no prompt dominates across models. Model choice explains more variation than prompt choice, and their interaction shows that prompt effectiveness depends on the selected model. Human and LLM suites are evaluated on unequal executable subsets, so their relative mutation scores do not establish superiority. Conclusion: Reliable assessment of LLM-generated tests should treat executability as a gate and combine coverage with mutation testing and structural quality indicators. In practice, model selection should precede prompt tuning.

0.13

PreMaQ: Predicting Maintainability-Related Quality of LLM-Generated Code Before Generation

cs.SE ·2026-10-05 ·Taiki Wakamatsu, Yuta Ishimoto, Masanari Kondo, Yasutaka Kamei
benchmark similarity 0.59
Abstract · 10 pages, 4 figures

As large language models (LLMs) become increasingly capable of code generation, adopting generated code in software development requires assessing not only its functional correctness but also its maintainability-related quality. If such quality could be estimated before generation, developers could avoid the cost of generating, reviewing, and discarding low-quality code. Although prior work has shown that the functional correctness of the LLM-generated code can be predicted in advance, it remains unclear whether maintainability-related quality is similarly predictable. We introduce Pre-Generation Maintainability-Related Quality Prediction (PreMaQ), which predicts the Code Smell Score (CSS) and Maintainability Index (MI) of generated code from the internal representations of LLMs before generation. Our evaluation covers four open-weight LLMs and four Python code generation benchmarks, comprising 2,695 tasks in total. Our results show that predicted CSS and MI consistently correlate with their observed values across all 16 model-benchmark combinations, achieving mean Spearman rank correlations of 0.57 and 0.65, respectively. When used for model selection, PreMaQ achieves 59.5% of the maintainability-related quality improvement attainable by an ideal maintainability-based selector over random selection on tasks for which multiple models generate functionally correct code. Combining predictions from PreMaQ and prompt embeddings increases this proportion to 60.7%, indicating that the two signals are complementary. These findings suggest that PreMaQ can be used to predict and improve the maintainability-related quality of LLM-generated code.

0.20

What Does MMLU Actually Measure? A Psychometric Audit of Difficulty Structure in Aggregate Benchmark Scores

cs.CL ·2026-09-08 ·Dana Paquin, Riddhiman Jain
benchmark similarity 0.58
Abstract · 14 pages

Although MMLU is widely adopted as a benchmark for calibrating general AI capabilities, we psychometrically demonstrate that its aggregate score primarily evaluates a model's factual retrieval capacity rather than its reasoning ability. By calibrating item difficulty for 1,000 open-weights language models over 14,042 MMLU test items using Item Response Theory, we show that evaluating both abilities via a single test is inherently flawed. Difficulty is then regressed on a deterministic, text-extractable framework of structural complexity. Applying a joint Wald test with subject-clustered covariances demonstrates that the MMLU conflates fundamentally separable constructs. The mapping from structural complexity to difficulty is not invariant across the benchmark's STEM and non-STEM partitions. This finding has practical consequences. Aggregate leaderboard ranks track non-STEM accuracy more closely than STEM accuracy, so selecting a Top-50 model on the aggregate for a reasoning-intensive deployment displaces roughly 22% of the STEM-appropriate choices. Furthermore, when controlling for the multiple-choice guessing floor natively inside the response model, we find that higher-ability models continue to degrade more steeply under increased reasoning depth. The MMLU aggregate therefore weights retrieval capacity and reasoning stability unequally, inadvertently favoring models optimized for retrieval. We release our deterministic framework as a reproducible auditing instrument and recommend disaggregated reporting.

0.27

Reviewer Capability Governs Rejection Targeting, Not Repair Skill: Evidence from LLM Execute-Review-Revise Pipelines

cs.SE cs.CLcs.MA ·2026-09-02 ·Faizan Tanveer
code/data similarity 0.58
Abstract · 6 pages, 5 tables. Code and data: https://github.com/faizan-tnvr004/llm-reviewer-capability

Multi-agent LLM pipelines increasingly assign roles, including execution and verification, to models of different capability tiers. This is done because running a flagship model at every stage is expensive. Previous literature has established that verification stages are not always beneficial, but holds reviewer capability roughly fixed relative to the executor. We vary it. We replace the reviewer with models spanning a capability range down to one that cannot solve the problems at all, and measure the outcome of every individual rejection. This is done across a constant set of 100 olympiad mathematics problems. A cross-family mid-tier reviewer improves final accuracy by 12 percentage points, from 52 to 64 percent (p = 0.0005), with zero damaged answers. Same-model self-review attains the highest error-detection rate of any condition (0.85 recall) yet yields no significant gain: it rejects 2.1 times as often for a third the repair rate (15 against 43 percent, p = 0.0074) and falsely rejects 35 percent of its own correct answers against 2 percent for the cross-family reviewer (paired p = 0.000015). The low damage rate of self-review proves to be an artifact of revision inertia rather than reviewer quality: of 18 falsely rejected correct answers, the three where the executor complied all became wrong, while the fifteen it ignored survived unchanged. Below a capability floor the role becomes inert: our weakest reviewer changed zero of 100 final answers while doubling token cost. These findings describe a single executor-reviewer configuration on 100 problems and should be read as a controlled pilot rather than a general claim about verification stages.

0.66

Causal Syntax Circuits in CodeLMs: Budget and Probe Decide What Looks Localised

cs.LG cs.SE ·2026-10-14 ·Harsh Kumar, Tanmay Shailesh Joshi, Rahul Maity, Anusa Saha
published similarity 0.58
Abstract · Accepted at the NeurIPS 2026 Workshop on Linguistic Principles for Foundation Models (LP4FM). All four authors contributed equally

Code models write Python when the prompt does not say which language to use. We ask a mechanistic question about that habit: is it produced by a small, findable group of components inside the model? We run one pipeline---mean ablation, activation patching, greedy circuit extraction, a random-control significance test, and activation steering---over 55 model-language settings spanning ten open code models (five base and five instruction-tuned), three target languages (Rust, C#, PHP), two prompt suites, and two component budgets. We report five findings. First, the preference is large, grows with model size, and survives instruction tuning: it is larger on every instruction-tuned checkpoint than on its base version, by 12% on average. Second, its measured size is mostly a property of the probe; replacing our aligned prompts with XLCoST parallel functions takes the same measurement on the same models from about 1.6 to about 0.01. Third, whether the preference looks localised depends on how many components the search may keep: with a budget of 12, 1 of 15 settings yields a circuit that beats size-matched random controls after multiple-comparison correction, and with a budget of 40, 6 of 15 do. Fourth, interventions that a smaller-budget study reports as uniformly failing do sometimes succeed: patching makes a Python prompt prefer target syntax in 2 of 45 settings, and steering changes the most likely next token in 9 of 45. Fifth, every circuit whose effect is significant but points away from the target language comes from a setting where circuit extraction failed, which makes such results a diagnostic rather than a phenomenon. The practical lesson is that a claim about whether a behaviour is localised can turn on analysis choices that papers rarely report. We release the full grid so those choices can be varied.

0.24