FutureFill: Fast Generation from Convolutional Sequence Models

Authors: Naman Agarwal, Xinyi Chen, Evan Dogariu, Vladimir Feinberg, Daniel Suo, Peter Bartlett, Elad Hazan
Primary area: foundation or frontier models, including LLMs
Keywords: sequence modeling, online learning, fast inference

Abstract:
We address the challenge of efficient auto-regressive generation in sequence prediction models by introducing FutureFill—a method for fast generation that applies to any sequence prediction algorithm based on convolutional operators. Our approach reduces the generation time requirement from linear to square root relative to the context length. Additionally, FutureFill requires a prefill cache sized only by the number of tokens generated, which is smaller than the cache requirements for standard convolutional and attention-based models. We validate our theoretical findings with experimental evidence demonstrating correctness and efficiency gains in a synthetic generation task.

Decision: reject
Reviewer scores: 5, 5, 3, 5

Reviews and discussion:
<thread>
creation date:
1730589281903

thread_type:
official_review

<thread_object>
creator: reviewer_rafq

<content>
summary:
The paper introduces a new method to autoregressively generate tokens from a convolutional model, improving the number of flops required to generate K tokens, both from scratch and with a prompt of length L. The core idea is to use a precomputed cache to avoid repeated computation of the same quantities. The cache is also smaller than that of alternative approaches.

The theoretical analysis is confirmed with an synthetic empirical study.

strengths:
The algorithms are presented are simple and it’s clear how the required number of FLOPs is improved when using the algorithm. The improvement in the number of required FLOPs is significant. 

With a practical implementation showcasing speedups over standard autoregressive generation for convolution models, the algorithm could have a good impact on the community.

weaknesses:
The biggest weakness is that the authors don't show that the algorithm gives practical speedups on real tasks of interests, such as language modeling. 

Even if the algorithm is not giving improvements on practical tasks it would have been useful to understand why it does not work well in these settings, so someone else can more easily build on top on the work. 

The experimental section is also unclear in it's current form, as it's not stated what operation S(T) implements in detail. 

The novelty of Algorithm 1 is also limited.

questions:
What is S(T)? Is it just a convolution operation or a full convolutional layer?

Did you try the algorithm on any real tasks? 

In figure 4, the improvement over the naive algorithm to generate 5e5 tokens is less than 2x. Given the difference in the theoretical number of FLOPs I would have expected a larger difference. Why is this?

Can you expand the Figure 4 to generate a larger number of tokens so that the difference between the suggested approach and the naive approach is more clear.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730645620597

thread_type:
official_review

<thread_object>
creator: reviewer_sqi8

<content>
summary:
The paper proposed an acceleration method for convolutional models called FutureFill, which reduced the asymptotic computation time of convolution models to $O(K\sqrt{L\log L})$ and $O(L\log L +K^2)$ in two respective settings and reduced cache size to $O(K)$ for generation from scratch. The theoretical acceleration was verified by experimental results.

strengths:
- The proposed acceleration method reduces the generation time and cache size, which is said in the paper to be applicable to many types of convolutional models.

weaknesses:
- Limited evaluation. 
	- Unclear setting. The evaluation (section 4.2) is missing information on detailed model architecture, size, timed operators, distribution of L and K, or hardware details, making the results hard to interpret or reproduce.
	- Limited results. Only a few data points from a single model are plotted. It would be more solid to cover results for models mentioned to be applicable in section 2.1 in a realistic setting to verify the end-to-end speedup and saved cache memory.
	- Experimental results for Algorithm1 compared with previous methods are not included.

- Limited novelty and contribution. 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(L\log L +K^2)$ is not significant.

Minor:
- a typo in line 66. $K\sqrt{L}\log L \to K\sqrt{L\log L}$

---

References:

[1] Laughing Hyena Distillery: Extracting Compact Recurrences From Convolutions http://arxiv.org/abs/2310.18780

questions:
- Can you provide more details on the evaluation setting?

- Can you provide additional results on more models mentioned in section 2.1 with a setting closer to realistic deployment?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730651911789

thread_type:
official_review

<thread_object>
creator: reviewer_hm23

<content>
summary:
Proposes a future fill algorithm for prompt-based and online inference of convolutional-based sequence models. In the first setting, authors use FFT to precompute a cache to generate the next K tokens given L tokens. In the second setting, they generate from scratch and create partial caches, to construct the output at the end of each token iteration. In both settings, authors prove their claimed asymptotic bound reductions.

strengths:
This paper attempts to address a relevant problem involving reducing inference's quadratic complexity.

Neat setup of the mathematical framework and proof of reducing the asymptotic complexity of setting 1 to O(L L+ K^2 ) and second setting to  Ksquare_root( L log L) .

The application of these techniques to spectral filtering is explained well.

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

The experimental analysis is insufficient in terms of details like hardware used, implementation framework, proof of correct implementation, timing measurements, models used, time breakdown, memory analysis, input data sizes, among others.

questions:
1. Since GPUs are typically used for inference of LMs, showing the gains in end-to-end inference time and how well the reduced asymptotic complexity translates to real performance gains needs to be validated.

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

3. Experimental analysis would benefit from a deeper analysis and also presentation.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730707456706

thread_type:
official_review

<thread_object>
creator: reviewer_7b51

<content>
summary:
The paper proposes FutureFill, a fast generation method designed for convolutional sequence models, aiming to reduce generation time complexity from linear to square root relative to context length. FutureFill utilizes a prefill cache that is theoretically more efficient in both time and memory, requiring less storage than traditional convolutional and attention-based models. The authors validate their approach through theoretical analysis and experimental evaluation on synthetic generation tasks.

