Superposed Decoding: Multiple Generations from a Single Autoregressive Inference Pass
Authors: Ethan Shen
Alan Fan
Sarah M Pratt
Jae Sung Park
Matthew Wallingford
Sham M. Kakade
Ari Holtzman
Ranjay Krishna
Ali Farhadi
Aditya Kusupati
Venue: NeurIPS 2024 poster (2024)
Keywords: Efficient Decoding
Superposition
Autoregressive Modelling
Primary area: generative_models
TL;DR: A new decoding technique to generate multiple drafts at the cost of a single autoregressive inference leveraging superposed token embeddings and n-gram filters.

Abstract: Many applications today provide users with multiple auto-complete drafts as they type, including GitHub's code completion, Gmail's smart compose, and Apple's messaging auto-suggestions. Under the hood, language models support this by running an autoregressive inference pass to provide a draft. Consequently, providing $k$ drafts to the user requires running an expensive language model $k$ times. To alleviate the computation cost of running $k$ inference passes, we propose Superposed Decoding, a new decoding algorithm that generates $k$ drafts at the computation cost of one autoregressive inference pass. We achieve this by feeding a superposition of the most recent token embeddings from the $k$ drafts as input to the next decoding step of the language model. At every inference step we combine the $k$ drafts with the top-$k$ tokens to get $k^2$ new drafts and cache the $k$ most likely options, using an n-gram interpolation with minimal compute overhead to filter out incoherent generations. Our experiments show that $k$ drafts from Superposed Decoding are at least as coherent and factual as Nucleus Sampling and Greedy Decoding respectively, while being at least $2.44\times$ faster for $k\ge3$. In a compute-normalized setting, user evaluations demonstrably favor text generated by Superposed Decoding over Nucleus Sampling. Superposed Decoding can also be combined with other decoding strategies, resulting in universal coverage gains when scaling inference time compute. Code and more examples open-sourced at https://github.com/RAIVNLab/SuperposedDecoding.

Superposed Decoding: Multiple Generations from a Single Autoregressive Inference Pass
Ethan Shen
Alan Fan Sarah Pratt Jae Sung Park Matthew Wallingford
Sham Kakade
Ari Holtzman
Ranjay Krishna Ali Farhadi Aditya Kusupati
University of Washington
"Harvard University UUniversity of Chicago
{ethans03, kusupati)@cs. washington.edu
Abstract
Many applications today provide users with multiple auto-complete drafts they type, including GitHub's code completion, Gmail's smart compose, and Apple's messaging auto-suggestions. Under the hood, language models support this by running an autoregressive inference pass to provide draft. Consequently, providing & drafts to the user requires running an expensive language model k times. To alleviate the computation cost of running & inference passes, we propose Superposed Decoding, new decoding algorithm that generates &t drafts the computation cost of one autoregressive inference pass. We achieve this by feeding a superposition of the most recent token embeddings from the l drafts as input to the next decoding step of the language model. At every inference step we combine the k drafts with the top-k tokens to get 1.2 new drafts and cache the k most likely options, using an n-gram interpolation with minimal compute overhead to filter out incoherent generations. Our experiments show that A drafts from Superposed Decoding Greedy Decoding respectively, while being at least 2.44x faster for 2 3. In a compute-normalized setting, user evaluations demonstrably favor text generated by Superposed Decoding over Nucleus Sampling. Superposed Decoding can also be combined with other decoding strategies, resulting in universal coverage gains when scaling inference time compute. Code and more examples open-sourced at https:// thub. http://aWWlaabtueeppedeeeeeeeee
least coherent and factual as Nucleus Sampling and
Introduction
Commercial surveys find that 80% of e-commerce websites provide autocomplete feature [21]. With the proliferation of large language models, autocomplete drafts are now ubiquitous in an even wider range of applications. Examples include short draft suggestions in Gmail Smart Compose [8] and code snippets in GitHub Copilot [7]. These options provide users with the ability to consider different phrasings and increase the likelihood of having at least one suggestion that reflects their intent. While language models (LMs) [34] now power these multiple suggestions, each additional suggestion necessitates another inference pass (batch size = 1), making it computationally expensive.
Language models use autoregressive inference to generate plausible sequence of next tokens for given prefix [40]. The next token generated depends on the prefix and the previously generated tokens. Decoding algorithms like Greedy Decoding, - Sampling [12], Beam Search, and Nucleus Sampling [18] present various ways of obtaining generations during autoregressive inference. For prefix, Greedy (maximum likelihood) Decoding picks the most probable token at every autoregressive timestep, eventually generating only one auto-completion suggestion. Instead of making a greedy
"A currently Google DeepMind
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

