Large Language Models (LLMs) have made significant advancements in the field of code generation, offering unprecedented support for automated programming and assisting developers. However, LLMs sometimes generate code that appears plausible but fails to meet the expected requirements or executes incorrectly. This phenomenon of hallucinations in the coding field has not been explored. To advance the community's understanding and research on code hallucinations in LLMs, we propose a definition method for these hallucinations based on execution verification and introduce the concept of code hallucinations for the first time. We categorize code hallucinations into four main types: mapping, naming, resource, and logic hallucinations, each further divided into different subcategories to better understand and address the unique challenges faced by LLMs during code generation. To systematically evaluate code hallucinations, we propose a dynamic detection algorithm for code hallucinations and construct the CodeHalu benchmark, which includes 8,883 samples from 699 tasks, to actively detect hallucination phenomena in LLMs during programming. We tested 16 popular LLMs on this benchmark to evaluate the frequency and nature of their hallucinations during code generation. The findings reveal significant variations in the accuracy and reliability of LLMs in generating code, highlighting the urgent need to improve models and training methods to ensure the functional correctness and safety of automatically generated code. This study not only classifies and quantifies code hallucinations but also provides insights for future improvements in LLM-based code generation research.
The CodeHalu benchmark and code are publicly available at <https://github.com/yuchen814/CodeHalu>.

§ INTRODUCTION

In recent years, Large Language Models (LLMs) have made remarkable progress in code generation [OpenAI, 2023, Gemini, 2023], showing the ability to complete code based on existing code and create entire programs from natural language instructions, displaying immense potential in automating the programming process and providing unprecedented support to developers [Yan et al., 2023, Jimenez et al., 2023].
However, LLMs sometimes generate incorrect, fabricated, or misleading information that appears to be true but actually contains errors, which can be referred to as the hallucinations of LLMs.
Hallucinations have attracted widespread attention in natural language and multimodal domains [Ji et al., 2023, Zhang et al., 2023, Liu et al., 2024], and researchers are working on exploring methods to mitigate hallucinations [Peng et al., 2023, Elaraby et al., 2023, Liu et al., 2023]. Yet, the issue of hallucinations in LLMs during code generation remains unexplored.

Code snippets with hallucinations can lead to runtime errors, security vulnerabilities, and a general decline in code quality, hindering the reliable deployment of LLMs in practical software development tasks. Therefore, exploring and verifying the occurrence of code hallucinations is crucial for guiding the improvement of LLMs architectures and training methods. It also holds great value for ensuring the accuracy and reliability of code generation results.
Moreover, unlike hallucinations for natural language text that mainly focus on the contextual semantic consistency and factual accuracy of the output content, hallucinations for code generation require stricter precision and correctness verification based on actual execution [Chen et al., 2021, Austin et al., 2021].
Accordingly, conducting specific research on how to reduce code hallucinations and improve the quality of code generated by LLMs is particularly urgent.

To fill this research gap, we propose a comprehensive method for defining code hallucinations in LLMs which considers the unique purpose and function of code. Code hallucinations refer to the phenomenon where code generated by LLMs appears reasonable or even semantically correct but actually cannot run as expected or does not meet specified requirements. This phenomenon is typically caused by various factors, such as errors or outdated information in the model's training data; insufficient understanding of the syntax rules and programming paradigms of programming languages; and limitations in the model's logical processing capabilities.
We focus on the hallucinations that actively occur during the code generation process of LLMs. Given that the ultimate goal of code is to be executed correctly and complete specific tasks, unlike the passive exploration of knowledge and common sense hallucinations in natural language through Q&A [Lin et al., 2021, Cheng et al., 2023], we define code hallucinations based on a code verification method of execution, dividing them into four major categories: Mapping hallucinations, Naming hallucinations, Resource hallucinations, and Logic hallucinations, as well as the eight subcategories under these three categories, as shown in Figure <ref>. This categorization not only helps the community deeply understand the nature of code hallucinations but also provides a theoretical foundation for developing corresponding mitigation measures.

The summary of CodeHalu Benchmark. CodeHalu includes 4 main categories and 8 sub-categories of hallucinations.

To effectively measure and compare the hallucinations of different LLMs in code generation, we introduce the CodeHalu benchmark. CodeHalu focuses on detecting and evaluating the active hallucinations of LLMs during code generation, closely corresponding to real-world scenarios of assisting human programming, and helps to ensure that the generated code can correctly implement the intended functionality. This benchmark includes four main types of hallucinations and their subdivisions into eight subtypes, covering 699 tasks corresponding to 8,883 hallucination detection samples. Additionally, we evaluate 16 popular LLMs on the CodeHalu benchmark to reveal the frequency of various types of hallucinations produced by LLMs in code generation. We hope these explorations not only reveal the prevalence and characteristics of code hallucinations in current LLMs but also provide valuable insights for developing more robust and reliable code generation systems. Our contributions can be summarized as follows:

* We are the first to propose a comprehensive method to define code hallucinations and discuss the three major categories of code hallucinations and their theoretical significance.

* We design and introduce the CodeHalu benchmark to evaluate the frequency of code hallucinations in LLMs in a manner more closely aligned with real-world application scenarios.

* We evaluate 16 popular LLMs on the CodeHalu benchmark, revealing the prevalence and characteristics of hallucinations in code generation by LLMs and providing insights for future research.

§ RELATED WORK

§.§ Existing Benchmarks for Coding

In recent years, numerous studies have focused on evaluating the capability of LLMs to handle various programming tasks. Among these, the most popular benchmark, HumanEval [Chen et al., 2021], includes 164 Python programming problems, each with an average of 6.7 unit tests. The equally popular MBPP [Austin et al., 2021] benchmark contains 974 entry-level Python programming tasks. Compared to these, the APPS [Hendrycks et al., 2021] benchmark presents more challenging programming questions, with each problem averaging 293.2 words in length. CodeScope [Yan et al., 2023] covers 43 programming languages and eight coding tasks to comprehensively evaluate LLMs in code understanding and generation. ClassEval [Du et al., 2023] focuses on complex scenarios of class-level program synthesis, proposing an evaluation method with 100 class-level Python programming samples. RepoEval [Zhang et al., 2023] uses unit tests to evaluate the performance of LLMs in library-level code completion. MMCode [Li et al., 2024] is designed to evaluate the programming capability of code models in multimodal scenarios, where programming problems need to be solved by integrating text and image information. SWE-bench [Jimenez et al., 2023] evaluates the capability of LLMs to edit code repositories to solve problems with a level of complexity similar to that faced by human programmers in real-world programming situations.

§.§ Hallucination

In NLP [Ji et al., 2023], Hallucination was first defined as a phenomenon where model-generated texts, despite being smooth and natural, lack practical meaning or are inconsistent with the provided source content. With the rapid development of LLMs, Zhang et al., 2023 recently standardize the definition of natural language hallucinations in LLMs into three categories: Input-conflicting hallucinations, where the content generated by LLMs diverges from the user's input; Context-conflicting hallucinations, in which the generated content contradicts previously generated content; and Fact-conflicting hallucinations, where the generated content conflicts with established world knowledge. These hallucinations can be attributed to various factors, such as poor-quality data samples in the training dataset or the use of sampling algorithms with high uncertainty. To mitigate these hallucinations, Shi et al., 2023 adjust decoding strategies to balance content diversity and factual accuracy, thereby reducing hallucinations. Additionally, Liu et al., 2023 integrate external knowledge sources to enhance the accuracy of LLM responses.

Within the realm of the multimodal field, hallucination often refers to inconsistencies between text descriptions and images [Yin et al., 2023]. Recently, Zhai et al., 2023 standardize the types of hallucinations in multimodal models: Object Existence Hallucination, which refers to instances where textual descriptions include objects that are not present in corresponding images; Object Attribute Hallucination, involving the inaccurate depiction of attributes for objects that do exist within the images; and Object Relationship Hallucination, pertaining to erroneous descriptions of the relationships between objects depicted in the images. To alleviate these hallucinations, Liu et al., 2023 have collected specialized data, such as negative samples, for more granular training. Zhou et al., 2023 have enhanced the accuracy of the descriptions by hallucination revisor to modify the segments most susceptible to generating hallucinations.

Despite widespread attention to hallucination problems in natural language processing and multimodal domains, hallucinations in code-related tasks have yet to be explored.

§ CODE HALLUCINATION

Code is a tool used to achieve specific human objectives through correct execution. Thus, whether the generated code can truly execute as expected and fulfil human requirements is important. Therefore, we define code hallucination as code that appears syntactically correct and semantically appropriate, but raises error during execution or meets specific requirements. This phenomenon manifests as a disconnect between the code generated by LLMs and human intentions. To explore and identify code hallucination, we adopt an execution-based verification approach. By explicitly defining code hallucination, our goal is to mitigate and eliminate inconsistencies and errors in code generated by LLMs, aiding them in more reliably generating code and advancing the development of code intelligence. In this section, we provide a detailed introduction to the methods for detecting code hallucinations (Section <ref>), the classification and definitions of code hallucinations (Section <ref>), and an exhaustive explanation and analysis of various hallucinations (Section <ref>).

§.§ Detection Methods

To explore the hallucination issues induced by LLMs during the code generation process, we chose the Automated Programming Progress Standard (APPS) dataset [Hendrycks et al., 2021], which has a high level of problem complexity. This dataset contains 10,000 programming problems, along with 131,777 test cases and 232,421 human-written reference solutions. The dataset is evenly split into training and testing sets, each containing 5,000 problems. Since some models may have been trained on the training set and the test set has more test cases on average (21.2), we opted to use only the test set to study the hallucination phenomena of LLMs in code generation.

We conduct code generation tests on 16 leading and widely-used LLMs using the APPS dataset. By executing these generated codes and verifying them against the specified test cases, we determine the correctness of the solutions and their consistency with human intentions. This execution-based verification method is crucial for identifying failure points caused by hallucinations in LLMs when completing specific programming tasks, such as code context inconsistencies, violations of programming common sense, ambiguous logic and data flow, and intent inconsistencies. By executing the codes generated by various models, we collect 14 common error types (detail in Section <ref>) and cases where the generated code does not match human expectations, and use these to characterize the hallucination phenomena of LLMs during code generation. We use these error types and cases of intent misalignment to detect and quantify the occurrence of code hallucinations. This exploration and characterization not only help us better understand the nature and causes of code hallucinations but also provide significant references and guidance for improving the code generation capabilities of LLMs and eliminating code hallucinations.

§.§ Classification & Definitions

We identify and validate 14 error types that characterize various code hallucination phenomena in LLMs, where the generated code does not align with human expected intentions. As shown in Figure <ref>, based on the nature and root causes of these phenomena, we categorize code hallucinations into four major types: mapping hallucinations, naming hallucinations, resource hallucinations, and logic hallucinations.

§.§.§ Mapping Hallucinations

Mapping hallucinations refer to the ambiguity and confusion that occur in LLMs' perception and mapping of data types, values, and structures during data operations. This phenomenon is further divided into two sub-categories: data compliance hallucinations and structural access hallucinations.