strengths:
1. FutureFill offers a novel approach to reducing the generation time for convolutional models from linear to square root relative to context length. This theoretical improvement addresses one of the core challenges of convolutional models, positioning FutureFill as a potentially valuable contribution to the field of efficient sequence generation. 
2. By using a prefill cache that scales with the number of generated tokens rather than the full context, FutureFill significantly reduces memory overhead. This is particularly valuable in applications where memory is a bottleneck, making the method more accessible for deployment in resource-constrained environments.
3. FutureFill offers an alternative to attention-based models, which suffer from quadratic complexity, especially with longer sequences. By exploring a convolution-based approach, the paper contributes to the broader goal of overcoming the limitations of self-attention in handling long sequences.

weaknesses:
1. The paper relies heavily on synthetic tasks for evaluation, which may not fully represent real-world applications. Without testing FutureFill on more practical benchmarks or large-scale NLP tasks, it’s difficult to assess its true effectiveness and scalability.
2. While the authors emphasize efficiency improvements, they do not compare FutureFill against other advanced, optimized generation techniques. 
3. The authors focus mainly on theoretical comparisons with standard convolution and attention models. However, many recent techniques in sequence modeling—such as token pruning, cache compression, or sparse attention mechanisms—are entirely overlooked, which limits the relevance of FutureFill in the context of state-of-the-art sequence generation methods.

questions:
1. How does FutureFill perform on standard language modeling or machine translation benchmarks compared to other optimized sequence models? Including such comparisons would significantly strengthen the paper’s claims about practical applicability. 
2. The paper briefly mentions the complexity of benchmarking FutureFill on accelerated hardware, but how feasible is it to implement this method in practice? Given the reliance on FFT, how does FutureFill perform on GPUs without optimized FFT support? 
3. The magin formatting of this paper is changed, which may violate the requirement of ICLR.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732335910847

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Response

comment:
We thank the reviewers for their reviews and evaluation. Multiple reviewers have asked for further evaluations and have raised concerns regarding  the real-world  applicability of our method. In this general response we reiterate the broad ideas which form the basis for our method and clarify why we believe the applicability of our proposed method is in our opinion immediate. We have further conducted upon the reviewers’ requests a comparison between a fully setup multi-layer attention model, convolutional model (STU) with the naive convolution and our proposed method. We have uploaded  these new experiments in the updated paper on the system as the first section of the Appendix. We have also appended  an Experiment Details section with all the details of the experimental setup.

We would like to emphasize that our work presents a general method for exact computation in convolutional models during inference, achieving a per-token complexity of $O(\sqrt{L})$. This is a significant improvement over the previously best-known result of $O(L)$. Prior to our work, it was not clear whether such an improvement was even feasible. As the recent work on the Laughing-Hyena model (see https://arxiv.org/abs/2310.18780) demonstrates, convolutional models naively have the same scaling on inference times as attention, namely $O(L)$. To address this, they resorted to approximating the convolutional model through distillation to an RNN, which sacrifices accuracy for speed. We note that the loss incurred by such approximations is difficult to predict in future settings. Importantly, our paper completely eliminates the need for such approximations, providing an efficient and completely accurate alternative.

The improvement afforded by our method FutureFill, is immediately applicable to any large language model (LLM) based on convolutional architectures. We believe that the reduction in inference time during token generation  is immediate from the design of our method since it performs a subset of the computational operations performed by the naive implementation. Therefore, we consider it self-evident that our method outperforms the naive approach in terms of computational efficiency, even perhaps without the need for experimental validation. While we have added further verification to the paper upon the reviewers’ requests, we note that the exact improvement will vary across different models based on the other non-convolutional components present in the model. Nevertheless it is clear that every model based on convolutions should choose to employ this method as opposed to the naive algorithm as it comes with no loss and a potential for a large gain. 

We would like to remind the committee that the improvement we provide is a really fundamental improvement to the natural and widely applicable problem of inference from convolutional sequence models. This is unlike inference improvements through approximation in attention models which come at different costs. Our improvement in comparison is immediate and we believe should be promptly adopted in any convolutional model of which there are several variants being researched in the sequence prediction and modeling community. As a result we request the committee to view the result which we believe to be of immediate and wide impact in the research community in the appropriate  light.

We would further like to bring to the reviewing committee’s attention that in our updated manuscript, using a straightforward  application of FutureFill we have been able to improve the inference speed of our algorithm from $O(\sqrt{L}) \rightarrow O(\log^2(L))$, per token generated, i.e. nearly constant per token closely matching that of RNNs/SSMs. We call the originally proposed method EpochedFutureFill in the revision which achieves $O(\sqrt{L})$ and the new improvement ContinuousFutureFill which achieves $O(\log^2(L))$. We leave it up to the reviewing committee to decide whether to take this significant improvement into account during their evaluation. We are happy to provide further details in comments, should the reviewing committee ask for it.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732638780697

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
No engagement thus far

comment:
We thank the reviewing committee for their efforts on this paper. Unfortunately we have not heard back from any reviewer post our rebuttal. We have clarified several of the reviewer concerns, added new experiments and added a new significantly improved method. If there are lingering concerns we would appreciate it if the reviewers let us know so that we can clarify. We believe we have a general method that has wide and immediate applicability for anyone who is looking to build new architectures for LLMs via convolutions and we hope for more engagement from the reviewers for us to clarify any lingering concerns.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper proposes FutureFill, a fast generation method designed for convolutional sequence models. After rebuttal, it received scores of 3555. One major concern shared by all the reviewers still remains, that is, limited evaluation. In the original paper, the theoretical analysis is confirmed with only a synthetic empirical study. The proposed method is highly suggested to test on real tasks of interests, such as language modeling. During rebuttal, the authors added some new experiments. However, overall, it's still lightweight and insufficient to convince reviewers. Therefore, the AC would like to recommend rejection of the paper.