Abstract
A critical component of a successful language generation pipeline is thedecoding algorithm. However, the general principles that should guide thechoice of a decoding algorithm remain unclear. Previous works only comparedecoding algorithms in narrow scenarios, and their findings do not generalizeacross tasks. We argue that the misalignment between the model's likelihood andthe task-specific notion of utility is the key factor to understanding theeffectiveness of decoding algorithms. To structure the discussion, we introducea taxonomy of misalignment mitigation strategies (MMSs), providing a unifyingview of decoding as a tool for alignment. The MMS taxonomy groups decodingalgorithms based on their implicit assumptions about likelihood--utilitymisalignment, yielding general statements about their applicability acrosstasks. Specifically, by analyzing the correlation between the likelihood andthe utility of predictions across a diverse set of tasks, we provide empiricalevidence supporting the proposed taxonomy and a set of principles to structurereasoning when choosing a decoding algorithm. Crucially, our analysis is thefirst to relate likelihood-based decoding algorithms with algorithms that relyon external information, such as value-guided methods and prompting, and coversthe most diverse set of tasks to date. Code, data, and models are available athttps://github.com/epfl-dlab/understanding-decoding.