# Reasoning over Description Logic-based Contexts with Transformers

Angelos Poulis Eleni Tsalapati Manolis Koubarakis
Dept. of Informatics and Telecommunications,
National and Kapodistrian University of Athens
{sdi1900230, etsalapati<EMAIL_ADDRESS>
###### Abstract

One way that the current state of the art measures the reasoning ability of
transformer-based models is by evaluating accuracy in downstream tasks like
logical question answering or proof generation over synthetic contexts
expressed in natural language. However, most of the contexts used are in
practice very simple; in most cases, they are generated from short first-order
logic sentences with only a few logical operators and quantifiers. In this
work, we seek to answer the question _how well a transformer-based model will
perform reasoning over expressive contexts_.

For this purpose, we construct a synthetic natural language question-answering
dataset, generated by description logic knowledge bases. For the generation of
the knowledge bases, we use the expressive language $\mathcal{ALCQ}$. The
resulting dataset contains 384K examples, and increases in two dimensions: i)
reasoning depth, and ii) length of sentences. We show that the performance of
our DeBERTa-based model, DELTAM, is marginally affected when the reasoning
depth is increased and it is not affected at all when the length of the
sentences is increasing. We also evaluate the generalization ability of the
model on reasoning depths unseen at training, both increasing and decreasing,
revealing interesting insights into the model’s adaptive generalization
abilities.

##  1 Introduction

Figure 1: An example from DELTAD where the context contains long sentences and
the true and false sentences are of depth 2. The sentence with the answer
“unknown” does not logically follow from the context. Logical quantifiers are
highlighted in bold and connectives in italic.

Ontological knowledge is usually represented with formalisms based on
description logic (DL) languages Baader et al. (2003). Description logics are
fragments of first-order logic that can be used in knowledge-based systems to
represent a domain of interest in a semantically well-defined manner. Their
formal apparatus allows us to perform reasoning tasks such as consistency
checking, deciding whether a sentence, or a set of sentences, logically
implies another, and answering queries over knowledge bases encoded in DL
languages. An expressive and decidable DL language that, besides the standard
Boolean operators, supports existential, universal, and numerical constraints
is $\mathcal{ALCQ}$. For instance, one can formally express in
$\mathcal{ALCQ}$ simple sentences like “ _Anne is a female_ ” or “ _Anne is a
female and a postdoc_ ” or complex sentences such as “ _If someone is a
postdoc then she has a Ph.D. degree, she teaches at most two courses and she
supervises at least one postgraduate student_ ”. As a result of its expressive
power, the complexity of reasoning in $\mathcal{ALCQ}$ is ExpTime-complete
Tobies (2000).

In this paper, we investigate the hypothesis that large language models (LLMs)
Devlin et al. (2019) could be used to carry out deductive reasoning tasks over
the DL language $\mathcal{ALCQ}$. If our hypothesis is correct then this
would: i) enable the users to perform deductive reasoning tasks (e.g., logical
question answering) over ontological knowledge bases using natural language
instead of logic language, and ii) possibly increase the time efficiency of
the reasoning process.

Recently, a substantial amount of research appeared in the literature
investigating the ability of LLMs to carry out various deductive reasoning
tasks, such as logical question answering Clark et al. (2020); Tian et al.
(2021); Han et al. (2022); Tang et al. (2023), proof generation Saha et al.
(2020); Tafjord et al. (2021) or satisfiability checking Richardson and
Sabharwal (2022), over _contexts_ expressed in natural language. These
contexts are generated from propositional logic or selected fragments of
first-order logic (FOL) expressed in natural language. To focus only on the
reasoning ability of the models, the datasets are generated in such a way that
commonsense knowledge that LLMs have already learned is isolated. A standard
way (Clark et al., 2020; Tafjord et al., 2021) to achieve this is by
performing random sampling over a probabilistic context-free grammar (PCFG).
The correct answers are determined by a logic reasoner and the reasoning
ability of the models is investigated with respect to the depth of the logical
proof.

In certain fragments of FOL, fined-tuned LLMs seem to have good performance,
but in more expressive ones the models do not perform equally well Tian et al.
(2021); Han et al. (2022). At the same time, generative models, such as
ChatGPT, seem to underperform over the same datasets Tang et al. (2023) (with
zero-shot, zero-shot with chain of thought, and few-shot with chain of
thought). The question that this work seeks to answer is _how well a fine-
tuned transformer-based model will perform reasoning over an expressive DL
language, like $\mathcal{ALCQ}$._ One question that arises here is if the
fragment of the formal language is enough to measure the reasoning ability of
a model. For instance, both synthetic sentences “ _Anne admires Bob_ ” and “
_If someone admires only people that are cold and not round or kind or that
love at least one not green person, then they love someone that is cold or
that loves someone kind_ ” can be expressed formally within $\mathcal{ALCQ}$.
Hence, the paper asks: If the context contains natural language sentences of
the latter form, i.e., of high _linguistic complexity_ , would the model
perform with high accuracy? It is important to note that most of the
benchmarks available in the literature are generated from short sentences
whose formal representation contains only a few logical operators and
quantifiers.

We have constructed the dataset DELTAD (DEscription Logics with TrAnsformers)
of 384K examples (context-question-answer-depth) based on $\mathcal{ALCQ}$,
where the question is the statement that we check whether it logically follows
from the context and answer is "True" (if it does), "False" (if it conflicts
with the context), "Unknown" (if none of the two). DELTAD increases in
complexity both in terms of reasoning and in terms of the size of the
sentences. An example of the dataset is presented in Figure 1.

We test the performance of our transformer-based model, DELTAM on two
dimensions: i) the minimum reasoning depth required to obtain the answer, and
ii) the complexity of the natural language sentences appearing in the context.
We show that the performance of DELTAM is marginally affected when the
reasoning depth increases and it is not affected at all when the length of the
sentences is increasing (accuracy 99.7% in max. reasoning depth and max.
length of sentence). Hence, DELTAM generalizes well with respect to these two
dimensions. It was recently shown Schlegel et al. (2022); Richardson and
Sabharwal (2022); Zhang et al. (2022); Tian et al. (2021); Saparov and He
(2022) that although transformer-based language models may perform well in
reasoning tasks, they cannot acquire the logical principles governing the
reasoning processes employed by standard logic reasoners. Inspired by Tian et
al. (2021), we tested how a DELTA model performs on datasets with low
reasoning depths when it is trained only on data of larger reasoning depths.
Differently from the BERT, RoBERTa, XLnet models used in Tian et al. (2021),
we show the DeBERTa-based model manages to generalize in both decreasing and
increasing reasoning depths when it is only trained on 3200 examples of
reasoning depth 3.

Overall, we make the following contributions:

  1. $C_{1}$.

We provide a large, balanced benchmark of 384K examples. Each example contains
the context, a question, an answer (true, false, unknown), and the minimum
reasoning depth required to obtain the answer. Additionally, the benchmark
contains the respective data in formal form (expressed in $\mathcal{ALCQ}$)
along with the minimum set of rules and facts involved in the proving process.
This is a significant contribution because: (i) this is the first dataset of
its kind for a DL, and (ii) building large benchmarks over expressive logic
languages, like $\mathcal{ALCQ}$, is a challenging task as it requires
performing query answering with logic reasoners, a process that can be very
time-consuming ($\sim$ 1 min. for KB with long rules/facts). Both the dataset
and the code for its generation will be openly available111Upon acceptance of
the paper to the conference of submission. to be used by other researchers.

  2. $C_{2}$.

