# Shadows of new physics on Dirac materials,
analog GUPs and other amusements

Alfredo Iorio<EMAIL_ADDRESS>Faculty of Mathematics and Physics,
Charles University, V Holešovičkách 2, 18000 Prague 8, Czech Republic  Boris
Ivetić<EMAIL_ADDRESS>Wohlergasse 6, 1100 Vienna, Austria  Salvatore
Mignemi<EMAIL_ADDRESS>Dipartimento di Matematica e Informatica, via
Ospedale 72, 09123, Cagliari, Italy and INFN Sezione di Cagliari, Italy  Pablo
Pais<EMAIL_ADDRESS>Instituto de Ciencias Físicas y Matemáticas,
Universidad Austral de Chile, Casilla 567, 5090000 Valdivia, Chile  Faculty of
Mathematics and Physics, Charles University, V Holešovičkách 2, 18000 Prague
8, Czech Republic

###### Abstract

We discuss here how, when higher-order effects in the parameter
$\frac{\ell}{\hbar}|\vec{p}|$, related to the lattice spacing $\ell$, are
considered, pristine graphene, and other Dirac materials, can be used as
tabletop systems where generalized commutation relations are naturally
realized. Such generalized algebras of quantization, which lead to generalized
versions of the Heisenberg uncertainty principle, are under intense scrutiny
these days, as they could manifest a fundamental length scale of spacetime.
Despite the efforts and the many intriguing results, there are no experimental
signatures of any generalized uncertainty principle (GUP). Therefore, our
results here, which tell how to use tabletop physical systems to test certain
GUPs in analog experiments, should be of interest to practitioners of quantum
gravity. We identify three different energy regimes that we call “layers”,
where the physics is still of a Dirac type but within precisely described
limits. The higher the energy, the more sensitive the Dirac system becomes to
the effects of the lattice. Here such lattice plays the role of a discrete
space where the Dirac quasi-particles live. With the goals just illustrated,
we had to identify the mapping between the high-energy coordinates, $X^{i}$,
and the low-energy ones, $x^{i}$, i.e., those measured in the lab. We then
obtained three generalized Heisenberg algebras. For two of them we have the
noticeable result that $X^{i}=x^{i}$, and for the third one we obtained an
improvement with respect to an earlier work: the generalized coordinates
expressed in terms of the standard phase space variables, $X^{i}(x,p)$, and
higher order terms.

##  I Introduction

In the search for new physics, it is an established tradition to look for
effects of high energy phenomena at our low energy scales. One way to do it is
to consider the action for the “high-energy” fields, $\hat{\Phi}_{a}$, as an
expansion in terms of “low-energy” fields, $\Phi_{a}$ and a suitable parameter
$\epsilon$, so that

$\displaystyle{\cal S}(\hat{\Phi}_{a})={\cal
S}(\Phi_{a})+S_{1}(\epsilon,\Phi_{a},\partial)+O(\epsilon^{2},\partial^{2})\,.$
(1)

Examples from earlier research are many. Two that come to mind are the
noncommutative field theories faced with the help of the Seiberg-Witten map
[1]

$\displaystyle\hat{A}_{\mu}$ $\displaystyle=$ $\displaystyle
A_{\mu}-\frac{1}{2}\theta^{\alpha\beta}\,A_{\alpha}\,(\partial_{\beta}A_{\mu}+F_{\beta\mu})+O(\theta^{2})\;,$
$\displaystyle\hat{F}_{\mu\nu}$ $\displaystyle=$ $\displaystyle
F_{\mu\nu}+\theta^{\alpha\beta}\,(F_{\mu\alpha}\,F_{\nu\beta}-A_{\alpha}\,\partial_{\beta}F_{\mu\nu})+O(\theta^{2})\;,$
(2)

that for (1) gives

${\cal S}(\hat{A}_{\mu})\ =\ -\frac{1}{4}\hat{F}\cdot\hat{F}\ =\
-\frac{1}{4}\left(F\cdot F-\frac{1}{2}(\theta\cdot F)\,(F\cdot
F)+2(F\,\theta\,F)\cdot F\right)+O(\theta^{2})\,,$ (3)

where $\theta\sim{\ell}_{P}^{2}$ and $\ell_{P}$ is a reference length, usually
taken to be the Planck length. For more on this see [1, 2, 3, 4] for the
theory and, e.g., [5, 6, 7] for some phenomenology.

Another, somehow more general, example is Colladay-Kostelecky’s Standard Model
Extension [8], that can be described by

$\displaystyle{\cal S}(\hat{\Phi}_{a})={\cal
S}_{SM}(\Phi_{a})+\sum_{k=1}^{\infty}C^{(k)}_{\mu...\nu}(\Phi_{a},\partial)^{\mu...\nu}\,,$
(4)

with $C^{(k)}\sim{\ell}_{P}^{k}$. For a review of both approaches, and a
comparison, see, e.g., [9].

These are the days of the generalized uncertainty principles (GUPs) [10, 11,
12]; see also the recent review [13]. Many approaches exist that consider
high-energy phase space variables, $(x,p)$, vs low-energy variables,
$(x_{0},p_{0})$. Here we focus on a specific one that has been introduced by
Ali, Das and Vagenas (ADV) in [14, 15, 16, 17]

$\displaystyle
p_{i}=p_{0i}\left(1-A|\vec{p_{0}}|+2A^{2}|\vec{p_{0}}|^{2}\right)\,,$ (5)

where $A=\tilde{A}\,\ell_{P}/\hbar$, $\tilde{A}$ is a numerical factor and

$\displaystyle x_{i}=x_{0i}\,,$ (6)

with $[x_{0i},p_{0j}]=\imath\hbar\delta_{ij}$, but where

$\displaystyle[x_{i},p_{j}]=\imath\hbar\left[\delta_{ij}-A|\vec{p}|\left(\delta_{ij}+\frac{p_{i}p_{j}}{|\vec{p}|^{2}}\right)+A^{2}|\vec{p}|^{2}\left(\delta_{ij}+3\,\frac{p_{i}p_{j}}{|\vec{p}|^{2}}\right)\right]\,.$
(7)

There is an intense activity to find GUP-corrected physics. Besides the
already cited work of [14, 15, 16, 17], other important results that use
different approaches are in [18, 19, 20]. A compelling example for this paper,
for instance, is in [17] where it is found that the GUP-corrected Dirac
equation, in any dimension, is

$\displaystyle H\,\psi$ $\displaystyle=$
$\displaystyle\left(c\vec{\alpha}\cdot\vec{p}+\beta mc^{2}\right)\,\psi$
$\displaystyle=$
$\displaystyle\left(c\vec{\alpha}\cdot\vec{p}_{0}-cA(\vec{\alpha}\cdot\vec{p}_{0})^{2}+\beta
mc^{2}\right)\,\psi$ $\displaystyle=$ $\displaystyle E\,\psi\,,$

that in two dimensions gives

$\displaystyle\left(-\imath\hbar
c\sigma_{1}\frac{d}{dx_{0}}+A\,\hbar^{2}c\,\frac{d^{2}}{dx_{0}^{2}}+\beta
mc^{2}\right)\,\psi$ $\displaystyle=$ $\displaystyle E\,\psi\,.$ (9)

This search for what we might call the “shadows of new physics” at our energy
scales is fascinating. Nonetheless, not even one single experiment over the
many performed over the decades has seen anything. Fortunately, due to the
higher experimental control of condensed matter systems, it is now becoming
increasingly popular to reproduce various aspects of fundamental physics in
analog systems. Examples include the Hawking phenomenon in Bose–Einstein
condensates [21], the Weyl symmetry [22, 23] and the related Hawking/Unruh
phenomenon on graphene [24, 25, 26], gravitational and axial anomalies in Weyl
semimetals [27], and more.

Henceforth, taking that road, we focus on the proposal of graphene as an
analog of high-energy fundamental physics [22, 23, 24, 25, 26, 28, 29, 30, 31,
32], based on the fact that its low-energy excitations are massless Dirac
pseudo-relativistic fermions (the matter fields $\psi$), propagating in a
carbon two-dimensional honeycomb lattice [33]. Such behaviour is shared by a
wide range of materials, called “Dirac materials” [34].

Here we shall rely heavily on [35] and, to a lesser extent, on [36, 37], and
shall take the chance to explain key details of the construction that are not
explicitly exposed there.

##  II Variables, Supervariables, Hypervariables

In this problem we are in two-space and one-time dimensions. We have three
energy “layers”, each with its own appropriate phase-space variables, that we
indicate as

$(x,p)\,,\quad(X_{0},P_{0})\,,\quad(X,P)\,.$ (10)

This notation is discussed at length in [35]. Let us say here that the
variables $(x,p)$ are the actual phase-space variables of the lowest energy
Dirac quasiparticles of graphene that originate from the $O(\ell)$ dispersion
relations, with $\ell$ the lattice spacing

$E_{\pm}=\pm v_{F}|\vec{p}|\,,$ (11)

where $v_{F}=3/2\,|\eta_{1}|\,\ell/\hbar$, with $\eta_{1}\simeq-2.8$eV the
nearest neighbor hopping energy; see details in [33].

Such variables have a clear physical meaning, as coordinates and momenta of
the low-energy conductivity electrons moving around (quantum mechanically) on
the membrane111This word is used on purpose, as the hexagonal lattice appears
as a continuum at that energy/wavelength..

There we explain how to obtain the dispersion relations in the usual way
(secular equation), based on the knowledge of the functions

${\cal
F}_{m}({\vec{k}})\equiv\sum_{i=1}^{n_{m}}e^{i{\vec{k}}\cdot{\vec{s}^{(m)}}_{i}}\,,$
(12)

encoding the relevant information on the geometry of the lattice relative to
the $m^{\rm th}$-near neighbors. Other details on the derivation of the ${\cal
F}_{m}$s are in [36], where it is explained that the $n_{m}$ vectors
$\vec{s}^{(m)}_{i}$ connect any given atom to its $m^{\rm th}$-near neighbors.

Using the fortuitous occurrence, ${\cal F}_{2}=|{\cal F}_{1}|^{2}-3$, and
various approximations explained in [35], we arrive at the dispersion
relations

