FutureFill: Fast Generation from Convolutional Sequence Models
sequence modeling;online learning;fast inference
Yes
No ethics review needed.
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.
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.
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.
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.
Yes
No ethics review needed.
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.
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.
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.
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.
Yes
No ethics review needed.
- 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?
- 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.
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.
- 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
Yes
No ethics review needed.
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.
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.
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.
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.
@inproceedings{
anonymous2024futurefill,
title={FutureFill: Fast Generation from Convolutional Sequence Models},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=kTIKlSzPTL},
note={under review}
}
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.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
sequence modeling online learning fast inference
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/ca61cca1c33f65aefbd79d4dc855e6966d78cb24.pdf
foundation or frontier models, including LLMs
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
FutureFill: Fast Generation from Convolutional Sequence Models
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission