# Laziness Is a Virtue When It Comes to
Compositionality in Neural Semantic Parsing

Maxwell Crouse, Pavan Kapanipathi, Subhajit Chaudhury,
Tahira Naseem, Ramon Astudillo, Achille Fokoue, Tim Klinger
{ maxwell.crouse, subhajit, ramon.astudillo<EMAIL_ADDRESS>
{ kapanipa, tnaseem, achille, tklinger<EMAIL_ADDRESS>
IBM Research

###### Abstract

Nearly all general-purpose neural semantic parsers generate logical forms in a
strictly top-down autoregressive fashion. Though such systems have achieved
impressive results across a variety of datasets and domains, recent works have
called into question whether they are ultimately limited in their ability to
compositionally generalize. In this work, we approach semantic parsing from,
quite literally, the opposite direction; that is, we introduce a neural
semantic parsing generation method that constructs logical forms from the
bottom up, beginning from the logical form’s leaves. The system we introduce
is lazy in that it incrementally builds up a set of potential semantic parses,
but only expands and processes the most promising candidate parses at each
generation step. Such a parsimonious expansion scheme allows the system to
maintain an arbitrarily large set of parse hypotheses that are never realized
and thus incur minimal computational overhead. We evaluate our approach on
compositional generalization; specifically, on the challenging CFQ dataset and
three Text-to-SQL datasets where we show that our novel, bottom-up semantic
parsing technique outperforms general-purpose semantic parsers while also
being competitive with comparable neural parsers that have been designed for
each task.

##  1 Introduction

Compositionality is inherent to natural language, with the meaning of complex
text or speech understood through the composition of constituent words and
phrases Montague (1973). For instance, having observed the usage of phrases
like "edited by" and "directed by" in isolation, a human would be able to
easily understand the question "Was Toy Story edited by and directed by John
Lasseter?". The ability to take individual components and combine them
together in novel ways is known as compositional generalization, and is a key
feature of human intelligence that has been shown to play a significant role
in why humans are so efficient at learning Lake et al. (2017).

Compositional generalization has been identified as a major point of weakness
in neural methods for semantic parsing Lake and Baroni (2018); Higgins et al.
(2018). Accordingly, this deficiency has been taken up as a challenge by the
machine learning community, leading to a slew of methods Liu et al. (2021);
Herzig et al. (2021); Gai et al. (2021) and datasets Keysers et al. (2019);
Kim and Linzen (2020) targeted towards compositional generalization. However,
while there has been progress in determining factors that allow systems to
compositionally generalize Furrer et al. (2020); Oren et al. (2020), there yet
remains gaps in our understanding as to why these neural models fail.

(a) Top-down decoding (nodes drawn with dotted lines are those being
generated)

(b) Bottom-up decoding (nodes drawn with dotted lines are those being
generated)

Figure 1: Top-down versus bottom-up decoding strategies for the Geoquery
question "What rivers are in s0?"

In this paper, we posit that the failure of traditional neural semantic
parsers to compositionally generalize is in part due to how they build logical
forms. Most commonly, neural semantic parsers treat parsing as an encoder-
decoder problem, where the decoder generates logical forms from the top down
in an autoregressive fashion Dong and Lapata (2016); Xiao et al. (2016);
Alvarez-Melis and Jaakkola (2017); Krishnamurthy et al. (2017); Dong and
Lapata (2018). That is, these systems output a linearization of the target
logical form’s abstract syntax tree, beginning from the root of the tree,
where the generation of each token is conditioned on both the input text as
well as the entire sequence of previously generated tokens.

Such an entirely autoregressive decoding scheme, wherein the production of
each new token is conditioned on all previously generated tokens, could result
in models that assume invalid dependencies to exist between tokens and thus
overfit to their training data (as observed in Qiu et al. (2022); Bogin et al.
(2022)). We hypothesize that this overfitting problem would lessen the ability
of these models to generalize to unseen compositions.

Here we introduce an alternative decoding approach that eschews the top-down
generation paradigm, and instead uses a bottom-up mechanism that builds
upwards by combining entities and subexpressions together to form larger
subexpressions (Figure 1 demonstrates this distinction). Unlike top-down
approaches, our decoder generates logical forms by conditioning on only the
relevant subexpressions from the overall graph, hence improving compositional
generalizability.

Contributions: (a) We introduce a novel, bottom-up semantic parsing decoder
that achieves strong results, specifically with respect to compositional
generalization. (b) We evaluate our approach on CFQ Keysers et al. (2019),
three Text-to-SQL Finegan-Dollak et al. (2018) datasets, and Geoquery Zelle
and Mooney (1996), and find that it outperforms general-purpose semantic
parsers while also being competitive with comparable neural parsers that have
been designed for each task. (c) We demonstrate the flexibility of our
architecture by testing our approach with multiple encoders, showing that our
architecture almost always leads to a significant performance improvement. (d)
We show how the bottom-up paradigm can result in a combinatorial explosion in
the number of subexpressions created at each decoding step and propose a lazy
evaluation scheme that mitigates this by selectively expanding the logical
form in a way that minimizes computational overhead.

##  2 Representing Logical Forms

Our parser is intended to be task-agnostic, with as few as possible
assumptions made regarding the particular formalism (e.g., SQL, SPARQL, etc.)
a logical form may instantiate. We assume only that we have access to a
vocabulary $V$ that defines the set of all symbols a logical form could be
constructed from (with no restrictions imposed as to the label or arity of any
particular symbol) and that the logical form is given as an s-expression.

S-expressions are a representation formalism that expresses trees as nested
lists (e.g., (count $0 (river:t $0)) as a query for the question "How many
rivers are there?"). Their use dates back to the earliest days of artificial
intelligence research McCarthy (1983) as the main unit of processing of the
LISP programming language McCarthy (1978). In this work, their main purpose is
to simplify the structure of logical forms into binary trees. Importantly, the
transformation of logical forms into s-expressions requires no knowledge
beyond the syntax of the target formalism.

(a) Internal conversion of the logical form (count $0 (river:t $0)) into a
tree-based s-expression for the question "How many rivers are there?"

(b) DAG representation of an s-expression where identical subtrees have been
mapped to the same nodes

Figure 2: Preprocessing graph transformations

Traditionally, logical forms are generated as trees; however, we instead
represent them as directed acyclic graphs (DAGs). This is a logically
equivalent representation that is created by collapsing all identical subtrees
into a single subgraph that maintains connections to each of the original
parent nodes. Figure 2(a) provides an example of how an s-expression would
initially be converted into a tree representation, while Figure 2(b) shows how
two overlapping trees would be merged into a single DAG form. Within a graph
all nodes will either have 1) one argument and a label drawn from the
vocabulary of symbols V or 2) two arguments and connect an incomplete list
(its left argument) with a complete list (its right argument). The nodes with
two arguments will always use a special pointer symbol “$\boldsymbol{\cdot}$”
as their label.

As the final preprocessing step, each logical form is wrapped in a special
root s-expression. For instance, the logical form (count $0 (river:t $0))
would become (root (count $0 (river:t $0))). This step provides a signal to
the model to stop generating new extensions to the logical form. During
decoding, only those s-expressions that begin with a root token may be
returned to the user.

##  3 Model

Given a question $Q$, our method is tasked with producing a graph
representation $G$ of a logical form using symbols drawn from a vocabulary
$V$. At the highest level, our approach follows the traditional encoder-
decoder paradigm. It first parses the input with a neural encoder (e.g., LSTM
Hochreiter and Schmidhuber (1997)) to produce real-valued vector
representations for each word in $Q$. Those representations are then passed to
a neural decoder, which iteratively takes decoding actions to generate $G$.
Our approach is agnostic to the choice of encoder, and thus in the following
sections we will describe only the decoding process.

An important desideratum of this work was architectural simplicity. Thus, when
using a pretrained large language model as the base to our approach, (e.g., T5
Raffel et al. (2019)), the model was left largely as is. None of the
modifications described in the following sections involve changes to the
internal parameters or architecture of the neural model itself (i.e., all
additions are kept to the output layer). Consequently, when our approach is
instantiated with a pretrained language model, that model is applied entirety
off-the-shelf.

###  3.1 Decoding Actions

At each step of decoding, our system executes either a generation action or a
pointer action. Generation actions take a single node from $G$ and add it as
the argument to a new node with a label drawn from $V$. Pointer actions
instead take two nodes from $G$ and add them both as arguments to a new node
with a special pointer symbol “$\boldsymbol{\cdot}$” as its label. The
division of decoding into generation and pointer actions is adapted from Zhou
et al. (2021a, b), which proposes this scheme to drive a transition-based AMR
parser. Key to note is that both action types will result in a new node being
generated that has as arguments either one or two already-existing nodes from
$G$, i.e., a bottom-up generation process. Figure 3 illustrates the outcomes
of both action types.

Figure 3: Nodes in $G$ originating from generation actions (yellow) and from
pointer actions (blue).

At the start of decoding our approach initializes two objects, $G$ as the
empty graph and a set of candidate actions $A~{}=~{}\\{\left<\ \texttt{(}\
,\emptyset,1\right>\\}$. The first action of $A$ will always be to generate
the left parenthesis, which is the start to every s-expression in $G$. Each
decoding step begins by extending $G$ with actions drawn from $A$ and ends
with a set of new candidate actions being added to $A$.

The key to our approach lies in its lazy evaluation scheme, wherein actions
that create nodes are generated at each decoding step, rather than the nodes
themselves. This allows our model to strongly restrict how $G$ expands at each
decoding step, with our approach being able to build up a large set of
unexecuted actions representing candidate logical forms that are never
processed with resource-intensive neural components and thus incur very little
computational overhead.

###  3.2 Candidate Selection

Each element $a\in A$ is a tuple $a=\left<v,\mathcal{A},p_{a}\right>$
consisting of: 1) a symbol $v$ drawn from our vocabulary $V$, 2) an ordered
list of arguments $\mathcal{A}$, where each member of $\mathcal{A}$ is a node
in $G$, and 3) a probability $p_{a}$ reflective of the model’s confidence that
this candidate should be part of the final returned output. Adding a candidate
$a=\left<v,\mathcal{A},p_{a}\right>$ to $G$ simply involves creating a new
node labeled $v$ within $G$ that has directed edges connecting the node to
each argument in $\mathcal{A}$, as Figure 4 demonstrates.