$E_{\pm}=\eta_{1}(\pm|{\cal F}_{1}|-\tilde{A}|{\cal F}_{1}|^{2})\;,$ (13)

where $\tilde{A}\simeq 0.15$.

It is then natural to define two further sets of variables, that we call
“supervariables”, $(X_{0},P_{0})$, and “hypervariables”, $(X,P)$, as both sets
refer to functions that appear in the dispersion relations that contain all
orders222This is literally true, as the function in (13) contains all orders
in $\ell$. Nonetheless, one needs to decide at which order one would like to
proceed, say $O(\ell^{m})$, and then all quantities need be taken at order
$m$. Furthermore, the simple expression (13) is already an approximation that
holds when higher-order contributions are not considered, see [35, 36, 37]. in
$\ell$. In other words (writing things in a dimensionless fashion, i.e., not
including a necessary factor of $1/\ell$)

$|{\cal F}_{1}|\sim p+O(\ell^{2})\,,\quad|{\cal F}_{1}|\sim
P_{0}\,,\quad|{\cal F}_{1}|-\tilde{A}|{\cal F}_{1}|^{2}\sim P\,.$ (14)

These relations are key in our analysis and are dictated by the phenomenology
of the system.

In (13), if we define the supermomenta as

$\vec{P_{0}}=-\frac{\hbar}{\ell}(\mbox{Re}{\cal F}_{1},\mbox{Im}{\cal
F}_{1})\;,$ (15)

then we can write

$E_{\pm}=V_{F}(\pm|\vec{P_{0}}|-A\,|\vec{P_{0}}|^{2})\,,$ (16)

where $V_{F}\equiv|\eta_{1}|\,\ell/\hbar$ and $A=\ell/\hbar\,\tilde{A}$.

Notice that in the following, we shall use a slightly different definition of
$\vec{P_{0}}$, that allows one to expand it as
$\vec{P_{0}}\sim\vec{p}+\cdots$, rather than $\vec{P_{0}}\sim
3/2\vec{p}+\cdots$. That is $\vec{{\cal P}_{0}}\equiv 2/3\vec{P_{0}}$, but, to
simplify notation with an abuse, we shall write $\vec{{\cal
P}_{0}}\to\vec{P_{0}}$.

Let us now set $\hbar=1$, unless otherwise stated.

Just like in the literature it is customary to use a standard Dirac
Hamiltonian, in relation to the linear dispersion relations (11), we can keep
going with the same logic by building-up the appropriate Hamiltonian in terms
of the supermomenta $\vec{P_{0}}$, whose dispersion relations, descending from
the secular equation

${\rm det}(H-E\mathbb{1})=0$ (17)

are indeed (16). To do that one must realize that to obtain, through (17),
$|\vec{P_{0}}|$ in the dispersion relation, a corresponding term
$\vec{\sigma}\cdot\vec{P_{0}}\equiv\not{P_{0}}$ needs be in the Hamiltonian:
$|\vec{P_{0}}|\to\not{P_{0}}$. Thus, the effective Hamiltonian we can use to
describe the physics of the “superlayer” $(X_{0},P_{0})$ is

$H(P_{0})=V_{F}\,\sum_{k}\,\psi^{\dagger}_{k}\left(\not{P_{0}}-A\not{P_{0}}\not{P_{0}}\right)\psi_{k}=V_{F}\,\sum_{k}\,\psi^{\dagger}_{k}\left(\vec{\sigma}\cdot\vec{P_{0}}-A|\vec{P_{0}}|^{2}\mathbb{1}\right)\psi_{k}\,.$
(18)

Notice that we use the convention333There are many conventions related to
different choices for the pairs of inequivalent Dirac points, and different
arrangements of the $a$ and $b$ operators to form the spinor $\psi$. See
Appendix B of [30] for more details.
$\psi_{k}^{\dagger}=(b_{k}^{\dagger},a_{k}^{\dagger})$, where $a_{k}$ and
$b_{k}$ are the annihilation operators of each graphene sublattice, see [22].

Indeed, by considering the $2\times 2$ structure of $H$

$H(P_{0})\sim
V_{F}\left(\begin{array}[]{cc}-A|\vec{P_{0}}|^{2}&P_{0}^{1}-iP_{0}^{2}\\\
P_{0}^{1}+iP_{0}^{2}&-A|\vec{P_{0}}|^{2}\\\ \end{array}\right)\;,$ (19)

clearly the two solutions of (17)

${\rm det}(H(P_{0})-E\mathbb{1})=0\sim{\rm
det}\left(\begin{array}[]{cc}-A|\vec{P_{0}}|^{2}-E&P_{0}^{1}-iP_{0}^{2}\\\
P_{0}^{1}+iP_{0}^{2}&-A|\vec{P_{0}}|^{2}-E\\\
\end{array}\right)=0\sim(A|\vec{P_{0}}|^{2}+E)^{2}=|\vec{P_{0}}|^{2}\;,$ (20)

are those given in (13).

We can then move one last step up, in energy and symmetry (see [35]), by
defining the hypermomenta

$\vec{P}=\vec{P_{0}}(1-A\,|\vec{P_{0}}|)\;,$ (21)

that is nothing more than a consequence of the above mentioned fortuitous
occurrence, ${\cal F}_{2}=|{\cal F}_{1}|^{2}-3$, hence a physical fact of this
system; see (14) and discussion there.

With this definition we arrive at the most symmetric situation of all, that is
a full linearization of the Hamiltonian

$H(P)=V_{F}\,\sum_{k}\,\psi^{\dagger}_{k}\,\not{P}\,\psi_{k}\,,$ (22)

with dispersion relations

$E_{\pm}=\pm V_{F}|\vec{P}|\,,$ (23)

which is, in all respects but two, similar to (11). The two differences are
crucial, though. First, the slope here is $V_{F}$ not $v_{F}\simeq 1.5V_{F}$.
Second, the hypermomenta are generalized variables, containing, in principle,
all orders in $\ell$ and $p$ (see [35] and later here).

To obtain $H(P_{0})$ from $H(P)$ one should first use the expansion (21), and
then use the prescription $|\vec{P_{0}}|\to\not{P_{0}}$

$\displaystyle H(P(P_{0}))$ $\displaystyle=$ $\displaystyle
V_{F}\,\sum_{k}\,\psi^{\dagger}_{k}\,\vec{\sigma}\cdot\vec{P}\,\psi_{k}$ (24)
$\displaystyle=$ $\displaystyle
V_{F}\,\sum_{k}\,\psi^{\dagger}_{k}\vec{\sigma}\cdot\left(\vec{P_{0}}(1-A|\vec{P_{0}}|)\right)\,\psi_{k}$
$\displaystyle\to$ $\displaystyle
V_{F}\,\sum_{k}\,\psi^{\dagger}_{k}\left(\vec{\sigma}\cdot\vec{P_{0}}-A(\vec{\sigma}\cdot\vec{P_{0}})\,(\vec{\sigma}\cdot\vec{P_{0}})\right)\,\psi_{k}$
$\displaystyle=$ $\displaystyle
V_{F}\,\sum_{k}\,\psi^{\dagger}_{k}\left(\not{P_{0}}-A|\vec{P_{0}}|^{2}\right)\,\psi_{k}=H(P_{0})\,.$

Now, let us move towards the measurable quantities of the lowest layer
$(x,p)$. We first need to expand ${\cal F}_{1}$ in powers of $\ell$ or $p$.
Indeed, this means, through (15), to expand $P_{0}$ in powers of $\ell$ or
$p$, and through (21), to expand $P$ in powers of $\ell$ or $p$. The function
in point is

${\cal F}_{1}=e^{i\ell
k_{y}}\,\left(1+2\,e^{i\frac{3}{2}\ell\,k_{x}}\,\cos(\frac{\sqrt{3}}{2}\ell\,k_{x})\right)\;.$
(25)

This expansion, in general, needs be done around the two inequivalent Fermi
points $K^{D}_{\pm}=(\pm\frac{4\pi}{3\sqrt{3}\ell},0)$, located where ${\cal
F}_{1}=0$. In our case, though, we are not considering topological defects or
other physical set-ups that include, in their description, both Dirac points.
For us it is sufficient to do all calculations near one Dirac point, e.g., if
$k_{i}=K^{D}_{+i}+p_{i}$.

Thus, the Hamiltonian $H(P_{0})$ in (18) expressed in terms of $\vec{p}$ up
to444One should recall that, in the Hamiltonian, there is always an overall
factor $O(\ell)$, given by the Fermi velocity
$v_{F}=\frac{3\eta_{1}}{2\hbar}\times\ell$, so that $O(p^{m})$ and
$O(\ell^{m})$, in the Hamiltonian, go actually together. $O(\ell^{3})$, is

$\begin{split}H(P_{0}(p))=H(p)=&\
v_{F}\sum_{\vec{p}}\psi^{\dagger}_{\vec{p}}\big{[}\sigma_{1}\left(p_{1}-\frac{\ell}{4}(p^{2}_{1}-p^{2}_{2})-\frac{\ell^{2}}{8}p_{1}(p^{2}_{1}+p^{2}_{2})\right)\\\
+&\
\sigma_{2}\left(p_{2}+\frac{\ell}{2}p_{1}p_{2}-\frac{\ell^{2}}{8}p_{2}(p^{2}_{1}+p^{2}_{2})\right)\\\
-&\
\frac{3}{2}A\left((p^{2}_{1}+p^{2}_{2})-\frac{\ell}{2}p_{1}^{3}+\frac{3\ell}{2}p_{1}p^{2}_{2}\right)\big{]}\psi_{\vec{p}}\;.\end{split}$
(26)

For the sake of complete control of the units, let us now reintroduce $\hbar$,
and let us write the dispersion relations for this Hamiltonian as

$\displaystyle
E_{\pm}=v_{F}\left[\pm|\vec{p}|\mp\frac{1}{4}\frac{\ell}{\hbar}|\vec{p}|^{2}\cos(3\theta)\mp\frac{1}{64}\frac{\ell^{2}}{\hbar^{2}}|\vec{p}|^{3}\left(7+\cos(6\theta)\right)-\frac{3}{2}\,A\,|\vec{p}|^{2}+\frac{3}{4}\,A\,\frac{\ell}{\hbar}|\vec{p}|^{3}\cos(3\theta)\right]\;,$
(27)

