**DeepEdit: Knowledge Editing as Decoding with Constraints** Yiwei Wang, Muhao Chen, Nanyun Peng, Kai-Wei Chang University of California, Los Angeles University of California, Davis **Abstract** The challenge of editing knowledge in multi-step reasoning for large language models (LLMs) has become a significant issue due to the hallucinations of LLMs, which often lead to incorrect use of new knowledge and answers. To address this, we propose DEEPEDIT (Depth-first Search-based Constrained Decoding for Knowledge Editing), a new framework that enhances LLMs' ability to generate coherent reasoning chains with new knowledge through depth-first search. Our method introduces decoding constraints to regulate LLMs' reasoning, ensuring logical coherence when incorporating new knowledge. We also introduce two new benchmarks, MQuAKE-2002 and MQuAKE-HARD, to provide more precise and challenging assessments of knowledge editing approaches. Qualitatively, DEEPEDIT enables LLMs to produce succinct and coherent reasoning chains involving new knowledge. Quantitatively, it yields significant improvements on multiple benchmarks. **Introduction** Knowledge editing (KE) aims to enable LLMs to incorporate new or updated knowledge, contrasting with relying solely on outdated parametric knowledge. Multi-hop question answering is a challenging task to evaluate KE, requiring models to answer questions involving a chain of facts, including new knowledge. Previous methods often suffer from hallucinations of LLM generators, leading to incorrect answers. To address this, we propose DEEPEDIT, which views KE as a problem of constrained decoding. We design decoding constraints to facilitate LLMs in soundly incorporating new knowledge. These constraints include CONCISENESS, COHERENCE, RECEPTIVENESS, and PERTINENCE. DEEPEDIT uses depth-first search to efficiently increase the reasoning depth while ensuring the constraints are met. **Methodology** DEEPEDIT incorporates the above constraints into a novel KE framework. At each iteration, DEEPEDIT verifies the constraints on the step candidates and selects the most important candidate as the next reasoning step. We also introduce an early-stopping mechanism to improve efficiency. DEEPEDIT is flexible and can be applied to any black-box LLM without requiring access to model parameters or token-wise distributions. **Experiments** We evaluate DEEPEDIT on various benchmarks, including MQuAKE-3k, MQuAKE-2002, and MQuAKE-HARD. Results show that DEEPEDIT significantly improves the accuracy of question answering with new knowledge, outperforming strong baseline methods by a significant margin. Ablation studies and qualitative analysis further validate the effectiveness of DEEPEDIT's constraints and its ability to produce coherent and succinct reasoning chains.**DeepEdit: Knowledge Editing as Decoding with Constraints** Yiwei Wang, Muhao Chen, Nanyun Peng, Kai-Wei Chang University of California, Los Angeles University of California, Davis **Abstract** The challenge of editing knowledge in multi-step reasoning for large language models (LLMs) has become a significant issue due to the hallucinations of LLMs, which often lead to incorrect use of new knowledge and answers. To address this, we propose DEEPEDIT (Depth-first Search-based Constrained Decoding for Knowledge Editing), a new framework that enhances LLMs' ability to generate coherent reasoning chains with new knowledge through depth-first search. Our method introduces decoding constraints to regulate LLMs' reasoning, ensuring logical coherence when incorporating new knowledge. We also introduce two new benchmarks, MQuAKE-2002 and MQuAKE-HARD, to provide more precise and challenging assessments of knowledge editing approaches. Qualitatively, DEEPEDIT enables LLMs to produce succinct and coherent reasoning chains involving new knowledge. Quantitatively, it yields significant improvements on multiple benchmarks. **Introduction** Knowledge editing (KE) aims to enable LLMs to incorporate new or updated knowledge, contrasting with relying solely on outdated parametric knowledge. Multi-hop question answering is a challenging task to evaluate KE, requiring models to answer questions involving a chain of facts, including new knowledge. Previous methods often suffer from hallucinations of LLM generators, leading to incorrect answers. To address this, we propose DEEPEDIT, which views KE as a problem of constrained decoding. We design decoding constraints to facilitate LLMs in soundly incorporating new knowledge. These constraints include CONCISENESS, COHERENCE, RECEPTIVENESS, and PERTINENCE. DEEPEDIT uses depth-first search to efficiently increase the reasoning depth while ensuring the constraints are met. **Methodology** DEEPEDIT incorporates the above constraints into a novel KE framework. At each iteration, DEEPEDIT verifies the constraints on the step candidates and selects the most important candidate as the next reasoning step. We also introduce an early-stopping mechanism to improve efficiency. DEEPEDIT is flexible and can be applied to any black-box LLM without requiring access to model parameters or token-wise distributions. **Experiments** We evaluate DEEPEDIT on various benchmarks, including MQuAKE-3k, MQuAKE-2002, and MQuAKE-HARD. Results show that DEEPEDIT significantly improves the accuracy of question answering with new knowledge, outperforming strong baseline methods by a significant margin. Ablation studies and qualitative analysis further validate the effectiveness of DEEPEDIT's constraints and its ability to produce coherent and succinct reasoning chains.