PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficiency Hallucination: Formalizing and Measuring Behavioral Calibration in LLM-Based Code Optimization

Sarah Wilson, Gail Kaiser, Patrick Musau

arXiv:2609.14839v1cs.SEcs.AI

TL;DR

LLMs can make plausible, unsupported performance claims when editing already-optimal code, while binary benchmark incentives do not penalize such claims. The paper formalizes this calibration problem and evaluates an IIV-derived penalty approach, finding increased abstention on optimal code while preserving edits on sub-optimal code.

  • Problem

    Binary optimization benchmarks reward correctness and runtime but do not penalize unsupported speedup claims, while edits to already-optimal code can pass tests without improving performance.

    Source: §I · p. 1

  • Method

    The paper formalizes four optimization-response outcomes and evaluates an IIV-derived penalty approach for measuring behavioral calibration across optimal and sub-optimal code.

    Source: §I · p. 1, B. Behavioral Calibration: Taxonomy · pp. 2–3

  • Results

    The penalty raises optimal-code abstention from 0% to 44.4% and lowers over-edit from 100% to 55.6%, while sub-optimal-code edit rate remains 100% and False Abstention Rate is 0.0%.

    Source: C. Result II: Behavioral Calibration… · p. 3

  • Takeaways & Limitations

    The findings frame over-editing at performance ceilings as a predictable consequence of benchmark incentives rather than simply a correctable model bug.

    Source: §VII · p. 6

    This pilot has limited statistical power per model (n = 5), focuses on algorithmic problems rather than repo-scale software, and leaves transfer to cross-file systems open.

    Source: §VI · p. 5

Abstract

from arXiv · show

The integration of Large Language Models (LLMs) into automated code optimization introduces a critical reliability risk we term the Efficiency Hallucination: an LLM's tendency to issue non-functional mutations with unsubstantiated performance claims on already-optimized code. This is driven by the Evaluation Trap, wherein binary benchmarks incentivize unnecessary modifications over safely abstaining. We present a validation framework using classification penalty methods, evaluated across 180 optimization runs on nine models (GPT, Claude, Gemini) using EffiBench. Under standard prompts, models exhibit a 100% over-edit rate on optimal code. Our guardrail raises correct abstention from 0% to to 44.4%, preserving a 100% edit rate on sub-optimal code with zero false abstentions. Calibration is uneven: GPT-5.4 Mini approaches near-perfect abstention, and simple code is recognized more reliably than complex code. Our framework offers a training-free mechanism to mitigate LLM overconfidence before deployment in production.

I. INTRODUCTION

LLMs can propose plausible edits to already-optimal code while making unsupported performance claims, a failure that ordinary tests may miss. The paper frames this risk within benchmark incentives and prior work on code optimization and evaluation.

I. INTRODUCTION

  • On already-optimal code, LLMs can make plausible edits with confident, unverifiable performance claims that compile and pass tests without improving performance.Such edits can escape per-commit tests and cost review time while eroding trust in automated tooling.Source: §I · p. 1
  • Binary benchmarks reward functional correctness and runtime but do not penalize unsupported speedup claims, making a plausible bluff a zero-risk gamble at the performance ceiling.The paper calls this incentive structure the Evaluation Trap.Source: §I · p. 1
  • The paper defines Efficiency Hallucinations, applies the IIV framework, proposes Optimal Baseline evaluation of behavioral calibration, and reports a 180-trial study across nine models.The study examines variation by model, family, and problem.Source: §I · p. 1

A. LLM-Based Code Optimization

  • Optimization research includes specialization methods such as LLaMoCo and PerfRL, which address optimization errors or improve speedup performance and motivate studying behavioral calibration.The paper asks whether specialization also improves calibration.Source: A. LLM-Based Code Optimization · p. 2
  • Agentic search expands optimization capability, while existing evaluations of improvable code alone cannot expose whether systems over-edit already-optimal code.The paper situates its work among architectural specialization, agentic search, and evaluation and benchmarking.Source: A. LLM-Based Code Optimization · p. 2

B. LLM Hallucination in Code

The paper distinguishes Efficiency Hallucination from other code hallucinations and relates the problem to error amplification in text generation. It focuses on efficiency misrepresentation when models claim improvements unsupported by their code.

