Control- DAG : Constrained Decoding for Non-Autoregressive Directed Acyclic T5 using Weighted Finite State Automata (2024)

Abstract: The Directed Acyclic Transformer is a fast non-autoregressive (NAR) model that performs well in Neural Machine Translation. Two issues prevent its application to general Natural Language Generation (NLG) tasks: frequent Out-Of-Vocabulary (OOV) errors and the inability to faithfully generate entity names. We introduce Control-DAG, a constrained decoding algorithm for our Directed Acyclic T5 (DA-T5) model which offers lexical, vocabulary and length control. We show that Control-DAG significantly enhances DA-T5 on the Schema Guided Dialogue and the DART datasets, establishing strong NAR results for Task-Oriented Dialogue and Data-to-Text NLG.

## introduction non-autoregressive (nar) models for text generation offer the promise of much faster generation than auto-regressive (ar) models. however nar models have been largely developed for neural machine translation (nmt) @xcite , with other natural language generation (nlg) tasks less well studied. we will show how a nar model developed for nmt, the directed acyclic transformer (dat) @xcite , can be used for generation in task-oriented dialogue (tod) and data-to-text (d2t) scenarios. dats as originally developed for nmt perform poorly in nlg on tod and d2t tasks: they fail to generate specified entity names in up to 40% of responses and frequently (>20%) produce out-of-vocabulary (oov) words. practical systems must operate at zero error rate in these aspects to be deployable at scale. previous nar study reported similar error patterns @xcite . unless these shortcomings are addressed, nar models will not be usable for general nlg. we introduce three constrained decoding procedures for nlg using dats. our approach converts directed acyclic graphs (dag) generated by dat into weighted finite state automata (wfsa). we then intersect these wfsas with other automata that are defined to ensure that designated entities (lexical constraints) are generated and oovs are eliminated (vocabulary constraints). to avoid generating responses that are too short, we employ a viterbi decoding algorithm to control the target length of the generated text (length constraints). we refer to the decoding procedure that incorporates all these steps as control-dag. we evaluate extensively on the schema guided dialogue (sgd) @xcite and the data record to text (dart) datasets @xcite for nlg in tod and d2t domains. our directed acyclic t5 model, when decoded with control-dag, is free from oov error, faithfully generates all specified entity names, and achieves marked bleu and bleurt gains on both datasets. we use pynini @xcite for wfsa operations. our contributions are summarized below: to our knowledge, da-t5 with control-dag is the first practical nar benchmark on the sgd and the dart datasets. foot_0 the directed acyclic transformer (dat) @xcite the length target predictor is a simple linear predictor based on the input sequence length (sec.4). 4. we intersect the wfsa with constraint fsas to obtain a constrained wfsa which only contains hypotheses that satisfy all lexical and vocabulary constraints. 5. dfs-viterbi is used to obtain the most likely string in the constrained wfsa that satisfies the length constraint. enforcing lexical constraints in auto-regressive decoding has been studied extensively. constrained beam search (cbs) @xcite @xcite ) is a widely used family of lexically constrained decoding procedure. we show how cbs can be adapted to nar directed acyclic models. ## constrained decoding with da-t5 the architecture of our da-t5 model follows that of the dat by @xcite . conceptually, dat takes an input sequence and generates a dag with a pre-determined number of dag vertices. vertex embeddings are produced first, and then token emission probabilities and state transition probabilities are generated from these vertex embeddings via softmax and self-attention, resp. each vertex has a token emission distribution. these vertices and transitions define a weighted dag that contains output string hypotheses. dat uses a vanilla transformer to produce vertex embeddings whereas we use t5, hence the name da-t5. in training da-t5, we use 'glancing training' @xcite as dat. in inference, dags are generated with da-t5 and converted to wfsas. the procedure is simply moore-to-mealy machine conversion (appendix b.1). prior to the conversion, we perform likelihood-based pruning of each vertex, keeping k e most likely output tokens and k t most likely out-going arcs. this pruning balances coverage against decoding speed, with larger thresholds leading to a more complete wfsa at the cost of slower decoding. ## experiments and results we evaluate on the sgd and the dart datasets. in sgd, the aim is to generate natural utterances from dialogue actions (e.g., inform(@xmath0. dart is a more general data-to-text task that takes triplets of (subject, relation, object) to generate natural texts. hyper-parameters and implementation details are in appendix a. ## conclusion we propose control-dag for decoding nonautoregressive directed acyclic models with lexical, vocabulary, and length constraints, addressing key limitations in nar text generation. constrained decoding is efficiently performed via wellstudied weighted finite state automata algorithms. da-t5 with control-dag establishes strong nar results on the schema guided dialogue and the dart datasets, bridging gaps in nar research. 6 acknowledgement jinghong chen is supported by the warwick postgraduate studentship from christ's college and the huawei hisilicon studentship for the undertaking of the phd in engineering at the university of cambridge. weizhe lin was supported by a research studentship funded by toyota motor europe (rg92562(24020)). prof. bill byrne holds concurrent appointments as a professor of information engineering at cambridge university and as an amazon scholar. this publication describes work performed at cambridge university and is not associated with amazon. we would also like to thank all the reviewers for their knowledgeable reviews.