Our model is equipped with a selection function that will select and remove
members of $A$ to add to $G$. In the experiments of this paper, our selection
function chooses all elements of $A$ with a probability above a certain
threshold $\kappa$ (e.g., $\kappa=0.5$) or, if no such options exist, chooses
the single highest probability option from $A$.

Figure 4: A generation action from A that, when selected and executed, adds a
node with label $0 to G

###  3.3 Graph Encoding

For our neural model to make predictions, it must first convert the newly
generated nodes into real-valued vector representations. The decoder of our
model largely follows the design of T5 Raffel et al. (2019), i.e., a
transformer Vaswani et al. (2017) using relative positional encodings Shaw et
al. (2018), but with modifications that allow it to process graph structure.
As most equations are the same as those detailed in the original T5 work, we
will only describe the differences between our model and theirs.

Throughout the remainder of this section, we will define a frontier $F$ to
refer to the set of nodes generated by actions in $A$ that were selected
during the current round of decoding. Each element of $F$ is first assigned a
vector embedding according to its label. The embedding is then passed through
the decoder to produce real-valued vector representations for each node. In
order to capture the structure of $G$ with the transformer, our model makes
use of two types of information within the attention modules of each layer of
the decoder.

First, within the self-attention module, a node $n\in G$ may only attend to
its set of descendants, i.e., only the nodes contained within the subgraph of
$G$ rooted at $n$. This has the effect that the resultant encoding of a node
is a function of only its descendants and the original text. Second, for a
pair of nodes $n_{i}$ and $n_{j}$ for which an attention score is being
computed (e.g., $n_{i}$ is the parent of $n_{j}$), the positional encoding
bias $b_{ij}$ used to represent the offset between $n_{i}$ and $n_{j}$ is
assigned according to a reverse post-order traversal of the descendants of
node $n_{i}$. That is, $b_{ij}$ is selected according to where $n_{j}$ is
positioned in a post-order traversal of the subgraph of $G$ rooted at $n_{i}$.
Figure 5 provides an example of this ordering scheme for a particular node.

This assignment strategy effectively linearizes the graph rooted at $n_{i}$
and has the added property that each descendant of $n_{i}$ will be assigned a
unique position bias with respect to $n_{i}$. This is also a somewhat
analogous encoding as to what is done for standard seq-to-seq models. To see
the similarity, consider a "linear" graph (e.g., a sequence); the encoding for
each node is exactly that given by a distance-based positional encoding Shaw
et al. (2018) (e.g., used by T5).

Figure 5: Reversed post-order traversal-based position assignment relative to
a newly generated node (colored in green). The number assigned to each node is
the index of the position bias (e.g., 0 would be assigned to bias $b_{0}$, 1
would be assigned to bias $b_{1}$, etc.)

###  3.4 Action Generation

Once the decoder has processed each node, our approach will have a set of node
embeddings $\\{h_{1},h_{2},\ldots h_{|F|}\\}$. To produce the set of decoding
actions, our model executes two operations (one for each action type). The
first operation proposes a set of generation actions (a brief depiction of
this is given in Figure 6). For a node $n_{i}$ and symbol $v$ with embedded
representations $h_{i}$ and $h_{v}$, respectively, this involves computing

$\displaystyle p_{i}^{(v)}$
$\displaystyle=\sigma\big{(}h_{i}^{\top}h_{v}+b\big{)}$

where $b$ is a bias term and $\sigma$ is the sigmoid function. The value
$p_{i}^{(v)}$ can be interpreted as the independent probability (independent
of all other action probabilities) that $G$ should contain a node with label
$v\in V$ that has $n_{i}$ as an argument. For each $v\in V$, $A$ is extended
as $A=A\cup\\{\big{<}v,\left<n_{i}\right>,p_{i}^{(v)}\cdot
p_{n_{i}}\big{>}\\}$, where $p_{n_{i}}$ refers to the probability of the
original action that generated $n_{i}$.

Figure 6: The embeddings of nodes in the frontier F and the embeddings of
symbols in the vocabulary V being used to construct new generation actions

The second operation proposes a set of pointer actions using an attention
mechanism. For a pair of nodes $\big{<}n_{i},n_{j}\big{>}$ with embedded
representations $h_{i}$ and $h_{j}$, respectively, this is computed as

$\displaystyle q_{i}$ $\displaystyle=W^{(q)}h_{i},\;\;\;\;k_{j}=W^{(k)}h_{j}$
$\displaystyle p_{i}^{(j)}$
$\displaystyle=\sigma\big{(}\dfrac{q^{\top}_{i}k_{j}}{\sqrt{d}}+b\big{)}$

where $W^{(q)}$, $W^{(k)}$ are learned matrices, $b$ is a bias term, $d$ is
the dimensionality of the embeddings, and $\sigma$ is the sigmoid function.
Like before, $p_{i}^{(j)}$ can be thought of as the independent probability
that $G$ will contain a node that has $n_{i}$ as its left argument and $n_{j}$
as its right argument. For each pair $\left<n_{i},n_{j}\right>\in(F\times
G)\cup(G\times F)$ (where $F\cup G$ is a slight abuse of notation to write the
union between $F$ and the set of nodes within $G$), we update the set of
actions $A=A\cup\\{\big{<}\ \boldsymbol{\cdot}\
,\left<n_{i},n_{j}\right>,p^{(j)}_{i}\cdot p_{n_{i}}\cdot
p_{n_{j}}\big{>}\\}$, where $p_{n_{i}}$ and $p_{n_{j}}$ refer to the
probabilities of the original actions that generated $n_{i}$ and $n_{j}$.

It is important to note the combinatorial nature of generating new actions. At
each round of decoding, the number of actions could grow by
$O(|F|\cdot|V|+|F|\cdot|G|)$. While it is certainly possible to restrict the
number of actions added to A (e.g., by adding only the top-$k$ actions), the
set still grows extremely quickly.

A key feature to our decoding scheme is that it does not actually build and
embed the graphs for a particular action until that action is executed.
Because each action maintains the probability of its source actions, our model
is effectively exploring via Dijkstra’s algorithm, where the frontier F
includes all actions yet to be executed. This contrasts with previous works,
e.g., Rubin and Berant (2021), which are greedier in that they keep a fixed
beam with new nodes that are added and embedded on each round and all nodes
outside this beam being discarded (our approach does not need to discard these
nodes since they have no significant cost until they are executed).

###  3.5 Terminating Decoding

Decoding terminates when an s-expression beginning with the root token is
generated (refer to the end of Section 2 for an example). In order to ensure
the highest probability s-expression is returned, decoding only terminates if
the final action’s probability is also the highest amongst all yet-unselected
actions in $A$. Upon generating the root s-expression, only the subgraph of
$G$ rooted at the newly generated node is returned. Thus, though the the size
of $G$ may grow to be quite large, not every element of $G$ is returned.

###  3.6 Training

Training our model is as efficient as other standard transformer-based models,
i.e., a single parallel operation that processes the entire graph and computes
all action probabilities simultaneously. Additionally, the memory footprint of
our model is practically equivalent to the underlying transformer used to
initialize its parameters (e.g., T5).

The loss function used to train our model is a cross-entropy-based loss.
Recall that both generation and pointer action probabilities are the output of
a sigmoid function. Letting $Q$ be the input question, $\mathcal{P}$ be the
set of positive actions (i.e., actions needed to generate the gold-annotation
logical form), and $\mathcal{N}$ be the set of negative actions (i.e., actions
not needed to generate the gold-annotation logical form), the objective is
written as

$\displaystyle\mathcal{L}$
$\displaystyle=\sum_{n\in\mathcal{P}}\log{p_{\theta}(n|Q)}+\sum_{n\in\mathcal{N}}\log{1-p_{\theta}(n|Q)}$

where the conditional probabilities $p_{\theta}(n|Q)$ are the sigmoid-
constrained outputs of generation (see Section 3.4) and $\theta$ is the set of
model parameters.

While $\mathcal{P}$ is fixed and finite, the set $\mathcal{N}$ is clearly
unbounded. In this work, we construct $\mathcal{N}$ from a small set of both
generation and pointer actions. For each node $n\in G$, we add negative
generation actions for each symbol $v\in V$ that is not the label of a parent
of $n$. For negative pointer actions, we add actions for each pair of nodes in
$G$ that do not have a common parent.

##  4 Experiments

(SELECT (count *) (WHERE
(directed_by M0 M1)
(directed_by M0 M2)
(edited_by M0 M1)
(edited_by M0 M2)
(prod_companies M0 M1)
(prod_companies M0 M2)))

Figure 7: S-expression for the CFQ question "Was M0 produced, directed, and
edited by M1 and M2"

In our experiments, we aimed to answer the following questions: 1) is bottom-
up a more effective decoding paradigm than top-down with respect to
compositional generalization and 2) how well does our approach generalize to
different domains and formalisms. To answer these questions, we evaluated our
approach on several datasets: 1) CFQ Keysers et al. (2019), 2) the SQL
versions of Geoquery Zelle and Mooney (1996), ATIS Dahl et al. (1994), and
Scholar Iyer et al. (2017), each of which were curated by Finegan-Dollak et
al. (2018), and 3) the version of Geoquery Zelle and Mooney (1996) used by
Dong and Lapata (2016); Kwiatkowski et al. (2011) which maps questions to a
variant of typed lambda calculus Carpenter (1997). To save space, we provide
all hyperparameters used for our experiments in the appendix.

