# SpaceNLI: Evaluating Natural Language Inference Models
on Spatial Reasoning

Lasha Abzianidze Joost Zwarts Yoad Winter
Institute for Language Sciences, Utrecht University
Utrecht, the Netherlands
{l.abzianidze, j.zwarts<EMAIL_ADDRESS>
# SpaceNLI: Test Bed for Consistent Inferences in Space

Lasha Abzianidze Joost Zwarts Yoad Winter
Institute for Language Sciences, Utrecht University
Utrecht, the Netherlands
{l.abzianidze, j.zwarts<EMAIL_ADDRESS>
# SpaceNLI: Test Bed for Consistent Natural Language Inferences in Space

Lasha Abzianidze Joost Zwarts Yoad Winter
Institute for Language Sciences, Utrecht University
Utrecht, the Netherlands
{l.abzianidze, j.zwarts<EMAIL_ADDRESS>
# SpaceNLI: Evaluating the Consistency of Predictions In Space

Lasha Abzianidze Joost Zwarts Yoad Winter
Institute for Language Sciences, Utrecht University
Utrecht, the Netherlands
{l.abzianidze, j.zwarts<EMAIL_ADDRESS>
# SpaceNLI: Evaluating the Consistency of Predicting Inferences In Space

Lasha Abzianidze Joost Zwarts Yoad Winter
Institute for Language Sciences, Utrecht University
Utrecht, the Netherlands
{l.abzianidze, j.zwarts<EMAIL_ADDRESS>
###### Abstract

While many natural language inference (NLI) datasets target certain semantic
phenomena, e.g., negation, tense & aspect, monotonicity, and presupposition,
to the best of our knowledge, there is no NLI dataset that involves diverse
types of spatial expressions and reasoning. We fill this gap by semi-
automatically creating an NLI dataset for spatial reasoning, called
SpaceNLI.111https://github.com/kovvalsky/SpaceNLI The data samples are
automatically generated from a curated set of reasoning patterns (see Figure
1), where the patterns are annotated with inference labels by experts. We test
several SOTA NLI systems on SpaceNLI to gauge the complexity of the dataset
and the system’s capacity for spatial reasoning. Moreover, we introduce a
_Pattern Accuracy_ and argue that it is a more reliable and stricter measure
than the accuracy for evaluating a system’s performance on pattern-based
generated data samples. Based on the evaluation results we find that the
systems obtain moderate results on the spatial NLI problems but lack
consistency per inference pattern. The results also reveal that non-projective
spatial inferences (especially due to the “between” preposition) are the most
challenging ones.

##  1 Introduction

Natural language inference (NLI) is a popular task that evaluates NLP systems
on text reasoning skills. In the task, a system has to predict an inference
relation from a premise text to a hypothesis sentence/phrase. Usually, the
task is three- or two-way classification, depending on whether in the
inference labels of _entailment_ , _neutral_ , and _contradiction_ , the
latter two are merged into _non-entailment_. The task is intended for
evaluation of NLP systems on reasoning, however, the systems with competitive
results on NLI benchmarks are often exploiting dataset biases (Tsuchiya 2018;
Poliak et al. 2018; Gururangan et al. 2018; McCoy et al. 2019, inter alia) and
their performance suffers from out-of-distribution NLI sample problems
(Glockner et al., 2018).

Figure 1: Sampling NLI problem from NLI patterns (with IDs 9 and 10,
Entailment and Contradiction, respectively). The problems are generated by
replacing NP placeholders with definite NPs that satisfy pattern-specific
selection restrictions. A system’s success rate on a pattern is defined as the
accuracy on its corresponding NLI problems.

To better evaluate the reasoning skills of NLI systems, a series of works have
been (semi-)automatically or manually creating NLI datasets that specialize in
certain semantic phenomena. While some of these datasets come with a training
part, most of them are intended solely for evaluation. For example, several
datasets have been dedicated to monotonicity reasoning (Yanaka et al., 2019b,
a, 2020), negation was targeted by Hossain et al. (2020), the dataset by Kober
et al. (2019) focuses on temporal and aspectual inferences, Jeretic et al.
(2020) semi-automatically generated NLI problems for implicatures and
presuppositions. There are also NLI datasets that cover several semantic
phenomena, having a separate section for each of the phenomena (Cooper et al.
1996; Richardson et al. 2020, inter alia).

While spatial reasoning has been included in several multi-modal QA datasets
(Antol et al., 2015; Suhr et al., 2017; Johnson et al., 2017; Hudson and
Manning, 2019) and in a couple of text-based QA datasets (Weston et al., 2016;
Mirzaee et al., 2021), to the best of our knowledge, no NLI dataset has
specifically covered it.222Even the FraCaS dataset (Cooper et al., 1996;
MacCartney, 2009), which was curated by linguists and semanticists, doesn’t
cover spatial semantics within its nine sections. This paper fills the gap by
semi-automatically creating an NLI dataset for spatial inferences. First, we
collected a diverse set of NLI problems inspired by the inference examples
found in the literature on spatial semantics. Second, the NLI problems were
manually converted into NLI patterns (see Figure 1), and finally, we
automatically generated a large number of NLI problems from the patterns.

The paper makes two main contributions:

  1. C1.

SpaceNLI: the spatial NLI dataset with diverse types of spatial inferences;
The inference labels of the generated problems are highly faithful (97%) to
the labels of the corresponding original patterns.

  2. C2.

Pattern accuracy and its curve: they measure systems’ performance on patterns
and the consistency in predictions on samples from the same patterns.

The conducted experiments answer the following research questions:

  1. Q1.

How much spatial reasoning current SOTA NLI systems are capable of?

  2. A1.

We found out that the SOTA NLI systems have problems with fine-grained spatial
inferences. Their performance drops at least by 24% compared to their results
on common NLI datasets. Moreover, their consistency in predictions is
sensitive to irrelevant lexical substitutions.

  3. Q2.

What types of spatial inference problems are easy or challenging for the SOTA
NLI systems?

  4. A2.

The results showed that the non-projective spatial relations are most
challenging for the models. This was mainly due to difficulty associated with
“between” and its frequent occurrence in the evaluation dataset.

##  2 Spatial expressions and inferences

###  2.1 Types of spatial expressions

Spatial expressions consist of spatial prepositions and other expressions with
spatial information (e.g., far, the left of, and in front of). They usually
describe a relation between two entities, the _figure_ and the _ground_. The
site or path of the figure is the focus of the discussion and is characterized
with respect to the ground. For example, in ($9_{1}$) and ($10_{1}$) from
Figure 1, Mary is a figure and garden a ground. John is also a figure in the
premise of ($10_{1}$).

Spatial expressions are roughly divided into _locative_ and _directional_
expressions, where locatives can be further classified into _projective_ and
_non-projective_ (Herskovits, 1986). The locative expressions describe static,
locative relations between the figure and the ground while directional ones
describe a more _dynamic_ relation involving a movement and/or path. An
example with a directional preposition is Cindi walked into the market. The
spatial expressions in Figure 1 are all locative except for from, which is
directional. These locative expressions are non-projective since they require
only the spatial location of the figure and the ground. In contrast,
projective locatives additionally require further information from the ground
in terms of a deictic frame of reference (i.e., an orientation structure). For
example, the site of the house is not sufficient to interpret Mary’s location
in Mary is behind the house, it requires knowledge about the frame of
reference of the house, in particular, what counts as a back side of the
house.

ID | Class | Premise(s) | L | Hypothesis
---|---|---|---|---
15 | Dir | John threw the ball into the box. | E | The ball went into the box.
16 | Dir | John threw the ball at the box. | N | The ball went into the box.
31a | Dir | Los Angeles is in California. John came from California. | N | John came from Los Angeles.
38 | NonP | John is in the garden. The garden is in the church. | E | John is in the church.
41 | Dir | John drove through the tunnel. | E | John was in the tunnel.
47a | Dir | Cindi walked into the market. | E | Cindi was outside the market.
56c | Proj | The trash can is to the right of the tree from John. | C | The tree is to the right of the trash can from John.
70 | Proj | Mary is between the tree and the house. The tree is behind the house. | E | Mary is behind the house.
80 | NonP | The cat is between the house and the fence. The cat is between the fence and the tree. | C | The cat is between the house and the tree.
99*d | Proj | The bucket is above the bowl. The pencil is above the bowl. | N | The bucket is below the pencil.
96b | ArgO | Mary met John at the party. | N | Cindi was not at the party.
100 | NonP | The house is far from the school. | E | The school is far from the house.
102a | ArgO | Mary has taken the cup out of the cabinet. | C | The cup is in the cabinet.
102f | ArgO | Mary has hidden the cup behind the cabinet. | E | The cup is not in the cabinet.

Table 1: Examples of the seed NLI problems annotated with spatial inference
classes: Directional, Projective, Non-Projective, and Argument Orientation.
Initial letters abbreviate the corresponding inference labels.

###  2.2 Types of spatial inferences

We characterize spatial inferences depending on the type of spatial
expressions licensing them. An inference might depend on several spatial
expressions of a different type, which makes partitioning the inferences
challenging, if not impossible. We define the following classes that represent
a coarse-grained partition of spatial inferences. The classes will be later
referred to in § 3.333Licensing contradiction and neutral problems will be
assumed from the perspective of a related entailment problem. For example, we
assume that the neutral problem (16) in Table 1 is licensed in the same way as
its related entailment (15). Put differently, one can see (16) as an adversary
to (15) and assume that solving (15) requires competence comparable to the one
required for solving (16).

##### Argument orientation

In spatial literature, an argument orientation entailment identifies which
argument of the verb is the figure of the spatial expression. For instance,
(91) in Figure 1 show that Mary is the figure of the locative PP in the
garden. In its original interpretation, the argument orientation entailment is
not restricted to spatial expressions of a particular type. Here, we restrict
the class of argument orientation to the entailment problems (and their
neutral and contradiction counterparts) that come close to resolving a PP
attachment. For example, correctly resolving the PP attachment in (91) boils
down to the hypothesis. The problems in this class contain a hypothesis with a
copula and a predicative spatial PP, where the PP is contrasted to a tightly
related PP in the premise(s). For more examples of the NLI problems in the
argument orientation class, see Table 1.

##### Directional

The directional class contains spatial inferences where directional spatial
expressions play the key role. Examples of such inferences are given in Table
1. Some of these NLI problems pertain to a path-place relation: (47a) shows
that walking into infers being outside;444Since moving along the path is
related to the change of the location, sometimes spatial entailments interfere
with tense and aspect.  (41) entails being in the tunnel from the premise that
states that the driving path was through the tunnel. (31a) combines a part-
whole relation with the movement path.

##### Projective

This class contains inferences that hinge on a frame of reference introduced
by projective spatial expressions. In principle, the frame of reference can
introduce six directions that can be referred to using the expressions like
front, behind, left, right, above, below, under, on top of, etc. (see the
examples of NLI problems in Table 1). The NLI problems that contain on top of
as only projective spatial expression, and when its projective interpretation
is not crucial for the inference, are put in a different class.

##### Non-projective

We classify a problem as having non-projective inference if the inference is
driven only by non-projective spatial expressions. Therefore, an occurrence of
non-projective spatial expressions in a problem is necessary but not
sufficient for assigning the problem to this class, e.g., see directional
problems (31a) and (41). NLI problems that depend on spatial expressions with
the semantics of order and proximity are also in this class, see between (80)
and far (100) in Table 1.

Class (#patterns) | Spatial expression counts
---|---
Directional (95) |  | in (20), from (17), into (9), to (8), on (8), away from (7), towards (7), out of (4), back (3),
---
through (3), across (2), at (2), outside (2), opposite (1), part of (1), by
(1)
Argument orientation (67) |  | in (21), at (10), from (9), away from (4), out of (4), near (3), with (3), inside (3), on (2),
---
under (2), through (1), opposite (1), towards (1), far from (1), on top of
(1), behind (1)
Projective (70) |  | behind (16), between (11), in front of (10), below (6), above (6), under (6), on top of (5),
---
front of (3), opposite (2), to the right of (2), on (2), to the left of (1)
Non-projective (48) | between (22), in (9), far from (5), close to (4), outside (3), on top of (2), on (2), opposite (1)

Table 2: The spatial expressions and their counts per entailment class in the
SpaceNLI patterns

##  3 Dataset construction

###  3.1 Pattern construction

Patterns are labeled NLI problems with NPs replaced by variables as
illustrated in Figure 1. The NLI patterns are obtained from the seed NLI
problems. To collect the latter, we extracted the initial 56 problems from
Zwarts and Winter (2000) and Nam (1995), where a majority of the problems were
labeled as entailment due to obvious biases in the semantic literature towards
licensing entailment. To create a representative and challenging NLI dataset
for machine learning, we applied several _revision phases_ to the problems:
introducing new problems that either cover new semantic aspects of spatial
expression or serve as a perturbed version of an existing problem.

In the initial revision phase, four annotators divided the extracted problems
and created slightly modified versions of them with an inference label
different from the original.555 The annotators for the pattern construction
consist of the authors of the paper, two linguist students, and one AI
student. The guideline for creating inference problems can be found in the
supplementary material.  This was motivated by the current trends in the
literature on adversarial, stress, and debiased datasets (Naik et al. 2018;
Ribeiro et al. 2020; Kaushik et al. 2020; Gardner et al. 2020, inter alia).
For example, (16) is a perturbed example of (15). Where possible, NLI problems
of a new type were also created using the similar spatial expressions found in
the extracted problems.

To validate the resulting pool of NLI problems (in total 162), following
(Zhang et al., 2017), they were labeled on a 5-point Likert scale by three
annotators.666 The question was to what extent the hypothesis sentence is
true, given that the premises are true, with choices: _definitely false_ ,
_most likely false_ , _unknown_ , _most likely true_ , _definitely true_. We
used two additional choices, _difficult_ (unable to annotate due to the
complex reasoning it requires) and _skip_ (presence of an ungrammatical or
nonsensical sentence). We used the brat annotation tool (Stenetorp et al.,
2012) for labeling. The annotation guideline is included in the supplementary
material.  After collecting the 5-point annotations, for each annotator, we
picked a mapping of 5-point to 3-point that maximizes the inter-annotator
agreement (avg. Cohen’s $\kappa=.71$). The problems without majority labels
were discarded and 111 problems remained.

To better balance the inference labels and increase the coverage of spatial
expressions, a second revision phase was carried out on the remaining
problems. In several cases, problems with low annotator agreement were
revised, e.g., changing the tense where it caused confusion or replacing a
preposition with a weaker version (at$\mapsto$near). All the new and revised
problems (in total 63) were validated based on three samples: each problem was
manually converted into a pattern by replacing NPs with variables, and three
random NLI samples per pattern were generated (see § 3.2 for details), which
were subsequently validated by three annotators.

Finally, a third revision phase was carried out on the remaining problems to
additionally decrease the overall and spatial type-specific label imbalance.
The collected problems (in total 160) were treated as a seed by converting
them into NLI patterns to generate a large amount of sample NLI problems from
them. To illustrate the coverage of spatial expressions in the collected
patterns, Table 2 gives the complete list of spatial expressions for each
entailment class.

###  3.2 Sample generation

We manually created NLI patterns from the initially collected NLI problems (§
3.1) by replacing NPs with placeholders and specifying selection restrictions
for them imposed by the verbs, spatial expressions, and gold inference labels
(see Figure 1). The selection restrictions imposed by spatial expressions are
subtle and can affect gold labels or the naturalness of sentences. For
example, if the figure is much larger than the ground, it can make the
sentence infelicitous: the apple on the fridge and the apple near the fridge
are preferred to the fridge under the apple and the fridge near the apple.
Inferences driven by proximity-related spatial expressions are sensitive to
the size of the objects. For instance, based on our conducted validations,
Cindi is opposite to the cat is more likely to be neutral to Cindi is far from
the cat, but the school is opposite to the house is more likely to contradict
the school is far from the house.

To meet selection restrictions and allow relative diversity of NPs in the
generated samples, we defined a mini world with a domain containing 171
entities corresponding to common and proper nouns. The entities are organized
in a taxonomy with 20 subclasses covering general types of entities (e.g.,
person, animal, vehicle), the projections of an argument in certain argument
structures (e.g., enter in $X$, be in $X$, throw $X$), compatibility with
projective spatial expressions, and size categories (S for entities comparable
to small objects like book and cat, M to persons, and L to vehicles). Binary
and ternary relations are defined based on the set unions of the products of
entity sets and subclasses.

To automatize the sampling of sound NLI problems from the patterns, we
formatted the mini world in YAML and NLI patterns in XML. We implemented a
procedure that samples problems from the patterns by filling in NP
placeholders with definite NPs from the mini world and respecting the pattern-
specific selection restrictions. For sanity checking, the procedure verifies
that it can generate corresponding seed NLI problems for each pattern.

To measure how faithfully the inference labels are transferred from seed and
pattern NLI problems to the corresponding NLI samples, we used sampled
problems in the second phase of validation when validating new NLI problems
(see § 3.1). The results showed that 79% of samples were unanimously labeled
with the original label. After filtering out patterns with a relatively low
agreement, this ratio increased to 97% for the samples generated from the
validated patterns.

The NLI problems sampled from the same pattern or related patterns are string-
wise very close to each other, sometimes differing only in terms of
occurrences of a single NP. Regardless of this similarity, we expect such
problems to pose a challenge for NLI systems based on large language models
(LLMs) as it has been shown that their predictions can be sensitive to a
single-word substitution (Glockner et al., 2018; Gururangan et al., 2018). In
addition to NPs, one could have allowed the replacement of other phrases in
the NLI patterns, but this would have significantly complicated the definition
of the mini world and generation of natural and sound NLI samples.

Property | E % | N % | C % | All % (#)
---|---|---|---|---
Dir | 39.6 | 35.4 | 25.0 | 30.00 (9600)
NonP | 25.0 | 41.7 | 33.3 | 22.50 (7200)
Proj | 29.4 | 26.5 | 44.1 | 21.20 (6800)
ArgO | 47.6 | 28.6 | 23.8 | 26.20 (8400)
$+$ neg | 48.0 | 28.0 | 24.0 | 15.60 (5000)
1prem | 41.8 | 26.5 | 31.6 | 61.3 (19600)
2prem | 25.0 | 42.9 | 32.1 | 35.0 (11200)
3prem | 50.0 | 50.0 | 0.0 | 3.8 0(1200)
All | 36.2 | 33.1 | 30.6 | 100.0 (32000)

Table 3: Statistics of several properties of the sampled NLI dataset. The
statistics also apply to the collection of NLI patterns as the samples are
evenly distributed over the patterns. The properties consist of the spatial
inference types, whether including negation, and the number of premises.

LLM-based NLI models |  Training data |  snli + mnli | SpaceNLI
---|---|---|---
Acc | PA0.95 | PA1.0
| DeBERTaV3-L#1
---
Joelzhang/deberta-v3…
smfa | 91.8 | 59.6 | 47.5 | 37.5
| ALBERT-XXLv2
---
ynie/albert-xxlarge-v2…
smfa | 90.8 | 57.8 | 48.1 | 36.2
| DeBERTa-L
---
He et al. (2021)
m | 90.7 | 54.1 | 42.5 | 36.2
| RoBERTa-L
---
Nie et al. (2020)
smfa | 90.6 | 55.6 | 40.0 | 31.9
| BART-L
---
ynie/bart-large-snli_mnli…
smfa | 90.4 | 55.4 | 39.4 | 29.4
| DeBERTaV3-L#2
---
Laurer et al. (2022)
mfalw | 90.3 | 66.5 | 44.4 | 33.8
| XLNet-L-cased
---
Nie et al. (2020)
smfa | 90.3 | 55.8 | 42.5 | 30.0

Table 4: Performance of SOTA NLI systems on SpaceNLI. snli+mnli shows the
average score on these datasets. Training data names are denoted with the
initial letters: SNLI, MNLI, ANLI, Fever-NLI, WANLI, and LingNLI. The best
system per problem accuracy on SpaceNLI, DeBERTaV3-L${}_{\text{MFALW}}$ (with
$\Delta\geq 6.9\%$), doesn’t turn out to be the best at the consistency
threshold $\geq 0.95$. See the extended version of the table in Appendix A.

##  4 Experiments

###  4.1 Sample dataset

We uniformly generated a spatial dataset of 32,000 NLI samples from 160 NLI
patterns, i.e., 200 samples per pattern. We used the mini world as described
in § 3.2. The dataset statistics are given in Table 3. The inference labels
are relatively balanced: each label being represented by at least 30% of the
problems. Each spatial inference type counts at least 20% of the overall
problems and 23% of label-specific problems. In contrast to the common biases
in NLI datasets, a majority of the problems with negation are labeled as
entailment, not contradiction. This is due to perturbed problems introduced in
the revision phases (§ 3.1). Around 39% of problems have multiple premises,
where three-premised problems occur only in the directional problems, the
argument orientation problems contain only single-premised problems, and most
of the multi-premised problems are in the non-projective problems. We refer to
the generated dataset as SpaceNLI and use it in subsequent experiments.777We
make the collection of the patterns, the generation code, and the sample
dataset publicly available upon the acceptance of the paper.

###  4.2 Evaluating SOTA NLI systems

####  4.2.1 Standard accuracy

We selected NLI models that have results comparable to the state of the art in
NLI and evaluate them on SpaceNLI. The models were chosen based on their
availability, tractable size, and high average accuracy ($>90\%$) on the SNLI
(Bowman et al., 2015) and MNLI (Williams et al., 2018) datasets (see Table 4).
The models are based on various large language models (LLMs) like DeBERTaV3
(He et al., 2023), BART (Lewis et al., 2020), ALBERT (Lan et al., 2020), XLNet
(Yang et al., 2020), etc. (see Table 4). The LLMs are fine-tuned on several
NLI train datasets: SNLI, MNLI, FEVER-NLI (Nie et al., 2019), ANLI (Nie et
al., 2020), LingNLI (Parrish et al., 2021), WANLI (Liu et al., 2022). We use
the models from the HuggungFace model hub888https://huggingface.co/models and
provide them with the corresponding hub names in Table 4.

The results in Table 4 show that DeBERTaV3-L#2 trained on a large collection
of training datasets (885K problems in total) generalizes best on the spatial
reasoning (66.5%), achieving a substantial improvement ($\geq 6.9\%$) over the
other models.999The second best, DeBERTaV3-L#1, is based on the same LLM fine-
tuned on a different combination of NLI datasets. Note that Laurer et al.
(2022) deliberately removed SNLI from the training set as it negatively
affected the accuracy of the model in their experiments.

####  4.2.2 Consistency & pattern accuracy

To evaluate the models on the consistency of their predictions for NLI
problems from the same pattern, we define the pattern accuracy (PA) score and
its curve. The PA curve records the PA score of a model for each consistency
threshold. Informally, the PA score with a consistency threshold $t$ is a
ratio of NLI patterns for which model gets at least $t$ portion of the samples
generated from them. For example, the PA of 50% with a threshold 90% means
that there are a half of the NLI patterns such that for each pattern a model
is able to correctly classify at least 90% of its sample problems. The formal
definition of the PA with a threshold $t$ is:

$\displaystyle
P\\!A_{t}(\hat{Y},\mathbf{y})=\frac{1}{N}\sum_{i=1}^{N}\bigg{[}\frac{\sum_{k=1}^{M_{i}}\delta(\hat{y}_{k}^{i}=y^{i})}{M_{i}}\geq
t\bigg{]}$

where $\hat{Y}=(\hat{y}^{i}_{k})_{1\leq i\leq N,1\leq k\leq M_{i}}$ are
predictions for $k^{\text{th}}$ sample of $i^{\text{th}}$ pattern, $N$ is the
number of patterns, $M_{i}$ is the number of samples for $i^{\text{th}}$
pattern, $\mathbf{y}=(y^{i})_{1\leq i\leq N}$ gold labels of $i^{\text{th}}$
pattern, and $\delta$ is the Kronecker delta.

Figure 2: Pattern accuracy curves of the NLI models from Table 4. The first
half, which corresponds to the scores allowing solving less than half of the
samples per pattern, is omitted (see Appendix A for the complete curves).

While DeBERTaV3-L#2 gets the best score on the SpaceNLI problems, based on the
PA scores in Table 4, it shows high consistency ($P\\!A_{0.95}$ or
$P\\!A_{1.0}$) in fewer NLI patterns than the other two competing models,
DeBERTaV3-L#1 and ALBERT-XXLv2. PA curves of the NLI models provide a closer
look at this contrast (see Figure 2). While the curve of DeBERTaV3-L#2
outperforms other models by a margin, it is noteworthy that it does this by
classifying sample problems of the patterns which it can hardly solve half of
the time (this is visible in the complete curves in Appendix A). It
drastically decreases after 95% of consistency while ALBERT-XXLv2 and
DeBERTAV2-L#1 maintain very high consistency for $>47$% of NLI patterns. This
demonstrates that a high-performing model is not necessarily the most
consistent across patterns.

RoBERTa-L and BART-L obtain similar accuracy scores, but RoBERTa-L is more
consistent in more NLI patterns than BART-L while the latter gets slightly
more NLI problems for inconsistently predicted patterns. The complete curves
in Appendix A shows how the curves swap places after the consistency threshold
of 50. This shows that the standard accuracy (i.e., based on NLI problem
samples) can blur the fine distinction in consistency between the models.

The dispersion of the curves at the lowest end of the consistency threshold is
twice larger than at the highest end. This shows that the model predictions
more diverge in coverage of patterns than in consistency per pattern. In other
words, the contrast confirms the sensitivity of the models towards the
inference-preserving word substitutions.

####  4.2.3 Few-shot learning experiments

We measured the difficulty of the SpaceNLI problems in terms of few-shot
learning experiments. We used 100 samples per pattern as a test set while
other 100 samples per pattern were used for drawing a few samples for each
pattern. In this way, the patterns are fully shared between the training and
test sets, but no sample NLI problem is in both sets. For each number of
shots, we carried out the sample drawing process three times. We used two NLI
models: a high performing NLI model RoBERTa-L${}_{\text{SMFA}}$ from Nie et
al. (2020) and a _vanilla_ NLI model based on the large RoBERTa pretrained
language model (Liu et al., 2019). The results of the few-shot experiments are
in Figure 3.

Finetuning RoBERTa-L${}_{\text{SMFA}}$ on a single sample of each pattern
increases the sample-based accuracy on the test set by 14%. Each additional
sample further boosts the model’s accuracy. The almost perfect accuracy (>99%)
is reached when 20 samples per pattern are seen during the finetuning. The
results show that the lexical variability poses a challenge to the high-
performing NLI model as it needs to be finetuned on at least five samples for
every pattern of the test set to achieve a high score.

The challenge coming from the lexical variability and the SpaceNLI patterns is
further emphasized by the relatively low results of RoBERTa Large. Even after
being finetuned on the 20 samples of each NLI pattern, the model is still far
from the high performance on unseen samples (but seen patterns). The
relatively low results can be also partially attributed to the low ratio
between the number of training samples and the large number of the model’s
trainable parameters.

Figure 3: Average of three runs for each few-shot finetuning experiment.
RoBERTa-L (SMFA, Nie et al. 2020) is already finetuned on several large NLI
datasets while RoBERTa Large (Liu et al., 2019) is a pretrained language model
without any previous training on NLI.

Figure 4: Prediction cartography of RoBERTa-large from Nie et al. (2020). NLI
patterns are characterized with _confidence_ and _variability_ : the mean and
the standard deviation of probabilities assigned by the model to the true
labels of the sample NLI problems. IDs mark NLI patterns from Figure 1 and
Table 1.

##  5 Analysis

Figure 5: Sample-based (in light shades) and $P\\!A_{0.95}$ (in dark shades)
accuracy scores of the models per spatial inference type.

To find out what type of inferences the models find challenging, we analyze
the models’ performance per inference type. Figure 5 shows the sample- and
pattern-based accuracy scores of the models per spatial inference types as
defined in § 2.2. The model ranking based on the sample accuracy varies across
the inference types. For instance, the best model, DeBERTaV3-L#2, remains at
the top of the rankings for all inference types with quite a margin except for
the projective type. On average, non-projective spatial inferences are the
most challenging for the models. The easiest of the types is argument
orientation, the type that is closest to the PP attachment task. For the other
inference types, projective inferences are harder than directional ones. The
apparent distinction in the scores between the inference types is also
preserved for the $P\\!A_{0.95}$ score (shown with the dark bars in Figure 5).
The fine-grained analysis additionally shows that the best model,
DeBERTaV3-L#2, suffers least in terms of consistency on the projective
inferences while its performance on this inference type is not among the best.

Based on the results in Figure 5, the non-projective NLI patterns and samples
are the most challenging for the SOTA models. When looking closer at the set
of non-projective problems, it turns out that it contains a high number of
problems (46%) with the spatial expression “between“ (as shown in Table 2),
and these problems are specially challenging due to complex semantics of
“between”. The average accuracy of the models on such NLI samples is 41.6%.
This is lower than the average sample-based accuracy (46.1%) on entire
SpaceNLI and much lower than the average sample-based accuracy (54.1%) on the
other part of the non-projective samples.

We further zoom in on the NLI patterns and measure a model’s probabilistic
predictions for the patterns. Namely, following Swayamdipta et al. (2020), we
measure a model’s confidence and variability. Originally the dataset
cartography (Swayamdipta et al., 2020) was used to analyze the training
dynamics of a model across the epochs and identify training samples that are
easy or difficult for learning. In contrast, we use dataset cartography for
analyzing evaluation dynamics across patterns and identifying easy and hard
ones.101010Put differently, iterative classification of the same training
sample across epochs, is replaced with the classification of the same NLI
pattern based on its samples.

Figure 4 illustrates the pattern-based evaluation dynamics of RoBERTa-L Nie et
al. (2020), an average model based on the evaluations. For instance, NLI
pattern (102f) happens to have one of the most variable samples according to
the model predictions: the mean and the standard deviation of the
probabilities the model assigns to the entailment class of the samples of
(102f) are 0.45 and 0.35, respectively.

(102f) NP1 has hidden NP2 behind NP3.
---
entailment NP2 is not in NP3.

The evaluation cartography shows that the predictions vary mostly for
entailment patterns (in green). Most of the hard patterns are neutral ones (in
blue) and vice versa. Contradiction patterns (in red) tend to be easy with
some variability.

##  6 Related work

Several works have automatically sampled NLI problems from curated
patterns/templates. Jeretic et al. (2020) generated the implicature and
presupposition diagnostic dataset IMPPRES from pre-defined templates. McCoy et
al. (2019) constructed the HANS dataset by designing templates of NLI problems
that support or refute certain inference heuristics, which were later used to
generate NLI problems. Richardson et al. (2020) used the template language
from Salvatore et al. (2019) to produce NLI problems involving negation,
Boolean connectives, quantifiers, cardinals, conditionals, and comparatives.
These works all use restricted vocabulary while generating samples from the
patterns.

With its pattern-based construction and restricted vocabulary, SpaceNLI comes
close to the IMPPRES (Jeretic et al., 2020) and HANS (McCoy et al., 2019)
datasets. Unlike these datasets, SpaceNLI involves multiple-premised problems
and puts more emphasis on satisfying selection restrictions to prevent
nonsensical sentences.

Based on the nature of NLI problems, SpaceNLI resembles FraCaS (Cooper et al.,
1996) as both contain inference problems often found in textbooks on formal
semantics. Unlike FraCaS, the inference labels of patterns in SpaceNLI are
quite balanced and the number of spatial NLI patterns is twice the size of the
largest section in FraCaS.

There have been attempts to identify semantic phenomena in existing NLI
datasets, including aspects of spatial reasoning. By looking up certain
keywords, Kim et al. (2019) automatically detect NLI problems in MultiNLI
(Williams et al., 2018) that might contain spatial expressions. They create a
mutated sample from the original NLI problem by negating the sentence with the
potential spatial expression. Joshi et al. (2020) annotate MultiNLI problems
based on the semantic aspects required by the inference label. Their taxonomic
categories include the spatial subcategory, grouped with the relational,
temporal, causal, and co-reference subcategories.

The problems in SpaceNLI are substantially diverse from a semantic perspective
than the MultiNLI problems that were identified by Kim et al. (2019) and Joshi
et al. (2020). The MultiNLI dataset is crowd-elicited and doesn’t have
problems with sufficient depth in spatial reasoning.

##  7 Conclusion

To the best of our knowledge, we have created the first spatial inference
dataset that involves diverse spatial inference types. The structure and the
evaluation protocol are unique as we focus on performance on the NLI patterns
and consistency across the samples in the pattern, instead of focusing on mere
quantitative accuracy based on the NLI problems/samples. The evaluation
protocol tests models whether they can consistently recognize inference
patterns while generalizing over _irrelevant_ lexical substitutions. The more
consistent a model is in its predictions, the less unexpected its behavior
becomes.

The SOTA NLI models show moderate generalization capacity on spatial problems.
While the top-performing model gets the highest overall accuracy, it is ranked
third when it comes to the consistency of predictions inside the patterns:
predicting at least 95% of the samples per pattern.

The introduced pattern accuracy (PA) curves provide a more fine-grained
distinction between the models: the models with comparable standard accuracy
scores might substantially differ in the consistency of their predictions.
Overall the performance of models drops ca. 10% when raising the consistency
threshold to 95%. This illustrates that the predictions of the SOTA models are
sensitive to lexical replacements that have no effect on the semantics of the
inference.

The evaluation results revealed that the most challenging inference type is
associated with non-projective locatives mainly due to the complex semantics
of “between” while the argument orientation type is the easiest. The latter is
somewhat expected as the problems in the argument orientation type are close
to the task of PP attachment which LLMs are expected to be good at.

## Acknowledgments

This work was funded by the European Research Council (ERC) under the European
Union’s Horizon 2020 research and innovation programme (grant agreement No
742204). We would like to acknowledge the help from three student assistants
with the data annotation and thank the anonymous reviewers for their helpful
comments.

## References

  * Antol et al. (2015) Stanislaw Antol, Aishwarya Agrawal, Jiasen Lu, Margaret Mitchell, Dhruv Batra, C. Lawrence Zitnick, and Devi Parikh. 2015.  VQA: Visual Question Answering.  In _International Conference on Computer Vision (ICCV)_.
  * Bowman et al. (2015) Samuel R. Bowman, Gabor Angeli, Christopher Potts, and Christopher D. Manning. 2015\.  A large annotated corpus for learning natural language inference.  In _Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing_ , pages 632–642, Lisbon, Portugal. Association for Computational Linguistics.
  * Cooper et al. (1996) Robin Cooper, Dick Crouch, Jan Van Eijck, Chris Fox, Josef Van Genabith, Jan Jaspars, Hans Kamp, David Milward, Manfred Pinkal, Massimo Poesio, Steve Pulman, Ted Briscoe, Holger Maier, and Karsten Konrad. 1996.  _FraCaS: A Framework for Computational Semantics_.  Deliverable D16.
  * Gardner et al. (2020) Matt Gardner, Yoav Artzi, Victoria Basmov, Jonathan Berant, Ben Bogin, Sihao Chen, Pradeep Dasigi, Dheeru Dua, Yanai Elazar, Ananth Gottumukkala, Nitish Gupta, Hannaneh Hajishirzi, Gabriel Ilharco, Daniel Khashabi, Kevin Lin, Jiangming Liu, Nelson F. Liu, Phoebe Mulcaire, Qiang Ning, Sameer Singh, Noah A. Smith, Sanjay Subramanian, Reut Tsarfaty, Eric Wallace, Ally Zhang, and Ben Zhou. 2020.  Evaluating models’ local decision boundaries via contrast sets.  In _Findings of the Association for Computational Linguistics: EMNLP 2020_ , pages 1307–1323, Online. Association for Computational Linguistics.
  * Glockner et al. (2018) Max Glockner, Vered Shwartz, and Yoav Goldberg. 2018.  Breaking NLI systems with sentences that require simple lexical inferences.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pages 650–655, Melbourne, Australia. Association for Computational Linguistics.
  * Gururangan et al. (2018) Suchin Gururangan, Swabha Swayamdipta, Omer Levy, Roy Schwartz, Samuel Bowman, and Noah A. Smith. 2018.  Annotation artifacts in natural language inference data.  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 107–112, New Orleans, Louisiana. Association for Computational Linguistics.
  * He et al. (2023) Pengcheng He, Jianfeng Gao, and Weizhu Chen. 2023.  DeBERTav3: Improving deBERTa using ELECTRA-style pre-training with gradient-disentangled embedding sharing.  In _The Eleventh International Conference on Learning Representations_.
  * He et al. (2021) Pengcheng He, Xiaodong Liu, Jianfeng Gao, and Weizhu Chen. 2021.  Deberta: Decoding-enhanced bert with disentangled attention.
  * Herskovits (1986) Annette Herskovits. 1986.  _Language and Spatial Cognition: an interdisciplinary study of the prepositions in English_.  Studies in Natural Language Processing. Cambridge University Press, London.
  * Hossain et al. (2020) Md Mosharaf Hossain, Venelin Kovatchev, Pranoy Dutta, Tiffany Kao, Elizabeth Wei, and Eduardo Blanco. 2020.  An analysis of natural language inference benchmarks through the lens of negation.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 9106–9118, Online. Association for Computational Linguistics.
  * Hudson and Manning (2019) Drew A Hudson and Christopher D Manning. 2019.  Gqa: A new dataset for real-world visual reasoning and compositional question answering.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 6700–6709.
  * Jeretic et al. (2020) Paloma Jeretic, Alex Warstadt, Suvrat Bhooshan, and Adina Williams. 2020.  Are natural language inference models IMPPRESsive? Learning IMPlicature and PRESupposition.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 8690–8705, Online. Association for Computational Linguistics.
  * Johnson et al. (2017) Justin Johnson, Bharath Hariharan, Laurens van der Maaten, Li Fei-Fei, C. Lawrence Zitnick, and Ross Girshick. 2017.  Clevr: A diagnostic dataset for compositional language and elementary visual reasoning.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_.
  * Joshi et al. (2020) Pratik Joshi, Somak Aditya, Aalok Sathe, and Monojit Choudhury. 2020.  TaxiNLI: Taking a ride up the NLU hill.  In _Proceedings of the 24th Conference on Computational Natural Language Learning_ , pages 41–55, Online. Association for Computational Linguistics.
  * Kaushik et al. (2020) Divyansh Kaushik, Eduard Hovy, and Zachary C Lipton. 2020.  Learning the difference that makes a difference with counterfactually augmented data.  _International Conference on Learning Representations (ICLR)_.
  * Kim et al. (2019) Najoung Kim, Roma Patel, Adam Poliak, Patrick Xia, Alex Wang, Tom McCoy, Ian Tenney, Alexis Ross, Tal Linzen, Benjamin Van Durme, Samuel R. Bowman, and Ellie Pavlick. 2019.  Probing what different NLP tasks teach machines about function word comprehension.  In _Proceedings of the Eighth Joint Conference on Lexical and Computational Semantics (*SEM 2019)_ , pages 235–249, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Kober et al. (2019) Thomas Kober, Sander Bijl de Vroe, and Mark Steedman. 2019.  Temporal and aspectual entailment.  In _Proceedings of the 13th International Conference on Computational Semantics - Long Papers_ , pages 103–119, Gothenburg, Sweden. Association for Computational Linguistics.
  * Lan et al. (2020) Zhenzhong Lan, Mingda Chen, Sebastian Goodman, Kevin Gimpel, Piyush Sharma, and Radu Soricut. 2020.  Albert: A lite bert for self-supervised learning of language representations.
  * Laurer et al. (2022) Moritz Laurer, Wouter van Atteveldt, Andreu Casas, and Kasper Welbers. 2022.  Less Annotating, More Classifying – Addressing the Data Scarcity Issue of Supervised Machine Learning with Deep Transfer Learning and BERT-NLI.
  * Lewis et al. (2020) Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Veselin Stoyanov, and Luke Zettlemoyer. 2020.  BART: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 7871–7880, Online. Association for Computational Linguistics.
  * Liu et al. (2022) Alisa Liu, Swabha Swayamdipta, Noah A. Smith, and Yejin Choi. 2022.  WANLI: Worker and AI collaboration for natural language inference dataset creation.  In _Findings of the Association for Computational Linguistics: EMNLP 2022_ , pages 6826–6847, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  Roberta: A robustly optimized bert pretraining approach.  Cite arxiv:1907.11692.
  * MacCartney (2009) Bill MacCartney. 2009.  _Natural language inference_.  Phd thesis, Stanford University.
  * McCoy et al. (2019) Tom McCoy, Ellie Pavlick, and Tal Linzen. 2019.  Right for the wrong reasons: Diagnosing syntactic heuristics in natural language inference.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 3428–3448, Florence, Italy. Association for Computational Linguistics.
  * Mirzaee et al. (2021) Roshanak Mirzaee, Hossein Rajaby Faghihi, Qiang Ning, and Parisa Kordjamshidi. 2021\.  SPARTQA: A textual question answering benchmark for spatial reasoning.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 4582–4598, Online. Association for Computational Linguistics.
  * Naik et al. (2018) Aakanksha Naik, Abhilasha Ravichander, Norman Sadeh, Carolyn Rose, and Graham Neubig. 2018.  Stress test evaluation for natural language inference.  In _Proceedings of the 27th International Conference on Computational Linguistics_ , pages 2340–2353, Santa Fe, New Mexico, USA. Association for Computational Linguistics.
  * Nam (1995) Seungho Nam. 1995.  _The Semantics of Locative Prepositional Phrases in English_.  Phd thesis, University of California, Los Angeles.
  * Nie et al. (2019) Yixin Nie, Haonan Chen, and Mohit Bansal. 2019.  Combining fact extraction and verification with neural semantic matching networks.  In _Association for the Advancement of Artificial Intelligence (AAAI)_.
  * Nie et al. (2020) Yixin Nie, Adina Williams, Emily Dinan, Mohit Bansal, Jason Weston, and Douwe Kiela. 2020.  Adversarial NLI: A new benchmark for natural language understanding.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 4885–4901, Online. Association for Computational Linguistics.
  * Parrish et al. (2021) Alicia Parrish, William Huang, Omar Agha, Soo-Hwan Lee, Nikita Nangia, Alexia Warstadt, Karmanya Aggarwal, Emily Allaway, Tal Linzen, and Samuel R. Bowman. 2021\.  Does putting a linguist in the loop improve NLU data collection? In _Findings of the Association for Computational Linguistics: EMNLP 2021_ , pages 4886–4901, Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Poliak et al. (2018) Adam Poliak, Jason Naradowsky, Aparajita Haldar, Rachel Rudinger, and Benjamin Van Durme. 2018.  Hypothesis only baselines in natural language inference.  In _Proceedings of the Seventh Joint Conference on Lexical and Computational Semantics_ , pages 180–191, New Orleans, Louisiana. Association for Computational Linguistics.
  * Ribeiro et al. (2020) Marco Tulio Ribeiro, Tongshuang Wu, Carlos Guestrin, and Sameer Singh. 2020.  Beyond accuracy: Behavioral testing of NLP models with CheckList.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 4902–4912, Online. Association for Computational Linguistics.
  * Richardson et al. (2020) Kyle Richardson, Hai Hu, Lawrence S. Moss, and Ashish Sabharwal. 2020.  Probing natural language inference models through semantic fragments.  In _The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020_ , pages 8713–8721. AAAI Press.
  * Salvatore et al. (2019) Felipe Salvatore, Marcelo Finger, and Roberto Hirata Jr. 2019.  A logical-based corpus for cross-lingual evaluation.  In _Proceedings of the 2nd Workshop on Deep Learning Approaches for Low-Resource NLP (DeepLo 2019)_ , pages 22–30, Hong Kong, China. Association for Computational Linguistics.
  * Stenetorp et al. (2012) Pontus Stenetorp, Sampo Pyysalo, Goran Topić, Tomoko Ohta, Sophia Ananiadou, and Jun’ichi Tsujii. 2012.  brat: a web-based tool for NLP-assisted text annotation.  In _Proceedings of the Demonstrations at the 13th Conference of the European Chapter of the Association for Computational Linguistics_ , pages 102–107, Avignon, France. Association for Computational Linguistics.
  * Suhr et al. (2017) Alane Suhr, Mike Lewis, James Yeh, and Yoav Artzi. 2017.  A corpus of natural language for visual reasoning.  In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pages 217–223, Vancouver, Canada. Association for Computational Linguistics.
  * Swayamdipta et al. (2020) Swabha Swayamdipta, Roy Schwartz, Nicholas Lourie, Yizhong Wang, Hannaneh Hajishirzi, Noah A. Smith, and Yejin Choi. 2020.  Dataset cartography: Mapping and diagnosing datasets with training dynamics.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 9275–9293, Online. Association for Computational Linguistics.
  * Tsuchiya (2018) Masatoshi Tsuchiya. 2018.  Performance impact caused by hidden bias of training data for recognizing textual entailment.  In _Proceedings of the Eleventh International Conference on Language Resources and Evaluation (LREC 2018)_ , Miyazaki, Japan. European Language Resources Association (ELRA).
  * Weston et al. (2016) Jason Weston, Antoine Bordes, Sumit Chopra, and Tomás Mikolov. 2016.  Towards ai-complete question answering: A set of prerequisite toy tasks.  In _4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings_.
  * Williams et al. (2018) Adina Williams, Nikita Nangia, and Samuel Bowman. 2018.  A broad-coverage challenge corpus for sentence understanding through inference.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)_ , pages 1112–1122. Association for Computational Linguistics.
  * Yanaka et al. (2020) Hitomi Yanaka, Koji Mineshima, Daisuke Bekki, and Kentaro Inui. 2020.  Do neural models learn systematicity of monotonicity inference in natural language? In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 6105–6117, Online. Association for Computational Linguistics.
  * Yanaka et al. (2019a) Hitomi Yanaka, Koji Mineshima, Daisuke Bekki, Kentaro Inui, Satoshi Sekine, Lasha Abzianidze, and Johan Bos. 2019a.  Can neural networks understand monotonicity reasoning? In _Proceedings of the 2019 ACL Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP_ , pages 31–40, Florence, Italy. Association for Computational Linguistics.
  * Yanaka et al. (2019b) Hitomi Yanaka, Koji Mineshima, Daisuke Bekki, Kentaro Inui, Satoshi Sekine, Lasha Abzianidze, and Johan Bos. 2019b.  HELP: A dataset for identifying shortcomings of neural models in monotonicity reasoning.  In _Proceedings of the Eighth Joint Conference on Lexical and Computational Semantics (*SEM 2019)_ , pages 250–255, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Yang et al. (2020) Zhilin Yang, Zihang Dai, Yiming Yang, Jaime Carbonell, Ruslan Salakhutdinov, and Quoc V. Le. 2020.  Xlnet: Generalized autoregressive pretraining for language understanding.
  * Zhang et al. (2017) Sheng Zhang, Rachel Rudinger, Kevin Duh, and Benjamin Van Durme. 2017.  Ordinal common-sense inference.  _Transactions of the Association for Computational Linguistics_ , 5:379–395.
  * Zwarts and Winter (2000) Joost Zwarts and Yoad Winter. 2000.  Vector space semantics: A model-theoretic analysis of locative prepositions.  _Journal of logic, language and information_ , 9:169–211.

LLM-based NLI models (train data) model names from Huggingface hub | snli | m${}_{\text{m}}$ | m${}_{\text{mm}}$ | s+m | SpaceNLI (accuracy & $\geq$ consistency score)
---|---|---|---|---|---
Acc | $\geq 0.5$ | $\geq 0.67$ | $\geq 0.9$ | $\geq 0.95$ | $=1.0$
| DeBERTaV3-L#1 (SMFA)
---
Joelzhang/deberta-v3-large-snli_mnli_fever_anli…
92.9 | 91.4 | 91.2 | 91.8 | 59.6 | 59.4 | 57.5 | 50.0 | 47.5 | 37.5
| ALBERT-XXLv2 (SMFA)
---
ynie/albert-xxlarge-v2-snli_mnli_fever_anli_R1_…
91.9 | 90.2 | 90.2 | 90.8 | 57.8 | 58.8 | 56.2 | 50.0 | 48.1 | 36.2
| DeBERTa-L (MNLI) (He et al., 2021)
---
microsoft/deberta-large-mnli
89.6 | 91.3 | 91.1 | 90.7 | 54.1 | 55.6 | 50.6 | 45.6 | 42.5 | 36.2
| RoBERTa-L (SMFA) (Nie et al., 2020)
---
ynie/roberta-large-snli_mnli_fever_anli_R1_R2_R…
91.8 | 89.9 | 90.0 | 90.6 | 55.6 | 55.0 | 52.5 | 43.8 | 40.0 | 31.9
| BART-L (SMFA)
---
ynie/bart-large-snli_mnli_fever_anli_R1_R2_R3-nli
92.0 | 89.4 | 89.6 | 90.4 | 55.4 | 55.0 | 48.8 | 41.2 | 39.4 | 29.4
| DeBERTaV3-L#2 (MFALW) (Laurer et al., 2022)
---
MoritzLaurer/DeBERTa-v3-large-mnli-fever-anli-l…
89.0 | 91.2 | 90.8 | 90.3 | 66.5 | 68.8 | 61.9 | 51.2 | 44.4 | 33.8
| XLNet-L-cased (SMFA) (Nie et al., 2020)
---
ynie/xlnet-large-cased-snli_mnli_fever_anli_R1_…
91.7 | 89.8 | 89.5 | 90.3 | 55.8 | 56.9 | 53.1 | 46.2 | 42.5 | 30.0

Table 5: Performance of NLI models on SpaceNLI and common NLI benchmarks:
SNLI-test, MNLI-val-matched, and MNLI-val-mismatched. S+M shows the average of
the three accuracy scores. Training data names are denoted with the initial
letters: SNLI, MNLI, ANLI, Fever-NLI, WANLI, and LingNLI. The best model per
problem accuracy on SpaceNLI, DeBERTaV3-L${}_{\text{MFALW}}$ (with $\Delta\geq
6.9\%$), doesn’t turn out to be the best at the consistency threshold $\geq
0.95$.

Figure 6: Pattern accuracy curves of the NLI models from Table 4. The area
under the curve represents a standard NLI problem-based accuracy.

##  Appendix A Results

Table 5 represents the extended version of Table 4. Note that the area under
the curve corresponds to the standard accuracy based on the NLI problems.


# PolyLUT: Learning Piecewise Polynomials for Ultra-Low Latency FPGA LUT-based
Inference

Marta Andronic and George A. Constantinides  Department of Electrical and
Electronic Engineering
Imperial College London, UK
Email: {marta.andronic18<EMAIL_ADDRESS>
###### Abstract

Field-programmable gate arrays (FPGAs) are widely used to implement deep
learning inference. Standard deep neural network inference involves the
computation of interleaved linear maps and nonlinear activation functions.
Prior work for ultra-low latency implementations has hardcoded the combination
of linear maps and nonlinear activations inside FPGA lookup tables (LUTs). Our
work is motivated by the idea that the LUTs in an FPGA can be used to
implement a much greater variety of functions than this. In this paper, we
propose a novel approach to training neural networks for FPGA deployment using
multivariate polynomials as the basic building block. Our method takes
advantage of the flexibility offered by the soft logic, hiding the polynomial
evaluation inside the LUTs with zero overhead. We show that by using
polynomial building blocks, we can achieve the same accuracy using
considerably fewer layers of soft logic than by using linear functions,
leading to significant latency and area improvements. We demonstrate the
effectiveness of this approach in three tasks: network intrusion detection,
jet identification at the CERN Large Hadron Collider, and handwritten digit
recognition using the MNIST dataset.

##  I Introduction and Motivation

Deep learning (DL) is a powerful technique for extracting abstract features
from raw data and has shown remarkable success in various applications such as
image classification and natural language processing [1]. Deploying these
models to the cloud leads to the inability to produce results in real-time,
security concerns, and increased latency and round-trip delay [2]. As a
result, there is a growing interest in deploying DL models on edge devices.
However, due to the models’ high computational cost and power and memory
requirements, this has proven to be a challenging task [3].

An approach that has been proposed to address the high computational cost of
neural networks and the infeasibility of deployment on memory-constrained
platforms is the binary neural network (BNN) [2]. Through the binarization of
weights and activations, on-chip memory is saved and, together with the
replacement of multi-bit multipliers with lightweight XNOR gates, it has been
suggested that BNNs can provide an area- and energy- efficient solution that
removes redundancy while maintaining high classification accuracy after
retraining.

However, BNNs are still not perfect for FPGAs because they do not take
advantage of the underlying FPGA architecture. In particular, the XNOR gates
and parts of the popcount logic end up mapped onto $K$-LUTs, which are capable
of implementing arbitrary Boolean functions with limited support. Prior works
that use LUTs as more than just XNORs can be divided in two categories:
Differentiable LUTs (LUTNet [4]) and LUT-based traditional networks (LogicNets
[5], NullaNet [6]).

Wang et al. introduced LUTNet, the first neural network architecture in which
the BNNs’ XNOR operations are replaced by learned $K$-input Boolean operations
[4]. By using the full flexibility of the LUTs, LUTNet reaches high logic
density, allowing heavy network pruning. However, the design is bottlenecked
by large adder trees and the number of parameters that need to be trained
scales exponentially with the number of LUT inputs. In contrast, LogicNets and
NullaNet are two architectures that encapsulate all the operations that happen
between the quantized inputs and the quantized outputs of a traditional linear
+ activation neuron, enumerating the LUT contents and hence generating a
netlist of LUTs.

We expand on the idea of converting a neural network into a netlist of LUTs by
exploiting the LUTs’ ability to implement a wide range of functions. A neural
network consisting of linear layers and rectified linear units taken as a
whole computes a continuous piecewise linear function. Rather than training
these traditional functions, we suggest training continuous piecewise
polynomial functions. This approach offers the advantage of providing a high
degree of flexibility in fitting training data while maintaining unchanged
truth table sizes. We are able to show that significantly shallower, and hence
lower-latency, networks are possible as a result. We perform the polynomial
transform inside each neuron by augmenting the feature space with all of its
monomials of degree at most some tunable constant, $D$, providing a tunable
trade-off between generality, potential for overfitting, and the number of
training parameters.

Our aim is to enable applications that require ultra-low latency real-time
processing and highly lightweight on-chip implementations. Examples include
the classification of particle collision events [7], the detection of
malicious network traffic [8], and image classification for real-time systems,
hence in common with other work in this field, we focus on networks that can
be implemented entirely on a single FPGA.

(a) LUTNet - $K$-LUTs, here $3$-LUTs, replace the XNORs present in a BNN. $x$
would be the input vector to the XNORs. $x_{r}$ and $x_{r^{\prime}}$ are
random selections (with replacement) from $x$.

(b) LogicNets - LUTs are used to absorb all the operations between the
quantized inputs and quantized output.

(c) PolyLUT - LUTs are used in the same context as LogicNets, however, inside
the neuron a multivariate polynomial of degree $D$, here $D=2$, replaces the
linear transformation.

Figure 1: Structural use of LUTs for a single output channel in prior works
(a,b) and our approach (c).

This paper makes the following novel contributions:

  * •

We present an open source framework called PolyLUT, the first quantized neural
network training methodology that maps a neuron to a LUT while using
multivariate polynomial function learning to exploit the flexibility of the
FPGA soft logic.111https://github.com/MartaAndronic/PolyLUT

  * •

We expose the degree of the monomials as a training hyperparameter that can be
adjusted to increase the flexibility of the functions. We show empirically
that higher degrees increase the ability of the model to fit the training data
which allows network depth reductions.

  * •

For the chosen datasets, we demonstrate the effectiveness of PolyLUT at
deployment, achieving shallower networks for the same accuracy, resulting in
network inference times of $\sim 10\text{ns}$ and Pareto optimal resource
utilization. For example, on the jet substructure classification task, we
demonstrate a 2-layer piecewise polynomial network achieving the same accuracy
as a 4-layer piecewise linear network while offering a significant
$2.69\times$ area compression combined with a $2.29\times$ reduction in
latency.

##  II Background

The migration of deep learning models from the cloud to the edge presents
challenges attributed to limited computational resources [2]. To address these
challenges, current research is primarily focused on employing various
techniques such as compression, algorithm-hardware co-design, and hardware
accelerators. Table I summarizes techniques used in prior low-latency FPGA
implementations.

###  II-A Low latency FPGA accelerators

FINN is a framework originally designed for building BNN accelerators that
reached the fastest classification rates on MNIST at the time of first
publication [9]. Ngadiuba et al. [10] also implement fully unrolled binary and
ternary neural networks in the hls4ml package, which maps neural networks to
FPGA circuits to target reduced computation time and resource utilization. In
contrast, Duarte et al. [7] use hls4ml but adopt higher network precision to
generate accurate and fast fully-unrolled and rolled designs at the cost of
high digital signal processing (DSP) block usage. Fahim et al. build upon
these two hls4ml works and also leverage the insights from prior approaches
using boosted decision trees [11] and quantization-aware training [12].
Additionally, Fahim et al. introduce new low power techniques, such as
quantization-aware pruning to enhance performance and efficiency. Another
real-time implementation of BNNs is presented by Murovic et al. [8] who
achieve high performance by exploiting full parallelization.

TABLE I: Key features of prior low-latency accelerators. Tool | Precision | Pruning | Implementation
---|---|---|---
|  |  | type
FINN | Binary | None | XNOR-based
[9]
Ngadiuba | Binary/ | None | XNOR-based
et al. [10] | Ternary
Duarte | Fixed point | Iterative pruning | DSP-based
et al. [7]
Fahim | Fixed point | Quantization-aware | DSP-based
et al. [13] | iterative pruning
Murovic | Binary | None | XNOR-based
et al. [8]
LUTNet | Residual | Pruning on | LUT-based
[4] | binarization | full-precision model
LogicNets | Low-bit | A priori | LUT-based
[5] | fixed sparsity

###  II-B BNN-specific micro-architectures using FPGA LUTs

####  II-B1 Differentiable LUTs

LUTNet replaced the dot product between the feature vector and weight vector
with a sum of learned Boolean functions that can each be computed using a
single $K$-LUT. The structure of LUTNet can be visualized in Figure 1(a),
where $K=3$ and $x_{r}$ and $x_{r^{\prime}}$ are vectors generated by randomly
selecting (with replacement) from the input vector $x$. Therefore, in LUTNet,
each input can participate multiple times in the weighted summation and
redundant operations can be reduced with the help of network pruning, while
maintaining accuracy [4].

Compared to PolyLUT, LUTNet contains exposed datapaths within neurons,
exhibits exponential scaling of training parameters with LUT input size, and
supports a single level of quantization.

####  II-B2 LUT-based traditional networks

NullaNet [6] proposes viewing layers as multi-input multi-output Boolean
functions that can be optimized through Boolean logic minimization. To address
the exponential growth of the size of the truth tables, output values are
determined only for a strict subset of input combinations with logic synthesis
treating the others as don’t-care conditions. LogicNets [5] is designed for
very low latency processing. LogicNets uses high sparsity to reduce the large
fan-in in order to combat the disadvantage of NullaNet’s lossy truth table
sampling method. Our work utilizes the same a priori fixed sparsity technique
as LogicNets, based on expander graph theory [14]. Figure 1(b) shows the
structure of a LogicNets neuron. Due to sparsity, the input vector $x$ is of
size $F\ll N$, with $F=3$ in the figure. After training, the function that
gets absorbed inside the LUT can be expressed as in (1), where $\phi$ is the
quantized activation function, $w$ is the real weight vector, and $b$ is the
real bias term.

$y_{0}=\phi\left[\sum_{i=0}^{F}w_{i}x_{i}+b\right]$ (1)

##  III Methodology

The novelty of our work comes through the expansion of the feature vector $x$
at each neuron with all the monomials up to a parametric degree. Figure 1(c)
illustrates PolyLUT’s expansion for $D=2$. When $D=1$, PolyLUT’s behavior
becomes linear and it is equivalent to LogicNets. It is thus a strict
generalization of LogicNets.

###  III-A Theoretical approach

Provided with a sufficient number of neurons, a deep neural network is capable
of modeling any function within a given error margin. However, there is
theoretical evidence [15] that multiplicative interactions are a way of
integrating contextual information in a neural network. It is proven that the
hypothesis space of a traditional multi-layer perceptron with rectified linear
unit activation functions is strictly included in the hypothesis space of an
equivalent network with each linear layer replaced by a multiplicative layer
[15]. Therefore, multiplicative interactions enlarge the hypotheses space
allowing for improved representational power, improved modeling of
interactions and robustness.

In a direct implementation, integrating multiplicative interactions in the
neural network would increase the processing cost, however, in a LUT-based
model, this additional complexity is entirely absorbed inside the LUT, and no
additional multiplication hardware is required. This is the key to our
approach, leading to a significant boost in model performance without
overhead. We are able to recycle the increase in function complexity within
each layer to reduce the number of layers required to achieve a given
accuracy.

Our fully-trainable layers can be described in the following way. Consider a
vector $x$ of inputs to a standard neural network layer. We may first form all
multiplicative combinations of these inputs up to a parametric degree $D$. For
example, if a given input vector is two-dimensional and $D=3$, then model
construction arises from the following transformation:
$[x_{0},x_{1}]\mapsto[1,x_{0},x_{1},x_{0}^{2},x_{0}x_{1},x_{1}^{2},x_{0}^{3},x_{0}^{2}x_{1},x_{0}x_{1}^{2},x_{1}^{3}]$.
The size of the feature vectors will see an increase from $N$ to
$\frac{(N+D)!}{N!D!}$, where $D$ can be seen as a hyperparameter allowing a
smooth variation from a number of terms linear in $N$ when $D=1$, equivalent
to LogicNets, to a number of terms exponential in $N$ when $D=N$, akin to
LUTNet, as seen in Table II. After this transformation, we apply a standard
linear layer + activation to the resulting expanded feature vector. This can
therefore be seen as replacing (1) with (2), where $M$ is equal to the number
of monomials $m(x)$ of degree at most $D$ in $F$ variables.

$y_{0}=\phi\left[\sum_{i=0}^{M}w_{i}m_{i}(x)\right]\text{, where
M}=\left(F+D\atop D\right)$ (2)

TABLE II: Number of parameters for a $\beta N$-input LUT. $\beta$ represents the input bitwidth and $N$ the number of inputs. PolyLUT’s number of parameters lies between Logicnets’ and LUTNet’s number of parameters. In contrast to LUTNet, LogicNets’ and PolyLUT’s number of parameters is independent of the input bitwidth. | Number of parameters | Scaling type
---|---|---
LUTNet | $2^{\beta N}$ | Exponential
PolyLUT | $\left(N+D\atop D\right)$ | Polynomial for
fixed D
LogicNets | $N+1$ | Linear

A common activation function in deep learning is the rectified linear unit
(ReLU). From a functional perspective, each ReLU partitions the input space
into two linear sub-regions. As the network depth increases, more piecewise
linear surfaces are generated.

In the polynomial setting, the input space is transformed into a surface
described by a multivariate polynomial function. This polynomial
transformation offers significantly greater flexibility and expressive power
compared to a linear transformation. As a result, a network that incorporates
polynomial transformations can accurately capture complex relationships in the
data using fewer “folds” or neurons.

Figure 2: Visual representation of a 3-layer network.

(a) Continuous piecewise linear function.

(b) Continuous piecewise polynomial function.

Figure 3: Input transformations visualized as contour graphs at the output of
each neuron. The black and red dots represent the training data points.

To visually illustrate this concept, we present a two-dimensional toy network
in Figure 2, which we have trained in two different settings. The first
setting incorporated linear functions and the second setting polynomial
functions of degree equal to three. The resulting transformations can be
observed in Figure 3. We have used a fictional dataset of two spirals, each
representing a class (black and red).

In Figure 3(a), the formation of the piecewise linear surface can be
visualized at the output of each neuron, as a contour graph. As expected, the
first layer of neurons tries to separate the data using a single line.
Following, the second layer brings in another linear transformation that
results in two separate lines on the contour graph. Consequently, the final
classification contains four distinct linear shapes and the darker shades
express an increased level of confidence. The importance of the ReLU function
can also be visualized, which prevents the network from collapsing into one
single linear function. Looking at the final piecewise linear classification
it is possible to observe that four linear functions are insufficient to
separate the data faithfully due to the high degree of overlap in the training
data. In order to increase the accuracy of the classification there would be a
need to increase the width or depth of the network.

In Figure 3(b), the formation of the piecewise polynomial surface is shown. It
is evident from the graphs that the piecewise polynomial surface can adopt
more intricate shapes, enabling it to distinguish more complex data patterns.
The network is able to fit the training data with significantly better
accuracy, being able to separate the intertwined spirals. In contrast to the
linear case, which is implemented in LogicNets, the polynomial model
introduces enhanced data fitting capabilities, facilitating better
representation of the underlying data patterns.

A high-degree multivariate polynomial model introduces more degrees of
freedom, which can lead to overfitting. To mitigate these issues, two
regularization techniques can be employed: reducing the number of layers or
decreasing the degree of the polynomial. The former leads to better
generalization through the reduction of the number of polynomial regions. The
latter increases the generalization while maintaining the same number of
layers. By controlling the model’s complexity through layer reduction,
significant resources can be saved. Moreover, this approach leads to a
reduction in the number of clock cycles required to classify input data,
thereby improving computational efficiency.

LUTNet and PolyLUT differ in several key aspects, one of which is the number
of operations absorbed inside the LUTs. With PolyLUT, not only is the weighted
feature vector absorbed, but also the summation, activation, and quantization
functions, resulting in no exposed datapath within a neuron. Another notable
difference is the choice of real functions used for network training. LUTNet
trains LUT functions using the fixed degree Lagrange interpolating polynomial,
whereas PolyLUT trains the coefficients of each monomial. Consequently,
PolyLUT enables variations in function complexity through degree adjustment
during training and allows the reduction of the trainable parameters, as per
Table II. Moreover, the exponential increase in the number of parameters in
LUTNet is dependent on bitwidth ($\beta$). The final key difference is that
LUTNet operates solely in the binary space, while PolyLUT supports any level
of quantization.

###  III-B Hardware approach

A lookup table is capable of evaluating any function with quantized inputs and
outputs. For a fixed number of LUT inputs, the time complexity of evaluation
is independent of the complexity of the function stored in the LUT, making it
ideal for implementing computationally intensive functions. By mapping complex
computations to lookup tables, their full potential can be leveraged.

The primary component of the soft logic in an FPGA is the $K$-LUT, which can
implement any Boolean function with $K$ inputs and one output. Utilizing truth
tables to represent the computation of an artificial neuron proves highly
efficient as it combines multiple operations such as multiplication,
summation, activation, quantization, and normalization into a single operation
that can be executed within a single clock cycle or less.

It is important to note that the size of a lookup table grows exponentially
with the number of inputs. To address this, we follow LogicNets by introducing
extreme sparsity, limiting the number of inputs a neuron can accept to a fan-
in of $F$ and we apply heavy quantization, constraining the bit-width of the
inputs to $\beta<4\text{ bits}$. As a result, the size of the truth tables
becomes $\mathcal{O}(2^{\beta\cdot F})$. The complexity of the truth tables is
therefore established through a trade-off between the precision of data
representation and the sparsity of the network.

###  III-C Building a neural network of LUTs

PolyLUT is a deep neural network (DNN) co-design methodology that builds upon
LogicNets’ toolflow [5] which realizes the training of quantized DNNs,
conversion to truth-tables, and generation of hardware netlists. The training
implementation was changed to accommodate PolyLUT. The toolflow’s complete
structure can be visualized in Figure 4.

####  III-C1 DNN Training

For the DNN training process, we utilize a PyTorch framework. Upon training,
certain specifications are required from the user, including the dataset,
model layer sizes, fan-in, bit-width, degree, and other machine learning-
specific parameters such as learning rate and weight decay.

Figure 4: High-level view of PolyLUT’s toolflow. We built upon the open-source
LogicNets toolflow. We show in red the elements that were modified.

The Pytorch framework includes a parameter, degree, to control the complexity
of the monomials. This parameter allows for adjusting the complexity of the
model and can also be set to one to enable linear learning. We train our model
using Decoupled Weight Decay Regularization [16] and Stochastic Gradient
Descent with Warm Restarts [17]. The inputs and outputs of each layer are
batch normalized and quantized using the Brevitas [18] quantized activation
functions, which employ learned scaling factors.

####  III-C2 Neuron to LUT conversion

After the model has been trained, the next step involves calculating the truth
tables for each neuron. This process entails generating all possible input
combinations based on their specified bit-width and fan-in, and then
tabulating the neuron function evaluated on these combinations to obtain the
corresponding outputs. As a result, each neuron requires the evaluation of
$2^{\beta\cdot F}$ input combinations to construct its truth table.

####  III-C3 RTL files generation

Each truth table is converted to Verilog RTL, by writing out the truth tables
as read-only memories (ROMs) that are converted to LUTs by the synthesis tool.
Additionally, each ROM is coded with registers at the output and the input
connections are specified using the activation masks.

##  IV Experimental Results

###  IV-A Datasets

To evaluate the efficacy of our method, we have analyzed three datasets that
are commonly used for the evaluation of ultra-low latency and size-critical
architectures. The first one is the UNSW-NB15 dataset [19], the second one is
the MNIST dataset [20] and the final one is the jet tagging dataset as
presented in [7], which has also been used for a case study.

####  IV-A1 Network intrusion detection

Ultra-low latency DNNs find application in cybersecurity, particularly in
network intrusion detection systems (NIDS). These systems are responsible for
monitoring network traffic and identifying and protecting against malicious
packets. Given that fiber-optic internet can achieve speeds of up to $940$
Mbps, it is essential to have NIDS solutions that can handle such high
throughput. However, privacy is also a significant concern in this context,
making on-chip FPGA design an ideal choice for implementation. To showcase the
effectiveness of our work in this domain, we have trained our models on the
UNSW-NB15 dataset, which has been randomly partitioned as described in [8].
This dataset is designed for the purpose of labeling network packets as either
safe ($0$) or malicious ($1$), based on $49$ input features.

####  IV-A2 Handwritten digit recognition

The advancements in autonomous driving, augmented reality, and edge
technologies have created a demand for real-time image classification. The
ability to perform low-latency inference opens up a wide range of applications
in this rapidly evolving field. To assess our work, we have chosen the MNIST
dataset, which aligns with the capabilities of our networks. The MNIST dataset
consists of handwritten digits represented as $28\times 28$ pixel images. The
input pixels are flattened, resulting in inputs of size $784$, while the $10$
output classes correspond to each digit.

####  IV-A3 Jet substructure classification

Real-time inference and efficient resource utilization have played a crucial
role in driving physics advancements at the CERN Large Hadron Collider (LHC).
Given the high collision frequencies at the LHC, the initial stage of data
processing demands exceptional throughput to effectively refine large volumes
of sensor data. Prior works [7, 13, 10, 11, 12] employed neural networks to
deploy inference models on FPGAs for the task of jet substructure analysis.
This particular task involves processing $16$ substructure properties to
classify $5$ types of jets. We showcase our work on this task as well, showing
that PolyLUT could be a solution for applications in high-energy physics.

###  IV-B Training and implementation setup

All the models are trained for $1000$ epochs for the smaller datasets, Jet
Substructure and UNSW-NB15, and for $500$ epochs for the MNIST dataset. We use
a mini-batch of $1024$ and $256$, respectively. Additionally, the models from
this paper were chosen to fit on a single FPGA device. To compile the Verilog
files generated by the PyTorch script we use Vivado 2020.1 and, to keep
consistency with LogicNets, we target the xcvu9p-flgb2104-2-i FPGA part. Also
for consistency, the projects are compiled using the Vivado
Flow_PerfOptimized_high settings, and the projects are configured to perform
synthesis in the Out-of-Context (OOC) mode. We target a clock period of $1.6$
ns for the smaller networks and $2$ ns for the largest ones. The accuracy of
the netlists is verified using the LogicNets’ pipeline since the hardware
architecture remains unchanged.

###  IV-C Case study

As a case study, we selected the jet substructure tagging task to investigate
the impact of the degree on training loss, test accuracy, latency, and area.
Our objective is to demonstrate that incorporating increased function
complexity through polynomial expansion improves training performance and
enables ultra-low latency FPGA implementations. By focusing on the jet
substructure tagging task, we are able to gain insights into the broader
implications and benefits of our methodology.

As our baseline, we adopted the JSC-M architecture from LogicNets, as outlined
in Table III. The JSC-M architecture comprises five layers with parameters
$\beta=3$ and $F=4$.

For our experimentation, we trained the JSC-M network using polynomial degrees
ranging from 1 to 6. Additionally, we systematically eliminated one hidden
layer at a time, generating a set of sub-networks that permitted the
evaluation of the same range of polynomial degrees. This approach allowed us
to analyze the effects of layer elimination on the performance metrics
mentioned above. Since each layer in the network can be processed within a
single clock cycle, we specifically considered networks that exhibit varying
inference speeds, ranging from $2$ to $5$ clock cycles. This ensured that we
examined the impact of different network configurations on both accuracy and
efficiency, taking into account the trade-off between inference speed and test
accuracy.

TABLE III: Model architectures used as benchmarks for evaluated datasets. Dataset | Model Name | Nodes per Layer | $\boldsymbol{\beta}$ | $F$ | Exceptions
---|---|---|---|---|---
Jet substructure | JSC-M | 64, 32, 32, 32, 5 | 3 | 4 |
Jet substructure | JSC-M Lite | 64, 32, 5 | 3 | 4 |
Jet substructure | JSC-XL | 128, 64, 64, 64, 5 | 5 | 3 |  $\beta_{0}=7$, $F_{0}=2$
UNSW-NB15 | NID Lite | 686, 147, 98, 49, 1 | 2 | 7 | $\beta_{0}=1$
MNIST | HDR | 256, 100, 100, 100, 100, 10 | 2 | 6 |

####  IV-C1 The impact of degree on training loss and test accuracy

$1.8$$2$$2.2$$2.4$$2.6$$2.8$$3$$3.2$$3.4$$3.6$$3.8$$4$$4.2$$4.4$$4.6$$4.8$$5$$5.2$$0.8$$0.85$Traditional
NetworkOur NetworksNumber of LayersTraining LossDegree123456

Figure 5:  Training loss variation with the number of layers across six
different polynomial degrees.

$-0.5$$0$$0.5$$1$$1.5$$2$$2.5$$3$$3.5$$4$$4.5$$5$$5.5$$70$$71$$72$Traditional
Network$\approx$ same accuracy with $<0.5\times$ layersOur NetworksNumber of
LayersTest Accuracy (%)Degree123456

Figure 6:  Test accuracy variation with the number of layers across six
different polynomial degrees.

Firstly, we analyze the effect of gradually increasing the degree on both
training loss and test accuracy. The results of this analysis can be
visualized in Figure 5 and Figure 6.

Observing the trends in training loss, it is evident that the curve
representing the points with $D=1$ is positioned above all the higher-degree
curves. This indicates that models with $D=1$ are less efficient in minimizing
loss compared to the other data points. We observe a consistent improvement as
the degree increases from $1$ to $2$. However, as the degree is further
increased, the improvements become less consistent, suggesting that very high
degrees may bring diminishing returns. This can be explained by the fact that
increasing the function complexity allows for better fitting of the data.
However, larger degrees tend to be more challenging to train.

Upon analyzing the test accuracy, we find that the same trends as observed in
the training loss apply. However, in this case, the separation between the
data points with higher degrees appears to be even more unpredictable,
suggesting that large degrees can result in overfitting the training data.

The most valuable observation from these graphs is that the performance boost
achieved through polynomial function training is equivalent to adding more
layers to a linear network. In this study, we observe that training a linear
$5$-layer network yields lower accuracy compared to training a $3$-layer
polynomial network, and the accuracy is nearly the same as that of a $2$-layer
polynomial network.

These findings highlight the effectiveness of multivariate polynomial function
training in improving network performance, allowing for comparable or even
better accuracy with fewer layers compared to linear networks. Thus, the
flexibility introduced by polynomial functions can compensate for training
very deep networks, resulting in more efficient models.

####  IV-C2 The impact of degree on latency and resource utilization

In the previous section, it was shown that PolyLUT networks allow reductions
in the number of layers for the same level of accuracy. Notably, each layer
reduction corresponds to a decrease in the inference speed by one clock cycle.

Figure 7 depicts the latency and test error rates of all data points from the
previous section. It is evident that the Pareto frontier of the polynomial
design points demonstrates greater efficiency in the trade-off between latency
and test error rate, surpassing the performance of the Pareto frontier of the
points with $D=1$. For the same test error rate, we record reductions in
latency ranging from $1.76\times$ to $2.29\times$.

If we were to calculate the theoretical cost using the LUTCost function used
in [5], it would yield the same result regardless of the polynomial degree.
However, in practice, some Boolean LUTs with $N$ inputs will naturally
synthesize to smaller circuits than others, when implemented within a network
of the native FPGA $K$-LUTs for $N>K$. This can be seen in Figure 7 which
illustrates the LUT count of all data points from the previous section
alongside their respective test error rates.

As the complexity increases with higher polynomial degrees slightly more
native $K$-LUTs are required for the same network topology. This is a direct
consequence of lookup tables now being utilized to express more meaningful
functions. However, the increase in LUT utilization due to increasing the
degree is well offset by the reduction in the number of layers, overall
leading to savings in the number of LUTs. Consequently, as shown in Figure 8,
the designs yielded through polynomial training reside on a more efficient
Pareto frontier compared to the one formed by the linear networks.

Comparing the performance of a $2$-layer network with $D=3$ (which achieves an
accuracy of $71.79\%$) to a $4$-layer network with $D=1$ (which achieves a
comparable accuracy of $71.78\%$), we observe a $2.29\times$ improvement in
latency and a $2.69\times$ improvement in resource utilization. This
demonstrates the advantages of implementing multivariate polynomial functions
inside the LUTs in terms of reducing both inference latency and resource
utilization.

$2$$3$$4$$5$$6$$7$$8$$9$$10$$11$$12$$28$$29$$30$$\mathbf{1.76\times}$$\mathbf{2.29\times}$$\mathbf{1.92\times}$Baseline
Pareto FrontierOur Pareto FrontierLatency (ns)Test Error Rate (%)Degree123456

Figure 7:  Analysis of the trade-off between test error rate and latency for
four models with varying numbers of layers across six different polynomial
degrees. Our improved Pareto frontier is depicted by (8).

$2$$3$$4$$5$$6$$7$$8$$9$$10$$11$$12$$28$$29$$30$$0$$0.2$$0.4$$0.6$$0.8$$1$$1.2$$1.4$$1.6$$1.8$$2$$2.2$$2.4$$2.6$$2.8$$28$$29$$30$$\cdot
10^{4}$$\mathbf{1.6\times}$$\mathbf{2.69\times}$$\mathbf{1.3\times}$Baseline
Pareto FrontierOur Pareto FrontierNumber of LUTsTest Error Rate
(%)Degree123456Degree123456

Figure 8:  Analysis of the trade-off between test error rate and resource
utilization for four models with varying numbers of layers across six
different polynomial degrees. Our improved Pareto frontier is depicted by (8).

###  IV-D Comparison with prior work

TABLE IV: Evaluation of PolyLUT on multiple datasets. Bold indicates best in class. |  | Accuracy | LUT | FF | DSP | BRAM |  $\text{F}_{\text{max}}$ (MHz) | Latency (ns)
---|---|---|---|---|---|---|---|---
| PolyLUT (NID Lite) | 92% | 3336 | 686 | 0 | 0 | 529 | 9
| LogicNets[5]a | 91% | 15949 | 1274 | 0 | 0 | 471 | 13
UNSW-NB15 | Murovic et al.[8] | 92% | 17990 | 0 | 0 | 0 | 55 | 18
| PolyLUT (HDR) | 96% | 70673 | 4681 | 0 | 0 | 378 | 16
| FINN[9] | 96% | 91131 | - | 0 | 5 | 200 | 310
MNIST | hls4ml[10] | 95% | 260092 | 165513 | 0 | 0 | 200 | 190
| PolyLUT (JSC-M Lite) | 72% | 12436 | 773 | 0 | 0 | 646 | 5
| PolyLUT (JSC-XL) | 75% | 236541 | 2775 | 0 | 0 | 235 | 21
| LogicNets[5]a | 72% | 37931 | 810 | 0 | 0 | 427 | 13
| Duarte et al.[7] | 75% | 88797b | 954 | 0 | 200 | 75
Jet substructure tagging | Fahim et al.[13] | 76% | 63251 | 4394 | 38 | 0 | 200 | 45
aNew results can be found on the LogicNets GitHub page.
bPaper reports “LUT+FF”.

####  IV-D1 Network intrusion detection

For the network intrusion task, we evaluate our work against LogicNets [5] and
Murovic et al. [8]. The results are summarized in Table IV.

For this task, we use the NID Lite architecture from Table III with a
polynomial degree set to $4$. PolyLUT achieves higher accuracy compared to
LogicNets and the same accuracy as Murovic et al. In terms of latency, PolyLUT
achieves a $1.44\times$ and a $2\times$ reduction compared to LogicNets and
Murovic et al., respectively. Additionally, PolyLUT improves the LUT count,
with a reduction of $4.78\times$ compared to LogicNets and $5.39\times$
compared to Murovic et al..

####  IV-D2 Handwritten digit recognition

To evaluate the performance of PolyLUT on the MNIST digit classification
dataset, we compare it against FINN’s SFC-max model [9] which is a fully
unfolded implementation, and against the ternary neural network (TNN) used in
hls4ml [10]. The results of the evaluation are shown in Table IV.

We use the HDR architecture from Table III for this task and train the network
with a polynomial degree of $4$. PolyLUT achieves higher accuracy compared to
hls4ml and the same accuracy as FINN. Notably, PolyLUT reaches a significant
latency reduction of $19.38\times$ against FINN and a latency reduction of
$11.88\times$ against hls4ml. Additionally, against FINN, PolyLUT has no block
random-access memory (BRAM) utilization, and it reduces the LUT utilization by
$1.28\times$. Against hls4ml, PolyLUT reduces the LUT utilization by
$3.68\times$.

We achieve high latency reductions without compromising accuracy through the
effective function complexity handling in our methodology and through the
minimization of exposed datapaths, which are susceptible to causing
bottlenecks.

####  IV-D3 Jet substructure tagging

To evaluate our method on the jet substructure tagging task, we conducted a
comparative analysis against three existing approaches: LogicNets [5], the
work presented by Duarte et al. [7], and the work presented by Fahim et al.
[13]. Our work demonstrates superior performance in terms of latency,
surpassing all previous approaches. This highlights the effectiveness of our
methodology in enabling applications that demand ultra-fast processing.

For our experiments, we utilized two architectures: JSC-M Lite and JSC-XL,
with polynomial degrees set to $6$ and $4$, respectively, as outlined in Table
III. Table IV provides a comprehensive comparison of our work.

In comparison to LogicNets, our JSC-M Lite architecture achieves the same
accuracy while reducing the LUT count by a factor of $3.05\times$ and the
latency by a factor of $2.6\times$. Compared to Duarte et al., our JSC-XL
architecture maintains comparable accuracy while achieving a latency reduction
of $3.57\times$. In comparison to Fahim et al., due to their higher precision
(fixed-point), our method exhibits a decrease in accuracy of $1$ percentage
point, however, we achieve an improvement in latency by a factor of
$2.14\times$.

In contrast to Duarte et al. and Fahim et al., our approach does not use DSP
blocks at all, however it can result in a large LUT count in specific cases
where both a high neuron fan-in and high precision is required to reach a
given accuracy. This situation can be seen in JSC-XL.

##  V Conclusion and Further Work

In this work, we introduced PolyLUT, a novel DNN-hardware co-design
methodology designed to meet the stringent demands of on-edge applications,
specifically in terms of ultra-low latency and minimal area requirements. We
proposed mapping sparse and quantized polynomial neural networks to netlists
of LUTs, by training multivariate polynomials instead of linear functions.
Thus, we leveraged the capabilities of a LUT to represent any function and we
maintained accuracy on shallower neural network models.

We have demonstrated the effectiveness of our approach on three different
datasets: network intrusion detection, handwritten digit classification, and
jet substructure tagging. Compared to prior works, for similar accuracies, our
method achieves significant latency improvements in these tasks, with
reductions of up to $2\times$, $19.38\times$, and $3.57\times$, respectively.

An evident extension of our work would be to incorporate neural architecture
search (NAS). NAS searches for optimal network architectures and performs
fine-tuning of various layer-specific parameters; those in Table III were
obtained by hand. These parameters could include the number of neurons, bit-
width, fan-in, and degree. This approach would enable the exploration of a
wider range of possibilities and it would potentially lead to the discovery of
architectures that offer improved performance and efficiency for specific
applications.

## References

  * [1] I. Goodfellow, Y. Bengio, and A. Courville, _Deep Learning_. MIT Press, 2016. [Online]. Available: https://www.deeplearningbook.org/
  * [2] M. M. H. Shuvo, S. K. Islam, J. Cheng, and B. I. Morshed, “Efficient Acceleration of Deep Learning Inference on Resource-Constrained Edge Devices: A Review,” _Proceedings of the IEEE_ , vol. 111, no. 1, pp. 42–91, Jan. 2023, doi: 10.1109/JPROC.2022.3226481.
  * [3] E. Wang _et al._ , “Deep Neural Network Approximation for Custom Hardware,” _ACM Computing Surveys_ , vol. 52, no. 2, pp. 1–39, May 2019, doi: 10.1145/3309551.
  * [4] E. Wang, J. J. Davis, P. Y. K. Cheung, and G. A. Constantinides, “LUTNet: Rethinking Inference in FPGA Soft Logic,” in _2019 IEEE 27th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM)_. San Diego, CA, USA: IEEE Computer Society, May 2019, pp. 26–34, doi: 10.1109/FCCM.2019.00014.
  * [5] Y. Umuroglu, Y. Akhauri, N. J. Fraser, and M. Blott, “LogicNets: Co-Designed Neural Networks and Circuits for Extreme-Throughput Applications,” in _2020 30th International Conference on Field-Programmable Logic and Applications (FPL)_. Gothenburg, Sweden: IEEE Computer Society, Sep. 2020, pp. 291–297, doi: 10.1109/FPL50879.2020.00055.
  * [6] M. Nazemi, G. Pasandi, and M. Pedram, “Energy-Efficient, Low-Latency Realization of Neural Networks through Boolean Logic Minimization,” in _Proceedings of the 24th Asia and South Pacific Design Automation Conference_. Tokyo, Japan: Association for Computing Machinery, Jan. 2019, p. 274–279, doi: 10.1145/3287624.3287722.
  * [7] J. Duarte _et al._ , “Fast inference of deep neural networks in FPGAs for particle physics,” _Journal of Instrumentation_ , vol. 13, no. 7, p. P07027, Jul. 2018, doi: 10.1088/1748-0221/13/07/P07027.
  * [8] T. Murovič and A. Trost, “Genetically optimized massively parallel binary neural networks for intrusion detection systems,” _Computer Communications_ , vol. 179, no. 7, pp. 1–10, Nov. 2021, doi: 10.1016/j.comcom.2021.07.015.
  * [9] Y. Umuroglu _et al._ , “FINN: A Framework for Fast, Scalable Binarized Neural Network Inference,” in _Proceedings of the 2017 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays_ , ser. FPGA ’17. Monterey, CA, USA: Association for Computing Machinery, Feb. 2017, p. 65–74, doi: 10.1145/3020078.3021744.
  * [10] J. Ngadiuba _et al._ , “Compressing deep neural networks on FPGAs to binary and ternary precision with hls4ml,” _Machine Learning: Science and Technology_ , vol. 2, no. 1, p. 015001, Dec. 2020, doi: 10.1088/2632-2153/aba042.
  * [11] S. Summers _et al._ , “Fast inference of Boosted Decision Trees in FPGAs for particle physics,” _Journal of Instrumentation_ , vol. 15, no. 5, p. P05026, May 2020, doi: 10.1088/1748-0221/15/05/P05026.
  * [12] C. N. Coelho, Jr. _et al._ , “Automatic heterogeneous quantization of deep neural networks for low-latency inference on the edge for particle detectors,” _Nature Machine Intelligence_ , vol. 3, no. 6, pp. 675–686, Jun. 2021, doi: 10.1038/s42256-021-00356-5.
  * [13] F. Fahim _et al._ , “hls4ml: An Open-Source Codesign Workflow to Empower Scientific Low-Power Machine Learning Devices,” in _TinyML Research Symposium’21_ , San Jose, CA, USA, Mar. 2021. [Online]. Available: https://doi.org/10.48550/arXiv.2103.05579
  * [14] A. Prabhu, G. Varma, and A. Namboodiri, “Deep Expander Networks: Efficient Deep Networks from Graph Theory,” in _Computer Vision - ECCV 2018_ , V. Ferrari, M. Hebert, C. Sminchisescu, and Y. Weiss, Eds. Munich, Germany: Springer International Publishing, Oct. 2018, pp. 20–36, doi: 10.1007/978-3-030-01261-8_2.
  * [15] S. M. Jayakumar, W. M. Czarnecki, J. Menick, J. Schwarz, J. Rae, S. Osindero, Y. W. Teh, T. Harley, and R. Pascanu, “Multiplicative Interactions and Where to Find Them,” in _8th International Conference on Learning Representations_ , Addis Ababa, Ethiopia, Apr. 2020. [Online]. Available: https://openreview.net/forum?id=rylnK6VtDH
  * [16] I. Loshchilov and F. Hutter, “Fixing Weight Decay Regularization in Adam,” in _7th International Conference on Learning Representations_ , New Orleans, LA, USA, May 2019. [Online]. Available: https://openreview.net/forum?id=Bkg6RiCqY7
  * [17] ——, “SGDR: Stochastic Gradient Descent with Warm Restarts,” in _5th International Conference on Learning Representations_ , Toulon, France, Apr. 2017. [Online]. Available: https://openreview.net/forum?id=Skq89Scxx
  * [18] A. Pappalardo, “Brevitas: neural network quantization in pytorch,” Jun. 2020, [Accessed: May 12, 2023]. [Online]. Available: https://github.com/Xilinx/brevitas
  * [19] N. Moustafa and J. Slay, “UNSW-NB15: a comprehensive data set for network intrusion detection systems (UNSW-NB15 network data set),” in _2015 Military Communications and Information Systems Conference (MilCIS)_. Canberra, ACT, Australia: IEEE, Nov. 2015, pp. 1–6, doi: 10.1109/MilCIS.2015.7348942.
  * [20] Y. LeCun, C. Cortes, and C. J. Burges, “THE MNIST DATABASE of handwritten digits.” [Online]. Available: http://yann.lecun.com/exdb/mnist/