From Decoding to Meta-Generation: Inference-time Algorithms for Large Language Models
Authors: Sean Welleck
Amanda Bertsch
Matthew Finlayson
Hailey Schoelkopf
Alex Xie
Graham Neubig
Ilia Kulikov
Zaid Harchaoui
Venue: Accepted by TMLR ()

Abstract: One of the most striking findings in modern research on large language models (LLMs) is that scaling up compute during training leads to better results. However, less attention has been given to the benefits of scaling compute during inference. This survey focuses on these inference-time approaches. We explore three areas under a unified mathematical formalism: token-level generation algorithms, meta-generation algorithms, and efficient generation. Token-level generation algorithms, often called decoding algorithms, operate by sampling a single token at a time or constructing a token-level search space and then selecting an output. These methods typically assume access to a  language model's logits, next-token distributions, or probability scores. Meta-generation algorithms work on partial or full sequences, incorporating domain knowledge, enabling backtracking, and integrating external information. Efficient generation methods aim to reduce token costs and improve the speed of generation. Our survey unifies perspectives from three research communities: traditional natural language processing, modern LLMs, and machine learning systems.

Published in Transactions on Machine Learning Research (11/2024)
From Decoding to Meta-Generation Inference-time Algorithms for Large Language Models
Sean Welleck Carnegie Mellon University
wellecks@cmu.com edu
Amanda Bertsch Carnegie Mellon University
abertschutcs. cmm.eeessssm.............
Matthew Finlayson"
mftnlays@uscc.cmm edu
University of Southern California
Hailey Schoelkopf EleutherAI
haileyBeleuther.eg ot
Alex Xie Carnegie Mellon University
alezz@tcs.
Mezz@osscmmuco cma, edu
Graham Neubig Carnegie Mellon University
gneubig@emau.c edu
Ilia Kulikov Meta FAIR
kulikov@mett..com com
Zaid Harchaoui University of Washington
zaid@ow. edu
*Co-second authors
Reviewed OpenReview:
Abstract
One of the most striking findings in modern research on large language models (LLMs) is that scaling up compute during training leads to better results. However, less attention has been given the benefits of scaling compute during inference. This survey focuses these inference-time approaches. We explore three areas under unified mathemati- cal formalism: token-level generation algorithms, meta-generation algorithms, and efficient generation. Token-level generation algorithms, often called decoding algorithms, operate by sampling a single token at a time or constructing token-level search space and then selecting an output. These methods typically assume access to a language model's logits, next-token distributions, or probability scores. Meta-generation algorithms work on partial or full sequences, incorporating domain knowledge, enabling backtracking, and integrating external information. Efficient generation methods aim to roduce token costs and improve the speed of generation. Our survey unifies perspectives from three research communties: traditional natural language processing, modern LLMs, and machine learning systems.

---

Contents
Introduction
3
2
Preliminaries
4
2.1
The user's goal in generation
5
2.2
The modeling problem
6
Token-level generation algorithms
7
3.1
MAP decoding algorithms
3.2
Sampling and adapters
3.3
Token-level sampling adapters
3.4
Controlled generation
3.5
Constrained decoding
12
Meta-generation algorithms
13
4.1
Chained meta-generators
13
4.2
Parallel meta-generators
4.3
Step-level search algorit.ms
19
Relinement algorithms
21
Incorporating external information
23
5.1
Multiple models
23
5.2
External environment information
24
Token cost and performance analysis
24
Token budget
25
6.2
Scaling the token budget to improve performance
................................
26
6.3
Minimizing the token budget
27
6.4
Compute optimal inference
27
6.5
Dependence on the underlying generator(s)
Speeding generation
27
7.1
Background
28
7.2
Speeding up the generator
29
Speeding up meta-generation algorithms
31
4
Libraries and tools for fast generation
32
Discussion: why use sophisticated generation algorithms?
32
Conclusion
34
2

---

Published in Transactions on Machine Learning Research (11/2024)
Meta-gena generator
Generation algorithms
def generate_proof theorem): strategies =
Maximization
Sampling
"Prove by contradiction. An",
Controlled generation
"Prove by induction. An",
]
Mleta-generation
candidates =
Programmatic patterns
External information
Generator
11m. generate theorem)
for strategy in strategies for sample in range(5)
Multiple models
Tools Environmentss
]
output = 11m. generatee
3. Efficient generation
"Which the proofs is best?\n" "An". join(candidates)
Optimizing token cost
Speeding up generators
Speeding up meta-generators
return output
Figure 1: Generation algorithms produce oulput lext using a language model. Mela-generation algorithms are programs that interleave calls to generation algorithms with control flow and external information, yiclding text. Our survey covers generation algorithms and their goals ($3), meta-generation patterns and sources of external information ($5). and efficiency in terms of token cost ($6 and speed ($70.
Introduction
One of the most striking findings in modern research on large language models (LLMs) is that, given model and dataset of sufficient scale, scaling the compute used at training time leads to better final results (Kaplan et al. 2020 Hoffmann et al. 2022). However, there is another, lesser-mentiondd scaling phenomenon, where adopting more sophisticated methods or scaling compute at inference time (Jones 2021 can result in substantially better outputs from LLMs. This survey focuses on these approaches by exploring three connected themes: token-level generation algorithms, meta meta- generation algorithms, and efficient generation.
Token-level generation algorithms, often called decoding algorithms, have rich history in natural language processing, ranging from classical greedy decoding and beam search to modern sampling algorithms such nucleus (Holtzman et al.) (2020) and s-smmplnn (Hewitt et al. 2022h. These methods operate by sampling one token at a time or constructing a token-level search space. They assume varying levels of accoss to a language model'ss internals, such as logits, nexl-token distributions, or probability scores.
Recently there has been growing interest in meta-generation adgorithms-algon algorithms that operate on partial full soquences, and treat the LLM
black box that is called part of larger generation program [Figure 1 Khattab et al. (2022); Dohan et al. (2022): Schlagg et al. (2023)). ). For example, meta-generation algorithm for solving a math problem might generate multiple solution paths, evaluate the solutions with a calculator, then select the most common answer. Meta-generators can increase the compute resources devoted to generation by making multiple model calls, augmenting the model with search algorithms (Yao et al. 2023 Madaan al. 2023). or incorporating external data sources. Doing so has seen success improving lask performance (c.g., problem solving (Lewkowyez al., 2022)) and stecring the output distribution (c.g., with human preferences (Stiennon et al. 20200), , and may oller a way to overcome linitations of standard LLMs such error accumulation (Dziri et al. 2023) and computational capacity (Merrill & Sabharwal 2024 Morcover, meta-gencration research is widely accessible, as it often only requires black-box L.M access.
Finally, generation needs lo be fast and cost-effective. Fast generation becomes increasingly challenging as models grow in size, while cost becomes a critical factor in meta-generation algorithms that call models many times. On the other hand, meta-generation algorithms open new kinds of shared computation that can be leveraged for improved efficiency. As result, there is growing interest in efficient generation algorithms that speed up generation and reduce token costs by drawing ideas from machine learning systems and
3

---

Published in Transactions on Machine Learning Research (11/2024)
related areas. Efficient generation in turn expands the frontier of algorithms that are feasible to experiment with and develop, leading to a virtuous cycle of algorithmic development.
Our survey provides a unified treatment of these three themes: token-level generation algorithms, meta- generation algorithms, and techniques for making generation fast and cost-effective. We integrate ideas from traditional natural language processing, modern I.LMs, and machine learning systems, and present a mathematical formalism that includes both classical generation algorithms and modern meta-generators. This unified view is particularly important the field expands. For example, practitioners working on novel meta- generation algorithms may benefit from learning about the historical context of generation algorithms or practical efficiency constraints, while rescarchers interested in efficiency may benefit. from learning about major algorithmic patterns. More broadly, we aim to promote further research on inference- approaches.
Several prior surveys have focused on training- time methods for better text generation (Li al., 2021 Lu al., 2018). Wiher et al. (2022) presents a detailed analysis of a smaller set of decoding strategies, while Zarrieß al. (2021) spotlight token-level methods, with particular focus on considerations for encoder-decoder models. In parallel, several surveys have addressed prompting and related
Comparison to existing surveys.
methods (Liu et al. 2021b; Sahoo et al. 2024), though these works do not address token-level methods.
Recent surveys have also considered strategies for speeding up inference (Chitty- Venkata et al. 2023 Miao
et al. 2023a Khoshnoodi et al. 2024 Wang et al. (0224a.. However, these works focus primarily on token- level generation, not mete-genneation; as a result, the discussion of inference-time compute-performance tradeoffs is limited. Our survey unifies and draws connections across these three areas. Finally, Xiao et al.)
(2023) focus on non-autoregressive generation, while our survey focuses on autoregressive generation.
This paper provides a survey of algorithms for token-level generation, meta-generation, and efficient generation, summarized in Figure I First, we consider why we use generation algorithms at all. Generally, a user's intent is to surface a high-quality output from the model, which we formalize and discuss in $ Readers who would like to review terminology or follow the mathematical formulation of the survey in depth should start in this section. Next, we discuss token-level generation algorithms in detail in $ Most algorithms referred to as "decoding algorithms" in the literature are covered in this section. We discuss these methods' thcoretical motivation, practical impact, commonalities, and provide unified frame for discussion. These methods generally require some degree of access to the model's internals.
Roadmap.
A growing set of methods operate over partial or full sequences rather than individual tokens. These meta- generation algorithms have emerged from several communitiles, including researchers interested in designing new decoding algorithms or prompting methods, as well as researchers interested in language model alignment and reasoning. Works from these communities often have different motivations and use different terminology. We present unified picture in $ classifying them according to their programmatic structure (e.g,, parallel generation, search, refinement), and discussing their motivations.
In addition to wanting high-quality output, we often care about the efficiency of generation. We consider two definitions of efficient generation. In $ we consider the token cost of generation algorithms, which is especially relevant for studying cost-performance tradeoffis as the amount of computation allocated to gener- ation is scaled up, and for those using APl-access models that charge by the token. In 7 we discuss methods for speeding up generation primarily from a systems perspective, where access to the model weights is as- sumed and latency and throughput. are the key considerat ions. In this section, we draw upon work primarily from the machine learning systems (MLSys) community. The section serves as both introduction to this area for machine learning researchers whose work does not focus systems, and practical exploration of tools for speeding up generation. We include a review of libraries that implement the described techniques.
We conclude the survey by discussing takeaways, broader directions, and future work in $
2 Preliminaries
Generation algorithms are used to produce outputs from a trained language model. Language models are probabilistic models over sequences, po(y)z), and most generation algorithms attempt to either find highly probable sequences or sample from the model's distribution. A natural question is why are sophisticated
4

---

Published in Transactions on Machine Learning Research (11/2024)
Symbol
Name
Explanation/examppl
pe
Model distribution
The conditional distribution defined by an LM with parameters Assigns LM scores to tokens. Normalizing gives po-
50
Model logit function
Р.
Training distribution
The target distribution for which an LM was trained. of outputs, assigns an acceptability score.
Acceptability function
Takes a
Reward function
Proxy for A.
Scoring function
Proxy for r. Also: value function, learned verifter, reward model. E.g,, sampling algorithm for LM, or a refinement algorithm.
A generalor
g(11>)
Generator distribution
The distribution obtained by applying a generator to an input x. E.g., the distribution of utterances in the style of helpful assistant. E.g., deterministic generator such as greedy decoding, or a calculator.
9-
Target distribution Deterministic function
f
A generator's parameters
E.g,, temperature, number of samples.
Distance function
Measures distance, e.g., KL divergence, between two distributions. The set of possible LM outputs, i.e., strings.
y
Output space
V
Vocabulary
The set of tokens that make up sequences in y.
P())
Probability distributions
The set of probability distributions over outputs.
yt
Current token
The token at index in a sequence y E y
g<t
Prefix, or context
The tokens preceeding index a sequence y E y.
Table 1: An overview of symbols for convenience.
generation algorithms needed at all? For example, we might imagine that simply sampling once from the model's unmodified output distribution, y po(ula) is sufficient. We begin by defining some terminology (summarized in Table D and then present general goals of generation which shed some light on this question.
2.1 The user's goal in generation
When user is generating outputs with language model, it may be with or more goals in mind. The user may want output that is as high quality possible for some notion of quality, such as correct answer to a math problem or a factual and well-written summary. The user may want multiple outputs, such as alternative solutions to a problem or multiple summaries to read through and synthesize. In general, users now access language models through general-purpose text-in text-out APIs, making it impossible enumcrate all of the specific use cases or goals that a user might have.
As result, to formalize overall goal for generation, will need to take fairly general perspective. We assume that the user has some underlying measure of "acceptability" for any set S of outputs, A(S) R. For example, a single sequence set may have high acceptability if it represents a correct solution to problem, while in a different context a set S may have high acceptability if it balances some notion of diversity with some notion of quality. The acceptability scores, when normalized, form a probability distribution that we call the target distribution qu,
q. (S( x A(S).
(1)
Next, we treat generating outputs with a language model as sampling from generator $ S~ g that produces a set of sequences cach time it is called. Finally, we assume that a user wants the distribution of outputs from the generator to be "close" to the distribution of their acceptability scores according to some proximity measurement. between distributions. An ideal generator g would thus satisfy:
arg min d(g..g). g
(2)
In practice, we typically do not. know how to measure the user's acceplability nor their desired notion of proximity, let alone how to design a generator that is guaranteed to produce outputs with high acceptability, At a high level, the remainder of this survey can be soen as surveying ways to design generators that optimize some proxy of acceptability in an efficient way. For example, some algorithms will try produce a single output that is acceptable with language model's probability as proxy of acceptability. Other algorithms
5

---

Published in Transactions on Machine Learning Research (11/2024)
will try to directly sample from some target distribution that we may interpret being proxy to user's target distribution. To begin with, let us go into more detail on what "generator" is, starting with the definition of a language model, a generation model, and a generation algorithm.
2.2 The modeling problem
Language models. Let Po be a language model that approximates the distribution pa, denoted pa s p.. We consider autoregressive language models pa (y)(z) = II-=1 from vocabulary V. Each conditional distribution is of the form, po po(1Vee.,2) 2) = exp(sa( ()).,)))) where so(-Iv<e, a E R are referred to logits and Z Σ/' exp (sa x-))e,)),)) We henceforth refer to model of this form as simply language model (LM) for brevity.
L po(urlves #), where is a sequence of tokens
A generation model associated with a language model po is a function : X' x θ x + - P()) that maps an input x E X, model pa with 0 E O, and any additional parameters & E to a probability distribution over outputs, g rx; Po: 6) E P()).
Calculating the probability distribution over outputs ((yla; po, Ø) E P())) is in most situations analytically intractable. One can use the generation algorithm in order to obtain independent or dependent samples from g(v|2; Po: σ) E P())); we refer to this process generating, y g zz; p). We will also refer to as a generator, and the distribution obtained by applying to an imput as a generation distribution. Generation algorithms may be deterministic or stochastic. We denote generating from a deterministic generator as y = (>; pe: p), where / the deterministic generator. While met to maximize a scoring function are often deterministic and methods for generating sets of outputs are often stochastic, practice each kind of method can be used toward either goal.
Let us return to the general goal of generation that formulated above. For notational simplicity, let us consider generating a single sequence, i.c. S = (v). In practice, we can design a generation algorithm to maximize some proxy r(-) of acceptability:
arg max r (g.
where r P()) x P(Y) + R is some reward function between distributions. We group generation methods into 3 categories: hods for maximization (.2.1 sampling from the model ($ (.....) and sampling from target distribution 2..33 These are special cases of (3). For maximization, q- for a scoring function v, and we have r(g,,9) Ey-=g-(Ulo)) For sampling from target distribution, is divergence between the target distribution and the generation distribution.
2.2.1 Maximization
We define decoding as the process of maximizing a score either deterministically or with high probability: Definition 1 (Score maximizing algorithm). A score maximizing algorithm for score u: S -+ R refers to algorithm that approximates:
f Φ) arg max v(S),
(4)
SEPO")
where P()) the set of all subsets y. Decoding algorithms can be greedy algorithms, concave maximiza- tion algorithms, combinatorial optimization algorithms, stochastic algorithms.
2.2.2 Sampling
Some algorithms are designed to sample from a distribution. The samples can then be used for any purpose, such for maximizing some task-specific metric (e-g., metric that balances quality and diversity). Definition 2 (Sampler for 4(pa)). A sampler for g(po) gives a sample from some distribution tp proportional to (Po)), where q is a map between probability distributions:
y Up (y)x)))
(5)
6

---

Published in Transactions on Machine Learning Research (11/2024)
V1 ~ po(-)
U2 ~ po(- |1a)
Va ~ ~p-l 922)
Va po(- yaa)
boyfriend
boyfriend
boyfriend
boyfriend
is
is
y
Karma
Karma
Karma
Karma
my
my
my
my
11
$2
83
$4
Figure 2: Sampling algorithms choose the next token at each time step 8; by sampling from the conditional distribution pe(- ya-1) and appending to the context.
2.2.3 Sampling from specified target distribution
In some cases we can specify which target distribution q. an algorithm is aiming to sample from.
Definition 3 (Sampler for a larget distribution). A generator is called a sampler for target distribution g. if it approximates:
max DKL (11)))))19(111 o))
(6)
An optimal sampling algorithm for yields an unbiased sample q. (-1x).
Next, will examples of algorithms that achieve these goals by generating token-by-token.
3 Token-level generation algorithms
In this section, we discuss representative methods that operate on the token-level (o.g., by sampling single token al time, or constructing token-level search space and then selecting an output at the end).
Methods in this category generally assume access to language model's logits, next-token distributions, probability scores. These methods will later be treated as black boxes that are called by meta-generators.
3.1 MAP decoding algorithms
When faced with the question of what sequence to choose from the distribution defined by language model, a natural objective is choose the most likely sequence. Several popular decoding algorithms therefore attempt to find generation that maximizes po (y (z), referred to maximum a-posteriori (MAP) decoding. Definition 4 (MAP decoding algorithms).
MAP decoding algorithm approximates:
[x; po, +) = arg max po (y((x))
yEY
The term MAP comes from viewing Po as a posterior over outputs y given the observed input x, and decoding comes from information theory.
Greedy decoding. Arguably the simplest MAP decoding algorithm is greedy decoding, which generates a sequence .1......8 fr by recursively selecting the highest probability token from the next-token distribution:
J = arg max po
(8)
for 1,..., T, with T' determined by a stopping condition (e.g., a fixed T' or y including a certain string). Greedy decoding is an opprozimate MAP decoding algorithm, meaning that it finds sequence that is not
1 Any divergence with the property that q. q iff d suitable.

---

Published in Transactions on Machine Learning Research (11/2024)
necessarily maximizer of 7
Specifically, it approximates as:
T II
arg max (o(()))
= arg max (ur Ur E 1=1
pa (v ()),,)
(9)
NEy
01 arg max (o(11 ... ,0 = arg max po(vrleer. vreV
(10)
BIEV
Despite its naive approximation, greedy decoding is a widely-used generation algorithm. For instance, it is used in Google's Gemini report (Gemini Team al. 2023) and is available on typical language model APIs.
Other MAP decoding algorithms. Several algorithms have been designed that typically return better approximations (i.e., more probable sequences) than greedy decoding. Tn the context of neural sequence- to-sequence models, beam search [Graves] 2012 Sutskever et al. 2014) is a widely-studied MAP decoding algorithm. It maintains data structure of multiple prefixes yet at cach generation step, expands each prefix with each possible next-loken, yer Dtt scores each expanded prefix with po o y)(r), and retains the top- expanded prefixes for the next iteration. This can be seen as a generalization of greedy decoding, which expands only a single prefix. In practice, beam search has been shown to improve upon greedy decoding in terms of downstream task performance in many settings (e.g., Sutskever et al.] (2014); Freitag & Al-Onaizan (2077; Kulikov et al. (2019)) ) It has several variations and generalizations that we will return to when we take the perspective of generation as search ($4.)). Although the space of possible outputs is extremely large, it is some possible to find an enact MAP solution (i.e., a sequence that maximizes 77). For instance, Stahlberg & Byrne (2019) combine elements of beam search and depth-first search to perform exact search with machine translation models, which was improved upon in Stahlberg et al. (2022).
Pitfalls of MAP decoding. Despite its popularity, several studies suggest that the MAP decoding objec- tive is not desirable (Meister et al.] 2020). Empirically, MAP decoding has a tendency to produce degenerate results. For example, Koehn & Knowles (2017 found that wide beam search (which approaches exact MAP decoding in the limit) degrades neural machine translation (NMT) outputs by favoring shorter outputs. In fact, Stahlberg & Byrne (2019) found that exact MAP decoding often returned the empty sequence in NMT. Length normalization (e.g., dividing the log-probability of the sequence by its length) can mitigate MAP decoding's tendency to favor shorter sequences (see Murray & Chiang, 2018), but this is only a heuristic and does not fully counteract degradation for the largest beam sizes (Kochn Knowles (2017). Approximate MAP decoding, o.g., greedy, can also fail by getting trapped in repotitive sequences (Holtzman et al. 2020;
Welleck et al. 2020: Fikema & Azin 2020
There are several explanations for degenerate behavior in MAP decoding, a phenomenon known the inadequacy of the mode (Eikema 2024). Some studies attribute degenerative phenomena in MAP decoding to the tendeney of the most. likely generations to accumulate so little probability that the mode becomes arbitrary due to small errors in probability estimation (Eikema & Aziz 2020 Stahlberg et al. 2022). In an alternative explanation, |Missee et al. (2023b) use inormation-theorette analysis to show that MAP decoding generations often fall outside of the typical set of sequences in the language model's distribution. To illustrate how this occurs, consider that the most probable outcome of 100 flips of slightly biased coin (with 0.51 probability of heads, 0.49 probability of tails) is a sequence of 100 heads. However, this result would be atypical; close-to-even mix of heads and tails would be more typical (Dieleman 2020).
Unrcasonable effectiveness of approximate MAP dccoding. Despite the drawbacks of MAP docod- ing, rough approximations of MAP decoding remain popular in the forms of greedy decoding and narrow beam search. For example, (Shi et al. (2024a] study Llama language models and find that beam search per- forms well on input-output tasks such as translation. |Misseer et al. (2020) hypothesize that these decoding methods are effective because they inadvertently enforce nnformation-theoreed patterns that are characteris- tic of human text. On the other hand, the MAP objective can limit diversity, and beam search in particular can incur large computational cost. Increasingly, practitioners using an inference library or language model API may instead turn to algorithms that efficiently sample from the model 2 which we describe next.
For example, the uidely-used Open AT API does not support beam search.
8

---

Published in Transactions on Machine Learning Research (11/2024)
3.2 Sampling and adapters
A popular alternative to the MAP objective is to sample directly from the language model's distribution ())a))))
Ancestral sampling. The most basic sampling algorithm for Po is motivated by the fact that autoregres- sive models decompose sequence probabilities into a product next-token conditionals:
l
po(y|=) = II po (x)l
(11)
where y = (y1...., Mlvl) and ye are individual tokens. As shown in Figure 2 sampling from this model can be done recursively,
yo (o
(12)
where yo is a given starting token, and the algorithm terminates upon reaching a particular token a given length. The result is mathematically equivalent to sampling a sequence directly from Pe(- 2) and is
known as ancestral sampling. Other algorithms such as speculative sampling (Leviathan et al. 2022 aim to
sample from Py more efficiently, which we will discuss in more detail later in the review ($7
Sampling, MAP, and the diversity-coherence trade-off. Ancestral sampling avoids many of the degenerate behaviors of MAP decoding, such repetition traps, and introduces more diversity into LM generations. However, ancestral sampling can suffer from incoherence, i.e., over-sampling highly-umlikely tokens due model error [Zang et al. 2021). Hewitt et al. (0022) hypothesize that this occurs because perplexity-based loss functions encourage language models to over-cstimate the probability of unlikely to- kens to avoid large loss penalties (a behavior called mode-seeking). Alternatively, Finlayson el al. (2024a) hypothesize that constraints imposed by the LM's output layer, i.e., the softmax bottleneck (Yang et al. 2018), cause model errors, and propose a method, basis-aware truncation (BAT), avoid these errors.
Balancing the civereet tradeoff. Several decoding strategies attempt to balance the diversity-coherence tradeoff by interpolating between greedy and ancestral sampling. These include mu- cleus (Holzzman et al. 2020), top-k (Fan et al. 2018), and 1/- and e-sampling (Hewitt et al. 2022 which use various heuristics to choose threshold at each time step and only sample tokens with probability greater than the threshold. Another approach, temperature sampling (Ackley et al.) 1985 Hinton et al. 2015), scales the LM logits to interpolate between greedy sampling and uniform sampling (sctting all token probabilities equal), which can be useful when one wants more diversity than ancestral sampling offers.
3.3 Token-level sampling adapters
Except for beam search, all of the token-level sampling methods discussed so far can be viewed as sampling adapters dt (Meister al. 2023a which adjust each next-token distribution,
Y/ ~ (pp((wll
(13)
Example (Temperature sampling adapter). Temperature sampling adjusts the distribution by dividing the logits by scalar lemperature parameter T:
(vllVecr,;po... 7) exp xs)().,))/TT.
(14)
Sending T to yields greedy decoding, == yields ancestral sampling, and t > 1 approaches uniform sampling (all tokens have the same probability).
Many other token-level decoding methods can be cast as sampling adapters, including methods that re- weight logits with outputs from another model (Liu al.] 2021a Li et al. (2023a), and a variety of other transformations summarized in Table 2 Many of these token-level generation algorithms assume access to
9

---

Published in Transactions on Machine Learning Research (11/2024)
Method
Purpose
Adapter
Extrinsic
Aucestral sampling
y ~ Pe
Temperature sampling
y ((p))
Rescale
Greedy decoding
y < max Po
Argmax (temperature-> 0)
Top-k sampling bd
y ~ ((p))
Truncation (top-k)
Nucleus sampling
36
y ~ g(pe)
Truncation (cumulative prob.)
Typical sampling
y ~ q(pe)
Truncation (entropy)
Epsilon sampling
82
y ~ ((ps)
Truncation (probability)
sampling S2
y ~ ((p))
Truncation (prob. and entropy) Truncation (adaptive top-k) Truncation (linear program)
Mirostat decoding
11
Target perplexity
Basis-aware sampling
57
y ~ a(po)
L.P Solver
Contrastive decoding
124
y ~ p(p))
log Por log pe and truncation & pa (po1 (Po-) (po por)"
Model por
DExperts 187
y ~ c)(
Models Pe 1 -Pa-
Inference-time adapters
146
y q, r(v)
Model Pe'
Proxy tuning 138
y ~ (-12,,)))
< pa (Do+ /Ps-)
Models Po+:
Table 2: Survey of token-level generation. r(y) is a scalar reward function. a control attribute. Extrinsic refers to model or solver separate from the underlying language model pø-
the language model's next-token distributions. In practice, next-token distributions are increasingly provided by common generation APIs, both for practical reasons and for security (Finlayson et al. 2024b: Carlini et al. 2024).. Instead, token-level algorithms are often implemented by the API provider, and used by setting hyperparameters (e.g., setting a temperature T).
Adapters for statistical control. Several decoding methods use sampling adapters to control the statis- tical and information-thcorcti propertics of model outputs and align them with those of human text. These include locally typical sampling (Meister et al. 2023b), which aims to sample from the LM distribution's typ- ical set (MacKay 2004); and mirostat sampling (Basu et al.) 2021). which attempts to match the perplexity of the generated text to the expected perplexity under Zipf's law (Zipf) 1999 Powers 1998). Intriguingly, (Shi et al. (0024a) evaluate Llama models with variety of adapters (temperature, top-k, top-p, 7), Mirostat, and typical sampling), and find definitive best method for the evaluated open-ended text generation tasks. Furthermore, temperature sampling usually outperformed the other adapters in input-output tasks such code generation and translation. In general, which adapter to use remains an open question.
Autoregression and lookahead adapters. Token-level algorithms generate from left-to-right, meaning that they generate each token without knowing the eventual identity of tokens to the right. Several algorithms have incorporated various heuristic scores v(ygr) that adjust the next-token distribution using information from potential future tokens. This includes explicitly generating several tokens ahead (e.g., Lu et al. (2022) Leviathan et al. (2022]), or learning a function (V(e) that predicts a property of full sequence (e.g., its aid in satisfying sequence-level criteria.
style score or correctness) Yang & Klein 2021 Doing
Distribution adjustment with another language model. Some algorithms adjust the next-token distribution using another language model. This can arise from several motivations, including removing abnormalities in the model's next-token distributions (Li et al. 2023a speeding up generation (Leviathan
et al. 2022), or shifting the generation distribution to one with property (e.g., style) (Liu et al. 2021a
3.4 Controlled generation
Many scenarios can be framed as aiming to sample from language model's distribution modulated by sequence-level criterion c(y) (Korbak et al. 2022a
Hu et al. 2024 Zhao et al. 2024a
g. pa x)(()))))))
(15)
10