Data compliance hallucinations occur when LLMs have a fuzzy understanding of the data types and parameter values of the objects being manipulated, resulting in generated code that attempts to perform type-mismatched or rule-violating operations. This hallucination typically manifests as TypeError, ValueError, or ZeroDivisionError exceptions being thrown during code execution, reflecting the model's unexpected behaviour in data type validation, parameter value handling, and arithmetic operations during the code generation process.

Structural access hallucinations occur when LLMs misinterpret the data structures of the objects being manipulated, leading to generated code that attempts to access non-existent array indices or dictionary keys. This hallucination typically manifests as IndexError or KeyError exceptions being thrown during code execution, reflecting the model's lack of clarity in understanding the data structures in the context during the code generation process.

§.§.§ Naming Hallucinations

Naming hallucinations refer to the memory-related issues and violations of facts exhibited by LLMs when handling variable, attribute, and module naming, scope, and existence. This phenomenon is further divided into two subcategories: identity hallucinations and external source hallucinations.

Identity hallucinations occur when LLMs have biased memories or insufficient understanding of the context, resulting in generated code that attempts to reference undefined variables, access non-existent object properties, or use unassigned variables in local scopes. This hallucination typically manifests as NameError, AttributeError, or UnboundLocalError exceptions being thrown during code execution, reflecting the model's difficulty in handling long-distance dependencies and accurately tracking variable definitions and scopes. Additionally, the model may overly rely on local cues while ignoring global information, leading to incorrect references to variables and properties.

External source hallucinations occur when LLMs have significant memory-related issues or obvious conflicts with facts regarding external knowledge sources, resulting in generated code that attempts to import non-existent modules or fails to correctly load modules from other paths. This hallucination typically manifests as ImportError or ModuleNotFoundError exceptions being thrown during code execution, reflecting a lack of deep understanding and accurate memory of the representation and organization of external knowledge sources by the model.

§.§.§ Resource Hallucinations

Resource hallucinations refer to the LLMs’ insufficient perception and prediction of resource consumption and control flow of the generated code during actual execution. This phenomenon is further divided into physical constraint hallucinations and computational boundary hallucinations.

Physical constraint hallucinations occur when LLMs underestimate resource consumption during data processing operations, causing code failure during execution due to exceeding memory capacity, stack depth, or other physical constraints. This hallucination typically manifests as RecursionError or MemoryError exceptions being thrown during code execution, reflecting the model's inadequate understanding of the global operating conditions of the code, thus ignoring the actual executability of the code.

Computational boundary hallucinations occur when LLMs have a blurred recognition of the limits of numerical calculations and iteration endpoints during data processing operations, causing code failure during execution due to numerical overflow or improper iteration control. This hallucination typically manifests as OverflowError or StopIteration exceptions being thrown during code execution, reflecting the model's erroneous understanding of numerical boundary conditions and insufficient grasp of the inherent logic of iterators, loops, and control flows.

§.§.§ Logic Hallucinations

Logic hallucinations refer to the discrepancies between the expected results and the actual outcomes after executing the code generated by LLMs, or outputs with low semantic density or even complete chaos. This phenomenon is further divided into logic deviation and logic breakdown, reflecting the varying degrees of logical inconsistency and misunderstanding in the model's output.

Logic deviation occurs when LLMs generate code with insufficient logical consideration or contradictions to the intended instructions. This hallucination usually does not cause errors during code execution, but due to logical deviations or errors, the program's running results do not achieve the expected effects. This reflects the model’s insufficient handling of logic or inadequate understanding of algorithms during the code generation process.

Logic breakdown occurs when LLMs struggle to interpret or maintain a continuous understanding of context during the code generation process. This suggests that the models may lose direction while generating code, finding it difficult to strictly maintain the consistency of contextual information. As a result, the models might generate stuttering, infinite enumeration, or gibberish code, which often lacks structural coherence and logical consistency.

§.§ Cause Analysis

Mapping hallucinations, such as data compliance hallucinations and structural access hallucinations, primarily stem from the model's misunderstanding of data types and structures. This phenomenon can be attributed to several factors: (1) The model generates code based on tokens as the basic unit, thus lacking insight into higher-level structures such as statements and functions [Yang et al., 2021]; (2) When dealing with long-distance data dependencies, especially within complex code blocks, the model often fails to continuously track the structure and state of variables, and may overly rely on local information while neglecting the importance of the overall context [Zhang et al., 2024]; (3) Since LLMs learn based on probabilistic statistics, they may not fully grasp the strict rules and constraints of data types in specific programming languages [Bouyamourn, 2023]; (4) The model does not explicitly perform type checking and structure matching during code generation, lacking static checking and error correction mechanisms; (5) The diversity of programming languages, with significant differences in data types and operation rules, makes it challenging for models to form a unified type system [Yan et al., 2023].

Naming hallucinations, including identity hallucinations and external source hallucinations, reflect the limitations of models in tracking information and utilizing external knowledge. This can be attributed to several factors: (1) Token-based feature representation makes it difficult to accurately model long-distance dependencies,  leading to model misjudgments regarding variable scope, lifecycle, and visibility [Xu et al., 2020]; (2) The model has insufficient semantic understanding of code, making it challenging to infer the meanings of identifiers based on context, thereby easily referencing undefined variables; (3) The code generation process lacks consistency checks for identifiers and does not perform global tracking of variable definitions and usage; (4) Knowledge of external libraries is not effectively and timely integrated into the model's knowledge system, making it difficult for the model to accurately understand the names, functions, and invocation methods of libraries; (5) The model's training data includes errors, or inconsistencies information [Jesse et al., 2023].

Resource hallucinations, such as physical constraint hallucinations and computational boundary hallucinations, showcase the model's lack of deep understanding of code execution mechanisms and physical constraints. These are due to several factors: (1) The lack of information related to resource consumption and performance optimization in the training data makes it difficult for the model to learn about complexity analysis and resource assessment; (2) Since the model generates code-based on probabilities, it has no module for calculating and estimating the resource consumption of the generated code, making it challenging to avoid extreme cases; (3) The model lacks common-sense understanding of numerical precision and value ranges, potentially generating code that exceeds boundaries or causes overflow; (4) The model lacks an intuitive understanding of code's time and space complexity, unable to simulate the real-world operating environment and resource limits, thus making it difficult to appropriately judge the feasibility of algorithms; (5) The model typically focuses on the immediate functionality of code, rather than its performance in specific operating environments.

Logic hallucinations reveal the model's deficiencies in semantic understanding and reasoning about code. This can be attributed to several factors: (1) The model mainly relies on pattern matching and statistical rules to generate code, lacking deep understanding and strict verification of program logic; (2) The training data is often not strictly verified for correctness and may contain code with very similar functions. As models depend on imitating and memorizing previous examples rather than performing rigorous reasoning [Yan & Li, 2022], this may result in code that seems formally correct but whose underlying logic does not align with specific requirements; (3) The reasoning capabilities of models are mainly reflected in local, short-distance dependencies, potentially leading to local optimizations while neglecting global optimization, lacking control and scrutiny over global logic; (4) When the model generates code, repetition at the line level has a self-reinforcing effect, causing the model to become increasingly confident in the code it generates, which may lead to a stuttering phenomenon. Furthermore, this stuttering is particularly pronounced when using decoding algorithms based on maximization [Xu et al., 2022].

§ THE CODEHALU BENCHMARK

CodeHalu Benchmark Construction

[1]
Input: Test dataset APPS with 5000 samples
Output: CodeHALU benchmark

% Validation Phase
Let $ER \gets$ empty list
each sample $A_i$, where $i \in \{1, \dots, 5000\}$
Let $ER^{A_i} \gets$ empty list
each $LLM_j$, where $j \in \{1, \dots, 16\}$
Generate code $GC_j^{A_i} \gets$ $LLM_j(GI_j, q)$
Let $ER_j^{A_i} \gets$ empty list
each test case $t_n$, where $n \in \{1, \dots, N\}$
Execution result $ER_j^{A_i}(t_n) \gets\text{Execute}(GC_j^{A_i})$
Append $ER_j^{A_i}(t_n)$ to $ER_j^{A_i}$
Append $ER_j^{A_i}$ to $ER^{A_i}$
Append $ER^{A_i}$ to $ER$

% Identification Phase
Let $HALU_A \gets$ empty list
each sample $A_i$, where $i \in \{1, \dots, 5000\}$
Let $HALU_{A_i} \gets$ empty list
each code hallucination type $halu_o$, where $o \in \{1, \dots, 15\}$
Aggregate occurrences of $halu_o$ in $ER^{A_i}$
Let $P_o \gets$ Frequency($halu_o$, $ER^{A_i}$)
Append $(halu_o, P_o)$ to $HALU_{A_i}$
Sort $HALU_{A_i}$ by frequency in descending order
Let $HALU_{A_i}^{top5} \gets$ Top($HALU_{A_i}$, 5)
Append $HALU_{A_i}^{top5}$ to $HALU_A$

% Construction Phase
Let $CodeHalu \gets$ empty list
each code hallucination type $halu_o$, where $o \in \{1, \dots, 15\}$
Sort all \(HALU_{A_i}^{top5}\) from \(HALU_A\) in descending order based on the frequency \(P_o\) of \(halu_o\)
Analyze the sorted frequency distribution to determine threshold $k$

$k$ is typically set to the 30th percentile of the sorted frequencies

Let $A_{halu_o} \gets$ empty set
each sample $A_i$
$(halu_o, P_o) \in HALU_{A_i}^{top5} \land P_o > k$
Add $A_i$ to $A_{halu_o}$
Add $A_{halu_o}$ to $CodeHalu$

To evaluate and compare the hallucination behaviours of different LLMs during code generation, we design the CodeHalu benchmark. This benchmark provides a standardized method to detect and evaluate various hallucinations that may occur during code generation by different LLMs and their incidence rates. The construction of the CodeHalu benchmark is based on the assumption ASS: if a specific type of error or unexpected execution result frequently appears in the code generated by multiple models, it indicates a common hallucination in LLMs. This method not only measures whether the code executes correctly but also reveals the types of errors LLMs tend to produce. This evaluation process simulates real-world programming scenarios and effectively ensures that the code generated by LLMs executes accurately in actual environments.

Collection of CodeHalu benchmark based on a verification-identification-construction process. For a sample from the APPS test set, we use $n$ LLMs to generate code, which is then executed and validated. We select the top 5 most frequent hallucinations from the code execution results to represent the main hallucinations of this sample. If the frequency of any selected hallucination exceeds the threshold $k$, we add this sample to the corresponding hallucination set. Finally, we combine all hallucination sample sets to form the CodeHalu benchmark.

Therefore, we evaluate hallucinations through the error rate of code after verification on the execution engine and the frequency of mismatches with human intentions. The reduction of these metrics can demonstrate an effective decrease in code hallucinations. The purpose of studying and defining hallucinations is to ensure that the generated code is correct and achieves the expected functionality, motivated by the applications and function of code in the real world. We use the APPS test set to construct the CodeHalu benchmark through a structured verification-identification-construction process based on the rate of active hallucinations in the model during code generation, as shown in Figure <ref>.

