Edit Flows: Variable Length Discrete Flow Matching with Sequence-Level Edit Operations
Marton Havasi, Brian Karrer, Itai Gat, Ricky T. Q. Chen
Autoregressive generative models naturally generate variable-length sequences, while non-autoregressive models struggle, often imposing rigid, token-wise structures. We propose Edit Flows, a non-autoregressive model that overcomes these limitations by defining a discrete flow over sequences through edit operations—insertions, deletions, and substitutions. By modeling these operations within a Continuous-time Markov Chain over the sequence space, Edit Flows enable flexible, position-relative generation that aligns more closely with the structure of sequence data. Our training method sidesteps intractable computations by leveraging an expanded state space with auxiliary variables, making the learning process efficient and tractable. Empirical results show that Edit Flows outperform baselines on image captioning tasks and significantly improve upon prior non-autoregressive models in code and text generation.