where

$A=0.15\,\frac{\ell}{\hbar}>0\;,$ (28)

$\tan\theta=p_{2}/p_{1}$ and

$v_{F}\equiv\frac{3}{2}\,|\eta_{1}|\,\frac{\ell}{\hbar}\,\simeq c/300\simeq
10^{6}m/s\;.$ (29)

Let us give here another writing of the dispersion relations

$\displaystyle E_{\pm}$ $\displaystyle=$
$\displaystyle\frac{3}{2}|\eta_{1}|\left[\pm\left(\frac{\ell}{\hbar}|\vec{p}|\right)\mp\frac{1}{4}\left(\frac{\ell}{\hbar}|\vec{p}|\right)^{2}\cos(3\theta)\mp\frac{1}{64}\left(\frac{\ell}{\hbar}|\vec{p}|\right)^{3}\left(7+\cos(6\theta)\right)\right.$
(30) $\displaystyle-$
$\displaystyle\left.\frac{3}{2}\,0.15\,\left(\frac{\ell}{\hbar}|\vec{p}|\right)^{2}+\frac{3}{4}\,0.15\,\left(\frac{\ell}{\hbar}|\vec{p}|\right)^{3}\cos(3\theta)\right]\;,$

which makes clear that the expansion parameter is
$\frac{\ell}{\hbar}|\vec{p}|$.

##  III Choice of the generalized coordinates and related GUPs

From the previous discussion, it is clear that the interpretation of
$P^{i}_{0}$ and $P^{i}$ as generalized momenta is suggested by the dispersion
relations, hence the functional form of $P_{0}^{i}(p)$

$\displaystyle P^{1}_{0}$
$\displaystyle=p^{1}+\frac{\ell}{4}\left((p^{2})^{2}-(p^{1})^{2}\right)-\frac{\ell^{2}}{8}p^{1}\left((p^{1})^{2}+(p^{2})^{2}\right)\,,$
$\displaystyle P^{2}_{0}$
$\displaystyle=p^{2}+\frac{\ell}{2}p^{1}p^{2}-\frac{\ell^{2}}{8}p^{2}\left((p^{1})^{2}+(p^{2})^{2}\right)\,.$
(31)

or, equivalently

$\displaystyle P^{1}_{0}$ $\displaystyle=p^{1}-\frac{\ell}{4}|\vec{p}|^{2}\cos
2\theta-\frac{\ell^{2}}{8}|\vec{p}|\cos\theta\;,$ $\displaystyle P^{2}_{0}$
$\displaystyle=p^{2}+\frac{\ell}{4}|\vec{p}|^{2}\sin
2\theta-\frac{\ell^{2}}{8}|\vec{p}|\sin\theta\;,$ (32)

Hence of $P^{i}(p)$, through (21), are dictated by the physics of the system.
The form of the dispersion relations, in turn, tells us how the effective
Hamiltonian must look like, with little or no freedom.

What is left to the interpretation is the meaning of the generalized
coordinates, $X^{i}_{0}$ and $X^{i}$. Only when this is done the picture is
complete, and we have all that is necessary, $(H,X,P)$, to describe the
dynamics.

Although there is room for different interpretations for the generalized
coordinates, there are two choices that are very natural, hence stand out as
privileged:

  * •

The first choice is to keep $x^{i}$ as the generalized coordinates,
$x^{i}=X_{0}^{i}=X^{i}$. This choice, as obvious from $[x,P(p)]\sim
i\partial_{p}P$, leads to some form of GUP.

  * •

The second choice is to demand the generalized coordinates to be canonical,
$[X_{0},P_{0}]=i=[X,P]$. This choice necessarily leads to both
$X_{0}^{i}(x,p)$ and $X^{i}(x,p)$.

To summarize (see [35] for details): One can move from the standard
(canonical) variables that describe the lowest energy physics of the Dirac
quasi-particles of graphene, $(x,p)$, to the next “layer”, by including higher
order contributions in $p$ to $P_{0}$, that we call supervariables,
$(X_{0},P_{0})$. Then, considering that contributions of the same order could
come by including next-to-near neighbors in the computations ($A\neq 0$), one
can move one more “layer” up, to the hypervariables $(X,P)$.

If, at every step, we only consider the two privileged choices for the
generalized coordinates, the GUP and the canonical, the overall options we
have are given in the following diagram [35]

canonical $(X,P)$ $(IV)$canonical $(X_{0},P_{0})$ $(II)$GUP $(X,P)$
$(V)$canonical $(x,p)$ $(I)$canonical $(X,P)$ $(VI)$GUP $(X_{0},P_{0})$
$(III)$GUP $(X,P)$ $(VII)$

It is important to notice that:

  * •

To include terms from $O(p^{2})$ on, we have to keep $A\neq 0$, as seen in
(28). Therefore, the “layer of reference” is always the “hyperworld”, $(X,P)$.

  * •

The interesting set-ups are those leading to GUPs in the final layer, the one
of reference. In the above scheme, these are (V) and (VII).

  * •

No matter the choice, all the quantities eventually need be expressed in terms
of the measurable standard variables, $(x,p)$.

With this in mind, the GUP-corrected physics here is given by the Hamiltonian
(26), and the related dispersion relations (27). We simply need to read-off
all results in terms of the appropriate variables, that for the coordinates
are:

  1. 1.

the case $X^{i}=x^{i}$ (that is the ladder $(I)\to(III)\to(VII)$), leading to
the GUP (VII)

$[X^{i},P^{j}]=\mathrm{i}F^{i\,k}(\vec{P})\,\left[\delta^{kj}-A|\vec{P}|\,\left(\delta^{kj}+\frac{P^{k}\,P^{j}}{|\vec{P}|^{2}}\right)-A^{2}|\vec{P}|^{2}\,\left(\delta^{kj}+\frac{P^{k}\,P^{j}}{|\vec{P}|^{2}}\right)\right]$
(33)

where

$F^{i\,j}(\vec{P})=\delta^{ij}+\frac{1}{2}\,\ell\,\left(\begin{array}[]{cc}-P^{1}&P^{2}\\\
P^{2}&P^{1}\\\
\end{array}\right)+\frac{1}{2}\,\ell\,A\,|\vec{P}|\,\left(\begin{array}[]{cc}-P^{1}&P^{2}\\\
P^{2}&P^{1}\\\
\end{array}\right)-\frac{1}{2}\,\ell^{2}\,\left(\begin{array}[]{cc}(P^{1})^{2}&P^{1}P^{2}\\\
P^{1}P^{2}&(P^{2})^{2}\\\ \end{array}\right)\;,$

Notice that $F^{ij}=F^{ji}$, and
$F^{i}_{i}(\vec{P})=2-\frac{\ell^{2}}{2}|\vec{P}|^{2}$.

  2. 2.

and the case $X^{i}=X^{i}_{0}(x,p)$ with

$\displaystyle X_{0}^{1}(x,p)$
$\displaystyle=\left[1+\frac{\ell}{2}p^{1}+\frac{\ell^{2}}{8}\left(5(p^{1})^{2}+3(p^{2})^{2}\right)\right]\,x^{1}+\left[-\frac{\ell}{2}p^{2}+\frac{\ell^{2}}{4}p^{1}p^{2}\right]\,x^{2}\;,$
(34) $\displaystyle X_{0}^{2}(x,p)$
$\displaystyle=\left[-\frac{\ell}{2}p^{2}+\frac{\ell^{2}}{4}p^{1}p^{2}\right]\,x^{1}+\left[1-\frac{\ell}{2}p^{1}+\frac{\ell^{2}}{8}\left(3(p^{1})^{2}+5(p^{2})^{2}\right)\right]\,x^{2}\;.$

That is the ladder $(I)\to(II)\to(V)$), leading to the GUP (V), an expression
coinciding, at first order in $A$, with the ADV-like GUP (see (7))

$[X^{i},P^{j}]=\mathrm{i}\,\left[\delta^{ij}-A|\vec{P}|\,\left(\delta^{ij}+\frac{P^{i}\,P^{j}}{|\vec{P}|^{2}}\right)-A^{2}|\vec{P}|^{2}\,\left(\delta^{ij}+\frac{P^{i}\,P^{j}}{|\vec{P}|^{2}}\right)\right]\;.$
(35)

The other commutators are trivial.

One does not need any special or exotic setup to have the GUP all-the-way
ladder at work. The only thing that is necessary is to include higher order
terms in the dispersion relations, and then move to the next-to-near
neighbors. The coordinates are always just $x^{i}$. Since the literature is
full of proposals on how GUPs affect a variety of phenomena, see, e.g., [10,
11, 12, 18, 19, 20, 32] and since we have obtained here many such GUPs, some
very similar to the ones descending from quantum gravity, then we are now in
the position to prove some of those theoretical conjectures in the lab.

Notice that, in going from $(I)$ to $(III)$, we also have a GUP

$[X_{0}^{i},P_{0}^{j}]=\mathrm{i}F^{ij}(\vec{P_{0}}),\ \ \
[X_{0}^{i},X_{0}^{j}]=0=[P_{0}^{i},P_{0}^{j}]\;,$ (36)

with $F^{ij}(\vec{P_{0}})$ given in

$F^{i\,j}(\vec{P_{0}})=\delta^{ij}+\frac{1}{2}\,\ell\,\left(\begin{array}[]{cc}-P_{0}^{1}&P_{0}^{2}\\\
P_{0}^{2}&P_{0}^{1}\\\
\end{array}\right)-\frac{1}{2}\,\ell^{2}\,\left(\begin{array}[]{cc}(P_{0}^{1})^{2}&P_{0}^{1}P_{0}^{2}\\\
P_{0}^{1}P_{0}^{2}&(P_{0}^{2})^{2}\\\ \end{array}\right)\;.$

Since, for the reasons explained earlier, we shall always like to include the
$A\neq 0$ effects, we only consider this as an intermediate mathematical step.

##  IV Conclusions

We have discussed here how analogs of three kinds of GUPs can be obtained when
higher order terms are considered in the dispersion relations of the
conductivity electrons of a generic Dirac material.

An analog system cannot behave as the target system in all respects but only
in certain specific conditions, for certain types of particles and for
particular regimes of the interaction. In fact, one of the aspects we have to
give up in an analog is the _universality_ , which should be expected in the
presence of a _fundamental_ GUP.

For instance, in the “three graphene worlds” we have explored here, we only
have at our disposal a limited set of all the possible particles and fields,
compared to those that nature gives us. Essentially, in a Dirac material we
have analogs of

  * •

massless Dirac spinors, $\psi$, that are the $\pi$-electrons quasiparticles;

  * •

the U(1) gauge fields, $A_{\mu}$, stemming from straining the material, that
could be used to mimic electromagnetic interactions;

  * •

the nonabelian gauge fields, $A^{a}_{\mu}$, due to the two copies of $\psi$,
one per Dirac point, often described as SU(2) gauge fields, that could be used
to mimic internal symmetries;

  * •

the spin connection, $\omega^{a}_{\mu}$, that always takes care of the
intrinsic curvature associated to disclination defects in the lattice, and may
or may not include contorsion, $\kappa^{a}_{\mu}$, that takes care of the
intrinsic curvature associated to dislocation defects;

  * •

classical (and quantum) metric fields, $g_{\mu\nu}$, that emerge as a
collective description of the elastic and unelastic properties of the
membrane.

Some more steps could be moved when we adapt (reduce) external fields, e.g.,
the true electromagnetic field, to the lower dimensional, and
$v_{F}$-relativistic (rather than the $c$-relativistic) and specific dynamics
of the system. That is all.

Clearly, then, here we cannot have all types of particles and fields
propagating in a GUP-compatible space, described by a suitable $g_{\mu\nu}$,
but we can do that for a limited set, for instance, $\psi$ propagating on a
flat space with granular structure.

Even for this limited situation, since the recipe here consists in having
control on the appropriate phase-space variables, we need to know how to
recognize the “shadows of the high energy physics”, so to speak, on what
mimics “the low energy GUP-corrected physics”.

With the results of [35], we are now able to face these issues because we now
know the form of $X^{i}$ and $X_{0}^{i}$, in terms of $x^{i}$ and $p^{i}$.
With those results in our hands, we may safely solve the problem of lack of
universality by, e.g., limiting the set-up to only Dirac quasi-particles
$\psi$ and setting up a potential well, as many others do routinely in the
same analog/effective language.

Such potential $V$ must be a function of the correct variables, $X^{i}$, i.e.
$V(X)$. But now we know $X(x,p)$, and this simply means $X_{i}=x_{i}$ in the
most interesting case. Hence, the very same potential well $V(x)$ one has for
the GUP-non-corrected physics (the standard one) stays for GUP-corrected
physics. In an experiment like that, we would prove that the GUP-corrected
dynamics can indeed be practically realized in such a simple system, and one
could check many theoretical statements in a lab.

To close, a note on the generality of our results. All condensed matter
systems have corrections to linear or quadratic dispersion laws. Some kind of
GUP may then appear in many systems after the suitable variables change.
Notice that our approach may or may not lead to sensible analogs GUPs. In
other words, it is not as simple as “any suitable change of variables leads to
some sensible GUP”. For instance, in our case, we have seen that only by
stopping at ${\cal F}_{2}$ and making other approximations, it is possible to
find GUPs related to the ADV GUPs. If one keeps going in the order of the
expansion, no natural ADV or ADV-like structures are recovered. Other systems
may have different natural GUPs, none at all, or unknown GUPs (like some of
those that we discussed here).

To close, let us stress again that, of course, we did not prove here that
graphene, or other materials of that kind, are systems where fundamental GUPs
are at work. Nor we are suggesting that, following our procedure, fundamental
GUPs can be spotted in other condensed matter systems. We are saying here that
those easy-to-produce tabletop real systems, by a simple redefinition of the
dynamical variables, can be turned into very efficient analogs of the
fundamental scenarios that are supposed to be responsible for the GUPs that
the high energy physics community is eagerly looking for. This seems
promising, especially in the light of how simple our recipe is and of how
difficult it is to run high energy experiments.

## Acknowledgements

A. I. and P. P. sincerely thank Thomas Elze and the other organizers of
DICE2022, for a wonderful and very productive conference. They gladly
acknowledge the financial support of Charles University Research Center
(UNCE/SCI/013). P. P. is also supported by Fondo Nacional de Desarrollo
Científico y Tecnológico–Chile (Fondecyt Grant No. 3200725). S. M.
acknowledges support from COST action CA18108.

## References

  * [1] Seiberg N and Witten E 1999 JHEP 1999 032 (Preprint eprint hep-th/9908142)
  * [2] Madore J, Schraml S, Schupp P and Wess J 2000 Eur. Phys. J. C16 161
  * [3] Iorio A and Sỳkora T 2002 Int. J. Mod. Phys. A17 2369
  * [4] Iorio A 2008 Phys. Rev. D77 048701
  * [5] Guralnik Z, Jackiw R, Pi S and Polychronakos A 2001 Phys. Lett. B517 450
  * [6] Jackiw R 2002 Nucl. Phys. B Proc. Suppl. 108 30
  * [7] Castorina P, Iorio A and Zappala D 2004 Phys. Rev. D69 065008
  * [8] Colladay D and Kostelecky V A 1998 Phys. Rev. D 58 116002 (Preprint eprint hep-ph/9809521)
  * [9] Iorio A 2007 J. Phys. Conf. Ser. 67 012008
  * [10] Maggiore M 1993 Phys. Lett. B 304 65 (Preprint eprint hep-th/9301067)
  * [11] Kempf A 1994 J. Math. Phys. (NY) 35 4483 (Preprint eprint hep-th/9311147)
  * [12] Scardigli F 1999 Phys. Lett. B 452 39 (Preprint eprint hep-th/9904025)
  * [13] Scardigli F 2022 Uncertainty principle and gravity (Preprint eprint 2212.13776)
  * [14] Das S and Vagenas E C 2008 Phys. Rev. Lett. 101(22) 221301
  * [15] Ali A F, Das S and Vagenas E C 2011 Phys. Rev. D84 044013 (Preprint eprint 1107.3164)
  * [16] Ali A F, Das S and Vagenas E C 2009 Phys. Lett. B678 497
  * [17] Ali A F, Das S and Vagenas E C 2010 Phys. Lett. B690 407
  * [18] Buoninfante L, Luciano G G and Petruzziello L 2019 Eur. Phys. J. C79 663 (Preprint eprint 1903.01382)
  * [19] Petruzziello L and Illuminati F 2021 Nature Commun. 12 4449 (Preprint eprint 2011.01255)
  * [20] Bosso P and Luciano G G 2021 Eur. Phys. J. C 81 982 (Preprint eprint 2109.15259)
  * [21] Muñoz de Nova J R, Golubkov K, Kolobov V I and Steinhauer J 2019 Nature 569 688
  * [22] Iorio A 2011 Ann. Phys. (Amsterdam) 326 1334
  * [23] Iorio A 2102 Eur. Phys. J. Plus 127 156
  * [24] Iorio A and Lambiase G 2012 Phys. Lett. B716 334
  * [25] Iorio A and Lambiase G 2014 Phys. Rev. D 90 025006
  * [26] Iorio A 2015 Int. J. Mod. Phys. D24 1530013
  * [27] Gooth J, Niemann A C, Meng T, Grushin A G, Landsteiner K, Gotsmann B, Menges F, Schmidt M, Shekhar C, Süß V, Hühne R, Rellinghaus B, Felser C, Yan B and Nielsch K 2017 Nature 547 324–327
  * [28] Iorio A and Pais P 2015 Phys. Rev. D 92 125005
  * [29] Iorio A and Pais P 2022 Phys. Rev. B106 157401
  * [30] Iorio A and Pais P 2018 Ann. Phys. (Amsterdam) 398 265
  * [31] Iorio A 2015 Front. Mater. 1 36 (Preprint eprint 1412.5160)
  * [32] Iorio A, Lambiase G, Pais P and Scardigli F 2020 Phys. Rev. D 101(10) 105002
  * [33] Castro Neto A H, Guinea F, Peres N M R, Novoselov K S and Geim A K 2009 Rev. Mod. Phys. 81 109
  * [34] Wehling T, Black-Schaffer A and Balatsky A 2014 Adv. Phys. 63 1–76
  * [35] Iorio A, Ivetić B, Mignemi S and Pais P 2022 Phys. Rev. D106 116011
  * [36] Iorio A, Pais P, Elmashad I A, Ali A F, Faizal M and Abou-Salem L I 2018 Int. J. Mod. Phys. D27 1850080 (Preprint eprint 1706.01332)
  * [37] Iorio A and Pais P 2019 J. Phys. Conf. Ser. 1275 012061 (Preprint eprint 1902.00116)


# Neural Sequence-to-grid Module for Learning Symbolic Rules

Segwang Kim, 1 Hyoungwook Nam, 2 Joonyoung Kim, 1 Kyomin Jung1

###### Abstract

Logical reasoning tasks over symbols, such as learning arithmetic operations
and computer program evaluations, have become challenges to deep learning. In
particular, even state-of-the-art neural networks fail to achieve out-of-
distribution (OOD) generalization of symbolic reasoning tasks, whereas humans
can easily extend learned symbolic rules. To resolve this difficulty, we
propose a neural sequence-to-grid (seq2grid) module, an input preprocessor
that automatically segments and aligns an input sequence into a grid. As our
module outputs a grid via a novel differentiable mapping, any neural network
structure taking a grid input, such as ResNet or TextCNN, can be jointly
trained with our module in an end-to-end fashion. Extensive experiments show
that neural networks having our module as an input preprocessor achieve OOD
generalization on various arithmetic and algorithmic problems including number
sequence prediction problems, algebraic word problems, and computer program
evaluation problems while other state-of-the-art sequence transduction models
cannot. Moreover, we verify that our module enhances TextCNN to solve the bAbI
QA tasks without external memory.

## Introduction

