Diver: Large Language Model Decoding with Span-Level Mutual Information Verification

Chen Wang

Introduction

Large Language Models (LLMs) have revolutionized natural language processing, yet they remain prone to "hallucinations"—generating text that is fluent but unfaithful to the source input. Standard decoding strategies, such as greedy search or nucleus sampling, operate in a unidirectional manner, predicting the next token based solely on the preceding context and the input. This "one-way" approach often leads to a semantic drift where the model ignores crucial prompt constraints or introduces irrelevant information.

While Point-wise Mutual Information (PMI) has been proposed as a verification metric, applying it at the token level often falls into "locally optimal" traps. A single token might appear poorly correlated with the input in isolation but could be the essential start of a highly accurate phrase. To address this, the DIVER (Decoding with span-level mutual Information VERification) strategy introduces a multi-token verification process that ensures generated text remains grounded in the source material.

The DIVER Methodology

DIVER shifts the focus from individual tokens to multi-token spans, capturing the semantic relationship between input and output more effectively. The process follows four distinct stages during inference:

  1. Identifying Divergence Points: To maintain efficiency, the model does not verify every step. Instead, it identifies "divergence points" where the model's confidence is split among multiple high-probability candidate tokens.
  2. Dynamic Span Generation: At a divergence point, the model generates several candidate spans. Unlike fixed-length methods, DIVER adaptively determines span length by looking ahead to the next potential risk point where the model might diverge again.
  3. Backward Verification (The PMI Core): This is the central innovation. DIVER calculates the log-likelihood gain of the original input $x$ given the candidate span $y$. If a span is truly faithful, the model should find the original input more "predictable" when conditioned on that span.
  4. Span Selection and Re-ranking: The original forward probability distribution is combined with these backward PMI scores to re-rank candidates, selecting the span that maximizes both fluency and faithfulness.
The DIVER decoding process: 1) Divergence point identification, 2) Dynamic span generation, 3) Input likelihood verification, and 4) Final span selection.

Key Insights

  • Faithfulness as a Span Property: The researchers demonstrate that faithfulness is a property of phrases and ideas rather than isolated tokens. Evaluating spans allows the model to escape the "short-sightedness" of token-level verification.
  • Efficiency through Asymmetry: A significant finding is that verification does not require a model of equal size to the generator. Using a smaller 1.1B parameter model (like Tiny-LLaMA) to verify a 7B or 13B model provides nearly identical performance gains with much lower computational overhead.
  • Backward Reconstruction: Using the model to "reconstruct" the input from the output serves as a powerful proxy for truthfulness. In tasks like translation, an accurate output should allow for a high-certainty reconstruction of the source sentence.

Experimental Results

DIVER was evaluated across a diverse set of benchmarks, including Machine Translation (Flores-200), Text Summarization (CNN/DailyMail), and Code Generation (MBPP).

Performance Gains

  • Translation: On the Flores Zh-En task, DIVER improved scores by 1.63 points over greedy decoding. In Ar-En, the improvement was a substantial 4.28 points.
  • Hallucination Reduction: In element-constrained generation (E2E dataset), DIVER achieved an 11.77 point improvement on LLaMA-2-7B-Chat, effectively solving "omission" errors where models previously ignored specific table attributes.

Human and Comparative Evaluation

Human evaluations confirmed that DIVER-generated text is perceived as significantly more faithful than standard decoding methods. As shown in the comparative analysis, DIVER consistently wins or ties against advanced baselines like Contrastive Decoding (CD) and Context-Aware Decoding (CAD).

Evaluation of DIVER: (a) Rate of most faithful translations compared to search baselines, and (b) Win/Tie/Loss rates against other decoding methods on faithfulness.

Conclusion and Future Work

DIVER provides a robust framework for improving LLM faithfulness by verifying output spans against the source input. While the strategy introduces some latency due to the additional backward passes, its ability to significantly reduce hallucinations across various tasks makes it a compelling choice for high-stakes generation. Future research may explore combining DIVER with speculative decoding to mitigate the computational cost while maintaining its superior faithfulness profile.

Summary updated

Abstract

Large language models (LLMs) have shown impressive capabilities in adapting to various tasks when provided with task-specific instructions. However, LLMs using standard decoding strategies often struggle with deviations from the inputs. Intuitively, compliant LLM outputs should reflect the information present in the input, which can be measured by point-wise mutual information (PMI) scores. Therefore, we propose Diver, a novel approach that enhances LLM Decoding through span-level PMI verification. During inference, Diver first identifies divergence steps that may lead to multiple candidate spans. Subsequently, it calculates the PMI scores by assessing the log-likelihood gains of the input if the candidate spans are generated. Finally, the optimal span is selected based on the PMI re-ranked output distributions. We evaluate our method across various downstream tasks, and empirical results demonstrate that Diver significantly outperforms existing decoding methods in both performance and versatility.
BibTeX
@misc{wang2024diver,
  author = {Chen Wang},
  title = {{Diver: Large Language Model Decoding with Span-Level Mutual Information Verification}},
  year = {2024},
  eprint = {2406.02120},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2406.02120},
}
Figure