Structural generalization in COGS: Supertagging is (almost) all you need
Authors: Alban Petit
Caio Corro
François Yvon
Venue: EMNLP 2023 Main (2023)
Keywords: semantic parsing
compositional generalization
graph-based parsing
TL;DR: We extend a graph-based semantic parser with a supertagging step for compositional generalization.

Abstract: In many Natural Language Processing applications, neural networks have been found to fail to generalize on out-of-distribution examples.
In particular, several recent semantic parsing datasets have put forward important limitations of neural networks in cases where compositional generalization is required.
In this work, we extend a neural graph-based parsing framework in several ways to alleviate this issue, notably:
(1) the introduction of a supertagging step with valency constraints, expressed as an integer linear program;
(2) the reduction of the graph prediction problem to the maximum matching problem;
(3) the design of an incremental early-stopping training strategy to prevent overfitting.
Experimentally, our approach significantly improves results on examples that require structural generalization in the COGS dataset,
a known challenging benchmark for compositional generalization.
Overall, these results confirm that structural constraints are important for generalization in semantic parsing.

Structural generalization in COGS: Supertagging is (almost) all you need
Alban Petit and Caio Corro² and François Yvon
Université Paris-Saclay, CNRS, LISN, 91400, Orsay, France SSrbonnne Université, CNRS, ISIR, F-75005 Paris, France
alban. peti www.sse.uussuaaa......... fr {caio. ccrio.corro, corro, francois, www.eeiiir.uum.... fr
Abstract
In this work, we explore a different method for compositional generalization, based on supertag- ging. We demonstrate that local predictions (with global consistency constraints) are sufficient for compositional generalization. Contrary to Herzig and Berant (2021) and Petit and Corro (2023), our approach can predict any semantic graph (including ones with reentrancies), and contrary to Weißen- horn al. (2022) it does require any intermedi- ate representation of the semantic structure.
In many Natural Language Processing applica- tions, neural networks have been found to fail generalize
-i-t--iiiitiittionn examples. In particular, several recent semantic parsing datasets have put forward important limitations of neural networks in cases where composi- tional generalization is required. In this work, we extend neural graph-based semantic pars- ing framework in several ways to alleviate this issue. Notably, we propose: (1) the introduc- tion of supertagging step with valency con- straints, expressed as an integer linear program; (2) a reduction the maximum matching problem; (3) the de- sign of an incremental early-stopping training strategy to prevent overfitting. Experimentally, our approach significantly improves results on examples that require structural generalization the COGS dataset, a known challenging benchmark for compositional generalization. Overall, our results confirm that structural con- straints important for generalization in se- mantic parsing.
Moreover, our experiments highlight two funda- mental features that are important to tackle com- positional generalization in this setting. First, as is well known in the syntactic parsing literature, introducing a supertagging step in a parser may lead to infcasible solutions. We therefore propose integer linear programming formulation of pertagging that ensures the existence of least one feasible parse the search space, via the so-called companionship principle (Bonfante et al., 2009, 2014). Second, as the development dataset used to control training is in-distribution (i.e., it does not test for compositional generalization), there is a strong risk of overfitting. To this end, we propose an incremental early-stopping strategy that freezes part of the neural network during training. Our contributions can be summarized follows:
graph prediction problem
1 Introduction
Semantic parsing aims to transform a natural lan- guage utterance into structured representation. However, models based on neural networks have been shown struggle terances where compositional generalization is re- quired, i.e., on sentences with novel combinations of elements observed separately during training (Lake and Baroni, 2018; Finegan-Dollak et al., 2018; Keysers et al., 2020). Jambor and Bahdanau (2022) showed that neural graph-base based semantic parsers are more robust to compositional general- ization than peuuuecce-toseqqueee (seq2seq) mod- els. Moreover, Herzig and Berant (2021), Weißen- horn et al. (2022) and Petit and Corro (2023) have shown that introducing valency and type con- straints in a structured decoder improves composi- tional generalization capabilities.
tuttof-distribution ut-
we propose to introduce supertagging step in graph-based based semantic parser;
we show that, in this setting, argument identifi- cation can be reduced to matching problem;
we propose a novel approach based on infer- ence in a factor graph to compute the weakly- supervised loss (i.e., without gold alignment);
we propose incremental carly-stopping strategy to prevent overfitting:
we evaluate our approach on COGS and ob- serve that it outperforms comparable baselines on compositional generalization tasks.

---

Training example
Generalization example
Lexical generalizations
Subj to obj (common)
A hedgehog ale the cake Paula
The baby liked the hedgehog
Prim to subj (proper)
Paula sketched William
Active to passive
The crocodile blessed William
A muffin was blessed
PP dative to double dative
Jane shipped the cake to John
Jane shipped John the cake
Agent NP to unaccusative
The cobra helped dog
The cobra froze
Structural generalizations
Obj to subj
Noah atc the cake on the plate
The cake on the table burned
PP recursion
Ava saw the ball in the bottle Ava saw the ball in the bottle on the table on the floor
CP recursion
Emma said that the cat danced
Emma said that Noah knew that Lucas saw that the cat danced
Table 1: Examples of lexical generalization and structural generalization from COGS, adapted from (Kim and Linzen, 2020, Table 1). For PP and recursions, the number recursions observed at test time greater than the number of recursions observed during training.
Notations. set written as {.} and a mul- tiset as [.]]- We denote by [n]] the set of integers {1..... n... We denote the sum of entries of the Hadamard product as (:,-) (i.e., the standard scalar product if arguments are vectors). We assume the input sentence contains n words. We use the term "concept" to refer both predicates and entities.
achieve good accuracy for lexical generalization but fail for structural generalization.
Semantic graph construction. A semantic
structure in the COGS dataset is represented
logical form. We transform this representation into graph follows:
1. For each concept instance, we add labeled vertex.
2
Semantic parsing
2.1 COGS
For each argument p of a concept instance p', we create a labeled are from the vertex representing p' to the vertex representing p.
The principle of compositionality states that
"The meaning of an expression is func- tion of the meanings of its parts and of the way they are syntactically combined." (Partee, 1984)
COGS explicitly identifies definiteness of nouns. Therefore, for each definite noun that triggers a concept, we create a vertex p with label definite and we create an are with la- bel det from p to the vertex representing the noun's 's concept." Indefiniteness is marked by the absence of such structure.
Linguistic competence requires compositional gen- eralization, that is the ability understand new utterances made of known parts, e.g., understand- ing the meaning "Marie sees Pierre" should entail the understanding of "Pierre sees Marie".
This transformation illustrated in Figure 1.
The Compositional Generalization Challenge based on Semantic Interpretation (COGS, Kim and Linzen, 2020) dataset is designed evaluate two types of compositional generalizations. First, lex- ical generalization tests a model on known gram- matical structures where words are used in un- seen roles. For example, during training the word hedgehog is only used as a subject; the model needs to generalize to cases where it appears as an object. Second, structural generalization tests model syntactic structures that were not ob- served during training. Illustrations are in Table The error analysis presented by WeiBenhorn et al. (2022) emphasizes that neural semantic parsers
2.2 Graph-based decoding
The standard approach (Flanigan et al., 2014; Dozat and Manning, 2018; Jambor and Bahdanau, 2022) to graph-based semantic parsing is a two-step pipeline:
concept tagging:
2. argument identification.
'Using the determiner as the head of a relation may be surprising for readers familiar with syntactic dependency pars- ing datasets, but there is no consensus among linguists about the appropriate dependency direction, see e.g. Miller (2016, Section 1.5) for a discussion.

---

ccomp
AND like. (rent 21)
AND like. ccomp(a2,, 225)
det agent
agent
xcomp
AND prefer.agent(Ce (Ns, Emma)
definite
cat
like
Emma
prefer
walk
AND prefer. xcomp ir7)
AND walk.agent (3y,, Emma)
The
liked
that
Enma
preferred
walk
Figure 1: (left) Semantic analysis of the sentence "The cat liked that Emma preferred to walk" in the COGS formalism. * denotes definiteness of the following predicate. (right) Graph-based representation of the semantic structure. Note that mark definiteness using extra vertex anchored the determiner.
The second step is a sub-graph prediction problem. Concept tagging. We assume that each word can trigger at most one concept. Let T be the set of concepts, including a special tag E T that will be used to identify semantically empty words (i.e., words that do not trigger any concept). Let À Rex? be tag weights computed by the neural network. Without loss of generality, we assume that A = 0, vi C [n]. We denote a sequence of tags as boolean vector æ E {0, 1 where Tie = 1, + 0, indicates that word triggers con- cept t. This means that Vi [n]] Eier Zi,t 1. Given weights A, computing the sequence of tags of maximum linear weight is a simple problem.
S
S
NP
VP
NPJ
VP
V
NP|
Figure Two supertag examples from an LTAG. (left) Supertag associated with an intransitive verb. The sub- stitution site NP1 indicates the position of the subject. (right) Supertag associated with transitive verb. The supplementary substitution site on the right indicates the position of the object of the verbal phrase.
for example via multi-label prediction or using sev- eral tagging layers (Jambor and Bahdanau, 2022). The argument identification step is left unchanged. iee, we create one vertex per predicted concept in the graph.
Argument identification. We denote L the set of argument labels, e.g., agent E T.. The second step assigns arguments to concepts instances. For this, we create labeled graph G - A) where:
V = c ( * 0} the set of vertices representing concept instances;
Supertagging for graph-based semantic parsing
A C V V x L is the set of labeled arcs, where (i,j,) A denotes to vertex j labeled I.
In the syntactic parsing literature, supertagging refers to assigning complex descriptions of the syn- tactic structure directly at the lexical level (Ban- galore and Joshi, 1999). For example, while an occurrence of the verb 'to walk' be described in coarse manner via its part-of-speech tag, pertag additionally indicates that this verb appears in a clause with subject on the left and a verbal phrase on the right, the latter also potentially re- quiring an object on its right, see Figure 2 for an illustration in the formalism of lexicalized Tree- Adjoining Grammars (LTAGs, Joshi et al., 1975).
from vertex
In practice, we construct a complete graph, includ- ing parallel ares with different labels, but excluding self-loops. Given weights µu AAA, argument identification reduces the selection of the subset of arcs of maximum weight such at most one are with given direction between any two vertices selected. Again, this problem is simple. We denote a set of arcs as a boolean vector z E {0. 1}" where Z.j.d = 1 indicates that there is an are from vertex to vertex j labeled / in the prediction.
We propose introduce an intermediary seman- tie supertagging step in graph- based semantic parser. The pipeline of Section 2.2 becomes:
Multiple concepts per words. More realistic semantic parsing scenarios require to trigger more than one concept per word. This only impacts the concept tagging step: one must change the model to allow the prediction of several concepts per word,
1. concept tagging:
semantic supertagging;

