# BoardgameQA: A Dataset for Natural Language Reasoning with Contradictory
Information

Mehran Kazemi, Quan Yuan, Deepti Bhatia, Najoung Kim, Xin Xu,
Vaiva Imbrasaite, Deepak Ramachandran
Google Research
{mehrankazemi, yquan, bhatiad, njkim, xxujasmine,
vimbrasaite<EMAIL_ADDRESS>

###### Abstract

Automated reasoning with unstructured natural text is a key requirement for
many potential applications of NLP and for developing robust AI systems.
Recently, Language Models (LMs) have demonstrated complex reasoning capacities
even without any finetuning. However, existing evaluation for automated
reasoning assumes access to a consistent and coherent set of information over
which models reason. When reasoning in the real-world, the available
information is frequently inconsistent or contradictory, and therefore models
need to be equipped with a strategy to resolve such conflicts when they arise.
One widely-applicable way of resolving conflicts is to impose preferences over
information sources (e.g., based on source credibility or information recency)
and adopt the source with higher preference. In this paper, we formulate the
problem of reasoning with contradictory information guided by preferences over
sources as the classical problem of _defeasible reasoning_ , and develop a
dataset called BoardgameQA for measuring the reasoning capacity of LMs in this
setting. BoardgameQA also incorporates reasoning with implicit background
knowledge, to better reflect reasoning problems in downstream applications. We
benchmark various LMs on BoardgameQA and the results reveal a significant gap
in the reasoning capacity of state-of-the-art LMs on this problem, showing
that reasoning with conflicting information does not surface out-of-the-box in
LMs. While performance can be improved with finetuning, it nevertheless
remains poor.

##  1 Introduction

A fundamental goal of AI since its early days has been automatically applying
logical or deductive reasoning to draw new conclusions from existing knowledge
[28, 20]. Since a large amount of knowledge is available in the form of
natural language, tremendous effort has been put into developing models that
can understand and reason over natural language [22, 40, 52, 30, 12] (see [33]
for a survey). Recent years have seen substantial improvements in this
direction thanks to advancements in pretrained language models (LMs) [8, 9]
that can handle unstructured data more flexibly, combined with advanced
prompting techniques [50, 29], and modular reasoning approaches [22, 12].

Existing work in automated reasoning in natural language usually assumes that
the provided knowledge is consistent and reliable. But in many applications,
the collection of information one has to reason with is inconsistent and
contradictory. This is the case, for instance, when reasoning is performed
with information found in different online sources or social media (e.g.,
retrieval-augmented LMs [17, 3]). When input sources are contradictory, one
can consider various strategies to resolve the contradictions. One simple and
practical formulation, which we adopt in this work, is to resolve the
conflicts based on preferences over the information sources: when a conflict
arises, the information from the source with a higher preference should be
used to solve the reasoning problem. Depending on the application, preferences
can be assigned based on different criteria, e.g., based on the credibility of
websites or social media users, or based on the recency of the information
with newer information being preferred over older information. Exceptions to
generics can also be expressed as preferences; for example, generic knowledge
such as _“birds fly”_ (see also [6]) should be overridden by exceptions such
as _“penguins are birds but do not fly”_ (see also [1]) when reasoning about
penguins. Figure 1 demonstrates an example of a reasoning problem with
conflicting information, where the conflict is resolved based on recency.

Figure 1:  A reasoning problem with contradictory information (conflict
resolved based on recency).

Reasoning with conflicting information guided by preferences can be formulated
as a form of the classical _defeasible reasoning_ problem [31, 19, 27]. In
this work, we study the reasoning ability of LMs in this setting. Toward this
goal, we create a synthetic dataset where each example contains a defeasible
theory (a set of input facts, possibly contradictory rules, and preferences
over the rules), and a question about that theory. Answering the questions in
the dataset requires multi-hop reasoning and conflict resolution over the
input theory. The difficulty level (e.g., the depth, amount and type of
conflicts, etc.) of the examples in the dataset can be controlled
automatically, enabling targeted comparisons of various aspects of reasoning.

We also note that while a large number of logical reasoning benchmarks provide
all the knowledge needed to answer questions [46, 39, 40, 18], such benchmarks
do not reflect common real-world scenarios where implicit background knowledge
plays an important role in reasoning. Moreover, models that translate the
textual examples into logical form and then leverage off-the-shelf solvers may
excel on these datasets, which does not reflect the true performance of such
models in real-world applications. For these reasons, in BoardgameQA only part
of the knowledge required to solve the problem is provided as input to the LM;
the missing knowledge has to come from the LM itself.

The problems in our dataset are formulated as scenarios of a board game, hence
we name it BoardgameQA111Available at:
https://storage.googleapis.com/gresearch/BoardgameQA/BoardgameQA.zip. License:
CC BY.. A board game theme allows us to create synthetic scenarios with
complex defeasible rules to reason about that seem natural when stated in text
and hence allows background commonsense world knowledge to also be used. To
the best of our knowledge, BoardgameQA is the first dataset for multi-hop
reasoning _with contradictory inputs_. Figure 2 shows a sample example from
the dataset where the conflict resolution and missing knowledge have been
highlighted.

We benchmark various LMs on BoardgameQA and measure their defeasible reasoning
capacity. Most notably, our results reveal that LMs perform poorly when
reasoning with conflicting sources, especially in the few-shot setting
(compared to the finetuning setting) suggesting that preference understanding
and defeasible reasoning capacities do not surface out-of-the-box in
pretrained LMs. Secondly, we find that smaller LMs perform poorly when not all
of the required information is provided as input. These results highlight a
critical gap in the reasoning capacity of current LMs, considering that
reasoning over contradicting and incomplete sets of information is a common
scenario in many applications, and is key for developing robust AI systems.

##  2 Related Work

Our work spans three dimensions: 1- text-based logical reasoning, 2- reasoning
with conflicting sources, and 3- reasoning with incomplete information. In the
following section, we briefly summarize the literature on each of these axes
that relate to our work.

Text-based logical reasoning approaches: Earlier works on natural language
logical reasoning have finetuned LMs to directly provide answers to logical
reasoning questions [11, 4, 38, 18]. Later work showed that explicitly
generating the entire proof leads to substantial improvements both in the case
of finetuning and in the case of few-shot learning [29, 13, 55, 56]. In
addition, modular reasoning approaches where the LM is used as a tool within a
reasoning algorithm [22, 12, 49, 23] have been shown to achieve both
performance gains and more precise intermediate proof chains. In this paper,
we experiment with four types of approaches: 1- finetuning without explicit
reasoning steps, 2- finetuning with explicit reasoning steps, 3- prompt-tuning
with chain-of-thought (CoT) prompting [50], and 4- few-shot in-context
learning with CoT.

Text-based logical reasoning datasets: Many datasets have been created to
measure the logical reasoning ability of NLP models [46, 40, 58, 18, 43]. In
Table 1, we provide a comparison of (a subset of) these datasets along three
desired features in this work. All datasets compared contain only facts and
rules that are non-contradicting. The dataset closest to our work is the
_ConditionalQA_ dataset [45] where the answer to the questions follows a _“If
X then yes, if Y then no”_ format.

Figure 2:  A sample example from BoardgameQA that requires one hop of
reasoning. The text in violet highlights conflict resolution and the text in
blue highlights the missing information.

Reasoning with conflicts: From the early days of AI, reasoning with
conflicting information has been an important topic and many approaches have
been developed to handle such conflicts [32, 31, 35]. The problem we study in
this paper is an instance of defeasible reasoning [31, 19, 27] which has
applications in various domains (especially in legal reasoning) [41, 16, 7]
and has been argued to be one of the most important future directions in a
recent survey of LM reasoning literature [54]. In defeasible reasoning, there
are preferences over the rules and in the case of conflict between two rules,
the conclusion from the higher preference rule is accepted. Previous work on
defeasible reasoning with natural language has studied the problem of
adjusting the probability of a conclusion based on new (single-hop) evidence
[37, 26]. Our work extends this line of work by developing a dataset for
multi-hop defeasible reasoning with preferences over sources.

Reasoning with incomplete information: Several existing reasoning benchmarks
adopt a setup where part of the required information is missing and needs to
come from the model itself [44, 5, 2, 48]. Some datasets also employ a setup
in which none of the required rules are provided as input [47, 15, 43, 21].
Our work focuses mainly on cases where part of the knowledge needs to come
from the model and another part of the knowledge is provided as input.

##  3 Background and Notation

We let $\mathcal{E}=\\{e_{1},\dots,e_{N}\\}$ and
$\mathcal{P}=\\{p_{1},\dots,p_{M}\\}$ represent a set of entities and
predicates. We represent a fact in the logical form using the triple notation
$(e_{i},p_{j},e_{k})$, where $e_{i},e_{k}\in\mathcal{E}$ and
$p_{j}\in\mathcal{P}$, and a rule as $r:r_{b}\rightarrow r_{h}$ where $r_{b}$
represents the body of the rule and $r_{h}$ represents the head. We use $!$ to
indicate negation. A monotonic theory $\mathcal{T}=(\mathcal{F},\mathcal{R})$
is a tuple containing a set $\mathcal{F}$ of (positive or negative) facts, and
a set $\mathcal{R}=\\{r_{1},\dots,r_{|\mathcal{R}|}\\}$ of rules. We let
$\mathcal{T}\vDash f$ represent that the fact $f$ can be derived from the
theory $\mathcal{T}$ using the standard inference rules of logic (See [42]).
For a monotonic theory $\mathcal{T}=(\mathcal{F},\mathcal{R})$, if
$\mathcal{T}\vDash f$, then for any theory $\mathcal{T}^{\prime}$ such that
$\mathcal{T}^{\prime}=(\mathcal{F}\cup\mathcal{F}^{\prime},\mathcal{R})$, we
also have $\mathcal{T}^{\prime}\vDash f$ (that is, adding new facts does not
change previously derived facts).

Dataset $\rightarrow$ Feature $\downarrow$ |  bAbI 15 |  CLUTRR |  FOLIO |  Proof Writer |  PrOntoQA OOD |  AR-LSAT |  ENWN |  Leap of Thought |  Conditional QA |  Boardgame QA
---|---|---|---|---|---|---|---|---|---|---
Contradictory Information |  ✗ |  ✗ |  ✗ |  ✗ |  ✗ |  ✗ |  ✗ |  ✗ |  $\sim$ |  ✓
Incomplete Information |  ✗ |  $\sim$ |  ✗ |  ✗ |  ✗ |  ✗ |  ✓ |  ✓ |  ✓ |  ✓
Auto. Diff. Control |  ✓ |  ✓ |  ✗ |  ✓ |  ✓ |  ✗ |  ✗ |  $\sim$ |  ✗ |  ✓
Table 1:  A comparison of BoardgameQA with some of the widely-used logical
reasoning datasets (bAbI 15 [51], CLUTRR [43], FOLIO [18], ProofWriter [46],
PrOntoQA-OOD [40], AR-LSAT [58], ENWN [44], leap-of-thought [48], and
ConditionalQA [45]) in terms of three key features. We use $\sim$ in the case
of incomplete information for CLUTRR because there is only a fixed set of
information that needs to come from the model (i.e., kinship relations), in
the case of automatic difficulty control for leap-of-thought because the depth
of reasoning is fixed (difficulty is added through distractors), and in the
case of contradictory information for ConditionalQA because while the answer
to a question can be yes under one set of conditions and no under another set
of conditions, the two sets of conditions are mutually exclusive.

Defeasible Theory: A defeasible theory
$\mathcal{T}^{(d)}=(\mathcal{F},\mathcal{R},\mathcal{O})$ is a triple
containing a set $\mathcal{F}$ of facts, a set
$\mathcal{R}=\\{r_{1},\dots,r_{|\mathcal{R}|}\\}$ of rules, and a set
$\mathcal{O}=\\{r_{t_{1}}>r_{t_{2}},\dots,r_{t_{3}}>r_{t_{4}}\\}$ of pair-wise
relative priorities/preferences between rules.222Note: Many types of
preferences can be converted into pair-wise relative preferences. The rules
hold _defeasibly_ , meaning the conclusion from a rule may be defeated by
contrary evidence from a higher priority rule. This happens, for example, when
one rule implies something is true but another rule with a higher priority
implies it is false; in such cases, we accept the conclusion from the higher
priority rule (see Figure 1). We let $\mathcal{T}^{(d)}\vDash f$ represent
that $f$ can be derived from a defeasible theory $\mathcal{T}^{(d)}$ after
resolving conflicts. Note that the initial facts $\mathcal{F}$ are internally
consistent and always have priority over the derived facts. We assume the
theory is _defeasibly consistent_ , meaning whenever a conflict arises, the
preferences can be used to resolve it. An example of a defeasible theory
$\mathcal{T}^{(d)}$ is as follows:

######  Example 3.1.

$\mathcal{F}=\\{\text{Tweety is a
penguin.}\\},\mathcal{R}=\\{r_{1}:\text{Penguins are
birds.}~{}r_{2}:\text{Birds fly.}~{}r_{3}:\text{Penguins do not
fly.}\\},\mathcal{O}=\\{r_{3}>r_{2}\\}$. From the theory, one can first use
$r_{1}$ to derive that “Tweety is a bird”. Then, one can use $r_{2}$ to derive
that “Tweety flies”. However, one can also use $r_{3}$ to derive that “Tweety
does not fly”, which is in conflict with the previous derivations. Since
$r_{3}>r_{2}$, we accept the derivation that “Tweety does not fly”.

Conflict types: Conflicts can arise for rules whose heads cannot be
simultaneously true, e.g., for two rules $r:r_{b}\rightarrow z$ and
$r^{\prime}:r^{\prime}_{b}\rightarrow!z$. For a theory $\mathcal{T}^{(d)}$
with these two rules, $\mathcal{T}^{(d)}\vDash z$ in two cases: (a) $r$ has
higher priority than $r^{\prime}$ and we can prove $r_{b}$, and (b) $r$ has
lower priority than $r^{\prime}$ and we can prove $r_{b}$ but we cannot prove
$r^{\prime}_{b}$. In the first case, one does not need to take into account
$r^{\prime}_{b}$ for conflict resolution, but in the second case it is
critical to take $r^{\prime}_{b}$ into account. We name the first type of
conflict Type1 conflict and the second type Type2.

Algorithm 1 GenerateTheory

Input: Question $q$, Depth $d$

1: if d == 0 then

2: addToFacts(q)

3: else

4: Sample sub-questions $\mathcal{Q}=\\{q_{1},...,q_{n}\\}$ and rule $r$ s.t.
$q$ can be derived from $\mathcal{Q}$ and $r$.

5: addToRules($r$)

6: if CoinFlip($p_{\textit{Conf}}$) == Conflict then

7: Sample sub-questions
$\mathcal{Q}^{\prime}=\\{q^{\prime}_{1},...,q^{\prime}_{m}\\}$ and rule
$r^{\prime}$ s.t. $!q$ can be derived from $\mathcal{Q}^{\prime}$ and
$r^{\prime}$.

8: addToRules($r^{\prime}$)

9: if CoinFlip($p_{\textit{ConfType1}}$) == Type1 then

10: $\mathcal{Q}=\mathcal{Q}+SubSample(\mathcal{Q}^{\prime})$

11: addToPreferences($r$, $r^{\prime}$)

12: else

13: $\mathcal{Q}=\mathcal{Q}+RemoveOneSubquestion(\mathcal{Q}^{\prime})$

14: addToPreferences($r^{\prime}$, $r$)

15: for $q_{i}$ in $\mathcal{Q}$ do

16: GenerateTheory($q_{i}$, d-1)

##  4 The BoardgameQA Dataset

We now describe how we create a dataset for measuring the ability of LMs in
reasoning with conflicting inputs in a defeasible setup. Our dataset creation
follows a backward story generation strategy similar to [53, 22]. Each example
in the dataset contains a (defeasible) theory $\mathcal{T}^{(d)}$ and a
question $q$. The goal is to predict whether $\mathcal{T}^{(d)}\vDash q$, or
$\mathcal{T}^{(d)}\vDash~{}!q$, or neither. Therefore, the label space for
each question is $\\{\textit{proved},\textit{disproved},\textit{unknown}\\}$.
We next describe how we generate examples with the label _proved_ ; examples
with the label _disproved_ or _unknown_ are created by modifying the examples
with label _proved_.

The facts of each theory describe the current state of a board game, the rules
of each theory represent the rules of the board game, and the questions are
about the game. In the design of BoardgameQA, we include several variables
that can be used to sample examples with varying levels of difficulty with
respect to several finer-grained properties (e.g., depth, number and types of
conflicts).

Entities and predicates: We start with a predefined set of entities
$\mathcal{E}$ (e.g., dog, cat, lion, etc.) and a predefined set of predicates
$\mathcal{P}$ (e.g., invite for dinner, attack the fields, etc.) that we
sample from to generate facts and rules. We use the animals as entities and
the boardgame-inspired verbs/operations as our predicates. Using these
entities and predicates, we can create facts such as the dog attacks the
fields of the lion. To make the problem more challenging, we use different
entities and predicates across training and test similar to [24]. The full
list of entities and predicates is provided in Appendix C.3.

Rule types: We adopt a set of 6 rule templates containing existential and
universal quantifiers, conjunctions, and missing information. The rules are as
follows: 1- $\forall X:(X,p_{1},e_{1})\Rightarrow(X,p_{2},e_{2})$, 2- $\forall
X:(X,p_{1},e_{1})\wedge(X,p_{2},e_{2})\Rightarrow(X,p_{3},e_{3})$, 3-
$(e_{1},p_{1},e_{2})\Rightarrow(e_{2},p_{2},e_{3})$, 4-
$(e_{1},p_{1},e_{2})\wedge(e_{3},p_{2},e_{2})\Rightarrow(e_{2},p_{3},e_{4})$,
5- $(e_{1},\hat{p},\hat{e})\Rightarrow(e_{1},p_{2},e_{2})$, and 6- $\exists
X(X,p_{1},e_{1})\Rightarrow(e_{2},p_{2},e_{3})$, where $X$ represents a
universally or existentially bounded variable, each $e_{i}$ represents an
entity, and each $p_{j}$ represents a predicate. The fifth rule template
corresponds to a rule where the predicate (or object entity) in the rule body
may not be an element of $\mathcal{P}$ (resp. $\mathcal{E}$). For more
information, see below.

Selecting a question: To generate each example, we first sample a question
$q=(e_{i},p_{j},e_{k})$ that should be proved or disproved, where $e_{i}$ and
$e_{k}$ are sampled from $\mathcal{E}$ and $p_{j}$ is sampled from
$\mathcal{P}$. We also sample the sign of the question (positive or negative).
For example, we might sample the question _!(dog, attack the fields, lion)_
asking whether _the dog does not attack the fields of the lion_. The question
is then converted into natural language using a template (see Appendix C.3).

Category |  Description |  Example Facts |  Example Rule
---|---|---|---
Time Conversion |  Compares the age of an entity to a certain age specified with different units. |  The dog is 13 months and a half old |  If the dog is more than a year old, then …
Orthography |  Asks about the letters in names. |  The dog is named Paco. The cat is named Pashmak. |  If the dog has a name that starts with the same letter as the name of the cat, then …
Numeric Comparisons |  Some numbers are required to be summed and then compared to other numbers. |  The dog has two friends that are nice and five that are not |  If the dog has less than 10 friends, then …
Lexical Entailment |  The fact and the rule body are not identical but the fact entails the rule body. |  The dog assassinated the mayor |  If the dog killed the mayor, then …
World Knowledge |  Some knowledge about the world is needed to connect the fact to the rule body. |  The dog is currently in Montreal. |  If the dog is currently in Canada, then …
Event Times |  Knowledge about times of events is needed to connect the fact to the rule body. |  The dog is watching a movie that was released in 2005. |  If the dog is watching a movie that was released after Covid19 started, then …
Part Of |  The fact and the rule body have a _part of_ relation. |  The dog is a nurse |  If the dog works in healthcare, then …
Affordance |  The rule body is about a certain feature/affordance of the fact. |  The dog has a knife |  If the dog has a sharp object, then …
Volumes |  Knowledge of what objects fit in what other objects is required. |  The dog has a ball with a radius of 15 inches. |  If the dog has a ball that fits in a 28 x 35 x 35 inches, then …

Table 2:  Categories, descriptions, and examples of incomplete information in
BoardgameQA. For lexical entailment, world knowledge, event times, and
affordance, a list of examples is written manually from which the sampling
procedure can select. In others, examples are generated automatically.

Theory generation: The theory generation is the main component of the dataset
generation that constructs the facts, rules and question to be used in each
example. A high-level description is provided in Algorithm 16 and an example
generation is shown in Appendix C. We first sample some sub-questions
$\mathcal{Q}={q_{1},…,q_{n}}$ and a rule $r$ which has $\mathcal{Q}$ in its
body and $q$ in its head, such that $q$ can be derived from $\mathcal{Q}$ and
$r$. The sampling is done by first selecting one of the aforementioned rule
types, then matching the head of the rule to the question $q$, and then
sampling sub-questions $\mathcal{Q}$ based on the body of the rule. For
example for the question _!(dog, attack the fields, lion)_ , we might sample
the first rule type (see the six types above), then $p_{2}$ will be mapped to
_attack the fields_ and $e_{2}$ will be mapped to lion, and we also sample a
sub-question such as _(dog, unite with, cat)_ and add the rule $\forall
X:(X,\textit{unite~{}with},\textit{cat})\Rightarrow!(X,\textit{attacks~{}the~{}fields},\textit{lion})$
to our set of rules. We then make a recursive call for each $q_{i}$ to
generate new rules and facts for them.

We then decide whether a conflict should be introduced or not, by using a
biased coin flip with $p_{\textit{Conf}}$ representing the probability of
conflict. If the decision is to produce conflicts, then we generate another
set of sub-questions $\mathcal{Q}^{\prime}={q^{\prime}_{1},…,q^{\prime}_{m}}$
and another rule $r^{\prime}$ such that $!q$ can be derived from
$\mathcal{Q}^{\prime}$ and $r^{\prime}$. Then we probabilistically decide if
we want to generate a Type1 or a Type2 conflict using a biased coin flip with
probability $p_{\textit{ConfType1}}$. If the first case is selected, then
$r>r^{\prime}$ is added to the preferences. In this case, we can make
recursive calls for all or a subset of the facts in $\mathcal{Q}^{\prime}$.
Otherwise, $r^{\prime}>r$ is added to the preferences. In this case, we make
recursive calls for _all but one_ of the facts in $\mathcal{Q}^{\prime}$
(selecting randomly) to ensure that $r^{\prime}$ does not activate.

Proofs: We keep track of the facts, rules, and preferences during the
generation process and turn them into proofs for the examples.

Stopping criterion: Every time we make a recursive call to the function in
Algorithm 16, the example will contain one extra hop in its proof. We set the
stopping criterion as the number of hops in the proof. Toward this goal, we
included an argument $d$ in Algorithm 16 which corresponds to the target
maximum number of hops in the proof; $d$ decreases by one every time we make a
recursive call. When the algorithm is called with $d=0$, instead of generating
rules and sub-questions for the input question $q$, we simply add $q$ to our
set of facts.

Incomplete information: We generate examples with incomplete information where
part of the knowledge should come from the LM (corresponds to rule type 5).
For a question $q$ in the theory generation phase, we sample sub-questions
$\mathcal{Q}$ and rule $r$ such that $\hat{\mathcal{Q}}$ can be derived based
on $\mathcal{Q}$ and $q$ can be derived from $\hat{\mathcal{Q}}$ and $r$. We
then hide $\hat{\mathcal{Q}}$ from the model so the model has to derive it
itself. We use a separate body of world knowledge, commonsense knowledge,
mathematical, and orthography reasoning for generating $\mathcal{Q}$ and
$\hat{\mathcal{Q}}$ (see Table 2 for a high-level description and Appendix C.2
for more details). For example, for the goal _“the dog unites with the cat”_
we generate the sub-question _“The dog is in Montreal.”_ and the rule _“If the
dog is in Canada, then the dog unites with the cat.”_. Then, an extra
reasoning step is needed from the model to recognize that Montreal is in
Canada.

We generate sub-questions and rules that require extra knowledge and reasoning
with probability $p_{\textit{{MissInfo}}}$; otherwise, we create sub-questions
and rules that require no extra knowledge and reasoning. To make the problem
more challenging, we only include some categories of extra knowledge and
reasoning in the training set; this ensures that the models cannot simply
learn the extra knowledge from the training set and use it in the test set.

Conversion to natural language: Finally, once we generate the facts, rules,
preferences, and question, we use manually constructed templates to turn each
of them into a textual format. To make the problem more challenging, we use
multiple templates per rule type and use some of the templates only in the
test set (see Appendix C.3 for details). A comparison of BoardgameQA with
other prominent deductive reasoning datasets in terms of the average length of
examples and the average number of unique tokens per example is provided in
Figure 3.

Figure 3:  A comparison of BoardgameQA with ProofWriter [46] and PrOntoQA [39]
in terms of average length of examples and average number of unique tokens per
example on depth 3 of the datasets.

Disproved and unknown examples: So far, we described how to generate examples
with the label _proved_. Generating examples with the label _disproved_ can be
done simply by first generating an example with the label _proved_ and then
negating the question. Also, generating examples with the label _unknown_ can
be done by perturbing the theory until the statement in the question cannot be
derived from the theory (e.g., reducing the amount of money of the frog to 50
dollars in the example of Figure 2). We randomly select and apply the
following perturbations to the theory and run a defeasible solver implemented
based on the scalable solver in [27] on the resulting theory until the label
becomes unknown: 1- change the predicate of a fact or a rule, 2- change the
sign of a fact or an element of the rule, 3- replace a fact with a new fact,
and 4- flip the order of a preference.

##  5 Experiments

One of the primary goals of our experiments is to verify if LMs are capable of
reasoning in a defeasible setup. For this reason, we conduct experiments with
various LM architectures (encoder-only, encoder-decoder, and decoder-only) and
various pre-training and learning paradigms (finetune with and without proofs,
prompt tuning, few-shot in-context learning, and instruction-tuned).
Specifically, we test 1) finetuning BERT-large [14] with a classification head
to predict the label directly, 2) finetuning T5 1.1 XXL [34] to generate the
entire proof and then the label, 3) few-shotting PaLM 62B and PaLM 540B [9]
where we provide demonstration examples and chain-of-thought (CoT) in the
prompt (the CoT corresponds to the proof), 4) few-shotting the instruction-
finetuned FLAN-PaLM 540B [10] with CoT, and 5) soft prompt-tuning [25] PaLM
62B with CoT where instead of providing a static prompt, we make the prompt
embedding learnable and tune its parameters using the training data (the rest
of the LM parameters are frozen). We report classification accuracy as the
metric. We also report the _majority class_ baseline ($\sim$33% since our
labels are balanced).