Our main experiments investigating compositional generalization were performed
on the CFQ and Text-to-SQL datasets. In CFQ, the distribution of train and
test data in each split is designed to exhibit maximum compound divergence
(MCD) Keysers et al. (2019). In the MCD setting, data is comprised of a fixed
set of atoms, i.e., the primitive elements to a question. But while each atom
is observed in training, the compositions of atoms between train and test sets
will vary significantly (an example of a CFQ question is provided in Figure
7). In the Text-to-SQL datasets, the train and test sets are constructed by
using separate template splits Finegan-Dollak et al. (2018); Herzig et al.
(2021), where the train and test sets have questions involving different SQL
query templates.

Method | MCD1 | MCD2 | MCD3 | MCD Avg.
---|---|---|---|---
Dynamic Least-to-Most Prompting Drozdov et al. (2022) | 94.3 | 95.3 | 95.5 | 95.0
LEAR Liu et al. (2021) | 91.7 | 89.2 | 91.7 | 90.9
LIR+RIR (T5-3B) Herzig et al. (2021) | 88.4 | 85.3 | 77.9 | 83.8
Grounded Graph Decoding Gai et al. (2021) | 98.6 | 67.9 | 77.4 | 81.3
HPD Guo et al. (2020) | 79.6 | 59.6 | 67.8 | 69.0
LIR+RIR (T5-base) Herzig et al. (2021) | 85.8 | 64.0 | 53.6 | 67.8
T5-11B-mod Furrer et al. (2020) | 61.6 | 31.3 | 33.3 | 42.1
LAGR Jambor and Bahdanau (2021) | 57.9 | 26.0 | 20.9 | 34.9
T5-3B Herzig et al. (2021) | 65.0 | 41.0 | 42.6 | 49.5
T5-base Herzig et al. (2021) | 58.5 | 27.0 | 18.4 | 34.6
Edge Transformer Bergen et al. (2021) | 47.7 | 13.1 | 13.2 | 24.7
Evolved Transformer Keysers et al. (2019) | 42.4 | 9.3 | 10.8 | 20.8
Universal Transformer Keysers et al. (2019) | 37.4 | 8.1 | 11.3 | 18.9
Transformer Keysers et al. (2019) | 34.9 | 8.2 | 10.6 | 17.8
LSTM Keysers et al. (2019) | 28.9 | 5.0 | 10.8 | 14.9
LSP (Ours) |  |  |  |
\+ T5-base | 88.7 | 57.7 | 43.8 | 63.4
\+ LSTM Encoder | 73.0 | 29.5 | 23.1 | 41.9
Table 1: Performance across different splits of the CFQ dataset. Those systems leveraging CFQ-specific algorithms or representations are grouped in the top half of the table, while those systems in the bottom half are domain general Method | ATIS | Geoquery | Scholar
---|---|---|---
Seq2Seq $\clubsuit$ | 32.0 | 20.0 | 5.0
GECA $\diamondsuit$ | 24.0 | 52.1 | –
Seq2Seq $\spadesuit$ | 28.0 | 48.5 | –
Transformer $\spadesuit$ | 23.0 | 53.9 | –
Seq2Seq+ST $\spadesuit$ | 29.1 | 63.6 | –
Transformer+ST $\spadesuit$ | 28.6 | 61.9 | –
SpanBasedSP $\square$ | – | 82.2 | –
Baseline (T5-base) $\heartsuit$ | 32.9 | 79.7 | 18.1
Baseline (T5-large) $\heartsuit$ | 31.4 | 81.9 | 17.5
Baseline (T5-3B) $\heartsuit$ | 29.7 | 79.7 | 16.2
LIR+RIR (T5-base) $\heartsuit$ | 47.8 | 83.0 | 20.0
LIR+RIR (T5-large) $\heartsuit$ | 43.2 | 79.7 | 22.0
LIR+RIR (T5-3B) $\heartsuit$ | 28.5 | 75.8 | 12.4
LSP (Ours) |  |  |
\+ T5-base | 38.3 | 81.3 | 25.1
Table 2: Performance on Text-to-SQL against: $\clubsuit$Finegan-Dollak et al. (2018), $\diamondsuit$Andreas (2020), $\spadesuit$Zheng and Lapata (2020), $\heartsuit$Herzig et al. (2021), $\square$Herzig and Berant (2021) Method | Acc.
---|---
DCS+L w/ lexicon Liang et al. (2013) | 91.1
TISP Zhao and Huang (2015) | 88.9
KZGS11 Kwiatkowski et al. (2011) | 88.6
DCS+L w/o lexiconLiang et al. (2013) | 87.9
AQA Crouse (2021) | 87.5
$\lambda$-WASP Wong and Mooney (2007) | 86.6
ZC07 Zettlemoyer and Collins (2007) | 86.1
AWP + AE + C2 Jia and Liang (2016) | 89.3
Graph2Tree Li et al. (2020) | 88.9
Coarse2Fine Dong and Lapata (2018) | 88.2
Seq2Tree Dong and Lapata (2016) | 87.1
SpanbasedSP Herzig and Berant (2021) | 86.4
Graph2Seq Xu et al. (2018) | 85.7
LSP (Ours) |
\+ LSTM Encoder | 86.4
Table 3: Performance on Geoquery, with neural-based approaches grouped in the
bottom half of the table

###  4.1 Dataset-Specific Processing

Task-specific representations and encoding schemes are very common with state-
of-the-art approaches for compositional generalization Shaw et al. (2021).
Most often, such approaches will transform the target logical form to better
reflect some characteristic of the input text. For instance, with CFQ, systems
will transform their target logical forms into a query that closely aligns
with the list-heavy syntactic structure of CFQ questions Liu et al. (2021);
Herzig et al. (2021); Jambor and Bahdanau (2021); Furrer et al. (2020).

As our objective was to determine the effectiveness of our bottom-up technique
for general-purpose semantic parsing, we avoided any transformation that
involved task-specific knowledge about the input text. For the Text-to-SQL and
Geoquery datasets, we performed no processing of the inputs or outputs beyond
the transformation of input logical forms into s-expressions. For CFQ, we
found it necessary to apply two preprocessing steps. First, to mitigate the
number of candidate logical forms proposed, only one WHERE clause was allowed
to be generated during decoding. Second, we observed that, because we
restricted the number of WHERE clauses generated, our method often prematurely
ended generation. Thus, we found it useful to add any completed s-expression
(i.e., s-expressions ending with the ) token) to the WHERE clause of the final
logical form.

###  4.2 Evaluation

We evaluated our approach using exact match accuracy, i.e., whether the
generated logical form exactly matches the gold logical form annotation. To
accommodate for unordered $n$-ary predicates, we reordered the arguments to
all such unordered predicates (e.g., and) lexicographically in both the gold
and generated logical forms before comparing them. The unordered predicates
are the WHERE operator in CFQ as well as the and predicate in the lambda
calculus version of Geoquery.

##  5 Results and Discussion

Table 1 shows the results of our approach, referred to as LSP (Lazy Semantic
Parser), on the CFQ dataset. As can be seen from the table, our approach fares
quite well against domain-general semantic parsing approaches and,
importantly, significantly outperforms both T5-base and the LSTM.

The large performance increase as compared to both the basic LSTM and T5-base
supports our hypothesis that a bottom-up, semi-autoregressive decoding
strategy is a better inductive bias for compositional generalization than
autoregressive, top-down decoding. However, a better decoding strategy clearly
does not provide the complete solution, as evidenced by the gap in performance
between the best systems designed specifically for compositional
generalization and our approach.

Table 2 shows the performance of our approach on the three Text-to-SQL
datasets of Finegan-Dollak et al. (2018). While our approach clearly
outperforms the baselines, it has mixed results as compared to the work of
Herzig et al. (2021). Additionaly, our approach was outperformed by Herzig and
Berant (2021) on the Geoquery SQL dataset; however we note that their approach
required a manually constructed lexical mapping of text to Geoquery terms
(they reached 65.9% accuracy without the mapping). Still, that our approach
outperformed T5-base in all three datasets again supports our hypothesis that
bottom-up is more effective for compositional generalization.

Method | MCD1 | MCD2 | MCD3 | ATIS | Geoquery | Scholar
---|---|---|---|---|---|---
T5-base | 58.5 | 27.0 | 18.4 | 32.9 | 79.7 | 18.1
RIR | 86.3 | 49.1 | 46.8 | 81.3 | 36.3 | 19.4
LIRd | 48.1 | 40.3 | 35.3 | 44.4 | 83.5 | 20.6
LIRd+RIR | 72.5 | 61.1 | 51.2 | 47.8 | 83.0 | 20.0
LIRind | 57.6 | 41.4 | 34.7 | 38.3 | 80.8 | 16.5
LIRind+RIR | 85.8 | 64.0 | 53.6 | 41.5 | 81.9 | 16.5
LSP (Ours) |  |  |  |  |  |
\+ T5-base | 88.7 | 57.7 | 43.8 | 38.3 | 81.3 | 25.1
Table 4: Performance as compared to task-specific T5-base models from Herzig
et al. (2021).

Table 3 shows the performance of our approach on Geoquery. To keep the
comparison relatively fair, we used only an LSTM encoder and randomly
initialized token embeddings for this experiment. Despite using an entirely
different generation scheme, our method is competitive with the other neural-
based semantic parsers on this dataset. Notably, there is not a significant
drop from Seq2Tree Dong and Lapata (2016), which can be considered the
antithesis to our method as it decodes trees from the top down. We find these
results to be very encouraging, as our approach maintains competitive
performance against a varied set of approaches that leverage hand-engineered
data augmentation strategies Jia and Liang (2016), pretrained word embeddings
Li et al. (2020), and hand-built lexicons Herzig and Berant (2021).