Symbolic reasoning tasks such as learning arithmetic operations or evaluating
computer programs offer solid standards for validating the logical inference
abilities of deep learning models. Among machine learning tasks, symbolic
reasoning problems are apt for testing mathematical, algorithmic, and
systematic reasoning as they have strict rules mapping a given input to a
well-defined unique target. In particular, a large body of works on deep
learning has considered sequence transduction problems for symbolic reasoning.
Some symbolic problems such as copying sequences (Dehghani et al. 2018;
Graves, Wayne, and Danihelka 2014; Grefenstette et al. 2015; Rae et al. 2016;
Zaremba and Sutskever 2014) and arithmetic addition (Graves, Wayne, and
Danihelka 2014; Joulin and Mikolov 2015; Kaiser and Sutskever 2015;
Kalchbrenner, Danihelka, and Graves 2015; Saxton et al. 2019; Wangperawong
2018) can be solved after understanding simple rules regardless of the inputs.
Others demand a deep learning model to discover necessary rules and apply them
depending on inputs given as natural language words (Li et al. 2019; Wang,
Liu, and Shi 2017; Weston et al. 2015), complex mathematical equations (Lample
and Charton 2019), or programming snippets (Zaremba and Sutskever 2014).

Among them, symbolic reasoning problems can test whether a trained deep
learning model can systematically extend rules to out-of-distribution (OOD)
data that follow a distinct distribution from the training data (Keysers et
al. 2019; Lake and Baroni 2017; Saxton et al. 2019). For instance, a model for
the addition problem whose training inputs are a pair of numbers up to five
digits, say 5872+13, can face an OOD input of a pair of two 6-digit numbers
upon the testing phase, e.g., 641436+135321. Human intelligence with algebraic
mind can naturally extend learned rules (Marcus 2003), yet it is non-trivial
to equip deep learning models for sequence transduction problems to handle OOD
generalization.

However, it has been found that popular sequence transduction neural networks,
such as LSTM seq2seq model (Sutskever, Vinyals, and Le 2014) and Transformer
(Vaswani et al. 2017), rarely extend learned rules in that they are inclined
to mimic the training data distribution (Dehghani et al. 2018; Lake and Baroni
2017). There have been significant initial efforts to improve a model’s
abilities to extend learned rules. However, their success has been dependent
on the direct use of numerical values (Trask et al. 2018) or has been limited
to rudimentary logic such as copying sequences (Dehghani et al. 2018; Graves,
Wayne, and Danihelka 2014; Grefenstette et al. 2015; Rae et al. 2016; Zaremba
and Sutskever 2014) and binary arithmetic (Graves, Wayne, and Danihelka 2014;
Joulin and Mikolov 2015; Kaiser and Sutskever 2015). Furthermore, OOD
generalization on symbolic problems for complex or context-dependent logic
forms such as decimal arithmetic, algebraic word problems, computer program
evaluation problems has not been tackled. Our objective is to fill this gap
and design a module that helps neural networks to achieve OOD generalization
in these problems.

One observation from a previous study (Nam, Kim, and Jung 2019) is that
typical sequence transduction neural networks cannot process OOD instances of
number sequence prediction problems, such as predicting a Fibonacci sequence.
However, when an input sequence is manually segmented and aligned into a grid
of digits, a CNN can easily process OOD instances. This means providing the
aligned grid input enables to exploit inductive bias by the convolution’s
local and parallel computation. The grid, however, must be handcrafted in the
study, which is inapplicable for general sequence transduction tasks.
Overcoming this limitation requires a new input preprocessing module that
automatically aligns an input sequence into a grid without supervision for the
alignment.

In this work, we propose a neural sequence-to-grid (seq2grid) module, an input
preprocessor that learns how to segment and align an input sequence into a
grid. The grid syntactically aligned by our module is then semantically
decoded by a neural network. In particular, our module produces a grid by a
novel differentiable mapping called nested list operation inspired by Stack
RNN (Joulin and Mikolov 2015). This mapping enables a joint training of our
module and the neural network in an end-to-end fashion via a backpropagation.

Experimental results show that ResNets with our seq2grid module achieve OOD
generalization on various arithmetic and algorithmic reasoning problems, such
as number sequence prediction problems, algebraic word problems, and computer
program evaluation problems. These are nearly impossible for other
contemporary sequence-to-sequence models including LSTM seq2seq models and
Transformer-based models. Specifically, we find that the seq2grid can infuse
an input context into a grid so that doing arithmetic under linguistic
instructions or selecting the true branch of if/else statements in code
snippets become possible. Further, we demonstrate that the seq2grid module can
enhance TextCNN to solve the bAbI QA tasks without the help of external
memory. From all the aforementioned problems, we verify the generality of the
seq2grid module in that it automatically preprocesses the sequential input
into the grid input in a data-driven way.

## Motivation for Sequence-to-grid Method

Figure 1: The illustration of the toy decimal addition problem. Each symbol is
stored with its representation vector.

Figure 2: The validation accuracy results of the toy problem. Each column
shows results from the $k$-digit set, where the three rightmost sets are OOD.

To demonstrate the benefits of the sequence-to-grid preprocessing method for
symbolic reasoning tasks, we devise a toy decimal addition problem in two
different setups: sequential and grid-structured. Figure 2 illustrates how the
problem is defined in both setups and shows why alignment on a grid makes it
easier. If the lengths of the numbers increase, the temporal distances between
corresponding digits, e.g., 2 and 3, also increase in the sequential setup.
However, the spatial distances between them remain constant in the grid-
structured setup since they are manually aligned according to their digits.
Therefore, we can expect that the local and parallel nature of convolution
will extend the rule to longer inputs, while sequence transduction models will
struggle to handle the increased distances.

To see this, we trained deep learning models111The models had the same
configurations used in arithmetic and algorithmic problems (refer to
experiments) except for the CNN that was the grid decoder of the S2G-CNN.
using numbers up to five digits and validate on six separate validation sets,
each of which contains only $k$-digit ($k\\!=\\!3,\dots,8$) numbers. Hence,
the validation results from the former three sets tested in-distribution (ID)
generalization, whereas the latter three tested OOD generalization. While the
input and the target in the sequential setup were sequentially fed to sequence
transduction models such as LSTM seq2seq model (Sutskever, Vinyals, and Le
2014) and Transformer (Vaswani et al. 2017), those in the grid-structured
setup were fed to a ResNet-based CNN model (He et al. 2016). As expected,
Figure 2 shows that extending the addition rule to OOD validation sets is easy
in the grid-structured setup, whereas it is extremely difficult in the
sequential setup.

Therefore, providing aligned grid input for local and parallel computation can
be key to achieving OOD generalization. However, manual preprocessing that
aligns an input sequence into a grid is impossible for most symbolic problems.
For instance, in computer program evaluation problems, symbols within the code
snippet can represent not only integers but also programming instructions so
that it is non-trivial to manually align those symbols on the grid. Likewise,
in the bAbI QA tasks, questions and stories given as natural language have no
ground-truth alignment which we can exploit for preprocessing in advance.
Accordingly, we need a data-driven preprocessing method that automatically
aligns an input symbol sequence into a grid for general symbolic tasks. We
implement it by designing a sequence-to-grid module executing novel nested
list operations.

## Related Work

#### Symbolic Reasoning Tasks

Symbolic reasoning requires discovering the underlying rules of a data
distribution rather than mimicking data patterns. Hence, there have been
studies to formulate symbolic reasoning tasks in machine learning problems to
examine the mathematical and systematic (rule-based) reasoning abilities of
deep learning models. Additions of unprecedented long binary numbers (Graves,
Wayne, and Danihelka 2014; Joulin and Mikolov 2015; Kaiser and Sutskever 2015)
or Number sequence prediction problems (Nam, Kim, and Jung 2019) are studied.
Also, school-level math problems including algebraic word problems are unified
(Saxton et al. 2019). Evaluating program snippets (Zaremba and Sutskever 2014)
further requires algorithmic abilities. Besides extending mathematical rules,
systematic generalization abilities in synthetic natural language tasks are
tested by the bAbI QA tasks (Weston et al. 2015) or the SCAN problems (Lake
and Baroni 2017).

#### Memory Augmented Neural Network

Storing all input information into external memory and querying over it is one
way to tackle symbolic reasoning tasks. Such neural networks, also known as
memory augmented neural networks (MANN), vary according to their memory
structures and controllers. Here, the memory controller is a neural network
that reads an input symbol and its external memory, encodes the symbol, and
write it on the memory. After the incipient MANNs like Memory network
(Sukhbaatar et al. 2015) were introduced, studies about implementing Automata
with differentiable tape as neural networks (Graves et al. 2016; Rae et al.
2016; Joulin and Mikolov 2015; Grefenstette et al. 2015) has been carried out.
We emphasize that our preprocessed grid input can be seen as another
representation of a sequential input rather than a memory used in MANNs; the
RNN encoder of our module does not read the grid and the symbol embedding is
directly written to the grid rather than passed through neural network layers.

#### Neural-Symbolic Learning

Another approach for OOD generalization in symbolic problems is Neural-
Symbolic-approach that integrates the connectionist and the symbolist
paradigms. Neural Programmer Interpreter (NPI) (Reed and De Freitas 2015) and
its recursion variant (Cai, Shin, and Song 2017) have been proposed for
solving compositional programs through sequential subprograms. Also, (Chen,
Liu, and Song 2017) proposes a reinforcement learning-based approach with
structured parse-trees. Recently, Neural Symbolic Reader (Chen et al. 2019)
trains models with weak supervision for generalization. However, our approach
via automatic alignment without domain-specific knowledge is distinct from
neural-symbolic approaches which require all of the supervision for sequential
sub-operations.

## Method

In this section, we first describe a sequence-input grid-output architecture
consisting of a neural sequence-to-grid (seq2grid) module and a grid decoder.
Then, we introduce how the seq2grid module preprocesses a sequence input as a
grid input. Finally, we explain nested list operations that are executed by
the seq2grid module.

### Sequence-input Grid-output Architecture

