PaperlayerView exact revision on arXiv

Source-linked AI summary

Refusing the Impossible: A Taxonomy and Benchmark for Code Hallucination in Large Language Models

Vishnu Asutosh Dasu, Ashish Kundu, Gang Tan

arXiv:2609.03267v1cs.SE

TL;DR

Code hallucinations are ungrounded generation, distinct from bugs in grounded code, yet prior code-quality evaluation does not capture all failures. The paper proposes a taxonomy and tests refusal on deliberately unsatisfiable prompts; across models, ungrounded code is more common than refusal.

  • Problem

    Code hallucinations are ungrounded generation, distinct from ordinary bugs, but existing code-quality measures and prior work do not cleanly separate grounded errors from hallucinations.

    Source: §1 · p. 2

  • Method

    The paper defines a three-dimensional taxonomy and evaluates responses to unsatisfiable prompts alongside matched solvable controls.

    Source: §1 · p. 2, §4 · p. 5

  • Results

    HR was 0.60 and RR was 0.27 across models on adversarial prompts.

    Source: §5.2 · p. 5

  • Takeaways & Limitations

    The findings indicate that ecosystem fabrications can be checked against live package registries, a check that substantially reduces package hallucinations [15].

    Source: §7 · p. 9

    The suite covers a non-exhaustive set of impossibilities and adversarial behaviors.

    Source: §6 · p. 9

Abstract

from arXiv · show

Large language models (LLMs) often produce code that looks plausible but is not grounded in reality. The code may import packages that do not exist or claim to implement algorithms that violate proven theorems, while still compiling and running. We study \emph{code hallucination} as \emph{ungrounded generation} and separate it from ordinary \emph{code error} (bugs in otherwise grounded programs). We propose a taxonomy with three dimensions: \textbf{groundedness} (absolute violations of universal truths vs.\ relative fabrications of contingent or ecosystem-specific facts), \textbf{manifestation level} (syntactic, semantic, or factual), and \textbf{behavior} (from confident fabrication to degenerate output), organized into a severity ordering. We build an \textbf{adversarial} suite of deliberately unsatisfiable tasks where the correct response is to refuse and categorize the responses under our taxonomy. The suite contains \textbf{270 prompts} across six languages and 24 subcategories, paired with \textbf{91 matched solvable controls}, and responses are judged by a two-tier protocol validated against human labels (82\% agreement, $\kappa{=}0.73$). Across twelve open-weight code and reasoning models (4{,}332 judged responses), models produce ungrounded code on about 60\% of unsatisfiable prompts and refuse only 27\%, while wrongly refusing 0\% of the solvable controls.

1 Introduction

The paper distinguishes ungrounded code hallucinations from ordinary bugs and asks whether models can recognize and refuse impossible tasks. It proposes a taxonomy and evaluates responses to deliberately unsatisfiable prompts.

1 Introduction

  • Execution-based benchmarks and real-world issue resolution are common code-quality measures, but some failures go beyond ordinary bugs.The paper identifies fabricated entities and impossible claims as distinct from conventional implementation errors.Source: §1 · pp. 1–2
  • Earlier efforts characterize, induce, or measure code hallucinations; this paper focuses on a principled taxonomy and testing refusal of impossible tasks.Prior ecosystem-scale measurements found that roughly 5% of packages recommended by commercial models and 22% from open-weight models did not exist [15].Source: §1 · p. 1
  • The taxonomy separates code hallucination—ungrounded generation—from code error, a bug in an otherwise grounded program.The paper argues that the two failure types call for different fixes: testing and static analysis for errors, and recognizing what exists and is possible for hallucinations.Source: §1 · p. 2
  • Models are evaluated on two regimes: solvable natural tasks, where code can be grounded but buggy, and unsatisfiable adversarial tasks, where they should refuse or flag impossibility.Adversarial prompts include fictional algorithms, nonexistent APIs, violated impossibility theorems, and contradictory constraints.Source: §1 · p. 2
  • The contributions are a groundedness boundary, a three-dimensional taxonomy with severity ordering, and an evaluation of twelve open-weight models with five reported findings.Those findings concern refusal patterns, model capability, recognition versus action, prompt phrasing, and prompt-level variation.Source: §1 · p. 2

2 Defining Code Hallucination

The paper defines hallucination as ungrounded generation, distinct from bugs in grounded programs, and offers a debugger-based test for drawing that boundary. It notes that hallucinations can look executable and identifies boundary cases that resist clean classification.