---

Published in Transactions on Machine Learning Research (11/2024)
For example, c(y) may assign high values to sequences with particular style, or low values to sequences with toxic content or buggy code. Another way of phrasing (15) is sampling from particular energy-based model (LeCun et al. 2006; Khalifa et al. 2021 We discuss three examples based on the structure of c(y).
Classifier. In some cases cly) is a classifier p(a/z, y), which predicts the probability that contains an "attribute" a, such as a style or non-toxicity. The goal is then to sample from:
9x x po(vlz)p(a(z:, v)
(16)
where 3 is hyperparameter assigning more weight to the classifier at higher values of B. Various generation algorithms have been developed for this purpose, such as approximations based on reweighting next-token distributions with other language models (Liu et al. 2021a). reweighting with a learned classifier that approx-
imates the sequence-level classification Pa(a Uet,, x 2 pla 2) (Yang & Klein 2021 1, or additional training
to sample from 9+ (Khalifa et al. 2021 Hu et al. 2024 Zhao et al. 2024a
Indicator. A special case is c(y) indicating whether y falls into a target set Y such as the set of correct solutions to a reasoning problem, or sequences that have desired keywords. The goal is then sample from:
qs x po(y)>)] E Y,).
(17)
where Ily E Y2" is 0 when E Y and 1 when & Y Various generation algorithms incorporate a learned verifier (2 y) x Tly E Y to aid in achieving this goal (Cobbe et al.] 2021 Lightman et al. 2024), or
design beam search hcuristics for the case of desired keywords (Hokamp & Liu 2017 Lu et al. 2022
There is a clear connection between sampling from a target distribution of the form scoring function 2.2.1 sampling from 17 maximizes v(y) = Ily E yg e.g., correctness.
17 and maximizing a
Reward. An important case is when cly) is governed by a reward function r(z,y) E:
q. x (o( exp (fr(x.0))
(18)
where 3 E IR interpolates between sampling from py (B - xc) and maximizing reward (3 + 0).
A notable example is aligning the distribution of generated text with distribution of text preferred by humans Ziegler et al., 2020; Stiennon et al.] 2020 Ouyang al.] 2022). One way of operationalixing this problem is one of finding policy x that balances maximizing a reward r(z, y) that quantifies human preferences with generating sequences that are probable under pretrained model ps:
max max Max.pa.n...-ooollll Ir(, v)] SKL (m(y)=)]ppo)ll))
(19)
The policy that maximizes the above objective is Korbak et al.
2022b;
Rafailov et al. 2023
1 (v(x)) = Z(x)) [ (wlxr) (v exp (g)(,.))
(20)
where 7xx) is a normalization factor. One strategy for sampling from q. is updating Po with reinforcement learning, then using ancestral sampling. This strategy is referred to as reinforcement learning from human foedback AAseel et al. 2021). Later, we will discuss mena-generattin algorithms for addressing this problem.
A second approach is re-weight each next-token distribution during autoregressive sampling. For example, reward-augmente decoding (Deng & Raffel 2023) assumes access to reward function r(yge, that assigns scalar reward to partial generations VS+- re-whights the tokens with the top-k next-token probabilities using the reward, and samples from the weighttt distribution. That is,
y/ softmax (s) (Ver, + Br
(21)
11

---

Published in Transactions on Machine Learning Research (11/2024)
where sbih (y<t,, 2) R are the top-k logits at timestep t, rlik R are the rewards evaluated after appending each of the top-k tokens to the prefix yer, and [ E RR is hyper-parameter. Inference-time policy adapters (Lu ett al., 2023) directly optimizes an "adapter" language model to adjust base language model's next-token distributions so that the combined modol's gencrations receive higher rewards. Specifically, an adapter language model Ps is combined with a base language model to form a "tailored policy",
x)) x po(-Iuee,
(22)
and the tailored policy is updated with reinforcement learning while freezing the basc model po parameters.
3.5 Constrained decoding
Often desirable to generate tokens that satisfy some constraint. These constraints may be structural, e.g., satislying a JSON schema, or lexical, i.e, containing specific words. In contrast to controlled generation, constrained generation mandates that the output conforms to specific, formal criteria. Several methods from controlled generation be employed to encourage LMs to conform to constraints, but here we focus methods that strictly enforce such constraints. Naïvely, one can strictly enforce constraints via rejection sampling ($4.233. though there is no guarantee that this method will terminate. In this section, we therefore focus on efficient methods for constrained decoding.
3.5.1 Parser-based decoding for structural constraints
Structural constraints often take the form of grammar. A simple example of this would be to constrain the language model output to valid US phone numbers. Another would be to constrain outputs that conform to a specific JSON schema. Structural constrained decoding methods enforce such constraints by pairing the language model with a parser. The parser filters nexl-Loken candidates by allowing only valid continuations. The central challenges of parser- based constrained decoding are efficiently identifying valid next-tokens with the parser and interfacing the parser with a sub-word tokenizer.
Formal languages and parser efficiency. The efficiency of a parser identifying valid next-tokens depends on the complexity of the formalism used to specify the set of valid outputs. Regular expression (RegEx)-based) parsers; e.g., Guidance (Lundberg et al. 2024), LMQL (Beurer-Kellner et al. 2022. and Out- lines (Willard & Louf 2023); can be implemented as finite-state automata, meaning that these can recognize valid continuations in constant time and space. More complex constraints, such as JSON specifications, re- quire more sophisticated, computationally expensive parsers. Though JSON is technically not a context-free grammar (CFG), several CFG-based parsers including PICARD (Scholak et al. 2021). GCD (Geng el al., 2023), Synchromesh (Poesia al. 2022), and DOMINO (Beurer-Kellnee et al. 2024 can be used enforce valid JSON outputs.
Template speedups Parser- based constrained decoding methods can accelerate decoding, i.e., when there is only single valid next token, that token can be immediately accepted without doing forward pass with the model. Highly templated RegEx-based hots benefit most from this property (Lundberg el al. 2024).
Token healing. One drawback of constraincd docoding is that constraints may cause the language model to exhibit unusual behaviors due to the template or grammar forcing an unnatural token boundary. Several decoding methods deal with this issue by employing a method called token healing (Lundberg) 2023). Token healing rolls back the tokenizer to the penultinate token then chooses the next token with the constraint that it must have the remaining characters as prefix (see Figure 3 for example). This method uses a prefix tree to track valid continuations.
Minimally invasive constrained decoding. Constrained LLM performance can also be limited by tem- plates that are too inflexible. Over-constrained templates can prevent the model from generating outputs that would otherwise be valid. (Beurer-Kellner et al.] (024) call this property the invasiveness of a con- strained decoding method, and refer to a method as being minimally irvasive if every valid output that the model can generate can still be generated under constrained decoding. They link the invasiveness of
12

---

Published in Transactions on Machine Learning Research (11/2024)
Template
Without healing
With healing
An unnatural token"
An
unnatural
token
zaat
ion
An
unnatural
tokenization
Figure 3: Pre-tokenizing templates can cause issues for (greedy) tokenization by forcing the model to break tokens at unnatural points (e.g,, at the end of the word "token"). Token healing rolls back the tokenizer by one token (back to "unnatural") then enforces that the continuation begin with the remaining text "token".
constrained docoding methods to explosions in output perplexity and attempt to mitigate these drawbacks with their method DOMINO.
3.5.2 Lexically constrained decoding
It is often desirable to constrain language model outputs to contain or not contain specific words. LLM inference APIs often allow users to specify token ban lists or logit. bias to discourage the model from out- putting specific words, but forcing LLMs to output specific words more challenging. Lexically constrained decoding often employs search (Hokamp & Liu 2017) to find likely generations that satisfy the constraints. Some methods seek to improve this search, such as through gradient guidance (Kumar et al. 2022
For more complex lexical constraints, NEUROLOGIC decoding (Lu et al.) 2021) allows users to specify con- straints as a logical formula in conjunctive normal form (CNF) then enforces these constraints via a modified beam search, e.g., (food V foods) A (table V tables) specifies that the generation must contain either "food" or "foods" and either "table" or "tables". Followup work (Lu et al. 2022) adds a lookahead to this approach.
In summary, we have seen several strategies for constructing a token-level search space and adjusting the next-token distributions of model during sampling. Next, we will treat these algorithms as black- boxes that can be used to generate partial or full sequences, and survey algorithms that construct search spaces the (partial-)sequence level or operate by drawing multiple samples.
4 cectaggnnrationn algorithms
Some generation algorithms have the distinctive property of requiring access to separate generation sub- routine. For instance, best-of-N calls generator sample N sequences from the language model. This sub-gencrator is interchangable; it can be freely chosen from top-k, temperature sampling, any other sequence generator. We coin the lerm mela-generation to describe algorithms that call sub-generators, i.e.,
y g0112, 9u.,....))..))
(23)
where g defines the strategy used by the meea-gennratoo, (c) are sub-gencrators, and á generic parameter for any other inputs (such as verifier or retrieval models) and hyperparameters (such as the number of tokens to generate). Since meta-generator is itself generation algorithm, i..,, function that maps token-level
inputs to a distribution over outputs 2.2)) we will freely use g(-) for either a meta-generator generator. We will often hide the parameters (9i.....gc] | or make other parameters explicit based on the context. We identify four common strategies among meta-generators. In particular, we find that they can be classified into the categorics of chained, parallel, step-level, and refinement-based meta-generators.
4.1 Chained meta-generators
The first meta-generation strategy chains multiple generators together. We start by explaining this idea. in the context of prompted language models.
Chaining prompted language models. language model by specifying a prompt 2,
It is increasingly common to perform input-output tasks with
y f(:;po, 2,,,,,000 2)
(24)
13

---