The APPS test set contains 5,000 samples, each sample \(A_i\) consists of a problem description \(q\) and a series of test cases \(t_1, t_2, \ldots, t_n\). Each test case \(t_n\) provides a set of inputs \(ip\) and the corresponding expected output \(op\). As shown in Algorithm <ref>, during the validation phase, we use a large language model \(LLM_j\) to generate code solutions \(GC_j^{A_i}\) for each sample \(A_i\), based on the recommended code generation instructions \(GI_j\) and the problem description \(q\). To test the potential hallucinations of the generated code at the finest granularity, we execute all the test cases of sample \(A_i\) one by one on \(GC_j^{A_i}\) to verify whether its functionality meets the expectations. We record the execution results \(ER_j^{A_i}\) = \([ER_j^{A_i}(t_1), ER_j^{A_i}(t_2), \ldots, ER_j^{A_i}(t_n)]\), where \(ER_j^{A_i}(t_n)\) represents the actual execution result of \(GC_j^{A_i}\) under the test case \(t_n\). As described in Section <ref>, each \(ER_j^{A_i}(t_n)\) is classified into one of 14 Error types, Mismatch op, or As expected, for a total of 16 types. We test 16 widely used LLMs on samples \(A_i\) to obtain a validation result set \(ER^{A_i}\) = \([ER_1^{A_i}, ER_2^{A_i}, \ldots, ER_{16}^{A_i}]\).

During the identification phase, based on the assumption ASS, we represent \(ER_j^{A_i}(t_n)\) as code hallucination \(halu_o\). We count the occurrence frequency \(P_o\) of each type of code hallucination \(halu_o\) in the execution results \(ER^{A_i}\) for each sample \(A_i\), and form the hallucination and frequency representation \(HALU_{A_i}\) = \([(halu_1, P_1), (halu_2, P_2), \ldots, (halu_o, P_o)]\) of sample \(A_i\). Then we sort these hallucination types according to their trigger frequency and filter out the top five most frequent hallucinations and their frequencies to form the main hallucination and frequency representation \(HALU_{A_i}^{top5}\) of sample \(A_i\).

During the construction phase, we sort each hallucination type \(halu_o\) in \(HALU_{A_i}\) in descending order and determine a threshold \(k\) by analyzing the frequency distribution after sorting, usually set at the 30th percentile of all sample trigger frequencies. We believe that if the trigger frequency of a hallucination type for a sample \(A_i\) exceeds the threshold \(k\), it means that using this sample in LLMs to generate code is highly likely to actively trigger this hallucination type. Therefore, for each hallucination type \(halu_o\), we traverse all samples, and if the main hallucination \(HALU_{A_i}^{top5}\) of sample \(A_i\) contains \(halu_o\) and its frequency \(P_o\) exceeds the threshold \(k\), we add this sample to the corresponding hallucination type set \(A_{halu_o}\). Finally, we combine all hallucination sample sets to form the final CodeHalu benchmark.

Through the above method, we establish the CodeHalu benchmark, with detailed statistics presented in Table <ref>. It includes the number of tasks and samples involved in various types of code hallucinations. The benchmark not only standardizes the identification method for code hallucinations but also provides an important recognition tool for further in-depth analysis and improvement of the accuracy of LLMs in code generation.

Category     #Tasks      #Samples       Sub-Category     #Tasks      #Samples

2*Mapping     2*262     2*2,288     0.9*Data Compliance     0.9*110     0.9*941

1.4*Structure Access     1.4*152     1.4*1347

2*Naming     2*157     2*1,853     0.9*Identity     0.9*115     0.9*1323

1.4*External Source     1.4*42     1.4*530

2*Resource     2*107     2*1,130     0.9*Physical Constraint     0.9*47     0.9*491

1.4*Computational Boundary     1.4*60     1.4*639

2*Logic     2*173     2*3,612     0.9*Logic Deviation     0.9*119     0.9*2,443

1.4*Logic Breakdown     1.4*54     1.4*1,169

Detailed statistics of categories, and quantities in CodeHalu benchmark.

§ EXPERIMENTS

§.§ Baselines

General LLMs
GPT-4 [OpenAI, 2023] is an advanced LLM that has demonstrated exceptional performance across multiple professional benchmarks, efficiently generating natural language and programming language texts that align with human intentions. Gemini [Gemini, 2023] has showcased its powerful ability to process various forms of data, including text, code, audio, images, and video, while exhibiting outstanding performance in human-computer interaction. Claude 3 [Anthropic, 2024] has made significant progress in cognitive domains such as reasoning, professional knowledge, mathematics, and language fluency, displaying its superior understanding and expression capabilities. Unlike these closed-source LLMs that only interact through APIs, LLaMA [Touvron et al., 2023] is a widely popular open-source LLM. It not only demonstrates excellent performance but also enhances model security through improved safety measures. Based on the LLaMA model, researchers have developed several supervised fine-tuned variants such as Vicuna [Chiang et al., 2023] and WizardLM [Xu et al., 2023] to further enhance the model's performance. Additionally, as a lightweight LLM, Gemma [Team et al., 2024] has also shown promising results in language understanding, reasoning, and safety.

LLMs for Coding
LLMs have demonstrated remarkable capabilities in understanding and generating code. For instance, Code LLaMA [Roziere et al., 2023] builds upon the LLaMA model, leveraging a massive dataset of code to enable contextual understanding and the generation of executable code. DeepSeek Coder [Guo et al., 2024] is trained on a dataset comprising over two trillion tokens, with 87% consisting of code and 13% natural language, resulting in leading performance across various code evaluation benchmarks. CodeGeeX [Zheng et al., 2023] is pretrained on 850 billion tokens across 23 programming languages, showing exceptional performance, particularly in code generation and code translation tasks. StarCoder [Li et al., 2023], trained on a dataset containing over one trillion tokens that span more than 80 programming languages, achieves an impressive maximum context length of 8,192 tokens, significantly enhancing performance in code auto-completion, instruction-based code modification, and natural language explanation of code snippets.

§.§ Metrics

Given the lack of exploration in code hallucination, there are currently no dedicated metrics to evaluate the phenomenon of code hallucinations in LLMs. Therefore, to more accurately evaluate the hallucination phenomenon of LLMs in code generation, we propose a novel and robust evaluation metric called Hallucination Rate (HR). The HR is calculated by detecting whether the code generated by LLMs exhibits code hallucination as defined in Section <ref> during actual execution.

Specifically, the HR is defined as the percentage of hallucination samples detected in the test set among all samples, with the formula: \(HR = \frac{1}{N} \sum_{i=1}^{N} S(i, K)\), where \(S(i, K)\) is an indicator function.  If the $i^{th}$ sample satisfies the hallucination condition, then $S (i, K)$ = 1; otherwise, $S (i, K)$ = 0. Ideally, a lower HR indicates a lower likelihood of hallucinations during code generation by the LLM, thus demonstrating greater robustness and reliability. To our knowledge, HR is the first metric that accurately reflects the hallucination phenomenon of LLMs in code generation tasks through actual execution tests. In this work, we use HR to evaluate the probability of LLMs, including GPT-4, producing hallucinations during the code generation process and their performance under different hallucination scenarios.

§.§ Result & Analysis

We evaluate 16 popular LLMs on various types of code hallucinations to explore differences in their frequency and category. The results are presented in Table <ref>, where lower numbers indicate a reduced likelihood of the model generating the corresponding type of hallucination, thereby reflecting better performance. Appendix <ref> provides detailed examples of various models on different hallucinations.

2.3*Model     3cMapping ($\downarrow$)           3cNaming ($\downarrow$)           3cResource ($\downarrow$)           3cLogic ($\downarrow$)         2*Average ($\downarrow$)

2-4 6-8 10-12 14-16
1.4*DC       1.4*SA     1.4*Avg.         1.4*ID      1.4*ES     1.4*Avg.         1.4*PC     1.4*CB     1.4*Avg.         1.4*LD    1.4*LB     1.4*Avg.

GPT-4[OpenAI, 2023]     32.31     10.02     19.19         27.74     0.57   19.97         0.20     3.76    2.21          85.76     0.51    58.17      33.04

DeepSeek Coder-6.7B[Guo et al., 2024]     24.23     25.61    25.04       15.80     0.00    11.28       17.52   17.21   17.35      99.06   0.17    67.05      38.28

GPT-3.5[Koubaa, 2023]     20.19     22.05    21.28        30.54     0.00    21.80       18.53   6.42   11.68      99.88   0.00   67.55       38.98

Claude-3[Anthropic, 2024]     38.68     29.25     33.13       9.07     0.75     6.69         37.07     20.81     27.88       100.00    0.17   67.69         41.00

ChatGLM-3-6B[Du et al., 2021]     36.13     44.91     41.30       50.87     0.00    36.32       24.85   2.35   12.12      88.99   0.00    60.19       44.23

Ernie-3.5[Baidu, 2023]    48.14     36.90     41.52       30.31     0.38    21.75       18.13   11.89   14.60      98.98   0.00     66.94       44.31

Qwen[Bai et al., 2023]     49.63     48.33     48.86       29.48     2.08    21.64       7.94   2.82   5.04      98.08   0.17    66.39      44.74

MagicCoder-7B[Wei et al., 2023]      50.27     26.58     36.32       17.69    0.00    12.63       21.18   28.33   25.22      100.00    16.25    72.90       44.84

Code LLaMA-7B[Roziere et al., 2023]     65.04     42.17     51.57       31.07     0.00    22.18       18.53   6.26   11.59      94.76   9.41   67.14       46.68

StarCoder-16B[Li et al., 2023]     48.14     38.83     42.66       60.70     9.25    45.98       28.92   11.11   18.85      95.09   0.77     64.56      49.23

LLaMA-2-7B[Touvron et al., 2023]     51.22     32.29     40.08       78.46     71.13   76.36        14.87   0.00   6.46      81.05   0.34    54.93       49.41

Gemini-1.0[Gemini, 2023]     34.11     53.53     45.54       45.88     0.00    32.76       24.44   16.12   19.73      98.65   10.35    70.07       49.57

Mistral-7B[Jiang et al., 2023]     45.48     36.53    40.21       59.18     15.85    46.79       27.49   10.80   18.05      99.35   0.17     67.25         49.76

WizardCoder-7B[Luo et al., 2023]     26.57     31.40     29.41       31.29     0.00    22.34       33.20   9.39   19.73      93.90   72.37    86.93      50.10

CodeGeeX2-6B[Zheng et al., 2023]     47.61     27.99     36.06       45.05     0.00    32.16       36.66   23.47   29.20      89.60   99.66   92.86       57.47

Gemma-7B[Team et al., 2024]     55.26     41.05     46.90       51.85     0.00    37.02       14.46   14.55   14.51      97.18   100.00     98.09      61.53

Evaluation results of 16 models on CodeHalu. DC means Data Compliance hallucination. SA means Structure Access hallucination. ID means identity hallucination. ES means External Source hallucination. PC means Physical Constraint hallucination. CB means computational Boundary hallucination. LD means Logic Deviation. LB means Logic Breakdown.

In the category of mapping hallucinations, GPT-4 and GPT-3.5 demonstrate excellent performance, which can be attributed to their advanced training algorithms and high-quality training data, enabling them to be more precise in identifying and following the rules of data types, values, and structures, exhibiting exceptional attention. In contrast, Qwen and Gemma performed poorly, indicating that they faced significant challenges in identifying data types and handling structured data.