Dataset sizes: To gain a more detailed understanding of the models’ defeasible
reasoning capacity, we create several variations of BoardgameQA. The nature of
the variation will be discussed in the remainder of this section with each
experiment. For each variation, we sample $1000$ examples for train, $500$ for
validation, and $1000$ for test. We sample an equal number of examples from
each label.

Figure 4:  The model performances on depths 1–3 of the BoardgameQA dataset.
Many models struggle on this dataset, especially with higher depths.

###  5.1 Can LMs Reason with Contradictory Inputs?

As explained in Section 4, BoardgameQA makes use of a number of variables that
control various aspects of the dataset such as the amount and types of
conflict and the amount of extra knowledge required. We start by creating a
default version of the dataset that exhibits each of these properties to some
degree by setting $p_{\textit{Conf}}=0.5$, $p_{\textit{ConfType1}}=0.5$, and
$p_{\textit{MissInfo}}=0.5$. We then generate three datasets with depth 1–3
(i.e., requiring 1–3 hop(s) of reasoning, respectively), and measure the
performance of our baselines on these datasets.

The results are in Figure 4. The tuned models perform reasonably on depth 1,
but their performance substantially degrades on depths 2–3. This contrasts
with previous observations for monotonic reasoning (e.g., in [11, 46]) where
finetuned LMs reach near-perfect performance even on higher depths. This
indicates that reasoning with contradictory inputs is more difficult even with
finetuning. Moreover, we see that the few-shot models perform poorly across
all depths showing that conflict resolution is not achieved out-of-the-box
with pretrained models. This includes both PaLM and instruction-finetuned FLAN
PaLM models. PaLM 540B performs better than PaLM 62B showing that larger
models may have higher capacity for defeasible reasoning. More insights from
full confusion matrices can be found in Appendix A.