Published in Transactions on Machine Learning Research (11/2024)
Parallel generate
Aggregate
Generate
Select
Replace
Initialize
Generate
Append
Feedback
Output
(a) Parallel search
(b) Heuristic step-level search
(c) Refinement
Figure 4: Three meta-generation patterns.
where J()) is a delerministic generator, and the prompt is a sequence tokens that specifies the desired behavior through natural language instruction or input-output examples (Brown et al., [0200] Ouyang al, 2022). For instance, given multiply the two numbers and 1432 293, can generate output that contains an (attempled) solution. It is natural to compose the generator call with other operations, such composing generator that outputs Python code with function that executes Python code.
Similarly, it natural to combine multiple calls to generators, c.g., generating a story using:
y f3 o f2 f1,
(25)
where f1 generates story outline, f2 fills in the sections, and fa revises the story to meet a length constraint. Notice that the composition itself a generation algorithm,
f(; po: (f1, f2, fz)),
(26)
i.e., a mapping from an input x, model pe, and other parameters é, to an output (here, á contains the generation algorithms fi, f2, fa), or in general, a distribution over outputs g(yla, Po, Φ). In general, we can view calls to generation algorithms as steps in a program whose execution yields a generated output. We can view the program (2: pe. F),, which calls generation algorithms f F, as meta-generation algorithm.
Related ideas appear in the literature under various names, including the programmatic view in Demonstrate- Search-Predict (DSP) and DSPy (Khattab et al. 2022 2024), language model cascades (Dohan et al. 2022
LLM program (Schlag et al. 2023). and recently, scaffolding program (Zelikman et al. 2024b). We introduce the term meta-generattin as an abstraction that is agnostic to the implementation of the underlying generator model(s) (which need not LLMs), and to clarify the connection with other generation algorithms.
Problem decomposition. A variety of algorithms have adopted the chain pattern in order to decompose an input-output problem into multiple steps, with each step implemented by a language model or exter- nal function. As a motivating example, Chain-of-Thon Thoughh (Wei et al. 2022 decomposes generation into generating a "chain-of-thought" followed by generating an answer i.c.,
z~ ((((()))))) ,(vl,,2),
(27)
where is a generator, & is an input, 2 is an intermediate sequence (a "chain-of-thought"" and is an answer. It is instructive to view a variety of methods as generalizing this two-part decomposition to multiple intermediate sequences, 21, 22,..., that involve calls to generators or external functions (Dohan et al. 2022). For instance, least-to-most prompting (Zhou al. 2023a) first calls generator to decompose problem into sub-questions and then consecutively calls a generator to answer each sub-question, while Self-Ask (Press et al. 2023 additionally calls search engine after generating each sub-question. Both of these special cases of Comonstratte-Scarl-PPrro.
(DSP) programs (Khattab et al.) 2022). A wide range of methods can be seen as constructing alternative chained meta-generators, ranging from System 2 Attention (Weston & Sukhbaatar 2023), which rewrites an input prior to generation to help the model refrain from attending to irrelevant information,
methods that decompose formal proof generation (Jiang et al.) [2023). More generally, a number of tools such as LangChain (Chase (2022) and MiniChain (Rush) (0023) provide domain- specific languages for declaring and executing chains involving prompted language models.
14

---

Published in Transactions on Machine Learning Research (11/2024)
Algorithm
A Aggregation type Scoring transforming with
Best-of-N
Rerank
LLM score or external score
Noisy-channel
10%
Rerank
Log-linear combination
Majority voting
9
Transform
Empirical vote frequency
Weighted majority voting 216
Transform
Empirical distribution over answers
Self-consistency (20)
Transform
Marginal distribution over answers
Universal self-consistency RM
Transform
Answer aggregation using LLM generator
Maanch-Solve-Meeee [86
Transform
Answer aggregation using an LLM generator / ruulebbssed parsing
QE-fusion P11
Transform
Answer contains spans from candidates
Table 3: Parallel mela-generators.
4.2 Parallel meta- meta-generators
Another pattern is to generate multiple trajectories in parallel, then merge the resulting terminal states to arrive at a final generated sequence. For instance, various sequence-level generation algorithms generate an N-best list [ Jn=1 ~ 9, then apply an aggregation function h y(.). to arrive at final generated sequence. The N-best list of sequences might come from sampled generations, a beam search algorithm, or any other generator y ~ I that generates full sequences. We discuss aggregation functions that rerank ($ (44.2.1 or transform ($4... the N-best list, then discuss sequence-leve statistical rejection sampling ($4.2.3) Table 3 presents brief summary of algorithms from the classes that we discuss.
4.2.1 Reranking algorithms
Reranking (or rescoring) is a classical approach (Collins, 2000 Huang & Chiang 2007 originally developed for parsing and automatic speech recognition to achieve a trade-off between the computational complexity of MAP decoding and its lendency lo rule out good hypotheses. A reranking algorithm orders an N-best list. with a reranking function (hyy"),..... (N)) - ",. (((()) then selects the top-k ranked sequences. Reranking has recently found new applications in text generation (e.g., Cobbe al. (2021); [Stiennon et al.) (2020gg Krishna et al. (2022): Ni et al. (2023 Lightman et al. (2024)) by using various reranking functions and various sources of data to learn the reranking functions. A simple and effective method is best-of-N.
Best-of-N. Best-of-N (Charniak & Johnson
2005 Pauls & Klein 2009 refers to generating an N-best
list and picking the best sequence according to scoring function.
Definition 5 (Best-of-N: BoN(z, v, N;)))) Let g be generation algorithm with output space V and v: y + I scoring function. Assume that governs the randomness in g. The best-of-N generation algorithm is defined as:
N(, max (u(y(")) | (/)) g((1)), (1,
(28)
where each (m) is a generated sequence.
Best-of-N can be performed with any algorithm that can be used to generate a list of N sequences, including temperature sampling, beam search, Viterbi decoding, or many others. In the context of language modeling, best-of-N was developed for parsing (Charniak & Johnson, 2005 Pauls & Klein 2009), and traditionally involved modifying decoding algorithm originally developed the top-N highest scoring decodings. An attractive property is that Best-of-N usually incurs only linear increase in computational complexity compared to top-1 decoding. In the context of LLMs, best-of-N is amenable to black-box generators (e.g., accessed via an API), since it does not require knowledge of the generator for populating the N-best list. Modern instances of best-of-N use learned scoring functions that are often themselves parameterized by LLMs. We discuss examples from reasoning and preference alignment.
find the top-1 hypothesis that it obtains
Best-of-N in reasoning. In some settings the goal is to generate correct sequences, such as a correct solution to mathematical problem or program that passes test cases. common approach these cases is to learn a verifier es (a. 9) + [0. 1] that predicts the probability that an output y correct, and use it within Best-of-N. Doing has seen success in mathematical reasoning (e.g., Cobbe et al. (0011) h Uesato
15

---

Published in Transactions on Machine Learning Research (11/2024)
et al. 2022 Lightman et al. (2024)), ) code generation Ni et al. 2023). and other settings with similar properties Naturally, the performance depends on the quality of the verifier, which we return to in 5.
Best-of-N in alignment. Previously in $3.4 we discussed how the problem of aligning the distribution of generated text with a distribution of text preferred by humans can be framed as sampling from
(ulx)) [(x) po (v/(r exp 2 (F)(c..))
(29)
When a single high-reward sequence is desired (e.g., at low values of 3), natural strategy to use best-of-NV with a learned approximation of the reward, (1, 3), as the scoring function. In practice, this strategy is effective alternative to reinforcement learning from human feedback (RLHF) methods (Gao et al 2022 Beirami et al. 2024). For example, AlpacaFarm (Dubois et al. 2023) found that Best-of-1024 with human- preference reward model was competitive with more standard decoding methods with a model trained using RLHF. A potential benefit is that Best-of-N does not require updating the model py's parameters, at the expense of generation-ting timeiiionotemeeeee compute.
Best-of-N depends on the quality of the reward function, which is typically a learned function ug (2, y), termed reward model. It can suffer from reward over-oplamizzaionn-i i.e., returning an undesired sequence that nevertheless receives high reward. Specifically, suppose that (-(1/z) x uz y), where v. perfectly captures the desired outcome of generation. Best-of-N at high values of N can be seen as approximating:
arg max q-(lar) yEy
arg max Uyp (2, Mn))
(30)
Un (L....)
where Vn g. In practice, the learned model uy typically does not match v., especially out-of-distribution sequences, so best-of-N N may find sequences that "overoptimize" the reward (Gao et al. 2022)
Noisy-channel reranking in Neural Machine Translation. A wide range of reranking methods pre- cede the era of large language models. A classic approach is a noisy-channel model (Brown et al. 1993). Noisy-channel means that the observed output from the system (e.g., a machine translation system) is distorted by some unknown noise pattern (i.e., noisy channel). If we consider (s(y(z) as the probability of the translation y of the source language text. v, then Bayes rule suggests the following relationship: po(y|z) x p(xly)p(y), where p(zly) channel model, and p(y) is the target language LM.
2019 propose use the following log linear As an example from the literature, Och & Ney 2002): Ng et al. combination to rerank translation candidates:
Spoisy-channel (y) logp(y(>> + A (ogp(zly) 1) + A2 log
(31)
where the log-linear coefficients X and X2 are tuned empirically on a development set. Therefore, the reranking function h in this case is defined so that the order of candidates given by a decreasing order of noisy channel scores Spoisy-channel computed for every translation candidate.
4.2.2 Transformation algorithms
In contrast to reranking elements of the N-best list, other algorithms transform the list into new sequence which might not be part of the N-best list itself. For instance, mathematical question answering is an example of a task where the potential outputs (answers to math questions) are produced as part of much longer decoded sequences from the LLM. In other cases we might draft N summaries, then synthesize them into a new, final summary. This requires a transformation of the summaries rather than a simple reranking.
Majority voting. Majority voting (or self-consistency Wang et al. 2023b processes N-best list and counts how each of the candidates (() votes lowards a different set of outputs (a1....,axt
h2y ..... (()) + (clr("))...c(((
(32)
16

---

Published in Transactions on Machine Learning Research (11/2024)
where : - I,...,K K is voting function that maps from sequence space to output from (a1, (A1,...,ax] ax).
Second, it selects the output that received the largest number of votes:
K N
= arg max
ΣΣ 1=
1(dy
j).
(33)
Weighted majority voting. Often is beneficial to incorporate reward model Up into voting. The reward model can bias the distribution break ties. The final output selection is done by aggregating (e.g. summing) scores associated with the votes:
K
N
à = arg max
Σ s
(
((((((()) j).
(34)
k
j=
Let = (2,0) denote an output decomposed into a sequence 2 (e.g., a reasoning chain) and an answer a. Wu et al. 2024) prove that as + oo, weighted voting accuracy on a dataset of M examples converges to,
M M
a arg max Σ (y(zza)g(a, 2|x)
(35)
This is the accuracy obtained after marginalizing out the sequences z. Voting can be seen as sample-based approximation based on N generated intermediate sequences (Wang et al. 2023b). Moreover, weighted voting will outperform voting when v 9 has more total mass on correct answers than g (Wu et al., 2024).
Figure 6 shows performance comparison of best-of-N,, majority voting, and weighted majority voting standard mathematical reasoning benchmark.
Minimum Bayes Risk decoding. Rather than seeking the most probable sequence as in MAP decoding, Minimum Bayes Risk algorithms aim to find the best sequence in terms of a pairwise utility function u(y, v/):
Example 2 (Minimum Bayes Risk algorithm). A Minimum Bayes Risk (MBR) decoding algorithm refers
to an algorithm of the form (Bickel & Doksum 1977
Kumar & Byrne 2004):
f(x) arg max y'EY
Σ
u(y. ((V../)p..w) (vlz),
(36)
yEy
where u y + R. A dependence on Po introduced in specific instances of MBR decoding algorithms.
The MBR objective is motivated by decision theory. Intuitively, it can be thought of as seeking an output with highest average "similarity," " as mcasured by the utility function u, to other candidates, particularly those assigned high probability under p..
Various algorithms provide approximate solutions to the Minimum Bayes Risk (MBR) objective. They typically consist of providing utility u(.,-) + R, populating hypothesis set Y%. using generator, and populating a evidence set Ye to estimate the risk of each hypothesis:
i = arg max
1
Σ u(y.v)).
(37)
v'E On
vEY.
The hypothesis set is typically akin to an N-best set, populated by calling generator ( J== 9(-
Simple strategies sample from the model, ((") pa. Others take the best-k outputs from ranked list of generations, or use more sophisticated strategics such as itcratively adding hypothescs or transforming
them Ruoio et al.) 2011 Ruuzález-Rubio & Casacuberta) 2013). Freitag el al. (2023) invest
the impact of the underlying sampling strategy, finding variation across strategies, with epsilon sampling performing best for machine translation. The evidence set is typically sampled from a generator, or set save on computation. Finally, the metric impacts performance. For example, MBR with metric tends to inflate performance that metric, sometimes by gaming (Freitag et al. 2023
the hypothesis
17

---

Published in Transactions on Machine Learning Research (11/2024)
Known upper bound distribution Mp
Un-normalized distribution q
Reject region
Accept region
Figure 5: In rejection sampling, the aim is to sample from distribution whose normalizing constant is unknown. To do so, use a known distribution p that serves as upper bound for the unknown distribution when scaled by a constant, ie., for some constant M and all values Mp(y) 2 g(v). Next, obtain a sample ~ and accept this sample with probability g(u)/Mp(y)), otherwise reject the sample and repeat the process. This is equivalent to sampling from q.
MBR methods have rich history in the machine translation and speech recognition literature (Goel et al. 2004 Heigold et al. 2005 GOEL. 2003 Kingsbury et al.] 2012 Fikema & Aziz 2020), and have also been
applied across other tasks (Shi et al. 2022 Suzgun et al. 2023). Interostingly. Bertsch et al. (0023 show
that self-consistency and other voting techniques are special cases of MBR. For example, weighted voling (and as a special case, voting) corresponds to a utility that checks if two answers match,
u(y. [a - =a' v(y'),
(38)
where y = (z,a) (z', and is the weighted voting scoring function. In general, there are several other dimensions along which MBR methods are calegorized. We refer the reader to Bertsch et al. (2023)
for further in-depth study and taxonomy of MBR methods.
In general, we can view the algorithms above as first generating an N best list, followed by transforming the N best list using a transformation h(y(2), (()()),...,,'"')), such as voling or one that internally estimates risk. Rather than hand-desiguing the transformation, recent methods explore using language models themselves. For instance, universal self-consistency (Chen et al., 2023c) prompts a language model to generate a final sequence given the N-best list, which can avoid the aforementioned issue of parsing sequences into answer. Branch-solve-merge (Saha et al. 2023) transforms input into N different prompts, generates with those prompts, then merges the results by prompting language model.
Generate-an--rrasffon
4.2.3 Sequence-level rejection sampling
Previously we discussed the goal designing genoration algorithm that samples from a target distribution g. ($2..33). related pattern using a stochastic sequence generator y ~ g lo sample from z. using rejection sampling. This involves sampling multiple sequences from g and thus akin a parallel meta-generator.
Specifically, statistical rejection sampling is technique for sampling from a target distribution 9x with unknown normalizing constant. This is accomplished by first sampling from a known distribution y g which serves as an upper bound for g., (c.g., for some constant M, MM(y) 2 q=()), then accepting the sample with probability q- (v())MM(() Figure 5 illustrates this process. Rejection sampling is a useful tool for sampling from a specified target distribution over an intractably large support, e.g., the set of sequences.
One example of sequence-level rejection sampling for LMs sampling valid JSON strings from an LM. The space of valid JSON strings is infinite and the normalizing factor is unknown, but can sample from this distibution by first sampling from the LM distribution pe, then rejecting any string that is not valid JSON. Here, the un-normalized distribution we are sampling from is
po(y) y is valid JSON
q- (v) x
0o
Otherwise
and we must use rejection sampling since the normalization term is unknown.
18

---

Published in Transactions on Machine Learning Research (11/2024)
Best-of-N and rejection sampling. Above we introduced best-of-N as deterministic algorithm (Defi- nition 5) Another view is that calling best-of-N with a stochastic generator g is itself stochasticc generator,
y - BoN(po, 9; N,,),
(39)
.......g)),)............)) g, then selecting the sequence with the highest where BON means generating N sequences ......., .....,
score v. This idea has been termed the best-of-N policy (Stiennon et al. 2020 Gao al. 2022). Interestingly, Gao et al. (2022) find that the best-of-N policy may give similar reward maximization to reinforcement learning, though with a different pattern of divergence from the underlying language model. Their analysis uses an analytical expression for the KL divergence from (Stiennon et al., 2020), Dx (TBox (TB) s log N (N - 1)/N. Beirami et al. (2024) show that this expression is an upper bound on the actual KL divergence and propose an estimator that empirically provides a tighter approximation.
Finally, y ~ BON can be understood as internally performing rejection sampling (Stiennon et al. 2020 We refer the reader to Liu et al. (2024c) for more detailed discussion of this connection, as well as an improved algorithm that builds on the connection between rejection sampling and best-of-N.
Pseudo-rejection sampling. Several decoding methods employ various forms of pseudo-rejection sam- pling- One example of this is [i et al. (2024a), where the authors sample a set of k outputs from the LM, compute the "value" of each of these outputs, and then sample from the output set by interpreting the values as logits. As l tends toward infinity, this method approaches sampling from the value function with a regularization term that keeps the distribution close to the LM distribution. Another method based on similar construct is the one of Zhao et al. (2024b). Such methods can also be interpreted as sampling importance resampling, in the spirit of sequential Monte-Care Carlo sampling algorithms (Doue et al., 2014). Pseudo-rejection sampling is often employed when the prerequisites for rejection sampling are not met, for instance when there is no known upper bound on the target distribution.
4.3 Step-level search algorithms
Next, we discuss meta- gentaaeenrrtion algorithms that implement classical search algorithms by calling generators. To introduce these, it is helpful to view generation as navigating a state space s E S by taking actions a E A using a generator, and receiving new states from an environment E : S x A + P(S), yielding a trajectory (so, d1, 81, "ti....,,,,6.. ST). The start state so contains the input to the generation algorithm, i.e. x E 80: while the terminal state contains the output of the generation algorithm, i.e. y E ST. Generation consists of running the resulting process until reaching a terminal state.
As basic example, recall that greedy decoding is defined as:
f+ = arg max po(uels<e...)
(40)
B.E
1,..., T. The search perspective interprets this as taking next-token actions å given states (at, Dcr), a generator that selects the most probable next-token from pe, and an environment that appends next-token to form a state (I. Ser o (t). Since greedy decoding is an approximate MAP decoding algorithm, it aims to end in a state that maximizes Po(y)z). In other cases the environment is less trivial, such as those involving code execution and visual observations (Shinn et al. 2023 Zhou et al. 2023b). Many algorithms can be recovered by varying the states, actions, environment, and/ or generator.
for l....,,..,
In particular, reasoning tasks such as mathematical problem solving or theorem proving have served as a testbed for developing step-level search algorithms. In these lasks, the final output (a solution or proof) naturally decomposes into 'steps', y (yI..... yr), where each y, is itself sequence of tokens. One can then consider a partial solution Y<t as the state 8t, and generating next-step y, as the action. The environment appends the next-step to the partial solution, Y<t o Yt- There is also a natural notion of success (i.e., a correct answer, a valid proof), leading to the idea of a value function v(st)) + 10 that is used to predict whether a solution-so-fe will eventually be correct (or in general, predict the expected reward of the state).
Several algorithms maintain a queue of states that contain partially generated outputs, and iteratively select states for exploration. Exploring state involves expanding the state's partial output and scoring the
19

---

Published in Transactions on Machine Learning Research (11/2024)
Method
Search
State
Generation
Value o(8e)
Tasks
got-f Proof Search
176
Best-first
Proof-so- so-fax
Proof step
log Pe
Formal proving
got-f +outcome 17
Best-first
Proof-so-faa
Proof step
By B (ssuccess)
Formal proving
Proofsize Search
1ni
Best-first
Proof-so-fai so-far
Proof step
By B(length)
Formal proving
Stepwise+++
224
Ream
Proof-so- far Stepe-so-far
Proof step Reasoning step Reasoning step
log pe --grams
Informal proving
Self-Evalusthe
[8
Beam
lo LLM
Multi-step correctness
Reward Balanced Search
229
BFS-like
stepe-so-fal far
Py R E(correct)
Multi-step correctness
Tree-of Thought 240
BFS/DFS
Stepæ-so-fa sep--s--far Steps-so-far
Generation step Generstion step
Prompted LLM
Multi-step generation
Graph-of-Thhugee 14
BFS/DFS
Prompted LLM
Multi-step generation
Hyper Proof Search
119
MCTS
Proof-so-far Stepe-so-far Stepe-so-far
Proof step Reasoning steps
Vy A (ssccess))
Formal proving
AlphaLLM 2211
MCTS
By ((correct) Prompted LLM
Multi-step correctness
Reasoning via Planning
7
MCTS
Generation step
Multi-step generation
Table 4: Survey of step-level search methods.
expanded output with a value function v(s)). The scores are then used to prune or prioritize states for the next iteration. Conceptually, step-level search is typically tree scarch, consisting of states as nodes and actions plus environment transitions as edges. Although the algorithms below typically contain domain- agnostic ideas, we will ground the discussion below by discussing reasoning tasks as the running examples.
Warmup: token-level beam search. Traditional beam search (Graves) 2012 Sutskever et al. 2014) maintains queue of prefixes ) termed a beam, expands each prefix using each possible next-token, (ukt M/ k E {L...., K}. V/ V}, scores each expanded prefix using log Po wr/z), and prunes the queue by keeping only the top-K K scored expansions for the next iteration. In this case, the value function is E(yer y1) = log pa (V o W)læ)) and it is used to prune states by selecting the top-K expanded prefixes. Traditional beam search operates on the token-level, using the specific strategy of expanding cach possible next-token, which assumes access to primitive operations (e.g,, next-token distributions).
Partial sequence expansion. We can consider higher-level algorithms that operate on the partial se- quence (i.c., "step") level rather than the token level, and call arbitrary generator to expand states, c.g.
( lk=t ~ g(-(s)). For example, stepwise beam search WWlleckk et al. 2022 Xie et al. 2023 performs a beam scarch over steps of mathematical problems or proofs. Troe-of-thoughts Yao et al. 2023 considers a
beam search over generated steps that include additional "thought" sequences. Potential benefits of partial sequence expansion over traditional beam search include efficiency due to executing the value function less often, and not requiring access to all of a model's next-token probabilities.
Alternate search strategy. Another axis of variation is the underlying search strategy. Beam search is a pruned breadth-first search, which has been used with contemporary LLMs in methods such as stepwise beam search (Welleck et al. 2022), tree-of-thoughts (Yao et al. 2023), and recently in Snell et al. (2024). However, other search algorithms are available, such as best-first search, used in the context of formal theorem proving (Polu& & Sutskever 2020 Polu et al.) 2023: Yang et al. 2023a). Formal theorem proving has natural decomposition of outputs (i.c., proof) into steps (termed "tactics"), which has historically made it a fruitful testbed for more advanced search algorithms. For example, HyperTree Proof Search (Lample) let al. 2022) draws on Monte-Carlo Tree Search (MCTS)- method that was central to the impactful Go playing system AlphaGo (Silver et al. 2016 2017) which prioritizes states according to a confidence bound and scores states by rolling out trajectories. Recently, similar ideas have been adapted to other LLM generation tasks. For instance, Reasoning via Planning (Hao al., 2023) and ThoughtSculpt. (Chi et al., 2024) incorporate MCTS selection and rollouts for several tasks. However, there are few key differences between environments in which MCTS has excelled (such Go) and cineral-purpon language generation. For example, MCTS explores based on visit counts in the search tree, which can require a large number of simulations (for instance, AlphaGo Zero used 1,600 simulations per move (Silver et al. 2017)). This can be prohibitively expensive with large language models. Second, Go has a natural decomposition into steps, and a reliable terminal reward (i.e., win vs. lose) that can aid in training a value function.
Alternate value functions. Another axis of variation is the choice of value function. For instance, in traditional beam search, value function can be manually designed to score candidates (yeroy)) more highly
20

---

Published in Transactions on Machine Learning Research (11/2024)
2022 while others use learned heuristics vy (y<e) trained to predict property of the full sequence (e.g., its style score or correctness) (Yang & Klein 2021) In formal theorem proving, it is common to train a value function that predicts whether a proof from the current state will eventually succoed (Polu & Sutskever 2020 Lample et al.) 2022) or a related statistic such as the expected proof length (Polu et al. (002)). In the context of large language models, a recent. trend to use a prompted language model to evaluate states (Yao et al., 2023). As mentioned previously, to achieve better results one can train & model that predicts whether the solution-so-fat will eventually be correct, (y(()))) - [0, 1] (or more generally, predict the expected reward from the current state), termed process-basee verifier (Uesato et al. 2.22). Recently, Reward Balanced Search (REBASE) [Wu et al. 2024) allocates its exploration budget to nodes based on their process-basee verifier scores. Liu et al. (2024b) repurpsses the value function from proximal policy optimization (Schulman et. al.) 2017) as a MCTS value function. Refer to Hao et al. (2024) for additional discussion, including a library implementing several of the algorithms above.
if they contain desired n-grams (Lu et al.
4.4 Refinement algorithms
A refinement algorithm consists of (1) initial generator 9o, (2) information source h, (3) refiner g:
( ~ go(y)2))
(41)
20 ~ h(21z, y (st), ((())) y() ~ slyla, y (<t) ((5)))
(42)
(43)
Intuitively, the refiner generates a "revised" output (()) given previous versions (<t)) and extra information z(50, such feedback or environment observations. The algorithm alternates between receiving information, ~ h, and refining, y ~ 9, until a stopping condition is met. Refinement algorithms vary based on choice of initial generator, the refiner, the content and source of extra information 2, and the stopping condition.
Learned refiners. Self-correction, introduced by Welleck al. (2023). provides a recipe for training refiner model po(y("1zz, [z, (2,/"//,,(11)))) f(t-1),, 2(0) which iteratively refines output to improve the score from reward function r(z,8) using (z(0, ,,(",,(t-)), f(t-1) (!)) examples collected from model trajectories. Here 2 is either 0/1 (apply the refiner or do not apply the refiner) or a feedback string. 2 is assumed to be given to the system at generation time, which is limitation for some tasks (e.g., we often do not know whether a mathematical solution should be revised). GLoRe (Havrilla et al.) 2024) relaxes this limitation by training a verifier to determine whether to apply the refiner, and to localize per-step errors.
Prompted refiners. A second option to parameterize the refiner using a prompted language model,
( ~ go (1) (v)Protne((a, y ((t)) (5")))
(44)
where go is a generation algorithm that involves prompting a model po with a prompl Prefine(;; (<0) z(50), as introduced in Self-Refine (Madaan al. 2023) and Reflexion (Shinn et al.) 2202).. This allows the initial generator and the refiner share a single language model that is not necessarily tuned for a specific task.
Prompted feodback. It common for the information 2 ~ h to include "foedback" on a precoding version y, with the leedback being a sequence of tokens generated with prompted language model:
(t) ho (2)Pronctbacc(1, 2(0))
(45)
This feedback is often also termed "critique" " (Matiana el al. 2021 Castricalo et al., 2022 Bai et al. 2022 Saunders et al.) 2022). Self-Refine (Madaan et al.) 2023) shares across the feedback provider, refiner, and initial generator, yiclding a refinement algorithm given only a model Pe and 3 prompts. Similarly, Reflexion (Shinn et al. 2023) uses a prompted foedback provider. In these cases, the feedback is termed self-feedback self-reflection.
21

---

Published in Transactions on Machine Learning Research (11/2024)
Environment feedback. As we discussed previously, the search perspective treats generation tra- jectory (8o. d1, .1, .1,...,,77,8777 ,r,,)) 8T); with state transitions determined by an environment & : S x A + P(S). Tn some cases the environment transitions are nontrivial, such as executing generated code or clicking a link in a webpage. We can view the resulting observations (e.g., code exccution results or an image of a webpage) as exlra information z(0) E ((0) that contained the state. This information can be passed to the leedback provider to generate foodback E, and the refiner (e.g., via prompts):
3((5)) 5(0) ~ ho (2 (z)Preedback (z, , x(5)))((0))) ,((0))
(46)
ylth ~ g0 (V)Prenne ((t)) z(50) )(5!))) )
(47)
mcaning that cach itcration refines based on new environment information (e.g., code exccution results).
Reflexion (Shinn et al. p023 adopts this perspective of generation as trajectory involving an environment,
with the refiner akin to an "actor". The idea has since been adapted to digital agents (Kim et al. 2023 Pan
ct al. 2024).
code (Chen et al. 2024b Shi et al. 2024b), and other environments (Pan et al. 2023
Does refinement work? Notice that a refinement algorithm is a 3-tuple h9,, Intuitively, if the information source h adds new information beyond that contained in the initial generator go(-lpe) to the refinement algorithm, it is plausible that refinement algorithm can outperform the initial generator alone. Hence, in our discussion we distinguish between algorithms that receive information external to the generator at inference time, and those that do not. receive external information at inference time (termed extrinsic and intrinsic refinement or self-correction, respectively (Huang et al. 2024 Kumar et al. 2024
For extrinsic refinement, it is plausible that there are information sources which add new information beyond that in 9o(-|po), and hence lead to potential gain with refinement. For instance, if h contains compiler error, test case results, or image of webpage after it is clicked, the refiner plausibly receives new information. Similarly, if 2 ~ h represents feedback, and the feedback comes from a source outside of the model pe (e.g., a human, a model with additional parameters, supervision, or a different objective), the feedback function may be expected to add new information beyond that in the initial generator. Indeed, refinement has seen success in code generation, where a code interpreter or compiler provides feedback (e.g.. Chen et al. (2023d)), ), or when a retriever or larger model (Olausson et al. 2024) provide feedback. In similar vein, Reflexion (Shinn et al., 2023) finds that without code execution, refinement yields little to gain on code generation. What factors contribute to the potential improvements, aside from the general notion of "adding new information"? Taking a compiler as example, the compiler can potentially (i) evaluate correctness, (ii) localize errors, and (iii) provide other semantic information related to an error (c.g., an error type). A parallel method such as Best-of-N (scc $4.2) can only use this information to prefer one sequence over another. A refiner, in contrast, can implement an arbitrary transformation that acts upon the information. That said, fully understanding the factors that enable refinement remains an open question.
For intrinsic refinement, we first consider refinement algorithms that prompt single model for initial gen- eration, feedback, and refinement (e.g.. Madaan et al. (2023) ). In these cases, the efficacy of refinement has been mixed. For example, [Huang et al. (2024) and [Teen et al. (2024) find that such methods often fail to improve on reasoning tasks. The failure likely stems from the difficulty of a model evaluating the correctness of its own outputs (Huang et al.) 2024). Similarly, Havrilla et al.] (2024) observe that even learned verifiers trained to predict cossect can have high false positive rates that trigger spurious refinements. In these cases, we can view the information source as being too noisy for the refiner to reliably act upon.
Finally, we consider intrinsic algorithms that aim to train refiner. The key difference with prompted methods is that the refiner can receive new information through the training procedure. For example, code correctness might be used as a reward signal to train refiner that maps buggy code to correct (high reward) code. Since the refiner is typically a generic refiner can be trained in practice. Self-corrective learning (Welleck et al. 2023) framed training as generating (x. y, )') examples online with the initial generator, refiner, and a reward function, updating the refiner by fino-tuning on the examples, then repeating the process. However, recently Kumar et al. (2024) identified behavior collapse phenomenon, in which the refiner learns to ignore the intermediate output y. This
model, the key question is whether such a
22

---

Published in Transactions on Machine Learning Research (11/2024)
motivated reinforcement learning procedure that alleviates behavior collapse and leads to some degree of intrinsic self-correction. More generally, learning intrinsic self-correction remains an active research direction.
In summary, refinement presently works best for tasks that either have rich environment feedback or can be reliably evaluated by current language models. As language models improve as verifiers, the range of tasks for which refinement effective will likely grow. However, this may be paired with improvements in the abilities of the initial generator 9o, potentially to the extent that intrinsic refinement is no longer necessary.
5 Incorporating external information
Next, consider what kinds of information generation or meta-generation algorithm incorporates outside of the language model, such as other models or tools. Algorithms use external information by calling operations beyond primitive operations from pa (e.g., those from another model), or through assumptions on the inputs or outputs. We comment on common patterns related to incorporating external information.
5.1 Multiple models
A variety of generation algorithms incorporate multiple models. More formally, recall that in ($2.2) we defined a generation algorithm as a function that maps an input x, model pa, and other inputs Φ to a distribution g(y|x; (oll::pp))))))))))))))))))>))) o). A generator uses multiple models language model), and operations from the model are used in the algorithm. In this sense, the external models can add new information beyond that contained in pa to the generator.
contains other models (e-g., an additiona
Small and large language models. A notable pattern is using a small language model to either adjust a model's distribution or to speed up generation. Lu et al. (2023) train a small model Pa with reinforcement learning such that it adjusts the next-token probabilities of larger model py to maximize a reward function. The models are combined into a token-level "product of experts" (Liu et al. 2021a),
1 (' 7 (yr (eel:
(48)
where Pa is a separate language model, a E IR, and Z E R is a normalization constant. Liu et al. (2024)) adopt a similar idea but with supervised finctuning of ps. In order amplify the improvement of large, strong model over small, weak one, contrastive decoding (Li et al., (2023)) defines scoring function for beam search that returns the difference between the likelihood under the model po with that of smaller language model pbo
S/yC o ve) log (o(olue)) log p' (yelu<t))
(49)
along with a truncation criterion that sets the score to zero for some tokens. Intuitively, the smaller model often has larger model errors on unfavorable tokens (e.g., assigning more probability to tokens leading repetition or incoherence compared to po). Assuming there is nontrivial difference in probability assigned to these tokens, the score will reduce their prevalence in generated texts.
Finally, speculative decoding [eviathan et al. 2022 is motivated by speeding up generation, which we will discuss further in ($7) It uses a small draft model to propose generations that are verified or rejected in parallel by the larger model pa, hence speeding up generation when the rejection rate is not too high.
Scalar feedback models. A common pattern is learning verifier model ug(x, + [0, 1] that predicts the probability that generation is correct (Cobbe et al., 2021 The verifier can be used to select outputs in best-of-N, or for weighted majority voting Li et al.] 2023b) This pattern is particularly suitable for mathematical problem solving and code generation (Ni et al. 2023), which have well-defined notions of correctness. Several works have iterated on the verifier model's design and learning procedure. [Uesalo et al. 2022 show that a verifier trained to predict the correctness of each step in an output (termed a process- based verifier) can outperform a verifier trained to predict the correctness of a full solution (termed an outcome-basee based verifier), and Lightman et al. (2024) obtain new human annotations for a process-based verifier. Math Shepherd (Wang et al. 2023a) propose a method for obtaining supervision from generations.
23

---

Published in Transactions on Machine Learning Research (11/2024)
An underlying idea is that a generation algorithm that incorporates the verifier may have capabilities beyond those of po- This may be due to additional supervision, or factors that stem from the intuitive idea that evaluation is often easier than generation. For example, Sun et al. (2024a) show that weighted majority voting with a verifier can improve the generator's 's ability to generalize to harder problems.
More generally, learning a verifier is a special case of learning a scalar reward model (2. y) that can be used to select or score outputs. For instance, in ($4.2.3) we discussed using reward model of human preference
ratings to select outputs in best-of-N (Stiennon et al.) 2020 Ouyang et al., 2022 Touvron et al. 2023 As discussed previously (4..33)
can view this shifting the generation distribution.
Information conveyed in prompts. Rather than using separate model in a multi-model system, it is now common to parameterize different models by providing different prompts. For instance, we can obtain a feedback model by prompting a model to provide feedback. It. important to note that the prompts can add new information to the generation algorithm. As another use of multiple prompts, Kim et al. (2024b) use the logits obtained with a perturbed input prompt to adjust the logits used for token-level generation.
5.2 External environment information
More generally, generation algorithms can incorporate information from an external environment.
Calling an external tool. Certain functionality such as reliably performing calculation or a web search may either be outside of model's capabilities or inefficient to perform with the language model. A natural alternative is to issue a call to an external routine that performs the functionality at generation time.
One way to do this is through special tokens that denote a call to the routine, followed by replacing the prefix with the result. For instance, suppose the preceding tokens yer include [CALC]4+4[/CALC]] Then at step of a token-level decoding algorithm, calculator would be called on the query 4+4, and in subsequent steps, the prefix Vę* would contain the result 8, along with possible reformatting (e.g., removing [CALC]).
A second common use of an external routine is as a verifier following the generation of a full sequence. For instance, in language-model based theorem proving the proof assistant is used to verify or reject generated proofs, while in code generation is common to execute test cases. More generally, the notion "tool use" (i.e., calling external programs) now widespread, and has been incorporated into libraries such as LangChain Chase 2022) and products. Refer Wang al. (2024b) for further discussion.
Receiving observations from an environment. The search perspective framed generation sequen- tial decision making process that involves observations from an environment ($4.)) A notable application area is code generation, which has natural environment information (e.g., interpreters, compilers). For instance, Lever (Ni et al. 2023) foods exccution results into a reward model used for best-of-N, while Self- Debugging (Chen et al. 2024b) incorporates error messages into refinement. A recent line of work tailors generation algorithms to language-condittonee digital agents-mont models that operate on diverse observation spaces X' such as images of web pages, and output sequences y representing actions including variants of refinement (Shinn et al. 2023 combined with learned evaluators (Pan et al. 2024
6 Token cost and performance analysis
A natural question is the cost of executing a given meta-generator, and its relationship with performance. There are several ways to measure cost, including the number tokens generated, the overall compute used during generation, or the runtime. In some cases, we would like to design an algorithm that improves as we add more cost, such as improving problem solving ability by generating more tokens. In other cases, we would like to minimize the cost. at fixed level of performance.
24