The key idea of the sequence-to-grid method is to decouple symbolic reasoning
into two steps: automatically aligning an input sequence into a grid, and
doing semantic computations over the grid. Hence, we propose the sequence-
input grid-output architecture consisting of a seq2grid module and a grid
decoder as shown in Figure 3. The seq2grid module preprocesses a sequential
input into a grid input. The grid decoder, a neural network that can handle
two-dimensional inputs, predicts the target from the grid input. Practically,
we choose the grid decoder like ResNet or TextCNN according to problems. Note
that our approach that separates the syntactic (=alignment) and semantic
processing is similar to the syntactic attention (Russin et al. 2020).

Figure 3:  The sequence-input grid-output architecture.

### Neural Sequence-to-grid Module

The main challenge for implementing the seq2grid module is that the grid must
be formed via differentiable mappings to ensure an end-to-end training. To do
so, we design the seq2grid module with an RNN encoder that gives an action
sequence for differentiable nested list operations.

Formally, the seq2grid module works as follows. First, for an input sequence
given as symbol embeddings $E^{(t)}\in\mathbb{R}^{h}$ where $t=1,\dots,T$, the
RNN encoder maps $(E^{(t)},r^{(t-1)})$ into $r^{(t)}\in\mathbb{R}^{h}$. Then,
a dense layer followed by a softmax layer computes an action: $r^{(t)}\mapsto
a^{(t)}\in\mathbb{R}^{3}$. Next, starting from the zero-initialized grid
$G^{(0)}\in(\mathbb{R}^{h})^{W{\times}H}$, a series of nested list operations
sequentially push the input symbol $E^{(t)}$ into the previous grid
$G^{(t-1)}$ in different extents under the action $a^{(t)}$. As a result, we
obtain the grid input $G^{(T)}\in(\mathbb{R}^{h})^{W{\times}H}$ that will be
fed through a grid decoder. Note that all aforementioned mappings are
differentiable including nested list operations which we will explain below.

### Nested List Operations

To understand how the nested list operations work, we first regard the grid
${G}\in(\mathbb{R}^{h})^{H\times W}$ as a nested list consisting of $H$ lists
of $W$ slots, where each slot is a vector of dimension $h$. We denote the
$i$-th list as ${G}_{i}\in(\mathbb{R}^{h})^{W}$ where ${G}_{1}$ is the top
list. Likewise, the $j$-th slot vector in the $i$-th list is denoted as
${G}_{i,j}\in\mathbb{R}^{h}$ where ${G}_{i,1}$ is the leftmost slot of the
$i$-th list.

Now, we define a differetiable map that pushes the input symbol
$E^{(t)}\in\mathbb{R}^{h}$ into the grid under the action
$a^{(t)}\in\mathbb{R}^{3}$. Here, each component of
$a^{(t)}=(a^{(t)}_{TLU},a^{(t)}_{NLP},a^{(t)}_{NOP})$ is the probability of
performing one of three nested list operations: top-list-update
($a^{(t)}_{TLU}$), new-list-push ($a^{(t)}_{NLP}$), and no-op
($a^{(t)}_{NOP}$). As shown in Figure 4, ${G}^{(t-1)}$ with
$(E^{(t)},a^{(t)})$ grows to ${G}^{(t)}$:

$\displaystyle{G}^{(t)}=a^{(t)}_{TLU}{TLU}^{(t)}+a^{(t)}_{NLP}{NLP}^{(t)}+a^{(t)}_{NOP}{G}^{(t-1)},$
$\displaystyle\mbox{where }{TLU}^{(t)}\in(\mathbb{R}^{h}$
$\displaystyle)^{H\times W}\mbox{ is defined as}$
$\displaystyle{TLU}^{(t)}_{1,1}$ $\displaystyle=E^{(t)},$
$\displaystyle{TLU}^{(t)}_{1,j}$
$\displaystyle={G}^{(t-1)}_{1,j-1}\qquad\text{for }j>1,$
$\displaystyle{TLU}^{(t)}_{i}$ $\displaystyle={G}^{(t-1)}_{i}\qquad\text{for
}i>1,$ $\displaystyle\mbox{and }{NLP}^{(t)}\in(\mathbb{R}^{h}$
$\displaystyle)^{H\times W}\mbox{ is defined }\mbox{as}$
$\displaystyle{NLP}^{(t)}_{1}$
$\displaystyle=(E^{(t)},E_{\emptyset},\dots,E_{\emptyset}),$
$\displaystyle{NLP}^{(t)}_{i}$ $\displaystyle={G}^{(t-1)}_{i-1}\qquad\text{for
}i>1.$

Here, $E_{\emptyset}:=\boldsymbol{0}\in\mathbb{R}^{h}$ is the empty symbol
$\emptyset$. Accordingly, the zero-initialized grid
$G^{(0)}=(E_{\emptyset},\dots,E_{\emptyset})$ grows to the final grid
$G^{(T)}$ as time goes. By doing so, we “preprocess” the input sequence into
the grid input in that each slot of $G^{(T)}$ holds nothing but a weighted sum
of input symbols.

Figure 4:  The nested list $G^{(t-1)}$ grows to $G^{(t)}$ by the action
$a^{(t)}=(a^{(t)}_{TLU},a^{(t)}_{NLP},a^{(t)}_{NOP})$. $TLU^{(t)}$ and
$NLP^{(t)}$ show outputs of top-list-update and new-list-push operations.

## Experimental Setup

We evaluated the seq2grid module on symbolic problems whose targets are given
as sequences or single labels. To this end, we built neural network models,
such as S2G-CNN and S2G-TextCNN, that followed the sequence-input grid-output
architecture by varying the grid decoder according to target modalities of
problems. Refer to each problem section for our grid decoder choices and their
training losses.

We compared our models with five baselines: Transformer (Vaswani et al. 2017),
Universal Transformer (UT) (Dehghani et al. 2018) with dynamic halting222The
UT can take different ponder time for each position., a LSTM seq2seq model
(LSTM) (Sutskever, Vinyals, and Le 2014), a LSTM seq2seq attention model with
a bidirectional encoder (LSTM-Atten) (Bahdanau, Cho, and Bengio 2014) and a
Relational Memory Core seq2seq model (RMC) (Santoro et al. 2018). The
Transformer and the UT consisted of two layers with the hidden size 128 and
four attention heads. The LSTM, the LSTM-Atten, and the RMC had three layers
with the hidden size 1024, 512, and 512 each.

We determined configurations of our models by hyperparameter sweeping for each
problem. Our implementations333https://github.com/SegwangKim/neural-seq2grid-
module based on the open source library
tensor2tensor444https://github.com/tensorflow/tensor2tensor contain detailed
training schemes and hyperparameters of our models and the baselines. All
models could fit in a single NVIDIA GTX 1080ti GPU.

The next three sections follow the same organization to illustrate the
experiments and their results. First, we introduce a set of symbolic reasoning
tasks by describing the layouts of the inputs and the targets. Next, we
describe our grid decoder architecture to solve such problems, which is
combined with the seq2grid module to follow the sequence-input grid-output
architecture. Finally, we analyze the experimental results and discuss their
implications.

## Arithmetic and Algorithmic Problems

Figure 5:  The grid decoder of S2G-CNN. Only the top list of the grid from
bottleneck blocks is passed to the logit layer. The raw target 29 is flipped
and padded to 92$\emptyset$.

Arithmetic and algorithmic problems are useful to test abilities to extend
rules on longer inputs since the input contains digits. We test our models on
three different arithmetic and algorithmic inference problems. Each problem
consists of a training set and two test sets randomly sampled from
distributions controlled by difficulty parameters. Two test sets represent in-
distribution data (ID) and OOD data (OOD). Difficulty parameters of the
training set can be overlapped with those of the ID test set, but instances of
the two sets are strictly separated by their hash codes. The training set of
all problems contains 1M random examples and the two test sets contain 10K
examples each. We tokenize all inputs and targets by characters and decimal
digits. We score the output by sequence-level accuracy, i.e., whether the
output entirely matches the target sequence. For convenience, we denote
$\langle$EOS$\rangle$ as $.

#### Number Sequence Prediction

As the name suggests, the goal of the number sequence prediction problem (Nam,
Kim, and Jung 2019) is to predict the next term of an integer sequence. After
randomly choosing three initial terms, we generate a sequence via the
recursion $a_{n}=2a_{n-1}-a_{n-2}+a_{n-3}$ which progresses the sequence up to
the $n$th term. The input is the first $n$ terms $a_{0},\dots,a_{n-1}$ and the
target is the last term $a_{n}$. The difficulty of the instance is
parameterized by the maximum number of digits of the initial terms
$a_{0},\dots,a_{k-1}$, i.e., length, and the total number of input integer
terms $n$, i.e., $\\#$terms. Those two difficulty parameters, length and
$\\#$terms, vary (1-4, 4-6), (4, 4-6), and (6, 10-12) for the training set,
the ID test set, and the OOD test set, respectively. The input and the target
of a training example are as follows.

Input: 7008 -205 4 7221$ Target: 14233$

#### Algebraic Word Problem

To test the arithmetic abilities under linguistic instructions, we choose
algebraic word problems, i.e., add-or-sub word, (Saxton et al. 2019). The
difficulty of the problems is controlled by entropy, the number of digits
within a question. Here, we make two differences from the original dataset.
First, we only allow integers whereas floating-point numbers can appear
originally. Second, our entropy is the total number of digits in the input,
whereas the original entropy is the maximum number of digits that input can
have. Our entropy varies 16-20, 16-20, and 32-40 for the training set, the ID
test set, and the OOD test set, respectively. In the OOD test, we also impose
every integer to be of length above 16 to guarantee that it is longer than any
integers in the training set. The input and the target of a training example
are as follows.

Input: What is -784518 take away 7323?$ Target: -791841$

#### Computer Program Evaluation

Predicting the execution results of programs requires algorithmic reasoning
such as doing arithmetic operations or following programming instructions like
variable assignments, branches, and loops. We use mixed strategy (Zaremba and
Sutskever 2014) to generate the training data with nesting 2 and length 5\.
For the ID test set and the OOD test set, nesting and length are set to be (2,
5) and (2, 7), respectively. The input, a random Python snippet, and the
target, the execution result, of a training example are as follows.

Input: j=891 for x in range(11):j-=878 print((368 if 821<874 else j))$ Target:
368$

### Grid Decoder

