# KCTS: Knowledge-Constrained Tree Search Decoding with Token-Level Hallucination Detection

arXiv: https://arxiv.org/abs/2310.09044 · HTML: https://mlsanity.com/paper/2310.09044/

## Key facts

- Cited by 45 papers in the map (data through 14 Oct 2026).
- Builds on 67 of its 92 references that are in the map.
- First posted on arXiv 13 Oct 2023.

## Builds on (most cited first, 30 of 67)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [LoRA: Low-Rank Adaptation of Large Language Models](https://mlsanity.com/paper/2106.09685/) (2021)
- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [Overcoming catastrophic forgetting in neural networks](https://mlsanity.com/paper/1612.00796/) (2016)
- [Dense Passage Retrieval for Open-Domain Question Answering](https://mlsanity.com/paper/2004.04906/) (2020)
- [Scaling Instruction-Finetuned Language Models](https://mlsanity.com/paper/2210.11416/) (2022)
- [TruthfulQA: Measuring How Models Mimic Human Falsehoods](https://mlsanity.com/paper/2109.07958/) (2021)
- [Survey of Hallucination in Natural Language Generation](https://mlsanity.com/paper/2202.03629/) (2022)
- [Multitask Prompted Training Enables Zero-Shot Task Generalization](https://mlsanity.com/paper/2110.08207/) (2021)
- [FEVER: a large-scale dataset for Fact Extraction and VERification](https://mlsanity.com/paper/1803.05355/) (2018)
- [Improving language models by retrieving from trillions of tokens](https://mlsanity.com/paper/2112.04426/) (2021)
- [Get To The Point: Summarization with Pointer-Generator Networks](https://mlsanity.com/paper/1704.04368/) (2017)
- [FActScore: Fine-grained Atomic Evaluation of Factual Precision in Long Form Text Generation](https://mlsanity.com/paper/2305.14251/) (2023)
- [Leveraging Passage Retrieval with Generative Models for Open Domain Question Answering](https://mlsanity.com/paper/2007.01282/) (2020)
- [LLM.int8(): 8-bit Matrix Multiplication for Transformers at Scale](https://mlsanity.com/paper/2208.07339/) (2022)
- [On Faithfulness and Factuality in Abstractive Summarization](https://mlsanity.com/paper/2005.00661/) (2020)
- [A Multitask, Multilingual, Multimodal Evaluation of ChatGPT on Reasoning, Hallucination, and Interactivity](https://mlsanity.com/paper/2302.04023/) (2023)
- [SelfCheckGPT: Zero-Resource Black-Box Hallucination Detection for Generative Large Language Models](https://mlsanity.com/paper/2303.08896/) (2023)
- [Plug and Play Language Models: A Simple Approach to Controlled Text Generation](https://mlsanity.com/paper/1912.02164/) (2019)
- [REPLUG: Retrieval-Augmented Black-Box Language Models](https://mlsanity.com/paper/2301.12652/) (2023)
- [CTRL: A Conditional Transformer Language Model for Controllable Generation](https://mlsanity.com/paper/1909.05858/) (2019)
- [Retrieval Augmentation Reduces Hallucination in Conversation](https://mlsanity.com/paper/2104.07567/) (2021)
- [Object Hallucination in Image Captioning](https://mlsanity.com/paper/1809.02156/) (2018)
- [Wizard of Wikipedia: Knowledge-Powered Conversational agents](https://mlsanity.com/paper/1811.01241/) (2018)
- [DExperts: Decoding-Time Controlled Text Generation with Experts and Anti-Experts](https://mlsanity.com/paper/2105.03023/) (2021)
- [8-bit Optimizers via Block-wise Quantization](https://mlsanity.com/paper/2110.02861/) (2021)
- [Asking and Answering Questions to Evaluate the Factual Consistency of Summaries](https://mlsanity.com/paper/2004.04228/) (2020)
- [GeDi: Generative Discriminator Guided Sequence Generation](https://mlsanity.com/paper/2009.06367/) (2020)
- [FUDGE: Controlled Text Generation With Future Discriminators](https://mlsanity.com/paper/2104.05218/) (2021)
- [Check Your Facts and Try Again: Improving Large Language Models with External Knowledge and Automated Feedback](https://mlsanity.com/paper/2302.12813/) (2023)

## Built on by (most cited first, 30 of 45)

- [A Survey on Hallucination in Large Language Models: Principles, Taxonomy, Challenges, and Open Questions](https://mlsanity.com/paper/2311.05232/) (2023)
- [s1: Simple test-time scaling](https://mlsanity.com/paper/2501.19393/) (2025)
- [Inference Scaling Laws: An Empirical Analysis of Compute-Optimal Inference for Problem-Solving with Language Models](https://mlsanity.com/paper/2408.00724/) (2024)
- [Think Only When You Need with Large Hybrid-Reasoning Models](https://mlsanity.com/paper/2505.14631/) (2025)
- [ReasonFlux: Hierarchical LLM Reasoning via Scaling Thought Templates](https://mlsanity.com/paper/2502.06772/) (2025)
- [TreeBoN: Enhancing Inference-Time Alignment with Speculative Tree-Search and Best-of-N Sampling](https://mlsanity.com/paper/2410.16033/) (2024)
- [Large Language Models Hallucination: A Comprehensive Survey](https://mlsanity.com/paper/2510.06265/) (2025)
- [Think Twice: Enhancing LLM Reasoning by Scaling Multi-round Test-time Thinking](https://mlsanity.com/paper/2503.19855/) (2025)
- [AdaptiveStep: Automatically Dividing Reasoning Step through Model Confidence](https://mlsanity.com/paper/2502.13943/) (2025)
- [To Backtrack or Not to Backtrack: When Sequential Search Limits Model Reasoning](https://mlsanity.com/paper/2504.07052/) (2025)
- [SciMMIR: Benchmarking Scientific Multi-modal Information Retrieval](https://mlsanity.com/paper/2401.13478/) (2024)
- [Beyond Instruction Following: Evaluating Inferential Rule Following of Large Language Models](https://mlsanity.com/paper/2407.08440/) (2024)
- [On the Effect of Sampling Diversity in Scaling LLM Inference](https://mlsanity.com/paper/2502.11027/) (2025)
- [CoAT: Chain-of-Associated-Thoughts Framework for Enhancing Large Language Models Reasoning](https://mlsanity.com/paper/2502.02390/) (2025)
- [On the Query Complexity of Verifier-Assisted Language Generation](https://mlsanity.com/paper/2502.12123/) (2025)
- [FACTOID: FACtual enTailment fOr hallucInation Detection](https://mlsanity.com/paper/2403.19113/) (2024)
- [ComparisonQA: Evaluating Factuality Robustness of LLMs Through Knowledge Frequency Control and Uncertainty](https://mlsanity.com/paper/2412.20251/) (2024)
- [Meta-Thinking in LLMs via Multi-Agent Reinforcement Learning: A Survey](https://mlsanity.com/paper/2504.14520/) (2025)
- [Active Layer-Contrastive Decoding Reduces Hallucination in Large Language Model Generation](https://mlsanity.com/paper/2505.23657/) (2025)
- [CoCoA: Confidence and Context-Aware Adaptive Decoding for Resolving Knowledge Conflicts in Large Language Models](https://mlsanity.com/paper/2508.17670/) (2025)
- [Sketch-Guided Constrained Decoding for Boosting Blackbox Large Language Models without Logit Access](https://mlsanity.com/paper/2401.09967/) (2024)
- [Dynamic Attention-Guided Context Decoding for Mitigating Context Faithfulness Hallucinations in Large Language Models](https://mlsanity.com/paper/2501.01059/) (2025)
- [Fake Artificial Intelligence Generated Contents (FAIGC): A Survey of Theories, Detection Methods, and Opportunities](https://mlsanity.com/paper/2405.00711/) (2024)
- [Enhancing Uncertainty Modeling with Semantic Graph for Hallucination Detection](https://mlsanity.com/paper/2501.02020/) (2025)
- [UniT: Unified Multimodal Chain-of-Thought Test-time Scaling](https://mlsanity.com/paper/2602.12279/) (2026)
- [Groundedness in Retrieval-augmented Long-form Generation: An Empirical Study](https://mlsanity.com/paper/2404.07060/) (2024)
- [Learning Shrinks the Hard Tail: Training-Dependent Inference Scaling in a Solvable Linear Model](https://mlsanity.com/paper/2601.03764/) (2026)
- [CLUE: Concept-Level Uncertainty Estimation for Large Language Models](https://mlsanity.com/paper/2409.03021/) (2024)
- [Enhancing Test-Time Scaling of Large Language Models with Hierarchical Retrieval-Augmented MCTS](https://mlsanity.com/paper/2507.05557/) (2025)
- [It's Not That Simple. An Analysis of Simple Test-Time Scaling](https://mlsanity.com/paper/2507.14419/) (2025)

## Abstract (arXiv)

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.