KCTS : Knowledge-Constrained Tree Search Decoding with Token-Level Hallucination Detection (2023)

Abstract: Large Language Models (LLMs) have demonstrated remarkable human-level natural language generation capabilities. However, their potential to generate misinformation, often called the *hallucination* problem, poses a significant risk to their deployment. A common approach to address this issue is to retrieve relevant knowledge and fine-tune the LLM with the knowledge in its input. Unfortunately, this method incurs high training costs and may cause catastrophic forgetting for multi-tasking models. To overcome these limitations, we propose a knowledge-constrained decoding method called KCTS (Knowledge-Constrained Tree Search), which guides a frozen LM to generate text aligned with the reference knowledge at each decoding step using a knowledge classifier score and MCTS (Monte-Carlo Tree Search). To adapt the sequence-level knowledge classifier to token-level guidance, we also propose a novel token-level hallucination detection method called RIPA (Reward Inflection Point Approximation). Our empirical results on knowledge-grounded dialogue and abstractive summarization demonstrate the strength of KCTS as a plug-and-play, model-agnostic decoding method that can effectively reduce hallucinations in natural language generation.

## introduction recent progress in instruction-tuned language models (lms) has brought forth strong general-purpose language ai that can perform well on various tasks in a zero-shot setting @xcite @xcite . however, there have been numerous studies indicating current language models may generate non-factual information that is not supported by evidence with a high level of confidence @xcite . this phenomenon, often referred to as hallucination, poses a significant risk to the reliability of the texts generated by these models. previous research has attempted to mitigate this issue by augmenting the input of the language model with relevant knowledge @xcite , involving knowledge retrieval @xcite @xcite to identify relevant information and a reader language model that takes both the context and the retrieved knowledge as input to generate a response @xcite @xcite @xcite . some works also proposed joint-train methods of the retriever and reader modules for better performance @xcite . while these approaches have demonstrated potential, it involves pre-training or fine-tuning the reader language model, which poses significant challenges. first, the ever-increasing size of language models makes training them computationally expensive, which is becoming increasingly prohibitive, not to mention that some api-based llms (e.g., ope-nai apis foot_1 ) are not trainable by end users. second, many state-of-the-art language models are designed to be multi-task zero-shot models through instruction tuning, aiming to perform well across various tasks. however, fine-tuning a language model extensively on a specific task can lead to catastrophic forgetting @xcite @xcite , causing the model to lose its generalizability across different tasks and compromising its overall performance. to address these challenges, there is a pressing need for methods that do not require updating weights of language models, enabling efficient knowledge-grounded generation without sacrificing the generalization capabilities of the model. although designing a decoding method for llms is a natural way to mitigate hallucinations without fine-tuning, current works in plug-andplay guided decoding @xcite @xcite are still inapt to directly be adapted to the knowledge-grounded scenarios due to their inability to identify the necessary knowledge required for generation, which leads to hallucination. therefore, in this work, we propose a novel approach to knowledge-constrained decoding (kcd), which applies an auxiliary knowledge classifier on top of a frozen lm to detect hallucinations, and uses its knowledge-groundedness score to guide the decoding process. by incorporating these classifiers during decoding, we aim to constrain the generated text, ensuring its faithfulness to the reference knowledge. in addition, we propose a novel tokenlevel hallucination detection method, ripa (reward inflection point approximation), which is trained to predict the starting point of the hallucinating token and enables effective adaptation of the knowledge classifier defined on the sequence level to the token level. to sum up, our contributions are two-fold: first, we introduce kcts (knowledge-constrained tree search), a discriminator-guided decoding method that constrains the generation to be grounded on the reference knowledge, together with a novel token-level approximation method of the future reward (groundedness) through the reward inflection point approximation (ripa). second, our extensive experiments in knowledge-grounded dialogue and abstractive summarization tasks show the strength of kcts, even outperforming chat-gpt and gpt 3.5 in some dimensions. ## related work measuring hallucinations hallucination of language models or the generation of contents that are either non-factual or not supported by evidence have been studied and reported in various fields @xcite , such as machine translation @xcite , abstractive summarization @xcite , open domain dialogue @xcite , question answering @xcite , or image captioning @xcite . recently developed llms such as bing chat, or perplexity.ai even serve as generative search engines, although their seemingly fluent and informative responses are not always verifiable @xcite . to automatically detect and quantify hallucination in model-generated text, several detection methods and benchmarks have been designed @xcite @xcite @xcite . in this work, instead of directly measuring hallucination, we aim to mitigate hallucination in knowledge-grounded systems, which naturally requires the response to be faithful to the knowledge. ## problem statement we propose to improve instruction-tuned lms' factual generation ability under a constrained decoding setting. the problem can be formulated as from an optimization perspective, obtaining a generation that is best grounded in the knowledge while being faithful to the task instruction can be written as the equation below: then, given the auto-regressive nature of language models, eq. ( 3 ) can be decomposed into token-level as found in fudge @xcite : token-level groundedness knowledge groundednss f (or hallucination in the opposite perspective) is well-defined at the sequence level, which can be modeled as an entailment or fact verification problem. however, to guide the generation at each step, we need to define f (@xmath0, k) for partially generated @xmath1. following nado @xcite , we define f (@xmath2, k) as the approximation of future groundedness, as denoted in eq. ( 5 ): in this section, we introduce the framework of kcts, which consists of a knowledge-constrained tree search decoding module ( §4.1) and a tokenlevel hallucination detection module, ripa ( §4.2). we will also introduce a sister method knowledge weighted decoding (kwd) ( §4.3), which is the weighted decoding variant using ripa. ## experiments setup in this section, we will first describe the tasks selected for knowledge-constrained decoding ( §5.1), then the evaluation metrics used ( §5.2). finally, the baselines and implementation details are provided in §5.3 and §5.4. ## main evaluation in this section, we provide the evaluation results on the above-mentioned two tasks and conduct more analysis to demonstrate the reasons behind the success of our method. ## conclusion in this work, we proposed kcts, a new guided decoding approach to knowledge-grounded natural language generation. our token-level hallucination detection module ripa used with mcts decoding has shown effectiveness in knowledge-grounded dialogue and abstractive summarization tasks regarding both automatic metrics and human evaluation, surpassing previous guided decoding baselines and even chatgpt in some metrics. applying kcts only on the first few tokens also proved helpful in the knowledge-grounded generation, adding another dimension of performance/speed trade-off.