Hereafter, due to inference costs, we only experiment with finetuned BERT and
T5, prompt-tuned PaLM 62B, and few-shot PaLM 540B, and with examples of depth
2 to keep a medium level of difficulty in terms of reasoning hops and enable
measuring the effect of the other factors.

###  5.2 Does Correct Label Prediction Mean Correct Proof?

Recently, it has been shown that although large LMs achieve high accuracy on
label prediction for (monotonic) reasoning task, they do so by generating
spurious proofs that do not represent valid steps of reasoning [22]. There is
also evidence that LMs frequently exploit spurious correlations in the data
distribution to achieve high label accuracy, rather than reasoning purely
deductively [57]. Hence we design evaluation metrics to reflect a more
rigorous measure of accurate defeasible reasoning. In the case where a model
predicts the label correctly, and the label is one of _proved_ or _disproved_
(where an actual proof exists), we measure whether the proof generated by the
model is correct or not. For this purpose, we compute two automated proof
accuracy metrics (named _Rule F1_ and _Conflict F1_) and one manual metric
(named _Overall Proof Accuracy_) as described below. For _Rule F1_ , we
extract the rules used in the golden proof and the ones in the proof generated
by the model that are used to derive new facts (and ultimately, the goal).
Then we compute the F1-score of the overlap of the two sets. For _Conflict F1_
, we extract the conflict resolutions (corresponding to pairs of rules) used
in the gold proof and the ones in the proof generated by the model, and
compute the F1-score of their overlap. For _Overall Proof Accuracy_ , we
manually verify whether the proof is correct for $50$ sampled examples per
model. We compute these metrics on depth 2 of the dataset.

