# Imputer: Sequence Modelling via Imputation and Dynamic Programming

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

## Key facts

- Cited by 66 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Feb 2020.

## Built on by (most cited first, 30 of 66)

- [Structured Denoising Diffusion Models in Discrete State-Spaces](https://mlsanity.com/paper/2107.03006/) (2021)
- [Continuous diffusion for categorical data](https://mlsanity.com/paper/2211.15089/) (2022)
- [Instances as Queries](https://mlsanity.com/paper/2105.01928/) (2021)
- [Learning to Efficiently Sample from Diffusion Probabilistic Models](https://mlsanity.com/paper/2106.03802/) (2021)
- [End-to-End Speech Recognition: A Survey](https://mlsanity.com/paper/2303.03329/) (2023)
- [Step-unrolled Denoising Autoencoders for Text Generation](https://mlsanity.com/paper/2112.06749/) (2021)
- [Intermediate Loss Regularization for CTC-based Speech Recognition](https://mlsanity.com/paper/2102.03216/) (2021)
- [SpeechStew: Simply Mix All Available Speech Recognition Data to Train One Large Neural Network](https://mlsanity.com/paper/2104.02133/) (2021)
- [Unleashing Transformers: Parallel Token Prediction with Discrete Absorbing Diffusion for Fast High-Resolution Image Generation from Vector-Quantized Codes](https://mlsanity.com/paper/2111.12701/) (2021)
- [A Survey on Non-Autoregressive Generation for Neural Machine Translation and Beyond](https://mlsanity.com/paper/2204.09269/) (2022)
- [Relaxing the Conditional Independence Assumption of CTC-based ASR by Conditioning on Intermediate Predictions](https://mlsanity.com/paper/2104.02724/) (2021)
- [Edit Flows: Flow Matching with Edit Operations](https://mlsanity.com/paper/2506.09018/) (2025)
- [PIMNet: A Parallel, Iterative and Mimicking Network for Scene Text Recognition](https://mlsanity.com/paper/2109.04145/) (2021)
- [Non-Autoregressive Translation with Layer-Wise Prediction and Deep Supervision](https://mlsanity.com/paper/2110.07515/) (2021)
- [A Comparative Study on Non-Autoregressive Modelings for Speech-to-Text Generation](https://mlsanity.com/paper/2110.05249/) (2021)
- [CTC Alignments Improve Autoregressive Translation](https://mlsanity.com/paper/2210.05200/) (2022)
- [Investigating the Reordering Capability in CTC-based Non-Autoregressive End-to-End Speech Translation](https://mlsanity.com/paper/2105.04840/) (2021)
- [Beyond In-Place Corruption: Insertion and Deletion In Denoising Probabilistic Models](https://mlsanity.com/paper/2107.07675/) (2021)
- [An Imitation Learning Curriculum for Text Editing with Non-Autoregressive Models](https://mlsanity.com/paper/2203.09486/) (2022)
- [Pushing the Limits of Non-Autoregressive Speech Recognition](https://mlsanity.com/paper/2104.03416/) (2021)
- [Improving CTC-based speech recognition via knowledge transferring from pre-trained language models](https://mlsanity.com/paper/2203.03582/) (2022)
- [Layer Pruning on Demand with Intermediate CTC](https://mlsanity.com/paper/2106.09216/) (2021)
- [Deliberation of Streaming RNN-Transducer by Non-autoregressive Decoding](https://mlsanity.com/paper/2112.11442/) (2021)
- [Learning Non-Autoregressive Models from Search for Unsupervised Sentence Summarization](https://mlsanity.com/paper/2205.14521/) (2022)
- [IPAD: Iterative, Parallel, and Diffusion-based Network for Scene Text Recognition](https://mlsanity.com/paper/2312.11923/) (2023)
- [Streaming End-to-End ASR based on Blockwise Non-Autoregressive Models](https://mlsanity.com/paper/2107.09428/) (2021)
- [BERT Meets CTC: New Formulation of End-to-End Speech Recognition with Pre-trained Masked Language Model](https://mlsanity.com/paper/2210.16663/) (2022)
- [Non-autoregressive End-to-end Speech Translation with Parallel Autoregressive Rescoring](https://mlsanity.com/paper/2109.04411/) (2021)
- [LegoNN: Building Modular Encoder-Decoder Models](https://mlsanity.com/paper/2206.03318/) (2022)
- [CTC-based Non-autoregressive Speech Translation](https://mlsanity.com/paper/2305.17358/) (2023)

## Abstract (arXiv)

This paper presents the Imputer, a neural sequence model that generates output sequences iteratively via imputations. The Imputer is an iterative generative model, requiring only a constant number of generation steps independent of the number of input or output tokens. The Imputer can be trained to approximately marginalize over all possible alignments between the input and output sequences, and all possible generation orders. We present a tractable dynamic programming training algorithm, which yields a lower bound on the log marginal likelihood. When applied to end-to-end speech recognition, the Imputer outperforms prior non-autoregressive models and achieves competitive results to autoregressive models. On LibriSpeech test-other, the Imputer achieves 11.1 WER, outperforming CTC at 13.0 WER and seq2seq at 12.5 WER.