Reranking Laws for Language Generation: A Communication-Theoretic Perspective

António Farinhas, Haau-Sing Li, André Martins

TL;DR

This paper reframes the common LLM strategy of generating multiple outputs and reranking them as a communication system problem. They show that this "redundancy" can lead to asymptotically error-free generation, even with imperfect rerankers, and derive "reranking laws" that predict how many hypotheses are needed for a desired error rate. This work provides a theoretical foundation for understanding and improving the reliability of LLM outputs.

What Problem Does This Paper Address?

Large Language Models (LLMs) are powerful but can sometimes produce undesirable outputs like hallucinations or incorrect answers. A common approach to mitigate this is to have the LLM generate several candidate responses (hypotheses) and then use a separate "reranker" to select the best one. While this strategy is intuitive and widely used, there's a lack of theoretical understanding about why it works, how well it works, and how many hypotheses are truly necessary. This paper aims to bridge this gap by providing a theoretical framework to analyze and predict the performance of these generator-reranker systems.

Methods

The authors draw an analogy between generator-reranker systems and communication theory, specifically error-correcting codes. They conceptualize the LLM generator as a sender transmitting multiple "descriptions" (hypotheses) of a message through noisy channels. The reranker acts as the receiver, decoding the message by ranking these potentially corrupted descriptions and picking the most reliable one.

Their core contributions involve:

  • Theoretical Analysis: They analyze conditions under which this generator-reranker system is "asymptotically error-free," meaning the probability of generating an unacceptable answer approaches zero as the number of hypotheses (N) increases. This analysis covers scenarios with independent hypotheses and, importantly, dependent hypotheses (which is more realistic).
  • Reranker Models: They model imperfect rerankers using established statistical ranking models like the Mallows and Zipf-Mandelbrot models. This allows them to quantify the impact of reranker imperfections on the overall error rate.
  • Reranking Laws: Based on their theoretical framework, they derive "reranking laws" that predict the relationship between the number of hypotheses, the reranker's quality, and the resulting error probability.

Datasets

The paper validates its theoretical framework and reranking laws using empirical experiments on two real-world tasks:

  • Text-to-Code Generation: Using the MBPP dataset.
  • Machine Translation of Medical Data: Using the TICO-19 dataset.

They also mention experiments on mathematical and commonsense reasoning benchmarks in the appendix.

Key Insights and Ideas

  • Redundancy is Key: The core idea is that generating multiple hypotheses (redundancy) is a powerful strategy for reducing errors, mirroring how redundancy is used in communication channels to combat noise.
  • Asymptotic Error-Free Generation: Even with imperfect rerankers (not just perfect ones) and statistically dependent hypotheses, the generator-reranker system can achieve an acceptable output with high probability as the number of generated hypotheses increases.
  • Reranking Laws Quantify Performance: The derived "reranking laws" provide a quantitative way to understand how many hypotheses are needed to achieve a target error rate, given the quality of the generator and reranker. This is crucial for practical deployment.
  • Communication Theory Analogy is Powerful: Framing LLM generation as a communication problem provides a robust theoretical lens to analyze and improve these systems.

Key Results

The paper presents several theoretical results and empirical validations:

  • Independent Hypotheses: With independent hypotheses and a perfect reranker, the error probability decays exponentially with the number of hypotheses (N). Even with imperfect rerankers (Mallows and Zipf-Mandelbrot models), the protocol remains asymptotically error-free, with error probabilities decaying exponentially or as a power law.
  • Dependent Hypotheses: When hypotheses are exchangeable (a more realistic scenario), the error probability still decays, but typically as a power law rather than exponentially, even with a perfect reranker.
  • Empirical Validation: The authors fit their derived reranking laws to experimental data from text-to-code generation (DeepSeek-Coder 7B) and machine translation (TowerInstruct 13B). The models show a reasonable fit to the empirical data, demonstrating the practical utility of their framework. For instance, in machine translation, they achieved good fits for various language pairs.

Limitations and Future Work

  • Asymptotic Guarantees: The theoretical guarantees are asymptotic, meaning a large number of hypotheses (N) might be needed for the error rate to become sufficiently low. The paper notes that the convergence rates can vary.
  • Reranker Model Fit: Determining if specific real-world rerankers precisely match the Mallows or Zipf-Mandelbrot models is not straightforward.
  • Empirical Fit Imperfections: While the models fit the empirical data reasonably well, the fit is not always perfect, especially on test sets. The authors attribute this to potential shifts in score distributions.
  • Continuous Quality Metrics: The current framework primarily focuses on binary acceptable/unacceptable decisions. Extending it to continuous quality metrics (like COMET scores) is a promising but challenging direction for future work.
  • More Efficient Designs: The paper suggests exploring more powerful error-correcting code designs (beyond simple repetition) to inspire more efficient reranking strategies.

Summary updated

Abstract

To ensure large language models (LLMs) are used safely, one must reduce their propensity to hallucinate or to generate unacceptable answers. A simple and often used strategy is to first let the LLM generate multiple hypotheses and then employ a reranker to choose the best one. In this paper, we draw a parallel between this strategy and the use of redundancy to decrease the error rate in noisy communication channels. We conceptualize the generator as a sender transmitting multiple descriptions of a message through parallel noisy channels. The receiver decodes the message by ranking the (potentially corrupted) descriptions and selecting the one found to be most reliable. We provide conditions under which this protocol is asymptotically error-free (i.e., yields an acceptable answer almost surely) even in scenarios where the reranker is imperfect (governed by Mallows or Zipf-Mandelbrot models) and the channel distributions are statistically dependent. We use our framework to obtain reranking laws which we validate empirically on two real-world tasks using LLMs: text-to-code generation with DeepSeek-Coder 7B and machine translation of medical data with TowerInstruct 13B.
BibTeX
@inproceedings{farinhas2024reranking,
  author = {António Farinhas and Haau-Sing Li and André Martins},
  title = {{Reranking Laws for Language Generation: A Communication-Theoretic Perspective}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2024},
  url = {https://openreview.net/forum?id=bKwizT1Or9},
}
Figure