Research map / Architectures and efficiency / Attention and transformers
Flash Inference: Near Linear Time Inference for Long Convolution Sequence Models and Beyond
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Flash Inference, a tiled relaxed-polynomial-interpolation scheme that makes exact autoregressive inference for long convolution sequence models (Hyena) run in O(L log^2 L), with across-layer parallelism.
Problem
Autoregressive inference for long convolution sequence models (LCSMs) like Hyena remains quadratic in sequence length because the convolution filter must be applied to incrementally revealed inputs, unlike the FFT-based training-time computation.
Approach
Applies van der Hoeven's relaxed polynomial interpolation via a fractal, power-of-two tiling of the contribution space, so each token's contributions are computed in FFT-sized blocks (O(L log^2 L) total) and tile work for different layers runs in parallel; generalizes to any associative, query-independent contribution-based mixer.
Key results
- Hybrid Flash Inference achieves up to 7.8x end-to-end speedup on Hyena inference over optimized baselines.
- The convolution (mixer) part is sped up by up to 110x relative to the lazy approach.
- Per-token cost is low-variance except at positions with large tiles, since 93.75% of tokens use tile size up to 8.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Flash Inference with Hybrid τ implementation instead of Lazy inference | Hyena · Hyena mixer, B=1, N=18, D=864, L=217 | mixer speedup over Lazy: 110.74 × | Helped |
| Use Flash Inference with Hybrid τ implementation instead of Lazy inference | Hyena · Hyena end-to-end inference | end-to-end speedup: up to 7.8× | Helped |
| Use Flash Inference with Hybrid τ implementation instead of Lazy inference | Hyena · Hyena end-to-end inference, B=4, D=768, 18 layers, L=215 | end-to-end speedup: 4.8× | Helped |
| Use the tiled approach instead of Eager or Lazy | Hyena mixer · Hyena mixer, B=4, D=768, 18 layers, L=215 | mixer speedup: 90× | Helped |
| Use the parallel-across-layers version instead of the non-parallel version (ablation) | Eager and Lazy inference · Hyena and synthetic inference | speedup: 10 −20% | Helped |
| Use the Hybrid τ implementation that dynamically selects an implementation by tile size instead of a fixed τ implementation (ablation) | Flash Inference · Synthetic inference | mixer time | Helped |
| Use Flash Conv1D instead of Eager or Lazy contribution computation (ablation) | Flash Inference · Synthetic inference | mixer time | Helped |
| Enable CUDA Graphs for token generation (ablation) | Flash Inference and its baselines · Hyena end-to-end inference | end-to-end speedup: up to 8×; 1.6× | Helped |
| Use the full Hybrid implementation rather than the FFT implementation (ablation) | Flash Inference · Synthetic inference | mixer time: less than 2% | Mixed |
| Use Hybrid instead of a fixed τ implementation (ablation) | Flash Inference · Synthetic inference | mixer time: close to 20% | Helped |
| Use parallel Lazy instead of non-parallel Lazy (ablation) | Lazy inference · Hyena and synthetic inference | speedup: 10% | Helped |
Surprising findings
- Without CUDA Graphs the end-to-end speedup is only about 1.6x because CPU dispatch overhead is exposed once the mixer becomes fast; CUDA Graphs raise it to up to 8x.
- Conv1D with a quadratic cost still gains over 5x from the tiling alone, due to better arithmetic intensity.
Limitations
- Proof-of-concept evaluated only with random-weight synthetic models and Hyena; no quality evaluation on real tasks.
- Current method requires data-independent filters for the efficient version; data-dependent filters cost a factor of 2 and are not yet causal in practice.
- Benefit diminishes when prompt prefill dominates total time.
Experimental setup
Metrics: end-to-end wall-clock time mixer time speedup over lazy baseline
Baselines: Lazy Eager Conv1D FFT FlashFFTConv
Builds on: Hyena relaxed polynomial interpolation (van der Hoeven 1997) FlashFFTConv Massaroli et al. 2024 (distilled LTI SSM inference)
Closest papers by meaning
- IceFormer: Accelerated Inference with Long-Sequence Transformers on CPUs (ICLR 2024 · similarity 0.89)
- FlashFFTConv: Efficient Convolutions for Long Sequences with Tensor Cores (ICLR 2024 · similarity 0.88)
- Linear Attention for Efficient Bidirectional Sequence Modeling (NeurIPS 2025 · similarity 0.86)
- SqueezeLLM: Dense-and-Sparse Quantization (ICML 2024 · similarity 0.86)
- Inference-Time Hyper-Scaling with KV Cache Compression (NeurIPS 2025 · similarity 0.86)
- Megalodon: Efficient LLM Pretraining and Inference with Unlimited Context Length (NeurIPS 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.