  How to edit the knowledge in multi-step reasoning has become the major
challenge in the knowledge editing (KE) of large language models (LLMs). The
difficulty arises because the hallucinations of LLMs during multi-step
reasoning often lead to incorrect use of new knowledge and incorrect answers.
To address this issue, we design decoding constraints to "regulate" LLMs'
reasoning, enhancing logical coherence when incorporating new knowledge. We
propose a new KE framework: DEEPEDIT (Depth-first Search-based Constrained
Decoding for Knowledge Editing), which enhances LLMs's ability to generate
coherent reasoning chains with new knowledge through depth-first search. Our
search selects the most important knowledge that satisfies our constraints as
the reasoning step to efficiently increase the reasoning depth. In addition to
DEEPEDIT, we propose two new KE benchmarks: MQUAKE-2002 and MQUAKE-HARD, which
provide more precise and challenging assessments of KE approaches.
Qualitatively, DEEPEDIT enables LLMs to produce succinct and coherent reasoning
chains involving new knowledge. Quantitatively, it yields significant
improvements on multiple KE benchmarks.