Figure 5:  Proof accuracy metrics for various models on depth 2 of the
dataset, when the label is predicted correctly.

According to the results in Figure 5, all models perform relatively well in
selecting the correct set of rules for the proof. The few-shot model performs
poorly on conflict resolution whereas the tuned models perform substantially
better, suggesting that preference understanding and conflict resolution do
not surface with simple few-shot prompting, and tuning is required for models
to exhibit this capacity. Second, the models often generate wrong proofs, even
when they predict the label correctly. The issue is less severe in the case of
the prompt-tuned model but becomes more severe for the finetuned and few-shot
models. We provide examples of proof failures in Appendix A.

Figure 6:  The model performances on four versions of the BoardgameQA dataset
with various amounts of conflicts in them.

###  5.3 Do Conflicts Make Reasoning More Difficult?

We create four versions of BoardgameQA named NoConflict, LowConflict,
MediumConflict, and HighConflict, with $p_{\textit{Conf}}$ set to 0.0, 0.2,
0.5 and 0.8 respectively; other factors are kept the same. Note that the
MediumConflict corresponds to the dataset in Figure 4. The results of the
models on these datasets are reported in Figure 6. The performance of all
models monotonically degrades as the number of conflicts increases, showing
that conflict resolution is indeed a major factor in the difficulty of the
problems. For example, BERT performs above-random for the NoConflict and
LowConflict cases, but the model performance drops to near-random on
MediumConflict and HighConflict cases.

Figure 7:  The model performances on three versions of the BoardgameQA dataset
with different distributions on the type of conflicts.

###  5.4 Which Conflict Type is More Difficult to Resolve?

To test which type of conflict (See sec. 4) is more difficult for the models,
we create three versions of the dataset with varying proportions of Type1 vs
Type2 conflicts, by setting $p_{\textit{ConfType1}}$ to 0.2, 0.5, and 0.8
respectively. The first dataset mostly contains conflicts of Type1, the second
contains both conflicts in a similar amount, and the third dataset contains
mostly Type2 conflicts. The other factors are kept constant across the
datasets.

The results of the models are reported in Figure 7. We see that models perform
slightly better on the dataset with mostly Type1 conflicts. This discrepancy
between performance on Type1 and Type2 conflicts is intuitive because in the
case of Type1 conflicts, the model can ignore the conflicting rule and whether
its body can be proved, but in the case of Type2 conflicts, the model has to
show that at least one of the elements in the body of the conflicting rule
cannot be proved. In the case of tuned models, we furthermore observe that
biasing the dataset toward one conflict type results in better performance
overall. This might be because the model mostly needs to learn to resolve one
type of conflict which may be easier than learning both.

###  5.5 Does Information Incompleteness Make Reasoning More Difficult?

As described in Section 4, we can control the amount of information
incompleteness using a parameter which we named $p_{\textit{MissInfo}}$. To
test how the information incompleteness affects the performance of various
models, we create three versions of our dataset with $p_{\textit{MissInfo}}$
set to $0.2$, $0.5$ and $0.8$, which we name _KnowledgeLight_ ,
_KnowledgeMedium_ and _KnowledgeHeavy_ , respectively.

Figure 8:  The model performances on three versions of BoardgameQA with
various degrees of incomplete information.

The results are reported in Figure 8. We observe that as the amount of
required knowledge increases, the performance of the finetuned models
decreases accordingly. However, the performance of the prompt-tuned and few-
shot models remain relatively unchanged, likely due to the larger size of the
model and the extra amount of knowledge that is present in the model, as well
as the fact that working with real-world knowledge might be easier for these
models than with artificial knowledge.

Figure 9:  The model performances on three versions of BoardgameQA with
various amounts of distracting facts and rules.

###  5.6 Do Distractors Make Reasoning More Difficult?

We also measure the effect of distracting facts and rules on model
performance. A distracting fact or rule is one that does not appear in the
proof and does not change the label. In Figure 2, for example, _“the frog has
a knife”_ is a distracting fact. To this end, each time we call Algorithm 16,
besides the sampled sub-questions, we also sample some distracting sub-
questions and add them to the set of sub-questions. We create three versions
of the BoardgameQA dataset where we add 0, 1, and 2 distracting facts in each
step, which we name _NoDistractors_ , _SomeDistractors_ , and
_ManyDistractors_ , respectively.

According to the results in Figure 9, the performance of the tuned models does
not substantially degrade with a small number of distractors, potentially
because the distractors can help the model avoid learning spurious
correlations. However, their performance drops substantially with more
distractors. Also, with more distractors, the performance of the few-shot
model decreases monotonically, although only marginally (this observation is
consistent with the results of [40]). This shows that distractors (that are
typically common in real applications) can also compound the problem
difficulty.