B. LLM Hallucination in Code

  • Unlike retrieval-based grounding for repository-level hallucinations, this work targets models that understand code but fabricate optimization improvements.The paper identifies this as a distinct failure mode.Source: B. LLM Hallucination in Code · p. 2
  • CodeMirage identifies efficiency misrepresentation—claiming superior complexity while producing sub-optimal code—as the hallucination subtype most directly related to this work.Repository-level hallucinations can also involve cross-file dependency neglect, stale documentation, or over-generalization.Source: B. LLM Hallucination in Code · p. 2
  • The IIV framework states that a misclassification rate of ϵ implies a generative error rate of at least 2ϵ, framing Efficiency Hallucinations as predictable under its assumptions.The passage identifies optimization micro-patterns appearing only once in training as especially difficult to distinguish from statistical noise.Source: B. LLM Hallucination in Code · p. 2

A. The Evaluation Trap and IIV Formalization

The formalization treats optimization as a binary classification problem and distinguishes correct outcomes from two kinds of error. It defines calibration through whether models edit improvable code and abstain on code at its performance ceiling.

A. The Evaluation Trap and IIV Formalization

B. Behavioral Calibration: Taxonomy

  • The taxonomy distinguishes performance-ceiling code C from genuinely sub-optimal code S, with editing S and abstaining on C as the two correct outcomes.Editing S is a true positive; signaling that C is already optimal is a true negative.Source: B. Behavioral Calibration: Taxonomy · p. 2
  • Modifying C is an Over-Edit (false positive) and an Efficiency Hallucination, while declining to improve S is a False Abstention (false negative).The taxonomy calls false abstention a pathological refusal.Source: B. Behavioral Calibration: Taxonomy · p. 2
  • Perfect calibration requires an edit rate of 1.0 on S and an abstention rate of 1.0 on C, making both Bluff Rate and False Abstention Rate zero.Bluff Rate measures over-edit frequency on optimal code; False Abstention Rate measures abstention frequency on sub-optimal code.Source: B. Behavioral Calibration: Taxonomy · p. 3

C. The Optimal Baseline Strategy

The Optimal Baseline tests top-percentile solutions alongside improvable code to separate abstention behavior from optimization capability. The study applies an IIV-derived confidence-threshold prompt across paired problems, models, and prompt conditions.

C. The Optimal Baseline Strategy

  • The Optimal Baseline adds top-percentile human solutions to evaluation, isolating Bluff Rate from optimization capability.Standard benchmarks test agents only on improvable code.Source: C. The Optimal Baseline Strategy · p. 3
  • The IIV-derived Penalty Prompt requires more than 90% confidence before suggesting an edit; complexity analysis can support that threshold on improvable code, unlike already-optimal code.The prompt otherwise instructs the model to output ALREADY_OPTIMAL.Source: C. The Optimal Baseline Strategy · p. 3
  • Comparing standard prompts with the penalty condition measures whether calibrated abstention is possible and whether it degrades optimization on improvable code.The explicit threshold adds an inference-time cost for the Error class that current benchmarks omit.Source: C. The Optimal Baseline Strategy · p. 3

A. Experimental Setup

  • The pilot spans 180 trials across five paired EffiBench problems, nine models from three families, and control and penalty conditions.Each problem pair contains an EffiBench top-percentile optimal solution and a functionally correct, algorithmically degraded variant; models were evaluated directly via API.Source: A. Experimental Setup · p. 3

B. Result I: The Evaluation Trap Confirmed

Under the control prompt, models edited already-optimal code in every trial, confirming that without a penalty they did not recognize the performance ceiling. They also edited sub-optimal code in every trial.

B. Result I: The Evaluation Trap Confirmed

  • 100% of control-condition trials modified already-optimal code, with zero abstentions.The edits could not improve execution speed by construction.Source: B. Result I: The Evaluation Trap… · p. 3
  • The control-condition edit rate on sub-optimal code was also 100%.The authors interpret this as uniformly high baseline optimization capability.Source: B. Result I: The Evaluation Trap… · p. 3
  • 100% Bluff Rate confirms that no tested model recognized optimal code absent an explicit penalty.The paper identifies this as the Evaluation Trap and says it validates the IIV prediction that bluffing dominates at the performance ceiling.Source: B. Result I: The Evaluation Trap… · p. 3

C. Result II: Behavioral Calibration under IIV Penalty

With the IIV penalty, correct abstention on optimal code increased while editing on sub-optimal code was preserved. The penalty did not eliminate over-editing, which the authors link to unreliable confidence self-assessment.