In the category of naming hallucinations, Claude-3 perform the best, with a HR of only 6.69%, indicating its ability to accurately remember and reference entity names from the context and external knowledge bases. However, LLaMA-2 perform poorly in this category, with an average HR as high as 76.36%, particularly reaching 71.13% when referencing external sources, showing a specific weakness in handling external naming sources. Notably, most models performed close to zero on external source hallucinations, indicating that they can effectively avoid referencing non-existent external resources.

In the category of resource hallucinations, GPT-4, Qwen, and LLaMA-2 exhibit excellent performance, indicating that they can effectively consider resource constraints in actual execution and understand computational boundaries when generating code. On the other hand, MagicCoder and CodeGeeX-2 perform poorly, indicating deficiencies in their perception of resource constraints.

In the category of logic hallucinations, all models exhibit significant issues with logic deviation hallucinations. LLaMA-2 and GPT-4 fare relatively well, showing their advantages in maintaining logical consistency and reducing language repetition. Gemma has the highest HR in logic hallucinations, reflecting its inadequacy in handling complex logical expressions and intent representation. Notably, most models rarely generate code containing stuttering and verbose infinite loops, but this is more common in Gemma, CodeGeeX2, and WizardCoder, indicating that they may lose semantic and logical coherence during code generation.

Overall, GPT-4 perform well across all categories of hallucinations, with an average HR of 33.04%, demonstrating its stability and robustness in multiple scenarios. DeepSeek Coder and GPT-3.5 also show competitive results. Additionally, the performance differences of different models on specific types of hallucinations are significant, which may be related to their training data, model architecture, or alignment strategies. It is worth noting that logic hallucinations are currently the greatest challenge for LLMs, necessitating further research and mitigation. Furthermore, the performance of the same model varies significantly across different types of hallucinations, such as Claude-3 excelling in naming hallucinations but performing moderately in logic ones. This suggests that when designing and training LLMs, a comprehensive approach is necessary to mitigate or eliminate various aspects of coding hallucinations to achieve balanced performance and enhance reliability and robustness in practical applications.

§ CONCLUSION

We propose an execution-based verification framework to define and categorize the hallucination phenomena that occur in the code generation process of LLMs for the first time. Moreover, we develop a dynamic detection algorithm and construct the CodeHalu evaluation benchmark. We evaluate 16 popular LLMs on CodeHalu and establish baselines, revealing the frequency and nature of their hallucinations during code generation, highlighting the necessity for the research community to explore and eliminate code hallucinations.

Overall, we not only provide a theoretical foundation and evaluation tools for understanding and mitigating the hallucination phenomena of LLMs in code generation but also offer critical insights for devising mitigation strategies to mitigate these hallucinations. Furthermore, the design of our dynamic detection algorithm and the CodeHalu benchmark allows for their extension to more diverse tasks and programming languages, enabling a more comprehensive evaluation of LLMs in various programming environments. We will further explore it in the future.

[Anthropic, 2024]
The Claude 3 Model Family: Opus, Sonnet, Haiku.
<https://www-cdn.anthropic.com/de8ba9b01c9ab7cbabf5c33b80b7bbc618857627/Model_Card_Claude_3.pdf>, 2024.

[Austin et al., 2021]
Jacob Austin, Augustus Odena, Maxwell I. Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie J. Cai, Michael Terry, Quoc V. Le, and Charles Sutton.
Program synthesis with large language models.
CoRR, abs/2108.07732, 2021.
URL <https://arxiv.org/abs/2108.07732>.

[Bai et al., 2023]
Jinze Bai, Shuai Bai, Yunfei Chu, Zeyu Cui, Kai Dang, Xiaodong Deng, Yang Fan, Wenbin Ge, Yu Han, Fei Huang, et al.
Qwen technical report.
arXiv preprint arXiv:2309.16609, 2023.

[Baidu, 2023]
Introducing ernie 3.5: Baidu’s knowledge-enhanced foundation model takes a giant leap forward, 2023.
URL <http://research.baidu.com/Blog/index-view?id=185f>.

[Bouyamourn, 2023]
Adam Bouyamourn.
Why LLMs hallucinate, and how to get (evidential) closure: Perceptual, intensional, and extensional learning for faithful natural language generation.
In The 2023 Conference on Empirical Methods in Natural Language Processing, 2023.
URL <https://openreview.net/forum?id=nYgu408UIo>.

[Chen et al., 2021]
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Pondé de Oliveira Pinto, Jared Kaplan, Harrison Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, Alex Ray, Raul Puri, Gretchen Krueger, Michael Petrov, Heidy Khlaaf, Girish Sastry, Pamela Mishkin, Brooke Chan, Scott Gray, Nick Ryder, Mikhail Pavlov, Alethea Power, Lukasz Kaiser, Mohammad Bavarian, Clemens Winter, Philippe Tillet, Felipe Petroski Such, Dave Cummings, Matthias Plappert, Fotios Chantzis, Elizabeth Barnes, Ariel Herbert-Voss, William Hebgen Guss, Alex Nichol, Alex Paino, Nikolas Tezak, Jie Tang, Igor Babuschkin, Suchir Balaji, Shantanu Jain, William Saunders, Christopher Hesse, Andrew N. Carr, Jan Leike, Joshua Achiam, Vedant Misra, Evan Morikawa, Alec Radford, Matthew Knight, Miles Brundage, Mira Murati, Katie Mayer, Peter Welinder, Bob McGrew, Dario Amodei, Sam McCandlish, Ilya Sutskever, and Wojciech Zaremba.
Evaluating large language models trained on code.
CoRR, abs/2107.03374, 2021.
URL <https://arxiv.org/abs/2107.03374>.

[Cheng et al., 2023]
Qinyuan Cheng, Tianxiang Sun, Wenwei Zhang, Siyin Wang, Xiangyang Liu, Mozhi Zhang, Junliang He, Mianqiu Huang, Zhangyue Yin, Kai Chen, et al.
Evaluating hallucinations in chinese large language models.
arXiv preprint arXiv:2310.03368, 2023.

[Chiang et al., 2023]
Wei-Lin Chiang, Zhuohan Li, Zi Lin, Ying Sheng, Zhanghao Wu, Hao Zhang, Lianmin Zheng, Siyuan Zhuang, Yonghao Zhuang, Joseph E Gonzalez, et al.
Vicuna: An open-source chatbot impressing gpt-4 with 90%* chatgpt quality.
See https://vicuna. lmsys. org (accessed 14 April 2023), 2023.

[Du et al., 2023]
Xueying Du, Mingwei Liu, Kaixin Wang, Hanlin Wang, Junwei Liu, Yixuan Chen, Jiayi Feng, Chaofeng Sha, Xin Peng, and Yiling Lou.
Classeval: A manually-crafted benchmark for evaluating llms on class-level code generation.
CoRR, abs/2308.01861, 2023.
URL <https://doi.org/10.48550/arXiv.2308.01861>.

[Du et al., 2021]
Zhengxiao Du, Yujie Qian, Xiao Liu, Ming Ding, Jiezhong Qiu, Zhilin Yang, and Jie Tang.
Glm: General language model pretraining with autoregressive blank infilling.
arXiv preprint arXiv:2103.10360, 2021.

[Elaraby et al., 2023]
Mohamed Elaraby, Mengyin Lu, Jacob Dunn, Xueying Zhang, Yu Wang, and Shizhu Liu.
Halo: Estimation and reduction of hallucinations in open-source weak large language models.
arXiv preprint arXiv:2308.11764, 2023.

[Gemini, 2023]
Gemini: a family of highly capable multimodal models.
arXiv preprint arXiv:2312.11805, 2023.

[Guo et al., 2024]
Daya Guo, Qihao Zhu, Dejian Yang, Zhenda Xie, Kai Dong, Wentao Zhang, Guanting Chen, Xiao Bi, Y Wu, YK Li, et al.
Deepseek-coder: When the large language model meets programming–the rise of code intelligence.
arXiv preprint arXiv:2401.14196, 2024.

[Hendrycks et al., 2021]
Dan Hendrycks, Steven Basart, Saurav Kadavath, Mantas Mazeika, Akul Arora, Ethan Guo, Collin Burns, Samir Puranik, Horace He, Dawn Song, et al.
Measuring coding challenge competence with apps.
arXiv preprint arXiv:2105.09938, 2021.

[Jesse et al., 2023]
K. Jesse, T. Ahmed, P. T. Devanbu, and E. Morgan.
Large language models and simple, stupid bugs.
In 2023 IEEE/ACM 20th International Conference on Mining Software Repositories (MSR), pp.  563–575, Los Alamitos, CA, USA, may 2023. IEEE Computer Society.
URL <https://doi.ieeecomputersociety.org/10.1109/MSR59073.2023.00082>.

[Ji et al., 2023]
Ziwei Ji, Nayeon Lee, Rita Frieske, Tiezheng Yu, Dan Su, Yan Xu, Etsuko Ishii, Ye Jin Bang, Andrea Madotto, and Pascale Fung.
Survey of hallucination in natural language generation.
ACM Computing Surveys, 550 (12):0 1–38, 2023.

[Jiang et al., 2023]
Albert Q Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, et al.
Mistral 7b.
arXiv preprint arXiv:2310.06825, 2023.

[Jimenez et al., 2023]
Carlos E Jimenez, John Yang, Alexander Wettig, Shunyu Yao, Kexin Pei, Ofir Press, and Karthik Narasimhan.
Swe-bench: Can language models resolve real-world github issues?
arXiv preprint arXiv:2310.06770, 2023.

[Koubaa, 2023]
Anis Koubaa.
Gpt-4 vs. gpt-3.5: A concise showdown.
Preprints, 2023.

[Li et al., 2024]
Kaixin Li, Yuchen Tian, Qisheng Hu, Ziyang Luo, and Jing Ma.
Mmcode: Evaluating multi-modal code large language models with visually rich programming problems, 2024.

[Li et al., 2023]
Raymond Li, Loubna Ben Allal, Yangtian Zi, Niklas Muennighoff, Denis Kocetkov, Chenghao Mou, Marc Marone, Christopher Akiki, Jia Li, Jenny Chim, et al.
Starcoder: may the source be with you!
arXiv preprint arXiv:2305.06161, 2023.

[Lin et al., 2021]
Stephanie Lin, Jacob Hilton, and Owain Evans.
Truthfulqa: Measuring how models mimic human falsehoods.
arXiv preprint arXiv:2109.07958, 2021.

[Liu et al., 2023]
Fuxiao Liu, Kevin Lin, Linjie Li, Jianfeng Wang, Yaser Yacoob, and Lijuan Wang.
Aligning large multi-modal model with robust instruction tuning.
arXiv preprint arXiv:2306.14565, 2023a.

[Liu et al., 2024]
Hanchao Liu, Wenyuan Xue, Yifei Chen, Dapeng Chen, Xiutian Zhao, Ke Wang, Liping Hou, Rongjun Li, and Wei Peng.
A survey on hallucination in large vision-language models.
arXiv preprint arXiv:2402.00253, 2024.