We show that LLMs can perform logical entailment with very high accuracy over
synthetic natural language contexts generated from $\mathcal{ALCQ}$ sentences.
This demonstrates the potential of LLMs to be utilized for scalable reasoning
tasks over vast KBs, thus bypassing formal representations required by
traditional knowledge-based systems.

  3. $C_{3}$.

We show that the performance of LLMs, is not affected by the length of the
sentences.

  4. $C_{4}$.

This is the first work in the literature that studies the ability of
transformer-based models to perform reasoning tasks over expressive
description logic languages.

##  2 Background on Description Logics

We can use $\mathcal{ALCQ}$ to represent knowledge about a domain by defining
three types of entities: individuals (e.g., _John_), concepts (e.g., _Postdoc_
, i.e., the concept describing the entities that are postdocs) and roles
(e.g., _teaches_). _Concept expressions_ can be formed using these entities,
the Boolean constructors conjunction ($\sqcap$), disjunction ($\sqcup$),
negation ($\neg$), and universal ($\forall$), existential ($\exists$),
numerical ($\leq,\geq$) role restrictions. For instance, one can represent
formally all entities that “ _have a Ph.D., teach at most two postgraduate
courses and are not academics_ ” ($\exists\textit{has.PhD}\sqcap\leq
2\textit{teaches}.\textit{PostgrCourse}\sqcap\neg\textit{Academic}$). _Rules_
in $\mathcal{ALCQ}$ describe relationships between concept expressions. For
example, the fact that all postdocs are described by the aforementioned
concept expression can be represented with the concept inclusion
$\textit{Postdoc}\sqsubseteq\exists\textit{owns.PhD}\sqcap\leq
2\textit{teaches}.\textit{PostgrCourse}\sqcap\neg Academic$. _Facts_ describe
knowledge about named individuals, i.e., that are _instances_ of some concept
(expression), e.g., John is a Postdoc ($\textit{Postdoc}(\textit{John})$), or
how they related, e.g., John teaches Module05
($\textit{teaches}(\textit{John},\textit{Module05})$). An $\mathcal{ALCQ}$
_knowledge base_ (KB) is a set of rules and a set of facts.

The valid expressions in $\mathcal{ALCQ}$ are defined as follows. We start
with a finite set of individuals, atomic concepts, and roles. If $A$ is an
atomic concept and $R$ is a role, according to the $\mathcal{ALCQ}$ grammar
Baader et al. (2003), the concept expressions $C$, $D$ are constructed
recursively as follows: $C,D::=A\mid\top\mid\bot\mid\neg C\mid C\sqcap D\mid
C\sqcup D\mid\forall R.C\mid\mbox{ }\exists R.C\mid\geq nR.C\mid\leq nR.C$,
where the top concept $\top$ is a special concept with every individual as an
instance, and the bottom concept $\bot$ is the dual of $\top$, i.e., with no
individuals as instances. In $\mathcal{ALCQ}$ we can construct very complex
concept expressions such as $\exists R_{1}.(C\sqcup(\forall R_{2}.(D\sqcap\geq
nR_{3}.\neg F)))$. A rule is of the form $C\sqsubseteq D$ and a _fact_ of the
form $C(a)$ or $R(a,b)$, where $a$, $b$ individuals. Using complex expressions
one can construct very complex rules and facts. We denote with _LHS_ (left-
hand side) the concept expression that appears on the left of the subsumption
symbol ($\sqsubseteq$) in a rule and with _RHS_ (right-hand side) the concept
expression that appears on the right. The _inferred closure_ of a KB
$\mathcal{K}$ is the minimum set of rules and facts that can be logically
inferred from $\mathcal{K}$. Given a KB $\mathcal{K}$ and a rule or a fact
$a$, depth of $a$ with respect to $\mathcal{K}$ denotes the minimum number of
rules and facts in $\mathcal{K}$ that can be used to logically deduce that $a$
is true or false. Following the semantics of DLs, we make the _open-world
assumption_ , i.e., missing information is treated as unknown.

##  3 Dataset Generation

We investigate the ability of transformers to perform logical question
answering over $\mathcal{ALCQ}$ KBs expressed in natural language with respect
to two dimensions: i) the minimum depth of inference $\mathcal{D}$ a logic
reasoner would need to answer the corresponding query, ii) the linguistic
complexity level $\mathcal{L}$ of the knowledge required to answer the query.

Each _example_ in the dataset is a quadruple $\langle\mathcal{T}$,
$\mathcal{Q}$, $\mathcal{A}$, $\mathcal{D}\rangle$, where $\mathcal{T}$ is the
_context_ containing $\mathcal{ALCQ}$ axioms expressed in natural language,
$\mathcal{Q}$ a rule or fact expressed in natural language which forms the
_question_ , $\mathcal{A}$ is the _answer_ which can be either _true_ ,
_false_ , or _unknown_ , and $\mathcal{D}$ the minimum set of rules/facts to
answer $Q$. The natural language of the dataset is English.

Figure 2: Data generation pipeline for examples with $n$-level context and
answers of minimum inference depth $\leq m$

The pipeline for the generation of the dataset is presented in Figure 2. For
the generation of an example of linguistic complexity level $n$
($\mathcal{L}\leq n$) and depth $m$ ($\mathcal{D}\leq m$), we first generate a
small (with maximum 12 axioms and 14 facts) KB $\mathcal{K}$ using a specially
crafted PCFG (denoted in Figure 2 with $\mathcal{ALCQ}$-$n$ PCFG). Then, the
inferred closure of $\mathcal{K}$ is calculated by utilizing the reasoner
HermiT Horrocks et al. (2012), from which we calculate as described in Section
3.2, _true_ (answer=true), _false_ (answer=false) and _unknown_
(answer=unknown) queries. A KB $\mathcal{K}$ is kept only if it can produce
queries with all three types of answers at all depths up to $m$ (as unknown
queries do not have proofs, we denote the depth as “na”), otherwise, it is
discarded and a new one is generated. Once this process is completed, the
generated rules, facts along with the original KB $\mathcal{K}$, are
translated into natural language statements and into the context
$\mathcal{T}$, respectively, by utilizing a set of natural language templates.

Next, the generation of the dataset is described in brief, further details are
given in Appendix A.1.

###  3.1 KB Generation

To create diverse contexts and help the model not to overfit to a specific
vocabulary setting, we have defined two different pools of terms, _Pool A_ and
_Pool B_. From each pool, we generate 40 datasets (20 from each pool) of 1000
KBs each, of different inference depths and axiom lengths. Pool A contains
$14$ atomic concepts, $5$ roles, and $8$ individuals, all taken from the
RuleTaker dataset Clark et al. (2020) (in RuleTaker the rules are simple
conjunctive implications, where the concept names are named “attributes”, the
roles “relations” and the individual names “entities”). Pool B contains $8$
atomic concepts, $8$ roles, and $8$ individuals.

For each pool of terms, we generate four types of
$\mathcal{ALCQ}$-$\mathcal{L}$ KBs ($\mathcal{L}=0$, $1$, $2$, $3$), based on
the number of constructors and quantifiers appearing in their axioms. In
general, an $\mathcal{L}$ KB includes axioms that their LHS or RHS contains
$\mathcal{L}$ Boolean constructors and at most $\mathcal{L}+1$ quantifiers,
but also includes simpler axioms of smaller levels. For instance, KBs of level
$\mathcal{L}=0$ contain only very simple facts or axioms that do not contain
any Boolean constructors but can contain one quantifier, such as
$\textit{Enthusiastic}\sqsubseteq\exists\textit{supports}.\textit{Enthusiastic}$
(translated in NL as “Enthusiastic people support someone enthusiastic”), KBs
of level $\mathcal{L}=1$ contain axioms that their LHS or RHS can contain up
to a single Boolean constructor and up to two quantifiers, etc. To keep the
KBs processible by the reasoners, the axioms can contain up to seven atomic
concepts and up to two nested quantifiers (e.g.,
$\exists\textit{likes}.(\exists\textit{loves}.\textit{Cat}))$, which describes
the entities that like some entity that loves some cat). All KBs are checked
with respect to satisfiability and consistency with HermiT.

