# FutureFill: Fast Generation from Convolutional Sequence Models

arXiv: https://arxiv.org/abs/2410.03766 · HTML: https://mlsanity.com/paper/2410.03766/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 33 references that are in the map.
- First posted on arXiv 2 Oct 2024.

## Builds on (most cited first, 29 of 29)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Mamba: Linear-Time Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2312.00752/) (2023)
- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning](https://mlsanity.com/paper/2307.08691/) (2023)
- [Efficiently Modeling Long Sequences with Structured State Spaces](https://mlsanity.com/paper/2111.00396/) (2021)
- [GLU Variants Improve Transformer](https://mlsanity.com/paper/2002.05202/) (2020)
- [Train Short, Test Long: Attention with Linear Biases Enables Input Length Extrapolation](https://mlsanity.com/paper/2108.12409/) (2021)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Simplified State Space Layers for Sequence Modeling](https://mlsanity.com/paper/2208.04933/) (2022)
- [Combining Recurrent, Convolutional, and Continuous-time Models with Linear State-Space Layers](https://mlsanity.com/paper/2110.13985/) (2021)
- [HiPPO: Recurrent Memory with Optimal Polynomial Projections](https://mlsanity.com/paper/2008.07669/) (2020)
- [KVQuant: Towards 10 Million Context Length LLM Inference with KV Cache Quantization](https://mlsanity.com/paper/2401.18079/) (2024)
- [Hungry Hungry Hippos: Towards Language Modeling with State Space Models](https://mlsanity.com/paper/2212.14052/) (2022)
- [Resurrecting Recurrent Neural Networks for Long Sequences](https://mlsanity.com/paper/2303.06349/) (2023)
- [Hyena Hierarchy: Towards Larger Convolutional Language Models](https://mlsanity.com/paper/2302.10866/) (2023)
- [Diagonal State Spaces are as Effective as Structured State Spaces](https://mlsanity.com/paper/2203.14343/) (2022)
- [Long Range Language Modeling via Gated State Spaces](https://mlsanity.com/paper/2206.13947/) (2022)
- [What Makes Convolutional Models Great on Long Sequence Modeling?](https://mlsanity.com/paper/2210.09298/) (2022)
- [KV Cache is 1 Bit Per Channel: Efficient Large Language Model Inference with Coupled Quantization](https://mlsanity.com/paper/2405.03917/) (2024)
- [Monarch Mixer: A Simple Sub-Quadratic GEMM-Based Architecture](https://mlsanity.com/paper/2310.12109/) (2023)
- [Simple Hardware-Efficient Long Convolutions for Sequence Modeling](https://mlsanity.com/paper/2302.06646/) (2023)
- [Learning Linear Dynamical Systems via Spectral Filtering](https://mlsanity.com/paper/1711.00946/) (2017)
- [Spectral Filtering for General Linear Dynamical Systems](https://mlsanity.com/paper/1802.03981/) (2018)
- [Laughing Hyena Distillery: Extracting Compact Recurrences From Convolutions](https://mlsanity.com/paper/2310.18780/) (2023)
- [Spectral State Space Models](https://mlsanity.com/paper/2312.06837/) (2023)
- [Sequence Modeling with Multiresolution Convolutional Memory](https://mlsanity.com/paper/2305.01638/) (2023)
- [Flash STU: Fast Spectral Transform Units](https://mlsanity.com/paper/2409.10489/) (2024)

## Built on by (most cited first, 7 of 7)

- [Universal Sequence Preconditioning](https://mlsanity.com/paper/2502.06545/) (2025)
- [Flash Inference: Near Linear Time Inference for Long Convolution Sequence Models and Beyond](https://mlsanity.com/paper/2410.12982/) (2024)
- [A New Approach to Controlling Linear Dynamical Systems](https://mlsanity.com/paper/2504.03952/) (2025)
- [Spectral Filtering for Complex Linear Dynamical Systems](https://mlsanity.com/paper/2601.22400/) (2026)
- [SpectraLDS: Provable Distillation for Linear Dynamical Systems](https://mlsanity.com/paper/2505.17868/) (2025)
- [Efficient Spectral Control of Partially Observed Linear Dynamical Systems](https://mlsanity.com/paper/2505.20943/) (2025)
- [Online Control via Counterfactual Tracking](https://mlsanity.com/paper/2607.13029/) (2026)

## Abstract (arXiv)

We address the challenge of efficient auto-regressive generation in sequence prediction models by introducing FutureFill, a general-purpose fast generation method for any sequence prediction algorithm based on convolutional operators. FutureFill reduces generation time from quadratic to quasilinear in the context length. Moreover, when generating from a prompt, it requires a prefill cache whose size grows only with the number of tokens to be generated, often much smaller than the caches required by standard convolutional or attention based models. We validate our theoretical claims with experiments on synthetic tasks and demonstrate substantial efficiency gains when generating from a deep convolutional sequence prediction model.