Lastly, in Table 4 we highlight the T5-base models of Herzig et al. (2021),
which used task-specific intermediate representations to simplify the learning
problem of semantic parsing for an off-the-shelf large language model. This is
a very useful work to compare against, as the number of parameters between our
model and theirs is near identical. From the table, we see that our approach
roughly matches that of their best performing T5-base model. This is an
interesting result, as it could suggest that our architecture is naturally
capturing the useful properties of their intermediate representations without
as much need for hand-engineering. Importantly, unlike their approach which
assumes knowledge of the syntactic structure of questions, ours needs only a
rule for identifying expressions (e.g., parentheses delineate expression
boundaries) or a grammar for the target (readily available for formalisms like
SPARQL or SQL).

##  6 Related Work

While the overall parsing approach of Zhou et al. (2021a, b) is quite
different from ours (as they propose a transition-based semantic parser),
several aspects of our work were inspired from their ideas. For instance, as
mentioned in Section 3.3, they proposed the use of two types of decoding
actions to expand the target graph.

Bottom-up neural semantic parsers are a relatively recent development. Most
related to our work is that of Rubin and Berant (2021), which introduced a
bottom-up system that achieved near state-of-the-art results on the Spider
dataset Yu et al. (2018) while being significantly more computationally
efficient than its top-down, autoregressive competitors. There are three
significant differences between their approach and ours. First, they generate
trees rather than DAGs and thus assume a many-to-one correspondence between
input spans in the question and tokens in the logical form (which does not
hold for datasets like CFQ). Second, they use an eager evaluation scheme
(i.e., nodes are generated at each decoding step and not actions), and thus
enforce a beam-size hyperparameter $K$ that must be defined a priori and
places a hard limit on the number of subtrees that can be considered at a
given time. Third, they use a highly customized decoder which limits how
tightly integrated their approach can be with off-the-shelf language models.
In contrast, when using a pretrained large language model as the base to our
approach, we reuse the entirety of the language model as is to instantiate our
model.

Another similar work is Herzig and Berant (2021), which introduced a method
that learned to predict span trees over the input question that could be
composed together to build complete logical forms. Their method achieves
strong performance on the Geoquery SQL dataset Finegan-Dollak et al. (2018);
however, similar to Rubin and Berant (2021), their approach differs from ours
in that they assume a one-to-one correspondence between disjoint spans of the
question and disjoint subtrees of the logical form. Further, their method can
only handle inputs whose parse falls into a restricted class of non-projective
trees, where the authors note that extending their method to all classes of
non-projective trees would prohibitively increase the time complexity of their
parser. Such assumptions make it unclear how it would directly apply to a more
complex dataset like CFQ.

There are several works targeted specifically towards compositional
generalization Gai et al. (2021); Liu et al. (2021); Jambor and Bahdanau
(2021); Guo et al. (2020); Herzig et al. (2021). Though these systems have
proven to be quite effective on compositional generalization datasets, they
make significant task-specific assumptions that limit how they might be
applied more broadly.

##  7 Limitations

The main limitation to our work lies in the handling of unordered $n$-ary
relations. We hypothesize that the bottom-up paradigm performs best when there
is one unambiguous logical form to generate for a particular question. While
this is quite often true for semantic parsing, in our experience, unordered
$n$-ary relations (e.g., WHERE) can quickly cause this not to be the case.
With such relations, there tends to be a large number of correct logical forms
for a particular question. In these situations, having so many candidate
logical forms can cause significant issues in terms of runtime. A second
limitation of our work is that it assumes the logical form will be given as a
graph. Thus, there is an annotation burden on the users of this system that
would not be present in systems that treat semantic parsing as a text-to-text
problem (e.g., fine-tuned large language models).

##  8 Conclusions

In this work, we introduced a novel, bottom-up decoding scheme that semi-
autoregressively constructs logical forms in a way that facilitates
compositional generalization. Key to our method was a lazy generation process
designed to address the computational efficiency issues inherent to bottom-up
parsing. We demonstrated our approach on five different datasets covering
three logical formalisms and found that our approach was strongly competitive
with neural models tailored to each task.

## References

  * Alvarez-Melis and Jaakkola (2017) David Alvarez-Melis and T. Jaakkola. 2017.  Tree-structured decoding with doubly-recurrent neural networks.  In _ICLR_.
  * Andreas (2020) Jacob Andreas. 2020.  Good-enough compositional data augmentation.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 7556–7566.
  * Bergen et al. (2021) Leon Bergen, Timothy O’Donnell, and Dzmitry Bahdanau. 2021.  Systematic generalization with edge transformers.  _Advances in Neural Information Processing Systems_ , 34.
  * Bogin et al. (2022) Ben Bogin, Shivanshu Gupta, and Jonathan Berant. 2022.  Unobserved local structures make compositional generalization hard.  In _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing_ , pages 2731–2747, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
  * Carpenter (1997) Bob Carpenter. 1997.  Type-logical semantics.
  * Crouse (2021) Maxwell Crouse. 2021.  _Question-Answering with Structural Analogy_.  Ph.D. thesis, Northwestern University.
  * Dahl et al. (1994) Deborah A Dahl, Madeleine Bates, Michael K Brown, William M Fisher, Kate Hunicke-Smith, David S Pallett, Christine Pao, Alexander Rudnicky, and Elizabeth Shriberg. 1994.  Expanding the scope of the atis task: The atis-3 corpus.  In _Human Language Technology: Proceedings of a Workshop held at Plainsboro, New Jersey, March 8-11, 1994_.
  * Dong and Lapata (2016) Li Dong and Mirella Lapata. 2016.  Language to logical form with neural attention.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 33–43, Berlin, Germany. Association for Computational Linguistics.
  * Dong and Lapata (2018) Li Dong and Mirella Lapata. 2018.  Coarse-to-fine decoding for neural semantic parsing.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 731–742, Melbourne, Australia. Association for Computational Linguistics.
  * Drozdov et al. (2022) Andrew Drozdov, Nathanael Schärli, Ekin Akyürek, Nathan Scales, Xinying Song, Xinyun Chen, Olivier Bousquet, and Denny Zhou. 2022.  Compositional semantic parsing with large language models.  _arXiv preprint arXiv:2209.15003_.
  * Finegan-Dollak et al. (2018) 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 1: Long Papers)_ , pages 351–360.
  * Furrer et al. (2020) Daniel Furrer, Marc van Zee, Nathan Scales, and Nathanael Schärli. 2020.  Compositional generalization in semantic parsing: Pre-training vs. specialized architectures.  _arXiv preprint arXiv:2007.08970_.
  * Gai et al. (2021) Yu Gai, Paras Jain, Wendi Zhang, Joseph Gonzalez, Dawn Song, and Ion Stoica. 2021\.  Grounded graph decoding improves compositional generalization in question answering.  In _Findings of the Association for Computational Linguistics: EMNLP 2021_ , pages 1829–1838.
  * Guo et al. (2020) Yinuo Guo, Zeqi Lin, Jian-Guang Lou, and Dongmei Zhang. 2020.  Hierarchical poset decoding for compositional generalization in language.  _Advances in Neural Information Processing Systems_ , 33.
  * Herzig and Berant (2021) Jonathan Herzig and Jonathan Berant. 2021.  Span-based semantic parsing for compositional generalization.  In _ACL/IJCNLP_.
  * Herzig et al. (2021) Jonathan Herzig, Peter Shaw, Ming-Wei Chang, Kelvin Guu, Panupong Pasupat, and Yuan Zhang. 2021.  Unlocking compositional generalization in pre-trained models using intermediate representations.  _arXiv preprint arXiv:2104.07478_.
  * Higgins et al. (2018) Irina Higgins, Nicolas Sonnerat, Loic Matthey, Arka Pal, Christopher P Burgess, Matko Bošnjak, Murray Shanahan, Matthew Botvinick, Demis Hassabis, and Alexander Lerchner. 2018.  Scan: Learning hierarchical compositional visual concepts.  In _International Conference on Learning Representations_.
  * Hochreiter and Schmidhuber (1997) Sepp Hochreiter and Jürgen Schmidhuber. 1997.  Long short-term memory.  _Neural computation_ , 9(8):1735–1780.
  * Iyer et al. (2017) Srinivasan Iyer, Ioannis Konstas, Alvin Cheung, Jayant Krishnamurthy, and Luke Zettlemoyer. 2017.  Learning a neural semantic parser from user feedback.  In _55th Annual Meeting of the Association for Computational Linguistics_.
  * Jambor and Bahdanau (2021) Dora Jambor and Dzmitry Bahdanau. 2021.  Lagr: Labeling aligned graphs for improving systematic generalization in semantic parsing.  _arXiv preprint arXiv:2110.07572_.
  * Jia and Liang (2016) Robin Jia and Percy Liang. 2016.  Data recombination for neural semantic parsing.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 12–22, Berlin, Germany. Association for Computational Linguistics.
  * Keysers et al. (2019) Daniel Keysers, Nathanael Schärli, Nathan Scales, Hylke Buisman, Daniel Furrer, Sergii Kashubin, Nikola Momchev, Danila Sinopalnikov, Lukasz Stafiniak, Tibor Tihon, et al. 2019.  Measuring compositional generalization: A comprehensive method on realistic data.  In _International Conference on Learning Representations_.
  * Kim and Linzen (2020) Najoung Kim and Tal Linzen. 2020.  Cogs: A compositional generalization challenge based on semantic interpretation.  _arXiv preprint arXiv:2010.05465_.
  * Krishnamurthy et al. (2017) Jayant Krishnamurthy, Pradeep Dasigi, and Matt Gardner. 2017.  Neural semantic parsing with type constraints for semi-structured tables.  In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing_ , pages 1516–1526, Copenhagen, Denmark. Association for Computational Linguistics.
  * Kwiatkowski et al. (2011) Tom Kwiatkowski, Luke Zettlemoyer, Sharon Goldwater, and Mark Steedman. 2011.  Lexical generalization in ccg grammar induction for semantic parsing.  In _Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing_ , pages 1512–1523.
  * Lake and Baroni (2018) Brenden Lake and Marco Baroni. 2018.  Generalization without systematicity: On the compositional skills of sequence-to-sequence recurrent networks.  In _International conference on machine learning_ , pages 2873–2882. PMLR.
  * Lake et al. (2017) Brenden M Lake, Tomer D Ullman, Joshua B Tenenbaum, and Samuel J Gershman. 2017\.  Building machines that learn and think like people.  _Behavioral and brain sciences_ , 40.
  * Li et al. (2020) Shucheng Li, Lingfei Wu, Shiwei Feng, Fangli Xu, Fengyuan Xu, and Sheng Zhong. 2020\.  Graph-to-tree neural networks for learning structured input-output translation with applications to semantic parsing and math word problem.  _EMNLP_.
  * Liang et al. (2013) Percy Liang, Michael I Jordan, and Dan Klein. 2013.  Learning dependency-based compositional semantics.  _Computational Linguistics_ , 39(2):389–446.
  * Liu et al. (2021) Chenyao Liu, Shengnan An, Zeqi Lin, Qian Liu, Bei Chen, Jian-Guang Lou, Lijie Wen, Nanning Zheng, and Dongmei Zhang. 2021.  Learning algebraic recombination for compositional generalization.  In _Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021_ , pages 1129–1144.
  * McCarthy (1978) John McCarthy. 1978.  History of lisp.  In _History of programming languages_ , pages 173–185.
  * McCarthy (1983) John McCarthy. 1983.  Recursive functions of symbolic expressions.  In _Programming Languages_ , pages 175–186. Springer.
  * Montague (1973) Richard Montague. 1973.  The proper treatment of quantification in ordinary english.  In _Approaches to natural language_ , pages 221–242. Springer.
  * Oren et al. (2020) Inbar Oren, Jonathan Herzig, Nitish Gupta, Matt Gardner, and Jonathan Berant. 2020\.  Improving compositional generalization in semantic parsing.  In _EMNLP (Findings)_.
  * Qiu et al. (2022) Linlu Qiu, Peter Shaw, Panupong Pasupat, Tianze Shi, Jonathan Herzig, Emily Pitler, Fei Sha, and Kristina Toutanova. 2022.  Evaluating the impact of model scale for compositional generalization in semantic parsing.  In _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing_ , pages 9157–9179, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
  * Raffel et al. (2019) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. 2019.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _arXiv preprint arXiv:1910.10683_.
  * Rubin and Berant (2021) Ohad Rubin and Jonathan Berant. 2021.  Smbop: Semi-autoregressive bottom-up semantic parsing.  In _Proceedings of the 5th Workshop on Structured Prediction for NLP (SPNLP 2021)_ , pages 12–21.
  * Shaw et al. (2021) Peter Shaw, Ming-Wei Chang, Panupong Pasupat, and Kristina Toutanova. 2021.  Compositional generalization and natural language variation: Can a semantic parsing approach handle both?  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 922–938.
  * Shaw et al. (2018) Peter Shaw, Jakob Uszkoreit, and Ashish Vaswani. 2018.  Self-attention with relative position representations.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers)_ , pages 464–468.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  In _Advances in neural information processing systems_ , pages 5998–6008.
  * Wong and Mooney (2007) Yuk Wah Wong and Raymond Mooney. 2007.  Learning synchronous grammars for semantic parsing with lambda calculus.  In _Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics_ , pages 960–967.
  * Xiao et al. (2016) Chunyang Xiao, Marc Dymetman, and Claire Gardent. 2016.  Sequence-based structured prediction for semantic parsing.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1341–1350, Berlin, Germany. Association for Computational Linguistics.
  * Xu et al. (2018) Kun Xu, Lingfei Wu, Zhiguo Wang, Yansong Feng, Michael Witbrock, and Vadim Sheinin. 2018.  Graph2seq: Graph to sequence learning with attention-based neural networks.  _arXiv preprint arXiv:1804.00823_.
  * Yu et al. (2018) Tao Yu, Rui Zhang, Kai-Chou Yang, Michihiro Yasunaga, Dongxu Wang, Zifan Li, James Ma, Irene Z Li, Qingning Yao, Shanelle Roman, Zilin Zhang, and Dragomir R. Radev. 2018.  Spider: A large-scale human-labeled dataset for complex and cross-domain semantic parsing and text-to-sql task.  In _EMNLP_.
  * Zelle and Mooney (1996) John M Zelle and Raymond J Mooney. 1996.  Learning to parse database queries using inductive logic programming.  In _Proceedings of the national conference on artificial intelligence_ , pages 1050–1055.
  * Zettlemoyer and Collins (2007) Luke Zettlemoyer and Michael Collins. 2007.  Online learning of relaxed ccg grammars for parsing to logical form.  In _Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL)_ , pages 678–687.
  * Zhao and Huang (2015) Kai Zhao and Liang Huang. 2015.  Type-driven incremental semantic parsing with polymorphism.  In _Proceedings of the 2015 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 1416–1421.
  * Zheng and Lapata (2020) Hao Zheng and Mirella Lapata. 2020.  Compositional generalization via semantic tagging.  _arXiv preprint arXiv:2010.11818_.
  * Zhou et al. (2021a) Jiawei Zhou, Tahira Naseem, Ramón Fernandez Astudillo, and Radu Florian. 2021a.  Amr parsing with action-pointer transformer.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 5585–5598.
  * Zhou et al. (2021b) Jiawei Zhou, Tahira Naseem, Ramón Fernandez Astudillo, Young-Suk Lee, Radu Florian, and Salim Roukos. 2021b.  Structure-aware fine-tuning of sequence-to-sequence transformers for transition-based amr parsing.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 6279–6290.