In line with Clark et al. (2020); Tafjord et al. (2021), each dataset contains
questions whose answers have a minimum depth of inference $\mathcal{D}$
($\mathcal{D}=0$, $1$, $2$, $3$, $5$).

###  3.2 Query Generation

For an inference depth $\mathcal{D}$, a _true query_ $q$ is an axiom or fact
selected from the inferred closure of a consistent $\mathcal{K}$, such that
$\textit{depth}(q,\mathcal{K})=\mathcal{D}$. An _unknown query_
(answer=unknown) is generated by creating a random fact or statement (using
the corresponding PCFG) such that it does not belong to the inferred closure
of $\mathcal{K}$ and is consistent with $\mathcal{K}$. A _false query_
(answer=false) can be generated in three ways:

  * •

From an inconsistent $\mathcal{K}$: for every $a\in\mathcal{K}$ if
$\mathcal{K}\setminus\\{a\\}$ is consistent then $a$ is a false query over the
KB $\mathcal{K}\setminus\\{a\\}$.

  * •

From a consistent $\mathcal{K}$: i) By negating a true query $q$ with
$\textit{depth}(q,\mathcal{K})=\mathcal{D}$ (and applying De Morgan’s laws).
ii) By automatically generating an appropriate axiom or fact $a$ such that
$\mathcal{K}\cup\\{a\\}$ is inconsistent and
$\textit{depth}(a,\mathcal{K})=\mathcal{D}$. For instance, suppose that a KB
$\mathcal{K}_{1}$ contains the axioms $(\forall\textit{admires}.\bot)(Anne)$
and
$\forall\textit{admires}.\bot\sqsubseteq\forall\textit{likes}.\textit{Quiet}$
which in natural language are translated into: “Anne admires none”, “All
people that admire none like only quiet people”. Then, the fact
$(\exists\textit{likes}.\neg\textit{Quiet})(\textit{Anne})$ stating that “Anne
likes someone who is not quiet” forms a false query for $\mathcal{K}$.

The disadvantage of the first approach is that it requires calling the
reasoner multiple times, a time-consuming process, especially in KBs with long
axioms (e.g., $\mathcal{L}$=3 KBs). Hence, we used the two latter approaches.

###  3.3 Data Translation to NL

The KBs and queries were translated to NL with the use of templates. The
templates were created based on the user-friendly Manchester syntax for
$\mathcal{ALCQ}$ Horridge et al. (2006). Following this syntax, the
intersection ($\sqcap$) and union ($\sqcup$) operators, are translated as
“and” and “or”, respectively, the existential ($\exists$) quantifier is
translated as “someone” or “something” (depending on whether the pool is about
people or things), the universal ($\forall$) as “only”, and the numerical
restrictions $\leq,\geq$ as “at most” and “at least”. Also, we use the word
“that” for intersections and nested quantifiers. For instance, the fact
$(\exists\textit{likes}.(\forall\textit{likes}.\textit{Kind}))(\textit{Bob})$
is translated as “Bob likes someone that likes only kind people”.

Following the template-based approach suggested by Tafjord et al. (2021), the
axioms of the form $C\sqsubseteq D$ are, roughly, translated into NL in four
different ways: i)“If $C$ then $D$”; ii)“People/Things that are $C$ are $D$”,
iii)“All people/things that are $C$ are $D$”; iv) If $C=\top$ and $D=\forall
R.C^{\prime}$ this is translated as “Someone/something can $R$ only
people/things that are $C^{\prime}$ ”. A fact $C(a)$ is translated as “$a$ is
$C$”. To ensure that the resulting NL sentences are grammatically correct we
have used a grammar checker222https://pypi.org/project/language-tool-python/.

###  3.4 The dataset DELTAD

After the generation and translation of all KBs and queries, examples of the
same depth and level from both pools are merged. This results in $20$ datasets
of $2000$ KBs each, with each resulting dataset containing sentences from both
vocabularies. From each KB we generated three queries (true, false, unknown)
for each depth ($\mathcal{D}=\\{0,1,2,3,5\\}$), i.e., from each KB we
generated $3\times(d+1)$, $d\in\mathcal{D}$. So, in total, the dataset
contains $\Sigma_{d\in\mathcal{D}}3\times(d+1)\times
2000\times(\mathcal{L}_{max}+1)$, where $\mathcal{L}_{max}=3$ is the highest
linguistic complexity level.

###  3.5 Statistical Features

As it is thoroughly discussed by Zhang et al. (2022), it is impossible to
eliminate all statistical features that exist in data, besides, some of them
inherently exist in logical reasoning problems (e.g., due to monotonicity, it
is more likely that large KBs will produce positive examples).

DELTAD is balanced with respect to the following features: i) _KB size_ : From
the same KB we extract all three types of questions (true, false, unknown);
ii) _Inference depth_ : We keep a KB only if it can provide all three types of
questions with the same inference depth; iii) _Formulation of the question_ :
The translation to natural language is implemented in such a way that the word
“not” appears almost equal number of times in true questions (52.39%), false
questions (50.71%) and unknown questions (46.60%); iv) _Average length in
words_ : True questions 10.85, false questions 8.97, unknown questions 10.34.

##  4 Experiments

##### Model Selected for Evaluation

For all our experiments we use DeBERTaV3-large He et al. (2023a). While
RoBERTa-large has been recognized as the most effective among the models
tested on deductive reasoning tasks involving logical rules in several studies
Clark et al. (2020); Tian et al. (2021), we chose the DeBERTaV3-large due to
its recent advancements in NLU tasks He et al. (2023a).

##### Evaluation Setup

We fine-tune the DeBERTaV3-large to predict true/false/unknown (i.e., multi-
class sentence classification) for each example. A context-question pair is
supplied to the model as [CLS] context [SEP] question [SEP]. For evaluation,
we measure accuracy. The test data has an equal balance of true/false/unknown
answers, hence the baseline of random guessing is $33.3\%$. For our training,
we used the AdamW optimizer Loshchilov and Hutter (2019) using its default
values for betas and a weight decay setting of $1e^{-4}$. The specifics of the
chosen hyper-parameters, which we maintained consistently throughout our
experiments, can be found in Appendix A.2.

We take subsets of DELTAD as they were formed during the generation process to
train the models in the following way: For each combination of depth $d$ and
level $l$ (20 combinations in total), we train a different model on subsets of
DELTAD with $\mathcal{D}\leq d$, and $\mathcal{L}\leq l$. The final model
DELTAM has been trained to all depths and all linguistic complexity levels.
The intermediate models are denoted with DELTAi,j, where $i$ represents the
reasoning depth and $j$ is the linguistic complexity level. For instance, the
model DELTA3,2 has been trained to depths up to $3$ and to linguistic
complexity levels up to $2$. DELTAM=DELTA5,3. For all datasets, we partitioned
the data into 70%/10%/20% splits for train/validation/test sets.