For solving arithmetic and algorithmic problems with digits, it is desirable
to choose a grid decoder that can do local and parallel computation.
Therefore, we implemented a CNN (He et al. 2016) consisting of three stacks of
3-layer bottleneck building blocks of ResNet. Also, we implemented its
attentional variant ACNN (Ramachandran et al. 2019); every $3{\times}3$
convolution of the CNN was substituted with a stand-alone self-attention
convolution. We used $3{\times}25$-sized grids from the seq2grid module having
3-layered GRU encoder of hidden size 128 for both decoders. As shown in Figure
5, we measured cross-entropy loss between the flipped-and-padded target and
the output from the logit layer. Here, the loss for empty symbol $\emptyset$
was included as we read out logits backward in the inference stage. We jointly
trained the seq2grid module and the CNN (ACNN) by the ADAM optimizer (Kingma
and Ba 2014) with a learning rate $1e^{-3}$.

### Results

| Sequence |  | Add-or-sub |  | Program
---|---|---|---|---|---
| ID | OOD |  | ID | OOD |  | ID | OOD
Baselines |  |  |  |  |  |  |  |
LSTM | 0.21 | 0.00 |  | 0.99 | 0.00 |  | 0.25 | 0.07
LSTM-Atten | 0.68 | 0.00 |  | 1.00 | 0.00 |  | 0.37 | 0.01
RMC | 0.01 | 0.00 |  | 0.99 | 0.00 |  | 0.33 | 0.01
Transformer | 0.97 | 0.00 |  | 0.97 | 0.00 |  | 0.37 | 0.00
UT | 1.00 | 0.00 |  | 1.00 | 0.00 |  | 0.62 | 0.00
Ours |  |  |  |  |  |  |  |
S2G-CNN | 0.96 | 0.99 |  | 0.98 | 0.53 |  | 0.51 | 0.33
S2G-ACNN | 0.90 | 0.92 |  | 0.96 | 0.55 |  | 0.44 | 0.35

Table 1: Best sequence-level accuracy (out of 5 runs) on number sequence
prediction problems (sequence), algebraic word problems (Add-or-sub), and
computer program evaluation problems (Program)

Figure 6:  Visualizations of preprocessed grid inputs of (a) number sequence prediction problems and (b) computer program evaluation problems. The top and the bottom row correspond to S2G-CNN and S2G-ACNN, respectively.  | instruction | ID | OOD
---|---|---|---
LSTM-Atten | if-else | 0.46 | 0.26
for | 0.06 | 0.03
* | 0.07 | 0.04
UT | if-else | 0.81 | 0.01
for | 0.38 | 0.00
* | 0.52 | 0.00
S2G-CNN | if-else | 0.73 | 0.57
for | 0.20 | 0.09
* | 0.25 | 0.14
Table 2:  Accuracy by instruction types of the best runs on the computer
program evaluation problems. For example, the S2G-CNN correctly answers 73% of
all ID snippets containing IF-ELSE instructions.

print((11*7288719))
---
print(((6110039 if 7327755<3501784 else
1005398)*11))
b=6367476
for x in range(19):b-=9082877
print((3569363 if 7448172<9420320 else b))
e=(450693 if 4556818<2999168 else 3618338)
for x in range(10):e-=4489485
print(e)

Figure 7:  Some OOD code snippets correctly answered by the best run of the
S2G-CNN. Note that snippets contain FOR or * instruction requiring non-linear
time complexity.

Table 1 shows that our models, S2G-CNN and S2G-ACNN, can generalize on OOD
test sets. In particular, both grid decoders achieve similar OOD
generalization, implying that feeding the grid input via our seq2grid module
can be beneficial to any decoder that can do local and parallel computations.
On the other hand, all baselines catastrophically fail at the OOD test sets
although they seemingly perform well on the ID test set. This shows that
extending rules to longer numbers via sequential processing is extremely
difficult.

As for the number sequence prediction problems, their OOD test results serve
as unit tests for the seq2grid module since it needs to align digit symbols on
the grid according to their scales. Indeed, Figure 6a shows that our module
automatically finds such alignments that resemble the tailored grid of digits
as shown in Figure 2.

For the algebraic word problems, they require context-dependent arithmetic
unlike number sequence prediction problems using the fixed progression rules.
In particular, linguistic instructions like add or take away indicates how to
add/subtract given two numbers in a specific order. Since our grid decoders
apply the fixed convolutional filters over the grid, linguistic instructions
must be reflected in the grid input beforehand for doing context-dependent
arithmetic. This shows that our seq2grid module can infuse the instruction
information into the grid input.

For the computer program evaluation problems, predicting the output of a code
snippet demands an understanding of algorithmic rules like branching
mechanisms or for-loop given as programming instructions IF-ELSE or FOR. Also,
computing * operations has non-linear time complexity, unlike addition or
subtraction. Hence, we further investigate accuracy on snippets by those
instructions as shown in Table 2. For the OOD snippets containing IF-ELSE
instructions, our S2G-CNN achieves 57% accuracy for them. Considering that
they can contain other instructions besides branching one as shown in Figure
7, the accuracy is fairly high. For the non-linear operations, the S2G-ACNN
shows little understanding compared with the UT on the ID test set. However,
the UT fails to extend rules of FOR and * instructions on the OOD test set
while the S2G-CNN does so on some examples as shown in Figure 7. These are
surprising in that both the seq2grid module and the ACNN grid decoder do
linear time computations in the input length.

## bAbI QA Tasks

Given as natural language with a small vocabulary of around 170, the bAbI QA
tasks (Weston et al. 2015) test 20 types of simple reasoning abilities such as
counting, induction, deduction, and path-finding. A problem instance consists
of a story, a question, and the answer. Here, the story contains supporting
sentences about the answer and distractors that are irrelevant sentences to
the answer.

Figure 8:  Input examples of the bAbI QA tasks.

We formulate the bAbI QA tasks (Weston et al. 2015) in a sequence
classification setup such that an input is a concatenation of
$\langle$CLS$\rangle$ token, a question, $\langle$SEP$\rangle$ token, and a
story as shown in Figure 8. While previous work (Dehghani et al. 2018) uses
sentence-level encodings, we use straightforward one-hot word-level encodings.
This setup yields the increase of the average input length from 13.6 to 78.9,
which in turn requires to handle much longer dependencies. Hence, solving the
bAbI tasks under word-level encodings is much harder than those under
sentence-level encodings. State-of-the-art models deal with longer
dependencies via augmenting neural networks with external memory (Munkhdalai
et al. 2019; Rae et al. 2016). However, we will show that the seq2grid module
can enhance a simple neural network like TextCNN to effectively solve the
word-level bAbI tasks, even in the absence of a complex and expensive memory
structure.

### Grid Decoder

We chose a grid decoder as a variant of TextCNN (Kim 2014). After the seq2grid
module having 2-layered GRU encoders of hidden size 128 gave the
$4{\times}8$-sized grid input, our TextCNN predicted the label by applying
$k{\times}k$-CNNs ($k=2,3,4$), max-pooling, and dropout with the rate $0.4$ as
shown in the Figure 9. We used the ADAM optimizer to jointly train the
seq2grid module and the TextCNN under a warm-up and decay learning rate
scheme3.

Figure 9:  The grid decoder of S2G-TextCNN.

|  $\\#$params | Error |  $\\#$Failed tasks
---|---|---|---
Baselines555We use only encoders of baselines used in arithmetic and algorithmic problems. As for the logit, LSTM uses the last hidden state while others use the hidden one corresponding to $\langle$CLS$\rangle$ token. |  |  |
LSTM | 25.6M | $24.9\pm 5.8$ | $12.1\pm 3.7$
Transformer | 0.5M | $33.1\pm 1.7$ | $18.9\pm 0.3$
UT | 0.5M | $26.8\pm 6.0$ | $15.0\pm 4.0$
TextCNN | 0.2M | $37.8\pm 0.4$ | $19.0\pm 0.0$
Ours |  |  |
S2G-TextCNN | 0.8M | $10.8\pm 0.8$ | $6.0\pm 0.0$

Table 3: Error and $\\#$Failed tasks ($>\\!5\%$ error) on the bAbI QA 10k
joint tasks (for 10 runs).

|  | Baselines |  | Ours
---|---|---|---|---
Task | #supps | LSTM | UT |  | S2G-
| TextCNN
1: single-supporting-fact | 1.0 | 0.0 | 0.0 |  | 0.0
2: two-supporting-facts | 2.0 | 47.4 | 55.0 |  | 31.2
3: three-supporting-facts | 3.0 | 45.9 | 67.9 |  | 31.5
4: two-arg-relations | 1.0 | 0.1 | 0.0 |  | 0.0
5: three-arg-relations | 1.0 | 0.8 | 5.5 |  | 1.0
6: yes-no-questions | 1.0 | 0.5 | 0.1 |  | 0.0
7: counting | 2.3 | 1.8 | 4.0 |  | 0.0
8: lists-sets | 1.9 | 0.2 | 2.3 |  | 1.8
9: simple-negation | 1.0 | 0.0 | 0.0 |  | 0.0
10: indefinite-knowledge | 1.0 | 0.3 | 0.0 |  | 0.0
11: basic-coreference | 2.0 | 0.0 | 0.1 |  | 0.0
12: conjunction | 1.0 | 0.0 | 0.0 |  | 0.0
13: compound-coreference | 2.0 | 0.0 | 0.0 |  | 0.0
14: time-reasoning | 2.0 | 20.6 | 4.4 |  | 7.3
15: basic-deduction | 2.0 | 34.8 | 18.5 |  | 0.0
16: basic-induction | 3.0 | 52.1 | 53.6 |  | 51.7
17: positional-reasoning | 2.0 | 41.1 | 41.0 |  | 31.4
18: size-reasoning | 2.0 | 8.6 | 9.1 |  | 3.8
19: path-finding | 2.0 | 90.9 | 79.1 |  | 35.1
20: agents-motivations | 1.0 | 1.8 | 1.4 |  | 0.0
Mean error (%) |  | 17.3 | 17.1 |  | 9.7
#Failed tasks |  | 8 | 8 |  | 6