[Liu et al., 2023]
Jiongnan Liu, Jiajie Jin, Zihan Wang, Jiehan Cheng, Zhicheng Dou, and Ji-Rong Wen.
Reta-llm: A retrieval-augmented large language model toolkit.
arXiv preprint arXiv:2306.05212, 2023b.

[Luo et al., 2023]
Ziyang Luo, Can Xu, Pu Zhao, Qingfeng Sun, Xiubo Geng, Wenxiang Hu, Chongyang Tao, Jing Ma, Qingwei Lin, and Daxin Jiang.
Wizardcoder: Empowering code large language models with evol-instruct.
arXiv preprint arXiv:2306.08568, 2023.

[OpenAI, 2023]
GPT-4 technical report, 2023.
URL <https://doi.org/10.48550/arXiv.2303.08774>.

[Peng et al., 2023]
Baolin Peng, Michel Galley, Pengcheng He, Hao Cheng, Yujia Xie, Yu Hu, Qiuyuan Huang, Lars Liden, Zhou Yu, Weizhu Chen, et al.
Check your facts and try again: Improving large language models with external knowledge and automated feedback.
arXiv preprint arXiv:2302.12813, 2023.

[Roziere et al., 2023]
Baptiste Roziere, Jonas Gehring, Fabian Gloeckle, Sten Sootla, Itai Gat, Xiaoqing Ellen Tan, Yossi Adi, Jingyu Liu, Tal Remez, Jérémy Rapin, et al.
Code llama: Open foundation models for code.
arXiv preprint arXiv:2308.12950, 2023.

[Shi et al., 2023]
Weijia Shi, Xiaochuang Han, Mike Lewis, Yulia Tsvetkov, Luke Zettlemoyer, and Scott Wen-tau Yih.
Trusting your evidence: Hallucinate less with context-aware decoding.
arXiv preprint arXiv:2305.14739, 2023.

[Team et al., 2024]
Gemma Team, Thomas Mesnard, Cassidy Hardin, Robert Dadashi, Surya Bhupatiraju, Shreya Pathak, Laurent Sifre, Morgane Rivière, Mihir Sanjay Kale, Juliette Love, et al.
Gemma: Open models based on gemini research and technology.
arXiv preprint arXiv:2403.08295, 2024.

[Touvron et al., 2023]
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al.
Llama 2: Open foundation and fine-tuned chat models.
arXiv preprint arXiv:2307.09288, 2023.

[Wei et al., 2023]
Yuxiang Wei, Zhe Wang, Jiawei Liu, Yifeng Ding, and Lingming Zhang.
Magicoder: Source code is all you need.
arXiv preprint arXiv:2312.02120, 2023.

[Xu et al., 2023]
Can Xu, Qingfeng Sun, Kai Zheng, Xiubo Geng, Pu Zhao, Jiazhan Feng, Chongyang Tao, and Daxin Jiang.
Wizardlm: Empowering large language models to follow complex instructions.
arXiv preprint arXiv:2304.12244, 2023.

[Xu et al., 2020]
Hongfei Xu, Josef van Genabith, Deyi Xiong, Qiuhui Liu, and Jingyi Zhang.
Learning source phrase representations for neural machine translation.
In Dan Jurafsky, Joyce Chai, Natalie Schluter, and Joel Tetreault (eds.), Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pp.  386–396, Online, July 2020. Association for Computational Linguistics.
URL <https://aclanthology.org/2020.acl-main.37>.

[Xu et al., 2022]
Jin Xu, Xiaojiang Liu, Jianhao Yan, Deng Cai, Huayang Li, and Jian Li.
Learning to break the loop: Analyzing and mitigating repetitions for neural text generation.
Advances in Neural Information Processing Systems, 35:0 3082–3095, 2022.

[Yan & Li, 2022]
Weixiang Yan and Yuanchun Li.
Whygen: explaining ml-powered code generation by referring to training examples.
In Proceedings of the ACM/IEEE 44th International Conference on Software Engineering: Companion Proceedings, pp.  237–241, 2022.

[Yan et al., 2023]
Weixiang Yan, Haitian Liu, Yunkun Wang, Yunzhe Li, Qian Chen, Wen Wang, Tingyu Lin, Weishan Zhao, Li Zhu, Shuiguang Deng, et al.
Codescope: An execution-based multilingual multitask multidimensional benchmark for evaluating llms on code understanding and generation.
arXiv preprint arXiv:2311.08588, 2023a.

[Yan et al., 2023]
Weixiang Yan, Yuchen Tian, Yunzhe Li, Qian Chen, and Wen Wang.
CodeTransOcean: A comprehensive multilingual benchmark for code translation.
In Houda Bouamor, Juan Pino, and Kalika Bali (eds.), Findings of the Association for Computational Linguistics: EMNLP 2023, pp.  5067–5089, Singapore, December 2023b. Association for Computational Linguistics.
URL <https://aclanthology.org/2023.findings-emnlp.337>.

[Yang et al., 2021]
Chen Yang, Yan Liu, and Changqing Yin.
Recent advances in intelligent source code generation: A survey on natural language based studies.
Entropy, 230 (9), 2021.
ISSN 1099-4300.
URL <https://www.mdpi.com/1099-4300/23/9/1174>.

[Yin et al., 2023]
Shukang Yin, Chaoyou Fu, Sirui Zhao, Tong Xu, Hao Wang, Dianbo Sui, Yunhang Shen, Ke Li, Xing Sun, and Enhong Chen.
Woodpecker: Hallucination correction for multimodal large language models.
arXiv preprint arXiv:2310.16045, 2023.

[Zhai et al., 2023]
Bohan Zhai, Shijia Yang, Xiangchen Zhao, Chenfeng Xu, Sheng Shen, Dongdi Zhao, Kurt Keutzer, Manling Li, Tan Yan, and Xiangjun Fan.
Halle-switch: Rethinking and controlling object existence hallucinations in large vision language models for detailed caption.
arXiv preprint arXiv:2310.01779, 2023.

[Zhang et al., 2023]
Fengji Zhang, Bei Chen, Yue Zhang, Jacky Keung, Jin Liu, Daoguang Zan, Yi Mao, Jian-Guang Lou, and Weizhu Chen.
Repocoder: Repository-level code completion through iterative retrieval and generation.
arXiv preprint arXiv:2303.12570, 2023a.

[Zhang et al., 2024]
Kechi Zhang, Ge Li, Huangzhao Zhang, and Zhi Jin.
Hirope: Length extrapolation for code models.
arXiv preprint arXiv:2403.19115, 2024.

[Zhang et al., 2023]
Yue Zhang, Yafu Li, Leyang Cui, Deng Cai, Lemao Liu, Tingchen Fu, Xinting Huang, Enbo Zhao, Yu Zhang, Yulong Chen, et al.
Siren's song in the ai ocean: a survey on hallucination in large language models.
arXiv preprint arXiv:2309.01219, 2023b.

[Zheng et al., 2023]
Qinkai Zheng, Xiao Xia, Xu Zou, Yuxiao Dong, Shan Wang, Yufei Xue, Zihan Wang, Lei Shen, Andi Wang, Yang Li, et al.
Codegeex: A pre-trained model for code generation with multilingual evaluations on humaneval-x.
arXiv preprint arXiv:2303.17568, 2023.

[Zhou et al., 2023]
Yiyang Zhou, Chenhang Cui, Jaehong Yoon, Linjun Zhang, Zhun Deng, Chelsea Finn, Mohit Bansal, and Huaxiu Yao.
Analyzing and mitigating object hallucination in large vision-language models.
arXiv preprint arXiv:2310.00754, 2023.

§ APPENDIX

§.§ Case Study

frame = none,
framerule = 0pt,
basicstyle = ,
breaklines = true,

Salem gave you $n$ sticks with integer positive lengths $a_1, a_2, \ldots, a_n$.

For every stick, you can change its length to any other positive integer length (that is, either shrink or stretch it). The cost of changing the stick's length from $a$ to $b$ is $|a - b|$, where $|x|$ means the absolute value of $x$.

A stick length $a_i$ is called almost good for some integer $t$ if $|a_i - t| \le 1$.

Salem asks you to change the lengths of some sticks (possibly all or none), such that all sticks' lengths are almost good for some positive integer $t$ and the total cost of changing is minimum possible. The value of $t$ is not fixed in advance and you can choose it as any positive integer.

As an answer, print the value of $t$ and the minimum cost. If there are multiple optimal choices for $t$, print any of them.

Input: The first line contains a single integer $n$ ($1 \le n \le 1000$) — the number of sticks. The second line contains $n$ integers $a_i$ ($1 \le a_i \le 100$) — the lengths of the sticks.

Output: Print the value of $t$ and the minimum possible cost. If there are multiple optimal choices for $t$, print any of them.

Generated Code
n = int(input())
a = list(map(int, input().split()))
min_cost = float('inf')
t = 0
for i in range(1, 101):
cost = sum(abs(x - i) - (abs(x - i) > 1) for x in a)
if cost < min_cost:
min_cost = cost
t = i
print(t, min_cost)

Input                                             Excepted Output                                   Executed Result

3 \n 10 1 4                                      3 7                                                           4 7

Reference Code
n = int(input())
arr = list(map(int, input().split()))
a = []
for t in range(1, 101):
tot = 0
for item in arr:
if (abs(item - t) >= 1):
tot += abs(item - t) - 1

a.append((tot, t))
print(a[0][1], a[0][0])

Input                                             Excepted Output                                   Executed Result

3 \n 10 1 4                                      3 7                                                           3 7

A detailed case study on wrong logic by WizardCoder.

A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array) and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

Consider a permutation $p$ of length $n$, we build a graph of size $n$ using it as follows: For every $1 \leq i \leq n$, find the largest $j$ such that $1 \leq j < i$ and $p_j > p_i$, and add an undirected edge between node $i$ and node $j$. For every $1 \leq i \leq n$, find the smallest $j$ such that $i < j \leq n$ and $p_j > p_i$, and add an undirected edge between node $i$ and node $j$.

In cases where no such $j$ exists, we make no edges. Also, note that we make edges between the corresponding indices, not the values at those indices.

For clarity, consider as an example $n = 4$, and $p = [3,1,4,2]$; here, the edges of the graph are $(1,3),(2,1),(2,3),(4,3)$.

A permutation $p$ is cyclic if the graph built using $p$ has at least one simple cycle.

Given $n$, find the number of cyclic permutations of length $n$. Since the number may be very large, output it modulo $10^9+7$.

Please refer to the Notes section for the formal definition of a simple cycle.

Input: The first and only line contains a single integer $n$ ($3 \le n \le 10^6$).

Output: Output a single integer $0 \leq x < 10^9+7$, the number of cyclic permutations of length $n$ modulo $10^9+7$.

Generated Code

