FutureFill: Fast Generation from Convolutional Sequence Models

We thank the reviewer for the review and appreciation of the strengths of the paper. Regarding the point of demonstrating practical speedups we refer the reviewer to the general response to put our contribution in the right light as well as the additional experiments we have provided in the Appendix (Section A) in the revised paper. We believe these experiments are close to a practical setting in language modelling and we do indeed see a significant improvement of our method. We answer the specific questions here –

• In our newly provided set of experiments we fully detail the operations measured. They now represent a fully formed two layer language model with STU convolutional layers. We note that the task in our newly uploaded experiments is widely used, i.e. decoding of language models. The main variations one would find in real tasks here are changes of the model specific parameters like number of hidden dimensions, number of layers etc.

• In the new experiments, we have provided a large horizon on the number of tokens generated and we do indeed see significantly larger gains as well as get a sense of the trends and scaling.

Thank you for your questions!

1. The results in Figures 5 and 6 are from averaging the timing experiments over 16 trials. The shaded regions represent + or - 1.96 times the standard deviation of the timing measurements for each method and number of decoding tokens (ie 95% confidence intervals). In our experiments, only for the naive decoding method is the variation noticeable enough to be seen on the graph, though this detail may be different with pre-compilation or hardware acceleration.
2. In order to add the continuous futurefill experiments, between the initial submission and the revision we switched the setup to use a numpy implementation instead of a jax one (which originally was implemented with a jax.lax.scan loop). There are extra considerations for a jax implementation of continuous futurefill (such as bottoming out the recursion to avoid creating kernels of all sizes, as mentioned to another reviewer) that made it more straightforward to do the timing in basic numpy. This difference in implementation leads to differences in the exact runtimes and the constant factors (and the difference at 1e5 steps you observe), but has the same asymptotic behaviors. We should have specified this difference in the revised version, we apologize. Thank you for pointing it out!

We remark that because these are unoptimized implementations for illustrative purposes, the exact times for particular decoding lengths in figures 5 and 6 are probably not exactly what would be seen when deploying our methods in serious applications. However, (as demonstrated in Appendix A) optimized implementations on accelerated hardware will also have immediate benefit over the naive decoding. The algorithmic advantage our methods provide is clear, present in both synthetic and accelerated settings, and improves with scale (which is what we set out to prove in this paper) — any airtight implementation (such as what would be developed for an industry application, for example) would likely require low-level design decisions specific to the application. For universality and clear presentation, we opted for simplicity over complicated optimality in our experiments. We hope this answers your questions and provides some context for our experimental choices!

We thank the reviewer for their review. We refer the reviewer to our general response regarding further comparisons. We disagree with the reviewer on the point of Limited Novelty and Contribution. Computing convolutions in an online fashion (such as the one during sequence inference) is a fundamental problem and no general improvement was known beforehand. Our method provides such an improvement. We believe this is a fundamental algorithmic improvement to a fundamental problem with a potential for wide-ranging impact. We respectfully disagree with the following comment by the reviewer

The major improvement for Algorithm1 compared with [1] appears to be the change of convolutional caches, and the improvement in asymptotic time from $O(L(\log⁡L+K)+K^2)$ to $O(Llog⁡L+K^2)$ is not significant.

It is absolutely clear in the setting that this result is reported i.e. $K << L$, $K \cdot L$ would be the dominant term in the known implementation and removing this term is clearly a significant improvement as acknowledged by other reviewers. If the reviewer typically considers the setting $K \sim L$ then as clearly stated in the paper they would use the second algorithm which would give them a complexity of $(K+L)\sqrt{(K+L)}$ which is also a clear and significant improvement over $(K+L)^2$ (the best known).

We thank the reviewer for their comments. We request the reviewer to also read the General Response provided by us to all reviewers for more context on comparisons and real-world applicability of our method. In the following we respond to other questions raised by the reviewer.

• Inference Efficiency and Comparison with Approximate Methods:

While comparisons to token pruning, cache compression, and sparse attention mechanisms are valuable, we believe they are outside the scope of this paper. These are methods to approximate the full attention model with performance vs. speed tradeoffs, while we focus on an exact inference method for convolutional sequence models without quality loss. In our view, comparing with these methods requires understanding and defining the acceptable quality loss inherent in approximate attention models. Many of these methods involve trade-offs between speed and accuracy, often with parameters adjusted on a case-by-case basis. Given this, a fair comparison is difficult to make without a clear understanding of the quality loss in these approximations. As such, we consider it premature to make these comparisons in the current context.