---

Published in Transactions on Machine Learning Research (11/2024)
Method
Input
Output
External
Cost Params
Ancestral Sampling
Tin
T
Reranking (general)
Tin * N Tin
I N T
N=
N,C, N
Best-of-N (log-p)
Best-of-N (LLM sequence scorer)
T+N
N (Tin
+
Transformation (general)
Tin N
T*N
C
N,C,
Self-consistency
T&N T*N
Weighted SC (seq. scorer)
Tim N
N+
N,C.
Step-level beam (log-p)
Ti N₂ Ne S Ti N₁ Ne S
T. N, N
No, Ne. N N,C N,,
Step-level beam (seq. scorer)
240
T. N₂ NN
N, S&C.. N Ca
Step-level DFS (seq. scorer)
240
Tm Ne S
T₃ + N₂ S
Refinement (general)
Ti (1 N.) Tim + (27in +1) Nr
T [1(1 N.) T + 27'+ N
N2
N,,C2
Refinement (self-foedback)
160
N,
Table 5: Token budget for representative algorithms from each meta-generation class. Reranking. Tin and T are the number of input tokens and output tokens for each call to the generalor, respectively. For simplicity, we assume the number of input and output tokens is constant across calls to the generator. C2 refers to the number of tokens required to call a scoring model (c.g., a prompted LLM) on an input and output sequence. LLM scorer refers to prompting a LLM with an input and output, and generating a scalar score (assumed to be token). Transformation. C. refers to the number of tokens required to call a transformation function (e.g., a prompted LLM) on N sequences. Step-level search. T. is the number of output tokens in a step, with S the maximum number of steps, such that T, * 2 T. N, is the number of candidates to keep after pruning (e-g., "beam size"), and N₂ is the number of expansions per iteration. We assume the cost of the scorer is equal to the cost of scoring full sequence (C.). Refinement. N, is the nunber of refinement iterations. C₂ refers to the number of tokens required to obtain external information during a refinement iteration.
6.1 Token budget
Meta-generators consist of calling generators, which leads to costs associated with generating lokens. For instance, common APIs charge by the number of tokens in the imput prompt and the number of output tokens. In general, meta-gencrators incur token costs from input tokens, output tokens, and external information.
For instance, a reranker that generates N sequences incurs a cost of Tin * N input tokens, T * N output tokens, and N Cg tokens to run the scoring model, where C, is the token cost of calling the scoring model on one sequence. When the scoring model is implementod by prompting an LLM and generating a scalar quality score (assumed cost token), the external information cost is N * (Tin + + Table 5 shows the token budget for representative algorithms from each meta-generation class.
Step-level vs. sequence-level search. Consider solving a mathematical problem by generating solu- tion that consists of multiple steps. Two strategies for doing so are (1) generating one step at time using step-level search algorithm, or (2) generating full solutions in transformation or re-ranking algorithm.
In this case, we can assume that T = T, 5, i.e., the total number of tokens in a solution (7) equals the number of tokens in a step (T,) times the number of steps (S). We can then use Table to reason about when step-level search can cost fewer tokens than sequence-levé search.
From Table 5) we see that step-level methods incur a cost. from generating output tokens that depends on the pruning parameter N6, the number of expansions per itcration Ne, and the number of iterations S. Assuming that T. S = T, step-level search has fewer output tokens than sequence-level search when No NN < N. For example, under these assumptions step-level beam with beam size of 16 and 64 expansions per iteration has the same number of output tokens as best-of-1024, while lowering the expansions per iteration to 32 would be half the output token cost compared to best-of-1024.
On the other hand, Table 5) shows that step-level search calls the scoring model more often than sequence- level search mothods. For instance, when N₂ N₂ = N, step-level beam search calls the scoring model N S times compared to N times with reranking. Therefore, one must also account for potential token costs associated with external information (e.g., sequence scores) when comparing meta-generator token budgets.
25

---

Published in Transactions on Machine Learning Research (11/2024)
Refinement vs. sequence-level search. Similarly, can compare the token budget for refinement versus sequence-level search. As seen in Tabll 5 general refinement algorithms have a lower outpui cost when N, < N, i.e, the number of refinements is less than the N in best-of-N. In practice this is often the case, c.g. Madaan et al. 2023) use N, = 3 in many experiments, while N typically ranges from 8 to 1024 in the literature. However, we need to factor the cost of external information. For instance, when generaling self-feedback as in Madaan et al. (2023), the output cost becomes 2T * N,, meaning that 3 refinements costs 77 output tokens, which still cheaper than best-of-8.
6.2 Scaling the token budget to improve performance
In various reasoning-related tasks such as mathematical problem solving, it has been widely observed that generation algorithms which generate multiple sequences and choose among the sequences (e.g., best-of- N, majority voting) can outperform generation algorithms that generate a single sequence (e.g., greedy
decoding) (Cobbe et al. 2021 Wang et al. 2023b
Azerbayev et al. 2024 Lightman al. 2024 Wang al.
2023a; Sun al. 2024a).
Figure shows plot from Sun et al 22224a] that compares the relationship between the gen- eration budget (in units of sequences) with three sequence-level approaches on the MATH500 bench- mark (Lightman et al. 2024). The plot shows that these algorithms can improve monotonically by in-
SFT-34b OPRM-34b (on PRM800K) Accuracy All (Level 1-5) Problems
55
Solved
50
creasing the generation budget. Moreover, each al-
45
gorithm has a different improvement as function of the generation budget. For instance, at budget of 1024 sequences, weighted voting is preferred to majority voting or best-of-N in terms of task per-
Robie Colemm
40
35
May
30
JM
Majority Voting
Weighted Voting w/ RM
& 25
formance. Recently, Chen et al. (2024a) found that some models can have a non-monotonic relationship between generation budget and voting performance.
Best-of-N w/ RM
20
16 32
64 128 256 5121024
N number solutions per problem
The idea of increasing the generation budget to im- prove performance has appeared in many applica- tions. For instance, AlphaCode (Li et al. 2022] generates up to million sampled programs that are then filtered using heuristics and execution results.
Figure 6: Plot from Sun et al. (022aa) Scaling behav- ior of three meta-generators in the number of samples N on mathematical problem solving (MATH500).
In theorem proving, Draft-Sketcc-Prrov (Jiang al. 2023) leverage the proof checker at generation time by generating and checking many formal proof candidates, resulting a monotonically increasing percentage of proven theorems function of the budget.
More formally, let q- ()(var)) x if y is correct, and O otherwise, where correctness may mean correct solution to mathematical problem, a valid proof, a program that passes test cases, etc. Then the goal of generation is y- = arg max q- x). Since the space of solutions y is too large, a meta-generator can approximate it by calling a generator multiple times,
y, = arg max q- (3/1z) DEy
(50)
RJ arg max g. (v())z))) (2), ""
(51)
where y" ~ o(-1x,pe)) It clear that performance should improve as N increases, so long as the generator q assigns probability mass to correct solutions. However, in practice we do not have access to g. at test time, so different meta-generators approximate (1 e.g. with learned verifier (z(2,)) y), or with a voting algorithm. The plot above shows that different approximations have different levels of effectiveness.
26

---

Published in Transactions on Machine Learning Research (11/2024)
6.3 Minimizing the token budget
A complementary direction is minimizing the generation budget to achieve given level of performance. One direction is to route generations to progressively more costly models. For instance, FrugalGPT (Chen) ct al. 2023b) first generates with a cheap model, then uses learned scoring function to determine whether to generate again with a more expensive model, leading lo significant cost reductions over calling GPT-4 in their experimental setting. Another direction is leveraging properties of specific mueaaggenration algorithms to reduce the number of calls. Aggarwal et al. (2023) propose to stop sampling in majority voting upon converging to majority.
6.4 Compute optimal inference
When choosing designing meta-generatoo,, key consideration is the cost of the meta-generator needed to achieve given level of performance. For example, running Monte Carlo Tree Search may give good task performance, but not if we only allow it to generate the same amount of tokens as parallel sampling. Relatedly, Kapoor et al. (2024b ab argue that performance comparisons of meta generation algorithms must be performed with respect to token budget and monctary cost, and that in some cases simple meta-geneeattin baselines can provide pareto-optimal cost-performance tradeoff compared to complex algorithms.
Wu et al. (2024) formalize these tradeoffs in terms of compute-optimal inference: the problem of choosing model size, number of generated tokens, and meta-generation algorithm that minimizes error subject to compute budget. Specifically, let. the error rale ((M,T;9) be function of the number of model parameters M, the number of generated tokens T, and the generator g. The goal is to minimize E' under the constraint g) is the compute used during inference, measured in floating- point operations:
c(M,T,g) = C, where c(M, T,g)
arg min (Mape(C), Tops Hops)) M.T.g c(M.T:))=C
E(M,
(52)
where MC))(C)), Topt (C), Sopt denotes the choice of model size, generated tokens, and meta-generator that achieves the lowest error with compute budget C. Wu et al. (2024) study tradcoffs between best-of-N, majority voting, and tree search variants, finding that sampling more tokens from smaller model often had better cost-performance tradeoffs compared to using a larger model at given compute budget. Moreover, Monte- Carlo tree search often had worse cost-performance tradeoffs than the other meta genergeeer.,ors. [Snell ct al. 2024) study similar cost-performance trade-offs between best-of-N, step-level scarch, and refinement.
6.5
Dependence on the underlying generator(s)
The defining property of meta-generators that they rely on calling other generation algorithms. Hence a second natural question to what degree their performance depends on the underlying generation algorithms.
Sampling parameters. Chen et al. 22021 found that the optimal temperature in best-of-N was dependent on N for code generation with the Codex model, with higher temperatures returning better performance for higher N. Many prior studies use temperatures or sampling parameters that are either unexplained or ad-hoc. For instance, Minerva (Lewkowyez al., 2022) uses majority voting with temperature 0.6 and nucleus sampling p 0.95. These settings have propagated into subsequent studics (Azerbayev et al. 2024
For some classes of meta-generators such minimum Bayes risk ($4.2.2), the effect of sampling parameters is relatively well-studied. For example, Freitag et al. (2023) investigate the impact of the underlying sampling strategy in MBR, finding variation across strategies, with epsilon sampling performing best for translation.
(aampte,Frriitag
7 Speeding up generation
In the precoding sections, we introduced generation algorithms (e.g., ancestral sampling, beam scarch) and meta-generatton algorithms (i.c., programs involving multiple generation calls), and discussed one aspect of efficient generation: making generation cost-effective in terms of the token budget. Next turn to another
27

---

Published in Transactions on Machine Learning Research (11/2024)
aspect of efficiency: the speed of (mett-)gennraation Speed is inherent concern of almost any practical application of generation algorithms: users typically want outputs quickly.
Meta-generators in particular raise demands for fast generation, since they often involve generating many sequences and coordinating multiple components. For example, the meta-generators shown in Figure 6 require generating and scoring 1024 sequences. There are at least two high-level strategies one can take to speed up generation: (1) speeding up the generation of each individual sequence, and (2) leveraging structure that comes from multiple generator calls, such as shared partial outputs or the structure of the overall meta-generation program. We will consider both of these below.
Before we start, it is worth noting two points. First, the notion of "speeding up" itself needs to be made more precise and measurable. To that end we provide background on the notions of lalency, throughput, and the idea that speed is often dependent on the hardware environment in which a meta- meta-generator is run.
Second, the topics in this section are part of rich, rapidly evolving research field that ranges from machine learning systems programming language design. It goes without saying that our survey here merely scratches the surface. We focus our discussion introducing key ideas, and on examining the interaction between the design space of (meta-)generation algorithms and generation speed.
7.1 Background
Goals of speeding up generation. Speeding up generation requires balancing between three high-level metrics: (1) latency, the time it takes to generale single output; (2) throughput, the rate at which outputs can be produced; and (3) quality, measures of model quality such as loss or downstream task metries. For instance, one might change the generation algorithm in a way that speeds up a single gencration (improving latency), but removes the ability to generale outpuls in parallel (degrading throughput). Other cases such as reducing the precision of model weights may improve latency and throughput, but degrade the model's task performance. Ideally, we would like to reduce latency, increase throughput, and maintain quality.
Hardware-aware optimization. The underlying hardware is key consideration for speeding up generation. LLMs are typically run on accelerators such as GPUs or TPUs.
In the case of GPUs, performance is largely dictaled by compute and memory bandwidth. Compute is typically measured via the number of floating-poii point operations (FLOP) used in a given operation, while memory bandwidth refers the rate at which data can be transferred to and from memory. For example,
A BC,
(53)
reads the matrices B, C from memory, computes BC on-chip, and writes the result out to memory. Similarly,
Y= ReeUU(XX)
(54)
must read X from memory, compute RcLU(X) on-chip, and write the result out to memory. However, these two operations have very different arithmetic intensities, defined the ratio of compute (in FLOP) to unit of memory read or written. This results in (53), for large enough B, C, being compute-bound (bottlenecked by the rate at which operations can be performed) while (54) for large X is memory-bound (bottlenecked by the speed of reading inputs and writing outputs to memory).
Thus, reducing the quantity of operations performed (in FLOPP) for a given step may not always proportion- ately transfer to on equivalent real-world speedup or cost reduction. This is exacerbated by the properties of recent accelerators-GPUs and TPUs are heavily specialized for matrix multiplication and other high- arithmetic intensity, heavily parallelizable workloads (NVIDIA 2017 2020). For example, the H100 can perform up to 989.4 TFLOP/s in BF16 within a dense matrix multiplication using Tensor Cores, but only 133.8 TFLOP/s of BF16 arithmetic (NVIDIA) 2022). This specialization and the fact that "naive" al- tempts to optimize performance oblivious to which operations may be the key bottlenecks may not achieve the anticipated gains-implict that hardwarc-aware optimization is a key viewpoint to take when socking speedy generation. Algorithmic and architectural co-design with the hardware (Dao et al. 2022 Dao 2023 Anthony al. 2024h has yielded some of the most significant speed gains in recent years, in contrast. to
28

---

Published in Transactions on Machine Learning Research (11/2024)
Type
Selected Examples
Strategy
Architectural
MQA 193
CQA 1. MLA
1
Efficient attention
RWKV 174.
Mamba
Transformer alternative
Compression
GPTQ 60
AWQ 13d. SqueezeLLM 106]
Quantize weights
LLM.int8(
10.
Smoothquant 230 QuaRot
Quantize activations
FlexGen
194.
KVQuant [8 W4 136.
Quantize KV Cache
Hardware-aware impl.
Rabe & Staats (202)) AltshAttention
4T
40
Efficient attention
Trilon [214] Torch compile [80] Cutlass
210
Libraries/ aibraries/toolinn
Parallelize over time
Speculative decoding
[2X
26
SpecInfer
157
Draft-then-verify
Table 6: Outline of classes of techniques for speeding up a single generation call.
approaches seeking to minimize theoretical complexity that are disconnected from the hardware level. On the flip side, however, Hooker (220)) discuss the notion of the hardware lottery- idea that co-design of novel techniques creates adverse selection effects, where research ideas "off the beaten path" are dispreferred because they interact less well with cxisting hardware.
7.2 Speeding up the generator
Generation algorithms with autoregressive language models depend on computing next-token distributions. Given an input sequence (yet, x), typical implementations start with an initial "prefill" step that computes
po po a) = (attmaa(((--1eee0))
(55)
Performing this step returns two outputs: po x), the probability distribution over immediate next tokens following (yet, 2) that we have discussod previously, and a "state" Spen. created as a byproduct of processing Vet, v. For a Transformer (Vaswani et al., 2017] Syer. is produced by retaining all keys and values from timesteps up to U/-1 within the attention for each layer This is termed the "Key-Value (KV) Cache" produced by attention at each layer. At this step, we may sample next-token y: from po(-Iuca,.z) x)).
Subsequently, to generate additional new tokens we may perform any number of "decoding" steps, where each step selects a token from a next-token distribution. For example, the t+ 1'th step selects a token using:
pa pa(-1uer+t I. Spe..) = softmax(se( (-B5e(1,,,,, Sysn.)))
(56)
Here, we feed the state Syge.r into the model, representing the already-processed sequence. Each decoding step saves on computations that are cached in the state, such as the attention keys and values from the preceding steps. After selecting the t + I'th token, the state is updated to Speet1.. These decoding steps may be repeated until we have finished generating sequence.
One can accelerate a single generation from LM by speeding up the time taken per step, such through architectural modifications, model compression, hardware-aware implementation decisions, by clever par- allelization during autoregressive generation. We discuss each of these in the following paragraphs.
Architectural modifications. One strategy is to modify the model architecture. For example, multi- query (Shazeer 2019 and grouped-query (Ainslic et al.] 2023a) attention propose the use of fewer key and value heads in translormers' attention, leading to reduced KV Cache sizes. Smaller KV Cache sizes can lower memory bandwidth demands, or provide the ability to process larger batches concurrently at a time by enabling more requests to be stored in GPU memory. Similarly, [DeepSeek-A] (2024) propose multi-headed latent attention, attempting to retain the reduced KV Cache of GQA while improving model quality. The O(t²) complexity of attention (O(t) for each decoding step) can slow generation down as sequences become longer, so another option is to forego the transformer architecture or its attention layer altogether. For example, traditional recurrent language models [Elman 1990 Mikolov et al., 2010) compute a next-token distribution by maintaining a hidden state, leading to a O(t) time and space complexity (O(1) per step).
TThe core attention operation is softmax (QKT/V/ V, where Q, K,K.V V E gixd are referred to as queries, keys, and values, respectively, is the time dimension, and is the hidden dimension.
29

---

Published in Transactions on Machine Learning Research (11/2024)
Recent architectures draw on ideas from recurrent language models (Hutchins et al
2022 Peng et al. 2023
De et al. 2024 Yang et al. 2024) and/or state-space models (Gu & Dao. 2023 Lieber et al.
2024) to achieve
sub-quadratic time and space complexities. Although models can occasionally be adapted post-hoc from a
transformer architecture to one of these more efficient variants (Zhang et al. 2024 Ainslic et al. 2023a this adaptation can degrade model quality or require substantial compute.
Model compression. Adjacent to architectural modifications, one can compress a model into more efficient form after the fact. Distillation can transfer knowledge from a more capable teacher model into a smaller one (Hinton et al., 2015 Sanh et al., 2020). or models can be quantized to reduce the floating- point precision of the model's weights which reduces the memory footprint of the model and in turn speeds up generation in memory bandwiddt--constrainee settings (Dettmers et al. (2022); FFranarr et al. (2023); Dettmers al. (2023); PyTorch (2023), inter alia). Model activations can also be quantized (Ashkboos ct al. 2024 Xiao et al. 2024a Lin et al., 2024b). Approaches to sparsify prune model weights (Frantar & Alistarh 2023), inter alia) can also be used. Such compression approaches frequently, but not always, degrade performance and require training to perform or to recover performance on a limited distribution.
Hardware-aware implementation. A number of optimizations may be performed without modifying the model architecture or what operations must. be performed, simply how they are performed.
For instance, Flash Attention (Dao et al. 2022 Dao 2023 famously overcomes the O(t²) space complexity
of self-attention by adapting the algorithm proposed by Rabe & Staats (2022) for computing self-attention
based on online softmax (Milakov & Gimelshein 2018 Jang et al.) 2019) and blockwise computation, crucially without changing the output of the attention mochanism, simply its mapping to hardware. Similarly, Flash Decoding (Dao et al. 2023) accelerates the attention operation during decoding by adding extra parallelism over the sequence dimension, allowing the GPU to be fully saturated even for small query and batch sizes, but only changing the order and mapping of operations on-device, not the end result (up to numeric procision).
Numerous soft ware tools Tiilet et al. 2019 Torch (223 Thakkar et al. (023)) inter alia) can enable fast decoding and efficient low-level implementation in practice. Overall, while architectural modifications to the model itself can increase the ceiling on generation speed, effective implementation is key for achieving performance anywhere near this ceiling on current accelerators.
Parallelization across time. Rather than speeding up the core next-token operation, the draft-then- verify (also called "speculative sampling" or "speculative decoding") pallern leverages clever parallelization during autoregressive generation. Draft-then-verify consists of generating proposed next-tokens with a fast method (c.g., a smaller model), computing next-token distributions given the proposed tokens in parallel, and either keeping or rejecting the proposed lokens.
For example, previously we briefly referred to speculative sampling (Leviathan al. 2022 2023a). This method assumes language model po(vel and an efficient draft model q Ver)). At a given step t, it generates continuation yt, Me+1..... .eth using q, then computes the next token distributions po(ylleet).... Po (c(+k) in parallel. Finally, it processes each proposed token, keeping it if g( (Verr) S pe(velVer), and rejecting it when q(ve (yee)) > pa pa (yer)) with probability pa pa( pa(wllerr) /// (B<r) or if a preceding token was rejected. Intuitively, as long as (i) generating with q() is much faster than computing the distributions with Pe in sequence, and (ii) the rejection rate is not too high, then speculative sampling will speed up generation without affecting the original modcl's output distribution or quality.
Chen et al,,
Several methods iterate ideas underlying speculative sampling, including guessing and verifying tree of proposed tokens (Miao et al., 2023b: Sun et al.) 2024b Chen et al. 2024ch, using alternative proposal models (Miao et al., 2023b] Cai et al. 2024), using prompt n-grams as proposals (Yang et al.] 2023b), or generating in parallel and reusing the generated n-grams as proposals (Fu et al. 2024). Interestingly, many speculative sampling approaches which require a separate draft model q() require more total FLOP in order
to generate given sequence (Chen et al.) 2023a Leviathan et al. 2023 Fu ct al. 2024). However, because the decoding step is typically memory-bound, the increased parallelism afforded is more than sufficient to provide substantial generation speedups.
30

---