##  6 Conclusion

In this work, we introduced BoardgameQA, a dataset for measuring the natural
language reasoning ability of language models (LMs) in the presence of
conflicting input sources. Our dataset furthermore includes scenarios in which
the knowledge required for reasoning is only partially provided as input and
additional information needs to come from the model itself. We tested several
types of LMs on different variations of the dataset and observed that LMs
perform poorly when reasoning with conflicting inputs. In the case of smaller
models, the performance was also poor when additional knowledge from the LM is
needed. Since reasoning over contradicting and incomplete sets of information
is a common scenario in real-world applications, our results highlight an
important gap in the reasoning capacity of current LMs. We hope our dataset
can guide future work developing methodology to improve the reasoning ability
of LMs under this setup, or finding alternative formulations of conflict
resolution that better facilitate LM reasoning.

## References

  * [1] Emily Allaway, Jena D Hwang, Chandra Bhagavatula, Kathleen McKeown, Doug Downey, and Yejin Choi.  Penguins don’t fly: Reasoning about generics through instantiations and exceptions.  arXiv preprint arXiv:2205.11658, 2022.
  * [2] Forough Arabshahi, Jennifer Lee, Mikayla Gawarecki, Kathryn Mazaitis, Amos Azaria, and Tom Mitchell.  Conversational neuro-symbolic commonsense reasoning.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 4902–4911, 2021.
  * [3] Parishad BehnamGhader, Santiago Miret, and Siva Reddy.  Can retriever-augmented language models reason? the blame game between the retriever and the language model.  arXiv preprint arXiv:2212.09146, 2022.
  * [4] Gregor Betz, Christian Voigt, and Kyle Richardson.  Critical thinking for language models.  In Proceedings of the 14th International Conference on Computational Semantics (IWCS), pages 63–75, Groningen, The Netherlands (online), June 2021. Association for Computational Linguistics.
  * [5] Chandra Bhagavatula, Ronan Le Bras, Chaitanya Malaviya, Keisuke Sakaguchi, Ari Holtzman, Hannah Rashkin, Doug Downey, Scott Wen-tau Yih, and Yejin Choi.  Abductive commonsense reasoning.  arXiv preprint arXiv:1908.05739, 2019.
  * [6] Sumithra Bhakthavatsalam, Chloe Anastasiades, and Peter Clark.  Genericskb: A knowledge base of generic statements.  arXiv preprint arXiv:2005.00660, 2020.
  * [7] Marco Billi, Roberta Calegari, Giuseppe Contissa, Francesca Lagioia, Giuseppe Pisano, Galileo Sartor, and Giovanni Sartor.  Argumentation and defeasible reasoning in the law.  J, 4(4):897–914, 2021.
  * [8] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei.  Language models are few-shot learners.  In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 1877–1901. Curran Associates, Inc., 2020.
  * [9] Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, Parker Schuh, Kensen Shi, Sasha Tsvyashchenko, Joshua Maynez, Abhishek Rao, Parker Barnes, Yi Tay, Noam Shazeer, Vinodkumar Prabhakaran, Emily Reif, Nan Du, Ben Hutchinson, Reiner Pope, James Bradbury, Jacob Austin, Michael Isard, Guy Gur-Ari, Pengcheng Yin, Toju Duke, Anselm Levskaya, Sanjay Ghemawat, Sunipa Dev, Henryk Michalewski, Xavier Garcia, Vedant Misra, Kevin Robinson, Liam Fedus, Denny Zhou, Daphne Ippolito, David Luan, Hyeontaek Lim, Barret Zoph, Alexander Spiridonov, Ryan Sepassi, David Dohan, Shivani Agrawal, Mark Omernick, Andrew M. Dai, Thanumalayan Sankaranarayana Pillai, Marie Pellat, Aitor Lewkowycz, Erica Moreira, Rewon Child, Oleksandr Polozov, Katherine Lee, Zongwei Zhou, Xuezhi Wang, Brennan Saeta, Mark Diaz, Orhan Firat, Michele Catasta, Jason Wei, Kathy Meier-Hellstern, Douglas Eck, Jeff Dean, Slav Petrov, and Noah Fiedel.  PaLM: Scaling language modeling with pathways.  arXiv:2204.02311, 2022.
  * [10] Hyung Won Chung, Le Hou, Shayne Longpre, Barret Zoph, Yi Tay, William Fedus, Eric Li, Xuezhi Wang, Mostafa Dehghani, Siddhartha Brahma, et al.  Scaling instruction-finetuned language models.  arXiv preprint arXiv:2210.11416, 2022.
  * [11] Peter Clark, Oyvind Tafjord, and Kyle Richardson.  Transformers as soft reasoners over language.  In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI’20, 2021.
  * [12] Antonia Creswell, Murray Shanahan, and Irina Higgins.  Selection-inference: Exploiting large language models for interpretable logical reasoning.  In The Eleventh International Conference on Learning Representations, 2023.
  * [13] Bhavana Dalvi, Peter Jansen, Oyvind Tafjord, Zhengnan Xie, Hannah Smith, Leighanna Pipatanangkura, and Peter Clark.  Explaining answers with entailment trees.  In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 7358–7370, Online and Punta Cana, Dominican Republic, November 2021. Association for Computational Linguistics.
  * [14] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  arXiv preprint arXiv:1810.04805, 2018.
  * [15] Mor Geva, Daniel Khashabi, Elad Segal, Tushar Khot, Dan Roth, and Jonathan Berant.  Did aristotle use a laptop? a question answering benchmark with implicit reasoning strategies.  Transactions of the Association for Computational Linguistics, 9:346–361, 2021.
  * [16] Sergio Alejandro Gómez, Carlos Iván Chesnevar, and Guillermo Ricardo Simari.  Defeasible reasoning in web-based forms through argumentation.  International Journal of Information Technology & Decision Making, 7(01):71–101, 2008.
  * [17] Kelvin Guu, Kenton Lee, Zora Tung, Panupong Pasupat, and Mingwei Chang.  Retrieval augmented language model pre-training.  In International conference on machine learning, pages 3929–3938. PMLR, 2020.
  * [18] Simeng Han, Hailey Schoelkopf, Yilun Zhao, Zhenting Qi, Martin Riddell, Luke Benson, Lucy Sun, Ekaterina Zubova, Yujie Qiao, Matthew Burtell, et al.  FOLIO: Natural language reasoning with first-order logic.  arXiv:2209.00840, 2022.
  * [19] Abdelraouf Hecham, Pierre Bisquert, and Madalina Croitoru.  On a flexible representation for defeasible reasoning variants.  In AAMAS 2018-17th International Conference on Autonomous Agents and MultiAgent Systems, number AAMAS’18, pages 1123–1131, 2018.
  * [20] Carl Hewitt.  Planner: A language for proving theorems in robots.  In Proceedings of the 1st International Joint Conference on Artificial Intelligence, IJCAI’69, page 295–301, San Francisco, CA, USA, 1969\. Morgan Kaufmann Publishers Inc.
  * [21] Uri Katz, Mor Geva, and Jonathan Berant.  Inferring implicit relations in complex questions with language models.  In Findings of the Association for Computational Linguistics: EMNLP 2022, pages 2548–2566, 2022.
  * [22] Seyed Mehran Kazemi, Najoung Kim, Deepti Bhatia, Xin Xu, and Deepak Ramachandran.  Lambada: Backward chaining for automated reasoning in natural language.  In ACL, 2023.
  * [23] Tushar Khot, Harsh Trivedi, Matthew Finlayson, Yao Fu, Kyle Richardson, Peter Clark, and Ashish Sabharwal.  Decomposed prompting: A modular approach for solving complex tasks.  In The Eleventh International Conference on Learning Representations, 2023.
  * [24] Najoung Kim and Sebastian Schuster.  Entity tracking in language models.  arXiv preprint arXiv:2305.02363, 2023.
  * [25] Brian Lester, Rami Al-Rfou, and Noah Constant.  The power of scale for parameter-efficient prompt tuning.  arXiv preprint arXiv:2104.08691, 2021.
  * [26] Aman Madaan, Niket Tandon, Dheeraj Rajagopal, Peter Clark, Yiming Yang, and Eduard Hovy.  Think about it! improving defeasible reasoning by first modeling the question scenario.  arXiv preprint arXiv:2110.12349, 2021.
  * [27] Michael J Maher, Ilias Tachmazidis, Grigoris Antoniou, Stephen Wade, and Long Cheng.  Rethinking defeasible reasoning: A scalable approach.  Theory and Practice of Logic Programming, 20(4):552–586, 2020.
  * [28] John McCarthy.  Programs with common sense.  In Proceedings of the Teddington Conference on the Mechanization of Thought Processes, pages 75–91, London, 1959. Her Majesty’s Stationary Office.
  * [29] Maxwell Nye, Anders Johan Andreassen, Guy Gur-Ari, Henryk Michalewski, Jacob Austin, David Bieber, David Dohan, Aitor Lewkowycz, Maarten Bosma, David Luan, Charles Sutton, and Augustus Odena.  Show your work: Scratchpads for intermediate computation with language models.  In Deep Learning for Code Workshop, 2022.
  * [30] Liangming Pan, Alon Albalak, Xinyi Wang, and William Yang Wang.  Logic-lm: Empowering large language models with symbolic solvers for faithful logical reasoning.  arXiv preprint arXiv:2305.12295, 2023.
  * [31] John L Pollock.  Defeasible reasoning.  Cognitive science, 11(4):481–518, 1987.
  * [32] David Poole.  A logical framework for default reasoning.  Artificial intelligence, 36(1):27–47, 1988.
  * [33] Shuofei Qiao, Yixin Ou, Ningyu Zhang, Xiang Chen, Yunzhi Yao, Shumin Deng, Chuanqi Tan, Fei Huang, and Huajun Chen.  Reasoning with language model prompting: A survey.  arXiv preprint arXiv:2212.09597, 2022.
  * [34] Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu.  Exploring the limits of transfer learning with a unified text-to-text transformer.  The Journal of Machine Learning Research, 21(1):5485–5551, 2020\.
  * [35] Raymond Reiter.  Nonmonotonic reasoning.  In Exploring artificial intelligence, pages 439–481. Elsevier, 1988\.
  * [36] Adam Roberts, Hyung Won Chung, Anselm Levskaya, Gaurav Mishra, James Bradbury, Daniel Andor, Sharan Narang, Brian Lester, Colin Gaffney, Afroz Mohiuddin, Curtis Hawthorne, Aitor Lewkowycz, Alex Salcianu, Marc van Zee, Jacob Austin, Sebastian Goodman, Livio Baldini Soares, Haitang Hu, Sasha Tsvyashchenko, Aakanksha Chowdhery, Jasmijn Bastings, Jannis Bulian, Xavier Garcia, Jianmo Ni, Andrew Chen, Kathleen Kenealy, Jonathan H. Clark, Stephan Lee, Dan Garrette, James Lee-Thorp, Colin Raffel, Noam Shazeer, Marvin Ritter, Maarten Bosma, Alexandre Passos, Jeremy Maitin-Shepard, Noah Fiedel, Mark Omernick, Brennan Saeta, Ryan Sepassi, Alexander Spiridonov, Joshua Newlan, and Andrea Gesmundo.  Scaling up models and data with t5x and seqio.  arXiv preprint arXiv:2203.17189, 2022.
  * [37] Rachel Rudinger, Vered Shwartz, Jena D Hwang, Chandra Bhagavatula, Maxwell Forbes, Ronan Le Bras, Noah A Smith, and Yejin Choi.  Thinking like a skeptic: Defeasible inference in natural language.  In Findings of the Association for Computational Linguistics: EMNLP 2020, pages 4661–4675, 2020.
  * [38] Mohammed Saeed, Naser Ahmadi, Preslav Nakov, and Paolo Papotti.  RuleBERT: Teaching soft rules to pre-trained language models.  In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 1460–1476, Online and Punta Cana, Dominican Republic, November 2021. Association for Computational Linguistics.
  * [39] Abulhair Saparov and He He.  Language models are greedy reasoners: A systematic formal analysis of chain-of-thought.  In The Eleventh International Conference on Learning Representations, 2023.
  * [40] Abulhair Saparov, Richard Yuanzhe Pang, Vishakh Padmakumar, Nitish Joshi, Seyed Mehran Kazemi, Najoung Kim, and He He.  Testing the general deductive reasoning capacity of large language models using ood examples.  arxiv preprint arXiv:2305.15269, 2023.
  * [41] Giovanni Sartor.  Defeasibility in legal reasoning.  Springer, 1995.
  * [42] J.R. Shoenfield.  Mathematical Logic.  Taylor & Francis, 2001.
  * [43] Koustuv Sinha, Shagun Sodhani, Jin Dong, Joelle Pineau, and William L Hamilton.  Clutrr: A diagnostic benchmark for inductive reasoning from text.  arXiv preprint arXiv:1908.06177, 2019.
  * [44] Zayne Sprague, Kaj Bostrom, Swarat Chaudhuri, and Greg Durrett.  Natural language deduction with incomplete information.  In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 8230–8258, Abu Dhabi, United Arab Emirates, December 2022. Association for Computational Linguistics.
  * [45] Haitian Sun, William W Cohen, and Ruslan Salakhutdinov.  Conditionalqa: A complex reading comprehension dataset with conditional answers.  arXiv preprint arXiv:2110.06884, 2021.
  * [46] Oyvind Tafjord, Bhavana Dalvi, and Peter Clark.  ProofWriter: Generating implications, proofs, and abductive statements over natural language.  In Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021, pages 3621–3634, Online, August 2021. Association for Computational Linguistics.
  * [47] Alon Talmor, Jonathan Herzig, Nicholas Lourie, and Jonathan Berant.  Commonsenseqa: A question answering challenge targeting commonsense knowledge.  arXiv preprint arXiv:1811.00937, 2018.
  * [48] Alon Talmor, Oyvind Tafjord, Peter Clark, Yoav Goldberg, and Jonathan Berant.  Leap-of-thought: Teaching pre-trained models to systematically reason over implicit knowledge.  Advances in Neural Information Processing Systems, 33:20227–20237, 2020.
  * [49] Boshi Wang, Xiang Deng, and Huan Sun.  Iteratively prompt pre-trained language models for chain of thought.  In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 2714–2730, Abu Dhabi, United Arab Emirates, December 2022. Association for Computational Linguistics.
  * [50] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed Chi, Quoc V. Le, and Denny Zhou.  Chain-of-thought prompting elicits reasoning in large language models.  In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 24824–24837. Curran Associates, Inc., 2022.
  * [51] Jason Weston, Antoine Bordes, Sumit Chopra, Alexander M Rush, Bart Van Merriënboer, Armand Joulin, and Tomas Mikolov.  Towards ai-complete question answering: A set of prerequisite toy tasks.  arXiv preprint arXiv:1502.05698, 2015.
  * [52] Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L Griffiths, Yuan Cao, and Karthik Narasimhan.  Tree of thoughts: Deliberate problem solving with large language models.  arXiv preprint arXiv:2305.10601, 2023.
  * [53] Anbang Ye, Christopher Cui, Taiwei Shi, and Mark O Riedl.  Neural story planning.  arXiv preprint arXiv:2212.08718, 2022.
  * [54] Fei Yu, Hongbo Zhang, and Benyou Wang.  Nature language reasoning, a survey.  arXiv preprint arXiv:2303.14725, 2023.
  * [55] Eric Zelikman, Yuhuai Wu, Jesse Mu, and Noah Goodman.  STaR: Bootstrapping reasoning with reasoning.  In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 15476–15488. Curran Associates, Inc., 2022.
  * [56] Hanlin Zhang, Ziyang Li, Jiani Huang, Mayur Naik, and Eric Xing.  Improved logical reasoning of language models via differentiable symbolic programming.  In First Workshop on Pre-training: Perspectives, Pitfalls, and Paths Forward at ICML 2022, 2022.
  * [57] Honghua Zhang, Liunian Harold Li, Tao Meng, Kai-Wei Chang, and Guy Van den Broeck.  On the paradox of learning to reason from data.  arXiv:2205.11502, 2022.
  * [58] Wanjun Zhong, Siyuan Wang, Duyu Tang, Zenan Xu, Daya Guo, Jiahai Wang, Jian Yin, Ming Zhou, and Nan Duan.  AR-LSAT: Investigating analytical reasoning of text.  arXiv preprint arXiv:2104.06598, 2021.