2 Defining Code Hallucination

  • A code error is a defect in a grounded program; a code hallucination introduces entities, properties, or facts that do not exist or cannot hold.Examples include an off-by-one implementation bug versus a nonexistent API or an algorithm claim that contradicts established theorems.Source: §2 · p. 2
  • The debugger criterion asks whether a perfect debugger could fix the output without changing its intended grounding: if not, it is likely a hallucination.Fixing an off-by-one quicksort bug preserves grounding; replacing a nonexistent import or retracting an impossible algorithm claim does not.Source: §2 · p. 2
  • Intent misuse is classified as error when an existing API could plausibly satisfy the requirement, but as hallucination when behavior or guarantees are falsely claimed.The paper also treats unacknowledged task changes as behavior B3 and discusses these cases further in Appendix B.1.Source: §2 · p. 2
  • Hallucinations may compile, run, and pass simple tests while remaining ungrounded, so execution success alone can miss them.Standard pass@k evaluation cannot detect silently substituted algorithms, plausible but wrong domain constants, or ignored constraints presented as satisfied.Source: §2 · pp. 2–3
  • Figure 1 separates errors from hallucinations, then organizes hallucinations into absolute and relative classes with manifestation and behavior as orthogonal axes.Absolute and relative classes are numbered A1–A4 and R1–R5, respectively.Source: Figure 1 · p. 3

3 A Multi-Dimensional Taxonomy

The taxonomy labels responses first as correct, error, or hallucination, then assigns hallucinations labels for groundedness, manifestation, and behavior. It also orders hallucinations by severity and reports that cascades between types are rare.

3 A Multi-Dimensional Taxonomy

  • Responses receive CORRECT, ERROR, or HALLUCINATION labels; only hallucinations receive the three-dimensional G, M, B classification.Correct includes appropriate refusal on adversarial prompts, while ERROR covers grounded attempts with implementation defects.Source: §3 · p. 3
  • Groundedness distinguishes absolute violations of universal truths from relative fabrications contingent on current knowledge or software ecosystems.Absolute examples include computability and distributed-systems impossibilities; relative examples include nonexistent APIs and modules.Source: §3 · p. 3
  • Manifestation classifies hallucinations as syntactic, semantic, or factual, and is largely orthogonal to the truth being violated.Factual hallucinations can use valid code while making false claims in comments, docstrings, or other assertions.Source: §3 · pp. 3–4
  • Behavior categories range from confident fabrication and hedged compliance to task substitution and degenerate output.Task substitution silently changes the task, while degenerate output includes scaffolding, placeholders, or collapsed generation.Source: §3 · p. 4
  • Severity rises with difficulty of detection and repair; factual manifestations and confident fabrications are especially severe because they give little signal of ungroundedness.The paper ranks factual above semantic and syntactic manifestations, and B1 above B2, B3, and B4.Source: §3 · p. 4
  • Cascades from absolute to relative hallucinations are rare, and failures overwhelmingly remain within a single type.The candidate cascade is answering an absolutely impossible request by importing a fabricated library.Source: §3 · p. 4

4 Evaluation Regimes and the Adversarial Suite

The evaluation distinguishes natural solvable prompts from adversarial unsatisfiable prompts, but instantiates only the adversarial regime. Its suite pairs generated impossibility prompts with minimally edited solvable controls.

4 Evaluation Regimes and the Adversarial Suite

  • Natural prompts measure baseline hallucination on solvable tasks, but the paper leaves this regime for future work.Responses in this regime may be correct, grounded but buggy, or hallucinated.Source: §4 · p. 4
  • For adversarial prompts, the correct response is to refuse or flag impossibility; any attempt to solve an unsatisfiable task is ungrounded rather than an ordinary error.The tasks are theoretically unsatisfiable, unlike test-conflict tasks designed to measure test exploitation.Source: §4 · p. 4
  • The suite contains 270 adversarial prompts across 24 subcategories and 91 matched solvable controls, spanning six languages.Controls minimally edit adversarial prompts to make them satisfiable, and each adversarial prompt has machine-checkable metadata describing the planted entity or why it is unsatisfiable.Source: §4 · pp. 4–5

5 Experimental Evaluation

Across twelve open-weight models, the evaluation finds frequent compliance with unsatisfiable code requests, with outcomes varying by model, prompt plausibility, framing, and prompt identity.

