Compositional Generalization without Trees using Multiset Tagging and Latent Permutations
This addresses the problem of improving compositional generalization for semantic parsing, offering a novel approach that is not incremental but provides a new method for a known bottleneck.
The paper tackles compositional generalization in semantic parsing by proposing a two-step model that tags input tokens with multisets and arranges them using latent permutations, outperforming prior models on realistic tasks and achieving high accuracy on generalization to deeper recursion without tree-based inductive biases.
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.