Superposed Decoding: Multiple Generations from a Single Autoregressive Inference Pass

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.

Strengths

- The method is intelligent and innovative, addressing a task that, while not highly popular, has numerous practical applications and significant real-world relevance. - 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.

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.

Rating

7

Confidence

3

Soundness

4

Presentation

3

Contribution

3

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.

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.

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

see weakness

Rating

4

Confidence

4

Soundness

2

Presentation

3

Contribution

2

Limitations

na

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.

Strengths

1. This paper is well written. 2. 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. 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

1. See weakness 1. 2. How often does this method generate incoherent or erroneous drafts?

Rating

4

Confidence

4

Soundness

1

Presentation

3

Contribution

2

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.

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.

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

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?

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

No societal impact needs to be addressed for this work.