Published in Transactions on Machine Learning Research (11/2024)
Type
Selected Examples
State reuse
PagodAttention memory sharing
[18
RadixAttention
252
State compression
Gisting 160,
KV Cache compression
136
251
Improved batching
Continuous batching 241 Disaggregated prefil
253
Program-level optimization
GPTT4 graph rewriting 252 DSPy
103
Table 7: Outline of techniques for speeding up meta-generation algorithms, requiring many calls to an underlying generator with often-predictable traflic patterns. Refer to the main text for more examples.
7.3 Speeding up meta-generation algorithms
While in 7..2 we note approaches to speeding up single autoregressive generation call, the space of possible optimizations is larger when considering usage patterns such as those found in meta-generation algorithms, where multiple or many calls are made to the same model over time, often in predictable way.
7.3.1 Leveraging shared prefixes.
The repeated model generation calls that occur in meta-generation algorithms crucially often share sim- ilarities in input. Most importantly, they oflen share preface across generation calls. This provides an opportunity to save on computation and dramatically speed up generation throughput.
KV Cache and state reuse. In typical transformers, because the KV Cache is updated by appending the keys and values of new token to the cache, the KV Cache for shared prefixes can be "prefilled" only single time and reused across generation calls that share this input prefix. For example, in parallel meta- generation algorithms ($4.2) such as Bost-of-N, when producing each candidate y² requires "prefill" step computing S, in order to sample yf and each successive token in y². Simply computing Sz once and reusing it when sampling each y' can save significant computation and time, in effect reducing the input token count for such algorithms by factor of N (Table 5).
N-best list (y(m)) Jn=i ~ 9, generating
Making such state sharing efficient requires careful handling the state in memory, but can significantly speed up throughput by allowing more outputs to be processed at a time as a result of lightened GPU memory requirements (Kwon et al., 2023). It can also be generalized beyond single prefix being shared (Zheng et al., 2023) in order handle branching, complex trees of already-processee inputs. Later work has shown that redundant computation can be eliminated even further, allowing specific speed optimizations in the presence of shared prefixes (Juravsky et al. 2024
KV Cache and state compression. A complementary line of work approaches the challenge of handling reused model states or KV Caches efficiently by compressing them, reducing the storage required. Gisting Mu et al. 2023 and other related techniques (Chevalicr et al. 2023 Ge ct al. 2024b) tackle the sub-problem of long, frequenlly-recurriin inpul prompls by learning to produce a series "soft" tokens (trained token embeddings) which compress given large input prompt into a much smaller, more compact state. These methods can be viewed generalization of prefix tuning prompt tuning (Li & Liang 2021 Lester et al.
2021 Other methods explore the shortening of KV Caches via determining which items to retain or evict
from the input prompt,, at each step whether to append new keys and values to the cache (Ge et. al.
2024a
Liu et al.) 2023 Zhang et al.) 2023 Li et al.) 2024b Nawrot et a..] 2024 Raposo et al.] 2024 Xiao et al. 2024b). Much like model weights, the KV Cache can also be compressed via reducing its storage procision, such as via quantization (Sheng el al. 2023 Lin el al.) 2024b Zhao el al.] 20224c Zirui Liu el al. Thus, the memory bandwidth cost of loading the KV Cache from memory reduced, and more tokens' caches can be fit onto GPU memory. However, these compression techniques can lose model quality.
2023
7.3.2 Optimizing computational graphs
Finally, class of optimizations takes into consideration the programmatic structure of the meta-generator.
31

---