Figure 10:  The model performances on various depths of a binary version of
the BoardgameQA dataset.

##  Appendix A More Experimental Results and Analysis

Binary Classification: It was observed in [22] that reasoning with _unknown_
labels is particularly challenging for few-shot LMs, because providing a
natural chain-of-thought for unknown is difficult. To measure if the poor
performance is merely due to the existence of examples with _unknown_ label or
due to conflict resolution being difficult for these models, we also created a
binary version of the dataset for depths 1, 2, and 3 where only examples with
_proved_ and _disproved_ labels are included.333In this case, we set
$p_{\textit{Conf}}=1.0$ for the first call we make to Algorithm 16; Otherwise,
the dataset will have a spurious correlation that can be exploited without
doing any reasoning. The results are reported in Figure 10. We overall see
similar patterns as the binary case, except for some improvements for the T5
model on depth 2.

Examples of Model Failures: To showcase some of the reasons why models
struggle with the BoardgameQA dataset, in Figures 12–21, we provide examples
where the model generated wrong proofs. Some of the dominant error cases
(showcased in the examples) include: 1- hallucinating or misunderstanding
conflicts and preferences, 2- not being able to correctly fill in the
incomplete information, 3- misunderstanding logical rules, 4- failing to prove
both elements in a conjunction, 5- getting distracted by distracting facts and
rules and going on a wrong proof path, and 6- being unfaithful to the provided
facts and rules and changing them so a proof can be found in the case where no
proof exists.