##  Appendix A Appendix

###  A.1 Dataset Sizes

Dataset | Split | Train | Test
---|---|---|---
CFQ | MCD1 | 95k | 12k
| MCD2 | 95k | 12k
| MCD3 | 95k | 12k
Text-To-SQL | ATIS | 4812 | 347
| Geoquery | 539 | 182
| Scholar | 408 | 315
Geoquery | - | 600 | 280
Table 5: Dataset sizes

Geoquery Zelle and Mooney (1996) is a standard benchmark dataset for semantic
parsing that consists of 880 geography-related questions. We use the standard
Zettlemoyer and Collins (2007) split of 600 train questions and 280 test
questions and the logical form representation of Dong and Lapata (2016);
Kwiatkowski et al. (2011), which is a variant of typed lambda calculus
Carpenter (1997).

###  A.2 Training Details

All models were trained on an HPC cluster, where each training run was
provided with 100 GB RAM, 2 CPUs, and 1 V100 GPU. The longest training run (on
CFQ with T5-base) would complete within 24 hours.

###  A.3 Model Sizes

The T5-base models have around 220 million parameters. As our model shares all
parameters with T5 except for the final attention-based pointer module, a
rough estimate is that our model would have approximately 221 million
parameters (with $768\times 768$ additional parameters from the attention
module).

###  A.4 Hyperparameters

We did not do much in the way of hyperparameter tuning, instead opting to base
most values off of the original CFQ Keysers et al. (2019) work and sharing
most hyperparameter settings between our experiments. In Tables 6 and 7, we
list the hyperparameters used in both experiments.

Hyperparameter | CFQ | Text-to-SQL | Geoquery
---|---|---|---
Embedding dimensionality | 256 | 256 | 256
Number of MHA heads | 8 | 8 | 8
Dimensionality of FFN hidden layers | 1024 | 1024 | 1024
Encoder Dropout | 0.4 | 0.4 | 0.4
Decoder Dropout | 0.1 | 0.1 | 0.1
Batch size | 32 | 32 | 32
Learning rate | 0.0001 | 0.001 | 0.001
Number of training epochs | 100 | 500 | 500
Table 6: Hyperparameters for CFQ, Text-to-SQL, and Geoquery experiments when an LSTM encoder was used Hyperparameter | CFQ | Text-to-SQL
---|---|---
Embedding dimensionality | 768 | 768
Number of MHA heads | 12 | 12
Dimensionality of FFN hidden layers | 3072 | 3072
Encoder Dropout | 0.1 | 0.1
Decoder Dropout | 0.1 | 0.1
Batch size | 16 | 16
Learning rate | 0.0001 | 0.0001
Number of training epochs | 20 | 500
Table 7: Hyperparameters for CFQ and Text-to-SQL experiments when T5-base was
used


