PICARD : Parsing Incrementally for Constrained Auto-Regressive Decoding from Language Models (2021)

Abstract: Large pre-trained language models for textual data have an unconstrained output space; at each decoding step, they can produce any of 10,000s of sub-word tokens. When fine-tuned to target constrained formal languages like SQL, these models often generate invalid code, rendering it unusable. We propose PICARD (code available at https://github.com/ElementAI/picard ), a method for constraining auto-regressive decoders of language models through incremental parsing. PICARD helps to find valid output sequences by rejecting inadmissible tokens at each decoding step. On the challenging Spider and CoSQL text-to-SQL translation tasks, we show that PICARD transforms fine-tuned T5 models with passable performance into state-of-the-art solutions.

## introduction while there have been many successes in applying large pre-trained language models to downstream tasks, our ability to control and constrain the output of these models is still very limited. many enterprise applications are out of reach because they require a degree of rigour and exactitude that language models are not able to deliver yet. if the target is a formal language like sql, then we would like the model to adhere exactly and provably to the sql specification with all its lexical, grammatical, logical, and semantical constraints. unfortunately, with pre-training alone, language models may not satisfy these correctness requirements. for text-to-sql translation, the most widespread solution to constrained decoding is to make invalid sql unrepresentable. for a while now it has been possible to restrict auto-regressive decoding to only those token sequences that correctly parse to sql abstract syntax trees @xcite @xcite . more recently, semi-auto-regressive improvements to this parsing figure 1 : exact-set-match accuracy of the highestscoring prediction as a function of beam size on the spider text-to-sql development set. with picard turned on, token predictions had to pass picard checking at every decoding step. only the top-2, -4, and -8 token predictions of each hypothesis were considered in the beam search. with picard turned off (none), all token predictions were considered and none were checked. the models, t5-base, -large, and -3b, did not have access to any database content, only to the database schemas. in our experiments, we find that picard can significantly improve the performance of a large pre-trained language model @xcite after it is fine-tuned on the text-to-sql task. on the spider text-to-sql dataset @xcite , we find that a t5-base model with picard can outperform a t5-large model without it, and likewise for a t5-large and a t5-3b model. significantly, with the help of picard, a t5-3b model can be raised to state-of-the-art performance on the spider and cosql datasets @xcite . at each generation step, picard first restricts prediction to the top-k highest probability tokens and then assigns a score of -∞ to those that fail picard's numerous checks (see figure 2 ). these checks are enabled by fast incremental parsing (o'sullivan and gamari, 2021) based on monadic combinators @xcite . there are four picard mode settings that control their comprehensiveness: off (no checking), lexing, parsing without guards, and parsing with guards-the highest mode. a prediction that passes a higher mode will always pass a lower mode but not necessarily vice versa. ## experiments our experiments are mainly focused on spider @xcite , a large multi-domain and crossdatabase dataset for text-to-sql parsing. we train on the 7,000 examples in the spider training set and evaluate on spider's development set and its hidden test set. we also report results on the cosql sql-grounded dialog state tracking task @xcite , where we predict a sql query for each question given previous questions in an interaction context. for this task, we train on both the spider text-to-sql training data and the cosql dialog state tracking training data, and evaluate on the cosql development and test sets. spider and cosql are both zero-shot settings. there is no overlap between questions or databases between the respective training, development, and test sets. on spider, we determine model performance based on three metrics: exact-set-match accuracy, execution accuracy, and test-suite execution accuracy @xcite . exact-set-match accuracy compares the predicted and the ground-truth sql query by parsing both into a normalized data structure. this comparison is not sensitive to literal query values and can decrease under semanticpreserving sql query rewriting. execution accuracy compares the results of executing the predicted and ground-truth sql queries on the database contents shipped with the spider dataset. this metric is sensitive to literal query values, but suffers from a high false positive rate @xcite . lastly, test-suite execution accuracy extends execution to multiple database instances per sql schema. the contents of these instances are optimized to lower the number of false positives and to provide the best approximation of semantic accuracy. on cosql, we measure model performance in terms of the question match accuracy and the interaction match accuracy. both metrics are based on exact-set-match accuracy. interaction match accuracy is the joint accuracy over all questions in an interaction. we are encouraged by results by @xcite , who showed that a pre-trained t5-base or t5-3b model can not only learn the text-to-sql task, but also generalize to unseen databases, and even that t5-3b can be competitive with the then-state-of-the-art @xcite )-all without modifications to the model. we therefore use t5 as the baseline for all our experiments. in order to allow for generalization to unseen databases, we encode the schema together with the questions. we use the same serialization scheme used by @xcite . in experiments using database content, we detect and attach the database values to the column names in a fashion similar to the bridge model by @xcite . when fine-tuning for the cosql dialog state tracking task, we append the previous questions in the interaction in reverse chronological order to the input. inputs exceeding the 512-token limit of t5 are truncated. the target is the sql from the spider and/or cosql training sets, unmodified except for a conversion of keywords and identifiers to lower case. we fine-tune t5 for up to 3072 epochs using adafactor @xcite , a batch size of 2048, and a learning rate of 10 -4 . ## conclusion we propose and evaluate a new method, picard, for simple and effective constrained decoding with 2 this is not exactly equivalent to filtering a completely finalized beam, because the hypotheses rejected by picard never enter it and never take up any space. large pre-trained language models. on both, the spider cross-domain and cross-database text-to-sql dataset and the cosql sql-grounded dialog state tracking dataset, we find that the picard decoding method not only significantly improves the performance of fine-tuned but otherwise unmodified t5 models, it also lifts a t5-3b model to stateof-the-art results on the established exact-match and execution accuracy metrics.