Table 4: Task-wise errors on the bAbI QA 10k joint tasks for the best runs.
#supps is the average number of supporting sentences in the story.

### Results

Our S2G-TextCNN outperforms sequential baseline models, such as the LSTM, the
Transformer encoder, and the UT encoder, as shown in Table 3. Note that we fed
word-level inputs that require doing reasoning over distant symbols, i.e., the
average length of inputs is 78.9, and we used the grid that has only 32
$(=\\!4{\times}8)$ slots. From these setups, we can conclude that our module
can compress long inputs into grid inputs while selecting only necessary words
along story arcs. Moreover, the compression is effective in terms of the
number of parameters. Indeed, the GRU encoder inside our module is much
smaller than the LSTM but enough to provide grid inputs to our grid decoder
for solving the bAbI tasks.

We highlight that our seq2grid module, not the TextCNN decoder, leads to the
superior performance of our model. Since the attempt to use the usual TextCNN
alone fails at almost all tasks, the dramatic performance gain by the aid of
the seq2grid module is somewhat surprising.

We further analyze errors by tasks to see the possibility and the limitation
of our sequence-to-grid method. The zero variance in the number of failed
tasks (Table 3) indicates that the S2G-TextCNN consistently fails on the same
set of tasks, as listed in Table 4. Those failed tasks including two-
supporting-facts, positional reasoning, and path-finding seem reasonably
difficult for our models in that all of them require more than one supporting
sentence for the reasoning.

## Conclusion

We introduced a neural sequence-to-grid (seq2grid) module which automatically
segments and aligns an sequential input into a grid. Our module was used as an
input preprocessor for a neural network that took a grid input. In particular,
our module executed our novel nested list operations, ensuring an end-to-end
joint training with the neural network. Empirically, our module enhanced
neural networks in various symbolic reasoning tasks.

## Acknowledgements

The authors appreciate Hyunkyung Bae for assistance with experiments. K. Jung
is with ASRI and ECE, Seoul National University, Korea. This work was
supported by Samsung Research Funding $\&$ Incubation Center of Samsung
Electronics under Project Number SRFCIT1902-06.

## References

  * Bahdanau, Cho, and Bengio (2014) Bahdanau, D.; Cho, K.; and Bengio, Y. 2014.  Neural machine translation by jointly learning to align and translate.  _arXiv preprint arXiv:1409.0473_ .
  * Cai, Shin, and Song (2017) Cai, J.; Shin, R.; and Song, D. 2017.  Making neural programming architectures generalize via recursion.  _arXiv preprint arXiv:1704.06611_ .
  * Chen et al. (2019) Chen, X.; Liang, C.; Yu, A. W.; Zhou, D.; Song, D.; and Le, Q. V. 2019.  Neural symbolic reader: Scalable integration of distributed and symbolic representations for reading comprehension.  In _International Conference on Learning Representations_.
  * Chen, Liu, and Song (2017) Chen, X.; Liu, C.; and Song, D. 2017.  Towards synthesizing complex programs from input-output examples.  _arXiv preprint arXiv:1706.01284_ .
  * Dehghani et al. (2018) Dehghani, M.; Gouws, S.; Vinyals, O.; Uszkoreit, J.; and Kaiser, Ł. 2018.  Universal transformers.  _arXiv preprint arXiv:1807.03819_ .
  * Graves, Wayne, and Danihelka (2014) Graves, A.; Wayne, G.; and Danihelka, I. 2014.  Neural turing machines.  _arXiv preprint arXiv:1410.5401_ .
  * Graves et al. (2016) Graves, A.; Wayne, G.; Reynolds, M.; Harley, T.; Danihelka, I.; Grabska-Barwińska, A.; Colmenarejo, S. G.; Grefenstette, E.; Ramalho, T.; Agapiou, J.; et al. 2016.  Hybrid computing using a neural network with dynamic external memory.  _Nature_ 538(7626): 471–476.
  * Grefenstette et al. (2015) Grefenstette, E.; Hermann, K. M.; Suleyman, M.; and Blunsom, P. 2015.  Learning to transduce with unbounded memory.  In _Advances in neural information processing systems_ , 1828–1836.
  * He et al. (2016) He, K.; Zhang, X.; Ren, S.; and Sun, J. 2016.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 770–778.
  * Joulin and Mikolov (2015) Joulin, A.; and Mikolov, T. 2015.  Inferring algorithmic patterns with stack-augmented recurrent nets.  In _Advances in neural information processing systems_ , 190–198.
  * Kaiser and Sutskever (2015) Kaiser, Ł.; and Sutskever, I. 2015.  Neural gpus learn algorithms.  _arXiv preprint arXiv:1511.08228_ .
  * Kalchbrenner, Danihelka, and Graves (2015) Kalchbrenner, N.; Danihelka, I.; and Graves, A. 2015.  Grid long short-term memory.  _arXiv preprint arXiv:1507.01526_ .
  * Keysers et al. (2019) Keysers, D.; Schärli, N.; Scales, N.; Buisman, H.; Furrer, D.; Kashubin, S.; Momchev, N.; Sinopalnikov, D.; Stafiniak, L.; Tihon, T.; et al. 2019.  Measuring Compositional Generalization: A Comprehensive Method on Realistic Data.  _arXiv preprint arXiv:1912.09713_ .
  * Kim (2014) Kim, Y. 2014.  Convolutional neural networks for sentence classification.  _arXiv preprint arXiv:1408.5882_ .
  * Kingma and Ba (2014) Kingma, D. P.; and Ba, J. 2014.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ .
  * Lake and Baroni (2017) Lake, B. M.; and Baroni, M. 2017.  Generalization without systematicity: On the compositional skills of sequence-to-sequence recurrent networks.  _arXiv preprint arXiv:1711.00350_ .
  * Lample and Charton (2019) Lample, G.; and Charton, F. 2019.  Deep learning for symbolic mathematics.  _arXiv preprint arXiv:1912.01412_ .
  * Li et al. (2019) Li, J.; Wang, L.; Zhang, J.; Wang, Y.; Dai, B. T.; and Zhang, D. 2019.  Modeling Intra-Relation in Math Word Problems with Different Functional Multi-Head Attentions.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , 6162–6167.
  * Marcus (2003) Marcus, G. 2003.  _The Algebraic Mind: Integrating Connectionism and Cognitive Science_.  MIT Press.
  * Munkhdalai et al. (2019) Munkhdalai, T.; Sordoni, A.; Wang, T.; and Trischler, A. 2019.  Metalearned neural memory.  In _Advances in Neural Information Processing Systems_ , 13331–13342.
  * Nam, Kim, and Jung (2019) Nam, H.; Kim, S.; and Jung, K. 2019.  Number Sequence Prediction Problems for Evaluating Computational Powers of Neural Networks.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 33, 4626–4633.
  * Rae et al. (2016) Rae, J.; Hunt, J. J.; Danihelka, I.; Harley, T.; Senior, A. W.; Wayne, G.; Graves, A.; and Lillicrap, T. 2016.  Scaling memory-augmented neural networks with sparse reads and writes.  In _Advances in Neural Information Processing Systems_ , 3621–3629.
  * Ramachandran et al. (2019) Ramachandran, P.; Parmar, N.; Vaswani, A.; Bello, I.; Levskaya, A.; and Shlens, J. 2019.  Stand-alone self-attention in vision models.  _arXiv preprint arXiv:1906.05909_ .
  * Reed and De Freitas (2015) Reed, S.; and De Freitas, N. 2015.  Neural programmer-interpreters.  _arXiv preprint arXiv:1511.06279_ .
  * Russin et al. (2020) Russin, J.; Jo, J.; O’Reilly, R.; and Bengio, Y. 2020.  Compositional Generalization by Factorizing Alignment and Translation.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics: Student Research Workshop_ , 313–327.
  * Santoro et al. (2018) Santoro, A.; Faulkner, R.; Raposo, D.; Rae, J.; Chrzanowski, M.; Weber, T.; Wierstra, D.; Vinyals, O.; Pascanu, R.; and Lillicrap, T. 2018.  Relational recurrent neural networks.  In _Advances in Neural Information Processing Systems_ , 7299–7310.
  * Saxton et al. (2019) Saxton, D.; Grefenstette, E.; Hill, F.; and Kohli, P. 2019.  Analysing mathematical reasoning abilities of neural models.  _arXiv preprint arXiv:1904.01557_ .
  * Sukhbaatar et al. (2015) Sukhbaatar, S.; Weston, J.; Fergus, R.; et al. 2015.  End-to-end memory networks.  In _Advances in neural information processing systems_ , 2440–2448.
  * Sutskever, Vinyals, and Le (2014) Sutskever, I.; Vinyals, O.; and Le, Q. V. 2014.  Sequence to sequence learning with neural networks.  In _Advances in neural information processing systems_ , 3104–3112.
  * Trask et al. (2018) Trask, A.; Hill, F.; Reed, S. E.; Rae, J.; Dyer, C.; and Blunsom, P. 2018.  Neural arithmetic logic units.  In _Advances in Neural Information Processing Systems_ , 8035–8044.
  * Vaswani et al. (2017) Vaswani, A.; Shazeer, N.; Parmar, N.; Uszkoreit, J.; Jones, L.; Gomez, A. N.; Kaiser, Ł.; and Polosukhin, I. 2017.  Attention is all you need.  In _Advances in neural information processing systems_ , 5998–6008.
  * Wang, Liu, and Shi (2017) Wang, Y.; Liu, X.; and Shi, S. 2017.  Deep neural solver for math word problems.  In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing_ , 845–854.
  * Wangperawong (2018) Wangperawong, A. 2018.  Attending to Mathematical Language with Transformers.  _arXiv preprint arXiv:1812.02825_ .
  * Weston et al. (2015) Weston, J.; Bordes, A.; Chopra, S.; Rush, A. M.; van Merriënboer, B.; Joulin, A.; and Mikolov, T. 2015.  Towards ai-complete question answering: A set of prerequisite toy tasks.  _arXiv preprint arXiv:1502.05698_ .
  * Zaremba and Sutskever (2014) Zaremba, W.; and Sutskever, I. 2014.  Learning to execute.  _arXiv preprint arXiv:1410.4615_ .