| DELTA0,3 | DELTA1,3 | DELTA2,3 | DELTA3,3 | DELTA5,3
---|---|---|---|---|---
Test (own) |  100.0 |  99.8 |  99.8 |  99.6 |  99.7
D5,3 |  61.2 |  90.5 |  95.2 |  99.3 |  99.8
$\mathcal{D}$ = N/A |  100.0 |  99.4 |  99.5 |  99.2 |  99.7
$\mathcal{D}=0$ |  100.0 |  100.0 |  100.0 |  100.0 |  100.0
$\mathcal{D}=1$ |  43.4 |  100.0 |  100.0 |  100.0 |  100.0
$\mathcal{D}=2$ |  24.5 |  73.1 |  99.5 |  100.0 |  100.0
$\mathcal{D}=3$ |  34.1 |  71.3 |  99.5 |  100.0 |  100.0
$\mathcal{D}=4$ |  29.2 |  77.6 |  84.5 |  99.5 |  100.0
$\mathcal{D}=5$ |  19.3 |  76.5 |  83.5 |  98.5 |  99.5

Table 1: Accuracy of DELTA models on Test (own), on D5,3 dataset, and on
slices of D5,3 per depth.

| $\mathcal{D}=0$ | $\mathcal{D}\leq 1$ | $\mathcal{D}\leq 2$ | $\mathcal{D}\leq 3$ | $\mathcal{D}\leq 5$
---|---|---|---|---|---
$\mathcal{L}=0$ |  100.0 |  99.7 |  99.4 |  98.9 |  98.9
$\mathcal{L}\leq 1$ |  100.0 |  99.7 |  99.6 |  99.7 |  99.5
$\mathcal{L}\leq 2$ |  99.9 |  99.5 |  99.7 |  99.7 |  99.6
$\mathcal{L}\leq 3$ |  100.0 |  99.8 |  99.8 |  99.6 |  99.7

Table 2: Accuracy of DELTA models on Test (own) across all levels.

| $\mathcal{D}=0$ | $\mathcal{D}\leq 1$ | $\mathcal{D}\leq 2$ | $\mathcal{D}\leq 3$ | $\mathcal{D}\leq 5$
---|---|---|---|---|---
$\mathcal{L}=0$ |  61.4 |  75.3 |  93.2 |  97.7 |  98.8
$\mathcal{L}\leq 1$ |  67.9 |  92.4 |  85.8 |  98.7 |  99.6
$\mathcal{L}\leq 2$ |  55.1 |  89.7 |  85.3 |  99.1 |  99.7
$\mathcal{L}\leq 3$ |  61.2 |  90.5 |  95.2 |  99.3 |  99.8

Table 3: Accuracy of DELTA models on the whole D5,l for $l\in\\{0,1,2,3\\}$

Table 1 illustrates the performance of DELTA models when trained on up to
$\mathcal{L}\leq 3$ linguistic complexity over the various inference depths
(the sets of results for $\mathcal{L}=0$, $\mathcal{L}\leq 1$,
$\mathcal{L}\leq 2$ are presented in Appendix A.3). For instance, the column
DELTA0,3 shows the performance of the model trained on all levels in depth 0.
Test (own) represents the (held out) test set of the dataset that the model
has been trained on. The D5,3 dataset has questions from all inference depths
($\mathcal{D}\leq 5$) of all levels ($\mathcal{L}\leq 3$). “Depth N/A” refers
to the unknown questions, as these are not provable. “$\mathcal{D}=0$” to
“$\mathcal{D}=5$” lines represent subsets of D5,3 of 0-reasoning depth to
5-reasoning depth, respectively. For instance, $\mathcal{D}=3$ denotes that
this subset of D5,3 only contains questions of depth 3.

DELTA models have in general high accuracies but those decrease (slightly) as
the reasoning depths increase. They show improved but plateaued generalization
on D5,3, up to $\mathcal{D}\leq 5$. As the training progresses, we observe
that the model masters (100%) answering questions of lower depths, while it
also improves its score on higher reasoning depths. It is quite interesting
that the model although masters answering questions of predefined depths,
doesn’t do so on unknown questions ($\mathcal{D}$ = N/A) except for the model
DELTA0,3.

Table 2 demonstrates the performance of each DELTA model DELTAi,j (the
intermediates and the final one) when tested on Test (own). For instance, the
cell that corresponds to $\mathcal{D}=0$, $\mathcal{L}=0$ shows the accuracy
of the model DELTA0,0. We observe that for all depths $\mathcal{D}=0$ to
$\mathcal{D}\leq 5$ the models are robust across levels, hence increasing
lengths do not affect their performance.

Table 3 presents the performance of intermediate models DELTAi,j on datasets
with a reasoning depth of $\mathcal{D}\leq 5$ and various levels
$\mathcal{L}=j,j\in\\{0,1,2,3\\}$. For example, the accuracy of the DELTA0,0
model in the cell corresponding to $\mathcal{D}=0$ and $\mathcal{L}=0$
reflects its performance on level $0$ data within this depth range. This table
effectively tracks the model’s progression during training, highlighting a
general trend of monotonic performance improvement. Notable exceptions occur
at depths $\mathcal{D}\leq 2$ for lengths $\mathcal{L}\leq 2$, where the model
initially encounters longer data sequences. In these instances, insufficient
training data leads to minor performance fluctuations.

| D0 | D1 | D2 | D3 | D4 | D5
---|---|---|---|---|---|---
DELTA${}^{\prime}_{3,3}$ |  99.0 |  93.8 |  94.8 |  97.5 |  98.0 |  97.5

Table 4: The performance of a model trained on questions of only depth 3,
evaluated on other depths.

##### Zero-shot performance on smaller depths.

We partitioned the dataset to the various depths, i.e., we extracted from
DELTAD datasets $D_{i}$, which contain only data of depth $\mathcal{D}=i$ (of
all levels) and not up to $i$. Additionally, we trained the
DELTA${}^{\prime}_{3,3}$ model on a set of 3200 examples specifically at depth
3 ($\mathcal{D}=3$) for all lengths ($\mathcal{L}\leq 3$). The outcomes of
this approach are detailed in Table 4. Notably, our results demonstrate the
model’s capacity for generalization across both lesser and greater reasoning
depths than those encountered during training.

##  5 Related Work

A survey of the most recent research on the use of transformers for reasoning
tasks can be found in Yang et al. (2023). One of the first studies in the
domain was from Clark et al. (2020) with RuleTaker, where it was demonstrated
the potential of transformers to perform logical question answering under CWA
by training LLMs on synthetic datasets. However, their approach was limited to
short expressions of simple conjunctive rules. Han et al. (2022), with the
FOLIO dataset (1.4K), in the same line with RuleTaker, tested the ability of
various LLMs for the same reasoning task under OWA. FOLIO was in FOL but
without numerical restrictions. The result was that RoBERTa performed better
than all models, but still the performance was low. Tafjord et al. (2021),
with the model ProofWriter built on top of T5 transformer Raffel et al. (2020)
and the (modified) datasets from RuleTaker showed that LLMs can generate
proofs (94.8% accuracy for depth 5). Ontañón et al. (2022) showed that LLMs
perform well (up to 90.5%) over context generated by propositional logic and a
small subset of FOL. Tian et al. (2021) introduced the much richer synthetic
dataset LogicNLI (30K), under OWA for diagnosing LLMs behavior. They showed
even the best-performing model on LogicNLI, RoBERTa, does not learn to reason
and cannot generalize to different scenarios. Schlegel et al. (2022) generated
a very simple dataset (containing a single conjunction) for satisfiability
checking and showed that models that perform well on hard problems do not
perform equally well on easier ones, resulting in the conclusion that
transformers cannot learn the underlying reasoning rules rather than they tend
to overfit to patterns in the generated data. Also, Zhang et al. (2022), Tian
et al. (2021) achieved similar results. Saparov and He (2022) showed that LLMs
are good at producing valid individual steps but are struggling when there is
more than one path in the proving process. Most of the aforementioned
benchmarks though are composed of short sentences. The ones that contain
longer sentences (avg. 13 words/sentence) are small ($\leq$ 40K), while none
of them have examples with numerical restrictions. In Table 5 we present the
metrics of the datasets that are most relevant to DELTAD.

