EEL : Efficiently Encoding Lattices for Reranking (2023)

Abstract: Standard decoding approaches for conditional text generation tasks typically search for an output hypothesis with high model probability, but this may not yield the best hypothesis according to human judgments of quality. Reranking to optimize for “downstream” metrics can more closely optimize for quality, but many metrics of interest are computed with pre-trained language models, which are slow to apply to large numbers of hypotheses. We explore an approach for reranking hypotheses by using Transformers to efficiently encode lattices of generated outputs, a method we call EEL. With a single Transformer pass over the entire lattice, we can approximately compute a contextualized representation of each token as if it were only part of a single hypothesis in isolation. We combine this approach with a new class of token-factored rerankers (TFRs) that allow for efficient extraction of high reranker-scoring hypotheses from the lattice. Empirically, our approach incurs minimal degradation error compared to the exponentially slower approach of encoding each hypothesis individually. When applying EEL with TFRs across three text generation tasks, our results show both substantial speedup compared to naive reranking and often better performance on downstream metrics than comparable approaches.

## introduction part of the progress in natural language generation over the past few years has been driven by a proliferation of decoding techniques, from beam search to sampling approaches like nucleus sampling @xcite , typical decoding @xcite , and contrastive decoding @xcite . these techniques, however, only optimize for probabilistic objectives, rather than alignment with human judgments, which is typically better encapsulated by downstream metrics il fait beau reranking (prior work) the weather is nice transformer reranker the weather is beautiful transformer reranker it is nice transformer reranker explicitly score candidates, choose highest score s4 s3 s2 the weather it is nice beautiful eel transformer (causal w/mask) compute reranker score for each node token-factored reranking of lattices (this work) the weather is nice beautiful it it is beautiful generation model efficiently extract highest scoring path transformer reranker s1 0.9 0.3 0.8 0.9 0.2 0.8 ## setting our approach centers on reranking output from conditional text generation with neural models @xcite . such models place distributions over target output @xmath0, . . . , y n ) given input sequence x via a text generation model θ: p(y | x; θ) = ∏ n @xmath1, x; θ). in trying to optimize this model probability p(y | x; θ) by finding the most likely x, decoding algorithms often produce candidate sets h of highly likely outputs under the model for our reranking stage (e.g. for beam search, the candidate set is the n completions for all beams). our goal is to rerank candidate sets to optimize for a downstream objective t (x, y ˆ). we assume our reranker s ∶ (x, y ˆ) → r scores an (input, hypothesis) pair and returns a real-valued approximation of t using a transformer model. reranking can be divided into two steps: (1) the generation of a candidate set @xmath2, y ˆ(2) , . . . , y ˆ(m) }, and in our setting, h is represented by a lattice which encodes the candidates (further detail in section 4). this can either be a packed representation of beam search candidates or can be a more complex lattice generated natively by alternate decoding approaches. specifically, we use the approach of @xcite , which expands paths with a modified depth first search and merges similar paths in a recombination step to focus search budget on new paths, allowing for generation of larger sets of hypotheses with greater diversity. notably, these lattices are not tree-structured and contain reentrancies. compared to complete candidate sets of normal text sequences, lattices can exponentially reduce the number of tokens needed to encode large candidate sets, enabling strong speedups if leveraged correctly. thus, step (2) is the focus of this paper: given a scoring model s and a lattice encoding h, can we encode a lattice and still select the highest scoring candidate encoded in h? our solution will specialize s to be a token-factored reranker, which we define below, and h to be en-coded in a lattice; we show that these assumptions hold for strong rerankers that can be applied to real-world generation problems, even when encoding thousands of candidates in as little as a single transformer pass. we attempt to minimize the error in our selected candidate versus the oracle best candidate y best (defined above), which we refer to as degradation. ## efficient encoding of lattices (eel) in this section, we discuss the computation of f c : how can we efficiently compute transformer encodings for a lattice? across decoding methods, as the total number of lattice nodes is often exponentially fewer than the total number of tokens in h, being able to rerank all the candidates by only encoding each lattice token once can lead to a huge reduction of computation. thus, our goal with eel is to compute embeddings for all nodes in a set of hypotheses h represented by a directed graph (lattice) @xmath3, e) encoding all candidates in h. v is the set of all expanded nodes v @xmath4, and e the set of directed edges e i,j which represents v @xmath5. figure 2 shows the overall steps of our solution, which we now describe in detail. ## intrinsic evaluation: finding hypotheses with high reranker scores we first evaluate how closely the tfr scores of eel selections come to matching the quality of the oracle top-1 hypotheses y best with respect to tfr model s(x, y ˆ). we compute an upper bound for this by calculating tfr scores on exploded lattice candidate sets: enumerating the exponentiallylarge set of complete paths and scoring each individually. our exhaustive numbers are the average top-1 tfr score (not the downstream metric score) across the entire exploded set. as baselines, we rerank on a randomly sampled sets of 1 (rand), 8 (tfr-8-samp), and 32 (tfr-32-samp) from exploded sets. for eel approaches, we test a single mask (eel 1-mask) and few-mask (eel 8-mask) approach. we report these results across decoding methods in ## downstream evaluation that said, we find diverse sampling works to produce several diverse samples. our approach is able to rapidly obtain a highly diverse set of candidates before the noun-tfr score of samples eventually converges with the random baseline. beam-12, across all 12 candidates, has an average diversity of 66.35 4-grams, and .848 oracle noun-tfr. at 3 samples, we have good diversity and good quality, while the first 5 diverse samples all outperform the b-12 noun-tfr and diversity baselines. it's worth noting that the diversity weight is a hyperparameter, and can be adjusted to allow for a slower trade-off. ablations ## related work reranking and efficiency there is substantial past work on reranking, including significant recent work using transformers for it @xcite . some models can be expressed as tfrs @xcite ; however, others like @xcite use approaches like pooling of representations of the hypothesis before additional preprocessing. we do not have an approximation for such techniques; we show that tfrs can be successfully trained in this setting, but other approximations beyond tfrs would be a useful contribution of future research. older machine translation work takes advantage of the structure of n-gram language models to do "reranking" on the fly, either in hierarchical models @xcite or phrase-based decoding @xcite . however, recent work on both evaluation @xcite and reranking @xcite show how effective transformers are, suggesting that approximating these is more promising than devising rerankers with inherently more restrictive factorizations. background: lattice encoding work in the speech recognition community @xcite encodes lattices of speech recognition model decoding outputs with lstms to decode better candidates in second pass. other work examines the ability to encode lattices with selfattentional models @xcite , for the purpose of augmented text generation @xcite , albeit using models trained on datasets of lattices. as these approaches often require lattice-specific training, and often don't account for degradation, due to alternate, coarser task formulations, they are much more constrained, and not suitable for our setting. controlled generation while we focus on reranking for better generation "quality", our work relates to tasks where one may want to re-rank with respect to some control attribute. prior work examines the ability to adjust output logits specific to controls (yang and klein, 2021), mcts @xcite as well as control classifier guided decoding @xcite . ## conclusion across a variety of settings, downstream objectives, and decoding methods, we consistently find eel to provide high quality selections with low degradation and substantial speedup compared to exhaustive top-1 reranking output. we further demonstrate the capability of our approach to select multiple diverse outputs while still optimizing for tfr scores. by proposing a method that can efficiently encode lattices of large candidate sets, through the combination of eel and tfr models, we thus demonstrate the capability of reranking to be more effective and efficient than what was previously possible with naïve approaches.