---

0. Input sentence
0. Input sentence
cat
ate
the
cake
cat
ate
the
cake
1. Part-of-speedt tagging
Concept tagging
cat
eat
def
cake
2. Syntactic supertagging
2. Semantic supertagging
thome
der
NP
NP4
VP
N
NP
NP4
agent
Theme
3. Derivation parsing
Argument identification
1.2.2
theme
1.1
1.1
agent
1.1
det
Figure 3: Comparaison a LTAG parsing pipeline and the proposed semantic parsing pipeline. (left) standard LTAG parsing pipeline. We start with an input sentence, then predict part-of-speech tag per word. This part-of-speech can be used as feature or to filter the set of possible supertags in the next step. The supertagging step chooses one supertag per word. Finally, in the last step we merge all supertags together. This operation can be synthesised as derivation tree where arc labels indicate Gorn adresses of substitution and adjunction operations. We refer readers unfamiliar with LTAG parsing to (Kallmeyer, 2010). (right) Our semantic parsing pipeline. We start with input sentence, then predict most concept per word, where indicates no concept. The supertagging step assigns one supertag per concept instance (i.e., excluding words tagged with 0). Finally, the argument identification step identifies arguments of predicates using the valency constraints from supertags.
3. argument identification.
and the one associated with 'prefer' is [ageett -), (xcomp, -), (ccomp, +)]. The set of all supertags is denoted S.
This new pipeline is illustrated on Figure Note that the introduction of the novel step does not impact the concept tagging step. As such, our ap- proach is also applicable to datasets that would require multiple concepts prediction per word (see Section 2.2).
The Companionship principle (CP).2 Let us first consider the following simple example: as- suming we would like to parse the sentence "Marie ate", yet associate the transitive supertag [(agent, -), (theme, -]] to the verb. In this case, the argument identification step will fail: the verb has no object in this sentence. The CP states that each substitution site must have potential root in the supertag sequence. That is, in the supertagging step, must make sure that the number of substi- tution sites with given label exactly matches the number of roots with the same label, to ensure that there will exist at least one feasible solution for the next step of the pipeline. As such, supertagging here is assigning tags in context.
3.1 Semantic supertagging
In setting, supertag indicates the expected arguments of concept instance (potentially none for an entity) and also how the concept used. Contrary to syntactic grammars, our supertags do not impose direction. In the following, we refer to an expected argument as a substitution site and to an expected usage as root.
Formally, we define a (semantic) supertag multiset of tuples dL, E L {-++) where is label and indicates either sub- stitution site or root, e.g., (agent,-) is substitution site and (agent, +) is root. For example, Figure I, the supertag associ- ated with 'like" is [[agentt -), (ccomp,-) -)]]
Theorem 1. Given set of supertags, a sequence of concept instances and associated supertag weights, the following problem NP-complete: is there
"We borrow the name from (Bonfante et al., 2009, 2014). although our usage is slightly different.

---