(a) Finetuned w/o proofs (BERT Large) (b) Finetuned w/o proofs (BERT Large)
(c) Finetuned w/o proofs (BERT Large)

(d) Finetuned w/ proofs (T5 XXL) (e) Finetuned w/ proofs (T5 XXL) (f)
Finetuned w/ proofs (T5 XXL)

(g) Prompt-tuned w/ CoT (PaLM 62B) (h) Prompt-tuned w/ CoT (PaLM 62B) (i)
Prompt-tuned w/ CoT (PaLM 62B)

(j) Fewshot w/ CoT (PaLM 540B) (k) Fewshot w/ CoT (PaLM 540B) (l) Fewshot w/
CoT (PaLM 540B)

Figure 11:  Confusion matrices for various models on the BoardgameQA dataset.

Confusion Matrices: The confusion matrices for the model predictions with
respect to the golden labels on the BoardgameQA dataset is provided in Figure
11 for various depths. One interesting observation is that for models tuned
with proofs, while the model perform well at predicting unknown labels in
lower depths, in higher depths they tend to generate proofs (with proved or
disproved labels) even when the label is unknown (e.g., for examples with
label unknown in depth 1 the prompt-tuned model predicts unknown for 268
instances, while in depth 2 it predicts unknown only for 2 instances). This
may be because when the search space for a proof increases, LMs cannot verify
all possible solutions and decide that the label is unknown. Instead, they
start a path in the hopes that it ends in a proof.