As an example, consider the evaluation style in the Laughing Hyena paper (NeurIPS 2023), which contrasts the approximate Hyena model with the base Hyena model in terms of inference speed and approximation loss. Like us, they do not compare their method against sparse attention models. It is crucial to note that our method does not need to rely on providing trade-offs—our approach provides exact computations but at a significantly faster inference speed, with no need to introduce any approximation or quality loss.

• Applicability to GPUs Without Optimized FFT Support:

Regarding the use of GPUs without optimized FFT support, we acknowledge the ongoing efforts to improve FFT performance on GPUs, including recent works such as Flash FFT Convolution (https://arxiv.org/abs/2311.05908) and earlier studies (https://arxiv.org/abs/2302.06646). These works demonstrate that FFT-based convolutional methods now outperform traditional attention mechanisms on GPUs due to their faster computational complexity. We would like to draw the reviewers’ attention to Table 6 in Flash FFT Convolution paper ((https://arxiv.org/abs/2311.05908)) and Figure 1 in the Laughing Hyena paper (https://arxiv.org/abs/2310.18780), which show that FFT-based convolution methods significantly outperform attention in GPU settings. Moreover, in token generation tasks starting from a prompt, our method can directly leverage these GPU-optimized algorithms, as a single FFT call produces all the necessary prefil cache information for our approach, further boosting performance.

• Our apologies regarding the margin issue. We will fix and correct this.

We thank the reviewer for their review. Regarding further comparisons we would like to refer the reviewer to the central response where we cover many of the questions raised by the reviewer. Regarding the point of GPU validation a similar point was raised by another reviewer which we repeat here –

• Applicability to GPUs:

Regarding the use of GPUs without optimized FFT support, we acknowledge the ongoing efforts to improve FFT performance on GPUs, including recent works such as Flash FFT Convolution (https://arxiv.org/abs/2311.05908) and earlier studies (https://arxiv.org/abs/2302.06646). These works demonstrate that FFT-based convolutional methods now outperform traditional attention mechanisms on GPUs due to their faster computational complexity. We would like to draw the reviewers’ attention to Table 6 in Flash FFT Convolution paper ((https://arxiv.org/abs/2311.05908)) and Figure 1 in the Laughing Hyena paper (https://arxiv.org/abs/2310.18780), which show that FFT-based convolution methods significantly outperform attention in GPU settings.

In our practice we have found even a simple implementation of Bailey’s FFT (https://en.wikipedia.org/wiki/Bailey%27s_FFT_algorithm) which leverages simple matrix multiplications is already sufficient to be used in our experiments on GPUs/TPUs and provides the benefits reported in our experiments. We note that our newly uploaded experiments are on a Google TPUv2 and indeed written in a way to leverage accelerators for all the compared models.

• Other concerns:

In the first setting of generation with prompt, the assumption that K is usually less than L is only applicable for a subset of tasks such as summarization.

Please note that we have provided two algorithms – one dealing with the setting of prompt + generation wherein we make the assumption of $K < L$. Furthermore we also provide an algorithm wherein we provide an algorithm for continuous auto-regressive generation. In the setting where $K > L$ we would apply the latter algorithm and the generation complexity per token would be $O(\sqrt(K + L))$ which is an improvement over the naive algorithm of $O(K+L)$.

The algorithms improve the complexity of convolutions, but models usually have several other components like projections, gating, MLPs, etc. 2a. It would be valuable to gauge the contribution of each of these components to final inference times. 2b. How different parameters like the number of layers, hidden dimension size, scaling with sequence lengths, batch size, etc affect the performance of the proposed algorithms.

Upon the reviewer’s requests in the updated version (Section A in the appendix) we have provided a comparison of the various models with a 2-layer set up with projections, feed-forward layers etc to get a sense of the contribution to inference times of those components. We would like to note (and as can be seen in the experiment provided) that scaling with sequence length (i.e. the number of generated tokens) is in our favor as the other components contribute a constant amount in terms of runtime per generated token. As the sequence length scales the effect of these constants vanish and our algorithm’s improvement in terms of sequence length shines. We would like to note that the performance will naturally scale in our favor as the number of layers or hidden model dimensions increases as there are more convolutions performed in the network in more dimensions. These parameters naturally scale the runtime linearly for every model involved. We have provided all experiment details for the reader in section A.1.