Superposed Decoding: Multiple Generations from a Single Autoregressive Inference Pass

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:

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.

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.

Diversity as measured by Self-BLEU

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

Thank you for your response and the support for the acceptance of the paper.

In the following we provide clarifications that were requested:

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.

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

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.

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.

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

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

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):

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

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

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:

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

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

Numbers 0-20 in the table represent timesteps.

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.

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.

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

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.

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

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

Ref: Olah et al July 2024: https://transformer-circuits.pub/2024/july-update/index.html

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.

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:

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.

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.

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.

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.

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

We wanted to check in to see if our rebuttal resolved your concerns. We are happy to discuss further.

We thank the reviewer for agreeing to raise their score, and we are glad that our rebuttal resolved the concerns you had.