Research map / Large language models / Language, safety and interpretability
Reranking Laws for Language Generation: A Communication-Theoretic Perspective
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Frames LLM generator-reranker systems as multiple-description communication over noisy channels and derives reranking laws predicting how error decays with the number of hypotheses N, validated on code generation (DeepSeek-Coder 7B) and medical machine translation (TowerInstruct 13B).
Problem
Generate-then-rerank LLM pipelines reduce hallucinations and unacceptable outputs by sampling multiple hypotheses, but there is no principled prediction of how error probability decays with the number of hypotheses N, especially with imperfect rerankers and dependent hypotheses.
Approach
Model the generator as a sender transmitting N descriptions through parallel noisy channels and the reranker as a decoder; analyze error probability under Mallows and Zipf-Mandelbrot reranker models and under exchangeable (Beta-coupled) hypotheses, yielding exponential, power-law, or still-error-free asymptotic laws.
Key results
- Under a Mallows reranker with independent hypotheses the error decays exponentially at rate e^{-lambda_eps}, while a perfect reranker gives epsilon^N.
- With Beta-coupled exchangeable hypotheses and a perfect reranker, error decays as a power law O(N^{-beta}) yet remains asymptotically error-free.
- Fitted reranking laws fit the code (MBPP, DeepSeek-Coder 7B) and translation (TICO-19, TowerInstruct 13B) test curves reasonably well, with MBR decoding giving lower failure than QE reranking.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a perfect reranker instead of selecting a hypothesis uniformly at random | Generator-reranker system with independent hypotheses · Independent hypotheses | error probability: \epsilon -> \epsilon^N | Helped |
| Use a Mallows reranker with $\lambda > 0$ instead of a random reranker | Generator-reranker system · Independent hypotheses | error probability: P_\mathrm{err}(N; q) = \mathcal{O}((e^{-\lambda}(1-\epsilon) + \epsilon)^N) | Helped |
| Use a Zipf-Mandelbrot reranker with $\lambda > 0$ and $\gamma < 1$ | Generator-reranker system · Independent hypotheses | error probability: P_\mathrm{err}(N; q) \rightarrow 0 | Helped |
| Use a reranker with mass proportional to $(N-j+1)^r$ | Generator-reranker system · Independent hypotheses | error probability: \mathcal{O}(\epsilon) -> \mathcal{O}(\epsilon^{r+1}) | Helped |
| Use a ranker with mass proportional to $(N-j+1)$ | Generator-reranker system · Independent hypotheses | error probability: \mathcal{O}(\epsilon) -> \mathcal{O}(\epsilon^2) | Mixed |
| Use a perfect reranker with Beta-coupled exchangeable hypotheses | Generator-reranker system · Exchangeable hypotheses with Beta coupling | error probability: P_\mathrm{err}(N; q) = \mathcal{O}(N^{-\beta}) | Helped |
| Use MBR decoding instead of QE reranking | TowerInstruct 13B · TICO-19 | failure rate | Helped |
| Fit separate reranking laws for each language pair | TowerInstruct 13B reranking · TICO-19 EN→PT, EN→ES, EN→RU test sets | fit quality | Mixed |
Surprising findings
- A reranker only slightly better than random (eta_j proportional to N-j+1) is not enough: error drops to O(epsilon^2) but is not eliminated.
- Under dependence (Beta coupling), error decays only as a power law rather than exponentially, slowing reranking gains.
Limitations
- Convergence rates are proven only for Mallows rerankers; the Zipf-Mandelbrot and general dependent cases are asymptotic only.
- No simple recipe to verify whether Mallows or Zipf-Mandelbrot models fit concrete rerankers, nor how to choose the prior p(tau).
- Errors are rare for large N, causing statistical noise in fitted curves; the binary acceptable/unacceptable framing excludes continuous metrics.
Experimental setup
Datasets: MBPP TICO-19 SVAMP StrategyQA
Benchmarks: MBPP TICO-19 SVAMP StrategyQA
Metrics: log failure rate error probability vs N
Baselines: majority voting MBR decoding quality estimation reranking
Builds on: Mallows model entmax multiple description source coding
Closest papers by meaning
- Improving Open-Ended Text Generation via Adaptive Decoding (ICML 2024 · similarity 0.88)
- Learning How Hard to Think: Input-Adaptive Allocation of LM Computation (ICLR 2025 · similarity 0.87)
- Language Ranker: A Lightweight Ranking framework for LLM Decoding (NeurIPS 2025 · similarity 0.86)
- MBR and QE Finetuning: Training-time Distillation of the Best and Most Expensive Decoding Methods (ICLR 2024 · similarity 0.86)
- Reflection-Window Decoding: Text Generation with Selective Refinement (ICML 2025 · similarity 0.86)
- The Consensus Game: Language Model Generation via Equilibrium Search (ICLR 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.