Figure 12:  An example of a wrong proof generated by PaLM 540B (fewshot) where
the error is due to misunderstanding a logical rule (given a fact $f$ and a
rule $f^{\prime}\rightarrow f$ the model concludes that $f^{\prime}$ must be
true.  Figure 13:  An example of a wrong proof generated by PaLM 62B (prompt-
tuned) where the error is due to assuming an antecedent of a high priority
rule cannot be proved, whereas it can indeed be proved.  Figure 14:  An
example of a wrong proof generated by PaLM 62B (prompt-tuned) where the error
is due to filling the missing information incorrectly.  Figure 15:  An example
of a wrong proof (but correct label) generated by PaLM 540B (fewshot) where
the error is due to 1- failing to prove one element of the conjunction and
also identifying a non-existence conflict between two rules.  Figure 16:  An
example of a wrong proof generated by PaLM 540B (fewshot) where the error is
due to 1- mistaking a football with a basketball, and 2- not being able to
fill in the incomplete information by realizing that a ball with a radius of
29 inches does not fit in a 26.3 x 25.6 x 24.2 inches box.  Figure 17:  An
example of a wrong proof generated by PaLM 540B (fewshot) where the error is
due to starting with a distracting fact that took the proof on a wrong path
(the correct proof is to first use the fact _The woodpecker swears to the
duck_ and Rule7 to conclude that _The woodpecker leaves the houses occupied by
the dragon_ , and then use Rule5 to conclude that _The vampire does not disarm
the bulldog_.  Figure 18:  An example of a wrong proof generated by PaLM 540B
(fewshot) where the error is due to misunderstanding a preference.  Figure 19:
An example of a wrong proof generated by T5 where the error is due to
hallucinating facts and rules.  Figure 20:  An example of a wrong proof
generated by T5 where the the model got distracted and ended up on a wrong
proof path.  Figure 21:  An example of a wrong proof generated by PaLM 540B
(fewshot) where the error is due to changing a rule in such a way that a proof
can be found, when a proof does not exist.  Figure 22:  A sample of theory and
question generation from Algorithm 16. Initially, the question has been
selected to be _(dog, attack, cat)_. The input depth $D=1$ indicates that a
theory with one hop of reasoning should be generated. Then a fact _(dog,
unite, lion)_ and a rule _R1: (X, unite, lion) $\Rightarrow$ (X, attack, cat)_
have been generated. Notice that the combination of the fact and the rule
conclude _(dog, attack, cat)_. Next we randomly decide if a conflict should be
generated. The decision is yes, so we generate another fact _(dog, respect,
cat)_ and rule _(dog, respect, cat) $\Rightarrow$ !(dog, attack, cat)_. Notice
that the two rules have contradictory conclusions now. We next decide randomly
the type of the conflict, and Type2 is selected in this case. Therefore, we
add _R2 > R1_ to our preferences, remove one of the facts generated for the
conflicting rule, and make recursive calls for the remaining facts, which is
only _(dog, unite, lion)_. This call is made with $D=0$, therefore the
stopping criterion triggers and we add _(dog, unite, lion)_ to our set of
facts.

##  Appendix B Experimental Details

We conducted our experiments on v3 TPUs for all the models, except for the
540B models where we used v4 TPUs due to their larger size. All the
experiments were done using the T5X framework [36] available at
https://github.com/google-research/t5x.

For the fewshot experiments, to ensure the demonstrations and the question fit
in the prompt, due to the large size of the examples in BoardgameQA, we only
included one example per label as demonstration (i.e. 3 examples one with
label proved, one with disproved, and one with unknown in the case of 3-way
classification datasets). For each example in the test set, we selected the
demonstrations randomly from the training set, while ensuring that they
contain both types of conflict resolution. For the prompt-tuning experiments,
we used a prompt-size of $100$ in all experiments, as it worked best in the
experiments of [25]. We allowed a maximum of 50K training steps with a batch
size of $8$, a learning rate of $0.1$, and a weight decay rate of $0.0001$.
For the T5 experiments, we also set the batch size to $8$ but set the learning
rate to $0.001$ and allowed 50K epochs (since it required more time to
converge). For BERT experiments, we set the batch size to $16$, learning rate
to $4.6e-5$, and ran the training for $20$ epochs. In all experiments
involving turning, we reported the results for the epoch that achieved best
validation accuracy.

Train entities |  cat, dog, pig, parrot, eagle, squirrel, penguin, lion, tiger, donkey, leopard, cheetah, grizzly bear, polar bear, sun bear, panda bear, black bear, turtle, crocodile, elephant, panther, cow, rabbit, hare, buffalo, baboon, sheep, whale, jellyfish, carp, goldfish, viperfish, starfish, catfish, oscar, zander, sea bass, swordfish, salmon, halibut, blobfish, doctorfish, tilapia, kangaroo, octopus, phoenix, aardvark, amberjack, eel, hummingbird, canary, hippopotamus, snail, caterpillar, mosquito, bat, ferret, gecko, kudu, moose, cockroach, cricket, grasshopper, meerkat, spider, lobster, squid, puffin, raven, kiwi, koala, wolverine
---|---
Test entities |  akita, bear, camel, coyote, snake, monkey, leopard, fish, ostrich, pigeon, dolphin, frog, goat, goose, wolf, gorilla, beaver, lizard, flamingo, swan, elk, duck, reindeer, bison, shark, mouse, owl, llama, cobra, zebra, otter, crab, peafowl, rhino, dinosaur, dove, badger, chinchilla, cougar, crow, seal, worm, ant, bee, butterfly, dragonfly, dragon, gadwall, mule, liger, german shepherd, bulldog, husky, poodle, chihuahua, dachshund, basenji, dalmatian, mermaid, seahorse, fangtooth, dugong, walrus, vampire, stork, swallow, songbird, woodpecker, starling, mannikin, pelikan, beetle, finch
Train predicates |  owe money to, give a magnifier to, learn the basics of resource management from, know the defensive plans of, show all her cards to, prepare armor for, sing a victory song for, need support from, respect, raise a peace flag for, become, an enemy of, roll the dice for, hold the same number of points as, offer a job to, wink at, steal five points from, knock down the fortress of, burn the warehouse of, eat the food of, attack the green fields whose owner is, proceed to the spot that is right after the spot of, remove one of the pieces of
Test predicates |  tear down the castle that belongs to, bring an oil tank for, reveal a secret to, enjoy the company of, neglect, want to see, swear to, refuse to help, manage to convince, call, stop the victory of, dance with, shout at, smile at, pay money to, unite with, hug, destroy the wall constructed by, create one castle for, disarm, acquire a photograph of, borrow one of the weapons of, fall on a square of, suspect the truthfulness of, invest in the company whose owner is, leave the houses occupied by, hide the cards that she has from, swim in the pool next to the house of, negotiate a deal with, trade one of its pieces with, build a power plant near the green fields of, take over the emperor of, capture the king of, surrender to
Train templates (sampled) |  If something [A] the [B], then it does not [C] the [D]. If at least one animal [A] the [B], then the [C] [D] the [E]. For the [A], if the belief is that the [B] does not [C] the [A] and the [D] does not [E] the [A], then you can add "the [A] does not [F] the [G]" to your conclusions.
Test templates (sampled) |  In order to conclude that the [A] does not [B] the [C], two pieces of evidence are required: firstly that the [D] will not [E] the [A] and secondly the [F] [G] the [A].’ There exists an animal which [A] the [B]? Then, the [C] definitely does not [D] the [F]. From observing that one animal [A] the [B], one can conclude that it also [C] the [D], undoubtedly.

Table 3:  Categories, descriptions, and examples of incomplete information in
BoardgameQA. For lexical entailment, world knowledge, event times, and
affordance, a list of examples is written manually from which the sampling
procedure can select. In the other cases, examples are generated
automatically.

##  Appendix C BoardgameQA Details

Here, we provide more in depth details about the generation and properties of
the BoardgameQA dataset. A sample of theory and question generation from
Algorithm 16 is provided in Figure 22.

###  C.1 Consistency of the Dataset

A defeasible theory is called _consistent_ if whenever a conflict arises, the
preferences can be used to resolve the conflict. In BoardgameQA, we aim to
produce consistent theories. To avoid inconsistencies and loops, each time we
call the function in Algorithm 16, we only allow it to sample from the
entities that have not been used in other rules and (sub-)questions. As an
example, if we have a rule such as $a\wedge b\Rightarrow c$, then when we call
the algorithm for $a$ and $b$ recursively, we use separate entities in the
facts and rules produced for the sub-branch of $a$ and for the sub-branch of
$b$. This way, we ensure that when we derive new facts in the sub-branch of
$a$, it does not defeat some of the derivations in the sub-branch of $b$ (and
the derivations in the later stages of the proof do not defeat the earlier
derivations). That is because the the set of facts used in the rule bodies are
for separate entities, and are therefore disjoint. We also apply defeasible
reasoning on the final logical theory to ensure that the question can be
derived from the theory.

###  C.2 Incomplete Information

Here, we provide more information about the nature and type of incomplete
information in BoardgameQA.

  * •

Age: We first generate a positive integer $x$ corresponding to the age of one
of the players expressed in days. Then we decide if we want to use a _more
than_ or _less than_ relationship. In the case of the former, we next generate
another integer $y<x$ and in the case of the latter $y>x$. Then, we randomly
decide a target unit (days, weeks, months, or years) for each integer and
convert them to that unit. Let $x^{\prime}$ and $y^{\prime}$ represent the
obtained values measured with the new units. Then we add a fact _[PLAYER] is
$x^{\prime}$ [unit] old_ and a rule _if the [PLAYER] is [more than/less than]
$y^{\prime}$ [unit] old then …_. The model has to be able to convert units of
time and then compare them.

  * •

Affordance: We manually wrote object properties/affordances, and a list of
items that have those properties. Examples of properties include _sharp_ ,
_drink_ , and _music_ and examples of objects for each of these properties
include _knife_ , _cappuccino_ , and _flute_ respectively. The facts are of
the form _The [PLAYER] has a [OBJECT]_ and the rules are of the form _If the
[PLAYER] has [AN OBJECT WITH PROPERTY] then …_. The model has to know about
the object properties to connect the facts and the rules.

  * •

Colors: We first identify groups of colors based on some property. This
includes _being a primary color_ , _being a rainbow color_ , and _being a
color in the flag of country X_. Then, we generate facts of the form _The
[PLAYER] has a card which is [COLOR] in color._ and rules of the form _If the
[PLAYER] has a card whose color is [COLOR PROPERTY] then …_. The model has to
have information about colors to connect the facts and the rules.

  * •

Money: We first generate a positive integer $x$ corresponding to the amount of
money a player has, then we randomly decide if we want the comparison to be
between two or three players. We also decide if we want to use a _more than_
or _less than_ relation. If the comparison is between two players and _more
than_ is used, then we generate another integer $y<x$ and if less than is used
then $y>x$; if the comparison is between three players and _more than_ is used
then we generate $y,z$ such that $y+z<x$, and if _less than_ is used then
$y+z>x$. We then generate facts of the form _The [PLAYER i] has x dollars._
and rules of the form _If [PLAYER i] has [more than/less than] than [PLAYER j]
and [PLAYER k] combined, then …_. The model has to do a summation and decide
which quantity is more or less.

  * •

Textual Entailment: We manually write multiple pairs of sentences where one
implies the other. Examples include _(assassinated the mayor, killed the
mayor)_ , _(struggles to find food, has difficulty to find food)_ , and
_(purchased a luxury aircraft, owns a luxury aircraft)_. The first element of
the pair is used in the fact and the second element in the body of a rule. The
model has to identify the entailment.

  * •

Places: We manually write a list of cities and the countries they are located
in. The city names are used in the facts (_The [PLAYER] is in [CITY] right
now._) and the countries are used in the rule bodies (_If the [PLAYER] is in
[COUNTRY] right now, then …_. The model has to know which city is in which
country.

  * •

Names: We assign a name (from a list of manually written names) to two of the
players and then write rules in the form of _If [PLAYER i] has a name that
starts with the same letter as [PLAYER 2], then … ._

  * •

Jobs: We manually write a list of pairs of jobs and the industry they belong
to. Examples include _(nurse, healthcare), (high school teacher, education),_
and _(sales manager, marketing)_. We use the job in the fact and the industry
in the rule body. The model has to know which job is part of which industry.

  * •

Volume: The facts mention that one of the players has an object (a notebook or
a ball) and give the dimensions of the object (the height and width for
notebook and the radius or diameter for the ball). The rule body asks whether
the object fit in a box with some given dimensions. The model has to
understand how 3D objects fit inside each other to be able to connect the fact
to the rule.

  * •

Events: We manually write a list of world events and the year when they
occurred. Examples include _(world war 1 started, 1914), (the first man landed
on moon, 1969)_ and _(Obama’s presidency started, 2009)_. Then we write facts
of the form _The [PLAYER] is watching a movie from [YEAR]_ and rules of the
form _If the [PLAYER] is watching a movie that was released [before/after]
[EVENT], then …_. The model has to know the time for major world events to be
able to connect the fact and the rule.

  * •

Friends: We first generate a positive integer $x$ corresponding to the number
of friends a player has. Then, we either generate a fact such as _The [PLAYER]
has $x$ friends_ or _The [PLAYER] has $x_{1}$ friends that are [ADJECTIVE] and
$x_{2}$ that are not_ where $x_{1}+x_{2}=x$. Then we decide if we want to use
a _more than_ or _less than_ relation. In the former case, we generate a
number $y<x$ and in the latter case $y>x$. Then we generate a rule of the form
_If the [PLAYER] has [more than/less than] $y$ friends, then …_.

Due to the nature of the extra knowledge and reasoning cases we consider, we
only add such cases at the last theory generation step of Algorithm 16 (i.e.
when $d=1$); Otherwise, we will need to follow generating sub-questions and
rules for questions such as _The dog is named Paco_ leading to unnatural rules
such as _“If … then the dog is named Paco_.

###  C.3 Entities, Predicates, and Templates

Table 3 presents the set of entities, predicates, and templates used in
BoardgameQA. To make the problem slightly more challenging in terms of
language complexity, we use different entities, predicates and templates in
the test set.

##  Appendix D Limitations and Negative Societal Impact

We identify the following limitations in our current work:

  * •

Our dataset, in its current form, focuses primarily on deductive logical
entailment, where the problem is a classification problem of whether a the
answer to a question is proved, disproved, or unknown based on a theory, and
the contradictions are also binary (i.e. one rule suggesting something is True
and the other suggesting it is False). Future work can extend BoardgameQA and
the analysis provided in this work to non-classification cases where 1- one
needs to apply defeasible logical reasoning to answer questions such as ‘‘Who
will be attacked by the dog?’’, and 2- one needs to resolve non-binary
conflicts where, e.g., one rule suggests ‘‘the dog is currently in Canada’’
and the other suggests ‘‘the dog is currently in Australia’’.

  * •

The current work assumes the initial state (facts) and the rules of the game
are small enough to be included in the prompt. Future work can extend
BoardgameQA and our analyses to the cases where not all the facts and rules
can be included in the prompt due to the limitation in the prompt length, and
retrieval is required to retrieve relevant facts and rules.

  * •

The current work is limited to deductive reasoning with the _modus ponens_
rule; future work can expand BoardgameQA and the analysis provided in this
paper to other types of rules such as proof by contradiction, disjunction
elimination, etc (see [40]).

  * •

In this work, we only studied one simple but highly practical solution to
conflict resolution (i.e. based on preferences). Future work can extend
BoardgameQA and the analysis in this paper to other natural types of conflict
resolution.

  * •

In some applications, preferences for conflict resolution have to be assigned
with great care and diligence to avoid unfair treatment of information
sources.