Bang et al. (2023) studied ChatGPT’s Liu et al. (2023) deductive reasoning
ability on bAbi task 16 Weston et al. (2016) and EntailmentBank Dalvi et al.
(2021), performing merely well. In addition, Tang et al. (2023) showed that
LLMs perform significantly better when using natural language text instead of
symbolic representations of logical facts and rules. Finally, He et al.
(2023b) tested the ability of LLMs, and specifically of RoBERTa (roberta-
large, roberta-base), to perform logical entailment over existing OWL
ontologies (e.g., FoodOn, Shema.org). They showed, that roberta-large can
reach high performance ($\sim 92\%$) with only few shots (128). However, in
our work, we make a more systematic analysis of the ability of the more recent
model DeBERTaV3 to perform logical entailments, as we check its ability both
in regard to the length of the sentences and the depth of reasoning.
Additionally, differently from He et al. (2023b) we do not consider only rules
but also facts.

| #Questions |  | Avg size of
---
sentences
| Max size of
---
sentences
Formal Language |  | Generating
---
method
bAbI Task15 Weston et al. (2016) | 2K | 4.6 | 5 |  | Role
---
assertions
Synthetic
RuleTaker Clark et al. (2020) | 520K | 6.13 | 27 |  | Conjunctive
---
Rules
Synthetic
ProofWriter Tafjord et al. (2021) | 500K | 6.07 | 27 |  | Conjunctive
---
Rules
Synthetic
BirdsElectricity Tafjord et al. (2021) | 5K | 12.85 | 22 |  | Conjunctive
---
Rules
Synthetic
ParaRulesC/O Tafjord et al. (2021) | 40K | 11.85/11.78 | 37/37 |  | Conjunctive
---
Rules
| Synthetic &
---
Manual
FOLIO Han et al. (2022) | 1.4K | 10.58 | 59 |  | FOL$\setminus$
---
Num. Restrictions
| Synthetic &
---
Manual
PrOntoQA Saparov and He (2022) | 5.8K | 6.2 | 20 |  | FOL$\setminus$
---
Num. Restrictions
Synthetic
LogicNLI Tian et al. (2021) | 30K | 8.72 | 25 |  | FOL$\setminus$
---
Num. Restrictions
Synthetic
| DELTAD
---
($\mathcal{L}_{0}$/ $\mathcal{L}_{1}$/ $\mathcal{L}_{2}$/ $\mathcal{L}_{3}$)
| 96K each,
---
384K (in total)
6.28/9.71/13.08/13.08 | 26/38/50/62 | $\mathcal{ALCQ}$ | Synthetic

Table 5: The state-of-the-art benchmarks for deductive reasoning with
transformers. The size of the sentences is calculated by the number of words
appearing in the sentences of the contexts. To calculate the expressivity of
each dataset we calculate the average number of Boolean operators and
quantifiers per sentence. The ProofWriter, Para-Rules, and BirdsElectricity
datasets are available in both closed-world and open-world versions. However,
both versions of ProofWriter and BirdsElectricity datasets had the same
metrics, while the Para-RulesC and Para-RulesO differed only in the average
size of sentences (11.85/11.78).

##  6 Summary and Future Work

We generated the only large, balanced, synthetic dataset (384K) in the
literature that targets expressive DLs (namely, $\mathcal{ALCQ}$), enjoys both
high expressivity and high linguistic complexity, and is publicly available
for further understanding of the functionality of LLMs. We showed that our
DeBERTa-based model, DELTAM, can carry out reasoning over expressive synthetic
datasets with very high accuracy regardless of the linguistic complexity of
the context. Differently from recent results in the literature, we showed that
our model has learned to generalize on unseen reasoning depths both lesser and
greater than those that it has seen during training.

In future work, we will expand our evaluation section with state-of-the-art
generative models such as Llama2 Touvron et al. (2023) and GPT-4 OpenAI
(2023). Furthermore, we plan to explore the upper limit of the expressivity of
the logic language so that a transformer-based model will be able to perform
reasoning tasks with high accuracy.

## Limitations

As one of the main goals of our research was to build the first DL-based
dataset which would be big (384K examples), balanced, and expressive, we
initially focused our evaluation on encoder-only models, such as DeBERTa. We
plan to expand our work as stated in the Future Work section.

Finally, as the focus of this study was to investigate if LLMs can perform
reasoning over contexts generated from $\mathcal{ALCQ}$ languages, we used
only datasets that were synthetic, hence non-sensical. Given the world
knowledge on which LLMs are already trained, we assume the performance over
real-world scenarios (that can be expressed formally in $\mathcal{ALCQ}$)
would be better.

## Ethics Statement

The literature contains many discussions about the possibilities of using LLMs
in unethical and even harmful ways. The same concerns apply to the work
presented in this paper since one can use languages like $\mathcal{ALCQ}$ to
construct knowledge bases that are biased, unethical, or even harmful.

