  Seq2seq models have been shown to struggle with compositional generalization
in semantic parsing, i.e. generalizing to unseen compositions of phenomena that
the model handles correctly in isolation.
  We phrase semantic parsing as a two-step process: we first tag each input
token with a multiset of output tokens. Then we arrange the tokens into an
output sequence using a new way of parameterizing and predicting permutations.
We formulate predicting a permutation as solving a regularized linear program
and we backpropagate through the solver. In contrast to prior work, our
approach does not place a priori restrictions on possible permutations, making
it very expressive.
  Our model outperforms pretrained seq2seq models and prior work on realistic
semantic parsing tasks that require generalization to longer examples. We also
outperform non-tree-based models on structural generalization on the COGS
benchmark. For the first time, we show that a model without an inductive bias
provided by trees achieves high accuracy on generalization to deeper recursion.
