Superposed Decoding: Multiple Generations from a Single Autoregressive Inference Pass

Authors: ethan  shen
alan  fan
sarah  pratt
jae sung park
⋄  matthew
sham  kakade
ari  holtzman
ranjay  krishna
ali  farhadi
aditya  kusupati
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-12 21:27:02

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.

Main paper: 
 introduction: 
 Commercial surveys find that 80% of e-commerce websites provide autocomplete as a 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 a plausible sequence of next tokens for a given prefix [40] . The next token generated depends on the prefix and the previously generated tokens. Decoding algorithms like Greedy Decoding, Top-k Sampling [12] , Beam Search, and Nucleus Sampling [18] present various ways of obtaining generations during autoregressive inference. For a 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 Figure 1 : To generate multiple k auto-complete suggestions for a prefix using an LM, the existing decoding methods like Nucleus Sampling need k 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 is Beam Search, which picks the most probable k beams from the k 2 possible drafts at every timestep. Alternatively, Nucleus Sampling [18] , particularly effective at generating natural-sounding 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 k most recent drafted tokens (Section 3.1). After selecting the top-k output tokens, SPD expands the existing k drafts with them, resulting in k 2 potential new drafts. Each draft has a probability score assigned to it, which is further smoothed using a combination of various n-gram models (n ∈ [2, 6] ) [38, 25] . 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 is computationally inexpensive and allows flexibility to change domains of interest during inference (eg., programming, healthcare, finance, etc.). Superposed Decoding's effectiveness 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 ≥ 1 drafts that are as coherent, in terms of perplexity, as Nucleus Sampling (Section 4.1). However, SPD achieves this with a single inference pass, making it at least 2.44× faster than any other standard decoding methods for k ≥ 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 are as preferred as Nucleus Sampling in direct comparison (1v1) while 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).Superposed Decoding can help improve user experience by offering significant computational efficiency 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 as diverse in suggestion as Nucleus Sampling (Section 5). 
related work: 
 Decoding algorithms determine how tokens are selected from a language model's next token distribution. 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 Θ(|V| T ), where V is the vocabulary size and T the total number of timesteps. A practical compromise is 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 its drawbacks.Alternatively, Nucleus Sampling and Top-k Sampling decode probabilistically. To avoid degeneration, Top-k Sampling truncates the probability mass to the k 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 of inference passes in these decoding methods. Multi-token prediction [14, 36] addresses this by pre-training an LM having n independent softmax heads that predict n future tokens in parallel. When using multi-token prediction with speculative decoding, exact inference is 3× faster. In a 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 a 2.2× reduction in inference latency while maintaining generation quality. However, multi-token prediction requires re-training and Medusa requires additional fine-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 to other decoding methods like Medusa and multi-token prediction, as well as efficiency techniques like speculative decoding [30, 26, 6] , quantization [10, 32, 19] , pruning [13, 39, 28] , and architectural optimizations [37, 2, 1, 43, 27, 11] . 