11institutetext: AWS/Amazon AI
<EMAIL_ADDRESS>{zhouho, shuoy, junfa, yuanjx<EMAIL_ADDRESS>
# Towards Regression-Free Neural Networks for Diverse Compute Platforms

Rahul Duggal Hao Zhou Shuo Yang
Jun Fang Yuanjun Xiong Wei Xia Currently at Georgia Tech. Work conducted
during an internship with AWS AI.

With the shift towards on-device deep learning, ensuring a consistent behavior
of an AI service across diverse compute platforms becomes tremendously
important. Our work tackles the emergent problem of reducing predictive
inconsistencies arising as negative flips: test samples that are correctly
predicted by a less accurate model, but incorrectly by a more accurate one. We
introduce REGression constrained Neural Architecture Search (REG-NAS) to
design a family of highly accurate models that engender fewer negative flips.
REG-NAS consists of two components: (1) A novel architecture constraint that
enables a larger model to contain all the weights of the smaller one thus
maximizing weight sharing. This idea stems from our observation that larger
weight sharing among networks leads to similar sample-wise predictions and
results in fewer negative flips; (2) A novel search reward that incorporates
both Top-1 accuracy and negative flips in the architecture search metric. We
demonstrate that REG-NAS can successfully find desirable architectures with
few negative flips in three popular architecture search spaces. Compared to
the existing state-of-the-art approach [Yan_2021_CVPR], REG-NAS enables
$33-48\%$ relative reduction of negative flips.

##  1 Introduction

Consider a manufacturer that uses deep learning to detect defective products
on their assembly line. To improve throughput, they use a small, low-latency,
on-device model to quickly detect potentially defective products which later
undergo a secondary examination by a large, and more accurate model deployed
on the cloud. If there are many cases where the on-device model correctly
identifies a defective product which, on second inspection the on-cloud model
incorrectly believes to be qualified, the defective product may end up
entering the market and damaging the reputation of the manufacturer (See Fig.
1a).

Figure 1: Regression arises when samples that are correctly predicted by a
less accurate model are negatively flipped or incorrectly predicted by a more
accurate one. (a) Three models from the popular RegNet [RegNet] family trained
on ImageNet suffer from $4.3-4.8\%$ pairwise negative flip rate (NFR); (b)
Models designed via REG-NAS achieve $1.9-2.3\%$ NFR with similar Top-1
accuracy.

Such samples, which one model predicts correctly while the other predicts
incorrectly, are called negative flips. The fraction of negative flips over
the dataset size is called the negative flip rate (NFR) [Yan_2021_CVPR] and is
used to measure regression between two models111Please note this definition of
regression is different from the traditional one which pertains to predicting
the outcome of continuous variables.. In this work, we aim to design a family
of models for diverse compute budgets (_e.g._ deployed on edge, server, and
cloud) that maximize Top-1 accuracy and minimizes the pairwise negative flip
rate (See Fig. 1b).

Positive congruent training [Yan_2021_CVPR] is the first work to tackle
negative flips. They propose the Focal Distillation (FD) loss, which enforces
congruence with the reference model by giving more weights to samples that
were correctly classified by the reference model. While [Yan_2021_CVPR] aims
at reducing flips along the temporal axis, _i.e._ between different model
versions trained on growing datasets, we tackle regression along the spatial
axis, _i.e._ between models deployed on diverse compute platforms. The key
difference being that the temporal setting constrains the model design to
necessarily be sequential since the past model is fixed while the current
model is designed and the future model is unknown. In contrast, the spatial
setting enjoys larger flexibility wherein all models can be jointly adapted
towards minimizing negative flips.

To quantify the difference between sequential and joint design strategies,
Fig. 2a presents the case of designing a small (reference) and a large
(target) model. Independently training a MobileNet-v3 reference and an
EfficientNet-B1 target model using cross entropy loss achieves 73.6% and
77.08% Top-1 accuracies with more than 4.25% negative flip rate. Training the
target model sequentially against the fixed reference model via focal
distillation loss [Yan_2021_CVPR] reduces the NFR to $3.25\%$ with a $0.8\%$
drop in Top-1 accuracy. However, jointly designing the reference and target
models using REG-NAS significantly reduces the NFR to $2.16\%$ with a marginal
$0.25\%$ drop in the Top-1 accuracy.

REG-NAS can jointly design models by sampling sub-networks from a common
super-network. We hypothesize this implicitly reduces negative flips due to
large weight sharing among the sampled sub-networks (see appendix A for a
detailed study). This naturally motivates the question: Could we further
reduce negative flipping by maximizing weight sharing? To this end, we propose
the first component of REG-NAS—a novel architecture constraint that maximizes
weight-sharing by enabling the larger sub-networks to contain all the weights
of smaller ones. Empirically, in Sec. 3.2 we show that architectures
satisfying this constraint exhibit much lower negative flips while still
achieving high accuracy.

Figure 2: (a) Independently training a MobileNet-V3 and EfficientNet-B1 as
reference and target models leads to 73.6%, 77.08% Top-1 accuracies with 4.25%
negative flip rate (NFR). Sequentially training the target against the
reference model with the Focal Distillation loss [Yan_2021_CVPR] reduces NFR
to the detriment of target model’s accuracy. Jointly designing the reference
and the target models via REG-NAS leads to lowest NFR with negligible drop in
accuracy. (b) Plotting the Top-1 accuracy and NFR (measured against a common
reference model) for 300 randomly sampled architectures. Observe that the NFR
and Top-1 accuracy are uncorrelated which means existing NAS that maximizes
Top-1 accuracy may fail to find models with the lowest negative flip rate.

While weight sharing implicitly helps reduce negative flips, it is not
sufficient. Fig. 2b shows that among architectures that maximally share
weights by satisfying the architecture constraint, there is a significant
variance in NFR and Top-1 accuracy. To search for highly accurate
architectures that minimize regression, in Sec. 3.3 we propose the second
component of REG-NAS—a novel search reward that includes both Top-1 accuracy
and NFR as the architecture search metric.

Together, our proposed architecture constraint and novel search reward enable
REG-NAS to reduce negative flips by $33-48\%$ over the existing state-of-the-
art FD loss [Yan_2021_CVPR]. We also show that REG-NAS can find low NFR sub-
networks from popular architecture search spaces, demonstrating its strong
generalization ability. Additionally, the models searched via REG-NAS are
transitive under the NFR metric, enabling the search for N ($\geq 2$) models
across diverse compute budgets. To summarize, our contributions are:

  1. 1.

We extend the search for regression-free models from the temporal to the
spatial setting. This support scenarios that simultaneously deploy a family of
models across diverse compute budgets.

  2. 2.

We propose two novel ideas to minimize negative flips while achieving high
Top-1 accuracy: an architecture constraint that maximizes weight sharing
thereby inducing similar sample-wise behavior; and a novel architecture search
reward to explicitly include NFR in the architecture search metric.

  3. 3.

We comprehensively evaluate our search method on ImageNet and demonstrate its
generalization on three popular architecture search spaces.

##  2 Related Work and Background

Minimizing regression between different models has previously been explored in
the temporal setting where different model versions arise during model updates
[BCT, srivastava2020empirical]. Generally, this task closely relates to
research in continual learning [kirkpatrick2017overcoming, chen2018lifelong,
parisi2019continual], incremental learning [castro2018end, wu2019large,
belouadah2019il2m] and model compatibility [BCT, Yan_2021_CVPR, CMPNAS].
However, the main difference lies in how regression is measured.
Traditionally, regression or forgetting was measured via the error rate
[lopez2017gradient, li2017learning, chaudhry2018riemannian], however, Yan
_et.al._ [Yan_2021_CVPR] observe that two models having the similar error
rates may still suffer from a high negative flip rate. Moreover, the methods
that proposed to alleviate catastrophic forgetting are insufficient at
reducing NFR. Different from these works, our work tackles NFR in the spatial
setting wherein different models arise due to a diversity in deployment
targets (_e.g._ edge, server, cloud). The spatial setting is fundamentally
different from the temporal one since it enjoys the additional flexibility of
jointly designing all architectures that can benefit from weight sharing that
ultimately leads to similar sample-wise behavior and lower NFR. This key
distinction calls for new methods that can leverage the flexibility of joint
architecture design.

Neural architecture search (NAS) is a popular tool for automated design of
neural architectures. Earlier NAS methods based on reinforcement learning
[zoph2016neural, liu2017hierarchical, tan2019mnasnet], evolutionary algorithms
[xie2017genetic, real2017large, suganuma2018exploiting, real2019regularized],
and Bayesian optimization [kandasamy2018neural] find highly accurate networks
but are notoriously computational heavy due to the independent evaluation of
candidate networks. Recently One-Shot NAS approaches [pham2018efficient,
DARTS, yu2019autoslim] successfully adopt weight sharing to alleviate the
compute burden. The main innovation in this area is a super-network
[guo2020single, OFA, BIGNAS, AttentiveNAS, alphanet, dai2021fbnetv3,
wu2021fbnetv5] that can encode and jointly train all candidate sub-networks in
an architecture space. Typically, One-Shot NAS algorithms have the following
two phases:

[P1] Super-network pre-training: The goal of which is to jointly optimize all
sub-networks through a weight sharing super-network. The optimization process
typically samples and minimizes the loss on many individual sub-networks
during training. Recent methods innovate on the sampling strategy [OFA,
BIGNAS, AttentiveNAS, dai2021fbnetv3, wu2021fbnetv5] or the loss formulation
[alphanet].

[P2] Sub-network searching: The goal of this phase is to find the best sub-
network from the well-trained super-network under some compute measure such as
flops or latency. This search is typically implemented via an evolutionary
algorithm [OFA, AttentiveNAS, alphanet] with Top-1 accuracy as the reward
function.

Our work leverages a super-network for an entirely new benefit– for reducing
negative flips between networks optimized for diverse compute platforms. This
is yet an unexplored problem that we believe will become increasingly
important in the era of on-device AI powered by hardware optimized neural
networks.

##  3 Regression Constrained Neural Architecture Search

Our REG-NAS algorithm relates to the super-network searching phase (P2) and
generally works with any super-network obtained via the recent pre-training
strategies (P1) [OFA, AttentiveNAS, alphanet]. We modify the search
optimization of P2 along two directions: We propose a novel architecture
constraint that maximizes weight sharing among sub-networks which is discussed
in Sec. 3.2. We propose a novel search reward that incorporates both Top-1
accuracy and the NFR metric as described in Sec. 3.3. Finally, we integrate
these two ideas into our REG-NAS algorithm as discussed in Sec. 3.4.

###  3.1 Measuring regression

We use the negative flip rate (NFR) [Yan_2021_CVPR] as the metric to measure
the regression between two models. Given a dataset $\mathcal{D}$ that contains
image and label pairs $(x_{i},y_{i})$, $i\in\\{1,...,N\\}$, the output of two
deep CNNs $\phi_{1},\phi_{2}$ on an input image $x_{i}$ are denoted by
$y_{i}^{1}$ and $y_{i}^{2}$. The NFR between $\phi_{1},\phi_{2}$ is defined
as:

$\text{NFR}(\phi_{1},\phi_{2};\mathcal{D})=\frac{1}{N}\sum_{i=1}^{N}\mathbbm{1}(y_{i}^{1}=y_{i},y_{i}^{2}\neq
y_{i}),$ (1)

where $\mathbbm{1}$ is an indicator function. The NFR measures the fraction of
samples that are predicted correctly by $\phi_{1}$ and incorrectly by
$\phi_{2}$. Note that NFR is asymmetric, so
$\text{NFR}(\phi_{1},\phi_{2})\neq\text{NFR}(\phi_{2},\phi_{1})$. We select
$\phi_{1}$ as the model with a lower Top-1 accuracy and $\phi_{2}$ as the one
with the higher Top-1 accuracy. As a result,
$\text{NFR}(\phi_{1},\phi_{2})\in[0,1]$.

###  3.2 Architecture constraint to reduce negative flips

We hypothesize that sub-networks sampled from a super-network share a lot of
weights, which induces similar sample-wise behavior and results in less
negative flips. A natural extension of this hypothesis prompts the question:
can we further reduce negative flips by maximizing weight-sharing between sub-
networks? In what follows, we describe the architecture constraint that
answers this question.

Consider a reference model with architecture $a_{r}$ that inherits weights
$W^{*}_{a_{r}}$ from a super-network. We aim to search for a target
architecture $a_{t}$ with weights $W^{*}_{a_{t}}$ such that the weight sharing
between $a_{r}$ and $a_{t}$ is maximized, _i.e._ :

$\displaystyle a_{t}\
=\operatorname*{arg\,max}_{a\in\mathcal{A}}\mathcal{N}(W^{*}_{a}\cap
W^{*}_{a_{r}}),$ (2) $\displaystyle\text{s.t.}~{}~{}C(a)<\tau,$

where $\mathcal{N}$ counts the number of weights, $\cap$ represents the
intersection of weights between two architectures, $C$ represents a
performance constraint such as flops or latency and $\mathcal{A}$ represents
the search space defined by the super-network. Eq. 2 specifies the
architecture constraint and we refer to the process of solving it as
constrained architecture search (CAS).

Observe that $N(W^{*}_{a}\cap W^{*}_{a_{r}})$ is upper bounded by
$N(W^{*}_{a_{r}})$, with the supremum occurring when $a$ contains all the
weights of $a_{r}$. This means Eq. 2 partitions the architecture space
$\mathcal{A}$ to a space $\mathcal{A}_{t}$ of constrained architectures:

$\displaystyle\mathcal{A}_{t}=\\{a:W^{*}_{a_{r}}\subseteq W^{*}_{a},\forall
a\in\mathcal{A}\\},$ (3)

and its complementary space $\mathcal{A}_{c}=\mathcal{A}-\mathcal{A}_{t}$ that
includes target architectures that do not contain all the weights of the
reference model. To visualize the two architecture spaces, we plot NFR _v.s._
Top-1 accuracy for 300 randomly sampled architectures from $\mathcal{A}_{t}$
and $\mathcal{A}_{c}$ in Fig. 4(a). Observe that the architectures in space
$\mathcal{A}_{t}$ generally have lower NFR and higher Top-1 accuracy compared
to those in $\mathcal{A}_{c}$. As a result, it is easier to find architectures
with lower NFR and higher Top-1 accuracy in space $\mathcal{A}_{t}$ than in
the complete space $\mathcal{A}$ as demonstrated empirically in Sec 4.3.

Note that, not all super-networks allow for partitioning the search space
according to Eq. 3. For example DARTS [DARTS, FAIR_DARTS] implements different
operators (_e.g._ $3\times 3$ and $5\times 5$ conv) using a completely non-
overlapping set of weights. In such search spaces, enforcing the architecture
constraint trivially leads to the same architecture for the reference and
target model. On the other hand, recent works [OFA, AttentiveNAS, alphanet]
implement different operators using an overlapping set of weights _e.g._ the
innermost $3\times 3$ weights of the $5\times 5$ kernel implements a $3\times
3$ kernel. To enable the architecture constraint for such works, we propose
the CAS recipe which specifies three rules for searching a candidate
architecture $a_{t}$ against a reference model $a_{r}$:

  1. 1.

Add new layers within blocks of $a_{r}$ (Fig. 3a).

  2. 2.

Add additional channels to filters in $a_{r}$ (Fig. 3b).

  3. 3.

Extend kernel size for filters in $a_{r}$ (Fig. 3c).

Figure 3:  Constrained Architecture Search (CAS) recipe specifies three
operations for searching a target model $a_{t}$ given a reference model
$a_{r}$: (a) Adding new layers within an existing block of $a_{r}$; (b) Adding
new channels to existing filters in $a_{r}$; (c) Extending the kernel size
beyond the existing one in $a_{r}$.

###  3.3 Search reward to reduce NFR

(a)

(b)

Figure 4: Through random sampling architectures from the MobileNet-V3 search
space $\mathcal{A}$ of OFA [OFA], we show: (a) The architecture constraint
partitions $\mathcal{A}$ into $A_{t}$ and $A_{c}$ wherein the architectures in
$A_{t}$ tend to have lower NFR; (b) An evolutionary search fitted with rewards
($\mathcal{R}_{0},\mathcal{R}_{1},\mathcal{R}_{2}$) explores different regions
of the architecture space. Specifically, $\mathcal{R}_{0}$ leads to
architectures with high Top-1 and NFR, $\mathcal{R}_{1}$ leads to
architectures with low Top-1 and NFR while $\mathcal{R}_{2}$ achieves the best
of both–high Top-1 accuracy and low NFR.

While the architecture constraint implicitly helps reduce NFR through weight
sharing, it is not sufficient. To illustrate this, we plot the Top-1 accuracy
and the NFR of 300 randomly sampled sub-networks from $\mathcal{A}_{t}$
against a fixed reference model in Fig. 2b. Observe that the model with
highest Top-1 accuracy has a NFR around $2.5\%$ which is higher than many of
the sampled architectures. This means that optimizing solely for the Top-1
accuracy as in existing NAS methods will not lead to architectures with small
NFR. Consequently, to optimize for architectures with low NFR it is essential
to include NFR in the search reward.

The observations of Fig. 2b naturally motivate the inclusion of NFR in the
search reward $\mathcal{R}$ as below:

$\displaystyle\mathcal{R}\left(W^{*}_{a_{t}};W^{*}_{a_{r}},~{}\mathcal{D}^{val}\right)$
$\displaystyle=$
$\displaystyle\lambda_{1}*\text{Top-1}(W^{*}_{a_{t}};~{}\mathcal{D}^{val})$
$\displaystyle-$
$\displaystyle\lambda_{2}*\text{NFR}(W^{*}_{a_{t}},W^{*}_{a_{r}};\mathcal{D}^{val}),$

where $W^{*}_{a_{r}},W^{*}_{a_{t}}$ represents the weights of the reference
and target models while $\lambda_{1},\lambda_{2}$ balance the trade off
between Top-1 accuracy and NFR respectively. To illustrate the extreme effect
of the two terms, we consider three different rewards obtained by setting the
following values of $\lambda_{1}$ and $\lambda_{2}$.

  1. $\mathcal{R}_{0}$

($\lambda_{1}=1,\lambda_{2}=0$): reward used by existing NAS methods that
solely optimizes for high Top-1 accuracy.

  2. $\mathcal{R}_{1}$

($\lambda_{1}=0,\lambda_{2}=1$): reward that solely optimizes for low NFR.

  3. $\mathcal{R}_{2}$

($\lambda_{1}=1,\lambda_{2}=1$): reward that optimizes for high accuracy and
low NFR.

We find that the rewards $\mathcal{R}_{0}$, $\mathcal{R}_{1}$ and
$\mathcal{R}_{2}$ can guide evolutionary search to different regions of the
architecture search space. Fig. 4(b) illustrates this by plotting the Top-1
accuracy and NFR of all architectures sampled during an evolutionary search
fitted with the three rewards. The plot clearly shows that $\mathcal{R}_{2}$
guides the search to architectures with high Top-1 and low NFR. We consider
$\mathcal{R}_{2}$ as the default choice for REG-NAS since it equally balances
the Top-1 accuracy and NFR. Please refer to appendix B for a complete ablation
on $\lambda_{1},\lambda_{2}$.

###  3.4 REG-NAS: Regression constrained neural architecture search

To search for sub-networks that achieve the highest Top-1 accuracy with the
minimum negative flips, we integrate the novel architecture constraint of Eq.
3 with the novel reward of Eq. 3.3 to propose REG-NAS, which solves the
following optimization.

$\displaystyle
a_{t}=\operatorname*{arg\,max}_{a\in\mathcal{A}}~{}~{}\mathcal{R}\left(W^{*}_{a};W^{*}_{a_{r}},~{}\mathcal{D}^{val}\right),$
(5) $\displaystyle\text{s.t.}~{}~{}W^{*}_{a_{r}}\subseteq
W^{*}_{a},\text{and}~{}~{}C(a)<\tau$

We solve the above optimization using a standard evolutionary based NAS
algorithm with two modifications: the random sampling and mutate operations
can only perform the operations specified by the CAS in Sec. 3.2; and the
search reward uses the reward formulation of Sec. 3.3 with
$\lambda_{1}=1,\lambda_{2}=1$.

##  4 Experiments

We begin by comparing REG-NAS against the state-of-the-art method
[Yan_2021_CVPR] designed to reduce NFR. To understand the effectiveness of
REG-NAS, we dissect the performance gains due to the novel architecture
constraint and search reward. We then extend the proposed method to search for
an entire family of architectures. Finally, we test the generalization of REG-
NAS across: different flop budgets, super-networks, and latency constraints on
diverse platforms.

###  4.1 Dataset, metrics and implementation details

We implement our methods using Pytorch on a system containing 8 V100 GPUs.
Other details are as follows:

Dataset. We present all results on ImageNet [imagenet]. We carve out a sub-
training set of 20,000 images from the original training set to evaluate the
rewards and update batchnorm statistics for each sub-network [OFA]. The final
results are presented on the original ImageNet validation set.

Evolutionary Search. To search for a sub-network, we run the evolutionary
search with the following hyper-parameters: 20 generations, 100 population
size, 0.1 mutate probability, 0.5 mutation ratio and 25% Top-K architectures
moving into the next generation. Overall, our search evaluates 1,525
architectures in each super-network. Following the setting of the original
work, for MobileNet-V3 and ResNet-50 search spaces of OFA [OFA], the rewards
are computed on the sampled sub-training set, while for FBNet-V3 super-network
of AttentiveNAS [AttentiveNAS] and AlphaNet [alphanet], the search is
performed on the ImageNet validation set as suggested by [AttentiveNAS,
alphanet].

Notation. We refer to different models following the consistent notation AA-
BB-CC. The first initial “AA” refer to the super-network, the middle initial
“BB” refers to the search reward and the final initial “CC” refers to the
performance constraint such as flops or latency. We use CAS to represent
constrained architecture search discussed in Sec. 3.2.

###  4.2 Regression Constrained Search

Given a small reference model, we aim to find a larger target model that,
under a fixed compute budget, maximizes the Top-1 accuracy while minimizing
NFR. Table 4.2 illustrates this task with comparative results from the
MobileNet-V3 and ResNet-50 search spaces of OFA [OFA].

Model Flops Top-1 NFR $\uparrow$(%) $\downarrow$ (%) ref
MB-$\mathcal{R}_{0}$-150 [OFA] 149 73.70 - 1-5[.7pt/1.5pt] baseline EffNet 385
77.08 4.25 PCT EffNet+FD [Yan_2021_CVPR] 385 76.25 3.25 wt. share
MB-$\mathcal{R}_{0}$-300 [OFA] 298 77.11 2.51 REG-NAS
MB-($\mathcal{R}_{2}$+CAS)-300 294 76.83 2.16

(a) MobileNet-V3 search space of OFA

Model Flops Top-1 NFR $\uparrow$(%) $\downarrow$ (%) ref
RN-$\mathcal{R}_{0}$-2000 [OFA] 1973 78.25 - 1-5[.7pt/1.5pt] baseline RN101
7598 79.21 4.83 PCT RN101+FD [Yan_2021_CVPR] 7598 79.90 3.06 wt. share
RN-$\mathcal{R}_{0}$-3000 [OFA] 2941 78.78 2.04 REG-NAS
RN-($\mathcal{R}_{2}$+CAS)-3000 2915 78.80 1.57

(b) ResNet search space of OFA (c) Comparing different model design
strategies. We present results for MobileNet-V3 (MB) and ResNet-50 (RN) search
spaces of OFA [OFA]. EffNet and RN101 represents EfficientNet-B0 and
ResNet-101 trained with cross entropy loss, while EffNet+FD and RN101+FD are
trained with state-of-the-art focal distillation loss [Yan_2021_CVPR]. Results
of weight sharing and our proposed method are averaged from three runs with
different random seeds.

We first search for the best reference model under $150$ mega flops constraint
(MB-$\mathcal{R}_{0}$-150) using the $\mathcal{R}_{0}$ reward which maximizes
Top-1 accuracy. Then, we establish a baseline by training an off-the-shelf
EfficientNet-B0 model222We choose EfficientNet-B0 since it has similar Top-1
accuracy with sub-networks searched from MobileNet-V3 in OFA [OFA] using
vanilla cross entropy. This model improves Top-1 accuracy to $77\%$, but
suffers from 4.25% negative flips. A stronger baseline can be achieved by
training the EfficientNet using Focal Distillation [Yan_2021_CVPR] which is
the current state-of-the-art method to reduce negative flips. It reduces the
NFR to $3.25\%$ with a $0.8\%$ drop in Top-1 accuracy. Another strong weight
sharing baseline can be obtained via searching a sub-network from the same
super-network as the reference model using $\mathcal{R}_{0}$ reward. This
leads to an NFR of $2.51\%$ with $77.11\%$ Top-1 accuracy. Compared to all of
these, the networks obtained via REG-NAS _i.e._
(MB-($\mathcal{R}_{2}$+CAS)-300) achieves the lowest NFR of $2.16\%$ with less
than $0.3\%$ drop in Top-1 accuracy compared with MB-$\mathcal{R}_{0}$-300.
This constitutes a $50\%$ and $33\%$ relative reduction of NFR with respect to
the baseline and existing state-of-the-art method with less than $1\%$ change
in accuracy (see appendix C). The strong performance of REG-NAS clearly
demonstrates the benefits of the search reward and architecture constraint.
Similar results can be observed for the ResNet-50 search space of OFA [OFA] in
Table 4.2.

Model Flops Top-1 NFR $\uparrow$ (%) $\downarrow$ (%) ref
MB-$\mathcal{R}_{0}$-150 149 73.70 - 1-5[.7pt/1.5pt] paragon Top-1
MB-$\mathcal{R}_{0}$-300 298 77.11 2.51 paragon NFR MB-$\mathcal{R}_{1}$-300
279 76.20 2.07 MB-$\mathcal{R}_{2}$-300 292 76.90 2.25 REG-NAS
MB-($\mathcal{R}_{2}$+CAS)-300 294 76.83 2.16

(d) MobileNet-V3 search space of OFA

Model Flops Top-1 NFR $\uparrow$(%) $\downarrow$ (%) ref
RN-$\mathcal{R}_{0}$-2000 1973 78.25 - 1-5[.7pt/1.5pt] paragon Top-1
RN-$\mathcal{R}_{0}$-3000 2941 78.78 2.04 paragon NFR
RN-$\mathcal{R}_{1}$-3000 2537 78.57 1.28 RN-$\mathcal{R}_{2}$-3000 2972 78.87
1.76 REG-NAS RN-($\mathcal{R}_{2}$+CAS)-3000 2915 78.80 1.57

(e) ResNet search space of OFA (f) Comparing different search rewards using
the MobileNet-V3 (MB) and ResNet-50 (RN) search spaces of OFA [OFA]. Results
(except ref) are averaged from three runs with different seeds.

###  4.3 Dissecting the performance of REG-NAS

In this subsection, we study the contribution of different components of REG-
NAS—the search reward and the constrained architecture search, in reducing
NFR. Table 4.2 presents the performance of architectures searched via
$\mathcal{R}_{0}$, $\mathcal{R}_{1}$, $\mathcal{R}_{2}$ and
$\mathcal{R}_{2}$+CAS. We observe that since $\mathcal{R}_{0}$ only includes
Top-1 accuracy in its formulation, the optimal architecture searched via it
achieves the best accuracy, which we treat as the paragon for Top-1 accuracy.
However, this same architecture also suffers from the highest NFR. On the
other hand, $\mathcal{R}_{1}$, which only includes the NFR in its formulation,
leads to a model with the lowest NFR, and also lowest Top-1 accuracy. We treat
this model as the paragon for NFR.

Effect of reward $\mathcal{R}_{2}$. By including both the Top-1 accuracy and
NFR in its formulation, reward $\mathcal{R}_{2}$ leads to models that lie
closer to the paragon of both metrics. The best results, however, are achieved
by including the architecture constraint which further brings the models
closer to the respective paragons. In the case of MobileNet-V3, architecture
searched by $\mathcal{R}_{2}$+CAS is within $0.09\%$ of the paragon of NFR and
within $0.28\%$ of the paragon of Top-1 accuracy, which demonstrates the
effectiveness of the proposed method.

Effect of architecture constraint. Besides reducing NFR, we find that CAS also
help search for an architecture with low NFR much faster compared with
$\mathcal{R}_{2}$ as shown in Fig. 5a. This is because CAS partitions the
overall architecture space into a subspace containing well performing
architectures that achieve low NFR and high Top-1 accuracy as described in
Sec. 3.2.

Effect of model size. It is natural to ask if a smaller gap in Top-1 accuracy
would imply a smaller NFR? The answer is provided in Fig. 5b which plots the
accuracy and NFR for 9 target models (from 175 to 600 Mflops) searched against
a common 150 Mflop reference model with 73.7% Top-1 accuracy. Observe that
with $\mathcal{R}_{0}$, even for the smallest model with similar accuracy as
the reference, the NFR is consistently high ($\approx 2.5\%$). This suggests
that accuracy gap between reference and target has little impact on the NFR.
Additionally, we see that the search with $\mathcal{R}_{2}+CAS$ outperforms
$\mathcal{R}_{0}$ across all model sizes.

Figure 5:  (a) NFR of the optimal architecture in each generation of the
evolutionary search. Observe that CAS leads to lower NFR early and throughout
the search. (b) Top-1 accuracy and NFR for 9 models (175-500 mflops) searched
against a common reference (150 mflops). Observe that a smaller accuracy gap
doesn’t imply a smaller NFR. Also $\mathcal{R}_{2}+CAS$ outperforms
$\mathcal{R}_{0}$ for all sizes.

###  4.4 Supercharging REG-NAS with PCT

We study if fine-tuning with FD loss proposed in [Yan_2021_CVPR] can help
further reduce the NFR for architectures searched via REG-NAS. Table
LABEL:tab:finetune compares two loss functions: vanilla cross entropy (CE) and
FD333We use FD-KD from [Yan_2021_CVPR] since it outperforms FD-LM in our
setting. for fine-tuning the target sub-networks obtained via REG-NAS.

We observe that fine tuning with CE generally results in a higher NFR. This is
expected because CE optimizes the weights for higher Top-1 accuracy, which may
push the weights of the target model away from those of the reference. In
contrast, FD loss promotes similar sample-wise behavior by penalizing negative
flips and leads to a lower NFR. This study demonstrates that FD loss can work
in tandem with REG-NAS to further reduce NFR. However, even without fine
tuning, the architectures searched by REG-NAS already enjoy a very low NFR,
even outperforming the MB-$\mathcal{R}_{0}$-300 architecture with fine tuning.
Considering the large time cost of fine tuning, we avoid it in the following
discussion.