def count_cyclic_permutations(n):
MOD = 10**9 + 7
powers = [1]
powers.extend([(p * i)
factorial = [1]
for i in range(1, n+1):
factorial.append((factorial[i-1] * i)
inverse_factorial = [1]
inv = powers[MOD-2]
for i in range(1, n+1):
inverse_factorial.append((inverse_factorial[i-1] * inv)

result = 0
for i in range(1, n+1):
result = (result + (powers[n-1] - powers[n-i-1]) * factorial[i-1] * inverse_factorial[i-1])

return result

# Read input
n = int(input())

# Calculate and print the result

Input                           Excepted Output                                     Executed Result

4 \n                               16                                                               NameError: name 'p' is not defined

A detailed case study on NameError by ernie-3.5 (Cont. Table <ref>).

Reference Code

n = int(input())
MOD = 10 ** 9 + 7
ans1 = 1
ans2 = 1
for i in range(1,n+1):
ans1 *= i
for i in range(n-1):
ans2 *= 2
print((ans1 - ans2)

Input                           Excepted Output                                      Executed Result

4 \n                               16                                                               16

A detailed case study on NameError by ernie-3.5.

frame = none,
framerule = 0pt,
basicstyle = ,
breaklines = true,

Ksenia has ordinary pan scales and several weights of an equal mass. Ksenia has already put some weights on the scales, while other weights are untouched. Ksenia is now wondering whether it is possible to put all the remaining weights on the scales so that the scales were in equilibrium.

The scales is in equilibrium if the total sum of weights on the left pan is equal to the total sum of weights on the right pan.

The first line has a non-empty sequence of characters describing the scales. In this sequence, an uppercase English letter indicates a weight, and the symbol "|" indicates the delimiter (the character occurs in the sequence exactly once). All weights that are recorded in the sequence before the delimiter are initially on the left pan of the scale. All weights that are recorded in the sequence after the delimiter are initially on the right pan of the scale.

The second line contains a non-empty sequence containing uppercase English letters. Each letter indicates a weight which is not used yet.

It is guaranteed that all the English letters in the input data are different. It is guaranteed that the input does not contain any extra characters.

If you cannot put all the weights on the scales so that the scales were in equilibrium, print string "Impossible". Otherwise, print the description of the resulting scales, copy the format of the input.

If there are multiple answers, print any of them.

Generated Code

def put_weights_on_scales(scales, weights):
left_weights = []
right_weights = []
for weight in weights:
if weight not in left_weights:
if weight not in right_weights:

if sum(left_weights) == sum(right_weights):
return scales + "|" + "".join(right_weights)
return "Impossible"

# Example usage
scales = input().strip()
weights = input().strip()
print(put_weights_on_scales(scales, weights))

Input               Excepted Output           Executed Result

AC|T\nL\n        AC|TL\n                           TypeError: unsupported operand type(s) for +: 'int' and 'str'

A detailed case study on TypeError by ChatGLM (Cont. Table <ref>).

Reference Code

scales = input().split('|')
weights = list(input())

balance = len(scales[0]) - len(scales[1])

while weights:
if len(scales[0]) < len(scales[1]):
scales[0] += weights[0]
scales[1] += weights[0]
balance = len(scales[0]) - len(scales[1])

if balance == 0:

Input                           Excepted Output                                      Executed Result

AC|T\nL\n                   AC|TL\n                                                      AC|TL\n

A detailed case study on TypeError by ChatGLM.

frame = none,
framerule = 0pt,
basicstyle = ,
breaklines = true,

While mostly known for the programs she wrote for Charles Babbage’s Analytic Engine, Augusta Ada King-Noel, Countess of Lovelace, described how the method of finite differences could be used to solve all types of problems involving number sequences and series. These techniques were implemented in Babbage’s Difference Engine.

The algorithm: If we compute the difference between consecutive values in a numeric sequence, we will obtain a new sequence which is related to the derivative of the function implied by the original sequence. For sequences generated from first-order polynomials (linear functions) the successive differences will be a list of identical values, (i.e., a constant difference). For second-order polynomial functions the lists of differences will be a new sequence whose values change linearly. In turn, the list of differences of the values in this generated list (i.e., the finite differences of the list of differences) will be constant, and so on for higher-order polynomials. In general the $n^{\text{th}}$ row of differences will be constant for an $n^{\text{th}}$ degree polynomial.

For example, the first-order polynomial $3x + 3$ produces the sequence below at $x=0,1,2,3,4$, and the first differences are shown on the following line.

3     6     9    12    15   3     3     3     3

As another example, the polynomial $x^2$, if evaluated at inputs $x=3, 5, 7, 9,$ produces the sequence below.

9    25    49    81
16    24    32 8     8

Furthermore, if we consider a minimum-order polynomial that produces the original sequence, its value at the next regularly spaced input can be predicted by extending the difference table.

The input consists of a value $n$, designating the number of polynomial evaluations given with $2 \leq n \leq 10$, followed by $n$ values $v_1, v_2, \ldots , v_{n}$ which represent the value of a polynomial when evaluated at $n$ regularly spaced input values. Each $v_j$ will satisfy $-2000000 \leq v_j \leq 2000000$ and at least two of those values will differ from each other.

Output two integer values $d$ and $v_{n+1}$, separated by a space. The value $d$ must be the degree of a minimal-degree polynomial producing the original sequence, and $v_{n+1}$ must be the value of the polynomial if evaluated at the next regularly spaced input value.

Generated Code

def finite_differences(values):
n = len(values)
differences = [values[i+1] - values[i] for i in range(n-1)]
degree = 1
while len(set(differences)) == 1:
differences = [differences[i+1] - differences[i] for i in range(len(differences)-1)]
degree += 1
return degree, values[-1] + differences[-1]

# Read input
n = int(input())
values = [int(x) for x in input().split()]

# Compute the degree and the next value
degree, next_value = finite_differences(values)
print(degree, next_value)

Input               Excepted Output      Executed Result

5 3 6 9 12 15     1 18                            ValueError: invalid literal for int() with base 10: '5 3 6 9 12 15'

A detailed case study on ValueError by Claude3 (Cont. Table <ref>).

Reference Code

def finite_differences(values):
n = len(values)
differences = [values[i+1] - values[i] for i in range(n-1)]
degree = 1
while len(set(differences)) == 1:
differences = [differences[i+1] - differences[i] for i in range(len(differences)-1)]
degree += 1
return degree, values[-1] + differences[-1] if differences else values[-1]

values = [int(x) for x in input().split()]

degree, next_value = finite_differences(values)
print(degree, next_value)

Input                           Excepted Output                                      Executed Result

5 3 6 9 12 15                1 18                                                            1 18

A detailed case study on ValueError by Claude3.

frame = none,
framerule = 0pt,
basicstyle = ,
breaklines = true,

Andrew and Jerry are playing a game with Harry as the scorekeeper. The game consists of three rounds. In each round, Andrew and Jerry draw randomly without replacement from a jar containing \( n \) balls, each labeled with a distinct positive integer. Without looking, they hand their balls to Harry, who awards the point to the player with the larger number and returns the balls to the jar. The winner of the game is the one who wins at least two of the three rounds.

Andrew wins rounds 1 and 2 while Jerry wins round 3, so Andrew wins the game. However, Jerry is unhappy with this system, claiming that he will often lose the match despite having the higher overall total. What is the probability that the sum of the three balls Jerry drew is strictly higher than the sum of the three balls Andrew drew?

The first line of input contains a single integer \( n (2 \leq n \leq 2000) \) — the number of balls in the jar.

The second line contains \( n \) integers \( a_{i} (1 \leq a_{i} \leq 5000) \) — the number written on the \( i \)th ball. It is guaranteed that no two balls have the same number.

Print a single real value — the probability that Jerry has a higher total, given that Andrew wins the first two rounds and Jerry wins the third. Your answer will be considered correct if its absolute or relative error does not exceed \( 10^{-6} \).

Namely: let's assume that your answer is \( a \), and the answer of the jury is \( b \). The checker program will consider your answer correct, if \( \frac{|a - b|}{\operatorname{max}(1, b)} \leq 10^{-6} \).

Generated Code

def calculate_probability(n, balls):
total_ways = n * (n - 1) * (n - 2) // 6
favorable_ways = 0

for i in range(n):
for j in range(i + 1, n):
for k in range(j + 1, n):
if balls[i] < balls[j] and balls[i] < balls[k] and balls[j] > balls[k]:
favorable_ways += 1

return favorable_ways / total_ways

n = int(input())
balls = list(map(int, input().split()))

result = calculate_probability(n, balls)

Input                           Excepted Output                       Executed Result

2\n1 2                           0.0                                               ZeroDivisionError: division by zero

A detailed case study on ZeroDivisionError by GPT3.5 (Cont. Table <ref>).

Reference Code

n = int(input())
t = list(map(int, input().split()))

s, k = 0, 5001
d = [0, 0] * k

for a in t:
for b in t:
d[b - a] += 1
for i in range(k, 2 * k):
d[i] += d[i - 1]

for i in range(1, k):
s += d[i] * sum(d[j] * d[-1 - i - j] for j in range(1, k - i))

print(8 * s / (n * n - n) ** 3)

Input                           Excepted Output                                      Executed Result

2\n1 2                           0.0                                                              0.0

A detailed case study on ZeroDivisionError by GPT3.5.

frame = none,
framerule = 0pt,
basicstyle = ,
breaklines = true,

Polycarp is a music editor at the radio station. He received a playlist for tomorrow, that can be represented as a sequence $a_1, a_2, ..., a_{n}$, where $a_{i}$ is a band, which performs the $i$-th song. Polycarp likes bands with the numbers from $1$ to $m$, but he doesn't really like others.

We define as $b_{j}$ the number of songs the group $j$ is going to perform tomorrow. Polycarp wants to change the playlist in such a way that the minimum among the numbers $b_1, b_2, ..., b_{m}$ will be as large as possible.

Find this maximum possible value of the minimum among the $b_{j}$ ($1 \leq j \leq m$), and the minimum number of changes in the playlist Polycarp needs to make to achieve it. One change in the playlist is a replacement of the performer of the $i$-th song with any other group.

The first line of the input contains two integers $n$ and $m$ ($1 \leq m \leq n \leq 2000$).

The second line contains $n$ integers $a_1, a_2, ..., a_{n}$ ($1 \leq a_{i} \leq 10^9$), where $a_{i}$ is the performer of the $i$-th song.

In the first line print two integers: the maximum possible value of the minimum among the $b_{j}$ ($1 \leq j \leq m$), where $b_{j}$ is the number of songs in the changed playlist performed by the $j$-th band, and the minimum number of changes in the playlist Polycarp needs to make.

In the second line print the changed playlist.

If there are multiple answers, print any of them.

Generated Code

def calculate_probability(n, balls):
total_ways = n * (n - 1) * (n - 2) // 6
favorable_ways = 0

for i in range(n):
for j in range(i + 1, n):
for k in range(j + 1, n):
if balls[i] < balls[j] and balls[i] < balls[k] and balls[j] > balls[k]:
favorable_ways += 1

return favorable_ways / total_ways

n = int(input())
balls = list(map(int, input().split()))

result = calculate_probability(n, balls)

Input                                                       Excepted Output           Executed Result

4 4\n1000000000 100 7 1000000000      1 4\n1 2 3 4                     IndexError: list index out of range

A detailed case study on IndexError by GPT4 (Cont. Table <ref>).

Reference Code

from collections import Counter

n, m = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]

tgt = n // m
b = Counter(a)
rd = sum(b[x] for x in b if x > m)
r = 0

for i in range(1, m + 1):
while rd and b[i] < tgt:
for j in range(n):
if a[j] > m:
b[a[j]] -= 1
b[i] += 1
a[j] = i
rd -= 1
r += 1
while b[i] < tgt:
for j in range(n):
if b[a[j]] > tgt:
b[a[j]] -= 1
b[i] += 1
a[j] = i
r += 1

print(tgt, r)
print(" ".join(str(x) for x in a))

Input                                                       Excepted Output           Executed Result

4 4\n1000000000 100 7 1000000000      1 4\n1 2 3 4                     1 4\n1 2 3 4

A detailed case study on IndexError by GPT4.

frame = none,
framerule = 0pt,
basicstyle = ,
breaklines = true,

Nearly each project of the F company has a whole team of developers working on it. They often are in different rooms of the office in different cities and even countries. To keep in touch and track the results of the project, the F company conducts shared online meetings in a Spyke chat.

One day the director of the F company got hold of the records of a part of an online meeting of one successful team. The director watched the record and wanted to talk to the team leader. But how can he tell who the leader is? The director logically supposed that the leader is the person who is present at any conversation during a chat meeting. In other words, if at some moment of time at least one person is present on the meeting, then the leader is present on the meeting.

You are the assistant director. Given the 'user logged on'/'user logged off' messages of the meeting in the chronological order, help the director determine who can be the leader. Note that the director has the record of only a continuous part of the meeting (probably, it's not the whole meeting).

The first line contains integers $n$ and $m$ $(1 \leq n, m \leq 10^5)$ — the number of team participants and the number of messages. Each of the next $m$ lines contains a message in the format:  '+ id': the record means that the person with number $id$ $(1 \leq id \leq n)$ has logged on to the meeting.  '- id': the record means that the person with number $id$ $(1 \leq id \leq n)$ has logged off from the meeting.

Assume that all the people of the team are numbered from $1$ to $n$ and the messages are given in the chronological order. It is guaranteed that the given sequence is the correct record of a continuous part of the meeting. It is guaranteed that no two log on/log off events occurred simultaneously.

In the first line print integer $k$ $(0 \leq k \leq n)$ — how many people can be leaders. In the next line, print $k$ integers in the increasing order — the numbers of the people who can be leaders.

If the data is such that no member of the team can be a leader, print a single number $0$.

Generated Code

def main():
n, m = map(int, input().split())
online = set()
leaders = set(range(1, n+1))

for _ in range(m):
message = input()
id = int(message.split()[1])
if '+' in message:
if not online:

if leaders:
print(' '.join(map(str, sorted(leaders))))

if __name__ == "__main__":

Input                                             Excepted Output                                    Executed Result

3 2\n+ 1\n- 2                                  1\n3                                                          KeyError: 2

A detailed case study on KeyError by DeepSeekCoder (Cont. Table <ref>).

Reference Code

n, m = [int(x) for x in input().strip().split(" ")]

ops = []
for _ in range(m):
op, num = input().strip().split(" ")
ops.append((op, int(num)))

posibles_jefes = set(range(1, n + 1))
mencionados = set()

for i, (op, num) in enumerate(ops):
if op == '+':
if num in posibles_jefes and all(ops[j][1] != num for j in range(i)):
if all(ops[j][1] != num for j in range(i)):

posibles_jefes -= mencionados - set(num for _, num in ops if ops.count(('+', num)) and ops.count(('-', num)))

if len(posibles_jefes):
print(" ".join(map(str, sorted(posibles_jefes))))

Input                                             Excepted Output                                    Executed Result

3 2\n+ 1\n- 2                                  1\n3                                                          1\n3

A detailed case study on KeyError by DeepSeekCoder.

frame = none,
framerule = 0pt,
basicstyle = ,
breaklines = true,

George woke up and saw the current time $s$ on the digital clock. Besides, George knows that he has slept for time $t$.

Help George! Write a program that will, given time $s$ and $t$, determine the time $p$ when George went to bed. Note that George could have gone to bed yesterday relative to the current time (see the second test sample).

The first line contains current time $s$ as a string in the format “hh:mm”. The second line contains time $t$ in the format “hh:mm” — the duration of George's sleep. It is guaranteed that the input contains the correct time in the 24-hour format, that is, $00 \leq hh \leq 23$, $00 \leq mm \leq 59$.

In the single line print time $p$ — the time George went to bed in the format similar to the format of the time in the input.

Generated Code
import datetime
s = input()
t = input()
s = datetime.datetime.strptime(s, "
t = datetime.datetime.strptime(t, "
p = s - t

Input                     Excepted Output                                 Executed Result

05:50\n05:44           00:06                                                         AttributeError: 'datetime.timedelta' object
has no attribute 'strftime'

Reference Code
n = int(input())
arr = list(map(int, input().split()))
a = []
for t in range(1, 101):
tot = 0
for item in arr:
if (abs(item - t) >= 1):
tot += abs(item - t) - 1

a.append((tot, t))
print(a[0][1], a[0][0])

Input                                             Excepted Output                                   Executed Result

05:50\n05:44                                  00:06                                                       00:06

A detailed case study on AttributeError by Gemma.

frame = none,
framerule = 0pt,
basicstyle = ,
breaklines = true,

The airline company NCPC Airways has flights to and from $n$ cities, numbered from 1 to $n$, around the entire world. However, they only have $n - 1$ different flights (operating in both directions), so in order to travel between any two cities you might have to take several flights. In fact, since the management has made sure that it's possible to travel between any pair of cities, there is exactly one set of flights a passenger have to take in order to travel between two cities (assuming you want to use the same airline).

Recently many of NCPC Airways frequent flyers have complained that they have had to change flights too often to get to their final destination. Since NCPC Airways doesn't want to lose their customers to other airline companies, but still keep the nice property of their flights, they have decided to cancel one of their current flights and replace it with another flight. Help the company by writing a program which finds the best flight to cancel and the best new flight to add so that the maximum number of flight changes a passenger might have to make when traveling between any pair of cities in which NCPC Airways operates is minimized.

The input will be constructed so that it is always possible to improve the maximum number of flight changes needed.

The first line in the input contains the integer $n$ ($4 \leq n \leq 2500$), the number of cities NCPC Airways operates in. Then follow $n - 1$ lines specifying the flights. Each flight is given as a pair of cities $a$ and $b$ ($1 \le a, b \le n$).

The output should consist of three lines. The first line should contain an integer, the minimum number of flights needed to take when traveling between any pair of cities after changing one of the flights. The second line should contain two integers, specifying the two cities between which the flight should be canceled. The third line should contain two integers, specifying the two cities where a new flight should be added.

Generated Code

import sys
def find_minimum_number_of_flight_changes(flight_pairs):
visited = set()
current_num_changes = len(flight_pairs)
while current_num_changes > 0:
min_num_changes = current_num_changes
for i in range(len(flight_pairs)):
current_pair = flight_pairs[i]
if current_pair not in visited:

min_num_changes = min(min_num_changes, find_minimum_number_of_flight_changes(remove_flight_pair(flight_pairs, i)))
current_num_changes -= 1
return min_num_changes
def remove_flight_pair(flight_pairs, index):
new_flight_pairs = flight_pairs[:index] + flight_pairs[index + 1:]
return new_flight_pairs
n = int(input())
flight_pairs = []
for i in range(n - 1):
flight_pair = tuple(map(int, input().split()))
min_num_changes = find_minimum_number_of_flight_changes(flight_pairs)

Input                     Excepted Output           Executed Result

4\n1 2\n2 3\n3 4       2\n3 4\n2 4                            UnboundLocalError: local variable 'min_num_changes'
referenced before assignment

A detailed case study on UnboundLocalError by ChatGLM (Cont. Table <ref>).

Reference Code

scales = input().split('|')
weights = list(input())

balance = len(scales[0]) - len(scales[1])

while weights:
if len(scales[0]) < len(scales[1]):
scales[0] += weights[0]
scales[1] += weights[0]
balance = len(scales[0]) - len(scales[1])

if balance == 0:

Input                           Excepted Output                                      Executed Result

AC|T\nL\n                   AC|TL\n                                                      AC|TL\n

A detailed case study on UnboundLocalError by ChatGLM.

frame = none,
framerule = 0pt,
basicstyle = ,
breaklines = true,

Salem gave you $n$ sticks with integer positive lengths $a_1, a_2, \ldots, a_n$.

For every stick, you can change its length to any other positive integer length (that is, either shrink or stretch it). The cost of changing the stick's length from $a$ to $b$ is $|a - b|$, where $|x|$ means the absolute value of $x$.

A stick length $a_i$ is called almost good for some integer $t$ if $|a_i - t| \le 1$.

Salem asks you to change the lengths of some sticks (possibly all or none), such that all sticks' lengths are almost good for some positive integer $t$ and the total cost of changing is minimum possible. The value of $t$ is not fixed in advance and you can choose it as any positive integer.

As an answer, print the value of $t$ and the minimum cost. If there are multiple optimal choices for $t$, print any of them.

Input: The first line contains a single integer $n$ ($1 \le n \le 1000$) — the number of sticks. The second line contains $n$ integers $a_i$ ($1 \le a_i \le 100$) — the lengths of the sticks.

Output: Print the value of $t$ and the minimum possible cost. If there are multiple optimal choices for $t$, print any of them.

Generated Code
from math import modulo

def number_of_games(a, b, k, t):
games = (2 * k + 1) ** t
return games

print(number_of_games(1, 2, 2, 1))
print(number_of_games(1, 1, 1, 2))
print(number_of_games(2, 12, 3, 1))

Input                                    Excepted Output                Executed Result

1 2 2 1                                      6                                               ImportError: cannot import name 'modulo'

Reference Code
def c(n, k):
if k > n:
return 0
a = b = 1
for i in range(n - k + 1, n + 1):
a *= i
for i in range(1, k + 1):
b *= i
return a // b

a, b, k, t = map(int, input().split())
n, m, s = 2 * k + 1, 2 * t, 2 * k * t + b - a
ans, mod = 0, 1000000007
for i in range(m + 1):
ans = (ans + [1, -1][i     1] * c(m, i) * c(m + s - n * i, m))
print((pow(n, m, mod) - ans)

Input                                             Excepted Output                                   Executed Result

1 2 2 1                                            6                                                              6

A detailed case study on ImporError by Llama.

frame = none,
framerule = 0pt,
basicstyle = ,
breaklines = true,

Ehab has an array $a$ of length $n$. He has just enough free time to make a new array consisting of $n$ copies of the old array, written back-to-back. What will be the length of the new array's longest increasing subsequence?

A sequence $a$ is a subsequence of an array $b$ if $a$ can be obtained from $b$ by deletion of several (possibly, zero or all) elements. The longest increasing subsequence of an array is the longest subsequence such that its elements are ordered in strictly increasing order.

Input:The first line contains an integer $t$ — the number of test cases you need to solve. The description of the test cases follows.

The first line of each test case contains an integer $n$ ($1 \le n \le 10^5$) — the number of elements in the array $a$.

The second line contains $n$ space-separated integers $a_1$, $a_2$, $\ldots$, $a_{n}$ ($1 \le a_i \le 10^9$) — the elements of the array $a$.

The sum of $n$ across the test cases doesn't exceed $10^5$.

Output:For each testcase, output the length of the longest increasing subsequence of $a$ if you concatenate it to itself $n$ times.

Generated Code
def longest_increasing_subsequence_length(arr):
n = len(arr)
tails = [0] * (n + 1)
for i in range(1, n + 1):
tail_index = tails[bisect_left(tails, arr[i] - 1)]
tails[tail_index + 1] = i
return tails[-1]

import bisect_left

t = int(input())
for _ in range(t):
n = int(input())
arr = list(map(int, input().split()))

Input                                      Excepted Output               Executed Result

2\n3\n3 2 1\n6\n3 1 4 1 5 9      3\n5                                       ModuleNotFoundError: No module named

Reference Code
t = int(input())
for _ in range(t):
n = int(input())
a = list(map(int, input().split()))

Input                                             Excepted Output                                   Executed Result

2\n3\n3 2 1\n6\n3 1 4 1 5 9           3\ n5                                                        3\n5

A detailed case study on ModuleNotFoundError by Qwen.

frame = none,
framerule = 0pt,
basicstyle = ,
breaklines = true,

Vasya is studying number theory. He has denoted a function \(f(a, b)\) such that:
\(
f(a, 0) = 0;
\)
\(
f(a, b) = 1 + f\left(a, b - \gcd(a, b)\right),
\)
where \(\gcd(a, b)\) is the greatest common divisor of \(a\) and \(b\).

Vasya has two numbers \(x\) and \(y\), and he wants to calculate \(f(x, y)\). He tried to do it by himself, but found out that calculating this function the way he wants to do that might take a very long time. So he decided to ask you to implement a program that will calculate this function swiftly.

Input:The first line contains two integer numbers \(x\) and \(y\) (\(1 \leq x, y \leq 10^{12}\)).

Output:Print \(f(x, y)\).

Generated Code
import math
def gcd(a, b):
if b == 0:
return a
return gcd(b, a
def f(a, b):
if b == 0:
return 0
return 1 + f(a, b - gcd(a, b))
x, y = map(int, input().split())
print(f(x, y))

Input                                      Excepted Output              Executed Result
1000000009 1000000008       1000000008                        RecursionError: maximum recursion depth
exceeded in comparison

Reference Code
from fractions import gcd
a, b = list(map(int, input().split()))
A = []
for i in range(2, int(a**0.5) + 1):
while a
a //= i
if a != 1:
out = 0
while b > 0:
n = len(A)
x = -1
for i in range(n):
if x == -1 or b
x = i
if n == 0:
out += b
b = 0
A[x], A[n - 1] = A[n - 1], A[x]
out += b
b //= A.pop()

Input                                             Excepted Output                                   Executed Result
1000000009 1000000008             1000000008                                             1000000008

A detailed case study on RecursionError by GPT3.5.

frame = none,
framerule = 0pt,
basicstyle = ,
breaklines = true,

Reziba has many magic gems. Each magic gem can be split into $M$ normal gems. The amount of space each magic (and normal) gem takes is $1$ unit. A normal gem cannot be split.

Reziba wants to choose a set of magic gems and split some of them, so the total space occupied by the resulting set of gems is $N$ units. If a magic gem is chosen and split, it takes $M$ units of space (since it is split into $M$ gems); if a magic gem is not split, it takes $1$ unit.

How many different configurations of the resulting set of gems can Reziba have, such that the total amount of space taken is $N$ units? Print the answer modulo $1000000007$ ($10^9+7$). Two configurations are considered different if the number of magic gems Reziba takes to form them differs, or the indices of gems Reziba has to split differ.

The input contains a single line consisting of $2$ integers $N$ and $M$ ($1 \le N \le 10^{18}$, $2 \le M \le 100$).

Print one integer, the total number of configurations of the resulting set of gems, given that the total amount of space taken is $N$ units. Print the answer modulo $1000000007$ ($10^9+7$).

Generated Code
def count_configurations(N, M):
MOD = 1000000007
dp = [0] * (N + 1)
dp[0] = 1
for i in range(1, N + 1):
for j in range(1, min(i, M) + 1):
dp[i] = (dp[i] + dp[i - j])
return dp[N]

N, M = map(int, input().split())
print(count_configurations(N, M))

Input                                             Excepted Output                                   Executed Result

1000000000000000000 2              680057396                                              MemoryError

A detailed case study on MemoryError by Claude3 (Cont. Table <ref>).

Reference Code

import sys

MOD = 10**9+7

def polymod(P, Q):
assert(Q[-1] == 1)
n = len(Q)
while len(P) >= n:
p = P[-1]
for i in range(n):
P[-i-1] -= p*Q[-i-1]
assert(P[-1] == 0)
return P

def polyprod(P, Q):
W = [0]*(len(P) + len(Q) - 1)
for i in range(len(P)):
for j in range(len(Q)):
W[i+j] += P[i]*Q[j]
return [w

def power(A, B, m, mult):
if m == 0:
return B
while m > 1:
if m
B = mult(A, B)
A = mult(A, A)
m //= 2
return mult(A, B)

def calc_nth_term(init, linear_coeff, n):
def mult(A, B):
return polymod(polyprod(A, B), linear_coeff)
ans = power([0, 1], [1], n, mult)
return sum(ans[i]*init[i] for i in range(len(ans)))

n, m = map(int, input().split())
linear_rec = [0]*(m+1)
linear_rec[0] = linear_rec[m-1] = -1
linear_rec[m] = 1
print(calc_nth_term([1]*m, linear_rec, n))

Input                                             Excepted Output                                   Executed Result

1000000000000000000 2              680057396                                              680057396

A detailed case study on MemoryError by Claude3.

frame = none,
framerule = 0pt,
basicstyle = ,
breaklines = true,

Given are two strings $s$ and $t$ consisting of lowercase English letters. Determine if there exists an integer $i$ satisfying the following condition, and find the minimum such $i$ if it exists.

* Let $s'$ be the concatenation of $10^{100}$ copies of $s$. $t$ is a subsequence of the string ${s'}_1{s'}_2\ldots{s'}_i$ (the first $i$ characters in $s'$).

* A subsequence of a string $a$ is a string obtained by deleting zero or more characters from $a$ and concatenating the remaining characters without changing the relative order. For example, the subsequences of  include , , and .

* $1 \leq |s| \leq 10^5$

* $1 \leq |t| \leq 10^5$

* $s$ and $t$ consist of lowercase English letters.

Input is given from Standard Input in the following format:

If there exists an integer $i$ satisfying the following condition, print the minimum such $i$; otherwise, print $-1$.

Generated Code

import sys

def solve(s, t):
s = s * (10 ** 100)
i = 0
j = 0
while i < len(s) and j < len(t):
if s[i] == t[j]:
j += 1
i += 1
if j == len(t):
return i - len(t)
return -1

s = input()
t = input()
print(solve(s, t))

Input                    Excepted Output         Executed Result

zv\nz                     1                                    OverflowError: cannot fit 'int' into an index-sized integer

A detailed case study on OverflowError by MagicCoder (Cont. Table <ref>).

Reference Code

import bisect

def solve(S, T):
dic =
for i, s in enumerate(S, 1):
if s not in dic:
dic[s] = []

prov = 0
turn = 0
for t in T:
if t not in dic:
return -1
x = bisect.bisect(dic[t], prov)
if x == len(dic[t]):
turn += 1
prov = dic[t][0]
prov = dic[t][x]
return turn * len(S) + prov

S = input()
T = input()
print(solve(S, T))

Input                           Excepted Output                                      Executed Result

zv\nz                            1                                                                 1

A detailed case study on OverflowError by MagicCoder.

frame = none,
framerule = 0pt,
basicstyle = ,
breaklines = true,

Our bear's forest has a checkered field. The checkered field is an $n \times n$ table, the rows are numbered from 1 to $n$ from top to bottom, the columns are numbered from 1 to $n$ from left to right. Let's denote a cell of the field on the intersection of row $x$ and column $y$ by record $(x, y)$. Each cell of the field contains growing raspberry, at that, the cell $(x, y)$ of the field contains $x + y$ raspberry bushes.

The bear came out to walk across the field. At the beginning of the walk his speed is $(dx, dy)$. Then the bear spends exactly $t$ seconds on the field. Each second the following takes place:  Let's suppose that at the current moment the bear is in cell $(x, y)$.  First the bear eats the raspberry from all the bushes he has in the current cell. After the bear eats the raspberry from $k$ bushes, he increases each component of his speed by $k$. In other words, if before eating the $k$ bushes of raspberry his speed was $(dx, dy)$, then after eating the berry his speed equals $(dx + k, dy + k)$.  Let's denote the current speed of the bear $(dx, dy)$ (it was increased after the previous step). Then the bear moves from cell $(x, y)$ to cell $\left(((x + dx - 1) \mod n) + 1, ((y + dy - 1) \mod n) + 1\right)$.  Then one additional raspberry bush grows in each cell of the field.

Your task is to predict the bear's actions. Find the cell he ends up in if he starts from cell $(sx, sy)$. Assume that each bush has infinitely much raspberry and the bear will never eat all of it.

The first line of the input contains six space-separated integers: $n, sx, sy, dx, dy, t$ $(1 \leq n \leq 10^9; 1 \leq sx, sy \leq n;  -100 \leq dx, dy \leq 100; 0 \leq t \leq 10^{18})$.

Print two integers — the coordinates of the cell the bear will end up in after $t$ seconds.

Generated Code

n, sx, sy, dx, dy, t = map(int, input().split())

def move(x, y, dx, dy, t):
for i in range(t):
x, y = (x + dx)
yield x, y

print(*next(move(sx, sy, dx, dy, t)))

Input                                      Excepted Output                              Executed Result

1 1 1 1 1 0                               1 1                                                      StopIteration

A detailed case study on StopIteration by StarCoder (Cont. Table <ref>).

Reference Code

mod, sx, sy, dx, dy, t = list(map(int, input().split()))
class Matrix():
def __init__(self, n):
self.n = n
self.a = [[0] * n for _ in range(n)]

def __mul__(self, b):
res = Matrix(self.n)
for i in range(self.n):
for j in range(self.n):
for k in range(self.n):
res.a[i][j] += self.a[i][k] * b.a[k][j]
return res

def __pow__(self, e):
res = Matrix(self.n)
for i in range(self.n):
res.a[i][i] = 1
tmp = self
while e:
if e     1:
res = res * tmp
e >>= 1
tmp = tmp * tmp
return res
M = Matrix(6)
M.a = [[2, 1, 1, 0, 1, 2],
[1, 2, 0, 1, 1, 2],
[1, 1, 1, 0, 1, 2],
[1, 1, 0, 1, 1, 2],
[0, 0, 0, 0, 1, 1],
[0, 0, 0, 0, 0, 1]]
sx -= 1
sy -= 1
r = M ** t
f = lambda i: (r.a[i][0] * sx + r.a[i][1] * sy + r.a[i][2] * dx + r.a[i][3] * dy + r.a[i][5])
print(f(0), f(1))

Input                                      Excepted Output                              Executed Result

1 1 1 1 1 0                               1 1                                                      1 1

A detailed case study on StopIteration by StarCoder.