just arrived in Xalapa, Mexico today my first"
day of class. At Universidad Veracruz...
Nucleus Sampling
3x
day of the Rosenkranz School at the...
day of orientation, and could not wait to...
day of work. I'm here to help...
Superposed Decoding
1x
day of work. I'm here to work...
33x faster!
day of classes. I'm here to help...
Figure 1: To generate multiple k auto-complete suggestions for a prefix using an LM, the existing decoding methods like Nucleus Sampling need inference passes. In contrast, Superposed Decoding can generate k suggestions at the cost of a single inference pass while being as coherent and factual.
choice at every timestep, we can also sample from the top-k most probable tokens to generate the sequence [12]. Also leveraging the top-k most probable tokens Beam Search, which picks the most probable & beams from the 122 possible drafts at every timestep. Alternatively, Nucleus Sampling [18], particularly effective at generating natural- -aturii--ounding text, grows generations by sampling from the collection of the smallest subset of tokens that form a preset probability mass (p) at every timestep. Top-k Sampling, Beam Search, and Nucleus Sampling offer the benefit of generating multiple suggestions. However, this comes at the cost of requiring multiple autoregressive inference passes.
We introduce Superposed Decoding (SPD) (Figure 1), a decoding algorithm that can generate mutiple (k) high-quality short generations using only a single autoregressive inference pass. At each autoregressive timestep during inference, Superposed Decoding feeds in the superposition (weighted combination) of the embeddings corresponding to the & most recent drafted tokens (Section 3.1). After selecting the top-k output tokens, SPD expands the existing i drafts with them, resulting in k22 potential new drafts. Each draft has probability score assigned to it, which is further smoothed using a combination of various r--grm models (n E [2, 6) [38, 25J. N-gram interpolation for smoothing helps improve coherency by selecting the most probable and coherent continuations (top-k drafts) for the next autoregressive step (Section 3.2). The n-gram interpolation computationally inexpensive and allows flexibility to change domains of interest during inference (cg.. programming, healthcare, finance, etc.). Superposed Decoding's 's effectivencss can be attributed to the apparent linearity of representations in language models [35, 23] which we concurrently discovered (Section 3.3).
Our experiments demonstrate that Superposed Decoding on Llama-2-7B [41] can generate k 2 1 drafts that are as coherent, in terms of perplexity, as Nucleus Sampling (Section 4.1). However, SPD achieves this with single inference pass, making it at least 2.44x faster than any other standard decoding methods for k 2 3 (Section 4.3). The ability to generate multiple drafts at the cost of one also increases the coverage significantly for fact-based evaluation tasks like TriviaQA and Natural questions- where SPD increases the chance of generating the correct answer by at least 5% when using 3 drafts (Section 4.2). Through an extensive human evaluation for a wide range of prefixes, we show that SPD generations outperforming by up to 20% in a compute normalized setting (3v1 and 3v2) (Section 4.4). Finally, we find that combining Superposed Decoding and other decoding strategies (e.g. Nucleus Sampling) results in substantial accuracy improvements when scaling inference compute (Section 4.5).
preferred as Nucleus Sampling in direct comparison (1v1) while
Superposed Decoding can help improve user experience by offering significant computational effi- ciency while maintaining accuracy for various writing tasks that often benefit from multiple short draft suggestions. Additionally, Superposed Decoding is extremely generalizable, works across different language models like Mistral 7B, and is capable of generating long-form content reliably, all while being nearly diverse in suggestion as Nucleus Sampling (Section 5).

---

2
Related Work
Decoding algorithms determine how tokens are selected from language model's next token distribu- tion. This is typically done greedily with Beam Search or Greedy Decoding, or stochastically with Nucleus Sampling [18] or Top-k Sampling [12]. Greedy Decoding operates by selecting the token with the highest probability at each timestep. However, locally optimal decisions can be globally suboptimal. On the other extreme, an exhaustive exploration of all token combinations is intractable with time complexity @(IV)), where V is the vocabulary size and 7 the total number of timesteps. practical compromise Beam Search, which continually caches the top-B most likely generations, where B is the number of beams or drafts. Thus, Beam Search is guaranteed to find more likely generations than Greedy Decoding while avoiding drawbacks.
Alternatively, Nucleus Sampling and Top-k Sampling decode probabilistically. To avoid degeneration, Top-k Sampling truncates the probability mass the most probable tokens, whereas Nucleus Sampling truncates the probability mass to the smallest possible set of words whose cumulative probability exceeds probability p. Because of Nucleus Sampling's propensity to produce unique and unrepetitive outputs, it has become the standard [4, 22, 42]. though Greedy Decoding is still favored for tasks such as short question answering [41].
Generating multiple drafts linearly scales the number inference passes in these decoding methods. Multi-token prediction [14, 36] addresses this by pre-training LM having n independent softmax heads that predict future tokens in parallel. When using multi-token prediction with speculative decoding, exact inference is 3x faster. In similar vein, Medusa [5] reduces the number of decoding steps by adding extra decoding heads, using a tree-based attention mechanism to generate candidates while simultaneously verifying them in each decoding step. Through this, Medusa achieves 2.2x reduction in inference latency while maintaining generation quality. However, multi-token tolti-ttoennn prediction requires re-training and Medusa requires additional mee-tuning for the extra decoding heads.
Superposed Decoding (SPD), on the other hand, can be easily integrated out of the box without any additional training on any language model. Further, Superposed Decoding is complementary other decoding methods like Medusa and multi-token prediction, as well as efficiency techniques like speculative decoding [30, 26, 6]. quantization [I0, 32, 19], pruning [13, 39, 28], and architectural optimizations [37, 2, 1, 43, 27, 11].
3 Superposed Decoding (SPD)
Given a text input as a prefix, Superposed Decoding uses an autoregressive LM fe to produce viable completion drafts in one inference pass.
First Timestep. Let x denote generated token in the vocabulary V and M (#11.. ......... Tm) represent an initial prefix of m tokens. Our goal is to generate k unique drafts starting from the prefix. The next token distribution at the first timestep m + is: pe p= [1...... Lm) = pe (
For the first timestep, each of the drafts is initialized as the prefix so we use the same next token distribution for all drafts. We grow draft d, by greedily selecting the 7th most probable token, making:
di = (M, +1+1)
where of is the token at timestep & for the 7th draft. We also track each draft's probability as its score, which is initially the probability of its first token po (1 Consequently, the set of drafts D after the first timestep is:
(M, (M,
po (
D
with probabilities P
(I)
(M, (M
po
Next Timesteps. As the input to the LM at timestep I, we construct ãt-1, which is a superposition (weighted linear combination) of the embeddings for the most recent token 2; of the & drafts. This means that im+1, the input to the LM at the second timestep m + 2, is the superposition of the tokens xm+1 for i = 1...., ..... k. We use this superposed embedding a single and accurate approximation
3

---

like
Superposdd
want
LM
Exponential mean
have
Drat: M-Gram
Drali Interpolated
Draft 1 "I likee"
Draft N-Gram
Draft Interpotated
Draft
like to"
Select overall top-k drafts
Draft 2 "I want"
Draft like
Draft 3 "I have"
N-Gram
Draft "I want
3
ed
Draft 3 Interpoloted
ITT Th 3n
Figure Superposed Decoding relies on feeding a superposed token embedding based on the most recent tokens from the current & drafts as the input during the auto-regressive inference step. This generates k² new drafts using the existing drafts and the top-k output tokens at the new timestep. Finally, keep the top-k drafts after filtering with an n-gram interpolation to improve coherency.
for the most recent token across all drafts at the (L - (1) timestep. We run autoregressive inference over Ze once for all & drafts instead of the usual once per draft, allowing us to formulate inference as:
Pa [M, ,.,
Because each draft contains its own contextual clues and syntax, cannot blindly use the distri- bution of for each draft. Instead, we interpolate the superposed distribution [x, 1m with draft-specific next token distribution from an n-gram model to get a final distribution Py (x²] J.r] M, 1m+1::-1) that is unique to each draft. Next, we rank the draft options by the joint probability their respective previous draft p; and their selected token. We choose the top options as drafts for the next timestep and update their probabilities. This gives:
(M, (M,
po(xn+alMM II s Pf Pf(x x! 1:s-1
D
with probabilities P
(M, x m
10 IT Pf (2 M, am
(2)
We continue generation until the maximum generation length or stop token is reached. In the following sections, we break down the process in detail. We also present pseudocode in Appendix A.
3.1 Token Superposition
During training, language models learn representation (token embedding) Rd for every token x E V. We leverage this representation at timestep to construct St, weighing the representation for _ by coefficient 74
2 where
74
=1
The performance of T is highly dependent on choosing the appropriate weight for each embedding 7, the normalized probability of draft such that
z{-1- We find that the best strategy
Pi
7
1
where is the probability of the hh draft, introduced in Section 3. This allows us to directly tie the weight of token the likelihood that it will be preserved in future timesteps, reducing drift between the superposed embeddings and the drafts they represent.
3.2 N-Gram Interpolation
We construct each draft's n-gram distribution Pogram (zt M, off smoothing the next token distributions over set of n-gram models using weights X, where n E [2, 6).
mm+i a{_1) by interpolatively

---

6
Pmgram (a/lM, x-
Σ An Pr Pro ( x m++ (7-1)
(5)
n=2
We base our interpolation weights on weights RedPajama found by Liu al. [31]. with additional tuning (specifics in Appendix B). However, domain-specific n-gram models can easily be swapped in for specific tasks such as code generation
[20]. We use exponential mean of po and Poyram as our final distribution ps. where is a hyperparameter controlling the impact of the n-gram distribution: Py ps(rg] M, Fm - = po [x) M, X 7m+ 1)--a Pangrmm (x; M, x +11--11)
This means that when generating, we only consider tokens appearing in both the Superposed Decoding and n-gram distributions. If there is no overlap between the distributions, then we instead calculate
Py 2 1a-1) = 5 po (2 M, #m+1:-1))
(7)
without interpolation, where 5 is penalty term that disincentivizes selecting uninterpolated draft for the next timestep. This approach the backbone Superposed Decoding (Equation 2) and allows to create context-aware next-token distributions for each draft with only one inference pass.
3.3 Superposed Decoding Semantically Approximates Beam Search
Superposed Decoding relies the ability of the underlying model to preserve the linear relationship between Σn and its component vectors zi-1 [23]. More formally, if ã; is the input to the LM fo. then fo(G.) Σ 7 fo(=Ş_1) should also true (7/ defaults to draft probability SPD). As long as this holds, the combination of superposed embedding and n-gram smoothing should allow to generate completions that resemble those from methods such as Beam Search.
We test this linearity by computing the cosine similarity between a set of superposed embeddings {i} and the linear combination of their component embeddings across 20 timesteps on Llama-2-7B. At each timestep, we first use Beam Search to generate tokens for three beams. We then manually input the superposed embedding the three tokens into a model using Superposed Decoding. Finally, we measure the alignment between (āt) and Σ 7 fo(2)-1) using cosine similarity cos(a, b) as:
cos(fo(Ft), Σ 7 fo(=)-1)
We compute the cosine similarities for ten randomly sampled batches of ten prefixes each from the OpenWebTens training split and plot the mean cosine similarities across batches, as well as the standard deviation (Figure 3). We find that Llama-2-7B is sufficiently linear up to 10 timesteps across all layers. However, this linearity imperfect, and Superposed Decoding and Beam Search eventually diverge over time. Owing this, we identify 10 timesteps the optimal generation length. We also show how linearity changes through the layers within each timestep Appendix H.
Experiments
We evaluate Superposed Decoding by analyzing generation quality, factuality, and latency. We demonstrate that Superposed Decoding improves over Nucleus Sampling and Greedy Decoding
1.0
Mean Cosine Similarity
0.8
0.6
0.4
0.0
0
3
5
6
9
12
Timestep
Figure 3: Llama-2-7B maintains the linear relationship between superposed embeddings and the component token embeddings, with mean cosine similarity 2 0.6 for the first 10 timesteps.
5

---

OpenWebText Text
century ago, Titanic's
Wayne said: calculations, but like theoretical
Hello Jump-Junkies! Apologies
Nucleus
was sealed when struck an iceberg on
calculations, is best try it out in
the long silence, but we've been busy the long wait. I've been busy with the long silence. I've been busy with the long silence, I've been busy with
was sealed when struck an losberg and was sealed when hit an iceberg and sealed when hit lcaberg
calculations, they are only as good as the data models, they are only as good data calculations, only good the assumptions
Superposed
Figure 4: Qualitative text generations in a compute-normalized setting for Superposed Decoding and Nucleus Sampling with prefixes sampled from OpenWebText. See Appendix G.1 for more.
in generation perplexity (Section 4. 4.1), fact-based benchmarks (Section 4.2), and wall-clock time (Section 4.3). We also conduct a user study highlighting that users prefer Superposed Decoding over Nucleus Sampling in a compute-normal normalized setting (Section 4.4). Finally, we show that Superposed Decoding improves performance while scaling inference compute (Section 4.5). We include example generations of Superposed Decoding in Figure 4, with more Appendix G.I.
We implement Superposed Decoding on the base version of Llama-2-7B [42] for the majority of our experiments, running on one A40 GPU. We do not change model weights. For perplexity evaluations, we use Llama-2-770 on eight A40 GPUs. We assume a batch size of one for all experiments.
For n-gram interpolation, construct n- n-gram models using 200,000 documents (roughly 200 million tokens) randomly sampled from the RedPajama dataset, an open-source replication of Llama-2's training dataset [9]. We represent each n-gram model internally as a frequency table, storing each unique n-gram and its corresponding count. This enables faster lookup and is the basis behind the compute reduction that we offer. Our n-gram models require approximately 14 GB of disk storage overall, split 57 MB, 433 MB, 2.15 GB, 4.7 GB, and 6.8 GB for n = to 6. While we interpolate up to n 6 in this work, we note that in practice the benefits of n-gram interpolation saturate past n 4, suggesting that the number of n-gram models can be lowered to reduce storage (Appendix C).
4.1 Generation Quality
We test generation quality on Web'e''ss s test split [15], which consists of 5,000 web-scraped documents. For each document, we use the first 15 tokens as the prefix and generate k = 3 drafts of 10 tokens with batch size of 1. We decide to focus on short generations because drafts are typically a short-form task. Before running experiments, we identify the optimal interpolation weight a and temperature by optimizing for the lowest average perplexity across three drafts on the validation split. We list the specific hyperparameter values that we use in Appendix B.
We only evaluate one draft of the baselines in order to match the compute used by Superposed Decoding. We find that while Nucleus Sampling and Greedy Decoding outperform Superposed Decoding on per-draft basis, the average best perplexity from Superposed Decoding is 5% lower than that of Nucleus Sampling. From the point of view of a user, this means for each prefix, least one draft can be expected to be on par with Nucleus Sampling and Greedy Decoding. The other drafts all come free of additional compute, In the following Sections 4.2 and 4.4, we show that this diversity is beneficial for both factuality and human preference.
Table 1: Superposed Decoding is natural-sounding and has lower average perplexity than Nucleus Sampling, which typically approximates human writing.
Nucleus
Beam/Greedy
N-Gram
Superposed Decoding
Draft
1
2
3
Best
Avg Perplexity
5.17
3.77
152.75
5.03
7.97
10.05
4.63
4.2
Fact-Based Evaluation
Next, we test the ability of Superposed Decoding to generate not only coherent but also accurate completions. We assess this using exact match precision (P@k) for k 1,2,3 on TriviaQA [24] and Natural Questions [29], two common benchmarks for short answer generations. We decide not to

---

TriviaQA
Natural Questions
57.24
50.18
50,59
52.96
20
18:64
18.39
15,17
Accuracy (%)
Accuracy (%)
Nucieus P@1
Beam P@1
Greedy P@
SPD P@
SPD p@P
SPD Pig
Nucteus P
Beam P@
Greedy P@1
SPD P@1
SPD P@2
SPD P@B
Figure Superposed Decoding is as accurate as Greedy Decoding for @@1 and increases the fact-based coverage using multiple drafts (P@2,3) on TriviaQA (left) and Natural Questions (right).
multiple choice datasets such as MMLU [17] and OpenBookQA [33] because multiple choice questions are trivial when using multiple drafts, unfairly advantaging Superposed Decoding.
In Figure 5, we show that Superposed Decoding outperforms Nucleus Sampling and Beam Search at P@ in a zero-shot setting, with three drafts providing aceuracy gains of up to 2.72% in TriviaQA and 1.69% in Natural Questions. These results demonstrate that Superposed Decoding substantially increases the likelihood of getting factually correct generation addition to one that coherent.
4.3 Latency
Superposed Decoding presents significant theoretical reduction in latency, but it is important to investigate how well this translates to the real-world. Figure 6, we show that dictionary lookups are the only additional cost incurred by Superposed Decoding, harring which Superposed Decoding has near-constant compute cost. Even so, the total cost Superposed Decoding is significantly lower than other decoding methods, with Superposed Decoding 2.44x faster three drafts and 3.54x faster on eight compared to Nucleus Sampling, the next fastest.
It is important to note that Superposed Decoding results are obtained using unoptimized code. Our threaded lookup on Python dictionaries, and we do cache any lookup results. This has an enormoos, visible impact. In addition, Liu et al. [31] propose the use of suffix arrays for n- n-gram models, allowing intatinnttntt lookup of arbitrary-lenglt n-grams in trillion-token corpora. These techniques open up multiple avenues for additional speedup.
n- n-gram models are implemented using single-threaded
2.0
Superpased Decading
N-Gram Lookup
60
Nucleus
Average Latency (5)
Sampling
1.5
Beam Search
SPD Draft
3.54x
(%))
40
30
0.5
0.0
10
Number of Generated Drafts
Decoding Method
Figure 6: Average wall clock time to generate 10 token long drafts, with batch size 1, from a 15 token prefix on WebTet.. Superposed Decoding significantly faster for all > 1, with n-gram lookup costs being a major factor for k 2 4, which can be optimized further.
Figure 7: Drafts are ordered by the prob- ability they obtain during generation us- ing SPD, which wins over Nucleus Sam- pling in a compute- normalized setting.

---

4.4 Human Evaluation
While perplexity and factuality are good proxies for textual quality, real human evaluation remains the best measure of coherency. Indeed, perplexity is imperfect evaluator of long- form-formmmm language modelling [44] while factuality metrics are inherently biased towards Greedy Decoding methods [41]. Consequently, to verify our findings, conduct random study asking human respondents to rank Superposed Decoding and Nucleus Sampling generations based on how well they complete a provided prefix. We compare against Nucleus Sampling because n-gram distributions from Nucleus Sampling are demonstrably the closest to those of humans [18].
Setup. We conduct our study using Amazon Mechanical Turk [16]. First, we randomly sample 1,000 prefixes from the OpenWebTex test set, truncating to the first 15 tokens as Section 4.1. Next, we manually remove prefixes that are grammatically incorrect, such as text from website toolbars. From the remaining prefixes, we generate three Superposed Decoding drafts and one Nucleus Sampling draft in compute- normalzzed setting, randomizing their order. Finally, filter out prefixes with duplicate or unparseable generations (c.g. emojis). After preprocessing. 707 prefixes are left.
It is important to note that one Nucleus Sampling generation is 20% less expensive than three Super- posed Decoding drafts, shown in Section 4.3, However, two Nucleus Sampling drafts disadvantages three Superposed Decoding drafts by 60%. Therefore, we decide to run our main survey using the first setup, which closest to equal compute, but also conduct smaller surveys 2v3 and Ivl settings.
Results. We define a Superposed Decoding "win" as when one of the Superposed Decoding drafts find that Superposed Decoding generations preferred
ranked first. As shown in Figure approximately 63.6% of the time. If every Superposed Decoding draft was consistently the same quality Nucleus Sampling, then we would expect the rankings to be uniform, resulting in a 75% win rate. However, this is not the case, suggesting that Nucleus Sampling is more reliable than any individual draft, but the aggregate of drafts provides diversity that highly valuable users.
We run the two scale iterations of the study with 100 prefixes each. In the 2v3 setting, we ask users rank two nucleus drafts and three superposed drafts investigate whether the benefits of Superposed Decoding persist even when compute favors Nucleus Sampling. In the Ivl setting, users choose between nucleus draft and the lowest perplexity superposed draft, removing any potential bias caused by unequal numbers of drafts. As shown in Figure 12, in both situations, users still prefer Superposed Decoding over Nucleus Sampling 60. 60 and 51.4% of the time respectively. While the surveys have higher variance due to their small size, they cement Superposed Decoding as strong alternative to Nucleus Sampling. We show details the additional studies in Appendix F. and present our survey page in Figure 13.
4.5 Inference-Tinn Scaling
Superposed Decoding also provides significant benefits for inference time compute scaling. Su- perposed Decoding completely complimentary to other decoding methods, expanding semantic coverage at no extra compute. For instance, if Nucleus Sampling is used to generate drafts, Su- perposed Decoding with drafts can be spliced at any timestep to strategically produce nkk drafts
Table Coverage on TriviaQA and Natural Questions a normalized compute setting comparing vanilla Nucleus Sampling (NS) to the combination of Nucleus Sampling and Superposed Decoding (NSspDe), where & the number of Superposed Decoding drafts generated on top of each Nucleus Sampled generation. NSPPD results in better coverage at nearly every compute budget n.
Compute (n)
Task
Decoding Method
10
20
30
40
50
70
80
90
100
NS
51.04
68.75
70.31
71.87
72.92
74.48
74.74
75.26
75.78
76.30
76.56
TriviaQA
NSarD2
51.30
68.75
70.57
72.66
74.74
75.78
76.30
76.82
78.39
79.17
79.43
NSsPDa
51.82
70.57
74.22
75.52
77.34
77.87
78.39
78.65
79.17
79.43
79.95
NS
14.32
32.55
36.98
38.54
40.36
41.15
41.67
41.93
42,19
42.71
42.97
Natural Questions
NS
15.36
31.25
34.90
38.02
39.84
41.41
41.67
42.45
43.75
43.75
43.75
NS
15.63
31.25
36.98
39.06
41.15
42.71
43.75
43.75
44.27
44.79
45.57

---

at no extra cost, using the Nucleus Sampled generations as prefixes. This bolsters every Nucleus Sampling generation with local searches (example in Appendix G.2).
This property is valuable for repeated sampling [3], a technique where the number of generations is scaled at inference time increase coverage the proportion of questions that can be answered correctly using at least one of the generations. While repeated sampling typically uses Nucleus Sampling, combining Superposed Decoding and Nucleus Sampling (NSSpp) produces even larger coverage gains. In Table 2, we compare the coverage of vanilla Nucleus Sampling and N NSPP in an equal compute setting up to 100 Nucleus Sampling drafts. We find that S results in higher coverage across the board on both TriviaQA [24] and Natural Questions [29], highlighting Superposed Decoding as a powerful method increase the impact of scaling inference compute.
Further Analysis and Ablations
5.1 Results on Mistral 7B
We also implement Superposed Decoding on pre-trained Mistral 7B [22] and conduct the same experiment as Section 4.1 with one change. In Section 4.1, it was possible to evaluate the perplexity of the 10 generated tokens exactly because the generating model (Llama-2-7B) and the evaluation model (Llama-2-70B) use the same tokenization. This is not the case for Mistral 7B and Llama-2-70B Consequently, we calculate perplexity for Mistral 7B over all tokens but the first five, ensuring that the entire generation is included. While this approach also includes several tokens from the initial prefix in perplexity calculations, they are redundant across generations, thus preserving relative ordering.
Table 3 compares the resulting perplexities. Like with Llama-2-7B. the average best draft perplexity using Superposed Decoding is lower than that of Nucleus Sampling, demonstrating that Superposed Decoding is adaptable to other language models out of the box.
5.2 Textual Analysis
Next, we extensively investigate the diversity and repetition of Superposed Decoding in order to better understand its properties.
Repetition within Generations. Repetition is well-documented issue in all decoding methods but is most prevalent when decoding greedily [18]. We explore to what extent, if any, Superposed Decoding degenerates well. To measure repetition, calculate the proportion of unique unigrams, bigrams, and trigrams in each generation. The lower the uniqueness, the higher the repetition. In Figure 8, plot results for Superposed Decoding and Nucleus Sampling for several generation lengths. Because drafting is usually a short-form task, we only consider generation lengths up to 20 tokens. We find that Superposed Decoding does not repeat significantly more than Nucleus Sampling in this range, suggesting that degeneration is not an issue in most use cases. This is especially true for bigrams and trigrams, which are more reliable indicators of degeneration than unigrams. However, we qualitatively observe that repetitions become frequent after 100 tokens. To address this, we propose Superposed Decoding Resets, which we explain Section 5.3.
Diversity across Drafts. To measure diversity, we apply Self- [45] on drafts and then calculate the average across prefixes. We compute Self-BLEU by calculating the BLEU score of each draft with the other k- drafts as references. Hence, low Self-BLEU signifies high diversity, while a high Self-BLED suggests low diversity. After caleulating Self- BeLf-BLEU for varying prefix lengths, generation lengths, and numbers of drafts, we find that generation length is the most impactful hyperparameter for diverse drafts. We plot Self-BLEU against generation length in Figure 8, demonstrating that shorter generations significantly increase diversity.
Table 3: Superposed Decoding generalizes across language models like Mistral 7B as shown here with similar results on coherency, as Llama-2-7B, when evaluated using Llama-2-708
Nucleus
Superposed Decoding
Draft #
2
3
Best
Avg Perplexity
11.42
11.34
12.74
13.63
10.87

---

1.00
1.0
N-Gram Uniq ueness
Draft Self-BLEU
0.95
0.90
Unigram
0.6
0.85
Bigram
Nucleus
Tigram
Superposed
Prefix Length - 15 Toianns
0.4
10
15
Generation Length
Generation Length
Figure 8: Left: Minimal difference in repetition for Superposed Decoding and Nucleus Sampling in short generations. Right: Generation length is an effective knob for adjusting the diversity of drafts. Both experiments use prefix length of 15 tokens.
5.3 Superposed Decoding Resets
To reduce long-form repetition in Superposed Decoding, we propose resetting superposed tokens every s timesteps, where user-selected hyperparameter. On each reset step sample one the k drafts and restart draft generation. Resetting helps Superposed Decoding escape repetitive loops while reestablishing linearity. which Figure shows deteriorate over time. This similar user selecting one of the & drafts while typing. We find that resetting noticeably improves long-form generation quality (examples in Appendix and leave further investigation for futuree work.
Further, we also ablate on prefix length, generation length, and number of drafts. Figures 9, 10, and 11 in Appendix E highlight that Superposed Decoding robust all three hyperparameters, with lower perplexity than Nucleus Sampling in nearly all settings tested.
6 Discussion and Conclusion
While we demonstrate that Superposed Decoding is an effective technique for multiple draft genera- tion, Superposed Decoding is limited by the quality of the n-gram models used, which essential for maintaining coherence. In addition, while Superposed Decoding drafts are syntactically diverse, they not often semantically diverse. We suspect that the orthogonality of token embeddings discovered by Jiang et al. [23] is a potential solution. While our initial experiments did not show diversity gains, believe that orthogonality is promising and logical next step for future work. We also note that mechanisms, like batching, that increase throughput of decoding algorithms are complementary Superposed Decoding.
In conclusion, we present Superposed Decoding, a novel decoding method that superposes token embeddings generate multiple short generations the cost of one. We demonstrate that Superposed Decoding improves on Nucleus Sampling in terms of generation quality and human preference. The plurality of choices from Superposed Decoding also leads to better performance benchmarks and expands coverage at scale. We envision that the latency reduction from Superposed Decoding will make it practical to apply large tre-trained language models drafting tasks where compute is often a barrier for deployability. Finally, Superposed Decoding can be deployed in messaging applications using n-grams personalized to each user, where the number of n-grams can be reduced to save storage without compromising performance.
common
Acknowledgments
We are grateful Jiacheng (Gary) Liu for his assistance in using infinigram for initial experimentation. We also thank Alisa Liu, Vivek Ramanujan, Reza Salchi, Prateek Jain, Yashas Samaga B L, and Yejin Choi for their feedback. We also acknowledge the computing resources and support from HYAK at the University of Washington, FAS RC at Harvard University & Kempner Institute, Gradient AI and research GCP credit award from Google Cloud and Google Research. Ali Farhadi acknowledges funding from the NSF awards IIS 1652052, IIS 17303 166. DARPA
DARPA W91 15-105433 and gifts from Allen Institute for Artificial Intelligence and Google. Sham Kakade acknowledges funding from the Office of Naval Research under award N00014-22-1-2377. This work has been made possible part by a gift from the Chan Zuckerberg Initiative Foundation to establish the Kempner Institute for the Study of Natural and Artificial Intelligence.
10

---

References
[1] M. Adnan, A. Arunkumar, G. Jain, P. J. Nair, I. Soloveychik, and P. Kamath. Keyformer: Kv cache reduction through key tokens selection for efficient generative inference, 2024.
[2] J. Ainslie, J. Lee-Thorp, M. de Jong, Y. Zemlyanskiy, F. Lebrón, and S. Sanghai. Gqa: Training generalized multi-query transformer models from multi-head checkpoints, 2023.
[3] B. Brown, Juravsky, R. Ehrlich, R. Clark, Q. Le, C. Ré, and Mirhoseini. Large language monkeys: Scaling inference compute with repeated sampling, 2024. URL https: //arxiv. wrg/abs/////eeooooooo.oooeeeeege absaaass0000 21787.
[4] T. B. Brown, B. Mann, N. Ryder, M. Subbiah, J. Kaplan, P. Dhariwal, Neelakantan, P. Shyam, G. Sastry, A. Askell, S. Agarwal, A. Hoss, G. Krueger, T. Henighan, R. Child, A. Ramesh, M. Ziegler, J. Wu, C. Winter, C. Hesse, M. Chen, E. Sigler, M. Litwin, Gray, B. Chess, J. Clark, C. Berner, S. McCandlish, A. Radford, I. Sutskever, and D. Amodei.
Language models are few-shot learners, 2020.
[5] Cai, Y. Li, Z. Geng, H. Peng, D. Lee, D. Chen, and T. Dao. Medusa: Simple Ilm inference acceleration framework with multiple decoding heads, 2024.
[6] C. Chen, S. Borgeaud, G. Irving, J.-B. Lespiau, L. Sifre, and J. Jumper. Accelerating large language model decoding with speculative sampling. arXiv preprint arXiv:2302.01318 2023.
[7] M. Chen, J. Tworek, H. Jun, Q. Yuan, H. P. O. Pinto, J. Kaplan, H. Edwards, Burda, N. Joseph, G. Brookman, et al. Evaluating large language models trained on code. arXiv preprint arXiv:2107.088 033744, 2021.
[8] M. X. Chen, B. N. Lee, G. Bansal, Y. Cao, S. Zhang, J. Lu, Tsay, Y. Wang, A. M. Dai, Z. Chen, T. Sohn, and Y. Wu. Gmail smart compose: Real-time assisted writing, 2019.
[9] T. Computer. Redpajama: an open dataset for training large language models, 2023, URL http://ttteereccotttt/eeeeeaaa LooddPaaaa-aaaaaee Ima--ata..
https://gt https://gthhb....t.e thub. wttcc//o/////// wttpb..ccommtgggtheerrrrpreeeeee
[10] T. Dettmers, M. Lewis, Y. Belkada, and L. Zettlemoyer. Llm.int80: 8-bit matrix multiplication for transformers at scale, 2022.
[11] Devvrit, S. Kudugunta, A. Kusupati, T. Dettmers, K. Chen, I. Dhillon, Y. Tsvetkov, H. Hajishirzi, S. Kakade, A. Farhadi, P. Jain, et al. Matformer: Nested transformer for elastic inference. arXiv preprint arXiv:2310.07707, 2023.
[12] A. Fan, Lewis, and Dauphin. Hierarchical neural story generation, 2018.
[13] E. Frantar, S. Ashkboos, Hoefler, and Alistarh. Gptq: Accurate post-training quantization for generative pre-trained transformers, 2023.
[14] F. Gloeckle, B. Y. Idrissi, B. Rozière, D. Lopez-Paz, and G. Synnaeve. Better & faster large language models via multi-token prediction, 2024.
[15] A. Gokaslan and V. Cohen. Openwebtext corpus. http:///kkylinn007. www.oo...tttuubii.i. io/ OpenWebTextCCrpuss, 2011 2019.
[16] V. Harinarayan, A. Rajaraman, and A. Ranganathan. Hybrid machine/human computing arrangement. United States Patent.
[17] D. Hendrycks, C. Burns, S. Basart, A. Zou, M. Mazeika, D. Song, and J. Steinhardt. Measuring massive multitask language understanding, 2021.
[18] A. Holtzman, J. Buys, L. Du, M. Forbes, and Y. Choi. The curious case of neural text degeneration, 2020.
[19] W. Huang. Y. Liu, H. Qin, L., S. Zhang, X. Liu, M. Magno, and X. Qi. Billm: Pushing the limit of post-training quantization for 1lms, 2024.
[20] H. Husain, H.-H Wu, T. Gazit, M. Allamanis, and M. Brockschmidt. CodeSearchNet challenge: Evaluating the state of semantic code search. arXiv preprint 10XVv:1909009436. 2019.
11

---

[21] B. Institute. 9 ux best practice design patterns for autocomplete suggestions. 2023, URL https://baymars com/blog/ wwwoocompeeeedeeieeeee Accessed: 2024-05-18.
[22] A. Q. Jiang, A. Sablayrolles, A. Mensch, C. Bamford. D. Chaplot, D. de las Casas, Bressand,
G. Lengyel, G. Lample, L. Saulnier, L. R. Lavaud, M.-A. Lachaux, P. Stock, T. L. Scao, T. Lavril,
T. Wang, T. Lacroix, and W. E. Sayed. Mistral 7b, 2023.
[23] Y. Jiang, G. Rajendran, P. Ravikumar, B. Aragam, and V. Veitch. On the origins of linear representations in large language models, 2024.
[24] M. Joshi, E. Choi, D. S. Weld, and L. Zettlemoyer. Triviaqa: A large scale distantly supervised challenge dataset for reading comprehension, 2017.
2017.
[25] U. Khandelwal, O. Levy, D. Jurafsky, L. Zettlemoyer, and M. Lewis. Generalization through memorization: Nearest neighbor language models. arXiv preprint 0rXiv:1911.00172 2019.
[26] S. Kim, K. Mangalam, S. Moon, J. Malik, M. W. Mahoney, A. Gholami, and K. Keutzer. Speculative decoding with big little decoder. Advances in Neural Information Processing Systems, 36, 2024.
[27] N. Kitaev, Łukasz Kaiser, and A. Levskaya. Reformer: The efficient transformer, 2020.
[28] A. Kusupati, Ramanujan, R. Somani, M. Wortsman, P. Jain, S. Kakade, and A. Farhadi. Soft threshold weight reparameterization for learnable sparsity. In International Conference on Machine Learning, pages 5544 5555. PMLR, 2020.
[29] T. Kwiatkowski, J. Palomaki, O. Redfield, M. Collins, A. Parikh, C. Alberti, D. Epstein, I. Polosukhin, M. Kelcey, J. Devlin, K. Lee, K. N. Toutanova, L. Jones, M.-W. Chang, A. Dai, J. Uszkoreit, Q. Le, and S. Petrov. Natural questions: a benchmark for question answering research. Transactions of the Association of Computational Linguisties, 2019.
[30] Y. Leviathan, M. Kalman, and Y. Matias. Fast inference from transformers via speculative decoding, 2023.
[31] Liu, S. Min, L. Zettlemoyer, Y. Choi, and H. Hajishirzi. Infini-gram: Scaling unbounded n-gram language models to a trillion tokens. arXiv preprint arXiv:2401.13377 2024.
[32] S. Ma, H. Wang, L. Ma, L.. Wang, W. Wang, S. Huang, L. Dong, R. Wang, J. Xue, and F. Wei. The era of 1-bit Ilm:: All large language models are in 1 1.58 bits, 2024.
[33] T. Mihaylov, P. Clark, T. Khot, and A. Sabharwal. Can suit of armor conduct electricity? new dataset for open book question answering, 2018.
[34] e. a. OpenAl. Gpt-4 technical report, 2024.
[35] K. Park, J. Choe, and V. Veitch. The linear representation hypothesis and the geometry of large language models. arXiv preprint 2.ti::3//1.03556 2023.
[36] W. Qi. Y. Yan, Y. Gong, D. Liu, N. Duan, J. Chen, R. Zhang, and M. Zhou. Prophetnet: Predicting future n-gram for sequence-to- sequeneee pre-training, 2020.
[37] N. Shazeer. Fast transformer decoding: One write-head is all you need, 2019.
[38] W. Shi, J. Michael, S. Gururangan, and L. Zettlemoyer. Nearest neighbor shot inference. In Conference on Empirical Methods in Natural Language Processing, 2022. URI. https: //api. semanticscholarr
Trrg/orpusIDD 249152130.
[39] M. Sun, Z. Liu, A. Bair, and J. Z. Kolter. A simple and effective pruning approach for large language models, 2024.
[40] I. Sutskever, O. Vinyals, and Q V. Le. Sequence to sequence learning with neural networks. Advances in neural information processing systems, 27, 2014.
[41] H. Touvron, T. Lavril, G. Izacard, X. Martinet, M.-A. Lachaux, T. Lacroix, B. Rozière, N. Goyal, E. Hambro, F. Azhar, A. Rodriguez, A. Joulin, E. Grave, and G. Lample. Llama: Open and efficient foundation language models, 2023,
12

---

[42] H. Touvron, L. Martin, K. Stone, P. Albert, A. Almahairi, Y. Babaei, N. Bashlykov, S. Batra, Bhargava, Bhosale, D. Bikel, L. Blecher, C. C. Ferrer, M. Chen, Cucurull, D. Esiobu, J. Fernandes, J. Fu, W. Fu, B. Fuller, C. Gao, V. Goswami, N. Goyal, A. Hartshorn, S. Hosseini, R. Hou, Inan, M. Kardas, V. Kerkez, M. Khabsa, Kloumann, Korenev, P. S. Koura, M.-A. Lachaux, T. Lavril, J. Lee, D. Liskovich, Y. Lu, Y. Mao, X. Martinet, T. Mihaylov, P. Mishra, I. Molybog. Y. Nie, A. Poulton, Reizenstein, R. Rungta, K. Saladi, A. Schelten, R. Silva, E. M. Smith, R. Subramanian, X. E. Tan, B. Tang, R. Taylor, A. Williams, J. X. Kuan, P. Xu, Z. Yan, Zarov, Y. Zhang, A. Fan, M. Kambadur, S. Narang, A. Rodriguez, R. Stojnic, S. Edunov, and T. Scialom. Llama 2: Open foundation and fine-tuned chat models, 2023.
[43] S. Wang, B. Z. Li, M. Khabsa, H. Fang, and H. Ma. Linformer: Self-attention with linear complexity, 2020.
[44] Q. Zhang, D. Ram, C. Hawkins, S. Zha, and T. Zhao. Efficient long-range transformers: You need attend more, but necessarily every layer, 2023.
[45] Y. Zhu, S. Lu, L. Zheng, Guo, W. Zhang, Wang, and Y. Yu. Texygen: benchmarking platform for text generation models. SIGIR, 2018.
13

---

A Superposed Decoding Pseudo-Code
Algorithm Superposed Decoding algorithm generating drafts.
1: Input: Prefix M (T) ( Fm). generation length G
2: Initialize & + m + 1
3: Initialize D - {M }b
Draft store
4: while L o m + G do
5: if m + then
> First timestep
6:
Pa - (MM do
7:
for
8:
sy - t- Largest(po: i)
D. Take the 1th most probable token
9:
D; + (D, U x m
10:
end for
11:
Tm+1 Superposel (1) m+1
m+1)
Superpose the selected tokens
else
13:
pø fo(M, 1m=1:111 Pe +- KcepTopK(pp)
14:
>> Keep only the top tokens
15:
for i 1 to do
16:
Pngram t N-Gram(D,)
> Calculate the n-gram distribution of draft i
17:
Pf Interpolate (po, Pugram)
18:
for r E pf do
19:
Demp +- (D, x + (DUDemp)
Create new draft option b Add draft option to draft store
20:
21:
end for end for
22:
23:
D (D)
Keep the top & drafts Superpose most recent tokens from drafts
24:
E. <- Superpose(at........
end
26:
t ++1
27:
end while
28: return D
B Hyperparameter Choices
and We find that the best performing hyperparameters for coherent generation Llama-2-7B are = 0.54 and 0.06, which we use in Section 4.1, 4.3, and 4.4. The only exception is in Section 4.2, where we disable n-gram smoothing.
N-Gram Interpolation. The weights we use for interpolation are [0.01, 0.04, 0.15, 0.18, 0.12] for 6.
C
Perplexity Evaluation with Fewer N-Grams
We evaluate perplexity for Superposed Decoding on the only n-grams from 2 n requiring only 2.64 GB of storage. We use the same n-gram interpolation weights as in Section but retune a and 7 to 0.55 and 0.1 respectively. In Table 4, we show that the perplexity Sampling perplexity. This demonstrates that Superposed Decoding can be effectively implemented with minimal storage overhead in storage-constrained devices like smartphones.
test split by interpolating
the average best generation almost identical the average Nucleus
D Standard Deviations for Perplexity Evaluation
We calculate the standard deviations across the 5000 for 1lama-2-7B and Mistral 7B and show them below in Tables and We note that Superposed Decoding has higher standard deviation than Nucleus Sampling and Beam Search when implemented
prefixes used for evaluation
14

---

Table 4: Superposed Decoding is highly competitive with Nucleus Sampling even when only n-grams from are interpolated calculate Pagrum-
Nucleus
Beam/Greedy
N-Gram
Superposed Decoding
Draft
2
Best
Avg Perplexity
5.17
3.77
152.75
5.83
8.38
9.97
5.18
on Llama-2-7B but that the standard deviations equalize on Mistral 7B. Despite this high variance, human evaluation results in Section 4.4 affirm that Superposed Decoding is consistently competitive coherency.
Table 5: Standard deviation of Llama-2-7B generation perplexity calculated on Open WebText test. split in Section 4.1.
Nucleus
Beam/Grredy
N-Gram
Superposed Decoding
Draft #
2
Best
Avg Perplexity
4.82
3.31
305.00
8.90
14.44
20.58
8.24
Table 6: Standard deviation of Mistral 7B generation perplexity calculated on Open test split in Section 5.1.
Nucleus
Superposed Decoding
Draft
Best
Avg Perplexity
10.19
9.92
11.53
12.53
9.38
E Further Ablations
In this section, we present further ablations studying the impact of number of drafts, prefix length, and generation length on Superposed Decoding perplexity (average best). We find that for scenarios such that the number of drafts (Figure 9). This is generally expected as the higher the number of drafts, the higher the likelihood that at least one draft is good quality. Similarly, we find that Superposed Decoding is robust to prefix length and generation length. Indeed, the patterns of Superposed Decoding given longer prefix and generation lengths mimic those of Nucleus Sampling in the same situation, with consistently similar perplexities suggesting good performance (Figures 10, 11).
3. Superposed Decoding consistently outperforms nucleus sampling
F
Human Evaluation
F.1
Additional Results
We the same experiment as in Section 4.4 more times a smaller scale. First, we compare two Nucleus Sampling drafts and three Superposed Decoding drafts. This scenario results in significant compute advantage for Nucleus Sampling. Still, we find that Superposed Decoding wins the majority of the time, with win rate of 60.6%. However, this is slightly lower than the 64% win rate in the main study.
Next, we compare one Nucleus Sampling draft and the lowest perplexity Superposed Decoding draft of three. This mimics the perplexity evaluation in Section 4.1 but in human setting. We find that Superposed Decoding is still ranked first the majority of the time, with a 51 win rate.
For cost efficiency, we run both studies only 100 random prompts, with five responses per prompt.
15

---

SPD
Nucleus
5.5
Beam
Perplexity
5.0
4.5
4.0
2
3
4
6
10
Number Drafts
Figure 9: Average perplexity of one draft of Nucleus Sampling and Beam Search compared against
average best perplexity of SPD using drafts k {2, 3, 4, 5, 6, 10) OpenWebText. SPD outperforms Nucleus Sampling for all values of k tested.
6.0
Nucleus
Perplexity
5.5
5.0
4.5
5
15
25
40
Prefix Length
Figure 10: Average perplexity of one draft of Nucleus Sampling compared against average best perplexity of SPD for prefix lengths 5, 15, 25, 40. We find that SPD and Nucleus Sampling consistently have similar perplexities.
SPD Nucleus
Perplexity
10
15
20
Generation Length
Figure 11: Average perplexity of one draft of Nucleus Sampling compared against average best perplexity of SPD for generation lengths 5, 10, 15, 20. We find that SPD is robust for wide range of short form generation lengths.
16

---

60
Nucleus
50
Nucleus
SPD Draft
SPD Draft
IM
SPD Draft
50
SPD Draft
40
Win Rate (%)
40
Win Rate (%)
30
30
20
20
10
10
0
Nucleus
SPD
Nucleus
SPD
Decoding Method
Decoding Method
Study results comparing two Nucleus Sampling drafts and three Superposed Decoding drafts. Right: Study results comparing one Nucleus Sampling draft & the lowest perplexity Superposed Decoding draft out of three generations. Note that uncertainty is higher for both iterations due to smaller sample size.
Figure 12: Left:
F.2 Mechanical Turk Survey
We show screenshot of our study page in Figure 13. We compensate workers an approximate rate of $15 per hour.
G Example Generations
G.1 Superposed Decoding
In Figure 14, we show 12 additional example generations comparing Superposed Decoding and Nucleus Sampling
compute-normalizee setting. Prefixes are sampled from Open WebTeex and truncated to the first 15 tokens, and each generated completion is 10 tokens in length.
G.2 Nucleus Sampling and Superposed Decoding
In Figure 15, we show an example generation that outputs three drafts using Nucleus Sampling for several timesteps, followed by Superposed Decoding with k This results in nine total drafts the compute of only three Nucleus Sampling drafts. The final Superposed Decoding drafts maintain the wide coverage offered by Nucleus Sampling and complement it with additional local coverage.
H Layer-Wise Linearity
In Figure 16, we show the cosine similarity between superposed embeddings {#} and the linear combination of the component embeddings of three tokens, after each layer within the first five timesteps using Llama-2-7B, Within each timestep, superposed embeddings pass through an initial layer (Layer 1) that embeds token indices and weights the resulting embeddings using corresponding token weights. The weighted embedings then pass through 32 transformer blocks (Layers 2-33), then through a final linear projection layer (Layer 34) that produces the output superposed embedding of that timestep.
17

---

I Resetting
Here, we show examples of the Superposed Decoding Resetting technique described in Section 5.3 for generations of 200 tokens using prefixes from OpenWebText. Superposed Decoding Resetting is significantly less repetitive than non-reset Superposed Decoding. However, Nucleus Sampling, which also shown, is qualitatively still the best performing decoding method in long form settings.
Prompt #1
Superposed Decoding with Resetting
Sydney architect Rana Abboud won NAWIC Scholarship for 2019. Sydney-based architect and interior designer Rana Abboud has been awarded a $10,000 scholarship to study a Masters of Architecture at the University of New South Wales. The scholarship, awarded by the National Association of Women in Construction (NAWIC) is designed to help women in the construction industry advance their careers. Rana Abboud, graduate of the University of Sydney, is the founder of Rana Abboud & Associates. am honoured to be awarded this scholarship. am passionate about design built for people and the environment. my studies and continue to develop my skills and knowledge," she said. The NAWIC Scholarship is awarded to women who are studying or working the construction industry. "The NAWIC Scholarship is great opportunity for women to further their care and
excited to be able further
Superposed Decoding without Resetting
Sydney architect Rana Abboud won NAWIC Scholarship in 2017. The National Association of Women in Construction (NAWIC) has announced the winners of its 2017 scholarships. The NAWIC Scholarship Program is designed to encourage women pursue careers in the construc- tion industry. The 2017 scholarship recipients are: Rana Abboud, student at the University of New South Wales, who studying a Bachelor of Architecture. Megan Brennan, student at the University of New South Wales, who is studying a Bachelor of Construction Management. Katee Cox, a student at the University of New South Wales, who is studying a Bachelor of Construction Management. Kate Dunn, student at the University of New South Wales, who is studying Bachelor of Construction Management, Kate Foster, student at the University of New South Wales, who
Nucleus Sampling
Sydney architect Rana Abboud won a NAWIC Scholarship of $1000 for 'Significant Contri- bution to Career Growth'. Sydney architect Rana Abboud has the National Association of Women Construction (NAWIC) NSW/ACT Scholarship for 2017 for 'Significant Contribution to Career Growth'. She has also just been accepted to undertake Master of Science in Archi- tecture with Higher Degree by Research at Sydney University. The scholarship one of eight awards presented by NAWIC women further their studies in the construction industry in Australia. "As working mother, am very grateful for the support am receiving to further my professional and academic development," Abboud said. Rana Abboud (middle) with associates (L-R) Tara Abdul-Khaled and Aditi Rana. Abboud is director of Pal Architecture in Alexandria,
Prompt #
18

---

Superposed Decoding with Resetting
NEW DELHI: Here's something ayurveda gurus have been telling for years. A new study has found that combination of three herbs including ashwagandha, guduchi and shatavari can help in the treatment of diabetes. "The study was conducted to evaluate the efficacy and safety of poly-herbal formulation containing three herbs Ashwagandha (Withania somnifera), Guduchi (Tinospora cordifolia), and Shatavari (Asparagus racemosus) in inhibiting the progression of diabetes in alloxan-induced diabetic rats" said the study published in the journal 'Journal of Ayurveda and Integrative Medicine'. The study was conducted by research team from the Department of Pharmacology, Dr D. Patil College of Pharmacy, Pune, Maharashtra, and the Department of Pharm
Superposed Decoding without Resetting
NEW DELHI: Here's something ayurveda gurus have been saying for years: Eat your way to health. A new study has found that a diet rich in fruits and vegetables can help reduce the risk of developing type 2 diabetes. The study, published in the journal BMJ Open, found that diet rich in fruits and vegetables can help reduce the risk of developing type 2 diabetes. The study, which was conducted by researchers from the University of Oxford, found that diet rich in fruits and vegetables can help prevent the risk of developing type 2 diabetes. The study, which was conducted by researchers from the University of Oxford, found that diet rich in fruits and vegetables can help prevent the risk of developing type diabetes. The study, which was conducted by researchers from the University of Oxford, found that diet rich fruits and vegetables can help prevent the risk
Nucleus Sampling
Here's something ayurveda gurus have been telling us about for years eating seasonal fruits and vegetables helps stay healthy. Here 7 foods which can keep you healthy during the summer. Pomegranate is a summer fruit and if you wish to have optimum health, it is necessary this fruit. The fruit be eaten in raw form, or into pieces and mixed with honey and taken twice day. The skin of the fruit is itself health tonic and can be chewed. It contains natural bleaching properties. The fruit can also be squeezed and then the pulp mixed with milk, cumin seeds, one teaspoonful of honey and a pinch of ginger and drank thrice daily. Beets are popular root vegetable. Beetroot juice may help increase exercise endurance, potentially because it increases blood flow, said WebMDD. The best fruits
NEW DELHI:
Prompt
Superposed Decoding with Resetting
As part of broad initiative to combat sexual harassment and assault, the University of California, Berkeley has launched a new website to help students, staff, and faculty report and respond to sexual harassment and assault. The new site, which went live Monday, is the one-stop destination for all things related to sexual harassment and assault at UC Berkeley. It is the result of collaboration between the Office of the Vice Chancellor of Student Affairs and the Office of the Vice Provost for Academic and Student Affairs. "This is a critical time for our campus and come together to address sexual harassment and assault in community," said Vice Chancellor for Student Affairs, Steph Sutton-Wheeler Wheeler, in a statement. "We are committed to providing safe and inclusive environment for all members of our community and this website is critical step in that effort." The site provides information on how to report sexual harassment and assault, as well as the for
19

---

Superposed Decoding without Resetting
As part of a broad initiative combat sexual harassment and assault, the University of Califor- nia, Berkeley, has launched new website that provides information about the university's s policies and procedures for reporting and responding sexual harassment and sexual violence. The website, which is available at htt:://sexualharassmett..m hataaaaassmmeet.eeelee.e..eeee berkeley.edu, is designed to help students, faculty and staff understand their rights and responsibilities under the university's policies and procedures. The website includes information about the university's 's policies and procedures for reporting and responding to sexual harassment and sexual violence, as well as information about the university's ' policies and procedures for investigating and responding to sexual harassment and sexual violence. The website also includes information about the university's 's policies and procedures for investigating and responding to sexual harassment and sexual violence, including information about the university's policies and procedures for investigating and responding to sexual harassment and sexual violence in the workplace.
Nucleus Sampling
As part of a broad initiative to combat sexual harassment and misconduct on campus, task force consisting of faculty, staff, students, and other members of the campus community will present draft report with recommendations at the Board of Trustees meeting on Friday, October 27, 2017. Under the leadership of Executive Director for Human Resources Jesse Bozeman, the task force was formed to address concerns raised at the end of the Spring 2017 semester, which included Student Government Association resolution and student-driven, faculty-approved course called "Sexual Misconduct: Consent and Culture," " taught by Professor Nancy Cantalupo and co-sponsored by Campus Life, Student Affairs, and Academic Affairs. The task force is comprised of the following members: Diana Ballin, Senior Lecturer the Department of Anthropology, Chair; Patricia Hopkins, Dean of Students; Kelly MeSweeney
20

---

Short Instructions Consent Form
Summary: Your task is rank four language model outputs based on how well they complete the provided prompt. should than a minute.
Data collccion shoring: We will not ask you for your name, and the data collected this study will be made unidentifabble the best our extent, We securely
only
Criteria: You should id rank completions coherency and and foctualiy only. Coherent generations should be gr grammatically correct and make logical sense. Some options may seem equally preferable. In suth pick
qualitied researchers degg. who study language model text completions), If you later decide that you do not want your responses includied this study, please email so can exclude your work.
cases, try your
other!
Exomples:
Contact: any about shudy, contacting
Prompt: The Engli soccer club flew yesterday
you should below.
Best Completion: compete tourn
Second Best: compete in comp
compete Fourth Best: with high hopes to sell
Prompt: in interview with BBC, Best Completion: the presi dent stated his desi Second Best: the manager explained inter Third Best: the man ager explained his favor defended decision
Fourth Best:
Task:
Order the completions in decreasing order such that the preferred one is the tap. denotes break
Prompt: s(prompt)
Candidates//Comglletons
(pen 1)
$ (gen 2)
$ $genn_3 3)
$ (gen 4)
(Optional) Please let us know if anything was unclear, if you experienced any issues, or if you have any other feedback for
Submit
Figure 13: A screenshot of our Mechanical Turk template, which presents the respondent with task summary, objective criteria for ranking generations, and two examples.
21

---

TeenWebText
When I worked scout for the Carolina Panthers in the
Over the next few years, NASA plans to get back to launching
As kid, played game called The Sims, a simulation life in suburban neighbormood.
Nucleus
1990s, would often
rockets from Cape Caneveral, Florida
always
your character and live game where you could create a character and live out astronauts from U.S. soil,
game where you
astronauts from U.S. soil.
Superposed
1990s, was
1990s, was responsible
game where you can create your character and live their
astronauts
OpenWebText
"Do you want extended warranty with that?"
Just this Tuesday wrote calling MUD present
Synopsis A library for running tasks(jobs)
Nucleus
"No, thanks. I'm sure
cluster of nodes. provides simple API
pian the community to resolve the situstion with the
don't want an extended
Installation
plan public
Superposed
'No. don't think exlended
cluster of computers. #0 installation
pian the public for the fulure the site pian to the community for the future of the M
Noo. don't want any extended
cluster of nodes. Ht Installation
OpenWebText
undergraduate,
"The Log
they?
In gluten-free
pie
Nucleus
Discovery' with
bassy.
ic of Scientific Discovery' with the lase
I'm not suro. I'm working sure. I'm not perfect. I'm working
the bananas are baked into cust bananas are baked
Superposed
Scientific Discovary" the Scientific: Discovery" from the late
the bananas are baked into the cust
OpenWebText
most managers probably starting
Various ancient maps discovered throughout time reveal slightly different reality than
figure out, Midfielders
Martin Shkreli, the bad boy of the U.S.
Nucleus
are the most important part of team. This
pharmaceutical industry, was convicted
what we are used to seeing. The maps
are important part the team. They
pharmaceutical industry,
Superposed
are most important are the most important part of a team. They
the team. They phermaceutical industry. has been found
what we used to. The world famous what we are used to. The most interesting
pharmaneutical industry, has been arrested
Figure 14: Additional qualitative text generations in a compute- compute-normalln normalized setting for Superposed Decoding and Nucleus Sampling with prefixes sampled from OpenWebTer.
22

---

Prompt (x1)
Nucleus Sampling (x3)
Superposed Decoding (x9)
Melboume is great city, with lot of things Melboume is great with lot things Melboume is great city, with a lot of history
Melbourne a great city, with
Melboume is city of many different cultures and relig Melboumne is city of many different cultures, relig Melboume is city of many different cultures and languages
Melbourne is a city of many different
Melboume
Melboume is the capital city of Victoria, Australia. It Melboume is the capital city Victoria and Australia. Melboume is the capital city of Victoria, Australia. The
Melbourne the capital city of Victoria
Figure 15: Example output generated by combining Nucleus Sampling and Superposed Decoding. Superposed Decoding generates three drafts per Nucleus Sampling sample, resulting in nine total drafts.
Timestep
Timestep
Timestep
0.98
Timestep
0.96
Timestep
0.92
Simllarity
0.90
0.86
0.84
0.80
X
0.78
0.74
0.72
Layer
Figure 16: Layer-wise linearity analysis of the first five timesteps on Llama-2-7B with three tokens. The relationship between superposed embeddings and the component token embeddings is initially entirely linear; linearity then degenerates over the first few layers, but gradually recovers through the subsequent transformer block layers.
23

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: All the claims made in the abstract and introduction are supported by problem formulation, solution and empirical evaluation.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We talk about the limitations of the proposed method in Section 6 along with appropriate places in the manuscript.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
Justification: N/A
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: The entire algorithm, experimental setup, and evaluation methodology clearly outlined in the paper. We shall also open-source the code.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The code will be open-sourced and all the experiments are done on public datasets and open models.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: See Section 4 and the Appendix.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Some of the baselines and our method are probabilistic and we have reported the means and standard deviation where applicable.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
24

---

Justification: See Section 4
9. Code Of Ethies
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics httpa: http:///neuispppeeeee httpe//pppp...cpppcccccccccacaaa
Answer: [Yes]
Justification: The paper deals with decoding algorithms for autoregressive inference which does not violate any aspect of the code of ethics.
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: As with any decoding algorithm the method tries to elicit information from large language model but n-gram interpolation has the potential to make more factual than it currently is. That being said, there are significant positive negative societal impacts this work.
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: We do not release any potentially misusable artifacts.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: We open language models and public datasets but do not train add any new things to them. We provide MIT License software to be used with the model and data.
New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: N/A
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [Yes]
Justification: See Figure 13
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: We obtained an IRB exception for the user study.
25


Reviews:
[{"review_id": "sec8SYNae2", "reviewer": "Reviewer_Tak7", "summary": "This paper presents a method to generate multiple sequences from an autoregressive model with a single forward pass. The Superposed Decoding method relies on the approximate linearity of the overall model to additively superpose embeddings for distinct sequences through the model in the same forward pass.", "questions": "The exploration of the alignment between the component vector and the superposition in Figure 3 is interesting, but could the authors create a baseline to get a better idea of how strong the alignment is. For example, calculating alignment between unrelated sequences would give a better idea of what the expected lower bound of of alignment would be.\n\nFor Table 3, again, to get a better idea of the properties of Superposed Decoding, can the authors show what the best perplexity would be (ignoring the fixed compute constraints/comparisons) if one were to generate multiple drafts from Nucleus, Beam/Greedy would be. This is strictly to understand what the difference would be if one were trying to generate the best sequences possible with each type of sampling to see if there's a reduction to that bound when using superposed decoding.\n\nHow much does the n-gram \"filtering\" improve generation quality of the decoding? What are the metrics without this additional step? How much does this step help the other methods like Nucleus/Beam sampling?", "limitations": "No societal impact needs to be addressed for this work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The method is shown to have practical benefit over other sampling methods. The idea appears to be novel and is surprising that it works, albeit with an additional n-gram filtering step.", "weaknesses": "Understanding this phenomenon better in the architectures tested like LLaMA and Mistral would help the idea in this paper substantially. What is it about the representations that allows them to be processed in superposition and why do these LLMs tend to remain in this condition. Is this impacted by the depth of the network?\n\nThere's an important aspect of the kind of linearity that allows the superposition observed here compared to previous work mentioned like [34. 22] cited in this work. The other work showed that representations of concepts are linear, but not that the decoding operations can process superpositions in a linear fashion. Furthermore, the Superposed Decoding method implies that these properties hold for intermediate representations throughout the network.\n\nAlso, some relevant work in this direction are worth mentioning:\n\nElhage, Nelson, et al. \"Toy models of superposition.\" arXiv preprint arXiv:2209.10652 (2022).\nCheung, Brian, et al. \"Superposition of many models into one.\" Advances in neural information processing systems 32 (2019).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive review and glad that the reviewer found the idea novel. We appreciate pointing to related work that we forgot to add in the paper initially and will add it. Below, we provide the clarifications requested:\n\n**1. Understanding the phenomenon:** We agree with the reviewer that the success of superposition is a surprising phenomenon and there is a lot to be understood. As pointed out by the reviewer, previous works on understanding superposition (Elhage, Nelson, et al.) and newer updates (Olah et al., July 2024) point to a need for more investigation. We are unsure about exactly what allows representations to be processed while being in superposition, but do observe that this phenomenon happens across various classes of LLMs (Llama, Mistral, OLMo (see below)). \n\nWith regards to the impact of network depth, we are unsure what the reviewer means and would appreciate clarification. If they mean the intermediate layers of the language models we currently use, we include an additional figure on linearity by layer in Llama-2-7B, which can be found in Figure 1 of the general response PDF. We will update the paper to contain this. Alternatively, if they mean models of different depth, we run additional experiments on linearity for OLMo-1B, OLMo-7B, Llama-2-13B, and Llama-2-70B. Interestingly, we discover that OLMo-7B is less linear than OLMo-1B. However, Llama-2-13B (40 layers compared to 7B’s 32 layers) is significantly more linear than Llama-2-7B. Linearity further improves on Llama-2-70B (80 layers) from Llama-2-13B. This variance highlights that there is still a lot more about superposition that we can learn.\n\n_Numbers 0-20 in the table represent timesteps._\n\n| Model       | Layers | 0 | 1    | 2    | 3    | 4    | 5    | 6    | 7    | 8    | 9    | 10 | 11   | 12   | 13   | 14   | 15   | 16   | 17   | 18   | 19   | 20      |\n|-------------|-------------|---|------|------|------|------|------|------|------|------|------|-------------|------|------|------|------|------|------|------|------|------|---------|\n| OLMo-1B| 16| 1 | 0.96 | 0.93 | 0.91 | 0.88 | 0.88 | 0.88 | 0.89 | 0.89 | 0.86 | 0.88| 0.87 | 0.88 | 0.87 | 0.87 | 0.85 | 0.86 | 0.85 | 0.85 | 0.85 | 0.87    |\n| OLMo-7B     | 32| 1 | 0.91 | 0.86 | 0.81 | 0.78 | 0.76 | 0.73 | 0.72 | 0.70 | 0.70 | 0.67| 0.65 | 0.65 | 0.60 | 0.58 | 0.59 | 0.59 | 0.60 | 0.57 | 0.59 | 0.58    |\n| Llama-2-7B  | 32| 1 | 0.92 | 0.84 | 0.79 | 0.81 | 0.76 | 0.71 | 0.65 | 0.67 | 0.61 | 0.59| 0.55 | 0.54 | 0.45 | 0.47 | 0.45 | 0.46 | 0.39 | 0.36 | 0.39 | 0.37    |\n| Llama-2-13B | 40| 1 | 0.95 | 0.91 | 0.88 | 0.85 | 0.85 | 0.83 | 0.79 | 0.78 | 0.77 | 0.76| 0.73 | 0.71 | 0.69 | 0.66 | 0.67 | 0.68 | 0.64 | 0.64 | 0.63 | 0.61    |\n| Llama-2-70B | 80| 1 | 0.94 | 0.92 | 0.91 | 0.89 | 0.87 | 0.84 | 0.83 | 0.84 | 0.81 | 0.82| 0.75 | 0.74 | 0.74 | 0.71 | 0.68 | 0.73 | 0.68 | 0.67 | 0.67 | 0.65    |\n\n**2. Observed Linearity:** We agree that our observation of superposition is not the same as other works. Figure 1 in the general response PDF shows that the linearity is more profound in the initial and later layers of the LLM than the middle layers, albeit still much better than random. In addition, while our experiments do suggest that decoding operations can process superpositions linearly, it is important to note that decomposing the superposed representation assumes that the top-k tokens provide a basis for the superposition and still requires further denoising with an n-gram model. We believe there is a lot of interesting future work to be done in this direction.\n\n**3. Linearity analysis with random sequences:** Thanks for the suggestion! Here are results from cosine similarity between random sequences to calibrate what a lower bound would be. Results are averaged over 5000 pairs of random sequences from OpenWebText. We will update our paper with these results as well.\n\n|Timestep|1|2|3 | 4| 5| 6| 7| 8| 9| 10| 11| 12| 13| 14| 15| 16| 17| 18| 19| 20  |\n|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|\n|**Cosine Similarity**|0.56|0.23|0.17|0.14|0.13|0.12|0.12|0.12|0.12|0.11|0.11|0.12|0.11|0.11|0.11|0.12|0.12|0.12|0.12|0.12|\n\n**4. Best perplexity for other decoding schemes:** Here are the numbers for the average best perplexity for other schemes in case of three drafts. However, we want to add that perplexity is a tricky thing to rely on alone because lower perplexity does not always indicate better coherence (Holtzman et al., ICLR 2020).\n|   | Best Perplexity |\n|--|-|\n| **Superposed Decoding** | 4.63   |\n| **Beam Search**  | 2.87  |\n| **Nucleus Sampling** | 3.47  |\n\n**5. Impact of n-gram filtering:** Thank you for raising this point. Below we show perplexity evaluation without n-gram filtering. At a high-level, one can think of n-gram filtering to be reducing the ambiguity in decomposing a superposed representation and denoising the process. Without this step, while the first draft will be more or less greedy, the other drafts will have significantly worse quality to the detriment of users.\n| Superposed Decoding | Draft 1 | Draft 2 | Draft 3 | Best |\n|-|-|-|-|-|\n| **PPL w/o filtering**| 4.54| 18.33| 18.61| 4.06 |\n| **PPL with filtering**  | 5.03| 7.97| 10.05| 4.63 |\n\nBelow, we also show n-gram filtering applied on nucleus sampling. We experiment with several beta values for how heavily n-gram filtering is weighted and evaluate using perplexity. From the experiments, n-gram filtering does not provide significant benefits to nucleus sampling but also does not diminish the performance of nucleus sampling either.\n| Beta (n-gram weight) |0| 0.01 | 0.05 |0.1|0.2|0.4| 0.6| 0.8|\n|-|--|---|--|-|-|-|-|-|\n| **Nucleus Sampling** | 5.17 | 5.18 | 5.26 | 5.16 | 5.24 | 5.16 | 5.15 | 5.11 |\n\nWe hope that this rebuttal answers any questions you have and solidifies your positive outlook on the paper. We would love to discuss more if you need any further clarifications.\n\nRef:\nOlah et al July 2024: https://transformer-circuits.pub/2024/july-update/index.html", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "G9OzsBiwlK", "reviewer": "Reviewer_E6Fn", "summary": "This paper proposed a novel decoding algorithm to generate k coherent drafts in one autoregressive inference pass. An additional n-grams model is used to keep the k-drafts coherent. Experimental results show that this method can generate three relatively coherent drafts while achieving a speed-up ratio of more than 2.44.", "questions": "1. See weakness 1.\n2. How often does this method generate incoherent or erroneous drafts?", "limitations": "The n-grams model is constructed by open-source texts, which containing toxic data that may affect the safety of the model. This factor should be taken into consideration.", "rating": 4, "confidence": 4, "soundness": 1, "presentation": 3, "contribution": 2, "strengths": "1. This paper is well written.\n2. Comprehensive experiments are conducted to evaluate the performance of the proposed method.", "weaknesses": "1. This paper proposed Superposed Decoding, which aims to generate k different sequences in a single inference of the LM.\nIt uses a superposition to approximately represent the last tokens of k drafts in each decoding step. However, it seems that this goal can be easily achieved by adopting tree attention masks [1] without the proposed superposition. For example, given a prefix [x1,x2,...,xn], we can greedy sample k tokens in the output distribution to initialize k different drafts. Next, we concatenate these k tokens with the prefix. Here, the current sequence has n+k tokens. The position id is [1,2,....,n]+[n+1]*k. We produce the corresponding tree attention mask to keep the k drafts independent. If we just want to complete these k drafts, we can input these k tokens in parallel and perform greedy sampling on each of them in each step. This generation also only costs one decoding process. (Let L be the max length of the k drafts; the whole generation process takes L decoding steps.) However, the k drafts are exactly the same as those generated separately.\nIn contrast, the proposed method loses precision. What is the strength of Superposed Decoding compared to the approach above?\n\nReference：\n[1] Li Y, Wei F, Zhang C, et al. Eagle: Speculative sampling requires rethinking feature uncertainty[J]. arXiv preprint arXiv:2401.15077, 2024.\n\n2. The coherence of the generated drafts depends on the quality of the n-grams model. Meanwhile, the introduction of additional n-gram models limits the convenience of this approach.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are glad that the reviewer found the paper to be well written and are happy to hear that the reviewer appreciated the experiments. Below are the clarifications requested in the review:\n\n**1. Comparison to tree attention masks:** While this paper is interesting and relevant, we do not believe it is a replacement for Superposed Decoding. It is true that tree masking will reduce KV cache size compared to vanilla drafting techniques because the prefix is stored only once. However, there are still _additional storage costs_ from storing every generated token in memory (Cai et al., ICML 2024), which Superposed Decoding does not need to do. These costs are present regardless of batching and can reduce effective batch size (i.e. number of prefixes that can be handled at once). This is further accentuated when the initial prefix length is small compared to the generation length, leading the generated tokens to dominate the overall storage requirement. Furthermore, every additional token that must be stored and processed means less efficiency from a FLOPs perspective. Superposed Decoding does not have any of these limitations because it combines multiple drafts into a single superposed LM input. In addition, Superposed Decoding is _completely complementary_ to Tree Attention because some drafted tokens can be superposed to save memory, only requiring slight adjustment to the tree attention mask. We are happy to discuss further on this. \n\n**2. Dependence on n-gram models:** We respectfully disagree that n-gram models limit the convenience of Superposed Decoding. Data stores and non-parametric modeling are widespread in language models (ACL 2023 Tutorial on Retrieval-based Language Models and Applications). For example, “Nonparametric Masked Language Modeling” establishes the use of an external corpus of two billion tokens for masked language generation (Min et al., ACL 2023). Similarly, large text corpuses are essential for document retrieval and RAG applications (Karpukhin et al., EMNLP 2020; Shi et al., NAACL 2024). N-gram models have also proven to be powerful in machine translation settings (Branst et al., ACL 2007). Finally, with the advances like Infinigram (Liu et al., COLM 2024), n-gram datastores are easy to access and scale up as part of language modeling. \n\n**3. Incoherent and erroneous drafts:** Thank you for this question. While incoherency is an important metric, there are currently no good ways to measure at scale without using proxies like perplexity, which we show in the paper. In practice, we rarely see any incoherent drafts, as highlighted by strong human evaluation performance. Erroneous drafts are a different problem because they are also tied to factuality – which is typically helped by non-parametric modeling and data stores similar to what we do with n-gram filtering.\n\n**4. Toxicity:** The risk of toxicity can be significantly reduced by building n-gram models on clean data stores created by domain experts. Furthermore, n-gram models are frequently used in personalized scenarios. In such cases, the relevant data stores are often pre-filtered to be appropriate for a user or specific task.\n\nWe hope that this rebuttal clarifies your concerns, and we are happy to discuss any further clarifications to increase the score and facilitate acceptance of the paper.", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "rsEK1xvEIz", "reviewer": "Reviewer_ZGM9", "summary": "The paper \"Superposed Decoding: Multiple Generations from a Single Autoregressive Inference Pass\" introduces a method to generate \nk similar responses in parallel using a single forward pass in autoregressive models.", "questions": "see weakness", "limitations": "na", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The paper validates its method on two open-source LLMs, providing empirical evidence of its applicability.", "weaknesses": "1. Limited Problem Scope and Optimization Potential:\n\nThe problem addressed might not have significant optimization potential. Using sampling and batch construction during inference can prevent an increase in latency. Autoregressive decoding is often memory-bounded, so the batch inference will not be a big burden for latency. It is unclear if the authors have considered batch construction for the vanilla method when measuring latency.\n\n2. Restricted Scenario and Lack of Strong Justification:\n\nThe scenario studied is highly restricted, and the authors do not provide compelling evidence that the proposed method yields superior results for n-decoding. Specifically, the top-1 result obtained using the proposed method performs worse than vanilla decoding.\n\n3. Complexity and Additional Dependencies:\n\nThe proposed method appears inelegant, relying on an additional n-gram language model to calibrate the outputs of the LLM. This dependency detracts from the method's appeal and does not demonstrate a clear advantage over batch inference.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "In the following we provide clarifications that were requested: \n\n**1. Limited scope and restricted scenarios:** We respectfully disagree with the reviewer about the limited scope and scenarios of Superposed Decoding. Short text generation and drafting are common real-world problems and a centerpiece to products such as GitHub Copilot and Tabnine. Features like Gmail SmartCompose, Word auto-suggestions, and iPhone auto-completions also rely on providing multiple suggestions.\n\n**2. Optimization potential:** We agree with the reviewer that batch construction helps with latency and that autoregressive decoding is often memory bound. However, solely using batch construction for multiple drafts reduces effective batch size by a factor of $k$ (i.e. number of prefixes that can be handled at once). On the other hand, Superposed Decoding is agnostic to these challenges and _complementary to batch construction_. Superposed Decoding helps generate $k$ drafts for every decoding run, _effectively multiplying the batch size of any decoding scheme_ like nucleus sampling. This avoids the limitations imposed by vanilla batching, benefiting scenarios where batch size is a limitation, such as server-based applications like Github Copilot or Tabnine.\nAn interesting way to think about Superposed Decoding is as a way to execute local searches while each nucleus sampling draft would be a global search. One can always combine both ideas and benefit from increasing the effective number of generated drafts. We are happy to discuss this further.\n\n**3. Lack of strong justification:** It is true that the top-1 result from Superposed Decoding is slightly outperformed by vanilla decoding in some metrics. However, these differences are small: 0.04% on TriviaQA and 0.33% on Natural Questions. In addition, Superposed Decoding is primarily meant for *multiple draft scenarios*, where it can significantly outperform the other decoding methods without *increasing compute* (Figure 5, Figure 7). In the case where the goal is just a single generation, then vanilla decoding (or any other sampling method) can be used at no detriment by simply toggling off n-gram filtering.\n\n**4. Complexity and dependence on n-gram models:** We respectfully disagree that n-gram models limit the convenience of Superposed Decoding. Data stores and non-parametric modeling are widespread in language models (ACL 2023 Tutorial on Retrieval-based Language Models and Applications). For example, “Nonparametric Masked Language Modeling” establishes the use of an external corpus of two billion tokens for masked language generation (Min et al., ACL 2023). Similarly, large text corpuses are essential for document retrieval and RAG applications (Karpukhin et al., EMNLP 2020; Shi et al., NAACL 2024). N-gram models have also proven to be powerful in machine translation settings (Branst et al., ACL 2007). Finally, with the advances like Infinigram (Liu et al., COLM 2024), n-gram datastores are easy to access and scale up as part of language modeling.\n\nWe hope that this rebuttal addresses your concerns and we are happy to discuss further if you need any further clarifications to increase the score and facilitate acceptance of the paper.", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "mPU88iUWmr", "reviewer": "Reviewer_Lot4", "summary": "This paper introduces Superposed Decoding, a novel method to generate multiple drafts (k drafts) in a single inference pass. The process involves two iterative steps: (1) running a large language model (LLM) inference on fused tokens and utilizing top-k sampling to produce k candidate tokens, and (2) combining n-gram probability scores with LLM probability scores to extend each draft with one candidate token, iteratively. This method demonstrates significant improvements in generation perplexity, downstream task performance, and is favored by human annotators, delivering results 2.44 times faster. The authors also suggest a resetting mechanism to mitigate repetitions in long drafts.", "questions": "- In Section 5.2, the authors indicate that shorter generations lead to higher diversity as shown by Self-BLEU. How does this diversity change in other decoding methods? Do these methods exhibit similar diversity patterns as Superposed Decoding?\n\nOverall, I lean towards accepting this work. The weaknesses and questions are primarily around clarifications rather than flaws in the method. If the authors address these questions and provide the necessary clarifications, I am inclined to raise my score.", "limitations": "The authors acknowledge and provide reasonable limitations:\n\n- The quality of Superposed Decoding largely depends on the n-gram models used, which are vital for maintaining coherence.\n- While the drafts produced are syntactically diverse, they may lack semantic diversity.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The method is intelligent and innovative, addressing a task that, while not highly popular, has numerous practical applications and significant real-world relevance.\n- The experiments are well-designed, covering text generation, question answering, and human evaluation, showcasing the method's effectiveness in both quality and efficiency.", "weaknesses": "- The current application is restricted to text drafting and does not extend to code generation, which could also benefit from this method and is frequently used in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive review. We are glad that the reviewer found the approach innovative and experiments well designed. Following are the clarifications requested in the review:\n\n**1. Code generation:** We agree with the reviewer and mention in the manuscript that code generation is yet another important step use case. However, in this paper we focus on language generation to showcase the generality of the method and hope to extend it to code generation in the future. \n\n**2. Diversity of other decoding schemes for short generations:** We run additional experiments generating three drafts using Beam Search and Nucleus Sampling and calculate the diversity of drafts using Self-BLEU. We find that while beam search, like Superposed Decoding, becomes more diverse at shorter generation lengths, the opposite is true with Nucleus Sampling. We attribute this to the fact that Beam Search, like Superposed Decoding, produces syntactically different but semantically alike drafts. This means that as generation length increases, more tokens are generally in common between drafts. On the other hand, Nucleus Sampling’s probabilistic nature results in semantically different drafts. Consequently, longer generation lengths lead to a higher proportion of token-level differences.\n\n_Diversity as measured by Self-BLEU_\n| Generation Length        | 5    | 10   | 15   | 20   |\n|---------|------|------|------|------|\n| **Superposed Decoding** | 0.51 | 0.81 | 0.88 | 0.91 |\n| **Beam**   | 0.35 | 0.64 | 0.75 | 0.81 |\n| **Nucleus** | 0.33 | 0.25 | 0.21 | 0.19 |\n\nWe hope that this rebuttal solidifies your positive outlook on the paper and we are happy to discuss if you need any further clarifications to increase the score and facilitate acceptance of the paper.", "claims_and_evidence": "", "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": "", "extra_scores": {}}]

Author rebuttal:
First, we would like to thank all reviewers for their feedback. We would also like to express sincere appreciation to the AC, SAC, and PCs for the time they have put into the current review cycle. We want to reiterate that Superposed Decoding is a novel algorithm leveraging an interesting phenomenon of representational superposition in LLMs towards generating multiple drafts in a single autoregressive inference pass and is complementary to other decoding methods and efficiency improvements.

In the rebuttal PDF, we include a figure on linearity by layer in Llama-2-7B through five timesteps in case it may be of use to the reviewers.

We address the rest of the questions and comments the reviewers had in their respective rebuttals.

Meta-review: The paper presents a novel method for generating multiple coherent text drafts from a single forward pass of an autoregressive model, named Superposed Decoding. The method leverages the approximate linearity of large language models (LLMs) to superpose embeddings of different sequences and decode them in parallel. The paper includes comprehensive experiments demonstrating the method's effectiveness in improving generation perplexity, downstream task performance, and human preference, all while reducing computation time. The concept of Superposed Decoding is novel and has the potential to significantly impact text generation tasks by providing multiple drafts efficiently. The effectiveness of Superposed Decoding relies heavily on the quality of the n-gram models, which could be a point of failure. Most reviewers recognize the novelty of this paper after thorough discussions and I think this paper could be a good contribution to the community.
Decision: Accept (poster)