# Accelerating Toeplitz Neural Network with Constant-time Inference Complexity

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 25 references that are in the map.
- First posted on arXiv 15 Nov 2023.

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

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Swin Transformer: Hierarchical Vision Transformer using Shifted Windows](https://mlsanity.com/paper/2103.14030/) (2021)
- [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (2020)
- [Conformer: Convolution-augmented Transformer for Speech Recognition](https://mlsanity.com/paper/2005.08100/) (2020)
- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [MetaFormer Is Actually What You Need for Vision](https://mlsanity.com/paper/2111.11418/) (2021)
- [Diagonal State Spaces are as Effective as Structured State Spaces](https://mlsanity.com/paper/2203.14343/) (2022)
- [Transformer Transducer: A Streamable Speech Recognition Model with Transformer Encoders and RNN-T Loss](https://mlsanity.com/paper/2002.02562/) (2020)
- [Should You Mask 15% in Masked Language Modeling?](https://mlsanity.com/paper/2202.08005/) (2022)
- [What Makes Convolutional Models Great on Long Sequence Modeling?](https://mlsanity.com/paper/2210.09298/) (2022)
- [Toeplitz Neural Network for Sequence Modeling](https://mlsanity.com/paper/2305.04749/) (2023)
- [Neural Architecture Search on Efficient Transformers and Beyond](https://mlsanity.com/paper/2207.13955/) (2022)

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

- [Log-Linear Attention](https://mlsanity.com/paper/2506.04761/) (2025)
- [Scaling Laws for Linear Complexity Language Models](https://mlsanity.com/paper/2406.16690/) (2024)
- [You Only Scan Once: Efficient Multi-dimension Sequential Modeling with LightNet](https://mlsanity.com/paper/2405.21022/) (2024)
- [Linear Attention Sequence Parallelism](https://mlsanity.com/paper/2404.02882/) (2024)
- [Unlocking the Secrets of Linear Complexity Sequence Model from A Unified Perspective](https://mlsanity.com/paper/2405.17383/) (2024)
- [Structured Recurrent Mixers for Massively Parallelized Sequence Generation](https://mlsanity.com/paper/2605.08696/) (2026)

## Abstract (arXiv)

Toeplitz Neural Networks (TNNs) have exhibited outstanding performance in various sequence modeling tasks. They outperform commonly used Transformer-based models while benefiting from log-linear space-time complexities. On the other hand, State Space Models (SSMs) achieve lower performance than TNNs in language modeling but offer the advantage of constant inference complexity. In this paper, we aim to combine the strengths of TNNs and SSMs by converting TNNs to SSMs during inference, thereby enabling TNNs to achieve the same constant inference complexities as SSMs. To accomplish this, we formulate the conversion process as an optimization problem and provide a closed-form solution. We demonstrate how to transform the target equation into a Vandermonde linear system problem, which can be efficiently solved using the Discrete Fourier Transform (DFT). Notably, our method requires no training and maintains numerical stability. It can be also applied to any LongConv-based model. To assess its effectiveness, we conduct extensive experiments on language modeling tasks across various settings. Additionally, we compare our method to other gradient-descent solutions, highlighting the superior numerical stability of our approach. The source code is available at https://github.com/OpenNLPLab/ETSC-Exact-Toeplitz-to-SSM-Conversion.