## References

  * Baader et al. (2003) Franz Baader, Diego Calvanese, Deborah L. McGuinness, Daniele Nardi, and Peter F. Patel-Schneider, editors. 2003.  _The Description Logic Handbook: Theory, Implementation, and Applications_.  Cambridge University Press.
  * Bang et al. (2023) Yejin Bang, Samuel Cahyawijaya, Nayeon Lee, Wenliang Dai, Dan Su, Bryan Wilie, Holy Lovenia, Ziwei Ji, Tiezheng Yu, Willy Chung, Quyet V. Do, Yan Xu, and Pascale Fung. 2023.  A multitask, multilingual, multimodal evaluation of chatgpt on reasoning, hallucination, and interactivity.
  * Clark et al. (2020) Peter Clark, Oyvind Tafjord, and Kyle Richardson. 2020.  Transformers as soft reasoners over language.  In _Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020_ , pages 3882–3890. ijcai.org.
  * Dalvi et al. (2021) Bhavana Dalvi, Peter Alexander Jansen, Oyvind Tafjord, Zhengnan Xie, Hannah Smith, Leighanna Pipatanangkura, and Peter Clark. 2021.  Explaining answers with entailment trees.  In _Conference on Empirical Methods in Natural Language Processing_.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4171–4186, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Gugger et al. (2022) Sylvain Gugger, Lysandre Debut, Thomas Wolf, Philipp Schmid, Zachary Mueller, and Sourab Mangrulkar. 2022.  Accelerate: Training and inference at scale made simple, efficient and adaptable.  https://github.com/huggingface/accelerate.
  * Han et al. (2022) Simeng Han, Hailey Schoelkopf, Yilun Zhao, Zhenting Qi, Martin Riddell, Luke Benson, Lucy Sun, Ekaterina Zubova, Yujie Qiao, Matthew Burtell, David Peng, Jonathan Fan, Yixin Liu, Brian Wong, Malcolm Sailor, Ansong Ni, Linyong Nan, Jungo Kasai, Tao Yu, Rui Zhang, Shafiq Joty, Alexander R. Fabbri, Wojciech Kryscinski, Xi Victoria Lin, Caiming Xiong, and Dragomir Radev. 2022.  Folio: Natural language reasoning with first-order logic.
  * He et al. (2023a) Pengcheng He, Jianfeng Gao, and Weizhu Chen. 2023a.  Debertav3: Improving deberta using electra-style pre-training with gradient-disentangled embedding sharing.
  * He et al. (2023b) Yuan He, Jiaoyan Chen, Ernesto Jimenez-Ruiz, Hang Dong, and Ian Horrocks. 2023b.  Language model analysis for ontology subsumption inference.  In _Findings of the Association for Computational Linguistics: ACL 2023_ , pages 3439–3453, Toronto, Canada. Association for Computational Linguistics.
  * Horridge et al. (2006) Matthew Horridge, Nick Drummond, John Goodwin, Alan L. Rector, Robert Stevens, and Hai Wang. 2006.  The manchester OWL syntax.  In _Proceedings of the OWLED*06 Workshop on OWL: Experiences and Directions, Athens, Georgia, USA, November 10-11, 2006_ , volume 216 of _CEUR Workshop Proceedings_. CEUR-WS.org.
  * Horridge et al. (2008) Matthew Horridge, Bijan Parsia, and Ulrike Sattler. 2008.  Laconic and precise justifications in OWL.  In _The Semantic Web - ISWC 2008, 7th International Semantic Web Conference, ISWC 2008, Karlsruhe, Germany, October 26-30, 2008. Proceedings_ , volume 5318 of _Lecture Notes in Computer Science_ , pages 323–338. Springer.
  * Horrocks et al. (2012) Ian Horrocks, Boris Motik, and Zhe Wang. 2012.  The hermit OWL reasoner.  In _Proceedings of the 1st International Workshop on OWL Reasoner Evaluation (ORE-2012), Manchester, UK, July 1st, 2012_ , volume 858 of _CEUR Workshop Proceedings_. CEUR-WS.org.
  * Liu et al. (2023) Yiheng Liu, Tianle Han, Siyuan Ma, Jiayue Zhang, Yuanyuan Yang, Jiaming Tian, Hao He, Antong Li, Mengshen He, Zhengliang Liu, Zihao Wu, Lin Zhao, Dajiang Zhu, Xiang Li, Ning Qiang, Dingang Shen, Tianming Liu, and Bao Ge. 2023.  Summary of ChatGPT-related research and perspective towards the future of large language models.  _Meta-Radiology_ , 1(2):100017.
  * Loshchilov and Hutter (2019) Ilya Loshchilov and Frank Hutter. 2019.  Decoupled weight decay regularization.
  * Ontañón et al. (2022) Santiago Ontañón, Joshua Ainslie, Vaclav Cvicek, and Zachary Fisher. 2022.  Logicinference: A new dataset for teaching logical inference to seq2seq models.  _CoRR_ , abs/2203.15099.
  * OpenAI (2023) OpenAI. 2023.  Gpt-4 technical report.
  * Raffel et al. (2020) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. 2020.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _J. Mach. Learn. Res._ , 21:140:1–140:67.
  * Richardson and Sabharwal (2022) Kyle Richardson and Ashish Sabharwal. 2022.  Pushing the limits of rule reasoning in transformers through natural language satisfiability.  In _Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI 2022, Thirty-Fourth Conference on Innovative Applications of Artificial Intelligence, IAAI 2022, The Twelveth Symposium on Educational Advances in Artificial Intelligence, EAAI 2022 Virtual Event, February 22 - March 1, 2022_ , pages 11209–11219. AAAI Press.
  * Saha et al. (2020) Swarnadeep Saha, Sayan Ghosh, Shashank Srivastava, and Mohit Bansal. 2020.  PRover: Proof generation for interpretable reasoning over rules.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 122–136, Online. Association for Computational Linguistics.
  * Saparov and He (2022) Abulhair Saparov and He He. 2022.  Language models are greedy reasoners: A systematic formal analysis of chain-of-thought.  _CoRR_ , abs/2210.01240.
  * Schlegel et al. (2022) Viktor Schlegel, Kamen V. Pavlov, and Ian Pratt-Hartmann. 2022.  Can transformers reason in fragments of natural language? In _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, EMNLP 2022, Abu Dhabi, United Arab Emirates, December 7-11, 2022_ , pages 11184–11199. Association for Computational Linguistics.
  * Tafjord et al. (2021) Oyvind Tafjord, Bhavana Dalvi, and Peter Clark. 2021.  Proofwriter: Generating implications, proofs, and abductive statements over natural language.  In _Findings of the Association for Computational Linguistics: ACL/IJCNLP 2021, Online Event, August 1-6, 2021_ , volume ACL/IJCNLP 2021 of _Findings of ACL_ , pages 3621–3634. Association for Computational Linguistics.
  * Tang et al. (2023) Xiaojuan Tang, Zilong Zheng, Jiaqi Li, Fanxu Meng, Song-Chun Zhu, Yitao Liang, and Muhan Zhang. 2023.  Large language models are in-context semantic reasoners rather than symbolic reasoners.
  * Tian et al. (2021) Jidong Tian, Yitian Li, Wenqing Chen, Liqiang Xiao, Hao He, and Yaohui Jin. 2021.  Diagnosing the first-order logical reasoning ability through logicnli.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, EMNLP 2021, Virtual Event / Punta Cana, Dominican Republic, 7-11 November, 2021_ , pages 3738–3747. Association for Computational Linguistics.
  * Tobies (2000) Stephan Tobies. 2000.  The complexity of reasoning with cardinality restrictions and nominals in expressive description logics.  _J. Artif. Intell. Res._ , 12:199–217.
  * Touvron et al. (2023) Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Dan Bikel, Lukas Blecher, Cristian Canton Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller, Cynthia Gao, Vedanuj Goswami, Naman Goyal, Anthony Hartshorn, Saghar Hosseini, Rui Hou, Hakan Inan, Marcin Kardas, Viktor Kerkez, Madian Khabsa, Isabel Kloumann, Artem Korenev, Punit Singh Koura, Marie-Anne Lachaux, Thibaut Lavril, Jenya Lee, Diana Liskovich, Yinghai Lu, Yuning Mao, Xavier Martinet, Todor Mihaylov, Pushkar Mishra, Igor Molybog, Yixin Nie, Andrew Poulton, Jeremy Reizenstein, Rashi Rungta, Kalyan Saladi, Alan Schelten, Ruan Silva, Eric Michael Smith, Ranjan Subramanian, Xiaoqing Ellen Tan, Binh Tang, Ross Taylor, Adina Williams, Jian Xiang Kuan, Puxin Xu, Zheng Yan, Iliyan Zarov, Yuchen Zhang, Angela Fan, Melanie Kambadur, Sharan Narang, Aurelien Rodriguez, Robert Stojnic, Sergey Edunov, and Thomas Scialom. 2023.  Llama 2: Open foundation and fine-tuned chat models.
  * 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_.
  * Wolf et al. (2020) Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander M. Rush. 2020.  Transformers: State-of-the-art natural language processing.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_ , pages 38–45, Online. Association for Computational Linguistics.
  * Yang et al. (2023) Zonglin Yang, Xinya Du, Rui Mao, Jinjie Ni, and Erik Cambria. 2023.  Logical reasoning over natural language as knowledge representation: A survey.  _CoRR_ , abs/2303.12023.
  * Zhang et al. (2022) Honghua Zhang, Liunian Harold Li, Tao Meng, Kai-Wei Chang, and Guy Van den Broeck. 2022.  On the paradox of learning to reason from data.  _CoRR_ , abs/2205.11502.

##  Appendix A Appendix

###  A.1 Dataset Generation

The dataset generation is based on the probabilistic context-free grammars
which are described below.

To ensure that we will produce datasets with inference depth $\mathcal{D}>0$,
i.e., datasets resulted from some inferencing, we generated a new statement
$C\sqsubseteq D$, if $C$ either appeared in some already generated fact or in
the RHS of some already generated statement.

####  A.1.1 Probabilistic Context-Free Grammars