a sequence of supertag assignments with linear weight 2 m that satisfies the CP?
containing (1) the set of all observed supertags in the training set, augmented with (2) the cross- product of all root combinations and substitution site combinations. For example, if the training data contains supertags [[ccomp, +), (agent, -)] and [(agent, -), (theme, clude [(ccomp, +), (agent, -), (theme, [)]l and [(agent, -) in the set of supertags.
Proof. First, note that given a sequence of su- pertags, it is trivial to check in linear time that its linear weight is > m and that it satisfies the CP. therefore the problem is in NP. We now prove NP- completeness by reducing 3-dimensional matching supertagging with the CP.
we also in-
Formally, let S (resp. S be the set of root combinations (resp. substitution site combinations) observed in the data. The set of supertags is:
3-dim. matching is defined as follows: Let A = {=l1)) = {b())]== and C = {c(t)) be 3 sets of n elements and D S x B x C. A subset D' S D is 3-dim. matching if and only if, for any two distinct triples (a, b, e) E D' and (a', b', b', E D', the following three conditions hold: + a',
g+ StESt A A
s Us
#1
Note that the empty multiset can not be a supertag. Supertag prediction. Let y E [0,1)axs* and y' {0, 1]axs*t be indicator variables of the substitution sites and roots, respectively, associated with each word, e.g. Vi, 1 indicates that concept instance at position
b * D' and f
The following decision problem is known to be
NP-complete (Karp, 1972): given A, B, C and D is there a 3-dim. matching D' S with [D|| 2 n?? We reduce this problem to supertagging with the CP as follows. We construct an in- stance of the problem with 3n concept instances a(1), ..., (n), b(1), (()), c(1), supertag set S is defined follows, where their associated weight 0 except stated otherwise:
[ri] has substitution sites E S We now describe the constraints that y and y must satisfy. First, each position in the sentence should have exactly one set of substitution sites and one set of roots if and only if they have an associated concept:
The
For each triple (a,b,c) b) D, we add su- pertag [[b. -), -)] with weight if and only if is predicted for concept a;;
Σ Vi, = 1 -;
vi [n]
(1)
SES
Σ Vr.s = - Iz.0
vi E [n]
(2)
For each E B, we add supertag [[b,+ +)] with weight 1 if and only if predicted for concept 6;
*ES+
Next, we forbid the empty supertag:
yan + vmmm 1
vi [n]
(3)
For each c E C. we add a supertag [[c, +)] with weight 1 if and only if predicted for concept c.
Finally, we need to enforce the companionship prin- ciple. We count in 05 the number of substitution sites with label C in E S and similarly in Va, for roots. We can then enforce the number of roots with given label to be equal to the number of substitution sites with the same label follows:
If there exists a sequence of supertag assignment satisfying the CP that has weight 2 m 3n, then there exists solution for the 3-dim. matching problem, given by the supertags associated with concept instances (I),....(n)).
Σ Vi. U. iE(n]. #ES
Σ S
Vl L.
(4)
Note that an algorithm for the supertagging deci- sion problem could rely on the maximisation vari- ant as subroutine. This result motivates the use of heuristic algorithm. We rely on the continu- ous relaxation of integer lincar program that embed in branch-and and-bound procedure. We first explain how we construct the of supertags impacts the whole program.
kEjm).
SEST
All in all, supertagging with the companionship principle reduces to the following integer linear
program:
(. +yy ++)
max yt
s.t.
(1-4),
Supertag extraction. To improve generaliza- tion capabilities, we define the set of supertags as
y E (0, 1n , E 10,1

---

In practice, we use the CPLEX solver.3
practice (Zhang al., 2017: Corro, 2023). The concept loss is sum of one NLL loss per word:
Timing. We initially implemented this ILP us- ing the CPLEX Python API. The resulting imple- mentation could predict supertags for only = 10 sentences per second. We reimplemented the ILP using the CPLEX C++ API (via Cython) with few extra optimizations, leading to an implementation that could solve s 1000 instances per second.
ccoccopt (A: = (A, σ +
log
exp Xiat
KET
For supertagging, we use the following losses:
Sub. ( = (Φ
3.2 Argument identification
+ Σ
log
exp 0i
The last step of the pipeline is argument identifica- tion. Note that in many cases, there is no ambiguity, see the example in Figure as there root and substitution site per label, we can infer that the theme of concept instance eat is cake, etc. However, in the general case, there may be several rools and substitution sites with the same label. In the example of Figure 1, we would have 3 agent roots after the supertagging step.
$CS
Fooc (8+
= (Φ
most one
+
Σ
log
exp
kE|p]
#ES+
Finally, for argument identification have loss per couple of positions in the sentence:
Larg. (1i: (H,, 2)
For ambiguous labels after the supertagging step, we can rely on bipartite matching (or assignment) algorithm. Let C be an ambiguous label. We construct a bipartite undirected graph as follows:
+
Σ
log exp Miji
(i.)) x(n]
IEL
Note that for the concept loss, we have a special empty tag with null score for the case where there is no concept associated with word in the gold output (and similarly for argument identification). Weakly-supervisee loss. In practice, it is often the case that we do not observe the alignment be- tween concept instances and words in the training dataset, which must therefore be learned jointly with the parameters. To this end, we follow an "hard" EM-like procedure (Neal and Hinton, 1998);
The first node set C contains node per substitution site with label
The second node set C" contains one node per root with label I;
we add an edge for each pair (c.c') c'c C x C" with weight Mi.jd where E [n] and [n]] sentence positions of the substitution site represented by e and the root represented by c' respectivell.
E step: compute the best possible alignment between concept instances and words;
We then use the Jonker-Volle Volgenant algorithm (Jonker and Volgenant, 1988; Crouse, 2016) com- pute the matching of maximum linear weight with complexity cubic w.r.t. the number of nodes. Note that thanks to the companionship principle, there is always at least one feasible solution to this problem, i.e., our approach will never lead to a "dead-end" and will always predict (potentially wrong) se- mantic parse for any given input.
M step: apply one gradient descent step using the "gold" tuple (œ, ",, N,, induced by the alignment from the E step.
Note that the alignment procedure in the step is NP-hard (Petit and Corro, 2023, Theorem 2). as the scoring function not linear. For example, assume two concept instances and p' such that p an argument of If and p' are aligned with i and j. respectively, the alignment score includes the token tagging weights induced by this alignment plus the weight of the labeled dependency from to
4 Training objective
Supervised loss. Let ( be a gold an- notation from the training dataset. We use separa- ble negative log-likelihood losses (NLL) for each step as they are fast to compute and work well in
We propose to reduce the E step to maximum a posteriori (MAP) inference in a factor graph, see Figure 4. We define one random variable (RV) tak- ing values in [n] per concept instance. The assign- ment these RVs indicate the alignment between
hht //www. ibm, com/ con//poddic prouctss/ ilog- cetex-xpptmizaaiion studio

---

AGENT
THEME
DET
ba4
A
Us
NA
2
3
4
A1.
M1,2,
|1,3,
M1,4
[4,5,
2
X2,1
M2,1,
-00
P2,3,
P2,4,
N2,5,1
Ms
A
A4
3
Ag,t
P3,13
A3,2,
-00
P3,4.
P3,5,1
4
Ad,1
P4,13
P4.2.
P4,3.
-00
P4,,511
5
A5,
M5,13
A5,2,4
[s,3,
M4,
-00
ArMOSTONE
Figure (left) The factor graph used to compute the best alignment the semantic graph E steps for the sentence "A cat ate the cake'. Each variable corresponds unary factor. For each argument of a concept instance, we add a binary factor between between the concept instance and its argument's 's instance. (center) Weights of am unary factor given the value of its corresponding variable. We denote the concept corresponding to that factor (displayed above unary factors). (right) Weights of a binary factor by, where the concept instance represented by A is an argument of the concept instance represented by A in the semantic graph. We denote the label of the argument (displayed above binary factors).
concept instance in the semantic graph and has associated
concept instances and words. Unary factors corre- spond to tagging weights, e.g, aligning a concept t E T with word i E [n]] induces weight A Bi- nary factors correspond to argument identification: for each are the semantic graph, add binary factor between the two concept instances RVs that will induce the dependency weight given the RVs assignment. Finally, there a global factor acting as an indicator function, that forbids RVs assign- ments where different concept instances are aligned with the same word. We use AD3 (Martins et al., 201 I) for MAP inference in this factor graph.
parser exhibits strong performance, this approach requires work from domain experts to define the set of operations needed to construct trees for each dataset. Other line of work that seek to tackle com- positional generalization issues include using pre- trained models (Herzig et al., 2021; Furrer et al.. 2021), specialized architectures (Korrel al., 2019; Russin et al., 2020; Gordon et al., 2020; Csordás et al., 2021) and regularization (Yin et al., 2023). Graph-based semantic parsing. Graph-based methods have been popularized by syntactic depen- dency parsing (McDonald al., 2005). To reduce computational complexity, Dozat and Manning (2018) proposed neural graph-based parser that handles each dependency as an independent classi- fication problem. Similar approaches were applied in semantic parsing, first for AMR parsing (Lyu and Titov, 2018: Groschwitz et al., 2018). Graph-based approaches have only recently been evaluated for compositional generalization. The approach pro- posed by Petit and Corro (2023) showed significant improvements compared existing work on com- positional splits of the GeoQuery dataset. However, their parser can only generate trees. Weißenhorn et al. (2022) and Jambor and Bahdanau (2022) introduced approaches that can handle arbitrary graphs, requirement to successfully parse COGS.
5 Related work
Compositional generalization. Compositional generalization has been a recent topic of interest in semantic parsing. This is because failure to generalize is an important source of error, espe- cially in seq2seq models (Lake and Baroni, 2018; Finegan-Dollak et al., 2018; Herzig and Berant, 2021; Keysers et al., 2020). Several directions have been explored in response. Zheng and La- pata (2021) rely on latent concept tagging in the encoder of a seq2seq model, while Lindemann et al. (2023) introduce latent fertility and re-ordering lay- ers in their model. Another research direction uses data augmentation methods improve generaliza- tion (Jia and Liang, 2016; Andreas, 2020; Akyürek et al., 2021: Qiu et al., 2022; Yang et al., 2022). Span- bpsed methods have also been shown im- prove compositional generalization (Pasupat et al., 2019; Herzig and Berant, 2021; Liu et al., 2021). Particularly, Liu et al. (2021) explicitly represent input sentences as trees and use a Tree-LSTM (Tai et al., 2015) in their encoder. While this
Experiments
We a neural network based BiLSTM (Hochreiter and Schmidhuber, 1997) and biaffine layer for are weights (Dozat and Manning, 2017).
More detail are given in Appendix A. As usual in the compositional generalization literature, we

---

Structural gen.
Lexical gen.
Overall
Obj to Subj PP
PP recursion
CP recursion
Seq2seq models
Kim and Linzen (2020)
0
42
Conklin et al. (2021)*
67
Akyürek et al. (2021)
1
0
96
83
Zheng and Lapata (2021)
39
12
99
89
Structured models
LEAR (Liu 2021)
97.7
w/o Tree-LSTM
80.7
reproduction by Weißenhorr et al. (2022)
99
100
99
Jambor and Bahdanau (2022)'
82.3
WoiBenhhrr et al. (2022)
59
36
100
82
79.6
Our baselines: Standard graph-based parser
Full model
11.6
97.4
84.1
w/o early stopping w/o early stopping supertagging loss
12.7
97.3
97.5
84.1
Proposed method: graph-based parser with supertagging
Full model
75.0
100
100
99.1
98.1
w/o early stopping
51.1
100
100
98.9
96.7
Table Exact match accuray COGS. We report results for each subset of the set (structural generalization and lexical generalization) and the overall accuracy. For our results, we report the mean over 3 runs. Entries marked with f use a subset of sentences from generalization set as their development set.
evaluate our approach in fully supervised setting, ie., we do not use pre-trained neural network like BERT (Devlin al., 2019). Code to reproduce the experiments is available online.
tion of tags, supertags, dependencies) is monitored independently on the in-distribution development set. As soon accuracy, we freeze the shared part of the neural architecture (word embeddings and the BiLSTM). We also freeze the layers that produce the scores of the perfectly predicted task. For each subsequent task that achieves perfect accuracy, the correspond- ing layers are also frozen. This early stopping approach prevents overfitting.
of these tasks achieves 100%
6.1 Early stopping
COGS only possesses in-distribution develop- ment and the accuracy of most parsers on this set usually reaches 100%. Previous work by Con- klin et al. (2021) emphasized that the lack of development set representative the generaliza- tion set makes model selection difficult and hard to reproduce. They proposed to sample a small subset of the generalization set that is used for de- velopment. Both their work and LaGR (Jambor and Bahdanau, 2022) use this approach and sample subset of 1000 sentences from the generalization set to use as their development set. However, we argue that this development set leaks compositional generalization information during training.
We also experimented using the hinge loss in- stead of the NLL loss shares similar properties to our early stopping strategy: once a prediction is correct (including a margin between the gold output and other outputs), the gradient of the loss becomes null. We however found that this loss yields very low experimental results (null exact match score on the test set).
6.2 Results
All results exact match accuracy, i.e., the ratio of semantic structures that are correctly predicted. We report the overall accuracy," 5 the accuracy over all lexical generalization cases as well as the indi- vidual accuracy for each structural generalization
We propose variant of carly stopping to pre- vent overfitting the in-distribution data without requiring a compositional generalization develop- ment set. We incrementally freeze layers in the neural network as follows: each subtask (predic-
As COGS contains 1,000 sentences for each generaliza- tion, case, this number mostly reflects the accuracy for lexical generalization, which account for 85.7% % of the test set.
htttps///iithu/ httpll..comalllaaaa cow/alban-petiti. www.nnticsuuuuttaaaaaa

---

Obj
Subj PP
PP rec.
CP rec.
agent
himod.in in theme
Word level accuracy
ILP
90.2
100
100
dct recip.
No ILP
71.6
99.9
100
donkey def. room sell Ella
donut
Sentence level accuracy
A donkey in the room sold Ella
donut
ILP
75.0
ILP
9.0
theme
nmodin
recip
theme
der
Table 3: Supertagging accuracy using our integer linear program (ILP) and without (i.e. simply predicting the best supertag for each word, without enforcing the com- panionship principle).
mmod.in in
agent
recip-
case. We report mean accuracy over 3 runs. External baselines. We compare our method to several baselines: (1) the seq2seq models of Kim and Linzen (2020), Akyürek et al. (2021) and Zheng and Lapata (2021); (2) two graph-based models, LAGR (Jambor and Bahdanau, 2022) and the AM parser of Weißenhorn al. (2022); (3)
Figure 5: (top) Gold semantic graph. (bottom) Su- pertags predicted without enforcing the companionship principle. A mistake occurs for 'donkey' as the theme root is predicted, instead agent. This is probably due the introduction of a PP before the verb, which con- fuses the network: PP only occur with objects during training. Using ILP fixes this mistake.
LeAR (Liu et al., 2021), a semantic parser that re- lies on a more complex Tree-LSTM encoder (Tai
for Obj to subj PP. resulting in 23.9 points in- crease (from 51.1 to 75.0). Such improvements are not observed for the baselines. From this, we conclude that neural architecture tends over- fit the COGS training set and that some measures must be taken to mitigate this behaviour.
et al., 2015).
also report the performance of LeAR when a BiLSTM is used in the encoder in- stead of the Tree-LSTM.
Our baselines. We also report results for our model using the standard graph-based semantic parsing pipeline (Section 2.2), that is without the intermediary supertagging step. Note that, in this case, the supertagging loss becomes an auxiliary loss, as proposed by Candito (2022).
Suppertagging accuracy. We report in Table 3 the supertagging accuracy with and without en- forcing the companionship principle. We observe a sharp drop in accuracy for the Obj to Subj PP generalization when the companionship principle is not enforced. This highlights the importance of structural constraints to improve compositional generalization. We observe that the many are due the presence of the prepositional phrase just after the subject: this configuration causes the supertagger to wrongly assign theme root to the subject, instead of agent. When the companion- ship principle is enforced, this mistake is corrected. An illustration is in Figure 5.
Result comparison. We observe that our ap- proach outperforms every baseline except LEAR. Importantly, our method achieves high exact match accuracy on the structural generalization examples, although the Obj to subj PP generalization remains difficult (our approach only reaches an accuracy of 75.0% for this case).
We now consider the effect of our novel infer- ence procedure compared to our standard graph- based pipeline. It predicts PP recursion and CP recursion generalizations perfectly, where the base- line accuracy for these cases For Obj subj PP generalization, our best configuration reaches an accuracy of 75.0%. times more than the base- lines. All in all, the proposed inference strategy improves results the three structural general- izations subsets, and brings lexical generalization cases closer to 100% accuracy.
Conclusion
We proposed to introduce supertagging step in graph-based semantic parser. We analysed com- plexities and proposed algorithms for each step of our novel pipeline. Experimentally, our method significantly improves results for cases where com- positional generalization is needed.
Impact of training procedure. The carly stop- ping approach introduced above has a clear impact

---

Limitations
Henry Conklin, Bailin Wang, Kenny Smith, and Ivan Titov. 2021. Meta-learning to compositionally gen- eralize. In Proceedings of the 59th Annual Meet- ing of the Association for Computational Linguistics and the 11th International Joint Conference on Natu- ral Language Processing (Volume I: Long Papers), pages 3322-3335, Online, Association for Computa- tional Linguistics.
One limitation of our method is that we cannot predict supertags unseen during training (e.g., com- binaison of roots unseen at training time). Note however that this problem is well-known in the syntactic parsing literature, and meta-grammars could be used to overcome this limitation. Another downside of our parser is the use of an ILP solver. Although it is fast when using the COGS dataset, this may be an issue in a more realistic setting. Fi- nally, note that our method uses pipeline, local predictions in the first steps cannot benefit from ar- gument identification scores to fix potential errors.
Caio Corro. 2023. On the inconsistency of separable losses for structured prediction. In Proceedings of the 17th Conference of the European Chapter of the Association for Computational Linguistics: Main Vol- ume. Association for Computational Linguisties.
David F Crouse. 2016. On implementing 2d rectan- gular assignment algorithms. IEEE Transactions on Aerospace and Electronic Systems, 52(4):1679- 1696.
Acknowledgments
Róbert Csordás, Kazuki Irie, and Juergen Schmidhuber. 2021. The devil in the detail: Simple tricks im- prove systematic generalization of transformers. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 619- 634, Online and Punta Cana, Dominican Republic. Association for Computational Linguisties.
We thank the anonymous reviewers and meta- reviewer for their comments and suggestions. This work was funded by the UDOPIA doctoral program in Artifial Intelligence from Université Paris-Saclay LANR-20-THIA-0011 and benefited from compu- tations done on the Saclay-IA platform.
Jacob Devlin, Ming-Was Wei Chang, Kenton Lee, and Kristina Toutanova. 2019. BERT: Pre-training of deep bidirectional transformers for language under- standing. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Tech- nologies, Volume (Long and Short Papers), pages 4171-4186, Minneapolis, Minnesota. Association for Computational Linguistics.
References
Ekin Akyürck, Afra Feyza Akyürek, and Jacob Andreas. 2021. Learning recombine and resample data for compositional generalization. In International Con- ference on Learning Representations.
Timothy Dozat and Christopher D. Manning. 2017. Deep biaffine attention for neural dependency pars- ing. In International Conference on Learning Repre- sentations.
Jacob Andreas. 2020. Good-enough compositional data augmentation. In Proceedings of the 58th Annual Meeting of the Association for Computational Lin- guistics, pages 7556-7566, Online. Association for Computational Linguistics.
Timothy Dozat and Christopher D. Manning. 2018.
Simpler but more accurate semantic dependency pars- ing. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics ( (Vol- 2: Short Papers), pages 484-490, Melbourne, Australia. Association for Computational Linguistics.
Srinivas Bangalore and Aravind K. Joshi. 1999. Su- pertagging: An approach to almost parsing. Compu- tational Linguistics, 25(2):237-265.
Catherine Finegan- Dollak, Jonathan K. Kummerfeld, Li Zhang. Karthik Ramanathan, Sesh Sadasivam, Rui Zhang, and Dragomir Radev. 2018. Improving text- to-SQL evaluation methodology. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pages 351-360, Melbourne, Australia. Association for Computational Linguistics.
Guillaume Bonfante, Bruno Guillaume, and Math- ieu Morey. 2009. Dependency constraints for lex- ical disambiguation. In Proceedings of the 11th International Conference on Parsing Technologies (IWPT'09). pages 242-255 Paris, France. Associa- tion for Computational Linguistics.
Guillaume Bonfante, Bruno Guillaume, Mathieu Morey, and Guy Perrier. 2014. Supertagging with Con- straints, chapter 12.
Jeffrey Flanigan, Sam Thomson, Jaime Carbonell, Chris Dyer, and Noah A. Smith, 2014. A discriminative graph-based based parser for the Abstract Meaning Repre- sentation. In Proceedings of the 52nd Annual Meet- ing of the Association for Computational Linguistics (Volume I: Long Papers), pages 1426-1436, Bal- timore, Maryland. Association for Computational Linguistics.
Marie Candito. 2022. Auxiliary tasks to boost biaffine semantic dependency parsing. In Findings of the As- sociation for Computational Linguistics: ACL 2022, pages 2422-2429 Dublin, Ireland. Association for Computational Linguistics.

---

Daniel Furrer, Mare van Zee. Nathan Scales, and Nathanael Schärli. 2021. Compositional generaliza- tion in semantic parsing: Pre-training vs. specialized architectures.
Richard M. Karp. 1972. Reducibility among Combina- torial Problems, pages 85-103. Springer US, Boston, MA.
Daniel Keysers, Nathanael Schärli, Nathan Scales, Hylke Buisman, Daniel Furrer, Sergii Kashubin, Nikola Momchev, Danila Sinopalnikov. Lukasz Stafiniak, Tibor Tihon, Dmiury Tsarkov, Xiao Wang, Mare van Zee, and Olivier Bousquet. 2020. Measur- ing compositional generalization: A comprehensive method on realistic data. In International Conference on Learning Representations.
Jonathan Gordon, David Lopez-Paz, Marco Baroni, and Diane Bouchacourt. 2020. Permutation equivariant models for compositional generalization in language. In International Conference on Learning Representa- tions.
Jonas Groschwitz, Matthias Lindemann, Mcaghan Fowlie. Mark Johnson, and Alexander Koller. 2018. AMR dependency parsing with a typed semantic al- gebra. In Proceedings of the 56th Annual Meering of the Association for Computational Linguistics (Vol- ume I: Long Papers). pages 1831-1841, Melbourne, Australia. Association for Computational Linguistics.
Najoung Kim and Tal Linzen. 2020. COGS: A compo- sitional generalization challenge based on semantic interpretation. In Proceedings of the 2020 Confer- ence on Empirical Methods in Natural Language Processing (EMNLP), pages 9087-9100 Online. As- sociation for Computational Linguisties.
Jonathan Herzig and Jonathan Berant. 2021. Span- based semantic parsing for compositional general- ization. In Proceedings of the 59th Annual Meet- ing of the Association for Computational Linguistics and the 11th International Joint Conference on Natu- val Language Processing (Volume 1: Long Papers), pages 908-921, Online, Association for Computa- tional Linguistics.
Kris Korrel, Dieuwke Hupkes, Verna Dankers, and Elia Bruni. 2019. Transcoding compositionally: Using attention to find more generalizable solutions. In Pro- ceedings of the 2019 ACL Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, pages 1-11, Florence, Italy. Association for Compu- tational Linguistics.
Jonathan Herzig, Peter Shaw, Ming- Wei Chang, Kelvin Guu, Panupong Pasupat, and Yuan Zhang. 2021. Un- locking compositional generalization in pre-trained models using intermediate representations. arXiv preprint 2rXhv:2104.074:
Brenden Lake and Marco Baroni. 2018. Generalization without systematicity: On the compositional skills of pequence-to-sequeee ceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Ma- chine Learning Research, pages 2873-2882. PMLR.
recurrent networks. In Pro-
Sepp Hochreiter and Jürgen Schmidhuber. 1997. Long short-term memory. Neural Comput..
Matthias Lindemann, Alexander Koller, and Ivan Titov. 2023. Compositional generalisation with structured reordering and fertility layers.
Dora Jambor and Dzmitry Bahdanau. 2022. LAGr: Label aligned graphs for better systematic general- ization in semantic parsing. In Proceedings of the 60th Annual Meeting of the Association for Compu- tational Linguistics (Voiume 1: Long Papers), pages 3295-3308, Dublin, Ireland. Association for Compu- tational Linguistics.
Chenyao Liu, Shengnan An, Zeqi Lin, Qian Liu, Bei Chen, Jian-Guang Lou, Lijie Wen, Nanning Zheng, and Dongmei Zhang. 2021. Learning algebraic re- combination for compositional generalization. In Findings of the Association for Computational Lin- guistics: ACL-IJCNLP 2021, pages 1129-1144 On- line. Association for Computational Linguistics.
Robin Jia and Percy Liang. 2016. Data recombination for neural semantic parsing. In Proceedings of the 54th Annual Meeting of the Association for Compu- tational Linguistics (Volume 1: Long Papers), pages 12-22, Berlin. Germany. Association for Computa- tional Linguisties.
Chunchuan Lyu and Ivan Titov, 2018 AMR parsing as graph prediction with latent alignment. In Proceed- ings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 397-407, Melbourne, Australia. Association for Computational Linguistics.
Roy Jonker and Ton Volgenant. 1988. A shortest aug- menting path algorithm for dense and sparse linear assignment problems. In DGOR/NSOR: Papers of the 16th Annual Meeting of DGOR in Cooperation with vosttror der 16. Jahrestagung der DGOR zusammen mit der NSOR, pages 622 -222. Springer.
André F. T. Martins, Mário A. T. Figueiredo, Pedro M. Q. Aguiar, Noah A. Smith, and Eric P. Xing. 201 An augmented lagrangian approach to con- strained map inference. In International Conference Machine Learning.
Aravind K. Joshi, Leon S Levy, and Masako Takahashi. 1975. Tree adjunet grammars. Journal of computer and system sciences, 1061)333-1163
Ryan McDonald. Fernando Pereira, Kiril Ribarov, and Jan Hajië. 2005. Non-projective dependency pars- ing using spanning tree algorithms. In Proceed- ings of Human Language Technology Conference and Conference on Empirical Methods in Natural
Laura Kallmeyer. 2010. Parsing Beyond Context-Free Grammars. Springer Science & Business Media.

---

Language Processing, pages 523-530. Vancouver, British Columbia, Canada. Association for Computa- tional Linguistics.
Jingfeng Yang, Le Zhang, and Diyi Yang. 2022. SUBS:
Subtree substitution for compositional semantic pars- ing. In Proceedings of the 2022 Conference of the North American Chapter of the Association for Com- putational Linguistics: Human Language Technolo- gies, pages 169-174, Seattle, United States. Associa- tion for Computational Linguistics.
Stefan Müller, 2016.
Grammatical theory: From transformational grammar to constraint-based ap- proaches. Language Science Press.
Yongjing Yin, Jiali Zeng, Yafu Li, Fandong Meng, Jie Zhou, and Yue Zhang. 2023. Consistency regular- ization training for compositional generalization. In Proceedings of the 61st Annual Meeting of the As- sociation for Computational Linguistics (Volume I: Long Papers), pages 1294-1300 Toronto, Canada. Association for Computational Linguisties.
Radford M. Neal and Geoffrey E. Hinton. 1998. A view of the EM algorithm that justifies incremental, sparse, and other variants. In Learning in graphical models, pages 353-368 Springer.
Barbara Partee. 1984. Compositionality. Varieties of formal semantics.
Xingxing Zhang, Jianpeng Cheng, and Mirella Lapata. 2017. Dependency parsing as head selection. In Proceedings of the 15th Conference of the European Chapter of the Association for Computational Lin- guistics: Volume 1, Long Papers, pages 665-676, Valencia, Spain. Association for Computational Lin- guistics.
Panupong Pasupat, Sonal Gupta, Karishma Mandyam, Rushin Shah, Mike Lewis, and Luke Zeulemoyer. 2019. Span-baste based hierarchical semantic parsing for task fask-oriented dialog. In Proceedings of the 2019 Con- ference Empirical Methods in Natural Language Processing and the 9th International Joint Confer- ence on Natural Language Processing (EMNLP- (JCNLP), pages 1520-1526, Hong Kong, China. As- sociation for Computational Linguistics.
Hao Zheng and Mirella Lapata. 2021. Compositional
generalization via semantic tagging. In Findings of the Association for Computational Linguisties: EMNLP 2021, pages 1022-1032, Punta Cana, Do- minican Republic. Association for Computational Linguisties.
Alhan Petit and Caio Corro. 2023. On graph-based reentrancy-free semantic parsing.
Linlu Qiu, Peter Shaw, Panupong Pasupat, Pawel Nowak, Tal Linzen, Fei Sha, and Kristina Toutanova. 2022. Improving compositional generalization with latent structure and data augmentation. In Proceed- ings of the 2022 Conference of the North Ameri- can Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 4341-4362, Seattle, United States, Association for Computational Linguistics.
Jacob Russin, Jason Jo, Randall O'Reilly, and Yoshua Bengio. 2020. Compositional generalization by fac- torizing alignment and translation. In Proceedings of the 58th Annual Meeting of the Association for Com- putational Lingwistics: Student Research Workshop, pages 313-327 Online. Association for Computa- tional Linguistics.
Kai Sheng Tai, Richard Socher, and Christopher Man- ning. 2015. Improved semantic representations from tree-structured long short-term memory networks. In Proceedings of the 53rd Annual Meeting of the As- sociation for Computational Linguistics and the 7th International Joint Conference Natural Language Processing (Volume Long Papers). pages 1556- 1566, Beijing, China. Association for Computational Linguistics.
Pia Weißenhom, Lucia Donatelli, and Alexander Koller. 2022. Compositional generalization with a broad- coverage semantic parser. In Proceedings of the 1 1thh Joint Conference Lexical and Computational Se- mantics, pages 44-54, Seattle, Washington. Associa- tion for Computational Linguistics.

---

A Neural architecture
The neural architecture used our experiments to produce the weights X, ot, o and is composed of:
An embedding layer of dimension 200 fol- lowed by a bi-LSTM (Hochreiter and Schmid- huber, 1997) with a hidden size of 400.
A linear projection of dimension 300 followed by RELU activation and another linear pro- jection of dimension [T'l to produce X.
A linear projection of dimension 200 followed by RELU activation and another linear pro- to produce +
jection of dimension
[S+|
A linear projection of dimension 200 followed by RELU activation and another linear pro- jection of dimension [S'| to produce &
A linear projection of dimension 200 followed by RELU activation and a bi-affine layer to produce Ja.
We apply dropout with probability of 0.3 over the outputs of each layer except the final layer for each weight matrix. The learning rate is 5 10-1 and there are 30 sentences per mini-batch.


Reviews:
[{"review_id": "hHyFe5dqiV", "reviewer": "Reviewer_Gx4y", "summary": "", "questions": "", "limitations": "", "rating": 2, "confidence": 4, "soundness": 3, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer,\n\nThank you for your review. We try to address your main concerns below.\n\nFirst, we want to emphasize that the term **supertagging** is used as an analogy to supertagging in the syntactic parsing litterature, but that our approach is simpler and does not suffer from many drawbacks of LTAG and CCG supertagging:\n- our semantic supertags are trivial to extract from the training corpus, and we do not need any heuristic to extract them as required for LTAGs (head-percolation tables, rules to decide if an attachment should be made via substitution or adjunction, etc);\n- in syntactic parsing, supertagging lowers the grammar size impact in the parsing step but may lead to an empty parse forest --- this is not the case of our approach thanks to the companionship principle constraint;\n- in syntactic parsing, the parsing step may still have a high complexity (e.g. O(n^7) in the case of LTAGs) --- this is not the case of our approach where the last step admits a fast cubic-time algorithm by reduction to bipartite matching for which many efficient implementations exist.\n\n---\n\n*\"[...] such as Tree-LSTMs which is more flexible than a supertagging and would be more easily adapted to new domains\"*\n\nWe beg to differ here:\n\n(1) There is nothing to do in order to adapt our supertagger to a new domain. All supertags are automatically extracted from training data (lines 237-246).\n\n(2) On the contrary, the tree-LSTM based approach of Liu et al. (2021), called LEAR, requires domain expert adaptation of the composition operation in their model, see Section 6.3 of their paper: \"In addition, while our approach is general for various semantic parsing tasks, the collection of semantic operations needs to be redesigned for each task. We need to ensure that these semantic operations are k-ary projections [..], and all the meaning representations are covered by the operations collection. This is tractable, but still requires some efforts from domain experts\"\n\nAs such, our approach is easier than Liu et al's to adapt to new domains (in fact it is straightforward --- there is nothing to do).\n\n---\n\n*\"The model is only competitive with the baseline graph-based parser but not to other structural models such as Tree-LSTMs\"*\n\nOur approach achieves better or comparable scores compared to all previous models **except** on one type of generalization (Obj to Subj PP) where a single model (Tree-LSTM LEAR) achieves better results. Moreover, as stated above, Tree-LSTM LEAR requires very specific domain related configuration. Finally, Tree-LSTM LEAR requires many extra tricks to work: for example, in Section 4.2 of Liu et al (2021), they explain that they need to introduce constraints in the latent structure inference procedure and that their model cannot predict concepts spanning unseen word sequences (cf. 'Phrase Table Constraint' paragraph). Our model has no such limitation.\n\n---\n\n*\"Supertagging as an intermediate step may introduce more errors into the 3-stage semantic parsing pipeline in the paper which could be alleviated at least partially with an end2end model\"*\n\nThere are two types of errors that can be introduced by intermediary steps in a pipeline:\n\n(1) errors that makes the following steps infeasible: we ensure our approach never yield this kind of error via the \"companionship principle\"\n\n(2) prediction errors: it is known that end-to-end models fails on compositional generalization problems. On the contrary, our pipeline achieves better results.\n\nMoreover, note that many methods improving compositional generalization are based on pipelines. For example, the Tree-LSTM LEAR approach of Liu et al (2021) is based on a pipeline method (see Section 3 of their paper where they have first a composer and then an interpreter, and Figure 5 where they show a failure example due of the first step of their pipeline).\n\n---\n\n*\"Supertagging then parsing introduces additional challenges in itself; the authors have shown a few theorems to prove otherwise, but empirically it's widely known the large amount of ambiguity present after supertagging may be hard to resolve and in combination with parsing, it may make it even harder and this challenge itself may require neural models, so why not just use an end2end neural model for semantic parsing?\"*\n\nWe show in the paper that resolving can be reduced to bipartite matching (or assignment) in Section 3.2. Moreover, constraints in our supertagging scheme ensure  that the last step is feasible.\n\nOn *\"this challenge itself may require neural models\"*: note that a standard graph based parser has, on top of a neural encoder, two distinct layers that produce nodes scores and arc scores. To this, our method only adds one extra layer for supertag scores.\n\n\nFinally, we experimentally demonstrate that a simpler approach, without a supertagger, fails on COGS (which was known and previous papers have similar results), see \"Our baselines: Standard graph-based parser\" in Table 2.\n\n---\n\n*\"3: Could reproduce the results with some difficulty. The settings of parameters are underspecified or subjectively determined; the training/evaluation data are not widely available.\"*\n\nThe COGS dataset is available freely on github.\n\nOur neural network is very simple and fully described in appendix B, including training hyperparameters.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "* Semantic parsing still has some relevance in some domains\n* Supertagging used to reduce the search space of a semantic parser which shows some positive results", "reasons_to_reject": "* The model is only competitive with the baseline graph-based parser but not to other structural models such as Tree-LSTMs which is more flexible than a supertagging and would be more easily adapted to new domains\n* Supertagging as an intermediate step may introduce more errors into the 3-stage semantic parsing pipeline in the paper which could be alleviated at least partially with an end2end model\n* Supertagging then parsing introduces additional challenges in itself; the authors have shown a few theorems to prove otherwise, but empirically it's widely known the large amount of ambiguity present after supertagging may be hard to resolve and in combination with parsing, it may make it even harder and this challenge itself may require neural models, so why not just use an end2end neural model for semantic parsing? \n", "questions_to_authors": "", "paper_topic_and_main_contributions": "The papers extends a graph-based neural semantic parser with an additional intermediate supertagging step, the results of which are used for subsequent argument identification for the semantic parser. The supertagging accuracies are in the range of 75 to 100 on 3 different types, and when plugged into the semantic parser it helps significantly over the baseline without supertagging. The supertagging is realised using ILP. Compared with fully sequential baseline models such as seq2seq models the proposed model outperforms these; however, in comparison with structural models such as Tree-LSTMs it's on par on most categories except 1. ", "excitement": 2, "reproducibility": 3, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "e5DnYc9ikT", "reviewer": "Reviewer_KQiC", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer,\n\nThank you for your review.\n\nIndeed, we can extend the related work section to include analyses conducted with pre-trained neural networks. We apologize for this unintentional omission.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "Supertagging techniques and related techniques such as CCG are an important part of NLP literature but it is difficult to find its position for NLP today. This paper shows in a narrow semantic parsing domain how those techniques can be used and combined with existing mainstream learning techniques.\n\nThe paper proposes some concrete technical contribution (e.g. early stopping based solely on distribution iid to training) that might generalize beyond the scope of this paper; the novelty has proved to have a practical performance impact on the tested dataset.\n\nThe authors discussed the limitations with transparency and insights. ", "reasons_to_reject": "Although it is understandable that the paper doesn't compare to pretrained models, it would still be appreciated if some literature can be covered for their performance on COGs. That would help to complete the picture for performance on this dataset.\n\nSimilarly, the authors only use LSTM and mainly LSTM baselines, it would be good to know the transformer performance on this dataset as well (e.g. https://arxiv.org/pdf/2108.12284.pdf), for the reason of completeness.", "questions_to_authors": "", "paper_topic_and_main_contributions": "Inspired by traditional NLP supertagging success, the paper investigates in applying similar techniques to compositional semantic parsing. More concretely, between the more common graph parsing steps where it involves concept tagging and argument identification, the proposed algorithm inserts a semantic supertagging step between the above two steps.\n\nThe paper also contains some technical novelties put forward including that the argument identification is reduced to graph matching and the paper proposes a novel early stopping criteria with dev distribution different from the test distribution. \n\nThe paper tests the proposed framework on COGs and show that the supertagging introduction significantly improves the performance and the introduced techniques also help the performance. ", "excitement": 4, "reproducibility": 3, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"Typos_Grammar_Style_and_Presentation_Improvements": "Line 484: I think it is \"compared to\" "}, "extra_text": {}}, {"review_id": "6J0PTcTJgh", "reviewer": "Reviewer_6hiA", "summary": "", "questions": "1. The restrictions imposed by equation 4 in ln 268 does not take loops into account, right? Is there some other constraint that would prevent a combination of supertags that could only form a graph with a loop or did I miss something else entirely?\n2. Can you explain the reasoning behind the weakly supervised loss? I don't understand why there is a concept tagging stage if these are not part of the corpus anyways. At some point I convinced myself these are used to be able to assign an empty concept tag that filters \"unproductive\" words for the remainder of the parsing pipeline, but that would also be possible and easier to formulate with an empty supertag, imho.", "limitations": "", "rating": 4, "confidence": 2, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer,\n\nThank you for your review.\n\nIndeed, there is a mistake line 250. A supertag is a multiset, and S is a set of supertags. The empty supertag is an empty multiset $[[ ]]$. Hence, the correct formula is what you proposed (slighthly modified so that the empty supertag is not allowed):\n$$\nS = \\\\{ s^- \\cup s^+ | s^- \\in S^-, s^+ \\in S^+, s^- \\cup s^+ \\neq [[ ]] \\\\}\n$$\n\n\"The restrictions imposed by equation 4 in ln 268 does not take loops into account, right? \"\n\nNo, it does not prevent self-loops, but they never appear in practice.\n\n\"Can you explain the reasoning behind the weakly supervised loss?\"\n\nThere is a concept tagging stage (that also identifies semantically empty words --- i.e. words that do not trigger any concept). However, in many semantic parsing datasets, we do not know to which words are concept anchors, i.e. we cannot learn the concept tagger in a supervised fashion. For a given sentence all we observe is a sequence of words and a list of concepts, with no explicit correspondance between the two. The weakly supervised loss learns this alignment between words and concepts in an unsupervised fashion.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "To me, their additions seems like a solid approach to formalize local substructures in graphs and their experimental results give the same impression. The COGS corpus enables a focused evaluation of the structural generalization capabilities and fits very well to the contribution.", "reasons_to_reject": "There are some minor inconsistencies in notation and some details about the approach that I (as someone unfamiliar with this specific topic) did not completely understand (listed below). However, these could be easily ironed out in a camera-ready version.", "questions_to_authors": "1. The restrictions imposed by equation 4 in ln 268 does not take loops into account, right? Is there some other constraint that would prevent a combination of supertags that could only form a graph with a loop or did I miss something else entirely?\n2. Can you explain the reasoning behind the weakly supervised loss? I don't understand why there is a concept tagging stage if these are not part of the corpus anyways. At some point I convinced myself these are used to be able to assign an empty concept tag that filters \"unproductive\" words for the remainder of the parsing pipeline, but that would also be possible and easier to formulate with an empty supertag, imho.", "paper_topic_and_main_contributions": "This paper focuses on generalizations from substructures in the field of parsing for semantic graph representations. The authors define supertags that contain local graph fragments (incoming and outgoing edges with label) and add their prediction as a prepocessing step in the parsing process. The predicted supertags are constrained such that they must form a valid derivation. Their experiments suggest that this addition to the parsing pipeline increases overall parsing accuracy and specific scores intended to measure structural generalization in COGS compared to a baseline without the supertagging stage.", "excitement": 4, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {"Typos_Grammar_Style_and_Presentation_Improvements": "1. line 250: You use [[ ]] for the empty multiset in line 266 it's $\\emptyset$\n2. line 250 as well: $S^-$ and $S^+$ are sets of multisets and supertags are tuples over multisets, right? Then the empty tag should be ([[]], [[]]) and the exclusion denoted by $S = S^+ \\times S^- \\setminus \\\\{ ([[]], [[]]) \\\\}$. Or you could define supertags as multisets and the set $S$ as the unions of all pairs in $S^+$ and $S^-$ as the elements are disjoint anyways. Then $S = \\\\{ s^- \\cup s^+ \\mid s^- \\in S^-, s^+ \\in S^+ \\\\}$ would also fit into your notation.\n3. line 263: $x_\\emptyset$ -> $x_{i, \\emptyset}$\n4. there are some missing line numbers after line 266, in this block $S^+$ should be $S$ or $S^-$\n5. Table 4 in the appendix seems pointless to me, that could have been a footnote."}}]

Author rebuttal:

Meta-review: We had really abundant discussions regarding this work, which help clarify many important technique issues. Thank  reviewer Gx4y for the patience and hard work. Also thank the authors for detailed responses. Reviewer 6hiA resolved several math notation problems.
Based on the comments of all reviewers and authors’ rebuttal and my own reading of this paper, I think this work proposes a novel and correct three-step semantic parsing approach, which works well on the COGS dataset, especially from the structural generalization perspective. 

Three minor suggestions for improving this paper:

1)	For the first step, please give more explicit discussions on the one-word-one-concept assumption. For example, how does the assumption affect the proposed approach in the sense that how or whether it can be applied to other datasets, especially those in which the number of concepts are often larger than that of words. 

2)	I have a feeling that more results and analysis can make this more influential, especially from the  structural generalization perspective. Please use the extra page properly. 

3)	Can you add discussion about the following recent work (ACL-2023) in the next version? I think there is strong connection between your work and this one. Of course I understand the two approaches are different. 

> Compositional Generalization without Trees using Multiset Tagging and Latent Permutations Matthias Lindemann | Alexander Koller | Ivan Titov
Decision: Accept-Main