superposed decoding (spd): 
 Given a text input as a prefix, Superposed Decoding uses an autoregressive LM f θ to produce k viable completion drafts in one inference pass.First Timestep. Let x denote a generated token in the vocabulary V and M = (x 1 , . . . , x m ) 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 + 1 is:p θ (x m+1 |x 1 , . . . x m ) = p θ (x m+1 |M ).For the first timestep, each of the k drafts is initialized as the prefix so we use the same next token distribution for all drafts. We grow draft d i by greedily selecting the i th most probable token, making:d i = (M, x i m+1 )where x i t is the token at timestep t for the i th draft. We also track each draft's probability p i as its score, which is initially the probability of its first token p θ (x i m+1 |M ). Consequently, the set of drafts D after the first timestep is:EQUATIONNext Timesteps. As the input to the LM at timestep t, we construct xt-1 , which is a superposition (weighted linear combination) of the embeddings for the most recent token x t-1 of the k drafts. This means that xm+1 , the input to the LM at the second timestep m + 2, is the superposition of the tokens x i m+1 for i = 1, . . . , k. We use this superposed embedding as a single and accurate approximation for the most recent token across all k drafts at the (t -1) th timestep. We run autoregressive inference over xt once for all k drafts instead of the usual once per draft, allowing us to formulate inference as: p θ (x t |M, xm+1 , . . . , xt-1 ) Because each draft contains its own contextual clues and syntax, we cannot blindly use the distribution of x t for each draft. Instead, we interpolate the superposed distribution p θ (x t |M, xm+1:t-1 ) with a draft-specific next token distribution from an n-gram model to get a final distribution p f (x i t |M, x m+1:t-1 ) that is unique to each draft. Next, we rank the draft options by the joint probability of their respective previous draft p i and their selected token. We choose the top k options as drafts for the next timestep and update their probabilities. This gives:D =    (M, x 1 m+1 , . . . , x 1 t ) . . . (M, x k m+1 , . . . , x k t )    with probabilities P =    p θ (x 1 m+1 |M ) t s=m+2 p f (x 1 s |M, x 1 m+1:s-1 ) . . . p θ (x k m+1 |M ) t s=m+2 p f (x k s |M, x k m+1:s-1 )   (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.During training, language models learn a representation (token embedding) z ∈ R d for every token x ∈ V. We leverage this representation at timestep t to construct xt , weighing the representation forx i t-1 by a coefficient γ i . xt = k i=1 γ i • z i t-1whereEQUATIONThe performance of xt is highly dependent on choosing the appropriate weight for each embedding z i t-1 . We find that the best strategy is to set γ i to the normalized probability of draft i such thatEQUATIONwhere p i is the probability of the i th draft, introduced in Section 3. This allows us to directly tie the weight of a token to the likelihood that it will be preserved in future timesteps, reducing drift between the superposed embeddings and the drafts they represent.We construct each draft's n-gram distribution p ngram (x i t |M, x i m+1 , . . . , x i t-1 ) by interpolatively smoothing the next token distributions over a set of n-gram models using weights λ, where n ∈ [2, 6] .EQUATIONWe base our interpolation weights on weights for RedPajama found by Liu et 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 the exponential mean of p θ and p ngram as our final distribution p f , where α is a hyperparameter controlling the impact of the n-gram distribution:EQUATIONThis 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 calculateEQUATIONwithout interpolation, where δ is a penalty term that disincentivizes selecting an uninterpolated draft for the next timestep. This approach is the backbone of Superposed Decoding (Equation 2) and allows us to create context-aware next-token distributions for each draft with only one inference pass.Superposed Decoding relies on the ability of the underlying model to preserve the linear relationship between xt and its component vectorsz i t-1 [23]. More formally, if xt is the input to the LM f θ , then f θ (x t ) = k i=1 γ i • f θ (z i t-1) should also be true (γ i defaults to draft probability in SPD). As long as this holds, the combination of a superposed embedding and n-gram smoothing should allow us 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 {x} 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 of the three tokens into a model using Superposed Decoding . Finally, we measure the alignment between f θ (x t ) andk i=1 γ i • f θ (z i t-1) using cosine similarity cos(a, b) as:EQUATIONWe compute the cosine similarities for ten randomly sampled batches of ten prefixes each from the OpenWebText 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 is imperfect, and Superposed Decoding and Beam Search eventually diverge over time. Owing to this, we identify 10 timesteps as the optimal generation length. We also show how linearity changes through the layers within each timestep in 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 3). We also conduct a user study highlighting that users prefer Superposed Decoding over Nucleus Sampling in a compute-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 in Appendix G.1.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-70B on eight A40 GPUs. We assume a batch size of one for all experiments.For n-gram interpolation, we construct 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 = 2 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).We test generation quality on OpenWebText'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 a 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 α 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 a 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, at 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. 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 N u c l e u s P @ 1 B e a m P @ 1 G r e e d y P @ 1 S P D P @ 1 S P D P @ 2 S P D P @ 3 0 10 TriviaQA N u c l e u s P @ 1 B e a m P @ 1 G r e e d y P @ 1 S P D P @ 1 S P D P @ 2 S P D P @ 3 0 5 Natural QuestionsFigure 5 : Superposed Decoding is as accurate as Greedy Decoding for P@1 and increases the fact-based coverage using multiple drafts (P@2,3) on TriviaQA (left) and Natural Questions (right).use 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@1 in a zero-shot setting, with three drafts providing accuracy 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 a factually correct generation in addition to one that is coherent.Superposed Decoding presents a significant theoretical reduction in latency, but it is important to investigate how well this translates to the real-world. In Figure 6 , we show that dictionary lookups are the only additional cost incurred by Superposed Decoding, barring which Superposed Decoding has near-constant compute cost. Even so, the total cost of Superposed Decoding is significantly lower than other decoding methods, with Superposed Decoding 2.44× faster on three drafts and 3.54× 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 n-gram models are implemented using single-threaded lookup on Python dictionaries, and we do not cache any lookup results. This has an enormous, visible impact. In addition, Liu et al. [31] propose the use of suffix arrays for n-gram models, allowing a near-instantaneous lookup of arbitrary-length n-grams in trillion-token corpora. These techniques open up multiple avenues for additional speedup. While perplexity and factuality are good proxies for textual quality, real human evaluation remains the best measure of coherency. Indeed, perplexity is an imperfect evaluator of long-form language modelling [44] while factuality metrics are inherently biased towards Greedy Decoding methods [41] . Consequently, to verify our findings, we conduct a 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 OpenWebText test set, truncating to the first 15 tokens as in 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 a compute-normalized setting, randomizing their order. Finally, we filter out prefixes with duplicate or unparseable generations (e.g. emojis). After preprocessing, 707 prefixes are left.It is important to note that one Nucleus Sampling generation is 20% less expensive than three Superposed 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 is closest to equal compute, but also conduct smaller surveys in 2v3 and 1v1 settings.Results. We define a Superposed Decoding "win" as when one of the Superposed Decoding drafts is ranked first. As shown in Figure 7 , we find that Superposed Decoding generations are preferred approximately 63.6% of the time . If every Superposed Decoding draft was consistently the same quality as 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 a diversity that is highly valuable to users.We run the two smaller-scale iterations of the study with 100 prefixes each. In the 2v3 setting, we ask users to rank two nucleus drafts and three superposed drafts to investigate whether the benefits of Superposed Decoding persist even when compute favors Nucleus Sampling. In the 1v1 setting, users choose between one 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.6% and 51.4% of the time respectively. While the surveys have higher variance due to their small size, they cement Superposed Decoding as a strong alternative to Nucleus Sampling. We show details on the additional studies in Appendix F.1 and present our survey page in Figure 13 .Superposed Decoding also provides significant benefits for inference time compute scaling. Superposed Decoding is completely complimentary to other decoding methods, expanding semantic coverage at no extra compute. For instance, if Nucleus Sampling is used to generate n drafts, Superposed Decoding with k drafts can be spliced in at any timestep to strategically produce nk drafts This property is valuable for repeated sampling [3] , a technique where the number of generations is scaled at inference time to 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 (N S SP D ) produces even larger coverage gains. In Table 2 , we compare the coverage of vanilla Nucleus Sampling and N S SP D in an equal compute setting up to 100 Nucleus Sampling drafts. We find that N S SP D results in higher coverage across the board on both TriviaQA [24] and Natural Questions [29] , highlighting Superposed Decoding as a powerful method to increase the impact of scaling inference compute.5 Further Analysis and Ablations 
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.Next, we extensively investigate the diversity and repetition of Superposed Decoding in order to better understand its properties.Repetition within Generations. Repetition is a 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 as well. To measure repetition, we calculate the proportion of unique unigrams, bigrams, and trigrams in each generation. The lower the uniqueness, the higher the repetition. In Figure 8 , we 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 in Section 5.3.Diversity across Drafts. To measure diversity, we apply Self-BLEU [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 -1 drafts as references. Hence, a low Self-BLEU signifies high diversity, while a high Self-BLEU suggests low diversity. After calculating Self-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. To reduce long-form repetition in Superposed Decoding, we propose resetting superposed tokens every s timesteps, where s is a user-selected hyperparameter. On each reset step we sample one of the k drafts and restart draft generation. Resetting helps Superposed Decoding escape repetitive loops while reestablishing linearity, which Figure 3 shows to deteriorate over time. This is similar to a user selecting one of the k drafts while typing. We find that resetting noticeably improves long-form generation quality (examples in Appendix I) and leave further investigation for future 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 is robust to all three hyperparameters, with lower perplexity than Nucleus Sampling in nearly all settings tested. 
discussion and conclusion: 
 While we demonstrate that Superposed Decoding is an effective technique for multiple draft generation, Superposed Decoding is limited by the quality of the n-gram models used, which are essential for maintaining coherence. In addition, while Superposed Decoding drafts are syntactically diverse, they are 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, we believe that orthogonality is promising and is a logical next step for future work. We also note that mechanisms, like batching, that increase throughput of decoding algorithms are complementary to Superposed Decoding.In conclusion, we present Superposed Decoding, a novel decoding method that superposes token embeddings to generate multiple short generations at 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 on common benchmarks and expands coverage at scale. We envision that the latency reduction from Superposed Decoding will make it practical to apply large pre-trained language models on 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.A Superposed Decoding Pseudo-Code Algorithm 1 Superposed Decoding algorithm generating k drafts.1: Input: Prefix M = (x 1 , . . . , x m ), generation length G 2: Initialize t ← m + 1 3: Initialize D ← {M } k ▷ Draft store 4: while t ̸ = m + G do 5: if t = m + 1 then ▷ First timestep 6: p θ ← f θ (M ) 7:for i = 1 to k do 8:x i m+1 ← Largest(p θ , i) ▷ Take the i th most probable token 9:D i ← {D i ∪ x i m+1 } 10:end for 11:xm+1 ← Superpose(x 1 m+1 , . . . , x k m+1 ) ▷ Superpose the selected tokens for i = 1 to k do 16:p ngram ← N-Gram(D i ) ▷ Calculate the n-gram distribution of draft i 17: p f ← Interpolate(p θ , p ngram ) 18:for xt ← Superpose(x x i t ∈ p f do 19: D tmp ← {D i ∪ x i t } ▷ Create new 
 
 Appendix: α and τ . We find that the best performing hyperparameters for coherent generation on 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 n = 2 to n = 6.We evaluate perplexity for Superposed Decoding on the OpenWebText test split by interpolating only n-grams from n = 2 to n = 4, requiring only 2.64 GB of storage. We use the same n-gram interpolation weights as in Section 3 but retune α and τ to 0.55 and 0.1 respectively. In Table 4 , we show that the perplexity of the average best generation is almost identical to the average Nucleus Sampling perplexity. This demonstrates that Superposed Decoding can be effectively implemented with minimal storage overhead in storage-constrained devices like smartphones.We calculate the standard deviations across the 5000 OpenWebText prefixes used for evaluation for Llama-2-7B and Mistral 7B and show them below in Tables 5 and 6 . We note that Superposed Decoding has higher standard deviation than Nucleus Sampling and Beam Search when implemented We show a screenshot of our study page in Figure 13 . We compensate workers at an approximate rate of $15 per hour.In Figure 14 , we show 12 additional example generations comparing Superposed Decoding and Nucleus Sampling in a compute-normalized setting. Prefixes are sampled from OpenWebText and truncated to the first 15 tokens, and each generated completion is 10 tokens in length.In Figure 15 , we show an example generation that outputs three drafts using Nucleus Sampling for several timesteps, followed by Superposed Decoding with k = 3. This results in nine total drafts at 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.In Figure 16 , we show the cosine similarity between superposed embeddings {x} 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.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 is also shown, is qualitatively still the best performing decoding method in long form settings.Sydney architect Rana Abboud won a 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 to advance their careers. Rana Abboud, a graduate of the University of Sydney, is the founder of Rana Abboud & Associates. "I am honoured to be awarded this scholarship. I am passionate about design built for people and the environment. I am excited to be able to further my studies and continue to develop my skills and knowledge," she said. The NAWIC Scholarship is awarded to women who are studying or working in the construction industry. "The NAWIC Scholarship is a great opportunity for women to further their care and Superposed Decoding without Resetting Sydney architect Rana Abboud won a 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 to pursue careers in the construction industry. The 2017 scholarship recipients are: Rana Abboud, a student at the University of New South Wales, who is studying a Bachelor of Architecture. Megan Brennan, a 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, a student at the University of New South Wales, who is studying a Bachelor of Construction Management. Kate Foster, a student at the University of New South Wales, who Nucleus Sampling Sydney architect Rana Abboud won a NAWIC Scholarship of $1000 for 'Significant Contribution to Career Growth'. Sydney architect Rana Abboud has won the National Association of Women in Construction (NAWIC) NSW/ACT Scholarship for 2017 for 'Significant Contribution to Career Growth'. She has also just been accepted to undertake a Master of Science in Architecture with Higher Degree by Research at Sydney University. The scholarship is one of eight awards presented by NAWIC to women to further their studies in the construction industry in Australia. "As a working mother, I am very grateful for the support I am receiving to further my professional and academic development," Abboud said. Rana Abboud (middle) with associates (L-R) Tara Abdul-Khalek and Aditi Rana. Abboud is a director of Pal Architecture in Alexandria,As part of a broad initiative to combat sexual harassment and assault, the University of California, Berkeley, has launched a new website that provides information about the university's policies and procedures for reporting and responding to sexual harassment and sexual violence. The website, which is available at http://sexualharassment.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 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 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.As part of a broad initiative to combat sexual harassment and misconduct on campus, a task force consisting of faculty, staff, students, and other members of the campus community will present a draft report with recommendations at the Board of Trustees meeting on Friday, October Order the completions in decreasing order such that the preferred one is at the top. Note that "\n" denotes a line break. 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. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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?

There'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.

Also, some relevant work in this direction are worth mentioning:

Elhage, Nelson, et al. "Toy models of superposition." arXiv preprint arXiv:2209.10652 (2022).
Cheung, Brian, et al. "Superposition of many models into one." Advances in neural information processing systems 32 (2019).
questions: 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.

For 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.

How 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: limitations: No societal impact needs to be addressed for this work.
paper_summary: paper_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.
strength_weakness: strength_weakness: 1. This paper proposed Superposed Decoding, which aims to generate k different sequences in a single inference of the LM.
It 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.
In contrast, the proposed method loses precision. What is the strength of Superposed Decoding compared to the approach above?

Reference：
[1] Li Y, Wei F, Zhang C, et al. Eagle: Speculative sampling requires rethinking feature uncertainty[J]. arXiv preprint arXiv:2401.15077, 2024.

2. 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.
questions: questions: 1. See weakness 1.
2. How often does this method generate incoherent or erroneous drafts?
limitations: 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.
paper_summary: paper_summary: The paper "Superposed Decoding: Multiple Generations from a Single Autoregressive Inference Pass" introduces a method to generate 
k similar responses in parallel using a single forward pass in autoregressive models.
strength_weakness: strength_weakness: 1. Limited Problem Scope and Optimization Potential:

The 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.

2. Restricted Scenario and Lack of Strong Justification:

The 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.

3. Complexity and Additional Dependencies:

The 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.
questions: questions: see weakness
limitations: limitations: na
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.
questions: 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?

Overall, 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: limitations: The authors acknowledge and provide reasonable limitations:

- The quality of Superposed Decoding largely depends on the n-gram models used, which are vital for maintaining coherence.
- While the drafts produced are syntactically diverse, they may lack semantic diversity.

Comments: comment: Before the discussion period ends, we were wondering if the reviewer could update their score to reflect the score change? Apologies for the repeated comments.
Thank you for your response and the support for the acceptance of the paper.
We thank the reviewer for raising their score. We would like to reiterate several points that highlight the benefits of Superposed Decoding and local mode coverage:

- In human evaluation experiments (Figure 7 in the paper), Superposed Decoding’s ability to provide multiple drafts results in generations preferred over Nucleus Sampling (**63% to 37%**). This can considerably benefit user experience in applications such as Github Copilot, Tabnine, Word Auto-Complete, and more.

- Alone, Superposed Decoding’s local coverage (three drafts) increases accuracy by **8%** in TriviaQA and **5%** in Natural Questions compared to one Nucleus Sampling generation at the same compute (Figure 5), highlighting significantly better factuality.

- Superposed Decoding added to Nucleus Sampling uses local coverage to expand Nucleus Sampling’s global modes, generating more factual outputs at scale than Nucleus Sampling alone without increasing compute cost for 1-100 inputs. This results in consistent accuracy gains up to **3%** as shown [here](https://openreview.net/forum?id=KSOkkHm9I7&noteId=DGv4vjS6rr).

We believe Superposed Decoding is an interesting phenomenon that adds value to the community, benefits users, and provides significant accuracy boosts. We are happy to answer any further questions.
Thanks for the authors' response. After carefully reading the response and the reviews from other reviewers, I would like to keep the score unchanged and recommend acceptance.
We thank the reviewer for agreeing to raise their score, and we are glad that our rebuttal resolved the concerns you had.
Thanks for the explanations. I will raise my score to 5.
The rebuttal partially solved my concern, but I still feel not sure about the importance of coverage of local modes. I raised the score and still welcome the authors to give further justification.
As we mentioned earlier in the rebuttal (and see Modes of Data in [here](https://openreview.net/forum?id=KSOkkHm9I7&noteId=T6Le0oX7hh)), SPD enables local search that helps improve the coverage of generations at no additional cost. For example, one nucleus sampled generation can be expanded by $k=3$ times using Superposed Decoding without increasing the compute. We do not claim that three SPD drafts are as good as three Nucleus Sampling drafts, but only that they are better than only one nucleus sampled draft, as shown in our paper’s experiments. This is a fair comparison because three nucleus sampled drafts will cost three times the compute as three Superposed drafts. 

Extending this further to the experiment above, we want to show that Superposed Decoding helps cover many modes of data. Using Nucleus Sampling as the scaffold (which can span the global space) and then generating many more drafts for the same compute cost using Superposed Decoding shows the practicality and complementary nature of SPD. Generating 3x or 100x drafts with SPD will not make a difference after a point (similar to Nucleus Sampling after 20-50 drafts despite linearly increasing compute) as accuracy saturates around a local minima. In this case, SPD helps Nucleus Sampling do a better local search (than just itself) to hit the right mode of the data to accurately answer a given question. This is shown by an asymptotic increase of accuracy/precision by roughly $3$% on both TriviaQA and Natural Questions. 

Do let us know if you have further questions. In short, we present Superposed Decoding as a novel alternative that generates multiple drafts for the same compute cost as a single draft while increasing the coverage for both factuality and user preferences.
Why do you use this setting instead of just use only SPD?
Following are the requested clarifications:

**1. Evaluation Metric:** We use precision as our metric. In addition, we follow the main body of [1] (Sections 2 and 3) and assume an ideal scenario where the best sample can always be identified. While [1] does suggest the usage of other verification methods, the paper’s experiments are primarily conducted assuming an ideal scenario.

**2. Notation:** $c$ is the number of timesteps that are generated with Nucleus Sampling before Superposed Decoding is applied to create drafts. $n$ is the total number of timesteps. For example, in TriviaQA, $c = 4$ and $n = 10$. For Natural Questions, $c = 9$ and $n = 15$. These values are held constant.
In the table, $NS_{SPD2}$ and $NS_{SPD3}$ denote whether two or three drafts are generated after $c$ timesteps.

Please let us know if anything is still unclear and thanks for extremely prompt responses. 

[1] Large Language Monkeys: Scaling Inference Compute with Repeated Sampling, arxiv
Please respond to my question as soon as possible to clear up any misunderstanding I have about your rebuttal.
And what is $c$? I do not see $c$ in the table, is it $SPD_{c}$?
Thanks for your reply. What is the evaluation metric for this table?

Do you have an external reward model to perform best-of-n or do you use self-consistency?
Yes, this is exactly correct. Without denoising, it is very difficult to get multiple coherent outputs from the superposed representations. 

Another way of thinking of the n-gram models is that they help ground the token distributions in reality to correct for noise in the top-k tokens.
>  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,

Yes, that is what I meant. Thank you for following up on this.

> 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.

If I understand this point correctly, you're referring to the softmax() of the representation when it maps to output tokens is a highly non-linear operation? And the denoising with an n-gram model is meant to repair this issue to some degree?
We wanted to check in to see if our rebuttal resolved your concerns. We are happy to discuss further.
We ran experiments from [1] and found that **Superposed Decoding significantly improves accuracy with no additional compute**, demonstrating its practicality. On TriviaQA and Natural Questions, **combining Nucleus Sampling and Superposed Decoding results in better performance** than vanilla Nucleus Sampling across the board.

TriviaQA (the three rows in each column use the same compute):

| Compute ($k$) | 1         | 10        | 20        | 30        | 40        | 50        | 60        | 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 |
| $NS_{SPD2}$   |     51.30 |     68.75 |     70.57 |     72.66 |     74.74 |     75.78 |     76.30 |     76.82 |     78.39 |     79.17 |     79.43 |
| $NS_{SPD3}$  | **51.82** | **70.57** | **74.22** | **75.52** | **77.34** | **77.87** | **78.39** | **78.65** | **79.17** | **79.43** | **79.95** |

Natural Questions (the three rows in each column use the same compute):

| Compute ($k$) | 1         | 10        | 20        | 30        | 40        | 50        | 60        | 70        | 80        | 90        | 100       |
|---------------|-----------|-----------|-----------|-----------|-----------|-----------|-----------|-----------|-----------|-----------|-----------|
| $NS$          |     14.32 | **32.55** | **36.98** |     38.54 |     40.36 |     41.15 |     41.67 |     41.93 |     42.19 |     42.71 |     42.97 |
| $NS_{SPD2}$   |     15.36 |     31.25 |     34.90 |     38.02 |     39.84 |     41.41 |     41.67 |     42.45 |     43.75 |     43.75 |     43.75 |
| $NS_{SPD3}$   | **15.63** |     31.25 | **36.98** | **39.06** | **41.15** | **42.71** | **43.75** | **43.75** | **44.27** | **44.79** | **45.57** |

Experimental Setup ($NS$: Nucleus Sampling; $SPD$: Superposed Decoding): 
- We evaluate three decoding strategies on Llama-2-7B:
   - Vanilla Nucleus Sampling for $n$ timesteps ($NS$).
   - Nucleus Sampling for $c$ timesteps then two SPD drafts for $n-c$ timesteps ($NS_{SPD2}$).
   - Nucleus Sampling for $c$ timesteps then three SPD drafts for $n-c$ timesteps ($NS_{SPD3}$).
- We compare accuracy on 1-100 inputs in a constant compute setting. This means the performance of the first $k$ $NS$ samples is compared against the first $2k$ $NS_{SPD2}$ samples and $3k$ $NS_{SPD3}$ samples, where $k \leq 100$.
- In the tables above, each column denotes results given the same compute. We show accuracy at intervals of 10 for $k$. We average results over three runs for each strategy.

We hope that these experiments resolve your concerns about Superposed Decoding’s practicality. We would also like to know if our earlier responses addressed your concerns about our method’s optimization potential, justification, and use of n-gram models.

[1] Large Language Monkeys: Scaling Inference Compute with Repeated Sampling, arxiv
Can you add more experiments like [1].

[1] Large Language Monkeys: Scaling Inference Compute with Repeated Sampling, arxiv

If cannot, I still do not think the proposed method has a clear practical usage.
We thank the reviewer for their prompt reply. Here are our thoughts.

**1. Nonparametric LMs:** We respectfully disagree that previous non-parametric LM research is unrelated to our method. In the context of language models, non-parametric language models are defined as language models whose data distribution is “a function of the available data,” with complexity growing with data (Siegel, 1957; Hollander et al., 2013; Min et al., 2023). We believe that this definition well-encapsulates a language model interpolated with n-gram models. Indeed, we see similar use cases in kNN-LM (Khandelwal et al., 2020) and NPM (Min et al., 2023), which use external datastores that behave like n-gram models - *the sole difference is that they are queried with a representation vector instead of a token sequence.* 

Superposed Decoding also can rely on representation vectors for retrieval from a datastore rather than directly doing a dictionary lookup during n-gram filtering. The former is “semantic” while the latter is “syntactic”.

**2. Modes of data:** Yes, the reviewer is right about Superposed Decoding potentially being unable to cover significantly different modes of the data like top-p sampling. However, this is not a concern nor a bug. The goal of Superposed Decoding is to provide multiple drafts at constant compute to help increase coverage. This coverage aids in improving user experience and factuality as shown in the experiments. As we mention, Superposed Decoding is intended for local exploration. More often than not, the greedy top-1 generation solves the problem at hand; further enabling local search and multiple drafts around it supports quite a few use cases. 

Having said that, Superposed Decoding can be combined with any sampling method, be top-p or something else, and it can help generate a local set of drafts for each sampling trajectory at no additional compute cost. For instance, if top-p sampling is used to generate $n$ drafts, Superposed Decoding with $k$ local drafts can be spliced in at any timestep to strategically produce $nk$ drafts, where each top-p trajectory is bolstered by $k$ local explorations at no extra cost. We include a sample generation below, using Superposed Decoding to produce three local drafts for each top-p sample; this expands the available options without extra compute or reducing mode coverage. 

*SPD denotes Superposed Decoding.*
```
Example of Top-p Sampling w/Superposed Decoding:
│  Prefix: “Melbourne is”
│
└───Top-p: Melbourne is a great city, with
│   │   SPD: Melbourne is a great city, with a lot of things
│   │   SPD: Melbourne is a great city, with a lot to things
│   │   SPD: Melbourne is a great city, with a lot of history
│
└───Top-p: Melbourne is a city of many different
│   │   SPD: Melbourne is a city of many different cultures and relig
│   │   SPD: Melbourne is a city of many different cultures, relig
│   │   SPD: Melbourne is a city of many different cultures and languages
│
└───Top-p: Melbourne is the capital city of Victoria
│    │   SPD: Melbourne is the capital city of Victoria, Australia. It
│    │   SPD: Melbourne is the capital city of Victoria and Australia. It
│    │   SPD: Melbourne is the capital city of Victoria, Australia. The
```

Do let us know if we are missing something here, and we are happy to discuss further. Also, let us know if the concern about optimization potential was resolved through the rebuttal.
My major concern is still the n-gram LM, your rebuttal is about all the nonparametric LMs. However, we are discussing n-gram LM. And the evidence you gave like Branst et al., ACL 2007 is a very old setting. I am an expert in machine translation, and I think this evidence can not prove anything in the context of LLM.

And I'm very concerned that your method can only find some paraphrased sentences rather than covering different modes of the data like top-p sampling. The self-bleu also validated my concern.

Can you add more experiments like [1].

[1] Large Language Monkeys: Scaling Inference Compute with Repeated Sampling, arxiv