Published in Transactions on Machine Learning Research (11/2024)
Caching. Caching model state across calls to generator done by Zheng et al. (2023): : Juravsky et al.
(2024); Kwon et al. (0023) and discussed previously can be beneficial for algorithms that involve backtracking (e.g., tree search), or in general programs that involve duplicate generator calls.
Graph optimization. Additionally, the computational graph of such programs can be optimized and rewritten with efficiency in mind, by hand or automatically. For example, SGLang uses GPT-4 its optimization of programs to reorder computational graph nodes (Zheng et al. 2023), and DSPy optimizes performance cost of LM programs via automating prompt engineering (Khattab et al. 2024
Algorithm-specife optimization. When the specific algorithm is known, optimizations can be made even more targeted, such as speeding up voting algorithms by stopping early upon converging to a majority (Ag- garwal et al. 2023), or a host of methods that optimize MBR-style algorit including confidence-baset hypothesis pruning (Cheng & Vlachos 2023) or leveraging reductions of MBR (Jinnai & Ariu 2024
7.4 Libraries and tools for fast generation
We briefly note a few useful libraries and tools for fast and efficient generation, although the space of useful tools and libraries is in particular espccially subject to fast change. vLLM (Kwon et al. 2023) is a highly popular library that introduced PagedAutention and implements a number of up-to-date optimizations for fast generation, including continuous batching, prefix caching and reuse, various model and KV cache quantization techniques, speculative docoding, and more. [ensorRT-LLMM is another highly efficient LLM serving library. Especially relevant to this survey, SGLang (Zheng et al. 2023 builds on vLLM to provide domain-specific language optimized for meta-generation.
GPT-Fast (PyTorch 2023) provides a minimal implementation of latency-constrainee fast decoding in Py- Torch, and is designed to be useful for prototyping new ideas and to demonstrate the ease of optimizing low-latency unbatched decoding workloads using simple tools such as torch. compile.
For end users, especially those without easy access data center-grade or high-end consumer-grade GPUs, number of libraries also implement fast decoding on CPU, which presents its own set of challenges not fully explored in this paper. Libraries such as Llama.cpp are popular for consumers, and libraries such as DeepSpeed-Inng Inferencce (Aminabadi et al. 2022 or PowerInfer (Song et al. 2023 Xue et al. 2024] explore optimization ions when offlouding activations or parameters lo slower-access storage or CPU RAM, which require systems considerations beyond those discussed for the more typical homogenous accelerator setting.
8 Discussion: why use sophisticated generation algorithms?
Finally, we return to the question that we posed in the introduction: why are sophisticated generation algorithms needed al all? For example, we might imagine that simply sampling once from the model's unmodified output distribution, y ~ po(y)z) is sufficient. We offer some takeaways based on our survey.
Takeaway 1: iron out degeneracies in the learned distribution. In $3. and $3.3 we discussed introducing token-level adapter algorithms to avoid errors in the model's distribution (for instance, when the learned model assigns too much probability to sequences that have low or zero probability under the true distribution). At a qualitative level, examples encountered in practice include ancestral sampling resulting in incoherent sequences. At another extreme, MAP decoding algorithms ($3.1) h can result in unnaturally repetitive sequences that are nevertheless assigned high probability by the model, or even empty sequences. These degeneracies motivate the use of generation algorithms with alternative goals, such as minimizing Bayes Risk 4.2.2 the use of a token-level adapter. In these cases, generation algorithms offer mechanism for modifying the resulting generation distribution to remove these errors.
Moving forward. As models improve, will generation algorithms for these cases still be needed? Since the aforementioned errors stem from a model imperfection, it is plausible that future models will not have these imperfections. Morcover, taking simplicity of the overall generation system as an objective to strive for, we might explicitly strive to ultimately remove the generation algorithm for these cases. On the other hand,
httpe://gthhbbbommggggggg/////n/
32

---

Published in Transactions on Machine Learning Research (11/2024)
imperfections may come from subtle design choices, such as the use of softmax (Finlayson et al. 2024a or the choice of an autoregressive architecture. Therefore, we speculate that on the way to achieving this objective, it will remain important to identify degeneracies in existing models, introduce practical methods to mitigate them, and ultimately gain an understanding that can be used in the design of now methods.
Takeaway 2: align the generation distribution with a new objective. Above we discussed how the learned distribution po may not equal the desired distribution of generations q- (e.g., $2.2.3 $3.4). For instance, language modeling corpora often contain sequences considered offensive in many contexts (Gehman ct al. 2020), and we may want to generate only non-offensive outputs. We have seen examples of generation algorithms that reweight the model's distribution using another model (e.g., one trained to adjust the distribution so that it optimizes a non-toxicity reward, $3.4. or draw a large number of samples from the model and select. one with a reward function (a form of rejection sampling, $1.2.3). In these cases, the generation algorithm offers layer of "control" over the generation distribution, allowing us to shift the generation distribution to a desired one.
Moving forward. Moving forward, we speculate that the language model's learned distribution will not always align with the desired distribution for all possible uses. Thus, using a generation algorithm to shift the model's distribution to a desired one may withstand the test of time. On the other hand, previously we discussed the connection between generation algorithms and reinforcement learning (e-g., see refer to the discussion of Equations 19 29 Indeed, if we have reward function, then for a particular application model may be finetuned to match the distribution induced by the reward function, offering potential channel to removing the complexity associated with generation algorithms.
In the near term, users may interact with models through black-box APIs that are simply imperfect for their application of interest, but obtaining a filtering function or scoring model is relatively straightforward. Thus we speculate that in practical cases, users will continue to benefit from algorithms such as rejection sampling ($4.2.3) that shift the generation distribution using repeated calls to the generator model.
Takeaway 3: dynamic computation. In $ we discussed how generation algorithms can be viewed as searching through the output space for a desired sequence ($4.3). and that generation algorithms offer a mechanism for using compute to expand the coverage of states explored during the search. For example, best-of-N algorithms (Equation 5) use compute to search for solution by generating N hypotheses. More formally, we can write down the objective of many algorithms approximating the maximization of some scoring function, and doing so with solution as the number of samples increases (e.g., see Equations 30 50). We saw an example (Figure 6) where taking this approach was effective for inercasing the probability of a generator's output being correct in reasoning problems. In this sense, generation algorithms offer a mechanism for dynamically expending compute with a language model to improve performance.
campling-based approximation indeed results in a better approximate
Moving forward. Moving forward, see several cases. For some tasks, models may become so good that single sequence is all that is needed to arrive at a desired state with near 100% probability. In these cases, the generation algorithm may not be useful. In challenging cases, the model may have acquired a useful representation, but may benefit from exploring the output space through backtracking, revision, etc. before arriving at a final solution. In these cases, the computation expended at inference time remains useful. Nevertheless, there are at least two potential alternatives to generation algorithms with respect. to dynamic computation. One is building dynamic computation into the architocture (Raposo et al., 2024) or lcarning algorithm &Goyal et al. 2024 Zelikman et al. 2024a), so that allocating more compute to harder problems is automatically handled by the model. A second alternative is learning the search algoritim (Chang et al.
2015 Lehnert et al.] 2024 Gandhi et al. 2024), then using vanilla generation algorithm.
In the nearer term, at the application level users may interact with models through black-box APIs that are simply imperfect. Thus we speculate that users will continue to benefit from using the API as a hypothesis generator that is called multiple times within a search algorithm, rather than a model that is called once for an answer. From a research perspective, the relationship between generation-time compute and performance requires further investigation. For instance, we saw above that the relationship varies by generation algorithm
33

---

Published in Transactions on Machine Learning Research (11/2024)
in voting settings (.6.2). In general, designing algorithms that optimally leverage test-time compute and studying their trade-ofls requires further research (Chen et al. 2024a Snell et al. 2024 Wu et. al. 2024
Finally, meta-generators can be seen as a new kind of computational graph that itself can be optimized, such as with architecture search Ghad-Falcon et al. 2024 or even with a gentaaggneratorr (e.g., refinement Yuk- sekgonul et al. 2024) ). These emerging perspectives open many future directions to explore.
Takeaway 4: leveraging external information. In S we saw several ways which generation algo- rithms incorporate information that is external to the language model. This includes predictions from other modcls, prompts, external tools or verifiers, or generally inputs and outputs from an external environment.
Moving forward. Moving forward, we may expect that generation algorithm that has information beyond that present in a language model may exceed the performance of the language model on its own. We speculate that language models on their own may cither be unable to solve subproblems that are required for a complete generation (e.g., performing an algebraic computation that is simple for a computer algebra system, or retrieving a piece of information that. outside of the model's parametric knowledge), or that doing so is an inefficient allocation of computation. Moreover, we expect that in many challenging settings, it may be necessary to decompose problems into cascade of generations, interact with an environment, and iteratively arrive at a final generation. In all of these cases, generation algorithms that incorporate external information, be it in prompts that alter model's distribution within a chain ($4.1) or environmental feedback offer a range of possibilities to explore in future research.
($4.4 $5.2,,
Finally, we expect that discrete autoregressive sequence generators will increasingly be used in domains traditionally outside of those considered in natural language processing, such as a component in an agent that receives states and lakes actions in potentially stochastic environment. In these cases, using external information is inherent to the problem. How this translates generation algorithms remains open area of rescarch. For instance, notions of planning (c.g., $4.3 $.2 are natural fits for planning actions in interactive
enviromments. In the near term, we expect to see generation algorithms developed in the context of language generation such as tree search and refinement ($ (.44 integrated into these settings.
Takeaway 5: speed up generation. Finally, in 7 we saw examples of how generation algorithms can themseeves be used to speed up generation, even in the case of ancestral sampling from a language model ($..2). On the other hand, the increasingly diverse configurations of meta-generation algorithms present new demands and opportunities for fast generation ($7.3).
Moving forward. Regardless of the future form of sequence generators, we expect that there will always be a need and opportunity for speeding up generation. Naturally, one must consider the expected marginal benefit of developing a new method for speeding up generation compared to existing methods. Given the evolving nature of model scale, architectures, applications, and compute environments, we expect the marginal benefits of new methods to remain high for the foreseeable future. In particular, optimized generation algorithms that involve multiple models, external information, and/or cascaded generation is a nascent research area.
9 Conclusion
We surveyed generation algorithms for language models. We motivated generation algorithms, formalized their goals, and provided a unified treatment of three themes: token-level generation algorithmms, meta- generation algorithms, and efficient generation. Our survey brings together past research from the decoding, LLM reasoning, and machine learning systems communities, and identifies directions for future work.
Acknowledgments
We thank Akari Asai, Rob Brekelmans, Yejin Choi, Saibo Geng, Konstantin Golobokov, Shibo Hao, Omar Khattab, Taehyeon Kim, Chufan Shi, Aditi Raghunathan, Sasha Rush, Peter West, Mert Yuksekgomul, and the TMLR reviewers for helpful discussions. This work was partially supported by NSF DMS-2134012 CCF-2019844, IARPA 0022-2207220008.. SW would like to thank Convergent Research. Part of this work done while Z. Harchaoui was visiting the Simons Institute for the Theory of Computing.
34

---

Published in Transactions on Machine Learning Research (11/2024)
References
David H. Ackley, Geoffrey E. Hinton, and Terrence J. Sejnowski. A learning algorithm for boltzmann machines. Cognitive Science, 9(1):147 169, 1985. ISSN 0364-0213. doi: https://
doi.org/10.1016// 00000011/0000002200100 (0884-0213(85)800022 URL https://www.sciences 50364021385800124
Pranjal Aggarwal, Aman Madaan, Yiming Yang, and Mausam. Let's sample step by step: Adaptive- consistency for efficient reasoning and coding with llms. In Conference on Empirical Methods in Natural Language Processing, 2023. URL httpps://apls www.nticschollatttttteteteooo
oorptt/sssss...ooooo/o/oo//ssso wwt.:oooooooo..0558.3.... 258823191
Joshua Ainslie, James Lee-Thorp, Michiel de Jong, Yury Zemlyanskiy, Federico Lebron, and Sumit Sang- Training generalized multi-query transformer models from multi-head chockpoints. In Houda Bouamor, Juan Pino, and Kalika Bali (eds.), Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pp. 4895 4901. Association for Computational Linguistics, 2023a. doi: 10.18653/vv http:////222.eeme 2tt22222....mmpmmm main.298.. URL https:://aclaatholoo...r//////// wttp:///00.....mmmammaa........ emnlp-main. 298
hai. GQA:
Joshua Ainslie, James Lee-Thhoe Lee-Th Michiel de Jong, Yury Zemlyanskiy, Federico Lebrón, and Sumit Sanghai. Gqa: Training generalized multi-query transformer models from multi-head chockpoints, 2023b.
Reza Yazdani Aminabadi, Samyam Rajbhandari, Minjia Zhang, Ammar Ahmad Awan, Cheng Li, Du Li, Elton Zheng, Jeff Rasley, Shaden Smith, Olatunji Ruwase, and Yuxiong He. Deepspeed inference: Enabling efficient inference of transformer models at umprecedented scale, 2022.
Quentin Anthony, Jacob Hatef, Deepak Narayanan, Stella Biderman, Stas Bekman, Junqi Yin, Aamir Shafi, Hari Subramoni, and Dhabaleswar Panda. The case for co-designing model architectures with hardware, 2024.
Saleh Ashkboos, Amirkeivan Mohtashami, Maximilian L. Croci, Bo Li, Martin Jaggi, Dan Alistarh, Torsten Hoefler, and James Hensman. Quarot: Outlier-free 4-bit inference rotatod Imss, 2024.
Amanda Askell, Yuntao Bai, Anna Chen, Dawn Drain, Deep Ganguli, Tom Henighan, Andy Jones, Nicholas Joseph, Ben Mann, Nova DasSarma, Nelson Elhage, Zac Haffield-Dodds, Danny Hernandez, Jackson Kernion, Kamal Ndousse, Catherine Olsson, Dario Amodei, Tom Brown, Jack Clark, Sam McCandlish, Chris Olah, and Jared Kaplan. A general language assistant as a laboratory for alignment, 2021.
Zhangir Azerbayev, Hailey Schoelkopf, Keiran Paster, Marco Dos Santos, Stephen Marcus McAleer, Al- bert Q. Jiang, Jia Deng, Stella Biderman, and Sean Welleck. Llemma: An open language model for mathematics. In The Twelfth International Conference on Learning Representations, 2024. URL
https://openrevieew wttp:/rrrwieeeeeeeefooo/i//ddddm nett/Forum2idd-NNNRRR11.
Yuntao Bai, Saurav Kadavath, Sandipan Kundu, Amanda Askell, John Kernion, Andy Jones, A. Chen, Anna Goldie, Azalia Mirhoseini, C. McKinnon, Carol Chen, Catherine Olsson, C. Olah, Danny Hernandez, Dawn Drain, Deep Ganguli, Dustin Li, Eli Tran-Johnson, F. Perez, Jamie Kerr, J. Mueller, Jeff Ladish, J. Landau, Kamal Ndousse, Kamilè Lukošiūté, Liane Lovitt, Michael Sellitto, Nelson Elhage, Nicholas Schiefer, Noem'i Mercado, Nova Dassarma, R. Lasenby, Robin Larson, Sam Ringer, Scott Johnston, Shauna Kravec, S. F. Showk, Stanislav Fort, Tamera Lanham, Timothy Telleen-Tawton, Tom Conerly, T. Henighan, Tristan Hume, Sam Bowman, Zac Hatficld-Dodds, Benjamin Mann, Dario Amodoi, Nicholas Joseph, Sam McCandlish, Tom B. Brown, and Jared Kaplan. Constitutional ai: Harmlessness from ai feedback. ArXiv preprint, abs/2212.080733, 2022. URL https://arxiis http:///axxxv.or/ab/////// 08073
Sourya Basu, Govardana Sachitanandam Ramachandran, Nitish Shirish Keskar, and Lav R. Varshney. Miro- stat: a neural text decoding algorithm that directly controls perplexity. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021.
URL http:://ppperrvveeeee/e///rrrrrr
Ahmad Beirami, Alckh Agarwal, Jonathan Bcrant, Alex D' D'Amour, Jacob Fisenstein, Chirag Nagpal, and Ananda Theertha Suresh. Theoretical guarantees on the best-of-n alignment policy. 2024. URL https:
35

---

Published in Transactions on Machine Learning Research (11/2024)
Amanda Bertsch, Alex Xie, Graham Neubig, and Matthew Gormley. It's MBR all the way down: Modern generation techniques through the lens of minimum Bayes risk. In Yanai Flazar, Allyson Ettinger, Nora Kassner, Sebastian Ruder, and Noah A. Smith (eds.), Proceedings of the Big Picture Workshop, pp. 108-122. Association for Computational Linguisties, 2023. doi: 10.18653/vo 101653/v1/// /2033 biihee/ggppctrrr-11. URL https://aclanthology org.ooggg///// bi giiictuue-11.9
Macicj Besta, Nils Blach, Ales Kubicok, Robert Gerstenberger, Lukas Gianinazzi, Joanna Gajda, Tomasz Lehmann, Michal Podstawski, Hubert Niewiadomski, Piotr Nyezyk, and Torsten Hoefler. Graph of Thoughts: Solving Elaborate Problems with Large Language Models. Proceedings of the AAAI Con- doi: 10.1609/
ference Artificial Intelligence, 38(16))17662--76690 2024.
URL
https://ojs..aaatt htw.aaa.ogggg..ee....../aaaaaaaa
Luca Beurer-Kellner, Marc Fischer, and Martín T. Vechev. Prompting is programming: A query language for large language models. Proceedings of the ACM on Programming Langwages, 7:1946 1969, 2022.
Luca Beurer-Kellner, Marc Fischer, and Martin T. Vechev. Guiding ilms the right way: Fast, non-invasive constrained generation. ArXiv, abs/
2024.
Peter Bickel and Kjell Doksum. Mathematical Statistics: Bosic Ideas and Selected Topics., volume 56. 1977.
doi: 10.2307 222007222800 /2866333.
Peter F. Brown, Stephen A. Della Pietra, Vincent J. Della Pietra, and Robert L. Mercer. The mathematics of statistical machine translation: Parameter estimation. Computational Linguistics, 19(2):263311, 1993.
URL https://aclantholll http:///lanttoooooooooo///////// org/J93-2003
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanic Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Ben- jamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), Advances in Newral Information Pro- cessing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NewrIPS 2020, December 6-12, 2020, virtual, 2020. URL https::/proceedinng
nww. http.rrrppppccppppr////000000
/ttcc//6bfcbb4677488bbaacalllllb waw.aaaaaaa...a.aaaaatatttt.tt.. Abstract.
Tianle Cai, Yuhong Li, Zhengyang Geng, Hongwu Peng, Jason D. Lee, Deming Chen, and Tri Dao. Medusa: Simple Ilm inference acceleration framework with multiple decoding heads. arXie preprint arxiv 2401.10774, 2024.
Nicholas Carlini, Daniel Paleka, Krishnamurthy Dvijotham, Thomas Steinke, Jonathan Hayase, A. F. Cooper, Katherine Lee, Matthow Jagielski, Milad Nasr, Arthur Conmy, Eric Wallace, David Rolnick, and Florian Tramèr. Stealing part of a production language model. ArXiu preprind, abs/2403.06634, 2024.
URL https::/arxxv.orgg//
06634
Louis Castricato, Alexander Havrilla, Shahbuland Matiana, Michael Pieler, Anbang Ye, Tan Yang, Spencer Frazier, and Mark Riedl. Robust preference learning for storytelling via contrastive reinforcement learning, 2022.
Kai- Wei Chang, Akshay Krishnamurthy, Alekh Agarwal, Hal Daumé I11, and John Langford. Learning to scarch better than your teacher. In Francis R. Bach and David M. Blei (ods.), Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, 6-11 July 2015, volume 37 of JMLR Workshop and Conference Proceedings, pp. 2058 2066. JMLR.org, 2015. URL//http://procediiin
mlr. pT.prrss/v37/chaaghh html
Eugene Charniak and Mark Johnson. Coarse-to-fine n-best parsing and MaxEnt discriminative reranking.
In Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL '05), pp. 173-180. Association for Computational Linguistics, 2005. doi: 10.3115 http///219981111111 URL https:
//aclaantoology..or///5--000
36

---

Published in Transactions on Machine Learning Research (11/2024)
Harrison Chase. LangChain, 2022. URL http:////sstttoooooo/////aaaaaaa
Charlic Chen, Scbastian Borgeaud, Geoffrey Irving, Jean-Baptiste Lospiau, Laurent Sifre, and John Jumper. Accelerating large language model decoding with speculative sampling, 2023a.
Lingjiao Chen, Matei Zaharia, and James Zou. Frugalgpt: How to use large language models while reducing cost and improving performance, 2023b.
Lingjiao Chen, Jared Quincy Davis, Boris Hanin, Peter Bailis, Ion Stoica, Matei Zaharia, and James Zou. Are more Ilm calls all you need? lowards scaling laws of compound inference systems, 2024a.
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde, Jared Kaplan, Harrison Edwards, Yura Burda, Nicholas Joseph, Greg Brockman, Alex Ray, Raul Puri, Gretchen Krueger, Michael Petrov, Heidy Khlaaf, Girish Sastry, Pamela Mishkin, Brooke Chan, S. Gray, Nick Ryder, Mikhail Pavlov, Alethea Power, Lukasz Kaiser, Mohammad Bavarian, Clemens Winter, Philippe Tillet, F. Such, D. Cummings, Matthias Plappert, Fotios Chantzis, Elizabeth Barnes, Ariel Cerbert-Vosss, William H. Guss, Alex Nichol, Igor Babuschkin, S. Balaji, Shantanu Jain, A. Carr, J. Leike, Joshua Achiam, Vedant Misra, Evan Morikawa, Alec Radford, M. Knight, Miles Brundage, Mira Murati, Katic Mayer, P. Welinder, Bob Mc- Grew, Dario Amodei, Sam McCandlish, I. Sutskever, and Wojeiech Zaremba. Evaluating large language models trained on code. ArXiv preprint, abs/2107.088
2021. httptt:/s//// http://aaxxvvoorgabbb///sss/ wwtp:oog//////eeeeeoooe /11./////////0033///
Xinyun Chen, Renat Aksitov, Uri Alon, Jie Ren, Kelan Xiao, Pengcheng Yin, Sushant Prakash, Charles Sutton, Xuezhi Wang, and Denny Zhou. Universal self-consistency for large language model generation, 2023c.
Xinyun Chen, Maxwell Lin, Nathanael Schärli, and Denny Zhou. Teaching large language models to self- debug, 2023d.
Xinyun Chen, Maxwell Lin, Nathansel Schärli, and Denny Zhou. Teaching large language models to self- debug. In The Twelfth International Conference on Learning Representations, 2024b. URL /ttps:// openreview. www..ntt/orummiiikuiiitiktt
Zhuoming Chen, Avner May, Ruslan Svirschevski, Yuhsun Huang, Max Ryabinin, Zhihao Jia, and Beidi Chen. Sequoia: Scalable, robust, and hardware-aware speculative decoding, 2024c.
Julius Cheng and Andreas Vlachos. Faster minimum Bayes risk decoding with confidence--ased pruming. In Houda Bouamor, Juan Pino, and Kalika. Bali (eds.). Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pp. 12473-12480. Association for Computational Linguisties, 2023. doi: 10.18653/v1 202000..mmlp-mmiinn........ URL httpss//aclanthologg.oor
eetp233.mmppmmi..... 767
Alexis Chevalier, Alexander Wettig, Anirudh Ajith, and Danqi Chen. Adapting language models to compress contexts, 2023.
Yizhou Chi, Kevin Yang, and Dan Klein. Thoughtseulpt: Reasoning with intermediate revision and search. 2024. URL htt.://s//ppp.ssmmaacccccorrrrrr
269010000
Krishna Teja Chitty-Venkata, Venkata, Sparsh Mittal, Murali Emani, Venkatram Vishwanath, and Arum K. Somani. A survey of techniques for omtimining transformer inference, 2023.
07982
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman. Training verifiers to solve math word problems. ArXiu preprint, abs/2110.141688 2021. URL https://arxivvoog:
111121110.11188
Michael Collins. Discriminative reranking for natural language parsing. In Pat Langley (ed.), Proceedings of the Seventeenth International Conference on Machine Learning (ICML 2000), Stanford Universily, Stanford, CA, USA, June 29 July 2, 2000, pp. 175- 182. Morgan Kaufmann, 2000.
Tri Dao. Flashattention-2 2: Faster attention with better parallelism and work partitioning. ArXiv preprint, fts/2307.086691 2023. URL. http:pp://aaa.i.oo//aa////////// 08691
37

---

Published in Transactions on Machine Learning Research (11/2024)
Tri Dao, Daniel Y. Fu, Stefano Ermon, Atri Rudra, and Christopher R'c. Flashattention: Fast and memory- efficient exact attention with io-awareness. ArXiv preprint, (0ss/2205.1441 2022. URL https://axxi. org/abs/2205. 14135
Tri Dao, Daniel Haziza, Francisco Massa, and Grigory Sizov. Flash-decoding for long-context inference. 2023. URL
Soham De, Samuel L. Smith, Amushan Fernando, Aleksandar Botev, George Cristian-Muraru, Albert Gu, Ruba Haroun, Leonard Berrada, Yutian Chen, Srivatsan Srinivasan, Guillaume Desjardins, Arnand Doucet, David Budden, Yee Whye Teh, Razvan Pascanu, Nando De Freitas, and Caglar Gulcehre. Griffin: Mixing gated linear recurrences with local attention for efficient language models, 2024.
DeepSeck-AI. Decpsock-v2: A strong, cconomical, and efficient mixture-of-cxperts language model, 2024.
Haikang Deng and Colin Raffel. Reward-augmented decoding; Efficient controlled text generation with a uni- directional reward model. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing. Association for Computational Linguistics, 2023, doi: (118653/v1/222/ emm..p..mmppppppm... emnlp-main. main. URL
http://dx.do1: org. 18653/v1/2023 w0w.2.3.mmmmpmmmiin... 721.
Tim Dettmers, Mike Lewis, Younes Belkada, and Luke Zettlemoyer. GPT33int8(): 8-bit matrix multiplication for transformers at scale. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL http:::/ooenrrvviee.neeeffroorr dXiGWqBoxaD
Tim Dettmers, Ruslan Svirschevski, Vage Egiazarian, Denis Kuznedelev, Elias Frantar, Saleh Ashkboos, Alexander Borzunov, Torsten Hoefter, and Dan Alistarh. Spqr: A sparse-quantized representation for near-lossless Ilm weight. compression, 2023.
Sander Dieleman. Musings on typicality, 2020. URL hettss///eramme.iiihddd.o/////// html
David Dohan, Winnie Xu, Aitor Lewkowyez, Jacob Austin, David Bieber, Raphael Gontijo Lopes, Yuhuai Wu, Henryk Michalewski, Rif A. Saurous, Jascha Sohl-dickstein, Kevin Murphy, and Charles Sutton. Language model cascades, 2022. URL httpps:/aarxiw.orr//bbbsss
10342
Randal Douc, Eric Moulines, and David Stoffer. Nonlinear time series: Theory, methods and applications with examples. CRC press, 2014.
Yann Dubois, Xuechen Li, Rohan Taori, Tianyi Zhang, Ishaan Gulrajani, Jimmy Ba, Carlos Guestrin, Percy Liang, and Tatsunori B. Hashimoto. Alpacafarm: A simulation framework for methods that learn from human feedback, 2023.
Nouha Dziri, Ximing Lu, Melanic Sclar, Xiang Lorraine Li, Liwei Jiang, Bill Yuchen Lin, Sean Welleck, Peter West, Chandra Bhagavatula, Ronan Le Bras, Jena D. Hwang, Soumya Sanyal, Xiang Ren, Allyson Ettinger, Zaid Harchaoui, and Yejin Choi. Faith and fate: Limits of transformers on compositionality. In Teirth- Conference on Neural Information Processing Systems, 2023. URL hhttps://openrrviiew net/forum?id-=Fcckkr333
Bryan Eikema. The effect of generalisation on the inadequacy of the mode. In Raúl Vázquez, Hande Celikkanat, Dennis Ulmer, Jörg Tiedemann, Swabha Swayamdipta, Wilker Aziz, Barbara Plank, Joris Baan, and Marie-Catherine de Marneffe (eds.), Proceedings of the 1st Workshop on Uncertainty-wuar NLP (UncertaiNLP 2024), pp. 87-92. Association for Computational Linguisties, 2024. URL https: //aclanthology.orgg htt.ttoo.ogg.ogg////a...rrrrrrar
Bryan Eikema and Wilker Aziz. MAP decoding all you need? the inadequacy of the mode in neural machine translation. In Proceedings of the 28th International Conference on Computational Linguisties, pp. 4506-4520. International Committee on Computational Linguistics, 2020. doi: 10.18653/v1/2022 coling-main.39k 398. URL http:::/accarttooooyy.o////////a wttp:///200....ooomaama.........
38

---

Published in Transactions on Machine Learning Research (11/2024)
Jeffrey L. Elman. Finding structure in time. Cogn. Sci., 14:179-211, 1990.
URL https://api.
semanticscholar httpa//ii.....ooooooo//ooooo/o//
Angela Fan, Mike Lewis, and Yann Dauphin. Hierarchical neural story generation. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguisties (Volume Long Papers), pp. 889 898. Association for Computational Linguisties, 2018. doi: 10.18653/11/P18-1053 URL https: //aclanntollog..org/P11----
Matthew Finlayson, John Hewitt, Alexander Koller, Swabha Swayamdipla, and Ashish Sabharwal. Clos- ing the curious case of neural text degeneration. In The Twelfth International Conference on Learning Representations, 2024a. URL
Matthew Finlayson, Xiang Ren, and Swabha Swayamdipta. Logits of api-protected llms leak proprietary information. ArXiv preprint, abs/2408.09559, 2024b. URL
wttp://www...rrraab////...../. 09539
Elias Frantar and Dan Alistarh. Sparsegpt: Massive language models can be accurately pruned in one-shot, 2023.
Elias Frantar, Saleh Ashkboos, Torsten Hoefler, and Dan Alistarh. OPTQ: Accurate quantization for gen- erative pre-trained transformers. In The Eleventh International Conference on Learning Representations, 2023. URL
Markus Freitag and Yaser Al-Onaizan. Beam search strategies for neural machine translation. In Proceed- ings of the First Workshop on Newral Machine Translation, pp. 56 60. Association for Computational Linguistics, 2017. doi: 10.
URL http::/awllaattoooooooogg///////
Markus Freitag, Behrooz Ghorbani, and Patrick Fernandes. Epsilon sampling rocks: Investigating sampling strategies for minimum Bayes risk decoding for machine translation. In Houda Bouamor, Juan Pino, and Kalika Bali (eds.), Findings of the Association for Computational Linguistics: EMNLP 2023, pp. 9198- 9209. Association for Computational Linguistios, 2023. doi: 10.18653/v1 /220////v/222..///// /202/222222nnn. finggiiniiiingggge........ URL
https://aallantholgg...rg. org.:223....g/22..... wtt..orr///....iiinnee.eeee
Yichao Fu, Peter Bailis, Ion Stoica, and Hao Zhang. Break the sequential dependency of 1lm inference using lookahead decoding, 2024.
Kanishk Gandhi, Denise Lec, Gabriel Grand, Muxin Liu, Winson Cheng, Archit Sharma, and Noah D. Goodman. Stream of search (sos): Learning to search in language, 2024.
Leo Gao, John Schulman, and Jacob Hilton. Scaling laws for reward model overoptimizationn In International Conference on Machine Learning, 2022. URL https://appl http:////....oeaaa..o.ooo..oor/p 252992904
Suyu Ge, Yunan Zhang, Liyuan Liu, Minjia Zhang, Jiawei Han, and Jianfeng Gao. Model tells you what to discard: Adaptive kv cache compression for Ilms, 2024a.
Tao Ge, Jing Hu, Lei Wang, Xun Wang, Si-Qing Chen, and Furu Wei. In-context autoencoder for context compression a large language model, 2024b.
Samuel Gehman, Suchin Gururangan, Maarten Sap, Yejin Choi, and Noah A. Smith. RealToxicity Evaluating neural toxic degeneration in language models. In Findings of the Associalion for Compulalional Linguistics: EMNLP 2020, pp. 3356 3369. Association for Computational Linguisties, 2020. doi: 10.18653/
v1/2020.fimdl aanding-cmmnlpppp 1m01..301. URL https://aclantthooog watpay.org/2000 org/2020. findings-emnlp mmmnpp.011 301
Gemini Team et al. Gemini: A family of highly capable multinodal models, 2023.
Saibo Geng, Martin Josifosky, Maxime Peyrard, and Robert West. Grammar-ccostrainee decoding for structured ulp lasks without finetuning, pp. 10932 10952, 2023.
V GOEL. Minimum bayes-risk automatic speech recognition. Pattern Recognition in Speech and Language Processing, 2003.
39

---

Published in Transactions on Machine Learning Research (11/2024)
V. Goel, S. Kumar, and W. Byrne. Segmental minimum bayes-risk decoding for automatic speech recognition.
IEFE Transactions on Speech and Audio Processing, 12(3):234-22 249, 2004. doi: 0tt.://TSAA200..222500
Jesús González- Rubio and Francisco Casacuberta. Improving the minimum Bayes' risk combination of machine translation systems. In Proceedings of the 10th International Workshop on Spoken Language Translation: Papers, 2013. URL httpps://aclanthooogy..rrr org/ 221gg/201.... iwslt=papers.4
Jesús Rubio, Alfons Juan, and Francisco Casacuberta. Minimum Bayes-risk system combination.
In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, pp. 1268 1277. Association for Computational Linguistics, 2011. URL https:
pooclantho.ogy.or//Pl0
Sachin Goyal, Ziwei Ji, Ankit Singh Rawat, Aditya Krishna Menon, Sanjiv Kumar, and Vaishnavh Nagarajan. Think before you speak: Training language models with pause tokens, 2024.
Alex Graves. Sequence transduction with recurrent neural networks, 2012.
Albert Gu and Tri Dao. Mamba: Lincar-time sequence modeling with selective state spaces. ArXiv preprint, abs/2312.00752, 2023. URL https://arxxv.org/ http/aawww....raaabaaa /rgg//////1/..a..///////// 00752
Shibo Hao, Yi Gu, Haodi Ma, Joshua Hong, Zhen Wang, Daisy Wang, and Zhiting Hu. Reasoning with language model planning with world model. In Houda Bouamor, Juan Pino, and Kalika Bali (eds.), Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pp. 8154- 8173, Singapore, December 2023. Association for Computational Linguisties. doi: 10.18653/v1/202. monlp-main.500 URL
Shibo Hao, Yi Gu, Haotian Luo, Tianyang Liu, Xiyan Shao, Xinyuan Wang, Shuhua Xie, Haodi Ma, Adithya Samavedhi, Qiyue Gao, et al. Lim reasoners: New evaluation, library, and analysis of step-by-step reason- ing with large language models. arXiv preprint or 244:2404. 05221, 2024.
Alex Havrilla, Sharath Chandra Raparthy, Christoforus Nalmpantis, Jane Dwivedi- Yu, Maksym Zhuravin- skyi, Eric Hambro, and Roberta Railneau. Glore: When, where, and how to improve Ilm reasoning via global and local refinements. ArXiv preprint, abs/2402.10963, 2024. URL https://aaxki org http://www..r/////2222//22/ abs2 10963
Georg Heigold, Wolfgang Macherey, Ralf Schluter, and Hermann Ney. Minimum exact word error training. In IEEE Workshop Automatic Speech Recognition and Understanding, 2005., pp. 186-190. IEEE, 2005.
John Hewilt, Christopher Manning, and Percy Liang. Truncation sampling as language model desmoothing, In Findings of the Association for Computational Linguistics: EMNLP 2022, pp. 3414-3427. Association for Computational Linguistics, 2022. URL
fere222finningg Sindings-emnil 249
Geoffrey Hinton, Oriol Vinyals, and Jeffrey Dean. Distilling the knowledge in a neural network. volume 2015. URL
02531
Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Flena Buchatskaya, Trevor Cai, Fliza Rutherford, Diego de las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, Tom Hennigan, Eric Noland, Katherine Millican, George van den Driessche, Bogdan Damoc, Aurelia Guy, Simon Osindero, Karen Simonyan, Erich Elsen, Oriol Vinyals, Jack William Rae, and Laurent Sifre. An empirical analysis of compute-optimal large language model training. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave. and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL https:
www.:/eeeooouuiidiiBBBBBeoac BBBRRUOAAR
Chris Hokamp and Qun Liu. Lexically constrained decoding for sequence generation using grid beam search.
In Proceedings of the 55th Annual Meeting of the Association for Computational Linguisties (Volume Long Papers). pp. 1535- 1546. Association for Computational Linguistics, 2017. doi: 10.18653/v1/
P17-1141. URI http:/sss//aclaanoollll.oo..g//p
40

---

Published in Transactions on Machine Learning Research (11/2024)
Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yefin Choi. The curious case of neural text degener- ation. In 8th International Conference on Learning Representations, TCLR 2020, Addis Ababa, Ethiopin, April 26-30, 2020. OpenReview.net, 2020. URL httppp//wweeeeeeeee.ee////////rr
Sara Hooker. The hardware lottery, 2020.
Coleman Hooper, Sehoon Kim, Hiva Mohammadzadeh, Michael W. Mahoney, Yakun Sophia Shao, Kurt Keutzer, and Amir Gholami. Kvquant: Towards 10 million context length 1lm inference with kv cache quantization, 2024.
Edward Hu, Moksh Jain, Eric Elmoznino, Younesse Kaddar, Guillaume Lajoie, Yoshua Bengio, and Niko- lay Malkin. Amortizing intractable inference in large language models. In The Twelfth International Conference on Learning Representations, 2024. URL http://ppeneeeieeeeeeeerrrrrrraa
Jie Huang, Xinyun Chen, Swaroop Mishra, Huaixiu Steven Zheng, Adams Wei Yu, Xinying Song, and Denny Zhou. Large language models cannot selfecorrect reasoning yet. In The Twelfth International Conference on Learning Representations, 2024. URL
Liang Huang and David Chiang. Forest rescoring; Faster decoding with integrated language models. In Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics, pp. 144-151. Association for Computational Linguistics, 2007. URL http:://acllattooooo.oo/////////
DeLesley Hutchins, Imanol Schlag, Yuhuai Wu, Ethan Dyer, and Behnam Neyshabur. Block-recurrent transformers. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Newral Information Processing Systems, 2022. URL https://openrewee nel/Fforummiccuuleeemm....o
Hanhwi Jang, Joonsung Kim, Jac-Fon Jo, Jaewon Lee, and Jangwoo Kim. Mnnfast: a fast and scalable system architecture for memery-angmented neural networks. In Proceedings of the 46th International Symposium on Compuler Architecbure, ISCA '19, pp. 250 263. Association for Computing Machinery, 2019, URL https:://oi.orgg/ 1145/3307656 3322214
ISBN 9781450366694. doi: 00.1145/3307650.388
Albert Qiaochu Jiang, Sean Welleck, Jin Peng Zhou, Timothee Lacroix, Jiacheng Liu, Wenda Li, Mateja Jamnik, Guillaume Lample, and Yuhuai Wu. Draft, sketch, and prove: Guiding formal theorem provers with informal proofs. In The Eleventh International Conference on Learning Representations, 2023. URL
https://openreviiet www..e//oorrmmdddSMMeeeooooonn
Yuu Jinnai and Kaito Ariu. Hyperparamcter-fice approach for faster minimum bayes risk decoding, 2024.
Andy L. Jones. Scaling scaling laws with board games, 2021.
Jordan Juravsky, Bradley Brown, Ryan Ehrlich, Daniel Y. Fu, Christopher Ré, and Azalia Mirhoseini. Hydragen: Higg-throughput Ilm inference with shared prefixes, 2024.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B. Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models, 2020.
Sayash Kapoor, Benedikt Stroebl, and Arvind Narayanan. Ai leaderboards no longer useful. it's time to switch to pareto curves. AI Snake Oil blog, 2024a. URL
ai hatpeerrrrrrdd-r-----ooooogrrsss
Sayash Kapoor, Benedikt Stroebl, Zachary S. Siegel, Nitya Nadgir, and Arvind Narayanan. Ai agent bench- marks that matter. Manuscript submitted for publication, 2024b.
Muhammad Khalifa, Hady Elsahar, and Mare Dymetman. distributional approach to controlled text generation. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. Open net, 2021. URL http::: httto://poeareeeeeeeeee//rom/tss
Omar Khattab, Keshav Santhanam, Xiang Lisa Li, David Hall, Percy Liang, Christopher Potts, and Matci Zaharia. Demonstrate-saarhhnndee Composing retrieval and language models for knowledge-intensiee NL... Xixvv preprint 221 14024, 2022.
41

---

Published in Transactions on Machine Learning Research (11/2024)
Omar Khattab, Arnav Singhvi, Paridhi Maheshwari, Zhiyuan Zhang, Keshav Santhanam, Sri Vardhamanan, Saiful Haq, Ashutosh Sharma, Thomas T. Joshi, Hanna Moazam, Heather Miller, Matei Zaharia, and Christopher Potts. Dspy: Compiling declarative language model calls into self-improving pipelines. 2024.
Mahsa Khoshnoodi, Vinija Jain, Mingye Gao, Malavika Srikanth, and Aman Chadha. A comprehensive survey of accelerated generation techniques in large language models, 2024. URL httpps://arxiv.org/
abs/2405. 13019
Geunwoo Kim, Pierre Baldi, and Stephen McAleer. Language models can solve computer tasks. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (ods.). Advances in Neural Information Processing Systems, volume 36, pp. 39648-3967 Cur- ran Associates, Inc., 2023. URL
Sehoon Kim, Coleman Hooper, Amir Gholami, Zhen Dong, Xiuyu Li, Sheng Shen, Michael W. Mahoney, and Kurt Keutzer. Squeezellm: Dense-and-sparse quantization, 2024a.
Taehyeon Kim, Joonkee Kim, Gihun Lee, and Se- Young Yun. Instructive decoding: Instruction-tunet large language models are self-refiner from noisy instructions. In The Twelfth International Conference on Learning Representations, 2024b. URL https://openreview nel/ForummidctLeezzZiHWw
Brian Kingsbury, Tara N. Sainath, and Hagen Soltau. Scalable minimum bayes risk training of deep neural network acoustic models using distributed hessian-free optimization. In Interspeech, 2012. URL https:
9762882
Philipp Koehn and Rebecca Knowles. Six challenges for neural machine translation. In Proceedings of the First Workshop on Newral Machine Translation, pp. 28 39. Association for Computational Linguistics, 2017. doi: 10.18653/v1
11//33//1/113222// W11-2204. URL htttps://aclanthooogy.. wtw.a/anntoooooooooo/1-//---- org//1332244
Tomasz Korbak, Hady Elsahar, Germán Kruszewski, and Mare Dymetman. Controlling conditional lan- guage models without catastrophic forgetting. In Kamalika Chaudhuri, Stefanie Jegelka, Te Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato (ods.), International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Muryland, USA, volume 162 of Proceedings of Machine Learning Re- search, pp. 11499 11528. PMLR, 2022a. URL https::/pproeeedingg mlr. haal.ppprrss/w1622/oooaa22a http:///pp.oocooa...orrr/esees/a
Tomasz Korbak, Hady ElSahar, Germán Kruszewski, and Mare Dymetman. On reinforcement learning and distribution matching for fine-tuning language models with no catastrophic forgetting. ArXiv preprint, abs/2206.00761, 2022b. URL htttp:://axxiv.orr/bbsss 0r960
Tomasz Korbak, Ethan Perez, and Christopher Buckley. RL with KL penalties is better viewed as Bayesian inference. In Pindings of the Associalion for Compulational Linguislics: EMNLP 2022, pp. 1083 1091. As- sociation for Computational Linguistics, 2022c. URL https::/ org/ 2022. 1e122.ffindii findings-ems emmlp.
77
Kalpesh Krishna, Yapei Chang, John Wieting, and Mohit lyyer. RankGen: Improving text generation with large ranking models. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pp. 199-232. Association for Computational Linguistics, 2022. URL httpp:://cclanthologg) org/2022. wwnnp-mmin......mmmmmmmmmmmmmmmm 15
Tia Kulikov, Alexander Miller, Kyunghyun Cho, and Jason Weston. Importance of search and evaluation strategies in neural dialogue modeling. In Proceedings of the 12th International Conference on Natural Language Generalion, pp. 76 87. Association for Computational Linguistics, 2019. doi: 10.18653/v1/ W19-8609, URL httpps://aclantholllee www.////wwoog//--/89999
Aviral Kumar, Vincent Zhuang, Rishabh Agarwal, Yi Su, John D Co-Reyes, Avi Singh, Kate Baumli, Shariq Iqbal, Colton Bishop, Rebecca. Roclofs, Lei M Zhang, Kay McKinney, Disha Shrivastava, Cosmin Paduraru, George Tucker, Doina Precup, Feryal Behbahani, and Aleksandra Faust. Training language models to self- correct via reinforcement learning, 2024. URL httpp::/aarv..org/bbb/////////// 12917
42

---

Published in Transactions on Machine Learning Research (11/2024)
Sachin Kumar, Biswajit Paria, and Yulia Tsvetkov. tradieen-baseee constrained sampling from language models. In Conference on Empirical Methods in Natural Language Processing, 2022. URL https:
semanticscholar.om wtt.:/cco.....oooo/oooooss/sa/a.
Shankar Kumar and William Byrne. Minimum Bayes-risk decoding for statistical machine translation. In Proceedings of the Human Language Technology Conference of the North American Chapter of the Asso- ciation for Computational Linguistics: HLT-NAACL 2004, pp. 169-176. Association for Computational Linguistics, 2004. URL https:://claanthoolgg -rw.e//-00////1110000
Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph E. Gon- zalez, Hao Zhang, and Ton Stoica. Efficient memory management for large language model serving with pagedattention, 2023.
Guillaume Lample, Timothee Lacroix, Marie anne Lachaux, Aurelien Rodriguez, Amaury Hayal, Thibaut Lavril, Gabriel Ebner, and Xavier Martinet. Hypertree proof search for neural theorem proving. In Alice H. Oh, Alckh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.). Advances in Neural Information Processing Systems, 2022. URL
Yann LeCun, Sumit Chopra, Raia Hadsell, Aurelio Ranzato, and Fu Jie Huang. tutorial on energy-based learning. 2006. URL https://api. http:/s//ppp...mmmmccccooooo wwwranntisccoola.oo/ooooorooooee
8531544
Lucas Lehnert, Sainbayar Sukhbaatar, Paul Mevay, Michael Rabbat, and Yuandong Tian. Beyond a Better planning with transformers via search dynamics bootstrapping, 2024.
Brian Lester, Rami Al-Rfou, and Noah Constant.
The power of scale for parametor-efficient prompt tuning. Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pp. 3045
3059. Association for Computational Linguistics, 2021. doi: 10.18653/<122021..mm main.243. URL
https://aa..antoolgg...org http:///o.oooy.oor///...e.em
2ttpg///ee.....mmmmmi... www.p-mmin.....m...memmmmmmm 243
Yaniv Leviathan, Matan Kalman, and Yossi Matias. Fast inference from transformers via speculative decod- ing. volume abs/2211.171B 2022. URL https://arxxw.orr/abb//11111
Yaniv Leviathan, Matan Kalman, and Yossi Matias. Fast. inference from transformers via speculative decod- ing, 2023.
Ailor Lewkowycz, Anders Johan Andreassen, David Dohan, Ethan Dyer, Henryk Michalewski, Vinay Venkatesh Ramasesh, Ambrose Slone, Cem Anil, Imanol Schlag, Theo Gutman-Solo, Yuhuai Wu, Behnam Neyshabur, Guy Gur-Ari, and Vedant Misra. Solving quantitative reasoning problems with lan- guage models. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL https:// wwtp://oooommiid-ITTEzEEeeee
Junyi Li, Tianyi Tang, Wayne Xin Zhao, and Ji-Rong Wen. Pretrained language model for text generation: A survey, In Zhi-Hua Zhou (ed.), Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21, pp. 4492-4499. International Joint Conferences on Artificial Intelligence Organi- zation, 8 2021. doi: 113966///caii22222 Track.
URL
2021/612 Survey
Kenneth Li, Samy Jelassi, Hugh Zhang, Sham M. Kakade, Martin Wattenberg, and David Brandfonbrener. Q-probe: A lightweight. approach to reward maximization for language models. 2024a. URL https:
http://cchoosaoooorrroooooo/oo/a wtgg/oorpusDD:227788333
Xiang Lisa Li and Percy Liang, Prefix-tuning: Oplimizing continuous prompts for generation. In Proceedings of the 59th Annuol Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pp. 4582-4597. Association for Computational Linguistics, 2021. doi: 10.18633/x1/2021.ee aac-ooo2..oooonnon33 3ong. URL https://aclaathoooggy
org/2021 acl- 1ong.3333
43

---

Published in Transactions on Machine Learning Research (11/2024)
Xiang Lisa Li, Ari Holtzman, Daniel Fried, Percy Liang, Jason Eisner, Tatsunori Hashimoto, Luke Zettle- moyer, and Mike Lewis. Contrastive decoding: Open-ended text generation as optimization. In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki (eds.), Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 12286-12312. Association for Computational Linguistics, 2023a. doi: 10.18653/ /1/55/11222232//lr/rg/ acl.oooo....oon........ 687
URL https://aclanthoooggy
Yifei Li, Zeqi Lin, Shizhuo Zhang, Qiang Fu, Bei Chen, Jian Jian-Guang Lou, and Weizhu Chen. Making language models better reasoners with step-aware verifier. In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki (eds.), Proceedings of the 61st Annual Meeling of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 5315 5333. Association for Computational Linguistics, 2023b.
doi: 10. 10.18653/v1. (1/665//1/2223... www.o.a..-ooog........ 291. URL ftttp:s/acclantholog..rrgg (1122223.ccc1110 gell-oong.29 291
Yuhong Li, Yingbing Huang, Bowen Yang, Bharat Venkitesh, Acyr Locatelli, Hanchen Ye, Tianle Cai, Patrick Lewis, and Deming Chen. Snapkv: Llm knows what you are looking for before generation, 2024b.
Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Lebiond, Tom Ec- cles, James Keeling, Felix Gimeno, Agustin Dal Lago, Thomas Hubert, Peter Choy, Cyprien de Mas- son d' d'Autume, Igor Babuschkin, Xinyun Chen, Po-Sen Huang, Johannes Welbl, Sven Gowal, Alexey Cherepanov, James Molloy, Daniel J. Mankowitz, Esme Sutherland Robson, Pushmect Kohli, Nando de Freitas, Koray Kavukcuoglu, and Oriol Vinyals. Competition-level code generation with alphacode. Science, 378 (66444 1097, 2022. doi: 11126///cinne.abbee URL https://www science. orge org/doi/ abq 158
abs/10. 11
Opher Lieber, Barak Lenz, Hofit. Bata, Gal Cohen, Jhonathan Osin, Itay Dalmedigos, Frez Safahi, Shaked Meirom, Yonatan Belinkov, Shai Shalev-Shwartz, Omri Abend, Raz Alon, Tomer Asida, Amir Bergman, Roman Glozman, Michael Gokhman, Avashalom Manevich, Nir Ratner, Noam Rozen, Erez Shwartz, Mor Zusman, and Yoav Shoham. Jamba: A hybrid transformer-mamba language model, 2024.
Hunter Lightman, Vineet Kosaraju, Yuri Burda, Harrison Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. Let's verify step by step. In The Twelfth International Conference on Learning Representations, 2024. URL https:://pperreview http://ppnreeieeeeeeeffrrrrrrmme mett/oorumiddev@@@@Nee...
Ji Lin, Jiaming Tang, Haotian Tang, Shang Yang, Wei-Ming Chen, Wei-Chen Wang, Guangxnan Xiao, Xingyu Dang, Chuang Gan, and Song Han. Awq: Activation-aware weight quantization for Ilm compression and acceleration. In MLSys, 2024a.
Yujum Lin, Haotian Tang, Shang Yang, Zhekai Zhang, Guangxuan Xiao, Chuang Gan, and Song Han. Qserve: W448ky4 quantization and system co-design for efficient 1lm serving, 2024b.
Alisa Liu, Maarten Sap, Ximing Lu, Swabha Swayamdipta, Chandra Bhagavatula, Noah A. Smith, and Yejin Choi. DExperts: Decoding- time controlled text generation with experts and anti-experts. In Proceedings of the 59th Annual Meeting of the Association. for Computational Linguistics and the 11th International Joint. Conference on Natural Language Processing (Volume 1: Long Papers), pp. 16016 Association for Computational Linguistics, 2021a. doi: (L18633/v12022/ acl- acn- URL https::/aclaantooloyy arg/2021.acl-1ong. 522
Alisa Liu, Xiaochuang Han, Yizhong Wang, Yulia Tsvetkov, Yejin Choi, and Noah A. Smith. Tuning language models by proxy, 2024a.
Jiachong Liu, Andrew Cohen, Ramakanth Pasunuru, Yejin Choi, Hannanch Hajishirzi, and Asli Celikyilmaz. Don't throw away your value model! generating more preferable text with value-guided monte-carlo tree search decoding. In First Conference on Language Modeling, 2024b. URL https:://penrevieewnttt forum22d-kk92t22.dm
Pengfei Liu, Weizhe Yuan, Jinlan Fu, Zhengbao Jiang, Hiroaki Hayashi, and Graham Neubig. Pro-train, prompt, and predict: A systematic survey of prompting methods in natural language processing, 2021b. URL
44

---

Published in Transactions on Machine Learning Research (11/2024)
Tianqi Liu, Yao Zhao, Rishabh Joshi, Misha Khalman, Mohammad Salch, Peter J Liu, and Jialu Liu. Statistical rejection sampling improves preference optimization. In The Twelfth International Conference on Learning Representations, 2024c. URL
Zichang Liu, Aditya Desai, Fangshuo Liao, Weitao Wang, Victor Xie, Zhaozhuo Xu, Anastasios Kyrillidis, and Anshumali Shrivastava. Scissorhands: Exploiting the persistence of importance hypothesis for Ilm kv cache compression at test time, 2023.
Sidi Lu, Yaoming Zhu, Weinan Zhang, Jun Wang, and Yong Yu. Neural text generation: Past, present and beyond, 2018. URL http::://axxvv.or//ea.// wtt.:o/gg//////..///////// 1801180330000 07133
Ximing Lu, Peter West, Rowan Zellers, Ronan Le Bras, Chandra Bhagavatula, and Yejin Choi NeuroLogic decoding: (un)supervieed neural text generation with prodicate logic constraints. In Kristina Toutanova, Anna Rumshisky, Luke Zettlemoyyr, Dilek Hakkani-Tur, Iz Beltagy, Steven Bethard, Ryan Cotterell, Tanmoy Chakraborty, and Yichao Zhou (eds.), Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 4288 4299, Online, June 2021. Association for Computational Linguistics. doi: 10.18653/v /2021 www...aaccc......mmm.... naacl-main.n. m39n.339. URL https:://aclanthho wwwpthhoolgo.rogg/2.... org/ naa.ll-aaalmmmmmaaam 339
Ximing Lu, Sean Welleck, Peter West, Liwei Jiang, Jungo Kasai, Daniel Khashabi, Ronan Le Bras, Lianhui Qin, Youngjae Yu, Rowan Zellers, Noah A. Smith, and Yejin Choi. NeuroLogic a essuue decoding: Con- strained text generation with lookahead heuristics. In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies, pp. 780 799. Association for Computational Linguistics, 2022. doi: https://aclannhologg.coo maa.2m2in..m
URL
Ximing Lu, Fazze Brahman, Peter West, Jachun Jung, Khyathi Chandu, Abhilasha Ravichander, Prithvi- raj Ammanabrolu, Liwei Jiang, Sahana Ramnath, Nouha Dziri, Jillian Fisher, Bill Lin, Skyler Hallinan, Lianhui Qin, Xiang Ren, Sean Welleck, and Yejin Choi. Inference-tine time policy adapters (IPA): Tailor- ing extreme-scale LMs without fine-tuning. In Houda Bouamor, Juan Pino, and Kalika Bali (eds.), Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pp. 6863- 6883. Association for Compulational Linguisties, 2023. doi: 10.18653/v1 w2.18653w1/2023.oom htt////w12222.mmmml/ ww003..emlp-mmmin..2. URL https://aclantholoyy.rrgg org/2023. mwrg//22.eemmppmmain. emnlp-main. 424
Scott Lundberg. The art of prompt design: Prompt boundaries and token healing. Medium, may 2023.
Scott Lundberg, Marco Ribeiro, et al. Guidance, 2024. URL, http::://ggihub...cc///udddeeeee
David John Cameron MacKay. Information theory, inference, and learning algorithms. JEEE Transactions on Information Theory, 50:2544 2545, 2004. URL http://ppssssmtttttccccccrrorr/p
Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Layu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, Shashank Gupta, Bodhisattwa Prasad Majumder, Katherine Hermann, Sean Welleck, Amir Yazdanbakhsh, and Peter Clark. Self-refine: Iterative refinement with self- feedback. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URT. https: //openreview net foeeffoooomnddss/eerre
Shahbuland Matiana, JR Smith, Ryan Techan, Louis Castricato, Stella Biderman, Leo Gao, and Spencer Frazier. Cut the carp: Fishing for zero-shot story evaluation, 2021.
Clara Meister, Ryan Cotterell, and Tim Vieira. If beam search is the answer, what was the question? In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 2173 2185. Association for Computational Linguistics, 2020. doi: 10.18653/v1/200 11.853//1/2000.emmlpp- eeee00emmlllmmma. mmain.170.. URL https://aclanntholggy.orrr wrgp///yy..ggg/0ooo/e 20122220.emeeppm..me momlp-main. 170
Clara Meister, Tiago Pimentel, Luca Malagutti, Ethan Wilcox, and Ryan Cotterell. On the efficacy of sampling adapters. In Anna Rogers, Jordan Boyd-Graben and Naoaki Okazaki (eds.). Proceedings of the 61st Annual Meeting of the Association for Compulational Lánguistics (Volume 1: Long Papers), pp-
45

---

Published in Transactions on Machine Learning Research (11/2024)
1437-1453. Association for Computational Linguistics, 2023a. doi: 10.18653/w1/22233cllbbm URL https://ae..nmhooogyyoor//// wwwp:/23....//....oooo a.l.acc-11. acl-long. 80
Clara Meister, Tiago Pimentel, Gian Wiher, and Ryan Cotterell. Locally typical sampling. Transactions
of the Association for Computational Linguistics, 11:102-121, 2023b. doi: 10.1162/tacl 00536. URL
https://aclanthologgy www.:/loggg.ogg/223333/ wrg./223. tacl-1.7
William Merrill and Ashish Sabharwal. The expressive power of transformers with chain of thought. In The Twelfth International Conference on Learning Represenlations, 2024. URL https::/openreeieww
net/forrumiddNxjjGPPHee)))
Xupeng Miao, Gabriele Oliaro, Zhihao Zhang, Xinhao Cheng, Hongyi Jin, Tianqi Chen, and Zhihao Jia. Towards efficient generative large language model serving: A survey from algorithms to systems, 2023a.
URL https///arxivv.org/bb///1/// 15234
Xupeng Miao, Gabriele Oliaro, Zhihao Zhang, Xinhao Cheng, Zeyu Wang, Rae Ying Yee Wong, Zhuoming Chen, Daiyaan Arfeen, Reyna Abhyankar, and Zhihao Jia. Specinfer: Accelerating generative Ilm serving with speculative inference and token tree verification. ArXiv preprint, abs/2305.09781, 2023b. URL 09781
fttps:://axxi..or//bbssss
Tomas Mikolov, M. Karafíát, L. Burget, J. Cernocký, and S. Khudanpur. Recurrent neural network based language model. pp. 1045-1048, 2010.
Maxim Milakov and Natalia Gimelshein. Online normalizer caleulation for soflmax, 2018.
Jesse Mu, Xiang Lisa Li, and Noah Goodman. Learning to compress prompts with gist tokens. In Thirty- seventh Conference on Neural Information Processing Systems, 2023. URT. /ttps:///penreevew. net/ Forumpid=20CxPCL3T55
Kenton Murray and David Chiang. Correcting length bias in neural machine translation. In Proceedings of the Third Conference Machine Translation: Research Papers, pp. 212 223. Association for Computational Linguistics, 2018. doi: 10.18653/ 1118653/11/W18-6660
URL https::/aclantholl.og org he/g//11-6222
Piotr Nawrot, Adrian Lańcucki, Marcin Chochowski, David Tarjan, and Edoardo M. Ponti. Dynamic memory compression: Retrofitting lims for accelerated inference, 2024.
Nathan Ng, Kyra Yee, Alexei Baevski, Myle Ott, Michael Auli, and Sergey Edunov. Facebook FAIR's WMT19 news translation task submission. In Proceedings of the Fourth Conference on Machine Trans- lation (Volume 2: Shared Task Papers, Day 1), pp. 314-319. Association for Computational Linguistics, 2019. doi: 10.18653/vl/ 11//3///1/W195333.3 URL http:://aclatthoooegy.r/////
Ansong Ni, Srini Iyer, Dragomir Radev, Ves Stoyanov, Wen-tau Yih, Sida Wang, and Xi Victoria Lin. Lever: Learning to verify language-to-code generation with execution. In Proceedings of the 40th International Conference on Machine Learning (ICML '23), 2023.
NVIDIA. Nvidia Tesla V100 GPU architecture, 2017.
NVIDIA. Nvidia A100 tensor core GPU architecture, 2020.
NVIDIA. Nvidia H100 tensor core GPU architecture, 2022.
Franz Josef Och and Hermann Ney. Discriminative training and maximum entropy models for statistical machine translation. In Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics, pp. 295-302 Association for Computational Linguistics, 2002. doi: 10.31 11711///07300011731133 URL http::///aaaanttooooo..gg////--
Theo X. Olausson, Joevana Priya Inala, Chenglong Wang, Jianfeng Gao, and Armando Solar-Lozama. Is self-repair a silver bullet for code generation? In The Twelfth International Conference on Learning Representations, 2024. URL
46

---

Published in Transactions on Machine Learning Research (11/2024)
Long Ouyang, Jeff Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishkinn Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke E. Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul Francis Christiano, Jan Leike, and Ryan J. Lowe. Training language models to follow instructions with human feedback. ArXiv preprint, abs/2203.02155, 2022. URL
02155
Jiayi Pan, Yichi Zhang, Nicholas Tomlin, Yifei Zhou, Sergey Levine, and Alane Suhr. Autonomous evaluation and refinement of digital agents, 2024.
Liangming Pan, Michael Stephen Saxon, Wenda Xu, Deepak Nathani, Xinyi Wang, and William Yang Wang. Automatically correcting large language models: Surveying the landscape of diverse self-correction 03188
strategies. ArXiv preprint, abs/2308.03188, 2023. URL https://arxiv/ http:///aaaxivv.ggabbbss////
Adain Pauls and Dan Klein. K-best A parsing. In Proceedings of the Joind Conference of the 47th Annuaal Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the APNLP, pp. 958 966. Association for Computational Linguistics, 2009, URL https::/aacaaantoooor....
P09- 1108
Bo Peng, Eric Alcaide, Quentin Anthony, Alon Albalak, Samuel Arcadinho, Stella Biderman, Huanqi Cao, Xin Cheng, Michael Chung, Leon Derczynski, Xingjian Du, Matteo Grella, Kranthi Gv, Xuzheng He, Haowen Hou, Przemyslaw Kazienko, Jan Kocon, Jiaming Kong, Bartlomiej Koptyra, Hayden Lau, Ji- aju Lin, Krishna Sri Ipsit Mantri, Ferdinand Mom, Atsushi Saito, Guangyu Song, Xiangru Tang, Jo- han Wind, Stanislaw Woéniak, Zhenyuan Zhang, Qinghua Zhou, Jian Zhu, and Rui-Jie Zhu. RWKV: Reinventing RNNs for the transformer era. In Houda Bouamor, Juan Pino, and Kalika Bali (eds.), Findings of the Association for Computational Linguistics: EMNLP 2023, pp. 14048-14077 Associ- ation for Computational Linguistics, 2023. doi: 1118653/v1202255 fnniini //acllanthooogyorrg/////
URL https:
findings-emnlp...
Gabriel Poesia, Oleksandr Polozov, Vu Le, A. Tiwari, Gustavo Soares, Christopher Meek, and Sumit Gulwani. Synchromesh: Reliable code generation from pre-trained language models. ArXiv, abs/22011 122221111222 11227, 2022.
Stanislas Polu and llya Sutskever. Generative language modeling for automated theorem proving, 2020.
Stanislas Polu, Jesse Michael Han, Kunhao Zheng, Mantas Baksys, Igor Babuschkin, and llya Sutskever.
Formal mathematics statement curriculum learning. In The Eleventh International Conference on Learning Representations, 2023. URL
8dmSh4
David M. W. Powers. Applications and explanations of Zipf's law. In New Methods in Language Processing and Computational Natural Language Learning, 1998. URL https::/aaclanthooogy.oorr wrg/
Ofir Press, Muru Zhang, Sewon Min, Ludwig Schmidt, Noah Smith, and Mike Lewis. Measuring and narrowing the compositionality gap in language models. In Houda Bouamor, Juan Pino, and Kalika Bali (eds.), Findings of the Association for Computational Linguistics: EMNLP 2023, pp. 5687-5711. Association for Computational Linguistics, 2023. doi: 10.18653/v1 http///1/222..fnnii// //aclanthology.org/// findings-emnlp.33 378
20t.://///112222.mnmnnnmnnmn ann....nninggeecnl........ URL https:
Team PyTorch. Accelcrating generative ai with pytorch ii: Gpt, fast. https://pytorch.oorgbbboo acceleeratinn--ggerativv------ 2023.
Markus N. Rabe and Charles Staats. Self-atenntion does not need o(n²) memory, 2022.
Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D Manning, Stefano Ermon, and Chelsea. Finn. Direct preference optimization: Your language model is secretly a reward model. Tn Thirty-seventh Conference on Newral Information Processing Systems, 2023. URL https:://operreview wttp://enrriiiiieee//rrrrrrrrm net/forum?id=
HPUSIXJaa9
David Raposo, Sam Ritter, Blake Richards, Timothy Lillicrpp, Peter Conway Humphreys, and Adam San- toro. Mixture-of-depths: Dynamically allocating compute in transformer-based language models, 2024.
47

---

Published in Transactions on Machine Learning Research (11/2024)
Alexander Rush. MiniChain, 2023. URL http:s//gghhbbb..cmo//sss////aaf
Jon Saad-Falcon, Adrian Gamarra Lafuente, Shlok Natarajan, Nahum Maru, Hristo Todorov, Etash Guha, Kelly Buchanan, Mayee Chen, Neel Guha, Christopher Ré, and Azalia Mirhoseini. Archon: An archi- tecture search framework for inference-time techniques, 2024. URL http:::/aaxt...r//////////////// 15254,
Swarnadeep Saha, Omer Levy, Asli Celikyilmaz, Mohit Bansal, Jason Weston, and Xian Li. Branch-solve- merge improves large language model evaluation and generation. ArXiv preprint, abs abs/2310.15123, 2023. URL httts:://axxiv.rr//bbbst.
Pranab Sahoo, Ayush Kumar Singh, Sriparna Saha, Vinija Jain, Samrat Mondal, and Aman Chadha. A systematic survey of prompt engineering in large language models: Techniques and applications, 2024. URL https://arxiv..o wwtp://///abb///....//////
Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf. Distilbert, a distilled version of bert: smaller, faster, cheaper and lighter, 2020.
William Saunders, Catherine Yeh, Jeff Wu, Steven Bills, Long Ouyang, Jonathan Ward, and Jan Leike. Self-critiquing models for assisting human evaluators, 2022.
Imanol Schlag, Sainbayar Sukhbaatar, Asli Celikyilmaz, Wen tau Yih, Jason Weston, Jürgen Schmidhuber, and Xian Li. Large language model programs, 2023.
Torsten Scholak, Nathan Schucher, and Dzmitry Bahdanau. Picard: Parsing incrementally for constrained auto-regressive decoding from language models. ArXiv, abs/2109.05093, 2021.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy opti- mization algorithms. ArXie, abs/1707.063477, 2017. URL https://api. www.nticschoooooooeooooo ottpaaatiiccicoooo.oooooooo/ss/s
28695052
Noam Shazeer. Fast transformer decoding: One write-head is all you need, 2019.
Ying Sheng, Lianmin Zheng, Binhang Yuan, Zhuohan Li, Max Ryabinin, Daniel Y. Fu, Zhiqiang Xie, Beidi Chen, Clark Barrett, Joseph E. Gonzalez, Percy Liang, Christopher Ré, Ion Stoica, and Ce Zhang. Flexgen: High-throughput generative inference of large language models with a single gpu, 2023.
Chufan Shi, Haoran Yang, Deng Cai, Zhisong Zhang, Yifan Wang, Yujiu Yang, and Wai Lam. A thorough examination of decoding methods in the era of LLMs. In Yaser Al-Onaizan, Mohit Bansal, and Yun-Nung Chen (eds.), Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, pp. 8601-8629, Miami, Florida, USA, November 2024a. Association for Computational Linguistics. URL https:://acLanthologyy wttgg/224.emnmmmmmaaaaa emnlp-main. 489
Freda Shi, Daniel Fried, Marjan Ghazvininejad, Luke Zettlemoyer, and Sida I. Wang. Natural language to code translation with execution. In Proceedings of the 2022 Conference on Empirical Methods in Natural Longuage Processing, pp. 3533 35-4.. Association for Computational Linguistios, 2022. URL
https:://alLanthllogy hrtp:yorg///2// watp.//...222..mmmmaaa..... 231
Quan Shi, Michael Tang, Karthik Narasimhan, and Shunyu Yao. Can language models solve olympiad programming?, 2024b.
Noah Shinn, Federico Cassano, Edward Berman, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. Reflexion: Language agents with verbal reinforcement learning, 2023.
David Silver, Aja Huang, Christopher J. Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittwieser, loannis Antonoglou, Veda Panneershelvam, Mare Lanetot, Sander Dieleman, Do- minik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Gracpel, and Demis Hassabis. Mastering the game of go with deep neural networks and tree search. Nature, 520,484-503, 2016. URL http::/t://t www.:na.auue.eeeteaaeea wtt.urr...o//atuuee/////a//////a Full/nature169p html
48

---

Published in Transactions on Machine Learning Research (11/2024)
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas baker, Matthew Lai, Adrian Bolton, Yutian Chen, Timothy P. Lillicrap, Fan Hui, L. Sifre, George van den Driessche, Thore Graepel, and Demis Hassabis. Mastering the game of go without human knowledge. Nature, 550:354-359, 2017. URL https://app ceemanniiccccoola.rggg//rrrplllp
Charlic Snell, Jachoon Lee, Kelvin Xu, and Aviral Kumar. Scaling 1lm test-time compute optimally can be more effective than scaling model parameters, 2024. URL
03314.
Yixin Song, Zeyu Mi, Haotong Xie, and Haibo Chen. Powerinfer: Fast large language model serving with a consumer-grade gpu, 2023.
Felix Stahlberg and Bill Byrne. On NMT search errors and model errors: Cat got your tongue? In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing sociation for Computational Linguistics, 2019. doi: (111853//1/DD1-111 1331. URL https:/
pp. 3356 15566--36..-2 As-
org/D19-1331
Felix Stahlberg, Ilia Kulikov, and Shankar Kumar. Uncertainty determines the adequacy of the mode and the tractability of decoding in requenco-to-seqqennce models. In Proceedings of the 60th Annual Meeting of the Associalion for Computational Linguisties (Volume 1: Long Papers), pp. 8634 8645. Association for Computational Linguistics, 2022. doi: 10. (t065///1//222.aa-loonn.../ URL
2022. a022.acl-long. 591.
Nisan Sticnnon, Long Ouyang, Jeff Wu, Daniel M. Zicgler, Ryan Lowe, Chelsea Voss, Alce Radford, Dario Amodei, and Paul Christiano. Learning to summarize from human feedback. In Proceedings of the 34th International Conference on Newral Information Processing Systems, NIPS'20. Curran Associates Tnc., 2020. ISBN 9781713829546.
Zhiqing Sun, Longhui Yu, Yikang Shen, Weiyang Liu, Yiming Yang, Sean Welleck, and Chuang Gan. Easy- to-hard generalization: Scalable alignment beyond human supervision, 2024a.
Ziteng Sun, Ananda Theertha Suresh, Jae Hun Ro, Ahmad Beirami, Himanshu Jain, and Felix Yu. Spectr: Fast speculative decoding via optimal transport, 2024b.
Tya Sutskever, Oriol Vinyals, and Quoe V. Le. Sequence to sequence learning with neural networks. Tn Zoubin Ghahramani, Max Welling, Corinna Cortes, Neil D. Lawrence, and Kilian Q. Weinberger (eds.), Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Pro- cessing Systems 2014, December 8- 13 2014, Montreal, Quebec, Canada, pp. 3104-3112, 2014. URL https: html
//proceedings.neurffe neur
4c55444244222888841113332444 wttp:/cccpppppppeeeeeeeeeeeeee 201 ///11//hh///// ccppsi/pppeerrrrpsscppppppppp/ee
Mirac Suzgun, Luke Melas-Kyriazi, and Dan Jurafsky. Follow the wisdom of the crowd: Effective text generation via minimum Bayes risk decoding. In Anna Rogers, Jordan Boyd-Graber, and Naoaki
Okazaki (eds.), Findings of the Association for Computational Linguistics: ACL 2023, pp. 4265-4293.
Association for Computational Linguistics, 2023. doi: 10. 10.18653/v1 /22/2...n2i2n.--.../.. //aclanthology.co orwp:y/..r/2.2../ htt.:toooooooorrrr//..3a.nnnnnnn findings--cl222555
URL. https:
Vijay Thakkar, Pradeep Ramani, Cris Cecka, Aniket Shivam, Honghao Lu, Ethan Yan, Jack Kosaian, Mark Hoemmen, Haicheng Wu, Andrew Kerr, Matt Nicoly, Duane Merrill, Dustyn Blasig, Fengqi Qiao, Piotr Majcher, Paul Springer, Markus Hohnerbach, Jin Wang, and Manish Gupta. Cutlass, 2023. URL
https://gi wttpah/....//////////aaaaaaaa//.
Ye Tian, Baolin Peng, Linfeng Song, Lifeng Jin, Dian Yu, Haitao Mi, and Dong Yu. Toward self-improvemmen of Imm via imagination, searching, and criticizing, 2024.
Philippe Tillet, H. T. Kung, and David Cox. Triton: an intermediate language and compiler for tiled neural network computations. In Proceedings of the 3rd ACM SIGPLAN International Workshop on Machine Learning and Programming Languages, MAPL 2019, pp. 10-19. Association for Computing Machinery, 2019. ISBN 9781450367196. doi: 00.1145/3315508.32 3329973
URL https: /ttpp:///oi..o org/10. 11413311111338588. http:///oooogg//...1
49

---

Published in Transactions on Machine Learning Research (11/2024)
Hugo Touvron, Louis Martin, Kevin R. Stone, Peter Albert, Amjad Almahairi, Yasmine Babaci, Nikolay Bashlykov, Soumya. Batra, Prajiwal Bhargava, Shruti Bhosale, Daniel M. Bikel, Lukas Blecher, Cris- tian Cantón Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller, Cynthia Gao, Vedanuj Goswami, Naman Goyal, Anthony S. Hartshorn, Saghar Hosseini, Rui Hou, Hakan Inan, Marcin Kardas, Viklor Kerkez, Madian Khabsa, Isabel M. Kloumann, A. V. Ko- renev, Punit Singh Koura, Maric-Anne Lachaux, Thibaut Lavril, Jenya Leo, Diana Liskovich, Yinghai Lu, Yuning Mao, Xavier Martinet, Todor Mihaylov, Pushkar Mishra, Igor Molybog, Yixin Nie, Andrew Poul- ton, Jeremy Reizenstein, Rashi Rungta, Kalyan Saladi, Alan Schelten, Ruan Silva, Eric Michael Smith, R. Subramanian, Xia. Tan, Binh Tang, Ross Taylor, Adina Williams, Jian Xiang Kuan, Puxin Xu, Zhengxu Yan, lliaan Zarov, Yuchen Zhang, Angela Fan, Melanie Kambadur, Sharan Narang, Aurelien Rodriguez, Robert Stojnic, Sergey Edumov, and Thomas Scialom. Llama 2: Open foundation and fine-tuned chat models. ArXiv preprint, abs/2307 23070009099 2023. URL https: http://akiv..oggbbbb/aa/e//// wttp:or///bb//////// 200./////70009888.8
Gladys Tyen, Hassan Mansoor, Victor Cärbunc, Peter Chen, and Tony Mak. Lims cannot find reasoning errors, but can correct them given the error location, 2024.
Jonathan Uesato, Nate Kushman, Ramana Kumar, Francis Song, Noah Siegel, Lisa Wang, Antonia Creswell, Geoffrey Irving, and Trina Higgins. Solving math word problems with process- and outcome-based feedback, 2022.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (eds.), Advances én Neural Information Processing Systems 30: Anneual Conference Newral Information Processing Systems 2017, neurips..
December 4-9, 2017, Long Beach, CA, USA, pp. 5998 6008, 2017. URL
Giorgos Vernikos and Andrei Copescu-Belis. Don't 't rank, combine! combining machine translation hypotheses using quality estimation, 2024.
Peiyi Wang, Lei Li, Zhihong Shao, R. X. Xu, Damai Dai, Yifei Li, Deli Chen, Y.Wu, and Zhifang Sui. Math-shepherd: Verify and reinforce 1lms step-by-step without human annotations. ArXic preprint, abs/231 abs/2312.008935, 2023a. URL https://arrtv..rg/aa//////
Wenxiao Wang, Wei Chen, Yicong Luo, Yongliu Long, Zhengkai Lin, Liye Zhang, Binbin Lin, Deng Cai, and Xiaofei He. Model compression and efficient inference for large language models: A survey, 2024a. URL
https://arriv.org//b///////
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc V Le, Ed H. Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. In The Eleventh International Conference on Learning Representations, 2023b. URL httpps://ooeneeviee..ee//oooott 1PL1NIMMrW
Zhiruo Wang, Zhoujun Cheng, Hao Zhu, Daniel Fried, and Graham Neubig. What are tools anyway? survey from the language model perspective, 2024b.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, brian ichter, Fei Xia, Ed H. Chi, Quoc V Le, and Denny Zhou. Chain of thought prompting elicils reasoning in large language models. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL https:://penreete http:://pppeeeeeeeeeeeeefrrrrrma hwt.fforummiddd_vooMeMseeaa VjQLMeSB__]
Sean Welleck, Ili Kulikov, Jaedeok Kim, Richard Yuanzhe Pang, and Kyunghyun Cho. Consistency of a recurrent language model with respect to incomplete decoding. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 5553 3563-556..45 Association for Computa- tional Linguistics, 2020. doi: 10. 10.18653/vl /22/222e0mmmp.... main.448. 448. URL http:://adlanttoooy..or///22 emnlp- mawn. 448
50

---

Published in Transactions on Machine Learning Research (11/2024)
Sean Welleck, Jiacheng Liu, Ximing Lu, Hannanch Hajishirzi, and Yejin Choi. Naturalprover: Grounded mathematical proof generation with language models. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave. and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL https:
Sean Welleck, Ximing Lu, Peter West, Faeze Brahman, Tianxiao Shen, Daniel Khashabi, and Yejin Choi. Generating sequences by learning to self-correct. In The Eleventh International Conference on Learning Representations, 2023. URL httpp:://openreiiieee htt.pp/ewweeeeeeeeeeeoeoootoiann
Jason Weston and Sainbayar Sukhbaatar. System 2 attention (is something you might need too), 2023.
Gian Wiher, Clara Meister, and Ryan Cotterell. On decoding strategies for neural text generators, 2022.
URL https://arxiv... wrwp.//.2.//bbb222....om 15721
Brandon T. Willard and Rémi Louf. Efficient guided generation for large language models. abs/2307.09702, 09702, 2023.
ArXiv,
Yangzhen Wu, Zhiqing Sun, Shanda Li, Sean Welleck, and Yiming Yang. An empirical analysis of compute- optimal inference for problem-solving with language models, 2024. URL https://arxiw.org/bb//// 00724
Guangxuan Xiao, Ji Lin, Mickael Seznec, Hao Wu, Julien Demouth, and Song Han. Smoothquant: Accurate and efficient post-training quantization for large language models, 2024a.
Guangxuan Xiao, Yuandong Tian, Beidi Chen, Song Han, and Mike Lewis. Efficient streaming language models with attention sinks, 2024b.
Yisheng Xiao, Lijun Wu, Junliang Guo, Juntao Li, Min Zhang, Tao Qin, and Tie yan Liu. A survey on non-autoregrrssivee generation for neural machine translation and beyond, 2023. URL htttss//aaxixt org/abs/2284.09265
Yuxi Xie, Kenji Kawaguchi, Yiran Zhao, Xu Zhao, Min Kan, Junxian Hc, and Qizhe Xic. Self-evaluation guided beam search for reasoning. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL https:://penrreview.c net hett/
Zhenliang Xue, Yixin Song, Zeyu Mi, Le Chen, Yubin Xia, and Haibo Chen. Powerinfer-22 2: Fast large language model inference on a smartphone, 2024.
Kaiyu Yang, Aidan Swope, Alex Gu, Rahul Chalamala, Peiyang Song, Shixing Yu, Saad Godil, Ryan Prenger, and Anima Anandkumar. LeanDojo: Thcorem proving with anggentel language models. In Newral Information Processing Systems (NeurIPS), 2023a.
Kevin Yang and Dan Klein. FUDGE:
Controlled text generation with future discriminators. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 3511 3535. Association for Computational Linguisties, 2021. doi: 10.1 10.18653/v1 22222 maacl-main.276, URL http::://aaclanthoooooooo///////
naacl-main. 276
Nan Yang, Tao Ge, Liang Wang, Binxing Jiao, Daxin Jiang, Linjun Yang, Rangan Majumder, and Furu Wei. Inference with reference: Lossless acceleration of large language models. ArXiv preprint, Abs/2234.044877 2023b. URL https://arxiv www.:oogg/bb/....... http:::/arxxi.oor//////200.0000 04487
Songlin Yang, Bailin Wang, Yikang Shen, Rameswar Panda, and Yoon Kim. Gated linear atlention trans- formers with hardware-efficient training, 2024.
Zhilin Yang, Zihang Dai, Ruslan Salakhutdinov, and William W. Cohen. Breaking the softmax bottleneck: A high-rank RNN language model. In 6th International Conference on Learning Representations, ICLR 2018, Vancoweer BC, Canada, April 30- May 3, 2018, Conference Track Proceedings. OpenReview.nect 2018. URL http://rereeeeeeeefoooooodddaa-a
51

---

Published in Transactions on Machine Learning Research (11/2024)
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, and Karthik R. Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. In Thirly-seventh Conference on Neural Information Processing Systems, 2023. URL https://openrevieww hwwp://wwwweeeeeeeeeeeeeeeeeeeee net net/forum?id=
5Xclecx01h
Gycong-In Yu, Joo Scong Joong, Geon- Woo Kim, Soojeong Kim, and Byung-Gon Chun. Orca: A distributed serving system for Transformer-Based generative models. In 16th USENIX Symposium on Operaling Systems Design and Implementation (OSDI 22), pp. 521 538. USENIX Association, 2022. ISBN 978-1- 939133-28-1. URL htll/httss:/// httts::/wwww...
Mert Yuksekgonul, Federico Bianchi, Joseph Boen, Sheng Liu, Zhi Huang, Carlos Guestrin, and James Zou. Toxtgrad: Automatic 'differentiation via text. 2024.
Sina ZarrieB, Henrik Voigt, and Simeon Schüz. Decoding methods in neural language generation: A survey. Information, 12(9), 2021. ISSN 2078-2489. doi: 10.3390 10090//nn1120000 10901209 URL https://www.nd/ com/
2078 2178-489//129/355
Eric Zelikman, Georges Harik, Yijia Shao, Varuna Jayasiri, Nick Haber, and Noah D. Goodman. Quict-star: Language models can teach themselves to think before speaking, 2024a.
Eric Zelikman, Eliana Lorch, Lester Mackey, and Adam Tauman Kalai. Self-taught optimizer (stop): Re- cursively self-improving code generation, 2024b.
Hugh Zhang, Daniel Duckworth, Daphne Ippolito, and Arvind Neelakantan. Trading off diversity and quality in natural language generation. In Proceedings of the Workshop Human Evaluation of NLP Systems (HumEval), pp. 25-33. Association for Computational Linguisties, 2021. URL httpps://aclantholossy org/2021. humeval-11..
Michael Zhang, Kush S. Bhatia, Hermann Kumbong, and Christopher R'e. The hedgehog & the porcupine:
Expressive lincar attentions with softmax mimicry. ArXiv preprint, abs/2402.043477, 2024. URL https:
//arxiv.org wwt./rg//bb////////////// 2432/4447
Zhenyu Zhang, Ying Sheng, Tianyi Zhou, Tianlong Chen, Lianmin Zheng, Ruisi Cai, Zhao Song, Yuandong Tian, Christopher Ré, Clark Barrett, Zhangyang Wang, and Beidi Chen. H2o: Heavy-hitter oracle for efficient generative inference of large language models, 2023.
Stephen Zhao, Rob Brekelmans, Alireza Makhzani, and Roger Grosse. Probabilistic inference in language models via twisted sequential monte carlo, 2024a.
Stephen Zhao, Rob Brekelmans, Alireza Makhzani, and Roger Grosse. Probabilistic inference in language models via twisted sequential monte carlo, 2024b. URL
wttpaa/www...rr///////....... 17546
Yilong Zhao, Chien- Yu Lin, Kan Zhu, Zihao Ye, Lequn Chen, Size Zheng, Luis Ceze, Arvind Krishnamurthy, Tianqi Chen, and Baris Kasikci. Atom: Low-bit quantization for efficient and accurate Ilm serving, 2024c.
Lianmin Zheng, Liangsheng Yin, Zhiqiang Xie, Jeff Huang, Chuyue Sun, Cody Hao Yu, Shiyi Cao, Christos Kozyrakis, Ion Stoica, Joseph E. Gonzalez, Clark Barrott, and Ying Sheng. Efficiently programming large language models using sglang, 2023.
Yinmin Zhong, Shengyu Liu, Junda Chen, Jianbo Hu, Yibo Zhu, Xuanzhe Liu, Xin Jin, and Hao Zhang, Distserve: Disaggregating prefill and decoding for goodput-optimized large language model serving, 2024.
Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Claire Cui, Olivier Bousquet, Quoe V Le, and Fd H. Chi. Teast-to-most prompting enables complex reasoning in large language models. In The Eleventh International Conference on Learning Representations, 2023a. URL https://openreviiew wttp://wwweee/oooonnn///////////
Shuyan Zhou, Frank F Xu, Hao Zhu, Xuhui Zhou, Robert Lo, Abishek Sridhar, Xianyi Cheng, Yonatan Bisk, Daniel Fried, Uri Alon, et al. Webarena: A realistic web enviromment for building autonomous agents. Ar preprint, Abs/2307. /2307,13844, 13854, 2023b. URL https://arxiv.org/absstt 13854
52

---

Published in Transactions on Machine Learning Research (11/2024)
Daniel M. Ziegler, Nisan Stiennon, Jeffrey Wu, Tom B. Brown, Alec Radford, Dario Amodei, Paul Christiano, and Geolfrey Irving. Fine-tuning language models from human preferences, 2020.
G. Zipf. The peycho-biology of language: An introduction to dynamic philology. 1999.
Zirui Liu, Jiayi Yuan, Hongye Jin, Shaochen Zhong, Zhaozhuo Xu, Vladimir Braverman, Beidi Chen, and Xia Hu. Kivi : Plug-and-play 2bit. kv cache quantization with streaming asymmetric quantization. 2023. doi: 1013110/K6.222225577..7722 URL https:://gdoiinntt//// 31 40/RG. 2. 2. 28167 37282
53


Reviews:
[{"review_id": "lqHVmehIiF", "reviewer": "Reviewer_zXpT", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- To the best of my knowledge, the paper is exhaustive in its coverage of previous inference-time methods. When it comes to a fine-grained category, the previous works selected and discussed in detail are the most impactful ones from a line of qualified works.\n- The terms are well-defined and the use of mathematical expressions is accurate.\n- The paper is rich in its presentation of key properties related to certain methods.\n\nConcerns:\n- The three areas—generation algorithms, meta-generation, and efficient generation—are presented in parallel, but efficient generation seems to be loosely connected to the first two at first sight: while generation algorithms and meta-generation methods alter the generation process to yield desirable outputs, efficient generation is about reducing cost and improving generation speed. In section 7, the authors touch on how certain efficient techniques could improve aforementioned inference-time methods which evinces its interconnections with the first two topics. I would suggest authors modify the narrative of the abstract and introduction so that efficient generation is not a stand-alone area parallel to the other two, but more like a separate subject that can be applied to the first two areas.\n\n- The paper lacks analysis of different inference-time methods’ performance, especially a quantitative one.\n  - It is understandable for a survey paper to be as general as possible to apply to as many cases and scenarios, but it does not hurt to pick a single downstream application/task to offer insights into the uniqueness of each method. For example, authors could elaborate on how certain algorithms behave in NMT tasks.\n  - Readers may wonder “When I have excessive/limited compute for model inference, what technique should I employ/forgo to get the best out of the budget?” This could be an entry point for enriching quantitative analysis in the paper.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper presents a holistic discussion of inference-time algorithms, ranging from token-level generation to meta-generation methods. The purposes and pitfalls of various decoding methods are covered in the first part of the paper. Then, treating LMs as black boxes, the authors shift focus to meta-generation, summarizing ways to improve generation quality by utilizing auxiliary components and external information. Efficient generation schemes that employ parallelism, compression, caching, etc. are presented as means to speed up the generation process. The paper eventually concludes with five key takeaways as to why, in certain cases, sampling from an original output distribution could be insufficient and inference-time algorithms are needed.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Fig. 2, consider changing candidate tokens to more probable next tokens to simulate real-life cases.\n- Page 24, footnote, mixed usage of notation $T$ for matrix transpose and the time dimension.\n\nRecommended\n- Section 4.2.3, consider supplying the analytical KL expression for BoN $log(n)-\\frac{n-1}{n}$ from \nStiennon et al., \"Learning to summarize from human feedback\", In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS’20\n- Section 4.3, consider citing \nLiu et al., \"Don't throw away your value model! Generating more preferable text with Value-Guided Monte-Carlo Tree Search decoding\", arXiv, 2023", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "EJIjtMVH6o", "reviewer": "Reviewer_cvxc", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n\n1. The paper offers a thorough survey of existing generation algorithms, categorizing and explaining their functionalities, motivations, and impact on language model performance.\n2. The paper introduces a framework for understanding and categorizing meta-generation algorithms. This helps provide some structures to compare the current \"prompt-engineering\" research.\n3. The paper provides explicit, practical insights into token cost analysis and reviews tools and libraries that facilitate these improvements.\n\n### Weaknesses\n\n1. The paper does not discuss the existing surveys nor motivate the need for a new survey or the proposed unified formalism with existing literature.\n2. The formalism helps clarify the paper but makes it hard to read and follow. The paper is rather long and introduces many notations that readers might have to come back to look up often.\n3. Section 8 often discusses \"generation\" methods in general, leaving some ambiguity between token-level generations and meta-generations. Thus, the suggested future research directions are somewhat unclear.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper provides a comprehensive survey of Generating high-quality samples efficiently from a large language model (LLM). It categorizes the research directions into three main topics: token-level generation methods, meta-generation methods, and efficient generation methods. The overall goal of the paper is to provide a unified framework for the research directions, summarize overall trends, and suggest future directions. \n\nThe paper first comprehensively discusses a survey of token-level generation algorithms under a unified formalism. Then, it introduces the concept of meta-generation algorithms, including all algorithms that use \"sub-generators,\" and further categorizes them into chained, parallel, step-level, and refinement-based meta-generators. For efficiency and speed considerations, the papers provide an analysis of theoretical token costs for generators and meta-generators and then discuss various techniques to minimize the costs and speed up the generation, including both hardware and software aspects.  \n\nFinally, the paper discusses its takeaways and future directions related to the surveyed methods. It suggests that research should improve the [token-level] generation method to simplify the way we tackle degeneracies. The paper, however, suggests that sophisticated generation algorithms will continue to be necessary for aligning the model’s distribution with specific user objectives and leveraging external information. In addition, the research should continue to work on dynamic computation or other speed-up methods of LLMs to reduce cost and time as the model scales will continue to rise.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. The paper is helpful and unique, but it might need additional justification. The authors should discuss existing surveys to motivate this survey paper and the proposed unified formalism.  Some existing surveys include:\n\n    - https://www.ijcai.org/proceedings/2021/612\n    - https://arxiv.org/abs/1803.07133\n    - https://arxiv.org/abs/2303.18223 \n\n2. Provide a reference of notations. This could be in an appendix of the paper. It would also help to provide a section summary to aid.\n3. Mentioning specific categories (e.g., sub-sections) in Section 8 will help clarify and strengthen the takeaways.", "broader_impact_concerns": "No ethical concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "8ArRt2rUiG", "reviewer": "Reviewer_YVip", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- This survey provides a list of most up-to-date references on a very relevant topic of language models. The references and the accompanying materials could serve as self-study materials for researchers interested in developments in this field.\n\n- The three categories of generation procedures provide a good coverage of ongoing developments in this field, which would be of interest to NLP, ML systems, and LLMs.\n\n- The paper provides very detailed discussions of the key techniques.\n\n    - For generation algorithms, this paper starts by presenting decoding and sampling schemes. The reader is reminded of these commonly used techniques, such as greedy decoding, ancestral sampling.\n\n    - For meta-generation algorithm, the paper talks about best-of-N ranking methods, beam search.\n\n    - For efficient generation, the paper provides a discussion about various reasoning related applications, architectural modifications, optimizing computational graphs, systems level improvement, etc.\n\nWeaknesses:\n\n- I think it would be useful to discuss other existing surveys in this space (broadly defined). Examples include, but may not be limited to, foundation models, data selection, transfer learning for NLP. I feel like placing this survey inside a range of other existing surveys will better serve the purpose of readers, helping them nagivate these online materials for understanding the research space.\n\n- I think it would also be helpful to discuss some limitations of this survey, including things like what topics are not covered by the survey. Again, this will help better serve the purpose, clearly specifying the scope of the paper.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents a survey of inference time algorithms for using large language models. These inference time algorithms make use of information already existing in the LLM, and apply this information to make inference for a target distribution.\n\nThis survey presents a survey from three aspects, including:\n- generation algorithms: these are the most standard generation procedures of a trained language model, such as the generation of the next token.\n\n- meta-generation algorithms: these are procedures that make use of another generation algorithm during its execution. Examples include models that can output Python code or execute Python code.\n\n- efficient generation: these algorithms discuss the computational cost of the generation procedure, focusing on the inference time.\n\nFor each aspect, this paper presents a very detailed discussion, starting from the mathematical definition of the algorithms; then, a list of detailed references and implementations of that definition.\n\nFinally, this paper also presents a thoughtful discussion of the takeaways from this survey. These discussions help highlight avenues that could be promising for future work.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- At various section titles, the paper has an extra dot. Examples include sections 4.3, 6.2, 6.3, 7.3.1, 7.3.2, 7.4. Possibly this is due to formatting changes. So please double check to make sure.\n\n- There are duplicate references in the reference list. See, e.g., the bottom of page 37. In addition, some references contain the editors of the conferences cited, whereas others do not. Please cross check to ensure consistency.\n\n- I feel like there are a lot of terminologies in the survey (possibly due to an extensive number of topics covered). This sometimes had the opposite effect on the reader, as they have to grapple with all the terms. For example, in Table 1, there are over 10 sampling methods. Some of them are clear to the reader but many of many may not be. It would be helpful to add some pointers to the terminology, so at least the reader knows where to look for the definition/citation of the method if they want.\n\n    - What does \"extrinsic\" mean in Table 1?\n\n- The term \"Adapter\" and \"Adaptor\" are both used in various places. Please cross check to ensure consistency.\n\n- For the mathematical definitions of each algorithm, I'm having difficulty with catching up on the notations---For instance, in Definition 4, what is $\\phi$, and why does it come into the left hand side?\n\n    - In Equation (8), what does the hat above $y$ refer to? and why does the previous Equation (7) not use this hat?\n\n    - In Equation (10), does the approximation $\\approx$ actually hold, or is it just a metaphor of the greedy decoding?\n\n- In Definition 2, I don't understand the meaning of this Equation (5). Please elaborate. Similarly, please elaborate on Equation (6).", "broader_impact_concerns": "I do not have any concerns with regard to Broader Impacts. I think this survey paper should be able to generate further discussions and interest regarding generation algorithms in language models.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Overall there were only minor concerns with this paper, stemming from notation in a few places and lack of comparison to existing surveys. The authors made updates accordingly and all reviewers recommended acceptance.
Decision: Accept (poster)