KCTS: Knowledge-Constrained Tree Search Decoding with Token-Level
  Hallucination Detection
Sehyun Choi Tianqing Fang Zhaowei Wang Yangqiu Song
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.