Efficiency Hallucination: Every Model Rewrote Code That Couldn't Get Faster

A Columbia University study published on arXiv in September reveals a phenomenon known as "Efficiency Hallucination" in large language models (LLMs) when asked to optimize code. Researchers Sarah Wilson, Gail Kaiser, and Patrick Musau tested nine models from Claude, GPT, and Gemini families on five problems from EffiBench. They paired the top-performing human solutions with deliberately degraded versions and asked the models to optimize both.

Under a standard prompt, all nine models rewrote the already optimal code without fail. The researchers dubbed this behavior "the Evaluation Trap," as every benchmark a model has been trained on rewards producing an edit, even if it's unnecessary. To combat this, the authors introduced a simple intervention: instruct the models to only suggest an edit if they are 90% confident it improves execution speed; otherwise, they should output "ALREADY_OPTIMAL."

This resulted in a significant decrease in over-editing on optimal code, from 100% to 55.6%. However, the models still overestimated their confidence level, reporting 90% even when they were unsure, which is a common overconfidence problem. The researchers note that the true solution lies in actual performance testing rather than just code optimization.

They also found a "Capability-Calibration Inversion," where better-performing models were often worse at recognizing when no optimization is needed. The study highlights the importance of evaluating not just the models' ability to optimize code but also their calibration in determining when a code snippet is already optimal.