# Motion Memory: Leveraging Past Experiences to
Accelerate Future Motion Planning

Dibyendu Das, Yuanjie Lu, Erion Plaku, and Xuesu Xiao All authors are with the
Department of Computer Science, George Mason University {ddas6, ylu22, plaku,
<EMAIL_ADDRESS>
###### Abstract

When facing a new motion-planning problem, most motion planners solve it from
scratch, e.g., via sampling and exploration or starting optimization from a
straight-line path. However, most motion planners have to experience a variety
of planning problems throughout their lifetimes, which are yet to be leveraged
for future planning. In this paper, we present a simple but efficient method
called _Motion Memory_ , which allows different motion planners to accelerate
future planning using past experiences. Treating existing motion planners as
either a closed or open box, we present a variety of ways that Motion Memory
can contribute to reduce the planning time when facing a new planning problem.
We provide extensive experiment results with three different motion planners
on three classes of planning problems with over 30,000 problem instances and
show that planning speed can be significantly reduced by up to 89% with the
proposed Motion Memory technique and with increasing past planning
experiences.

##  I INTRODUCTION

Motion planning refers to the computational process of determining a sequence
of control inputs and actions to move a robot from a given start state to a
desired goal location while avoiding obstacles and observing system and
environment constraints. Motion planners are essential components for almost
all robotic applications [1], such as autonomous navigation [2], [3] and
manipulation [4], [5]. Therefore, quick, efficient, and optimal collision-free
motion planning is of paramount value to the entire robotics community.

Decades of research into motion planning have made significant progress and
are able to find motion-planning solutions for different robot platforms,
e.g., using Probabilistic Roadmaps (PRM) [6], Expansive Spaces algorithm [7],
and Rapidly-Exploring Random Trees (RRT) [8, 9] to move mobile robots or
manipulator arms. Nevertheless, these planners still face challenges in
complex real-world settings when real-time planning is required to assure fast
and reliable motion execution. Conventional motion planners need to plan from
scratch every time they encounter a new environment. This situation remains
true even when robots repeatedly face similar environments, where prior
experiences could be beneficial. Such repetitive planning introduces
unnecessary planning time and therefore limits the robot performance in real-
world environments where fast planning time can benefit the downstream tasks,
such as quickly moving through highly constrained obstacle spaces.

On the other hand, advances in machine learning have demonstrated that robots
are capable of learning emergent behaviors in a data-driven manner without
depending on heavily engineered attributes and heuristics. One particular
benefit of learning methods is the potential to continually improve with
increasing real deployment experiences [10], a capability that the classical
motion planners lack.

Figure 1: Traditional motion planners require significant amount of effort to
plan from scratch (left), such as large amount of samples or iterations
(illustrated in green); Motion Memory utilizes past planning experiences to
accelerate future planning when facing new planing problems (right).

Considering the limitations of classical motion planners and the potential of
learning from experiences, we present Motion Memory, a new paradigm based on
past planning experiences to guide traditional motion-planning methods when
facing new planning problems in order to reduce computational overhead and
therefore improve planning efficiency, as robots gather more and more
deployment experiences in the real world. Leveraging machine learning, Motion
Memory includes an experience augmentation technique and a representation
learning method that enable robots to reflect on prior planning experiences
for efficient future planning as shown in Fig. 1. To be specific, the
experience augmentation strategy automatically generates new planning
problems, for which past motion plans are (or are not) the solutions, and thus
provides Motion Memory with an extensive corpus of training data to generalize
to future planning problems. Motion Memory also utilizes representation
learning to enable autonomous robots to learn from augmented previous planning
experiences so that motion planners can identify, store, memorize, and
retrieve past planning experiences to facilitate motion planning in unseen
future environments. We present different ways to integrate Motion Memory with
three existing motion planners in three different categories of environments
both in a closed and open box manner to showcase the wide applicability and
generalizability of the technique. Our experiments demonstrate that Motion
Memory significantly reduces the motion-planning time in future unseen
environments by up to 89% with increasing deployment experiences.

##  II RELATED WORK

We review related work in classical motion planning and motion planning with
machine learning.

###  II-A Classical Motion Planning

Among classical motion planners, sampling-based approaches have shown to be
effective in solving challenging problems in complex, unstructured
environments [11, 12]. To account for dynamics [13, 14, 15, 16], sampling-
based motion planners often expand a motion tree whose branches correspond to
collision-free and dynamically-feasible trajectories. RRT[17, 18] and its
variants [19, 20, 21] rely on nearest neighbors to expand the motion tree
toward random samples. EST [22] relies on probability distributions to push
the tree toward less-explored areas. KPIECE [23] leverages a grid
decomposition and interior-exterior cells. GUST [24] introduces a discrete
layer based on a roadmap abstraction and relies on discrete search to expand
the motion tree along shortest paths in the roadmap. The work in [25] further
improves the motion-tree expansion to more aggressively follow the roadmap
paths, while also increasing the clearance from the obstacles. When presented
with a new planning problem, these approaches, however, have to plan from
scratch as they do not learn from prior experiences. This is precisely what
our Motion Memory framework addresses, enabling motion planners to leverage
prior solutions to similar planning problems.

###  II-B Learning Assisted Motion Planning

Throughout the years, the learning and planning communities have investigated
a variety of strategies for implementing the concept of machine learning for
efficient motion planning [26]. One intuitive approach is to apply machine
learning to generate high-quality valid samples in critical regions more
efficiently. Some methods produce valid samples in relevant areas by learning
the representation of the configuration space [27, 28, 29, 30], whereas other
methods train models to bias sampling over the critical regions of predicted
trajectories [31, 32, 33]. Another practical strategy is to minimize the
number of collisions [34, 35, 36] by learning Gaussian mixture models [37],
kernel perceptron [38], and graph neural network [39] to replace the
conventional collision checker or using a learned model to determine the order
of testing the nodes to identify valid paths [40, 41, 42].

Instead of learning a specific planning operation, other learning-based
pipelines learn from prior experience to solve motion planning problems in an
end-to-end manner. One strategy is to use similarity function to determine the
relevant information and retrieve it from a database in the form of paths [43,
44, 45] or sampling distributions [46, 47]. Another approach is to train a
deep neural network for efficient motion planning by using a database of past
solved problems. These methods take as input point-cloud representations of a
workspace and learn to encode this point-cloud into a latent space [48, 49,
50, 51]. Chamzas et al. [52] and Lien et al. [53] construct a similarity
function only over the workspace to extract suitable local representations of
planning problems [54]. Although these planners improve future motion planning
with experiences, these planners are usually designed as one standalone
planner and do not guarantee safety assurance, provable optimality, and good
explainability.

Informed by the aforementioned works, this paper proposes to hallucinate
planning problems by experience augmentation, construct a memory of past
planning experiences by classifying environments as similar or dissimilar
using representation learning, and retrieve relevant planning experience to
assist planners in future planning. Compared to all these specific techniques
developed for a specific motion planner in an ad hoc manner, our Motion Memory
is designed to be a universal technique that is applicable to any motion
planner and allows them to improve planning efficiency with increasing
planning experiences in a principled manner.

##  III Motion Memory

The key inspiration behind Motion Memory is that most motion planners will
encounter many different planning problems and produce different planning
solutions throughout their lifetimes. Motion Memory aims at reflecting on past
planning experiences by generating a set of planning problems that will make
the past planning solutions feasible/non-feasible. Then, utilizing
representation learning, Motion Memory learns a latent space which contains
efficient but also expressive information regarding the feasibility or
optimality of the existing problem solutions with respect to any new planning
problems in the future.

Figure 2: Motion Memory: Using Past Planning Experiences, Environment
Generation, and Representation Learning to Accelerate Future Planning.

###  III-A Problem Formulation

We formulate our motion planning problem in the state space (S-space) [55],
which represents the universe of all possible robot states. For the scope of
this paper, we use a 2D ground mobile robot as an example, but the general
paradigm of Motion Memory has the potential to scale up to high-dimensional
workspaces. A particular environment’s S-space can be decomposed as
$S=S_{\textrm{free}}\cup S_{\textrm{obst}}$, where
$S_{\textrm{free}}\in\mathcal{S}_{\textrm{free}}$ is the set of reachable
states and $S_{\textrm{obst}}\in\mathcal{S}_{\textrm{obst}}$ is the
unreachable set due to obstacles, nonholonomic constraints, velocity bounds,
etc. The robot state $s\in S$ is defined as in collision with obstacles when
$s\in S_{\textrm{obst}}$ and collision free otherwise ($s\in
S_{\textrm{free}}$). We denote the robot action to be $u\in\mathcal{U}$, e.g.,
commanded linear and angular velocity $\left(v,\omega\right)$, and define a
motion plan $P\in\mathcal{P}$ as a sequence of such actions and resulted
states $P=\\{u_{i},s_{i}~{}|~{}1\leq i\leq t\\}$. $\mathcal{P}$ is the space
of all motion plans. Notice that some motion planners may produce the resulted
states only, i.e., $P=\\{s_{i}~{}|~{}1\leq i\leq t\\}$ and leave the action
generation to a low-level controller. With the aforementioned notation, any
motion planner can be defined as a function $f(\cdot)$ that can be used to
produce motion plans,

$\begin{gathered}P=f(S~{}|~{}s_{\textrm{s}},s_{\textrm{g}}),\\\
\textrm{s.t.}\quad S=S_{\textrm{free}}\cup S_{\textrm{obst}},\quad
s_{\textrm{s}},s_{\textrm{g}},s_{i}\in S_{\textrm{free}},\forall s_{i}\in
P,\end{gathered}$ (1)

that result in the robot moving from the robot’s start state $s_{\textrm{s}}$
to a specified goal state $s_{\textrm{g}}$ without intersecting
$S_{\textrm{obst}}$, while observing robot motion constraints and optimizing a
particular cost function (e.g. distance, clearance, energy, and combinations
thereof).

A motion planner $f(\cdot)$ that has been used to solve different motion
planning problems in the past will have available a dataset
$\mathcal{D}=\\{d_{i}\\}_{i=1}^{N}=\\{S_{i},P_{i}\\}_{i=1}^{N}$, where $N$ is
the amount of currently available S-space (planning problem) and motion plan
(planning solution) pairs. Here, we assume that the start and goal states are
a constant distance away from each other and remain the same throughout all
planning problems by aligning them through rotation and translation of the
S-space. For example, $s_{\textrm{s}}$ can be always expressed as the origin
of the S-space, and $s_{\textrm{g}}$ as $(50,50)$. The goal of Motion Memory
is to utilize the existing $\mathcal{D}$ from past planning experiences to
accelerate future planning as shown in Fig. 2.

###  III-B Augmenting Past Experiences with Hallucination

Although $\mathcal{D}$ may contain a variety of planning problem and solution
pairs which have the potential to cover a new planning problem faced in the
future, the chance of encountering exactly the same problem is still very low,
considering the changing real world, sensory noise, and perceptual
imperfectness. Therefore, Motion Memory bootstraps on the existing dataset
$\mathcal{D}$ and augments it with hallucinated planning problems.

In contrast to the motion planning problem of finding the optimal motion plan
$P$ given a S-space $S$ in Eqn. (1), the hallucination problem is defined as
its inverse problem [56, 57, 58], i.e., given a motion plan $P$, what are the
S-spaces $S$ that assure this motion plan is optimal:

$\begin{gathered}\\{S_{i}\\}_{i=1}^{\infty}=f^{\dagger}(P~{}|~{}s_{\textrm{s}},s_{\textrm{g}}),\\\
\textrm{s.t.}\quad S=S_{\textrm{free}}\cup S_{\textrm{obst}},\quad
s_{\textrm{s}},s_{\textrm{g}},s_{i}\in S_{\textrm{free}},\forall s_{i}\in
P.\end{gathered}$ (2)

Notice that $f^{\dagger}(\cdot)$ is not strictly the inverse function of
$f(\cdot)$, because $f(\cdot)$ is non-injective, i.e., different S-spaces can
map to the same optimal plan. Therefore, instead of one S-space $S$, we need
to find the set of all S-spaces $\\{S_{i}\\}_{i=1}^{\infty}$, where the motion
plan $P$ is optimal. In most cases, such a set is an infinity set, except for
finitely discretized $S$.

Compared to the forward motion planning problem, which needs to run in real
time onboard computation-limited robot platforms, the inverse hallucination
problem in Eqn. (2) is much easier to solve. Researchers have proposed
different ways to approximate the infinity set $\\{S_{i}\\}_{i=1}^{\infty}$
using representative obstacle states, e.g., the maximal [56], a minimal [57],
or a learned distribution of [58] obstacle set in the S-space. With these
hallucination techniques, each member of the original pairwise motion planning
problem-solution dataset can be augmented from $d_{i}=\\{S_{i},P_{i}\\}$ to
$d_{i}^{*}=\\{\\{S_{i}^{j}\\}_{j=1}^{M_{i}},P_{i}\\}$, where $M_{i}$ is the
number of total generated planning problems for solution $i$. Thus, the
original dataset $\mathcal{D}$ is augmented to

$\mathcal{D}^{*}=\\{d_{i}^{*}\\}_{i=0}^{N}=\\{\\{S_{i}^{j}\\}_{j=1}^{M_{i}},P_{i}\\}_{i=0}^{N},$

in which each past planning solution $P_{i}$ is no longer only paired with one
original planning problem $S_{i}$, but a set of $M_{i}$ planning problems
$\\{S_{i}^{j}\\}_{j=1}^{M_{i}}$, for which $P_{i}$ is optimal. While
$P_{1},P_{2},...,P_{N}$ indicate $N$ existing motion plans, $P_{0}$
corresponds to an empty set: It is also possible to produce a set of motion
planning problems in which no existing motion planning solutions are feasible
or optimal, e.g., by adding obstacles to intersect with at least one robot
state in every existing motion plan, which will yield
$d_{0}^{*}=\\{\\{S_{0}^{j}\\}_{j=1}^{M_{0}},P_{0}\\}$, which is also included
in $\mathcal{D}^{*}$.

###  III-C Representation Learning

The augmented dataset $\mathcal{D}^{*}$ contains more planning problems for
each past planning solution, where the solution is feasible or optimal. Such
an augmented dataset is used to learn an efficient latent representation
space, which contains critical information regarding the feasibility or
optimality of each existing motion plan solution with respect to any motion
planning problem. Specifically, we adopt a triplet loss to enforce solution
invariance in the learned latent space so that all environments where solution
$P_{i}$ is feasible or optimal stay close to each other in the learned
embedding space. We generate triplet training data of anchor, similar, and
dissimilar planning problems $\langle S^{a},S^{s},S^{d}\rangle$ by sampling
$S^{a}$ and $S^{s}$ from the same set of planning problems where solution
$P_{i}$ is feasible or optimal, i.e., $\\{S_{i}^{j}\\}_{j=1}^{M_{i}}$, and
sample $S^{d}$ from other problem sets and assure $P_{i}$ is not feasible or
optimal for $S^{d}$. The planning problem (S-space) encoder
$e_{\theta}(\cdot)$ is then trained to minimize a triplet loss,

$\begin{split}&L(\langle S^{a},S^{s},S^{d}\rangle)=\\\
&\max(||e_{\theta}(S^{a})-e_{\theta}(S^{s})||-||e_{\theta}(S^{a})-e_{\theta}(S^{d})||+\delta,0),\end{split}$

with $\theta$ as the learnable parameters. The representation space will
contain data points from $N$ different latent clusters corresponding to the
$N$ existing motion plans $\\{P_{i}\\}_{i=0}^{N}$, including a cluster for
S-spaces where none of the $N$ plans are feasible or optimal. The cluster
centroids are computed as

$c_{i}=\frac{1}{M_{i}}\sum_{j=1}^{M_{i}}e_{\theta}(S_{i}^{j}).$

###  III-D Accelerating Future Planning

Using representation learning, the planning problem encoder is able to project
any new motion planning problem $S_{N+1}$ into the latent space, i.e.,
$l_{N+1}=e_{\theta}(S_{N+1})$. The existing motion plan associated with the
closest cluster centroid $P_{i^{*}}$ is likely the closest to the actual
motion planning solution of the problem $S_{n+1}$:

$i^{*}=\operatorname*{argmin}_{i}||e_{\theta}(S_{n+1})-c_{i}||.$

For existing motion planners, a motion plan $P_{i^{*}}$ potentially very close
to the actual solution can be used to accelerate planning in different ways.
For example, for sampling-based motion planners, the states in $P_{i^{*}}$ can
be used to bias sampling. For optimization-based approaches, both the actions
and states can be used as an initial guess. For motion planners treated as a
closed-box or an open-box, $P_{i^{*}}$ can be collision checked and be used as
the final solution if no collisions are detected, or utilize the closed-box
planner to only fix the plan segments which are in collision. In cases where
$P_{0}$ is the closest in the representation space, the motion planner can
start planning from scratch.

##  IV EXPERIMENTS

Figure 3: Different Planning Problem Classes : Curves (Left), Random (Middle),
Trap (Right) Figure 4: Different Motion Memory configurations improve three
planners in three classes of motion planning problems.

We present extensive experimental results by integrating our Motion Memory
technique with three different motion planners in both a closed-box and an
open-box manner to solve three different classes of motion-planning problems.
We present detailed results on the three planners’ performances with or
without Motion Memory for each problem class and for all three classes
combined into one. Furthermore, we present evidence demonstrating Motion
Memory allows motion planners’ planning efficiency to improve with increasing
past planning experiences. Finally, we conduct an ablation study to show that
the improved planning efficiency is not only due to more past planning
experiences, rather the Motion Memory technique itself is an indispensable
part.

###  IV-A Experimental Setup

Considering Motion Memory is designed to be a universal paradigm that is
agnostic to any underlying planner, we integrate Motion Memory with three
different motion planners, in both a closed-box and an open-box manner to show
its general applicability (denoted as “C” and “O” in all experiment results).
In the closed-box integration, we do not assume any access to or knowledge
about the underlying planner, and only interface Motion Memory with it using
the Motion Memory output as a potential solution after taking a new planning
problem as input. The open-box integration assumes access to and knowledge
about the underlying planner and depends on which components can be benefited
from the Motion Memory output, e.g., sampling distribution or initial
optimization guess. We describe the three underlying planners with their
closed-box and open-box Motion Memory integration as follows.

####  IV-A1 Baseline Planners

We experiment with different sampling-based motion planners. We first use RRT
[17, 18], one of the most popular methods. RRT uses random sampling and
nearest neighbors to guide the motion-tree expansion. We also use GUST [24],
which was specifically designed for motion-planning problems for vehicles with
dynamics. GUST introduces a discrete layer obtained by building a roadmap to
guide the motion-tree expansion. The roadmap is then used to induce a
partition of the motion-tree into groups based on their nearest roadmap node.
During the motion-tree expansion, priority is given to those groups associated
with short paths to the goal. Our third planner, which we refer to as Follow
[25], further improves GUST by more aggressively following the roadmap paths,
and dynamically adjusting the weights based on the progress made during the
motion-tree expansion.

##### Closed-box Versions of the Motion Planners

We first use these planners as black boxes in conjunction with the motion-
memory framework. Specifically, let $\zeta_{1},\ldots,\zeta_{k}$ be the top
$k$-predictions obtained by the motion-memory framework for a new motion-
planning problem. Each of these predictions corresponds to a dynamically-
feasible trajectory (retrieved from the database). The black-box version,
referred to as $\text{MP}_{\text{ClosedBox}}$, first checks these trajectories
$\zeta_{1},\ldots,\zeta_{k}$ in order for collisions. If some $\zeta_{i}$ is
not in collision, then $\text{MP}_{\text{ClosedBox}}$ returns $\zeta_{i}$ as
the solution. Otherwise, $\text{MP}_{\text{ClosedBox}}$ runs MP and returns
the solution (if any) found by MP.

##### Open-box Versions of the Motion Planners

We can better leverage the predictions made by the motion-memory framework by
looking inside the motion planners to better leverage the predictions. We
refer to these versions as $\text{MP}_{\text{OpenBox}}$.
$\text{MP}_{\text{OpenBox}}$, as the closed-box version, starts by checking if
any of the predicted trajectories $\zeta_{1},\ldots,\zeta_{k}$ is not in
collision. If all of them are in collision, then $\text{MP}_{\text{OpenBox}}$
runs a modified version of MP, as described below.

$\text{RRT}_{\text{OpenBox}}$ is obtained by changing the sampling
distribution from which the target is drawn. In the original RRT, the target
is sampled with probability $b_{\text{goal}}$ (usually $b_{\text{goal}}=0.1$)
from an area near the goal, and with probability $1-b_{\text{goal}}$ from the
entire state space. To leverage the predictions, we bias the sampling to be
along the predicted trajectories $\zeta_{1},\ldots,\zeta_{k}$. In particular,
let $b_{1},\ldots,b_{k},b_{\text{goal}},b_{\text{other}}$ such that
$b_{1}+\ldots+b_{k}+b_{\text{goal}}+b_{\text{other}}=1$. Generally,
$b_{1}>\ldots>b_{k}>b_{\text{goal}}>b_{\text{other}}$. We sample the target
with probability $b_{i}$ along $\zeta_{i}$, with probability $b_{\text{goal}}$
from near the goal, and with probability $b_{\text{other}}$ from the entire
state space. To generate a target along $\zeta_{i}$, we first select an
intermediate state in $\zeta_{i}$ and then sample around it. In this way,
$\text{RRT}_{\text{OpenBox}}$ biases the exploration toward the predicted
trajectories $\zeta_{1},\ldots,\zeta_{k}$.

$\text{GUST}_{\text{OpenBox}}$ differs from GUST only in the roadmap
construction. Specifically, while GUST generates a roadmap node by sampling
from the entire space, $\text{GUST}_{\text{OpenBox}}$ biases the sampling
along $\zeta_{1},\ldots,\zeta_{k}$. Specifically, to generate a roadmap node,
$\text{GUST}_{\text{OpenBox}}$ selects $\zeta_{i}$ with probability $b_{i}$,
selects a state $s$ uniformly at random from $\zeta_{i}$, and generates a
roadmap node by sampling near $s$. This results in a roadmap that captures the
connectivity along the predicted trajectories $\zeta_{1},\ldots,\zeta_{k}$.
Note that the roadmap is collision free, even if parts of
$\zeta_{1},\ldots,\zeta_{k}$ are in collision (since samples that result in
collision are discarded during the roadmap construction). This biased roadmap
construction allows for a more efficient expansion of the motion tree along
the predicted trajectories.

$\text{Follow}_{\text{OpenBox}}$ differs from Follow only in the roadmap
construction. In fact, $\text{Follow}_{\text{OpenBox}}$ uses the same
procedure as $\text{GUST}_{\text{OpenBox}}$ for constructing the roadmap.
$\text{Follow}_{\text{OpenBox}}$ then seeks to closely follow the shortest
roadmap path from the start to the goal by aggressively expanding the motion
tree to follow the nodes in the shortest path in succession.

####  IV-A2 Planning Problem Classes

Fig. 3 shows the three different classes of planning problems used in our
experiments, referred to as “Curves,” “Random,” and “Trap.” These problem
classes are parametrized, and the obstacles are procedurally generated.
Placement (location and orientation) and size of the obstacles are drawn from
a probability distribution so that numerous instances can be generated for
each problem class. An instance corresponds to a specific placement of the
obstacles, as shown in Fig. 3. For example, for the “Curves” problem class we
can vary the number of curves, number of segments per curve, separation among
segments, and so on. For the “Random” problem class, we can vary the density
of the obstacles as well as their shape and placement. For the “Trap” problem
class we can perturb the placement of the major obstacles and also of the
random obstacles spread throughout the environment.

####  IV-A3 Motion Memory Implementation

For each of the three motion planning problem classes, we assume our Motion
Memory has access to 100 planning problems and their corresponding motion
planning solutions as its past planning experiences, i.e.,
$\mathcal{D}=\\{d_{i}\\}_{i=1}^{100}=\\{S_{i},P_{i}\\}_{i=1}^{100}$. We
augment each data point in $\mathcal{D}$ with 999 more planning problems and
generate an augmented dataset
$\mathcal{D}^{*}=\\{d_{i}^{*}\\}_{i=1}^{100}=\\{\\{S_{i}^{j}\\}_{j=1}^{1000},P_{i}\\}_{i=1}^{100}$,
a dataset of 100,000 problems per class with 100 solutions, by slightly
rearranging obstacles close to the motion plan and randomly shuffling
obstacles in other places. For simplicity, we omit the set of problems where
no existing motion plan is a solution, i.e., $d_{0}^{*}$. To train the
planning problem encoder $e_{\theta}(\cdot)$, we use a Convolutional Neural
Network which takes motion planning problems as input and outputs a
30-dimensional latent space. For testing, we generate another 10,000 unseen
planning problems per class for the motion planners to solve.

We present experiments comparing closed-box and open-box integrations with
both top-one and top-five predictions for new problems. While top-five
predictions provide more information, they also incur additional computational
costs due to the need to process multiple predicted solutions.

###  IV-B Improvement for Different Planners and Problems

In Fig. 4, we show individual planning performance of the three underlying
planners (GUST, Follow, and RRT in row 1, 2, and 3 respectively) in the three
classes of motion planning problems (Curves, Random, and Trap in column 1, 2,
and 3 respectively). The fourth column is the results of a large Motion Memory
which does not distinguish among different motion planning problem classes,
with 300,000 training and 30,000 testing data points. In each figure, we show
the average planning time of default baseline planner without Motion Memory
(Planner_Baseline), the baseline planner assisted by Motion Memory in a
closed-box manner with top-one or top-five prediction(s) (MM_Planner_C_1 and
MM_Planner_C_5), and also assisted in an open-box manner (MM_Planner_O_1 and
MM_Planner_O_5).

The results show that Motion Memory can significantly reduce planning time
compared to all three default baseline planners, with the only exception of
using Motion Memory in a closed-box manner with Follow in the Trap
environment. In each of the 12 sub-figures in Fig. 4, we can observe
increasing performance from left to right. Using Motion Memory in a open-box
manner achieves similar or more improvement compared to using it in a closed-
box manner. In most cases, using the top-five Motion Memory predictions
outperforms using the top-one prediction, despite the potentially more
computation to process four extra predictions. Comparing the first three
columns, Motion Memory can achieve the most significant improvement for Curves
environments with GUST and Follow, while RRT enjoys the most Motion Memory
benefits in the Trap environments. In the last column where Motion Memory does
not distinguish among the three classes of planning problems, it also
outperforms all three baseline planners. Comparing the three rows, Motion
Memory is the most helpful for GUST, while the difference made by Motion
Memory to RRT is relatively smaller.

###  IV-C Continual Improvement with Increasing Experience

Figure 5: Improvement with Increasing Experiences.

Figure 6: Ablation Study: Random Path Selection.

We also study the performance improvement of Motion Memory with respect to
increasing past planning experiences. In Fig. 6, we show how the runtime of
the GUST planner to solve planning problems in Curves environments changes
when having access to more available motion plans. For each bar in Fig. 6, we
go through the entire Motion Memory pipeline, including environment generation
and representation learning, with a limited number of available motion plans
(20, 40, 60, 80, or 100). By integrating the Motion Memory model produced by
the corresponding amount of past experiences with GUST, we test the planner
performance on the 10,000 unseen test problems. With only 20 or 40 available
past motion plans, Motion Memory underperforms the baseline GUST, because a
limited set of available motion plans is not able to sufficiently cover the
variety of new planning problems. With increasing experiences, we see a
significant reduction in runtime and improvement in planning efficiency. Such
experiment results confirm our hypothesis that a motion planner can
continually improve when having access to increasing amount of past planning
experiences with the assistance of Motion Memory.

###  IV-D Ablation Study

Finally, to demonstrate the necessity of the Motion Memory technique, in
addition to the access to a large amount of past planning experiences, we
conduct an ablation study, in which we do not use the environment generation
and representation learning in Motion Memory to decide which past plan may be
most helpful for a future planning problem, but randomly pick a past plan to
assist the motion planner. Fig. 6 shows that randomly picking one or five past
plans to assist GUST in Curves environments in a open-box manner will increase
the planning time. Such results indicate it is necessary to use Motion Memory
to decide which past planning experience is useful to accelerate future
planning.

##  V DISCUSSION

We present Motion Memory, a universal technique which is agnostic to different
underlying motion planners but helps them to accelerate their future planning
runtime with past planning experiences. By augmenting past experiences and
using representation learning, Motion Memory avoids unnecessary and repetitive
replanning from scratch when facing similar future planning problems. We
demonstrate the efficacy of Motion Memory by integrating it with different
planners in a closed-box and open-box fashion, and solving different classes
of motion-planning problems more efficiently. One possible direction for
future research is to extend Motion Memory for manipulation planning, where
the robot interacts with the objects in the environment. Another direction is
to consider a heterogeneous team of robots and how Motion Memory can
facilitate planning for different types of robot, possibly adpating plans from
one robot type to another.

## References

  * [1] J. Canny, _The complexity of robot motion planning_. MIT press, 1988.
  * [2] Y. Kuwata, J. Teo, G. Fiore, S. Karaman, E. Frazzoli, and J. P. How, “Real-time motion planning with applications to autonomous urban driving,” _IEEE Transactions on control systems technology_ , vol. 17, no. 5, pp. 1105–1118, 2009.
  * [3] D. Fox, W. Burgard, and S. Thrun, “The dynamic window approach to collision avoidance,” _IEEE Robotics & Automation Magazine_, vol. 4, no. 1, pp. 23–33, 1997.
  * [4] S. Murray, W. Floyd-Jones, Y. Qi, D. J. Sorin, and G. D. Konidaris, “Robot motion planning on a chip.” in _Robotics: Science and Systems_ , vol. 6, 2016\.
  * [5] R. Volpe, “Rover functional autonomy development for the mars mobile science laboratory,” in _Proceedings of the 2003 IEEE Aerospace Conference_ , vol. 2, 2003, pp. 643–652.
  * [6] L. E. Kavraki, P. Svestka, J.-C. Latombe, and M. H. Overmars, “Probabilistic roadmaps for path planning in high-dimensional configuration spaces,” _IEEE transactions on Robotics and Automation_ , vol. 12, no. 4, pp. 566–580, 1996.
  * [7] D. Hsu, J.-C. Latombe, and R. Motwani, “Path planning in expansive configuration spaces,” in _Proceedings of international conference on robotics and automation_ , vol. 3. IEEE, 1997, pp. 2719–2726.
  * [8] S. LaValle, “Rapidly-exploring random trees: A new tool for path planning,” _Research Report 9811_ , 1998.
  * [9] S. Karaman and E. Frazzoli, “Sampling-based algorithms for optimal motion planning,” _The international journal of robotics research_ , vol. 30, no. 7, pp. 846–894, 2011.
  * [10] X. Xiao, B. Liu, G. Warnell, and P. Stone, “Motion planning and control for mobile robot navigation using machine learning: a survey,” _Autonomous Robots_ , vol. 46, no. 5, pp. 569–597, 2022.
  * [11] H. Choset, K. M. Lynch, S. Hutchinson, G. Kantor, W. Burgard, L. E. Kavraki, and S. Thrun, _Principles of Robot Motion: Theory, Algorithms, and Implementations_. MIT Press, 2005.
  * [12] S. M. LaValle, _Planning Algorithms_. Cambridge, MA: Cambridge University Press, 2006.
  * [13] X. Xiao, J. Biswas, and P. Stone, “Learning inverse kinodynamics for accurate high-speed off-road navigation on unstructured terrain,” _IEEE Robotics and Automation Letters_ , vol. 6, no. 3, pp. 6054–6060, 2021.
  * [14] H. Karnan, K. S. Sikand, P. Atreya, S. Rabiee, X. Xiao, G. Warnell, P. Stone, and J. Biswas, “Vi-ikd: High-speed accurate off-road navigation using learned visual-inertial inverse kinodynamics,” in _2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2022, pp. 3294–3301.
  * [15] P. Atreya, H. Karnan, K. S. Sikand, X. Xiao, S. Rabiee, and J. Biswas, “High-speed accurate robot control using learned forward kinodynamics and non-linear least squares optimization,” in _2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2022, pp. 11 789–11 795.
  * [16] A. Datar, C. Pan, and X. Xiao, “Learning to model and plan for wheeled mobility on vertically challenging terrain,” _arXiv preprint arXiv:2306.11611_ , 2023.
  * [17] S. M. LaValle and J. J. Kuffner, “Randomized kinodynamic planning,” _International Journal of Robotics Research_ , vol. 20, no. 5, pp. 378–400, 2001.
  * [18] S. M. LaValle, “Motion planning: The essentials,” _IEEE Robotics & Automation Magazine_, vol. 18, no. 1, pp. 79–89, 2011.
  * [19] W. Xinyu, L. Xiaojuan, G. Yong, S. Jiadong, and W. Rui, “Bidirectional potential guided RRT* for motion planning,” _IEEE Access_ , vol. 7, pp. 95 046–95 057, 2019.
  * [20] A. Shkolnik, M. Walter, and R. Tedrake, “Reachability-guided sampling for planning under differential constraints,” in _IEEE International Conference on Robotics and Automation_ , 2009, pp. 2859–2865.
  * [21] D. Devaurs, T. Simeon, and J. Cortés, “Enhancing the transition-based RRT to deal with complex cost spaces,” in _IEEE International Conference on Robotics and Automation_ , 2013, pp. 4120–4125.
  * [22] D. Hsu, J.-C. Latombe, and R. Motwani, “Path planning in expansive configuration spaces,” in _IEEE International Conference on Robotics and Automation_ , vol. 3, 1997, pp. 2719–2726.
  * [23] I. A. Şucan and L. E. Kavraki, “A sampling-based tree planner for systems with complex dynamics,” _IEEE Transactions on Robotics_ , vol. 28, no. 1, pp. 116–131, 2012.
  * [24] E. Plaku, “Region-guided and sampling-based tree search for motion planning with dynamics,” _IEEE Transactions on Robotics_ , vol. 31, pp. 723–735, 2015\.
  * [25] E. Plaku, E. Plaku, and P. Simari, “Clearance-driven motion planning for mobile robots with differential constraints,” _Robotica_ , vol. 36, pp. 971–993, 2018.
  * [26] T. McMahon, A. Sivaramakrishnan, E. Granados, K. E. Bekris _et al._ , “A survey on the integration of machine learning with sampling-based motion planning,” _Foundations and Trends® in Robotics_ , vol. 9, no. 4, pp. 266–327, 2022.
  * [27] G. S. Aoude, B. D. Luders, J. M. Joseph, N. Roy, and J. P. How, “Probabilistically safe motion planning to avoid dynamic obstacles with uncertain motion patterns,” _Autonomous Robots_ , vol. 35, pp. 51–76, 2013\.
  * [28] B. Burns and O. Brock, “Sampling-based motion planning using predictive models,” in _Proceedings of the 2005 IEEE international conference on robotics and automation_. IEEE, 2005, pp. 3120–3125.
  * [29] Z. Kingston, M. Moll, and L. E. Kavraki, “Exploring implicit spaces for constrained sampling-based planning,” _The International Journal of Robotics Research_ , vol. 38, no. 10-11, pp. 1151–1178, 2019.
  * [30] G. Sutanto, I. R. Fernández, P. Englert, R. K. Ramachandran, and G. Sukhatme, “Learning equality constraints for motion planning on manifolds,” in _Conference on Robot Learning_. PMLR, 2021, pp. 2292–2305.
  * [31] I. Baldwin and P. Newman, “Non-parametric learning for natural plan generation,” in _2010 IEEE/RSJ International Conference on Intelligent Robots and Systems_. IEEE, 2010, pp. 4311–4317.
  * [32] M. Zucker, J. Kuffner, and J. A. Bagnell, “Adaptive workspace biasing for sampling-based planners,” in _2008 IEEE International Conference on Robotics and Automation_. IEEE, 2008, pp. 3757–3762.
  * [33] B. Ichter, J. Harrison, and M. Pavone, “Learning sampling distributions for robot motion planning,” in _2018 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2018, pp. 7087–7094.
  * [34] K. Hauser, “Lazy collision checking in asymptotically-optimal motion planning,” in _2015 IEEE international conference on robotics and automation (ICRA)_. IEEE, 2015, pp. 2951–2957.
  * [35] A. Mandalika, S. Choudhury, O. Salzman, and S. Srinivasa, “Generalized lazy search for robot motion planning: Interleaving search and edge evaluation via event-based toggles,” in _Proceedings of the International Conference on Automated Planning and Scheduling_ , vol. 29, 2019, pp. 745–753.
  * [36] J. Bialkowski, M. Otte, S. Karaman, and E. Frazzoli, “Efficient collision checking in sampling-based motion planning via safety certificates,” _The International Journal of Robotics Research_ , vol. 35, no. 7, pp. 767–796, 2016.
  * [37] J. Huh and D. D. Lee, “Learning high-dimensional mixture models for fast collision detection in rapidly-exploring random trees,” in _2016 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2016, pp. 63–69.
  * [38] N. Das and M. Yip, “Learning-based proxy collision detection for robot motion planning applications,” _IEEE Transactions on Robotics_ , vol. 36, no. 4, pp. 1096–1114, 2020.
  * [39] C. Yu and S. Gao, “Reducing collision checking for sampling-based motion planning using graph neural networks,” _Advances in Neural Information Processing Systems_ , vol. 34, pp. 4274–4289, 2021.
  * [40] J. Pan, S. Chitta, and D. Manocha, “Faster sample-based motion planning using instance-based learning,” in _Algorithmic Foundations of Robotics X: Proceedings of the Tenth Workshop on the Algorithmic Foundations of Robotics_. Springer, 2013, pp. 381–396.
  * [41] M. Bhardwaj, S. Choudhury, B. Boots, and S. Srinivasa, “Leveraging experience in lazy search,” _Autonomous Robots_ , vol. 45, pp. 979–996, 2021.
  * [42] B. Hou, S. Choudhury, G. Lee, A. Mandalika, and S. S. Srinivasa, “Posterior sampling for anytime motion planning on graphs with expensive-to-evaluate edges,” in _2020 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2020, pp. 4266–4272.
  * [43] D. Berenson, P. Abbeel, and K. Goldberg, “A robot path planning framework that learns from experience,” in _2012 IEEE International Conference on Robotics and Automation_. IEEE, 2012, pp. 3671–3678.
  * [44] È. Pairet, C. Chamzas, Y. Petillot, and L. E. Kavraki, “Path planning for manipulation using experience-driven random trees,” _IEEE Robotics and Automation Letters_ , vol. 6, no. 2, pp. 3295–3302, 2021.
  * [45] D. Coleman, I. A. Şucan, M. Moll, K. Okada, and N. Correll, “Experience-based planning with sparse roadmap spanners,” in _2015 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2015, pp. 900–905.
  * [46] C. Chamzas, A. Shrivastava, and L. E. Kavraki, “Using local experiences for global motion planning,” in _2019 International Conference on Robotics and Automation (ICRA)_. IEEE, 2019, pp. 8606–8612.
  * [47] S. Finney, L. P. Kaelbling, and T. Lozano-Pérez, “Predicting partial paths from planning problem parameters.” in _Robotics: Science and Systems_. Citeseer, 2007.
  * [48] A. H. Qureshi, A. Simeonov, M. J. Bency, and M. C. Yip, “Motion planning networks,” in _2019 International Conference on Robotics and Automation (ICRA)_. IEEE, 2019, pp. 2118–2124.
  * [49] J. J. Johnson, L. Li, F. Liu, A. H. Qureshi, and M. C. Yip, “Dynamically constrained motion planning networks for non-holonomic robots,” in _2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2020, pp. 6937–6943.
  * [50] R. Strudel, R. G. Pinel, J. Carpentier, J.-P. Laumond, I. Laptev, and C. Schmid, “Learning obstacle representations for neural motion planning,” in _Conference on Robot Learning_. PMLR, 2021, pp. 355–364.
  * [51] A. H. Qureshi, J. Dong, A. Choe, and M. C. Yip, “Neural manipulation planning on constraint manifolds,” _IEEE Robotics and Automation Letters_ , vol. 5, no. 4, pp. 6089–6096, 2020.
  * [52] C. Chamzas, Z. Kingston, C. Quintero-Peña, A. Shrivastava, and L. E. Kavraki, “Learning sampling distributions using local 3d workspace decompositions for motion planning in high dimensions,” in _2021 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2021, pp. 1283–1289.
  * [53] J.-M. Lien and Y. Lu, “Planning motion in environments with similar obstacles.” in _Robotics: Science and systems_ , 2009.
  * [54] C. Chamzas, A. Cullen, A. Shrivastava, and L. E. Kavraki, “Learning to retrieve relevant experiences for motion planning,” in _2022 International Conference on Robotics and Automation (ICRA)_. IEEE, 2022, pp. 7233–7240.
  * [55] J.-C. Latombe, _Robot motion planning_. Springer Science & Business Media, 2012, vol. 124.
  * [56] X. Xiao, B. Liu, G. Warnell, and P. Stone, “Toward agile maneuvers in highly constrained spaces: Learning from hallucination,” _IEEE Robotics and Automation Letters_ , vol. 6, no. 2, pp. 1503–1510, 2021.
  * [57] X. Xiao, B. Liu, and P. Stone, “Agile robot navigation through hallucinated learning and sober deployment,” in _2021 IEEE international conference on robotics and automation (ICRA)_. IEEE, 2021, pp. 7316–7322.
  * [58] Z. Wang, X. Xiao, A. J. Nettekoven, K. Umasankar, A. Singh, S. Bommakanti, U. Topcu, and P. Stone, “From agile ground to aerial navigation: Learning from learned hallucination,” in _2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2021, pp. 148–153.


11institutetext: School of Informatics, The University of Edinburgh,
Edinburgh, UK

# Can Large Language Models put 2 and 2 together? Probing for Entailed
Arithmetical Relationships

Dagmara Panas  0009-0007-7805-2141 Sohan Seth  0000-0002-7464-4752 Vaishak
Belle  0000-0001-5573-8465

###### Abstract

Two major areas of interest in the era of Large Language Models regard
questions of what do LLMs _know_ , and if and how they may be able to _reason_
(or rather, approximately reason). Since to date these lines of work
progressed largely in parallel (with notable exceptions), we are interested in
investigating the intersection: probing for reasoning about the implicitly-
held knowledge. Suspecting the performance to be lacking in this area, we use
a very simple set-up of comparisons between cardinalities associated with
elements of various subjects (e.g. the number of legs a bird has versus the
number of wheels on a tricycle). We empirically demonstrate that although LLMs
make steady progress in knowledge acquisition and (pseudo)reasoning with each
new GPT release, their capabilities are limited to statistical inference only.
It is difficult to argue that pure statistical learning can cope with the
combinatorial explosion inherent in many commonsense reasoning tasks,
especially once arithmetical notions are involved. Further, we argue that
bigger is not always better and chasing purely statistical improvements is
flawed at the core, since it only exacerbates the dangerous conflation of the
production of correct answers with genuine reasoning ability.

###### Keywords:

Large Language Models Prompting Knowledge extraction Reasoning

##  1 Introduction

The introduction of the Transformer architecture [23], together with the
unprecedented abundance of data (in)untarily donated by the masses of social
media users and digital content producers, has brought about a fundamental
shift in Natural Language Processing, which had until then substantially
lagged behind Computer Vision. Although early forays into straightforward
network approaches to analysing textual data yielded a surprising success111As
well as a degree of controversy around the implicit biases in the data exposed
through vector algebra. with the introduction of _word embeddings_ [15],
arguably it was not until the release of GPT and its successors that questions
of knowledge, reasoning abilities, and even sentience [22] of computers have
become a mainstream topic of debate. Further additions of efficient fine-
tuning solutions, as well as code-less options such as in-context few-shot
learning or chain-of-thought (CoT) prompting techniques, have enabled these
tools to become incredibly useful personal assistants and further contributed
to the perception that we are approaching Artificial General Intelligence
(AGI) [4]. Juxtaposing the extremely convincing nature of LLMs and great
appetite for adoption in every area of society with at times spectacular
failure modes [18, 11] understandably elicits a host of safety, reliability
and trustworthiness concerns [6, 9]. Specifically, while it may often _seem_
that a model is a thinking rational agent, not only capable of carrying out a
conversation but also performing useful tasks [19] and a degree of logical
inference [17] or calculations [3], in reality it is simply performing
(data-)informed guesses. Perhaps the most stark illustration of this nature
comes from research into memorisation versus stability of acquired knowledge:
the first arc shows that an astonishing proportion of data examples can be
recovered from an LLM by simply feeding it part of the example [1, 24]; the
second arc on the other hand demonstrates that small perturbations in prompts
lead to a drastic drop in performance [13, 10].

While there is no doubt that LLMs and their statistically-informed guesses can
be of great assistance in many fault-tolerant domains, in areas such as
medicine, governance or finance the bar is higher than current capabilities
would allow. There are two ways to try and meet such reliability demands: more
data covering more bases [13, 7, 16]; or a Neuro-Symbolic (NeSy) approach, be
it through hybrid ‘enablement’ with external solvers [17] or via integrated
architectural solutions [2, 21]. We argue that the first path is doomed in the
long run, as it addresses the symptoms, not the underlying systemic flaw.
Although we are ultimately interested in more complex tasks such as
satisfiability checking, especially in hybrid languages such as satisfiability
modulo theories (SMT), here as a motivating example we carry out a quick and
straightforward empirical assessment at the intersection of knowledge
extraction [13] and arithmetic comparative reasoning [17].

We are interested specifically in finding out whether LLMs can perform one of
the most basic symbolic manipulations over entities recalled from memory. That
is, we probe for numerical adjectives that capture a comparison between
quantities, without providing these quantities but rather expecting the model
to rely on implicit knowledge; we refer to this as Entailed Arithmetic
Relationship probing, as we assume that the values are _entailed_ by the
textual description. Inspired by [13] we use the number of elements of a
subject (e.g. the number of legs a bird has, the number of wheels on a
tricycle), and for our ‘symbolic solver’ [17] we directly employ the python
interpreter, which allows us to circumvent the problem of parsing natural
language into symbolic formulae222As we turn to more complex arithmetic and
logical reasoning, using an SMT solver will be prudent, which we leave for
future work.. We use this simple approach rather than more sophisticated
symbolic tasks as, first, we expect sub-par performance, and, second, such a
set-up allows us to clearly and efficiently foreground our main argument:
producing correct answers is not synonymous with reasoning. We confirm our
suspicions, in that LLMs struggle with basic mathematical inequalities between
memorised or hallucinated facts, and that performance on pure string matching
surpasses taking into account fact correctness. We also find, similarly to
others, that the answers given by LLMs are unstable and depend on prompt
phrasing [11], and can be fairly clearly biased leading to concept
entanglement [13]. The entanglements manifest most prominently in areas of
knowledge with presumed lack of explicit data regarding the number 0, what we
refer to as the ‘null value problem’, and which is a form of a wider
phenomenon of people typically ‘not stating the obvious’ [5, 8].

##  2 Related work

There is a fast growing body of literature that addresses evaluating the
capabilities of LLMs across a whole spectrum of tasks, ranging from possessing
general commonsense knowledge to specialised domains (for a review we refer
the reader to [9]). In the area of knowledge extraction, of particular
relevance is the work of [13] which served as the inspiration for our data
creation strategy. There, the authors propose NumerSense, a human-verified
benchmark dataset consisting of masked sentences where the number or numeral
is obscured, and which can be used for probing or for fine-tuning language
models (probing and tuning portions are similarly constructed but from
disjoint knowledge bases). They go on to benchmark several models, including
BERT and RoBERTa-Large fine-tuned to a portion of the data, and demonstrate
surprisingly weak arithmetical knowledge of generally-pretrained models from
the BERT family as well as GPT-2. They further analyse the performance and
show instability (susceptibility to adversarial attacks) and entanglement of
concepts or object bias. An example that is also the namesake of their paper
is one of predicting birds to have 4 legs, presumably due to bias towards
4-legged animals and objects in the pretraining corpus. In our experiments we
add to that line of work by, first, examining the latest GPT-family models,
and second, extending to a situation where many of the true answers are
‘zero’.

From the reasoning side we take our inspiration from [17], which introduces
LogicLM, and which compares the performance of GPT-family models on 5 logical
reasoning tasks against a hybrid approach involving symbolic solvers. In the
latter, authors propose to use LLMs as merely parsers, and leverage in-context
learning to induce translation into appropriate formulations for the external
reasoning tools. The comparison of pure LLM reasoning versus the hybrid
approach comes out in favour of the symbolic approach, although we note not
uniformly so: for the simplest of the 5 logical tasks, both GPT-3.5-turbo as
well as GPT-4 reach better performance than the hybrid approach, with GPT-4
improving on the hybrid by 15%. We highlight this, as such a result might
sound encouraging for pushing the efforts in simply making LLMs larger and
trained on more of the edge cases. However, we want to stress that the ‘win’
over a symbolic solver is merely because GPT-4 failed in appropriate parsing
of the problem, not because it can reason better than a symbolic solver. We
take on a much simpler problem here, and we construct the queries for LLMs
from the underlying symbolic representation, so we do away with any issues of
parsing. We also differ in that we do not provide the predicates to reason
over, we merely refer to them and assume them to be part of LLMs’ knowledge
base.

Several other recent studies tackle the related problems of relational
inference [12], arithmetical reasoning [14] and causal inference [10, 14].
Similarly to ours, these are all empirical assessments of LLM performance, but
in the setting where the reasoning predicates are provided explicitly. We want
to also highlight that in the case of [10] the performance is sub-par without
a full fine-tuning first. Further, the authors point out that the fine-tuned
model is biased and unstable to input perturbations: a mere swapping of labels
on the query subjects results in diminished performance, indicating
memorisation of answers rather than learning of causal structures.

The two works most closely aligned to ours overall are the introduction of the
VerbPhysics challenge and dataset [5] and a further follow-up study of the
same problem by [8]. Both address the task of inferring entailed relationships
from textual data, and although there are several differences to our work we
feel they are our predecessors in spirit. In the first of these studies the
authors aim to supplement visual commonsense reasoning by leveraging word
embeddings. Since many physical relationships between objects may be
impossible to deduce from a 2-D visual input (e.g. weight), and explicit data
stating the obvious is rare (e.g. ‘a human weighs less than a house’), the
authors propose to mine the semantic knowledge captured in contextual
embeddings. Specifically, they pose the problem of inferring a physical
relationship as (joint) probabilistic graph inference over nodes of either
object pairs, or object-verb-object triplets, where the similarity of nodes is
informed by the semantic similarity captured by GloVe, one of the earliest
embeddings proposed. Intuitively, the idea is to use the fact that pairs of
similar objects are typically similarly related, and furthermore an action
verb tends to imply a particular physical relationship (e.g. ‘Joe entered the
house’ implies that Joe is smaller than the house, and a person is smaller
than a building etc). The authors then go on to demonstrate that the intuition
holds, and that text embeddings can be probabilistically mined for
relationships such as size, weight or speed. We note that although the paper
also introduces a crowd-sourced dataset, only 5% of it is used as seed
knowledge. In the following work of [8], the authors propose to simplify the
inference further, and train a single-layer fully-connected network with
embeddings of single words as input and relationship as output (again on only
5% of the VerbPhysics). They demonstrate improved performance on three
separate embeddings (GloVe, ELMo and BERT) as compared to the graph inference
approach, despite providing nominally less information. Both these works thus
point to the fact that embeddings are semantically rich enough to already
capture a lot of relational knowledge. In this sense, our work can be seen as
an extension and further simplification of these approaches. First, we also
part-manually part-combinatorially create a relational dataset within an area
of reporting bias; however our relation regards constitutive cardinalitites
rather than physical attributes such as weight or size. Second, we use even
richer representations of GPT-3.5-turbo and GPT-4, models that are larger in
parameter size, trained on more data, and with wider context windows. Lastly,
we do not impose a separate model for relational knowledge inference but
effectively use the LLM itself as the model, i.e., we leverage the few-shot
‘reasoning’ capabilities of the latest pre-trained architectures.

Finally, in the context of using LLMs as out-of-the-box reasoners, and
empirical expositions of their flaws, another related study that aligns with
our findings is that of [3]. In there the authors conduct a thorough
examination of several powerful LLMs across a range of logical reasoning and
arithmetical numeracy tasks. They employ CoT prompting as well as causal
interventions to infer the underlying causal reasoning graph of LLMs. What
emerges is that surprisingly often the chain of thought that the models are
supposed to follow appears to not be used in determining the final answer.
Further, while GPT-3.5 and GPT-4 appear to adhere to the CoT on some tasks, it
is only on the minority, and the implied reasoning graphs differ with task for
each model. Although we target implicit knowledge rather than providing
predicates, and we do not use CoT prompting, we arrive at very similar
conclusions: LLMs can not reason, they only fake it.

##  3 Methods: EAR probing

As we are interested in relational reasoning about implicit knowledge, we
separately probe the model for atomic facts relating to numbers, and
separately for relationships between the numbers entailed by (subject,
elements) pairs, as illustrated in the bottom-left panel of Fig. 1. This
allows us to (re-)examine numerical factual knowledge, as well as relational
knowledge and relational reasoning. The last one, in particular is our main
contribution: applying the ‘symbolic solver’ of the python interpreter to
check whether LLMs’ idea of arithmetic inequality is correct when the numbers
are not provided explicitly but rather assumed to be elicited by the query
(bottom-right panel of Fig. 1).

###  3.1 Data

Data is constructed by leveraging the very combinatorial explosion problem
that renders naturally produced text lacking with respect of negative
statements. First, a dictionary with 9 subjects and a defaultdict per subject
with varying number of constituent elements each (totalling 63) is manually
constructed (this was done by one of the authors and cross-checked by an
independent party). Since various subjects have a potentially overlapping but
essentially different sets of constituent parts, and a defaultdict allows us
to specify a default value for any missing key, we are thus able to generate
280 subject-elements pairs associated with an atomic numerical fact, e.g.
(sparrow, legs, 2) from explicitly input data and (sparrow, wheels, 0) from
the assumption of missingness (see upper-left panel of Fig. 1). Second, from
that base dictionary we then generate a grand total of 6003 quad-tuples of the
form (sparrow, wheels, tricycle, legs) by pairing subjects and possible parts
each of them possesses (or does not)333Note this number could be over 50%
higher if we included quad-tuples where both subjects do not contain the
queried element, but we exclude those.. These quad-tuples are then used to
populate a template natural language statement for probing the model. Each
quad-tuple is also associated with a ground truth numeral adjective relating
the atomic facts (either ‘less’, ‘same’ or ‘more’), which we obtain from our
‘symbolic solver’ i.e., a function that outputs one of these strings depending
on the relationship between the numbers from the atomic facts dictionary
(upper-right panel of Fig. 1).

Figure 1: (upper-left) Data is constructed as subject-element pairs with known
associated ground truth values from which many combinations of subject-
element-subject-element quad-tuples can be generated, assuming 0 for missing
parts. (upper-right) For each quad-tuple we can assign the ground truth
relationship string, since we know the atomic facts. (lower-left) From these
pairs and quad-tuples, prompts for numerical probing and entailed relationship
probing are generated by populating templates. (lower-right) To evaluate
_Entailment_ , once numerical answers are given by an LLM, the relationship
‘reasoned’ by an LLM (orange) can be compared to an exact reasoning carried
out in Python (black).

###  3.2 Probing and evaluating the LLMs

We use the OpenAI API to prompt GPT-3.5-turbo and GPT-4 in three settings
differing in the formulation of the prompt, with the temperature parameter at
0 to fetch only the most likely answer. The settings are all a form of mask-
prompting, with a preceding instruction to fill in the <mask> token; we employ
two 0-shot variants and one 1-shot variant, and two fact formulations, A and
B. Notably, the A and B versions differ in the preposition next to the <mask>
token for the relationship prompt:

  * •

A typical <thing_a> has a number of <elements_a> that is <mask> than the
number of <elements_b> that a typical <thing_b> has.

  * •

A typical <thing_a> has a number of <elements_a> that is <mask> to/than the
number of <elements_b> a <thing_b> has.

For the 1-shot setting, we include a single example of a query along with a
correct answer; the example is one not present in the dataset, but also in the
domain of commonsense numerical facts / comparisons. For each setting we
iterate through the atomic facts data, as well as the quad-tuple relational
data, populating the appropriate templates. The answers require little
interpretation, as most often either a single token is returned, or the
sentence is repeated back with only the <mask> replaced. For the remaining
cases simple heuristics suffice to extract and canonise the answer. We note
that these heuristics are by no means universal - they were developed
iteratively, and a different model or prompt formulation may result in a
different behaviour. The few exceptions are where the chat answers are not
valid or coherent, which is highlighted in the Experiments section.
To evaluate either the numerical facts or the relationship, we can simply
compare the answers with the (known) ground truth; we report proportion of
correct answers. We also compute the _Entailment_ , which is simply applying
the proportion of correct answers metric to a relationship string entailed by
the extracted numerical facts (rather than the one implied by the actual
numerical facts).

##  4 Experiments

###  4.1 Numerical facts

####  4.1.1 When and how to pop the question?

As can be seen in Fig.2, depending on who one asks (GPT-3.5-turbo versus
GPT-4), as well as how one asks (two versions of 0-shot prompt formulation and
one version of 1-shot formulation), the answers differ. GPT-4 generally
outperforms GPT-3.5, and does not benefit nearly as much from a 1-shot
demonstration setting; both these observations are in line with expectation,
as it is a newer and more powerful model, possibly even explicitly addressing
the gaps in factual knowledge identified by previous research. A little
surprising perhaps is the performance gain of GPT-3.5 in a 1-shot setting,
which improves the outcomes to almost match GPT-4 (and in the case of the
subject ‘human’, surpass GPT-4). Obviously GPT-3.5 has far more room for
improvement, but we further speculate that such a big change may be due to the
demonstration potentially counteracting the particular nature of dominant
hallucinations, which are biased towards subjects rather than elements, as
detailed in the next section. As a final note on the ‘fickle’ nature of the
tested LLMs, for some queries the answer may change from one API call to
another with exact same prompt and despite setting the API parameters to
minimally ‘creative’ values (temperature of 0); we suspect that may be the
case when several tokens have identical probabilities and one of them is being
served randomly. A common situation when this behaviour occurred was the
numeral and the number being used interchangeably. The notable example that
alerted us to this in the first place was the case of the ears of a sparrow,
which about a third of the time GPT-3.5 deemed to be ‘small’ rather than
‘two’.

Figure 2: Proportion of correct answers on numerical facts, by subject. For
each subject the same set of elements was probed, e.g. number of legs, tyres,
fins etc.

####  4.1.2 Null value blindness and subject bias.

An interesting side-effect of the statistical nature of the LLMs and the
selective biases of widely available textual data is that all probed models
struggle to correctly predict the occurrence of zero, what we dubbed here the
‘null value blindness’444 Interesting and at times highly amusing: when probed
separately in early development, GPT-4 has claimed that humans are equipped
with tusks, dorsal fins and no less than 10 suction cups.[5, 8]. We suggest it
is simply due to the fact that data explicitly stating what a subject lacks is
scarce. As noted also in [5] and [8] in the context of physical knowledge,
people do not tend to state the obvious; and since data annotation is an
expensive task, foundational knowledge databases such as ConceptNet [20] are
typically concerned with identifying constructive elements and concepts,
rather than (a much larger set of) ones that are absent. With deficits in
performance on the ‘null’ numerical fact, what do then the models hallucinate?
Following [13] and many other works noting entanglement of concepts and biases
towards more abundant data, we suspected this may also show in our results and
we had deliberately constructed parts of the dataset to facilitate
investigating this (e.g., having unicycle, bicycle and tricycle as subjects).
We choose GPT-3.5 in the 0-shot setting and fact formulation A, as this model
is the weakest and thus most illustrative. As shown in 3, there is a fairly
obvious subject bias in the hallucinated answers that tend to be 1, 2 and 3
for each of the corresponding ‘cardinalities’ of cycles. The notable
exceptions to this pattern are ‘toes on each foot’ and ‘fingers on each hand’,
which are conversely elements-biased, presumably since humans are likely the
most commonly occurring subject in the written language.

Figure 3: Number of elements predicted by GPT-3.5 in a 0-shot setting with
fact formulation A, by element, for selected 3 illustrative subjects: a
unicycle, a bicycle and a tricycle. For majority of cases, answers are biased
towards the defining characteristic number of each subject; notable exception
is fingers on each hand and toes on each foot.

###  4.2 Numerical entailment

The main result of our probing study is summarised in Table 1, which details
the proportions of correct answers on different components of the arithmetical
entailment: numerical facts from either side of the (in)equality in isolation,
and in concert; relation string of the (in)equality; all elements
simultaneously; and finally the _entailed_ relation. We discuss all aspect in
more detail below. For reference we also compute two baselines. First is the
random choice, where atomic facts are sampled randomly from 0-10 once, and
relationship strings from ‘less’,‘same’ or ‘more’; second is always choosing
the majority label.

Table 1: Proportion correct across the probed models and prompt configurations evaluated over the 6003 quad-tuples; best in-model performance in bold. Fact no.1/2 refers to proportion of queries where first/second of the two numerical facts in a given relational query was correct; note this is not equivalent to pure numerical facts since different facts appear in probes with varying rates. Model and prompt | Fact no.1 | Fact no.2 | Both facts | Relation | All facts | Entailment
---|---|---|---|---|---|---
base random | 0.124 | 0.085 | 0.011 | 0.324 | 0.002 | 0.342
base majority | 0.459 | 0.45 | 0.196 | 0.37 | 0.0 | 0.37
GPT-3.5 0-shot A | 0.522 | 0.461 | 0.237 | 0.414 | 0.109 | 0.432
GPT-3.5 0-shot B | 0.614 | 0.535 | 0.325 | 0.4 | 0.143 | 0.419
GPT-3.5 1-shot B | 0.843 | 0.792 | 0.66 | 0.461 | 0.301 | 0.447
GPT-4 0-shot A | 0.836 | 0.814 | 0.676 | 0.585 | 0.417 | 0.631
GPT-4 0-shot B | 0.809 | 0.821 | 0.66 | 0.444 | 0.308 | 0.458
GPT-4 1-shot B | 0.866 | 0.871 | 0.751 | 0.552 | 0.422 | 0.549

####  4.2.1 All ducks in a row

First we would like to note that due to the combinatorial construction of the
dataset from a smaller set of isolated numerical facts, the performance of all
models on numerical facts in Table 1 is not representative and does not match
that of Fig 2, since some subjects-element pairs end up over-represented in
the quad-tuples for EAR probing. The same applies to the random baseline, as
we randomly sample atomic facts only once. We report this primarily to
illustrate the attrition of performance, which predictably drops as conditions
are added. Although ‘Relation’ alone is predicted at modestly above chance
levels, it obviously can’t be seen as a metric of relational reasoning
abilities of LLMs, since for anything resembling reasoning one needs a
foundation of correct assumptions; we suspect shortcut learning or some form
of data bias driving this performance. Hitting ‘all ducks in a row’ in the
best case of GPT-4 in 1-shot settings achieves an impressive 42% improvement
over either of the baselines. However, as we expand on more later, we doubt
this is any indication of reasoning, but rather larger memory.

####  4.2.2 An EAR to the ground

How then might performance look if one evaluates the correctness of the
predicted relational string not against the ground truth but rather against
the relation _entailed_ by the implicit knowledge? As shown in the last column
of Table 1, the performance when factoring in the hallucinatory ‘knowledge’ of
LLMs shows a performance modestly to substantially better than chance,
although with some counter-intuitive patterns. First, for GPT-3.5 as expected
the best performing setting throughout, including ‘Entailment’, is a 1-shot
prompt with fact formulation B. However, a closer look at just the
‘Entailment’ column reveals that for ‘reasoning’ the 1-shot setting or fact
formulation have only a marginal impact; but what is more striking is that
‘Entailment’ is lower than ‘Relation’. Second, for GPT-4 the picture is yet
more confusing, with 0-shot setting decidedly outperforming the others. We
pose that this is simply due to the fact that EAR is not measuring actual
reasoning abilities, merely measuring how well LLMs fake reasoning; we expand
on this in the next subsection.

####  4.2.3 ‘Circumvential’ evidence

As shown recently in the excellent investigation of Chain-of-Thought prompting
by Bao et al. [3], it is highly questionable as to whether LLMs can be said to
‘reason’. Even when they are encouraged to bias themselves towards the correct
answers by producing relevant supporting knowledge, they still may fail to be
biased sufficiently to override underlying data biases and then answer
incongruently with the generated chain of thoughts. Thus we highly doubt
whether a mere invoking of two object-element pairs is sufficient for the LLMs
to put the 2 and 2 together and compare the relevant numbers; and the case of
GPT-4 performing best in 0-shot fact formulation A setting provides the
circumstantial evidence here. The main difference between fact formulation A
and B is that A uses the preposition ‘than’, while B uses ‘to/than’ in order
to not bias the model with grammar. This results in both GPT-3.5 and GPT-4
never answering ‘same’ in setting A and works as an interventional probe
showing that LLMs use the technically task-irrelevant information from other
tokens and circumvent relational reasoning in at least some of the cases. As a
final note and nail in the coffin, we have observed that when a rephrased
answer is returned it occasionally contains two _conflicting_ relational
strings, e.g.

  * •

A typical bicycle has a greater number of handlebars that is fewer than the
number of exhaust pipes a car has.

##  5 Conclusion

Unsurprisingly, we have found that when LLMs are probed for relationships
between implicit knowledge, their performance is poor. Although better than
chance, we highlight that this is on very basic commonsense knowledge (as
opposed to [13] whose data contains also specialist knowledge). We presume the
sub-par outcome to be due to scarcity of negative numerical statements and
relationship comparisons in the training data. As has been noted before [5,
8], explicit data that ‘states the obvious’ is rarely recorded; humans are
agents acting in a physical world and hardly need to write down assumptions
that go into every mundane task. We further observe entangled concepts,
instability and guesswork on the part of LLMs. We conclude that non neuro-
symbolic LLMs are in effect big statistical search engines. Although the
supported data distributions are ever more rich with each GPT release, giving
an impression of innate reasoning capabilities, we emphasise that these models
are not _bona fide_ reasoners.

####  5.0.1 Acknowledgements

This work was supported by funding from Cisco. VB was additionally funded by
Royal Society University Research Fellowship.

## References

  * [1] Al-Kaswan, A., Izadi, M., van Deursen, A.: Traces of memorisation in large language models for code. In: Proceedings of the IEEE/ACM 46th International Conference on Software Engineering. ICSE ’24, ACM (Apr 2024). https://doi.org/10.1145/3597503.3639133, http://dx.doi.org/10.1145/3597503.3639133
  * [2] Badreddine, S., Garcez, A.d., Serafini, L., Spranger, M.: Logic tensor networks. Artificial Intelligence 303, 103649 (2022)
  * [3] Bao, G., Zhang, H., Yang, L., Wang, C., Zhang, Y.: Llms with chain-of-thought are non-causal reasoners (2024)
  * [4] Bubeck, S., Chandrasekaran, V., Eldan, R., Gehrke, J., Horvitz, E., Kamar, E., Lee, P., Lee, Y.T., Li, Y., Lundberg, S., Nori, H., Palangi, H., Ribeiro, M.T., Zhang, Y.: Sparks of artificial general intelligence: Early experiments with gpt-4 (2023)
  * [5] Forbes, M., Choi, Y.: Verb physics: Relative physical knowledge of actions and objects. In: Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). pp. 266–276 (2017)
  * [6] Geiping, J., Stein, A., Shu, M., Saifullah, K., Wen, Y., Goldstein, T.: Coercing llms to do and reveal (almost) anything (2024)
  * [7] Geva, M., Gupta, A., Berant, J.: Injecting numerical reasoning skills into language models. In: Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics. pp. 946–958 (2020)
  * [8] Goel, P., Feng, S., Boyd-Graber, J.: How pre-trained word representations capture commonsense physical comparisons. In: Proceedings of the First Workshop on Commonsense Inference in Natural Language Processing. pp. 130–135 (2019)
  * [9] Guo, Z., Jin, R., Liu, C., Huang, Y., Shi, D., Yu, L., Liu, Y., Li, J., Xiong, B., Xiong, D., et al.: Evaluating large language models: A comprehensive survey. arXiv preprint arXiv:2310.19736 (2023)
  * [10] Jin, Z., Liu, J., Lyu, Z., Poff, S., Sachan, M., Mihalcea, R., Diab, M., Schölkopf, B.: Can large language models infer causation from correlation? arXiv preprint arXiv:2306.05836 (2023)
  * [11] Li, Y., Liu, Y., Deng, G., Zhang, Y., Song, W., Shi, L., Wang, K., Li, Y., Liu, Y., Wang, H.: Glitch tokens in large language models: Categorization taxonomy and effective detection (2024)
  * [12] Li, Z., Cao, Y., Xu, X., Jiang, J., Liu, X., Teo, Y.S., Lin, S.w., Liu, Y.: Llms for relational reasoning: How far are we? arXiv preprint arXiv:2401.09042 (2024)
  * [13] Lin, B.Y., Lee, S., Khanna, R., Ren, X.: Birds have four legs?! numersense: Probing numerical commonsense knowledge of pre-trained language models. In: Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP). pp. 6862–6868 (2020)
  * [14] Liu, X., Wu, Z., Wu, X., Lu, P., Chang, K.W., Feng, Y.: Are llms capable of data-based statistical and causal reasoning? benchmarking advanced quantitative reasoning with data (2024)
  * [15] Mikolov, T., Chen, K., Corrado, G., Dean, J.: Efficient estimation of word representations in vector space (2013)
  * [16] Mostafazadeh, N., Kalyanpur, A., Moon, L., Buchanan, D., Berkowitz, L., Biran, O., Chu-Carroll, J.: Glucose: Generalized and contextualized story explanations. arXiv preprint arXiv:2009.07758 (2020)
  * [17] Pan, L., Albalak, A., Wang, X., Wang, W.: Logic-lm: Empowering large language models with symbolic solvers for faithful logical reasoning. In: Findings of the Association for Computational Linguistics: EMNLP 2023. pp. 3806–3824 (2023)
  * [18] Rumbelow, J.: Solidgoldmagikarp (plus, prompt generation). LessWrong (2023), https://www.lesswrong.com/posts/aPeJE8bSo6rAFoLqg/solidgoldmagikarp-plus-prompt-generation
  * [19] Schick, T., Dwivedi-Yu, J., Dessì, R., Raileanu, R., Lomeli, M., Hambro, E., Zettlemoyer, L., Cancedda, N., Scialom, T.: Toolformer: Language models can teach themselves to use tools. Advances in Neural Information Processing Systems 36 (2024)
  * [20] Speer, R., Chin, J., Havasi, C.: Conceptnet 5.5: An open multilingual graph of general knowledge. In: Proceedings of the AAAI conference on artificial intelligence. vol. 31 (2017)
  * [21] Teso, S., Sebastiani, R., Passerini, A.: Structured learning modulo theories. Artificial Intelligence 244, 166–187 (2017)
  * [22] Vallance, C.: Google engineer says lamda ai system may have its own feelings. BBC (2022), https://www.bbc.co.uk/news/technology-61784011
  * [23] Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A.N., Kaiser, L., Polosukhin, I.: Attention is all you need (2017), https://arxiv.org/pdf/1706.03762.pdf
  * [24] Yu, J., Wu, Y., Shu, D., Jin, M., Xing, X.: Assessing prompt injection risks in 200+ custom gpts. arXiv preprint arXiv:2311.11538 (2023)