We have created two pools of terms.

##### Pool A

  * •

Atomic Concepts: “red”, “blue”, “green”, “kind”, “nice”, “big”, “cold”,
“young”, “round”, “rough”, “orange”, “smart”, “quiet”, “furry”.

  * •

Role Names: “likes”, “loves”, “eats”, “chases”, “admires”.

  * •

Individual Names: “Anne”, “Bob”, “Charlie”, “Dave”, “Erin”, “Fiona”, “Gary”,
“Harry”.

##### Pool B

  * •

Atomic Concepts: “ambitious”, “confident”, “creative”, “determined”,
“enthusiastic”, “innovative”, “logical”, “persevering”.

  * •

Role Names: “admires”, “consults”, “guides”, “instructs”, “leads”, “mentors”,
“supervises”, “supports”.

  * •

Individual Names: “Ioanna”, “Dimitrios”, “Eleni”, “Maria”, “Manolis”,
“Angelos”, “Panos”, “Anna”.

To generate the KBs, we employ a random sampling technique to select a subset
of individuals, roles, and atomic Concepts from the aforementioned pools. An
item from each pool has the same probability of being chosen.

The probabilistic context-free grammar for the linguistic complexity level
$\mathcal{L}=0$ is shown in Table 10, the rest can be found in the link we
provide. The PCFG shown is for Pool B. The grammars for the Pool A are
similar. The probabilities in the PCFGs were determined experimentally with
the goal of generating appropriate KBs that would yield the desired inferences
in the minimum amount of time.

The level of linguistic complexity $\mathcal{L}$ of a concept is defined as
follows:

  * •

Level0: 0 connectives (i.e., Boolean operators) and $\leq$ 1 quantifiers

  * •

Level1: 1 connectives and $\leq$ 2 quantifiers

  * •

Level2: 2 connectives and $\leq$ 3 quantifiers

  * •

Level3: 3 connectives and $\leq$ 4 quantifiers

Specifically, (as it shown in Table 10 for the $\mathcal{L}=0$ PCFG) the rules
of KBs of each complexity level $\mathcal{L}$ are defined as follows:

  * •

If KB is of level $\mathcal{L}=0$ : $Level_{0}\sqsubseteq Level_{0}$

  * •

If KB is of level $\mathcal{L}=1$ : $Level_{0}\sqsubseteq Level_{1}$,
$Level_{1}\sqsubseteq Level_{0}$, $Level_{1}\sqsubseteq Level_{1}$

  * •

If KB is of level $\mathcal{L}=2$ : $Level_{0}\sqsubseteq Level_{2}$,
$Level_{2}\sqsubseteq Level_{0}$, $Level_{1}\sqsubseteq Level_{2}$,
$Level_{2}\sqsubseteq Level_{1}$

  * •

If KB is of level $\mathcal{L}=3$ : $Level_{0}\sqsubseteq Level_{3}$,
$Level_{1}\sqsubseteq Level_{3}$, $Level_{2}\sqsubseteq Level_{3}$,
$Level_{3}\sqsubseteq Level_{0}$, $Level_{3}\sqsubseteq Level_{1}$,
$Level_{3}\sqsubseteq Level_{2}$

####  A.1.2 KB sizes

We utilize randomized parameters to control the size of KB based on the target
reasoning depth of the corresponding dataset. The optimal predefined ranges of
the rules and facts per reasoning depth $\mathcal{D}$ are as follows:

  * •

For $\mathcal{D}=0$: $|\textit{rules}|\in[3,8]$, $|\textit{facts}|\in[1,5]$

  * •

For $\mathcal{D}=1$: $|\textit{rules}|\in[3,8]$, $|\textit{facts}|\in[2,6]$

  * •

For $\mathcal{D}=2$: $|\textit{rules}|\in[3,8]$, $|\textit{facts}|\in[3,8]$

  * •

For $\mathcal{D}=3$: $|\textit{rules}|\in[4,8]$, $|\textit{facts}|\in[5,10]$

  * •

For $\mathcal{D}=5$: $|\textit{rules}|\in[6,14]$, $|\textit{facts}|\in[6,12]$

####  A.1.3 Depth of inference

To investigate transformers’ performance with respect to the minimum number of
inference steps a logical reasoner would require, we use the _size of the
smallest justification_ Horridge et al. (2008) for the answers to the queries.
This is a good approximation for two reasons: First, because it expresses the
minimum depth of a proof, and second because the probability to reuse the same
axioms in the proving process is rather small as the KBs are small and they
are generated in a chain-like as discussed in A.1.

The _justification_ for an inferred axiom or fact from $\mathcal{K}$ is a
minimal set of axioms from $\mathcal{K}$ that is sufficient for the entailment
to hold.

####  A.1.4 Usage of long axioms in the proving process

Figure 3: Analysis of explanation axioms per linguistic complexity level on
$\mathcal{L}\leq 3$ datasets.

Figure 3 presents the analysis of linguistic complexity (frequency of
connectives and quantifiers) of axioms appearing in explanations of questions
produced by the PCFG for $\mathcal{L}\leq 3$. We observe that only 10% of the
rules did not contain any quantifier (i.e., were of Level0) and only 20% did
not contain any Boolean operator. More than 50% of the rules contained axioms
with more than 2 Boolean operators and more than 60% with more than 2
quantifiers. Hence, there is a high chance many of the rules in the
explanation were of at least Level2.

###  A.2 Additional training details

We used PyTorch 2.0 to set up our training and testing (inferencing). We use
the microsoft/deberta-v3-large model from the transformers Wolf et al. (2020)
library, along with the accelerate Gugger et al. (2022) framework.

We trained the DeBERTaV3-large (304M parameters) model on two A100 GPUs. We
used mixed precision (FP16) for our calculations to save memory and speed up
the process. The specific set of hyper-parameters used for all our models’
training is given in Table 6.

Hyper-parameter | Value
---|---
Batch size | 4
Accumulation steps | 2 (Effective Batch size = 8)
Learning rate | $2\times 10^{-5}$
Warm-up ratio | 0.06
Epochs | 4
Mixed precision | FP16
Betas | (0.9, 0.999)
Weight Decay | $1\times 10^{-4}$
Text Embedding Size | 512 (dimensions)

Table 6: Detailed specifications of the hyper-parameters used in
DeBERTaV3-large training.

The model output corresponds to the truth value
$\\{0-False,1-True,2-Unknown\\}$.

###  A.3 Performance of the models at datasets for
$\mathcal{L}_{0},\mathcal{L}_{1},\mathcal{L}_{2}$

The performance of the models on datasets of each level are illustrated in
Tables 7, 8, 9.

| DELTA0,0 | DELTA1,0 | DELTA2,0 | DELTA3,0 | DELTA5,0
---|---|---|---|---|---
Test (own) |  100.0 |  99.7 |  99.4 |  98.9 |  98.7
$\mathcal{D}\leq 5,\mathcal{L}=0$ |  61.4 |  75.3 |  93.2 |  97.7 |  98.8
$\mathcal{D}$ = N/A |  98.8 |  97.9 |  94.4 |  95.2 |  98.2
$\mathcal{D}=0$ |  99.9 |  100.0 |  100.0 |  99.5 |  100.0
$\mathcal{D}=1$ |  48.9 |  99.6 |  100.0 |  99.5 |  100.0
$\mathcal{D}=2$ |  11.9 |  47.1 |  96.3 |  99.0 |  99.0
$\mathcal{D}=3$ |  34.3 |  49.5 |  75.7 |  99.0 |  99.0
$\mathcal{D}=4$ |  32.1 |  45.0 |  72.0 |  99.0 |  99.0
$\mathcal{D}=5$ |  29.6 |  42.9 |  67.2 |  97.5 |  99.0

