Structure-Conditional Minimum Bayes Risk Decoding

Bryan Eikema, Anna Rutkiewicz, Mario Giulianelli

TL;DR

This paper tackles a limitation in how language models select responses, particularly in open-ended tasks where outputs can have diverse underlying structures (like dialogue acts or emotions). They propose new "structure-aware" utility functions for Minimum Bayes Risk (MBR) decoding that better account for this structural variability, leading to more optimal and higher-quality generations.

What Problem Does This Paper Address?

When a language model generates text, it produces a probability distribution over possible sequences. Traditional decoding methods like beam search aim for high probability, but this doesn't always align with human preferences. Minimum Bayes Risk (MBR) decoding offers an alternative by selecting the sequence that minimizes "risk" with respect to a utility function, often based on similarity to other generated sequences. While effective in constrained tasks like machine translation, MBR struggles in more open-ended scenarios (dialogue, instruction-following) where outputs can vary significantly in their underlying structure (e.g., a question vs. a statement, a short answer vs. a detailed explanation). Standard MBR, using generic similarity metrics, can end up selecting a "compromise" response that isn't truly optimal for any specific underlying structure, leading to suboptimal outputs. This paper aims to make MBR more sensitive to this latent structural variability.

Methods

The core contribution is the development of three "structure-aware" adaptations to MBR's utility function:

  • Utility Cut-off: This method introduces a threshold to filter out low-utility comparisons. By limiting the influence of structurally dissimilar candidates, it encourages MBR to focus on more relevant parts of the outcome space.
  • Clustering: This approach explicitly partitions the candidate generations into clusters based on their underlying structure. MBR is then applied within the largest cluster, ensuring the selected response is optimal for the most dominant structural type.
  • Structure Embeddings: Instead of hard clustering, this method uses sequence embeddings that are fine-tuned to capture structural properties. The utility function is then modified to weight candidate comparisons by the similarity of their structure-aware embeddings. This allows for a "soft" bias towards structurally coherent outputs.

The authors also introduce two metrics to evaluate their methods: Cluster Optimality (CO), which measures how often the MBR solution matches the MBR solution conditioned on a specific structure, and Cluster-Optimal Rank Correlation (CORC), which assesses how well the overall ranking of candidates aligns with the structure-optimal ranking.

Datasets

  • Curated Dataset: The authors construct a novel dataset of 3,000 outcome spaces (350,000 candidate generations) by controlling for three types of latent structure: dialogue act, emotion, and response structure. This dataset is designed to simulate hypothetical language models with uncertainty over these structures.
  • Real-world Benchmarks: AlpacaEval and MT-Bench are used to evaluate the proposed methods on actual instruction-following tasks.

Key Insights and Ideas

  • MBR's Blind Spot: Standard MBR, relying on generic similarity metrics, often fails to identify the "best" response when the outcome space has diverse underlying structures. It can pick a "jack of all trades, master of none" response.
  • Structure Matters: Explicitly accounting for latent structure in the utility function significantly improves MBR's ability to select cluster-optimal responses.
  • Soft vs. Hard Clustering: Structure Embeddings, which use a "soft" approach to structural awareness, sometimes outperform hard Clustering, suggesting that subtle structural differences can be better captured without rigidly excluding potentially relevant candidates.
  • Computational Efficiency: The proposed methods add only a modest computational overhead, making them practical for real-world applications.

Key Results

  • Controlled Datasets: On their curated datasets, standard MBR achieved Cluster Optimality (CO) in less than half of the cases. The proposed methods significantly improved this:
  • Utility Cut-off: Increased CO by 11.7% on average.
  • Clustering: Increased CO by 37.3% on average.
  • Structure Embeddings: Increased CO by 38.7% on average.
  • Real-world Benchmarks: On AlpacaEval and MT-Bench, the structure-aware MBR methods showed improvements in win rates against strong baselines (like GPT-4o):
  • MT-Bench (single-turn): Utility Cut-off achieved a notable 13.7 percentage point improvement in win rate over standard MBR.
  • Overall, the methods demonstrated improved generation quality, suggesting their effectiveness in practical scenarios.

Limitations and Future Work

  • Dataset Coverage: The curated dataset, while comprehensive for the studied structures, may not cover all possible structural variations in natural language.
  • Model Assumptions: The evaluation assumes language models accurately represent uncertainty over latent structures, which might not always hold.
  • LLM Judge Imperfections: The evaluation on real-world benchmarks relies on LLM judges (Prometheus), which have known biases and limitations.
  • Alternative Utilities: The study focuses on BERTScore and BLEURT. Future work could explore how task-specific or learned reward models behave with structure-aware MBR.
  • Computational Cost: While minimal, MBR decoding is inherently more computationally demanding than simpler methods. Future research could focus on improving MBR efficiency.
  • Generalization: Further investigation is needed to understand how well structure embeddings generalize to unseen structural variations.

Summary updated

Abstract

Minimum Bayes Risk (MBR) decoding has seen renewed interest as an alternative to traditional generation strategies. While MBR has proven effective in machine translation, where the variability of a language model's outcome space is naturally constrained, it may face challenges in more open-ended tasks such as dialogue or instruction-following. We hypothesise that in such settings, applying MBR with standard similarity-based utility functions may result in selecting responses that are broadly representative of the model's distribution, yet sub-optimal with respect to any particular grouping of generations that share an underlying latent structure. In this work, we introduce three lightweight adaptations to the utility function, designed to make MBR more sensitive to structural variability in the outcome space. To test our hypothesis, we curate a dataset capturing three representative types of latent structure: dialogue act, emotion, and response structure (e.g., a sentence, a paragraph, or a list). We further propose two metrics to evaluate the structural optimality of MBR. Our analysis demonstrates that common similarity-based utility functions fall short by these metrics. In contrast, our proposed adaptations considerably improve structural optimality. Finally, we evaluate our approaches on real-world instruction-following benchmarks, AlpacaEval and MT-Bench, and show that increased structural sensitivity improves generation quality by up to 13.7 percentage points in win rate.
BibTeX
@inproceedings{eikema2025structure,
  author = {Bryan Eikema and Anna Rutkiewicz and Mario Giulianelli},
  title = {{Structure-Conditional Minimum Bayes Risk Decoding}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2025},
}
Figure