5.1 Setup

  • The study evaluates twelve open-weight code and reasoning models using two-tier judging, validated on a 138-prompt human-labeled gold set.The judge agrees with human labels on 82% of items (κ = 0.73); when the deterministic detector and LLM judge agree, consensus matches human labels 92% of the time.Source: §5.1 · p. 5, §5 · p. 5

5.2 Main results

  • Across models, adversarial hallucination rate is 0.60 and refusal rate is 0.27, while over-refusal on solvable controls is 0.0%.Controls are answered correctly 95% of the time, with a residual 5% hallucination rate. Hallucination rate ranges from 0.26 for qwen3-coder-next to 0.90 for codellama:7b; deepseek-r1:32b hallucinates on 69% of adversarial prompts versus 37% for qwen2.5-coder:32b.Source: §5.2 · pp. 5–6

5.3 Refusal depends on surface plausibility, not depth of impossibility

  • Hallucination is highest for plausible ecosystem fabrications, such as nonexistent npm packages (0.98), and lower for abstract impossibilities (0.46 to 0.73).Surface-cued or open tasks are caught most often; across ecosystems, nonexistent npm packages are fabricated at 0.98, Rust crates at 0.89, Go packages at 0.70, Python modules at 0.66, and Java APIs at 0.40.Source: §5.3 · p. 6, Figure 2 · p. 7

5.4 Capability gains fix theory first, while plausible fabrications barely improve

  • Among the top four versus bottom four models, hallucination falls to 0.23 versus 0.82 on theory-heavy tasks, but remains 0.87 versus 0.98 on plausible-entity tasks.Pooled rates are nearly identical for absolute violations and relative fabrications (0.61 vs. 0.62); the authors suggest ecosystem grounding may need targeted mitigation, such as package-registry retrieval.Source: §5.4 · p. 7, Table 2 · p. 7

5.5 How models hallucinate: awareness comes before abstention

  • Confident fabrication accounts for 67% of hallucinated responses, while 20% hedge their compliance and still generate ungrounded code.Hedging rises from 4% of hallucinations in the two oldest models to 43% in the three lowest-hallucination-rate models, suggesting awareness can precede abstention.Source: §5.5 · p. 8

5.6 How you ask matters: framing shifts hallucination by 17 points

  • The gap between the documentation frame and question frames is 17.4 percentage points (bootstrap 95% CI [4.0, 31.3]).Settled, routine-work framing produces more fabrication than open-question framing; the ordering persists when controlling for subcategory composition.Source: §5.6 · p. 8, Table 3 · p. 8

5.7 Hallucination is chiefly a property of the prompt

  • Prompt identity explains 36% of hallucination variance versus 14% for model identity, making the request roughly 2.5× more predictive.Twenty-two percent of adversarial prompts fool at least 11 of 12 models, and all twelve nonexistent-npm-package prompts fool at least 11.Source: §5.7 · p. 9

5.8 Do hallucination types cascade?

  • Only 0.6% (3/522) of absolute-impossibility hallucinations import a verifiably nonexistent package, a rate indistinguishable from noise.The measure does not capture fabricated function or method calls on real libraries; API-level verification is left to future work.Source: §5.8 · p. 9

6 Limitations

The paper identifies boundaries in its classification, validation, evaluation design, and coverage of adversarial behavior.

6 Limitations

  • Relative prompts rely on registry snapshots and need periodic re-validation as software ecosystems evolve.Source: §6 · p. 9
  • The two-tier automatic judge was validated on 138 human-labeled items, not through exhaustive human annotation.Source: §6 · p. 9
  • The framing and per-ecosystem comparisons are observational; prompts were not fully crossed with tasks, and the suite covers a non-exhaustive set of impossibilities.The authors note that a fully crossed design is planned.Source: §6 · p. 9

7 Conclusion

The conclusion presents a taxonomy distinguishing ungrounded hallucination from grounded error and reports an adversarial evaluation across models. It also points to registry checks for package hallucinations and discloses AI assistance in writing and implementation.

7 Conclusion

  • Models produce ungrounded code on roughly 60% of unsatisfiable prompts and refuse about a quarter, while wrongly refusing none of the matched solvable controls.Source: §7 · p. 9
  • The adversarial regime comprises 270 unsatisfiable prompts and 91 matched solvable controls, evaluated across twelve open-weight models with a human-validated judge.Source: §7 · p. 9
  • Live package-registry checks can mechanically verify ecosystem fabrications, and the paper reports that this check substantially reduces package hallucinations [15].Source: §7 · p. 9