Table 7: Accuracy of DELTA models on their own test sets, and on the entire,
and slices of $\mathcal{D}\leq 5,\mathcal{L}=0$ dataset.

| DELTA0,1 | DELTA1,1 | DELTA2,1 | DELTA3,1 | DELTA5,1
---|---|---|---|---|---
Test (own) |  100.0 |  99.7 |  99.6 |  99.7 |  99.5
$\mathcal{D}\leq 5,\mathcal{L}\leq 1$ |  67.9 |  92.4 |  85.8 |  98.7 |  99.6
$\mathcal{D}$ = N/A |  99.0 |  98.1 |  99.3 |  98.8 |  99.7
$\mathcal{D}=0$ |  99.9 |  100.0 |  100.0 |  100.0 |  100.0
$\mathcal{D}=1$ |  52.5 |  99.3 |  99.5 |  100.0 |  100.0
$\mathcal{D}=2$ |  27.4 |  81.7 |  97.5 |  99.0 |  99.5
$\mathcal{D}=3$ |  47.9 |  79.5 |  61.5 |  99.0 |  99.5
$\mathcal{D}=4$ |  46.9 |  77.2 |  58.0 |  98.0 |  99.0
$\mathcal{D}=5$ |  39.4 |  66.0 |  53.5 |  96.5 |  99.0

Table 8: Accuracy of DELTA models on their own test sets, and on the entire,
and slices of $\mathcal{D}\leq 5,\mathcal{L}\leq 1$ dataset.

| DELTA0,2 | DELTA1,2 | DELTA2,2 | DELTA3,2 | DELTA5,2
---|---|---|---|---|---
Test (own) |  99.9 |  99.5 |  99.7 |  99.7 |  99.6
$\mathcal{D}\leq 5,\mathcal{L}\leq 2$ |  55.1 |  89.7 |  85.3 |  99.1 |  99.7
$\mathcal{D}$ = N/A |  99.6 |  95.6 |  98.7 |  99.2 |  99.7
$\mathcal{D}=0$ |  99.9 |  100.0 |  100.0 |  100.0 |  100.0
$\mathcal{D}=1$ |  37.2 |  99.6 |  100.0 |  100.0 |  99.5
$\mathcal{D}=2$ |  16.1 |  81.7 |  98.5 |  100.0 |  99.0
$\mathcal{D}=3$ |  16.4 |  62.7 |  59.0 |  98.5 |  99.5
$\mathcal{D}=4$ |  17.6 |  63.1 |  62.0 |  99.5 |  100.0
$\mathcal{D}=5$ |  10.0 |  63.4 |  51.0 |  98.0 |  98.5

Table 9: Accuracy of DELTA models on their own test sets, and on the entire, and slices of $\mathcal{D}\leq 5,\mathcal{L}\leq 2$ dataset. $ABoxAssertion$ | $\rightarrow$ | $ConceptAssertion\,|\,RoleAssertion$
---|---|---
$TBoxAxiom$ | $\rightarrow$ | $ConceptInclusion$
$ConceptInclusion$ | $\rightarrow$ | $InclusionL0$
$InclusionL0$ | $\rightarrow$ | $ConceptL0\,\sqsubseteq\,ConceptL0\,[0.6]\,|\,SpecialAxiom\,[0.4]$
$SpecialAxiom$ | $\rightarrow$ | ${}^{\prime}+^{\prime}\,\top\,\sqsubseteq\,\forall\,RoleName\,^{\prime}.^{\prime}\,{}^{\prime}(^{\prime}\,Concept\,^{\prime})^{\prime}\,|$
|  | $\exists\,RoleName\,^{\prime}.^{\prime}\,{}^{\prime}(^{\prime}\,{}^{\prime}+^{\prime}\,\top\,^{\prime})^{\prime}\,\sqsubseteq\,Concept$
$Concept$ | $\rightarrow$ | $ConceptL0$
$ConceptL0$ | $\rightarrow$ | $ConceptNameOrRestriction$
$ConceptNameOrRestriction$ | $\rightarrow$ | $Polarity\,ConceptName\,|\,RestrictionConcept$
$RestrictionConcept$ | $\rightarrow$ | $RestrictionD0$
$RestrictionD0$ | $\rightarrow$ | $Restriction\,RoleName\,^{\prime}.^{\prime}\,{}^{\prime}(^{\prime}\,Polarity\,ConceptName\,^{\prime})^{\prime}\,|$
|  |  $\exists\,RoleName\,^{\prime}.^{\prime}\,{}^{\prime}(^{\prime}\,{}^{\prime}+^{\prime}\,\top\,^{\prime})^{\prime}\,|\,\forall\,RoleName\,^{\prime}(^{\prime}\,{}^{\prime}+^{\prime}\,\bot\,^{\prime})$’
$Restriction$ | $\rightarrow$ | $\forall\,|\,\exists\,|\,Symbol\,Number$
$Symbol$ | $\rightarrow$ | ${}^{\prime}>^{\prime}\,|\,^{\prime}\geq^{\prime}\,|\,^{\prime}<^{\prime}\,|\,^{\prime}\leq^{\prime}\,|\,^{\prime}=^{\prime}$
$Number$ | $\rightarrow$ | ${}^{\prime}1^{\prime}\,|\,^{\prime}2^{\prime}\,|\,^{\prime}3^{\prime}$
$ConceptName$ | $\rightarrow$ | ${}^{\prime}ambitious^{\prime}\,|\,^{\prime}confident^{\prime}\,|\,^{\prime}creative^{\prime}\,|\,^{\prime}determined^{\prime}\,|$
|  | ${}^{\prime}enthusiastic^{\prime}\,|\,^{\prime}innovative^{\prime}\,|\,^{\prime}logical^{\prime}\,|\,^{\prime}persevering^{\prime}$
$RoleName$ | $\rightarrow$ | ${}^{\prime}admires^{\prime}\,|\,^{\prime}consults^{\prime}\,|\,^{\prime}guides^{\prime}\,|\,^{\prime}instructs^{\prime}\,|$
|  | ${}^{\prime}leads^{\prime}\,|\,^{\prime}mentors^{\prime}\,|\,^{\prime}supervises^{\prime}\,|\,^{\prime}supports^{\prime}$
$IndividualName$ | $\rightarrow$ | ${}^{\prime}Ioanna^{\prime}\,|\,^{\prime}Dimitrios^{\prime}\,|\,^{\prime}Eleni^{\prime}\,|\,^{\prime}Maria^{\prime}\,|$
|  | ${}^{\prime}Manolis^{\prime}\,|\,^{\prime}Angelos^{\prime}\,|\,^{\prime}Panos^{\prime}\,|\,^{\prime}Anna^{\prime}$
$RoleAssertion$ | $\rightarrow$ | $RoleName\,^{\prime}(^{\prime}\,IndividualName\,^{\prime},^{\prime}\,IndividualName\,^{\prime})^{\prime}$
$ConceptAssertion$ | $\rightarrow$ |  ${}^{\prime}(^{\prime}\,Concept\,^{\prime})^{\prime}\,{}^{\prime}(^{\prime}\,IndividualName\,^{\prime})$’
$Polarity$ | $\rightarrow$ | ${}^{\prime}+^{\prime}\,|\,^{\prime}\neg^{\prime}$
$Connective$ | $\rightarrow$ | ${}^{\prime}\sqcup^{\prime}\,|\,^{\prime}\sqcap^{\prime}$
Table 10: Probabilistic Context-Free Grammar for $\mathcal{L}=0$ KBs