Language Model Decoding as Likelihood–Utility Alignment

Findings of the Association for Computational Linguistics: EACL 2023, pages 1455–1470 May 2-6, 2023 ©2023 Association for Computational Linguistics Language Model Decoding as Likelihood–Utility Alignment Martin Josifoski,♢ Maxime Peyrard,♢ Frano Rajic,♢ Jiheng Wei,♣ Debjit Paul,♢ Valentin Hartmann,♢ Barun Patra,♠ Vishrav Chaudhary,♠ Emre Kıcıman,♠ Boi Faltings,♢ Robert West♢ ♢EPFL ♠Microsoft Corporation ♣PSL University {martin.josifoski, maxime.peyrard, robert.west}@epfl.ch Abstract A critical component of a successful language generation pipeline is the decoding algorithm. However, the general principles that should guide the choice of a decoding algorithm re- main unclear. Previous works only compare decoding algorithms in narrow scenarios, and their findings do not generalize across tasks. We argue that the misalignment between the model’s likelihood and the task-specific notion of utility is the key factor to understanding the effectiveness of decoding algorithms. To struc- ture the discussion, we introduce a taxonomy of misalignment mitigation strategies (MMSs), providing a unifying view of decoding as a tool for alignment. The MMS taxonomy groups decoding algorithms based on their implicit assumptions about likelihood–utility misalign- ment, yielding general statements about their applicability across tasks. Specifically, by an- alyzing the correlation between the likelihood and the utility of predictions across a diverse set of tasks, we provide empirical evidence sup- porting the proposed taxonomy and a set of principles to structure reasoning when choos- ing a decoding algorithm. Crucially, our anal- ysis is the first to relate likelihood-based de- coding algorithms with algorithms that rely on external information, such as value-guided methods and prompting, and covers the most diverse set of tasks to date. Code, data, and models are available at https://github.com/epfl- dlab/understanding-decoding. 1 Introduction Large transformer-based language models (LMs) have been pushing the boundaries on tasks ranging from natural language generation (Radford et al., 2018) to information extraction (Josifoski et al., 2022), theorem proving (Polu and Sutskever, 2020), code generation (Zügner et al., 2021), and even pro- tein generation (Ferruz et al., 2022). At inference time, these models rely on a decoding algorithm to generate an output. The goal of decoding algo- rithms is to select an output of high utility from Input What is the shortest name of a US president? ..… Training Corpus Text scraped from the Web before 2021 Ja Jo … John Joe … ..… … James … ..… ..… Ja 0.5 mes 0.5 Jo 0.4 hn 0.8 e 0.1 0.25 0.32 0.04 Greedy Beam Search (2 beams) Highest Utility Figure 1: Example of likelihood–utility misalignment. Imagine a fictional LM trained before Joe Biden became the US president. The input asks for the shortest name of a US president. After Joe Biden’s inauguration, this is ‘Joe’, but before, it was ‘John’. Greedy search re- turns ‘James’ since its first token ‘Ja’ has the highest likelihood. Beam search manages to find the highest likelihood sequence ‘John’. Both fail to find the correct answer ‘Joe’ with the highest utility since ‘Joe’ has a very low likelihood. the exponentially large output space. In contrast to the generic language modeling training objective, which is based on the data …

Content truncated to 500 words