A Generative AI Usage

  • Generative AI tools assisted with writing and implementing the approach; the authors say they verified the tools’ outputs and retained responsibility for the intellectual contributions.Source: A Generative AI Usage · p. 12

B Taxonomy: Full Definitions and Examples

The taxonomy addresses boundary cases and hallucinations that may compile and run, including failures that ordinary execution-based checks can miss.

B.1 Boundary cases and hallucinations that compile and run

  • Intent misuse is an error when an existing API could plausibly meet a requirement under some interpretation, but hallucination when behavior or guarantees are falsely claimed.Source: §B.1 · p. 12
  • Unacknowledged substitution of a different task is classified as B3 task substitution, including answers that follow memorized patterns instead of modified instructions [14].Source: §B.1 · p. 12
  • Hallucinations can compile and run, so standard pass@k evaluation may miss them; examples include algorithm substitution, fabricated constants, and false constraint claims.Source: §B.1 · p. 12

B.2 Dimension 1: Groundedness

Groundedness separates absolute violations of universal truths from relative fabrications tied to contingent knowledge or the current software ecosystem.

B.2 Dimension 1: Groundedness

  • Absolute hallucinations violate truths independent of language, libraries, platforms, or time, including mathematics, computability, information theory, and physical laws.Source: §B.2 · p. 12
  • Examples of absolute impossibilities include universal lossless compression, a collision-free finite-output hash, and algorithms claiming guarantees that contradict stated hardness results.Source: §B.2 · p. 12
  • Relative hallucinations fabricate facts that are false under current knowledge or ecosystem conditions but could become true after future developments.Source: §B.2 · p. 13
  • Ecosystem fabrications include nonexistent APIs, modules, headers, compiler flags, protocols, and language features.Source: §B.2 · p. 13

B.3 Dimension 2: Manifestation level

The taxonomy distinguishes hallucinations by manifestation and behavior, then orders combinations by severity. The prompt-suite details describe its generator families, response labels, and evaluation setup.

B.3 Dimension 2: Manifestation level

  • Syntactic, semantic, and factual hallucinations differ by whether the violation is in language syntax, referenced semantics, or claims about correctness and facts.A factual hallucination may compile and run while making false algorithmic claims.Source: §B.3 · pp. 13–14

B.4 Dimension 3: Hallucination behavior

  • B1 is confident fabrication, B2 hedged compliance, B3 task substitution, and B4 degenerate output such as placeholders or collapsed generation.B2 includes proceeding with ungrounded code despite signaling uncertainty or stating the task is impossible.Source: §B.4 · p. 14

C Prompt Suite Details

  • The prompt suite draws on twelve generator families, including impossible claims, fictional algorithms, nonexistent APIs, contradictory constraints, and fictional language features or build flags.Source: C Prompt Suite Details · pp. 14–15

B.5 Severity ordering

  • Severity increases with harder-to-detect and harder-to-fix hallucinations; B1 and factual manifestations rank highest, while absolute hallucinations exceed relative ones.Factual hallucinations can compile and run; absolute violations cannot be resolved by future ecosystem changes.Source: §B.5 · p. 14, Figure 3 · p. 15, C Prompt Suite Details · p. 15

C Prompt Suite Details

  • Judges label responses CORRECT, ERROR, or HALLUCINATION, then assign hallucination dimensions; manifestation labeling was deferred in this evaluation.Adversarial prompts cannot receive ERROR, and labels came from a two-tier automatic judge validated against human labels.Source: C Prompt Suite Details · p. 15
  • Twelve models generated 4,332 responses locally at temperature 0, with one completion per prompt; no training was performed.Generation ran on a multi-GPU Linux server and required a few GPU days.Source: C Prompt Suite Details · p. 15

D Additional Results

Outcome composition varies across models: newer and larger models refuse more often, while older 7B models almost always generate ungrounded code. Among hallucinations, confident fabrication predominates for most models, while hedged compliance and task substitution grow for newer and larger models.

E Noteworthy Hallucination Samples

The examples illustrate confident fabrication, hedged compliance, and task substitution, including a fabricated construction on a solvable control task. The samples also show that a model may state an impossibility and still generate code.

Loading 2609.03267v1…