LLMs rewrote already-optimal code in all 45 trials; one prompt line halved the failure

An unimprovable function, rewritten anyway

A developer writing on dev.to describes an experiment run after reading a new paper: they took a two-pointer sweep over a sorted list — linear time, one pass over the data, already benchmarked — and asked Claude, GPT and Gemini to optimize it for execution speed. All three complied. One rewrite swapped the loop for a comprehension, which the author measured to be slower. Another added an early return that could never fire. A third replaced the function with a dictionary plus a second pass, still O(n) but doing the work twice, annotated with a comment about reducing redundant comparisons that was simply false.

The study behind the experiment

The post points to "Efficiency Hallucination: Formalizing and Measuring Behavioral Calibration in LLM-Based Code Optimization," a paper by Sarah Wilson, Gail Kaiser and Patrick Musau posted to arXiv on 13 September. According to the post's summary, the Columbia researchers selected five problems from EffiBench, paired each top-percentile human solution — code already at its performance ceiling — with a deliberately degraded version, and asked nine models across the Claude, GPT and Gemini families to optimize both.

Under a plain prompt, the edit rate on already-optimal code was 100%: 45 of 45 trials, zero abstentions. Every model rewrote code that could not be improved and asserted an improvement. The paper names the cause the Evaluation Trap: the benchmarks models are trained and scored on reward producing an edit and never reward declining to edit, which the post glosses as a classification problem whose negative class was never supplied.

One prompt line cut the failure roughly in half

The paper's intervention is a single sentence: only suggest an edit when more than 90% confident it improves execution speed, otherwise output ALREADY_OPTIMAL. With that added, correct abstention on optimal code rose from 0% to 44.4%, and the over-edit rate fell from 100% to 55.6%. On the genuinely slow versions, the edit rate stayed at 100% with no false abstentions across all nine models — the instruction removed bad edits without suppressing good ones.

The post explains the effect through an asymmetry: suboptimal code can often justify high confidence through complexity analysis alone, while optimal code offers no static proof, so a model with any honesty about its own confidence falls below the threshold. The remaining over-edits are models claiming confidence they do not hold. The authors' real fix, the post notes, is execution — run both versions and compare timings, so the model's opinion of its own work counts for nothing.

Cheaper models said no more often

Within the GPT and Gemini families, the lighter model abstained correctly more often than its larger sibling. GPT-5.4 Mini was the only model in the study to abstain on all five problems, while full GPT-5.4 managed one. Gemini 3 Flash Preview reached 60% correct abstention against 20% for Gemini 3.1 Pro Preview — although Gemini 3.5 Flash scored zero, so it is not a clean rule. Claude's three models clustered at 60, 40 and 60 percent with no inversion. The authors call this the Capability-Calibration Inversion but, as the post emphasizes, five trials per model leaves the confidence intervals wide.

Dense code is the trigger

The per-problem spread was large. On "Remove Duplicates from Sorted Array II," eight of nine models correctly abstained. On "Finding 3-Digit Even Numbers," one of nine did, even though that solution is a fixed iteration over a thousand values with a Counter — constant time and unbeatable. The post's reading is that surface complexity, not actual complexity, invites rewrites: nested comprehensions and terse lines read as improvable. Backtracking structures are the other reliable trigger, since they invite pruning suggestions a model cannot rule out without running the code. The paper's practical advice is to flag syntactically dense functions for human review before an optimization agent touches them — and the author notes their own mangled function had a compound loop condition and one terse arithmetic line.

Why it matters

This is a concrete, reproducible hallucination mode for AI-assisted coding: agents confidently rewrite code that cannot be improved, sometimes making it slower, and attach plausible justifications a tired reviewer will take on faith. The mitigations are cheap. The post's author now keeps an abstention clause in the instruction file of every repo where agents may propose performance changes, paired with a rule that no change may be described as faster unless both versions have been run. Measurement stays out of the model's hands: a roughly twenty-line pytest-benchmark fixture in CI, with the old implementation pinned as baseline, catches all three of the Sunday rewrites. The broader lesson is that capability and calibration are separate skills, and the benchmark numbers usually quoted measure only the first — sometimes with the stronger model proving the worse judge of when there is nothing left to do.