C. Result II: Behavioral Calibration under IIV Penalty

  • 44.4% abstention on optimal code under penalty, up from 0%, while the over-edit rate fell from 100% to 55.6%.Under the same condition, the edit rate on sub-optimal code remained 100%, and the False Abstention Rate was 0.0% across models.Source: C. Result II: Behavioral Calibration… · p. 3
  • All models achieved 5/5 correct edits on sub-optimal snippets; separately, the cited table concerns calibrated abstention on optimal code under IIV penalty.The caption specifies n = 5 per model and N = 180.Source: C. Result II: Behavioral Calibration… · p. 4, Table II · p. 4
  • Calibration and capability were behaviorally independent: the penalty reduced over-editing without reducing the 100% edit rate on sub-optimal code.The authors distinguish the penalty's effect on optimal-code edits from its preserved editing performance on sub-optimal code.Source: C. Result II: Behavioral Calibration… · pp. 3–4
  • A 55.6% Bluff Rate persisted because the >90% confidence threshold changes the decision rule, not the model's underlying calibration.The authors describe self-assessed confidence as the unreliable judgment and identify external runtime verification as the definitive solution.Source: C. Result II: Behavioral Calibration… · p. 4

D. Result III: Cross-Family and Within-Family Variation

Calibration under penalty varied substantially across model families and individual models, with GPT-5.4-mini reaching perfect abstention while larger variants in GPT and Gemini showed lower rates. Qualitative examples include confident optimization claims about nonexistent bottlenecks and deliberative abstention reasoning.

D. Result III: Cross-Family and Within-Family Variation

  • 53% (8 of 15 trials) for Claude and GPT, versus 27% (4 of 15) for Gemini, were family-level abstention rates under penalty.Aggregate family averages mask substantial within-family heterogeneity.Source: D. Result III: Cross-Family and… · p. 4
  • GPT-5.4-mini reached 100% (5/5) abstention, while GPT-5-mini and GPT-5.4 reached 40% and 20%, respectively.It was the only model in the study to achieve perfect calibration.Source: D. Result III: Cross-Family and… · p. 4
  • GPT-5.4-Mini (100%) exceeded GPT-5.4 (20%) by 80 percentage points; Gemini-3 Flash Preview (60%) exceeded Gemini-3.1 Pro Preview (20%).The authors call this Capability-Calibration Inversion and note the implication for localized or block-level optimization pipelines.Source: D. Result III: Cross-Family and… · p. 4
  • Claude’s Opus 4.8 (40%) and Sonnet 4.5 (60%) show a weaker version of the capability-focused-training pattern described by the authors.The authors say Claude’s tighter cluster suggests uniform constraints attenuate the effect.Source: D. Result III: Cross-Family and… · p. 4
  • Gemini-3.5 Flash diagnosed an O(N) list-slicing bottleneck in already-optimal O(N) code, though the original never sliced the list.It proposed an iterator rewrite as “extremely minimal and fast,” but whether the rewrite was faster was never measured.Source: D. Result III: Cross-Family and… · p. 4
  • Claude responses sometimes verified candidate micro-optimizations before abstaining, while residual over-edits persisted across all families.The authors describe this as a deliberative, auditable reasoning chain and suggest RLHF-driven actionability biases are only partially suppressed by inference-time constraints.Source: D. Result III: Cross-Family and… · p. 4

E. Result IV: Per-Problem Calibration Difficulty

Calibration on optimal code varies substantially by benchmark problem: models abstain most often on a simple two-pointer task and least often on a problem whose code surface appears complex. The results identify problem-level variation, not just model-level variation.

E. Result IV: Per-Problem Calibration Difficulty

  • 8/9 models abstained on the O(n) two-pointer Remove Duplicates task, while only 1/9 abstained on Finding 3-Digit Even Numbers.The latter had the highest Bluff Rate despite its O(1000) counter solution; nested comprehensions and Counter objects made its surface appear improvable.Source: E. Result IV: Per-Problem Calibration… · pp. 4–5
  • Abstention rates ranged from 89% to 11%, with Is Same Tree at 56%, Min Operations at 44%, and Combination Sum II at 22%.The paper attributes tractability to Is Same Tree’s short recursive structure, and says Min Operations benefited from CoT verification of bit-level invariants; Combination Sum II’s backtracking invited spurious pruning suggestions.Source: E. Result IV: Per-Problem Calibration… · pp. 4–5
  • 89% of models abstained on Remove Duplicates from Sorted Array II, versus 11% on Finding 3-Digit Even Numbers.The table reports correct abstentions out of nine models per problem.Source: E. Result IV: Per-Problem Calibration… · pp. 4–5, Table III · p. 5

V. DISCUSSION

The discussion characterizes behavioral calibration as a reliability dimension distinct from optimization capability. Correct abstention matters because efficiency hallucinations can pass ordinary functional checks.

V. DISCUSSION

  • Behavioral Calibration is an orthogonal reliability property, distinct from optimization capability.Across models and sub-optimal problems, the False Abstention Rate was zero, showing the penalty constraint did not inhibit correct optimizations.Source: A. Calibration as an Orthogonal… · p. 5
  • The penalty constraint produced zero False Abstention Rate across models and sub-optimal problems.The result indicates that correct edits were preserved even as the framework sought to improve abstention on optimal code.Source: A. Calibration as an Orthogonal… · p. 5
  • Efficiency hallucinations can evade standard suites because code may pass functional tests while claiming a speedup without improving performance.The discussion presents Behavioral Calibration as a reliability dimension current benchmarks do not capture.Source: A. Calibration as an Orthogonal… · p. 5

B. The Calibration Pareto Frontier

At the 90% IIV penalty threshold, the results locate a non-trivial abstention point with no false abstentions, while leaving a substantial residual Bluff Rate. The authors propose deployment guidance and identify validity boundaries for the pilot.

B. The Calibration Pareto Frontier

  • 44.4% aggregate abstention on optimal code leaves a 55.6% over-edit rate, while false abstentions remain at 0%.The paper describes the 90% threshold as a navigable point on the calibration frontier; lower thresholds are expected to raise false abstentions, while higher thresholds may return behavior toward the 100% over-edit control state.Source: B. The Calibration Pareto Frontier · p. 5

C. Practical Deployment Guidance

  • The authors recommend the IIV penalty prompt as a zero-overhead guardrail, lighter models for isolated function-level tasks, and human review of syntactically complex code.In this study, the prompt dropped over-edit rate by 55.6% with zero false abstentions; the guidance also reflects the reported capability-calibration inversion and elevated Bluff Rates on complex code.Source: C. Practical Deployment Guidance · p. 5

VI. LIMITATIONS

  • The internal-validity results may be affected by model memorization of familiar optimal solutions or Gemini recognizing its own generated sub-optimal snippets.Both possible confounds would increase edit rates and lower false abstentions, making the zero false-abstention result a conservative bound.Source: §VI · p. 5
  • The pilot has limited statistical power per model (n = 5) and tests algorithmic problems rather than repo-scale software; transfer to cross-file systems remains open.The authors describe the study as establishing directional validity and a foundational case study.Source: §VI · p. 5
  • The Optimal Baseline assumes EffiBench top-percentile solutions are performance ceilings, though some may admit further source-level micro-optimizations.Compiler and runtime optimizations may also widen the gap between source-level and execution-level performance; if any optimal snippet was improvable, the 55.6% Bluff Rate is an upper bound.Source: §VI · p. 5

VII. CONCLUSION AND FUTURE WORK

The conclusion frames Efficiency Hallucination as a calibration failure associated with binary benchmark incentives and reports gains from an IIV penalty prompt. Future work targets broader execution-based evaluation, calibration-frontier mapping, and deployment contexts.

VII. CONCLUSION AND FUTURE WORK

  • The pilot found a 100% Bluff Rate under control, 44.4% abstention on optimal code with the IIV penalty, and 100% edits on sub-optimal code with 0% false abstentions.The conclusion also identifies within-family calibration variation, capability-calibration inversion, and surface complexity as a risk factor.Source: §VII · p. 6
  • The authors propose scaling execution-based verification to all 1,000 EffiBench problems and testing transfer to production software and open-source repositories.Examples include SWE-Perf performance pull requests, Abseil, and RocksDB.Source: §VII · p. 6
  • Future work should vary the IIV penalty threshold to map the Pareto frontier between Bluff Rate and False Abstention Rate.The authors suggest that the optimal threshold should reflect code criticality, such as whether a path is high-frequency and latency-sensitive.Source: §VII · p. 6
  • The authors propose integrating execution-based performance verification as a blocking criterion in rubric-based benchmarks.They frame the IIV penalty as an optimization-specific instance of the broader binary-verifier problem described by FrontierCode.Source: §VII · p. 6
  • RAUQ-style uncertainty signals are proposed as feedback for agentic optimization loops, potentially triggering higher confidence thresholds or human review.The authors present this as a longer-term alternative to static prompt engineering.Source: §VII · p. 6
Loading 2609.14839v1…