* [23] R. M. McCutchen.  The least-unpopularity-factor and least-unpopularity-margin criteria for matching problems with one-sided preferences.  In LATIN 2008: Proceedings of the 8th Latin-American Theoretical Informatics Symposium, volume 4957 of Lecture Notes in Computer Science, pages 593–604. Springer Berlin Heidelberg, 2008.
  * [24] E. McDermid and R. W. Irving.  Popular matchings: structure and algorithms.  Journal of Combinatorial Optimization, 22:339–358, 2011.
  * [25] S. Merrill and B. Grofman.  A Unified Theory of Voting: Directional and Proximity Spatial Models.  Cambridge University Press, 1999.
  * [26] J. Mestre.  Weighted popular matchings.  ACM Transactions on Algorithms, 10, article number 2, 2014.
  * [27] U. G. Rothblum.  Characterization of stable matchings as extreme points of a polytope.  Mathematical Programming, 54:57–67, 1992.
  * [28] L. Shapley and H. Scarf.  On cores and indivisibility.  Journal of Mathematical Economics, 1:23–37, 1974.
  * [29] C. Sng and D. F. Manlove.  Popular matchings in the weighted capacitated house allocation problem.  Journal of Discrete Algorithms, 8:102–116, 2010.
  * [30] J. Tan.  A necessary and sufficient condition for the existence of a complete stable matching.  Journal of Algorithms, 12:154–178, 1991.

## Appendix

The proofs of Proposition 3 and Lemma 10 are given below; for convenience, we
restate their statements.

See 3

###### Proof

Define $t^{\prime}=\max\\{|\alpha_{b}|:b\in B^{\prime}\\}$ which also equals
$\max\\{\alpha_{a}:a\in A^{\prime}\\}$ by complementary slackness. Suppose for
contradiction that $t^{\prime}>t$, and let $B_{\max}$ denote the set of all
objects $b$ with $\alpha_{b}=-t^{\prime}$. We choose $\vec{\alpha}$ so that
$t^{\prime}$ is minimized, and subject to that, $|B_{\max}|$ is as small as
possible. Let us call an edge $(a,b)$ in $G$ _tight_ , if
$\alpha_{a}+\alpha_{b}=\mathsf{wt}_{M}(a,b)$; clearly, all edges of $M$ are
tight by complementary slackness. For each object $b\in B_{\max}$, let us
define the subgraph $H_{b}$ of $G^{\prime}$ spanned by all
$M^{\prime}$-alternating paths in $G^{\prime}$ starting at $b$ with an
$M^{\prime}$-edge (if any) that only contain tight edges. By the same
arguments as in the proof of Theorem 4.4, we know that $H_{b}$ must contain an
agent whose $\alpha$-value is zero, otherwise we could increase the
$\alpha$-value of each object in $H_{b}$ by $1$ and decrease the
$\alpha$-value of each agent in $H_{b}$ by 1, contradicting our choice of
$\vec{\alpha}$.

First, suppose that $l_{i}(a)\in B_{\max}$ for some $a\in A$ and $i\in[t]$. We
claim $i=t$. On the one hand, if $i<t$ and $(p_{i}(a),l_{i+1}(a))\in
M^{\prime}$, then by $\mathsf{wt}_{M^{\prime}}(p_{i}(a),l_{i}(a))=1$ we know
$\alpha_{p_{i}(a)}\geq t^{\prime}+1$, a contradiction to the definition of
$t^{\prime}$. On the other hand, if $i<t$ and $(p_{i}(a),l_{i}(a))\in
M^{\prime}$, let $a^{\prime}$ be an agent in $H_{l_{i}(a)}$ with
$\alpha_{a^{\prime}}=0$. Note that $a^{\prime}\neq p_{i}(a)$ because
$\alpha_{p_{i}(a)}=-\alpha_{l_{i}(a)}=t^{\prime}>0$. Hence the
$M^{\prime}$-alternating path certifying that $a^{\prime}$ is in
$H_{l_{i}(a)}$ must begin with the edges $(l_{i}(a),p_{i}(a))$ and
$(p_{i}(a),l_{i+1}(a))$. In particular, these two edges must be tight,
yielding $\alpha_{p_{i}(a)}=t^{\prime}$ and
$\alpha_{l_{i+1}(a)}=-t^{\prime}-1$ due to
$\mathsf{wt}_{M^{\prime}}(p_{i}(a),l_{i+1}(a))=-1$, again a contradiction.
Thus $l_{i}(a)\in B_{\max}$ implies $i=t$.

Consequently, we know $B_{\max}\subseteq L_{t}\cup B$. Thus, for each dummy
$d\in D$ we must have $\alpha_{d}\geq t^{\prime}$, since $d$ is adjacent to
all objects in $L_{t}\cup B$ and indifferent between them. By the definition
of $t^{\prime}$ we get $\alpha_{d}=t^{\prime}$.

Consider any agent $a\in A$ for which $M^{\prime}(a)\in B$. Then we have
$M^{\prime}(l_{t}(a))\in D$, which in turn yields
$\alpha_{l_{t}(a)}=-t^{\prime}$. Since each edge in $P(a)\setminus M^{\prime}$
has $\mathsf{wt}_{M^{\prime}}$-weight $-1$, for each $i=1,\dots,t-1$ we
iteratively obtain that $\alpha_{p_{t-i}(a)}\geq t^{\prime}-i$ and
$\alpha_{l_{t-i}(a)}\leq-t^{\prime}+i$, yielding also $\alpha_{a}\geq
t^{\prime}-t\geq 1$. Hence, all agents on $P(a)$ have positive
$\alpha$-values.

Now let $b\in B_{\max}$ and let $a_{0}$ be an agent in $H_{b}$ with
$\alpha_{a_{0}}=0$. We know that $a_{0}$ is not a dummy (since all dummies
have $\alpha$-value $t^{\prime}$), and by the previous paragraph, $a_{0}$ does
not lie on any path $P(a^{\prime})$ with $M^{\prime}(a^{\prime})\in B$. Hence,
$a^{\prime}$ must lie on a path $P(a^{\prime})$ for which
$M^{\prime}(a^{\prime})=l_{1}(a)$. Let $Q$ be an $M^{\prime}$-alternating path
in $H_{b}$ from $b$ to $a_{0}$. Since $Q$ starts with an edge of $M^{\prime}$
and is $M^{\prime}$-alternating, the fact $M^{\prime}(a^{\prime})\notin B$
implies that $Q$ must enter $P(a^{\prime})$ from some dummy $d$, proceeding
through the subpath of $P(a^{\prime})$ from $l_{t}(a^{\prime})$ to $a_{0}$.
However, by $\alpha_{d}=-t^{\prime}$ and the tightness of the edges of $Q$ we
obtain that all agents on $P(a^{\prime})$ have positive $\alpha$-value, a
contradiction to the definition of $a_{0}$. This proves the proposition. ∎

See 10

###### Proof

Let $G$ be an instance with weak rankings. We divide the proof into two parts.
In the first part we show that we can assume without loss of generality that
the set of agents in $G$ can be partitioned into two groups, $A_{\succ}$ and
$A_{\sim}$, where agents in $A_{\succ}$ have strict preferences over the
objects in their neighborhood and agents in $A_{\sim}$ are indifferent among
all their neighboring objects. Starting from such an instance, we then prove
the lemma.

##### Part I.

Starting from a graph $G$ with weak rankings, we create a graph $\hat{G}$ and
preferences as follows: For every agent $v$ in $G$, let
$B_{v}^{(1)}\succ\dots\succ B_{v}^{(r_{v})},r_{v}\in\\{1,\dots,m\\}$ be the
weak ranking over its neighboring objects. We add agent $v$ to $\hat{G}$, and
for each $i\in\\{1,\dots,r_{v}\\}$ we further add a new agent $a_{v}^{(i)}$
and a new object $b_{v}^{(i)}$ to $\hat{G}$. The new agent $a_{v}^{(i)}$ is
connected to—and defined to be indifferent among—all objects in
$B_{v}^{(i)}\cup\\{b_{v}^{(i)}\\}$. Lastly, we introduce edges from $v$ to all
objects in $\bigcup_{i=1}^{r_{v}}b_{v}^{(i)}$, with preferences
$b_{v}^{(1)}\succ b_{v}^{(2)}\succ\dots\succ b_{v}^{(r_{v})}$. In $\hat{G}$ we
can partition the set of nodes into $A_{\succ}$, containing copies of agents
in $G$, and $A_{\sim}$, containing the newly introduced agents. Agents in
$A_{\succ}$ have strict preferences and all agents in $A_{\sim}$ are
indifferent among all their neighbors. Below, we show that the two instances
are essentially equivalent.

$v$$1$$1$$2$$2$$2$$B_{v}^{(2)}$$B_{v}^{(1)}$$G$

$v$$b_{v}^{(1)}$$a_{v}^{(1)}$$b_{v}^{(2)}$$a_{v}^{(2)}$$1$$2$$\hat{G}$

Figure 7: Illustration of the first part of the proof of Lemma 10. The left
side illustrates the neighborhood of a fixed node $v$ within the original
graph $G$. The right side illustrates the corresponding situation within the
graph $\hat{G}$. Agents are depicted by circles and objects by squares. Labels
of the edges indicate the rank of the edge within the ranking of the incident
agent. Agents $a_{v}^{(1)}$ and $a_{v}^{(2)}$ are indifferent among all their
neighbors, hence, their labels are omitted.

More precisely, we show that there exists a bijection $f$ mapping assignments
in $G$ to assignments in $\hat{G}$ such that $\Delta(N,M)=\Delta(f(N),f(M))$
for any two assignments $M$ and $N$ in $G$. Let $M$ be an assignment in $G$.
We start with $f(M)=\emptyset$. For every edge $(v,w)\in M$ we do the
following: Let the preferences of $v$ be $B_{v}^{(1)}\succ\dots\succ
B_{v}^{(r_{v})}$, and let $i\in\\{1,\dots,r_{v}\\}$ be such that $w\in
B_{v}^{(i)}$. Then, we add the edges $(v,b_{v}^{(i)})$ and $(a_{v}^{(i)},w)$
to $f(M)$ (see Fig. 7). Moreover, for all indices
$j\in\\{1,\dots,r_{v}\\}\setminus\\{i\\}$ we add the edge
$(a_{v}^{(j)},b_{v}^{(j)})$ to $f(M)$. It is easy to see that this is a
bijection.

Since for every agent in $A_{\succ}$ the rank of its partner in $M$ equals the
rank of its partner in $f(M)$ and agents in $A_{\sim}$ are indifferent among
all their neighbors, we get $\Delta(N,M)=\Delta(f(N),f(M))$.

##### Part II.

Due to part I, we can assume that the agents in $G$ are partitioned into sets
$A_{\succ}$ and $A_{\sim}$ such that agents in $A_{\succ}$ have strict
preferences over objects and the agents in $A_{\sim}$ are indifferent among
all their neighboring objects. Starting from the graph $G$, we create a graph
$G^{\prime}$ with strict rankings as follows. We first copy all agents and
objects to $G^{\prime}$. Then for each $a\in A_{\sim}$ we introduce two new
agents $a^{\prime}$ and $a^{\prime\prime}$ and two new objects
$b^{\prime}_{a}$ and $b^{\prime\prime}_{a}$. We add all possible edges from
$\\{a,a^{\prime},a^{\prime\prime}\\}$ to
$\mathsf{Nbr}_{G}(a)\cup\\{b^{\prime}_{a},b^{\prime\prime}_{a}\\}$ (see Fig.
8). The preferences of agents $a,a^{\prime}$, and $a^{\prime\prime}$ are
identical, namely, $b^{\prime}_{a}$ is their first choice,
$b^{\prime\prime}_{a}$ their second choice, followed by all objects in
$\mathsf{Nbr}_{G}(a)$ in arbitrary order.

We define a function $f$ which maps assignments in $G^{\prime}$ to assignments
in $G$. Let $M^{\prime}$ be an assignment in $G^{\prime}$. For each $(a,b)\in
M^{\prime}$ where $a\in A_{\succ}$, we add the edge $(a,b)$ to
$f(M^{\prime})$. Now, observe that for every $a\in A_{\sim}$, exactly one of
the nodes $a,a^{\prime},a^{\prime\prime}$ is matched to a node of the original
neighborhood, i.e., $\mathsf{Nbr}_{G}(a)$. Let $b$ be the assigned object.
Then we add $(a,b)$ to $f(M^{\prime})$. It is easy to see that $f(M^{\prime})$
is then an assignment in $G$. We continue by observing that

  1. (i)

$f$ is surjective, and

  2. (ii)

for all $a\in A_{\succ}$ and two assignment $M^{\prime}$, $N^{\prime}$ in
$G^{\prime}$: $M^{\prime}\succ_{a}N^{\prime}$ if and only if
$f(M^{\prime})\succ_{a}f(N^{\prime})$.

For (i), note that for every assignment $M$ in $G$ we can create an assignment
$M^{\prime}$ in $G^{\prime}$ such that $f(M^{\prime})=M$ holds, as follows:
Copy all edges from $M$ to $M^{\prime}$ and then add for every $a\in A_{\sim}$
the edges $(a^{\prime},b_{a}^{\prime})$ and
$(a^{\prime\prime},b_{a}^{\prime\prime})$. Clearly, $f(M^{\prime})=M$. For
(ii) observe that for all assignments $M^{\prime}$ in $G^{\prime}$, agents in
$A_{\succ}$ have the same assigned object in $M^{\prime}$ as in
$f(M^{\prime})$.

We define $q=|A_{\sim}|$ and show that $G$ admits an assignment with
unpopularity margin at most $k$ if and only if $G^{\prime}$ admits an
assignment with unpopularity margin at most $k+q$, for any $k\in\mathbb{N}$.

$\mathsf{Nbr}_{G}(a)$$a$$1$$1$$1$$1$$G$

$G^{\prime}$$a$$a^{\prime}$$a^{\prime\prime}$$b^{\prime}_{a}$$b^{\prime\prime}_{a}$$1$$1$$1$$2$$2$$2$

Figure 8: Illustration of the second part of the proof of Lemma 10. The left
side illustrates the neighborhood of an agent $a$, indifferent among all its
neighbors, within the graph $G$. The right side captures the corresponding
gadget in the graph $G^{\prime}$. Labels on the edges indicate the preferences
of agents. The ranks of edges between $\\{a,a^{\prime},a^{\prime\prime}\\}$
and $\mathsf{Nbr}_{G}(a)$ can be chosen arbitrarily (but need to be larger
than $2$), hence, these labels are omitted.

##### Direction “$\Rightarrow$”.

Assume that $G$ admits an assignment $M$ with unpopularity margin at most $k$.
Choose an assignment $M^{\prime}$ from $G^{\prime}$ such that
$f(M^{\prime})=M$ holds (such an $M^{\prime}$ is guaranteed to exist by (i)).
Let $N^{\prime}$ be an assignment in $G^{\prime}$ maximizing
$\Delta(N^{\prime},M^{\prime})$, so
$\mu(M^{\prime})=\Delta(N^{\prime},M^{\prime})$. Since
$\Delta(f(N^{\prime}),f(M^{\prime}))\leq\max_{N}\Delta(N,M)=k$, we know by
(ii) that agents in $A_{\succ}$ contribute at most $k$ to
$\Delta(N^{\prime},M^{\prime})$. Moreover, we claim that agents not in
$A_{\succ}$ contribute at most $q$ to $\Delta(N^{\prime},M^{\prime})$. To see
this, consider the gadget for some agent $a\in A_{\sim}$. We distinguish two
cases. First, assume that the agent from $\\{a,a^{\prime},a^{\prime\prime}\\}$
which is assigned an object in $\mathsf{Nbr}_{G}(a)$ is the same in
assignments $M^{\prime}$ and $N^{\prime}$; w.l.o.g. we assume it is agent $a$.
Then $a^{\prime}$ and $a^{\prime\prime}$ together contribute $0$, and $a$ at
most $1$ to $\Delta(N^{\prime},M^{\prime})$. Second, assume w.l.o.g. that $a$
is assigned some object in $\mathsf{Nbr}_{G}(a)$ by $M^{\prime}$, while
$a^{\prime}$ is assigned some object in $\mathsf{Nbr}_{G}(a)$ by $N^{\prime}$.
Then $a$ and $a^{\prime}$ together contribute $0$,and $a^{\prime\prime}$ at
most $1$. As this holds for every gadget belonging to agents in $A_{\sim}$,
this proves $\Delta(N^{\prime},M^{\prime})\leq k+q$.

##### Direction “$\Leftarrow$”.

For the other direction, assume that $G^{\prime}$ admits an assignment
$M^{\prime}$ with unpopularity margin at most $k+q$. We claim that
$f(M^{\prime})$ has unpopularity at most $k$. Assume for contradiction that
there exists some assignment $N$ in $G$ with $\Delta(N,f(M^{\prime}))>k$. We
construct $N^{\prime}$ as follows. For every agent $a\in A_{\succ}$, we let
$N^{\prime}(a)=N(a)$. Next, for every agent $a\in A_{\sim}$, let $b_{M}$ be
its assigned object in $f(M^{\prime})$ and $b_{N}$ be its assigned object in
$N$. We can assume w.l.o.g. that $a$ is matched to $b_{M}$ in $M^{\prime}$,
$a^{\prime}$ is matched to $b^{\prime}_{a}$, and $a^{\prime\prime}$ is matched
to $b^{\prime\prime}_{a}$. In $N^{\prime}$ we match $a^{\prime}$ to $b_{N}$,
$a^{\prime\prime}$ to $b^{\prime}_{a}$, and $a$ to $b^{\prime\prime}_{a}$.
Then $a$, $a^{\prime}$, and $a^{\prime\prime}$ together contribute exactly $1$
to $\Delta(N^{\prime},M^{\prime})$. Using the same argument for all $a\in
A_{\sim}$ and (ii) yields that
$\mu(M^{\prime})\geq\Delta(N^{\prime},M^{\prime})>k+q$, a contradiction. ∎


# General covariance and dynamics with a Gauss law

Viqar Husain<EMAIL_ADDRESS>Department of Mathematics and Statistics,
University of New Brunswick, Fredericton, NB Canada E3B 5A3  Perimeter
Institute for Theoretical Physics, 31 Caroline Street North, Waterloo ON N2L
2Y5, Canada  Hassan Mehmood<EMAIL_ADDRESS>Department of Mathematics
and Statistics, University of New Brunswick, Fredericton, NB Canada E3B 5A3

###### Abstract

We present a 4-dimensional generally covariant gauge theory which leads to the
Gauss constraint but lacks both the Hamiltonian and spatial diffeomorphism
constraints. The canonical theory therefore resembles Yang-Mills theory
without the Hamiltonian. We describe its observables, quantization, and some
generalizations.

##  I  Introduction

The difficulty of constructing a fully satisfactory theory of quantum gravity
gives rise to the need for simpler models, which consist in writing down
generally covariant theories that are different from general relativity but
simpler to analyze from a quantum-theoretical perspective. These include BF
theory Horowitz (1989); Husain (1991), 2+1 gravity Witten (1988); Ashtekar
_et al._ (1989); Carlip (1989); Moncrief (1990), $U(1)^{3}$ theory Smolin
(1992); Bakhoda and Thiemann (2021), the Husain-Kuchar (HK) model Husain and
Kuchar (1990); Barbero G. and Villasenor (2001), and many others with symmetry
reductions Barbero G. and Villasenor (2010) and matter.

The Hamiltonian version of the HK theory lacks the Hamiltonian constraint of
general relativity, which encodes the dynamics of general relativity and is
the most difficult object to quantize in any canonical approach to quantum
gravity. As such, the model furnished the hope for clearly separating the
question of dynamics from that of kinematics, and thus determining which
quantum-gravitational effects are solely kinematical in nature. To this end,
subsequent developments revealed subtle and surprising results, such as the
fact that black-hole entropy calculations in loop quantum gravity (LQG) can be
performed with generally covariant theories that lack black-hole solutions
entirely Husain (1999).

In this paper, we describe a model that, on the face of it, is a slight
variation of the HK model, but turns out to have significantly different
features: the canonical theory lacks not only the Hamiltonian, but also the
diffeomorphism constraint, and the remaining Gauss constraint contains a
source term. This leads to new observables in the classical and quantum
theories that resemble “quarks on a string.” Furthermore, these features
obtain regardless of the gauge group of the model, provided that the
corresponding Lie algebra is semisimple. This gives considerable freedom in
constructing classical solutions that include metrics corresponding to almost
any three-geometry.

The surprising feature that a generally covariant model realizes dynamics only
as internal gauge provides a large class of exactly solvable classical and
quantum models with local degrees of freedom; the canonical theory may be
viewed as Yang-Mills theory without its Hamiltonian, and for the gauge group
$SU(N)$ the theory has $2(N^{2}-1)$ local degrees of freedom.

The plan of the paper is as follows. In Section II, we introduce the model and
derive its canonical theory. Sections III and IV are devoted to describing
certain classical observables and solutions, respectively, and Section V
discusses the quantum theory. Finally, Section VI describes possible
extensions of the model, such as addition of a Chern-Simons boundary term, and
the 3-dimensional version of the model.

##  II  Action and canonical theory

Let $M$ be a spacetime, and let $\phi^{i}(x)$ and $A^{i}_{\alpha}(x)$, be
scalars and connection one-forms in the Lie algebra $\mathfrak{g}$ of a
semisimple group $\mathcal{G}$. We denote by $f_{ijk}$ the structure constants
(totally antisymmetric) of the algebra and by $\kappa_{ij}$ the (non-
degenerate) Cartan-Killing form, which can be used to raise and lower Lie-
algebra-valued objects. We consider the action

$\displaystyle S[\phi,A]$ $\displaystyle=\frac{1}{2}\int_{M}d^{4}x\
\tilde{\epsilon}^{\alpha\beta\gamma\delta}f_{ijk}D_{\alpha}\phi^{i}D_{\beta}\phi^{j}F^{k}_{\gamma\delta}$
(1) $\displaystyle=\frac{1}{2}\int_{M}d^{4}x\,\text{Tr}\,(D\phi\wedge
D\phi\wedge F),$ (2)

where $D$ and $F$ denote, respectively, the covariant derivative and the
curvature 2-form corresponding to the connection $A$, i.e.

$\displaystyle D_{\alpha}\gamma^{i}$
$\displaystyle=\partial_{\alpha}\gamma^{i}+\tensor{f}{{}^{i}_{jk}}A^{j}_{\alpha}\gamma^{k}$
(3) $\displaystyle F^{i}_{\alpha\beta}$
$\displaystyle=\partial_{[\alpha}A^{i}_{\beta]}+\tensor{f}{{}^{i}_{jk}}A^{j}_{\alpha}A^{k}_{\beta},$
(4)

and $\tilde{\epsilon}^{\alpha\beta\gamma\delta}$ is the four-dimensional
densitized Levi-Civita symbol.

This action is manifestly invariant both under spacetime diffeomorphisms and
the internal gauge group $\mathcal{G}$. It resembles the HK action: if one
replaces $D_{\alpha}\phi^{i}$ with $\mathfrak{su}(2)$-valued one-forms
$e_{\alpha}^{i}$, one recovers the HK action. However, as we shall see, the
canonical theory is drastically different.

Variation of the action with respect to $A$ and $\phi$ yields the equations of
motion:

$\displaystyle\delta\phi$ $\displaystyle:\qquad\qquad D\wedge(D\phi\wedge
F)=0,$ (5) $\displaystyle\delta A$ $\displaystyle:\qquad D\wedge(D\phi\wedge
D\phi)=\phi\times(D\phi\wedge F),$ (6)

where ‘$\times$’ denotes an internal product using the strcuture constants
$f_{ijk}$, i.e. $(u\times v)^{i}=\tensor{f}{{}^{i}_{jk}}u^{j}v^{k}$.

To perform canonical decomposition of the action, we assume $M$ has the
topology $\mathbb{R}\times\Sigma$, where $\Sigma$ is a compact three-
dimensional, differentiable manifold. Then, choosing the coordinates
$x^{\alpha}=(x^{0},x^{a})$, with $x^{0}\in\mathbb{R}$ and $x^{a}\in\Sigma$,
and defining

$\displaystyle\tilde{\epsilon}^{abc}$ $\displaystyle:=$
$\displaystyle\tilde{\epsilon}^{0abc},$ (7) $\displaystyle\tilde{E}^{a}_{i}$
$\displaystyle:=$
$\displaystyle\tilde{\epsilon}^{abc}f_{ijk}D_{b}\phi^{j}D_{c}\phi^{k},$ (8)
$\displaystyle\tilde{p}_{i}$ $\displaystyle:=$
$\displaystyle\tilde{\epsilon}^{abc}f_{ijk}D_{a}\phi^{j}F^{k}_{bc},$ (9)

we see that

$S=\int
d^{4}x\left[\tilde{E}^{c}_{k}\dot{A}^{k}_{c}+\tilde{p}_{i}\dot{\phi}^{i}+A^{k}_{0}(D_{c}\tilde{E}^{c}_{k}+\tensor{f}{{}_{kl}^{i}}\phi^{l}\tilde{p}_{i})\right]$
(10)

where the overdot indicates $\partial_{0}$. It thus follows that
$\tilde{E}^{c}_{k}$ is the momentum conjugate to $A^{k}_{c}$ and
$\tilde{p}_{i}$ is the momentum conjugate to $\phi^{i}$; there are thus two
sets of configuration variables, the $\mathfrak{g}$-valued connection $A$ and
scalar $\phi$. There is only one constraint, the Gauss law with a source term

$\tilde{G}_{k}=-(D_{c}\tilde{E}^{c}_{k}+\tensor{f}{{}_{kl}^{i}}\phi^{l}\tilde{p}_{i})\approx
0.$ (11)

The Hamiltonian is therefore the linear combination of constraints

$\displaystyle H=\int d^{3}x\,\lambda_{k}G^{k}(x)$ (12)

and it is evident that there is neither a Hamiltonian nor a spatial
diffeomorphism constraint. The reason for the vanishing of the former can be
traced back to the non-existence of a lapse function in the theory, as in the
original HK model Husain and Kuchar (1990); the vanishing of the
diffeomorphism constraint comes from the fact that the time component of the
frame fields $e_{0}^{i}$ in the HK model, which furnishes the shift vector
$N^{a}$, is no longer present in our model, and is instead replaced by
$\partial_{0}\phi^{i}$, the time derivative of a configuration variable. We
thus have here an example of a theory that is invariant under four-dimensional
spacetime diffeomorphisms but in which only the internal gauge is realized as
constraints. It is readily verified that the Gauss constraint remains first
class with the source term:

$\displaystyle\\{G(\lambda),G(\mu)\\}$ $\displaystyle=$
$\displaystyle\left\\{\int d^{3}x\ \lambda^{m}D_{a}\tilde{E}^{a}_{m}(x),\int
d^{3}y\ \gamma^{n}D_{b}\tilde{E}^{b}_{n}(y)\right\\}+\left\\{\int d^{3}x\
\lambda^{m}\tensor{f}{{}_{ml}^{s}}\phi^{l}\tilde{p}_{s}(x),\int d^{3}y\
\gamma^{n}\tensor{f}{{}_{ij}^{k}}\phi^{j}\tilde{p}_{k}(y)\right\\}$ (13)
$\displaystyle=$ $\displaystyle G([\lambda,\mu]).$

For the group $SU(N)$ the theory therefore has $3(N^{2}-1)$ configuration
degrees of freedom per space point in $E^{ai}$ and $(N^{2}-1)$ in $\phi^{i}$,
subject to the $(N^{2}-1)$ component Gauss constraint, for a net $3(N^{2}-1)$
unconstrained local degrees of freedom; for $SU(2)$ that gives nine, six more
than for the HK model.

##  III  Observables

Let us recall that an observable is a dynamical function(al)
$f(\phi,A,\tilde{E},\tilde{p})$ that has vanishing Poisson brackets with the
constraints. For comparison with the HK model, let us restrict attention to
$SU(2)$. We can define a spatial metric by

$q_{ab}=\kappa_{ij}D_{a}\phi^{i}D_{b}\phi^{j};$ (14)

It is readily verified that this is an observable:

$\\{D_{a}\phi^{i}(x),G(\lambda)\\}=\tensor{f}{{}^{i}_{mn}}\lambda^{m}D_{a}\phi^{n},$
(15)

hence $\displaystyle\\{q_{ab},G(\lambda)\\}=0.$ Since the metric is gauge-
invariant, so are all the classical observables that depend on it. Hence, for
instance, the area and volume functionals are observables in this model, just
as in loop quantum gravity (LQG) Rovelli and Smolin (1995).

Other obvious examples of observables are $\mathcal{G}$-valued loop variables,
which are defined using traces of holonomies around curves in $\Sigma$ and
insertions of configuration and momentum variables along the curves. That is,
given a smooth curve $\gamma:[a,b]\to\Sigma$, we define the Wilson line from
$a$ to $b$:

$U[\gamma](a,b):=\mathcal{P}\exp\left({\int_{a}^{b}dx^{a}A^{i}_{a}\tau_{i}}\right),$
(16)

where $\mathcal{P}$ stands for path-ordering and $\tau_{i}$ are the generators
of $\mathfrak{g}$. If $a=b$, we get the so-called Wilson loops. Since these
are matrices in $\mathcal{G}$, and hence transform under $\mathcal{G}$ via
conjugation (i.e. $g\cdot U[\gamma]=g^{-1}(a)U[\gamma]g(b)$), the cyclic
invariance of the trace operation entails that

$T^{0}[\gamma]:=\text{Tr}\,(U[\gamma](a,a))$ (17)

is an observable. Similarly, the rest of the familiar $T$ variables, defined
via insertions of the momentum $\tilde{E}^{a}_{i}$ along Wilson lines, are
also observables, e.g.

$\displaystyle T^{a_{1}\cdots
a_{n}}[\gamma](x_{1},\ldots,x_{n})=\text{Tr}\,\left[U[\gamma](a,x_{1})\tilde{E}^{a_{1}}(x_{1})\right.$
$\displaystyle\left.\times
U[\gamma](x_{1},x_{2})\tilde{E}^{a_{2}}(x_{2})\cdots\tilde{E}^{a_{n}}U[\gamma](x_{n},a)\right],$

where $\tilde{E}^{a}=\tilde{E}^{a}_{i}\tau^{i}$ and $x_{1},\ldots,x_{n}$ are
fixed points on the curve $\gamma$.

However, unlike in standard LQG, these are not the only loop observables,
since we now have the additional $\mathfrak{g}$-valued configuration and
momentum variables, namely $\phi^{i}$ and $\tilde{p}_{i}$, that may be
inserted along Wilson lines as well. Here there are multiple possibilities,
ranging from simple end-of-the-curve insertions such as

$\text{Tr}\,\left[\phi(x)U[\gamma](x,y)\phi(y)\right]$ (18)

to mixed and middle-of-the-curve insertions such as

$\displaystyle\text{Tr}\,[\phi(x_{1})U[\gamma](x_{1},x_{2})\tilde{E}(x_{2})U[\gamma](x_{2},x_{3})$
$\displaystyle\left.\times\tilde{p}(x_{3})U[\gamma](x_{3},x_{4})\phi(x_{4})\right].$
(19)

The former are essentially flux tubes analogous to those found in Yang-Mills
theory, except that the nonzero Hamiltonian of the latter can cause these
tubes to break to form more such tubes, whereas our model has unbroken tubes
floating around in spacetime.

##  IV  Classical Solutions

Since the Hamiltonian constraint, which generates orthogonal transformations
of three-dimensional hypersurfaces, vanishes in both the HK model and the
model here, both are essentially theories of three-geometry that arise from
four-dimensional actions. For the HK model, constraint free initial data
specified on a three-dimensional hypersurface are solutions of the Gauss and
spatial diffeomorphism constraints. Since the Hamiltonian constraint vanishes,
these data do not evolve. Therefore they are solutions for a three-geometry.
This means that constraint free data for Einstein gravity is a subset of the
data for the HK model.

In the model at hand the Gauss constraint contains a source term. Two peculiar
features of the model conspire to yield a large class of interesting three-
geometries as solutions of the model. First, the three-metric (14) depends
solely on the configuration variables $\phi$ and $A$. Since these variables
are independent, one can set their conjugate momenta $\tilde{p}^{i}$ and
$E^{ai}$ to zero to trivially solve the Gauss constraint. Second, since the
model is valid for arbitrary (semisimple) gauge groups, which include those
with Cartan-Killing metrics of mixed signature, one can even construct
solutions of 2+1 gravity. Thus, by appropriately fixing the form of $\phi$ and
$A$ while $\tilde{p}$ and $\tilde{E}$ are zero, it is possible to construct
almost any three-metric, including all those resulting from projecting
solutions of the 3+1 Einstein equations on three-dimensional hypersurfaces, as
well as all the solutions of 2+1 gravity. To illustrate these remarks, we
explicitly construct the spatial Schwarzschild metric and the Banados-
Teitelboim-Zanelli (BTZ) black-hole metric Bañados  _et al._ (1992).

###  IV.1 3d Schwarzschild metric

For $\mathcal{G}=SU(2)$, $\tilde{p}=\tilde{E}=0$, use spherical coordinates
$(r,\theta,\varphi)$ on $\Sigma$, and set

$\displaystyle A$
$\displaystyle=\frac{r}{P(r)}\tau_{1}d\theta+(\cos\theta\tau_{3}-\frac{r}{P(r)}\sin\theta\tau_{2})d\varphi$
(20) $\displaystyle\phi$ $\displaystyle=P(r)\tau_{3},\qquad f(r)=\sqrt{1-R/r}$
(21) $\displaystyle P(r)$
$\displaystyle=\frac{R}{2}\left[\ln\left|\frac{f(r)+1}{f(r)-1}\right|+\frac{2f(r)}{(f(r)+1)(f(r)-1)}\right],$
(22)

where $\tau^{i}$ are the Pauli matrices. Then (14) gives the Schwarzschild
three-metric

$\displaystyle ds^{2}=f^{-2}(r)dr^{2}+r^{2}d\Omega^{2}.$ (23)

###  IV.2 BTZ black hole

Let $\mathcal{G}=SO(2,1)$ and use the Cartan-Killing metric
$\text{diag}(-1,1,1)$. Pick cylindrical coordinates $(r,\varphi,z)$ on
$\Sigma$. Then the BTZ metric can be obtained as follows. Let

$\displaystyle A$ $\displaystyle=$
$\displaystyle[P(r)\tau_{1}+Q(r)\tau_{2}]d\varphi+[R(r)\tau_{2}+S(r)\tau_{3}]dz,$
$\displaystyle\phi$ $\displaystyle=$ $\displaystyle T(r)\tau_{3},$ (24)
$\displaystyle N^{2}(r)$ $\displaystyle=$
$\displaystyle-M+\frac{r^{2}}{l^{2}}+\frac{J^{2}}{4r^{2}},\;N_{\varphi}(r)=-\frac{J}{2r^{2}},$
(25)

where the last two functions are used to define the BTZ metric. Substituting
these into (14) yields the equations

$\displaystyle T^{\prime}(r)^{2}$ $\displaystyle=$ $\displaystyle N^{-2}(r),$
(26) $\displaystyle T^{2}(r)(P^{2}(r)-Q^{2}(r))$ $\displaystyle=$
$\displaystyle r^{2},$ (27) $\displaystyle R^{2}(r)T^{2}(r)$ $\displaystyle=$
$\displaystyle N^{2}(r),$ (28) $\displaystyle R(r)Q(r)T^{2}(r)$
$\displaystyle=$ $\displaystyle r^{2}N_{\varphi}(r),$ (29)

which can be solved for the functions $P,Q,R,T$ to obtain $A$ and $\phi$: the
first equation gives

$\displaystyle T(r)$ $\displaystyle=$
$\displaystyle\frac{l}{2}\ln\left|\sqrt{h^{2}(r)+1}+h(r)\right|,$
$\displaystyle h(r)$ $\displaystyle=$
$\displaystyle\frac{2r^{2}-Ml^{2}}{\sqrt{J^{2}l^{2}-M^{2}l^{4}}},$ (30)

and the others three are algebraic.

These examples show that almost any desired 3-metric may be constructed by
solving for $A$ and $\phi$.

##  V  Quantum Theory

To proceed to the quantum theory, we restrict attention to compact gauge
groups, since the quantum configuration space in LQG is constructed from the
Lie algebra of a compact Lie group. Thus in this section, $\mathcal{G}$ refers
to a compact semisimple Lie group.

###  V.1 Connection representation

Since there are now two types of configuration variable, the connection $A$
and the $\phi$ variables, the connection representation is better termed the
$A$-$\phi$ representation. Physical states are gauge-invariant functionals of
$\phi$ and $A$ – for instance, the loop variables defined above but depending
solely on $A$ and $\phi$, e.g

$\displaystyle\Psi(\phi,A)=\text{Tr}\,(\phi(x_{1})U[\gamma](x_{1},x_{2})\phi(x_{2})$
$\displaystyle\times U[\gamma](x_{2},x_{3})\phi(x_{3})).$ (31)

The inner product on these states is well-defined, with there being now an
additional integration over the $\phi$:

$\displaystyle\langle\Psi_{1}|\Psi_{2}\rangle=\int d\mu(\phi)\int
d\mu(A)\Psi^{*}_{1}(\phi,A)\Psi_{2}(\phi,A),$ (32)

where $\mu(A)$ is a measure on the space of connections (modulo gauge
transformations), such as the Ashtekar-Lewandowski measure, and $\mu(\phi)$ is
some suitable measure on the space of the $\phi$ fields (say, a Gaussian
measure).

###  V.2 Spin-network states

As in LQG, quantum states in the model can be realized as spin networks, with
one addition. As usual, $SU(2)$ representations label the edges of embedded
graphs, corresponding to holonomies of the connection along those edges, i.e.
functionals of the form $\Psi(A)$, and these representations are sewed by
intertwiners associated with the vertices of the graph. However, here we can
also have physical functionals that involve insertions of $\phi$ at the end of
Wilson lines. In a spin network, such states correspond to the $\phi$
variables sitting at selected vertices of the underlying graph, along with the
intertwiners. Thus in general, a typical spin-network state corresponding to a
graph $\gamma$ would look like

$|\gamma;j_{1},\ldots,j_{n};I_{1},\ldots,I_{n};\phi_{1},\ldots,\phi_{k}\rangle,\qquad
k\leq n,$ (33)

with the obvious inner product. Such states are physical states of the theory,
and the area and volume operators of LQG are diagonal physical observables.
The quantum tetrahedra are physical states of the theory, and as there is no
spatial diffeomorphism constraint, each graph representating a tetrahedron is
a distinct physical state, unlike in the HK model.

##  VI Discussion

Our main observation is the theory defined by (1), and its unexpected
canonical theory, with the missing Hamiltonian and diffeomorphism constraints.
The theory may be viewed as an exactly solvable theory of $3$-geometries,
classically and quantum mechanically.

An natural extension of the model arises by adding a Chern-Simons boundary
term to the action (1):

$\displaystyle S$
$\displaystyle=\frac{1}{2}\int_{M}d^{4}x\,\text{Tr}\,(D\phi\wedge D\phi\wedge
F)$ $\displaystyle+\gamma\int_{\partial M}d^{3}x\,\left(A\wedge
dA+\frac{2}{3}A\wedge A\wedge A\right).$ (34)

Varying the action now yields

$\displaystyle\delta S=-\int_{M}d^{4}x\,[D\wedge(D\phi\wedge F))]_{i}$
$\displaystyle\delta\phi^{i}+\gamma\int_{\partial
M}d^{3}x\,\tilde{p}_{i}\delta\phi^{i}$
$\displaystyle-\int_{M}d^{4}x\,[D\wedge(D\phi\wedge
D\phi)-(\phi\times(D\phi\wedge F))]^{\alpha}_{k}\delta
A^{k}_{\alpha}+\int_{\partial
M}d^{3}x\,[\gamma\tilde{\epsilon}^{abc}F_{iab}+\tilde{E}^{c}_{k}]\delta
A^{k}_{c}.$

Thus, if we insist that the variations in $\phi$ and $A$ on the boundary
$\partial M$ can be nonzero, the conjugate momenta must be constrained on the
boundary to ensure a well-defined variational principle:

$\left.\tilde{E}^{c}_{k}\right|_{\partial
M}=-\gamma\tilde{\epsilon}^{abc}F_{iab},\quad\left.\tilde{p}_{i}\right|_{\partial
M}=0.$ (35)

The first of these conditions is the condition on conjugate momenta that also
arises with a topological bulk theory Smolin (1995), and in the context of
black-hole entropy in LQG for an inner boundary Ashtekar  _et al._ (1998);
Husain (1999), where quantization of this condition in the spin-network basis
with area operator provides an area-entropy relation. The same would occur in
the present theory.

Other possible variants of the action (1) include the addition of bulk
topological term $\displaystyle\int d^{4}x\ {\rm Tr}(F\wedge F)$, more than
one connection Barbero G.  _et al._ (2019), as well as boundaries with
multiple components for identifying corner observables; see, e.g. Jubb  _et
al._ (2017).

Lastly, there is also an interesting 3d version of the model with action

$\int_{M}d^{3}x\ \tilde{\epsilon}^{abc}\kappa_{ij}D_{a}\phi^{i}F^{j}_{bc}.$
(36)

Variation with respect to $\phi$ yields the Bianchi identity, and variation
with respect to $A$ gives the remaining equation of motion

$\tilde{\epsilon}^{abc}f_{ijk}F^{j}_{bc}\phi^{k}=0.$ (37)

Thus the solutions of the theory are rather simple: $F=0$ and $\phi^{i}\neq
0$; $F\neq 0$ and $\phi^{i}=0\ \forall\ i$; or, for any $F\neq 0$, choose
$\phi$ parallel to $F$ in the internal space. The canonical theory is
unchanged in form in that there is only a Gauss law constraint with source,
except that the definition of conjugate momenta is altered:

$\displaystyle\tilde{p_{i}}=\kappa_{ij}\tilde{\epsilon}^{uv}F^{j}_{uv},\quad\tilde{E}^{ui}=\frac{1}{2}\tilde{\epsilon}^{uv}D_{v}\phi^{i},$

where the indices $u,v=1,2$ and $\tilde{\epsilon}^{uv}$ is the alternating
tensor of density in 2d. For $SU(2)$ the theory has 6 configuration degrees of
freedom per space point; it provides a curious 3d geometric theory with local
degrees of freedom. Lastly, the abelian theory has no content—its equations of
motion are identically satisfied.

As the model and its variants we present are generally covariant theories with
local degrees of freedom, they provide a useful testing ground for other
quantization methods such as the spin foam path integral Baez (2000); Perez
(2013), and group field theory Gielen and Sindoni (2016).

###### Acknowledgements.

This work was supported by NSERC of Canada. VH thanks the Perimeter Institute
where this work was completed; Research at Perimeter Institute is supported in
part by the Government of Canada through the Department of Innovation, Science
and Economic Development Canada and by the Province of Ontario through the 25
Ministry of Colleges and Universities.

## References

  * Horowitz (1989) G. T. Horowitz, Commun. Math. Phys. 125, 417 (1989).
  * Husain (1991) V. Husain, Phys. Rev. D 43, 1803 (1991).
  * Witten (1988) E. Witten, Nucl. Phys. B 311, 46 (1988).
  * Ashtekar  _et al._ (1989) A. Ashtekar, V. Husain, C. Rovelli, J. Samuel, and L. Smolin, Class. Quant. Grav. 6, L185 (1989).
  * Carlip (1989) S. Carlip, Nucl. Phys. B 324, 106 (1989).
  * Moncrief (1990) V. Moncrief, J. Math. Phys. 31, 2978 (1990).
  * Smolin (1992) L. Smolin, Class. Quant. Grav. 9, 883 (1992), arXiv:hep-th/9202076 .
  * Bakhoda and Thiemann (2021) S. Bakhoda and T. Thiemann, Class. Quant. Grav. 38, 215006 (2021), arXiv:2010.16351 [gr-qc] .
  * Husain and Kuchar (1990) V. Husain and K. V. Kuchar, Phys. Rev. D 42, 4070 (1990).
  * Barbero G. and Villasenor (2001) J. F. Barbero G. and E. J. S. Villasenor, Phys. Rev. D 63, 084021 (2001), arXiv:gr-qc/0012040 .
  * Barbero G. and Villasenor (2010) J. F. Barbero G. and E. J. S. Villasenor, Living Rev. Rel. 13, 6 (2010), arXiv:1010.1637 [gr-qc] .
  * Husain (1999) V. Husain, Phys. Rev. D 59, 084019 (1999).
  * Rovelli and Smolin (1995) C. Rovelli and L. Smolin, Nucl. Phys. B 442, 593 (1995), [Erratum: Nucl.Phys.B 456, 753–754 (1995)], arXiv:gr-qc/9411005 .
  * Bañados  _et al._ (1992) M. Bañados, C. Teitelboim, and J. Zanelli, Physical Review Letters 69, 1849 (1992).
  * Smolin (1995) L. Smolin, J. Math. Phys. 36, 6417 (1995), arXiv:gr-qc/9505028 .
  * Ashtekar  _et al._ (1998) A. Ashtekar, J. Baez, A. Corichi, and K. Krasnov, Physical Review Letters 80, 904 (1998).
  * Barbero G.  _et al._ (2019) J. F. Barbero G., B. Díaz, J. Margalef-Bentabol, and E. J. S. Villaseñor, JHEP 10, 121 (2019), arXiv:1906.09820 [gr-qc] .
  * Jubb  _et al._ (2017) I. Jubb, J. Samuel, R. Sorkin, and S. Surya, Class. Quant. Grav. 34, 065006 (2017), arXiv:1612.00149 [gr-qc] .
  * Baez (2000) J. C. Baez, Lect. Notes Phys. 543, 25 (2000), arXiv:gr-qc/9905087 .
  * Perez (2013) A. Perez, Living Rev. Rel. 16, 3 (2013), arXiv:1205.2019 [gr-qc] .
  * Gielen and Sindoni (2016) S. Gielen and L. Sindoni, SIGMA 12, 082 (2016), arXiv:1602.08104 [gr-qc] .


Copyright for this paper by its authors. Use permitted under Creative Commons
License Attribution 4.0 International (CC BY 4.0).

NeSy 2023, 17th International Workshop on Neural-Symbolic Learning and
Reasoning, Certosa di Pontignano, Siena, Italy

[email=flavio.petruzzellis@phd.unipd.it,] [1]

<EMAIL_ADDRESS>]

<EMAIL_ADDRESS>]

[1]Corresponding author.

# A Hybrid System for Systematic Generalization in Simple Arithmetic Problems

Flavio Petruzzellis  Department of Mathematics, University of Padova, Padova,
Italy  Department of General Psychology, University of Padova, Padova, Italy
Alberto Testolin  Alessandro Sperduti

(2023)

###### Abstract

Solving symbolic reasoning problems that require compositionality and
systematicity is considered one of the key ingredients of human intelligence.
However, symbolic reasoning is still a great challenge for deep learning
models, which often cannot generalize the reasoning pattern to out-of-
distribution test cases. In this work, we propose a hybrid system capable of
solving arithmetic problems that require compositional and systematic
reasoning over sequences of symbols. The model acquires such a skill by
learning appropriate substitution rules, which are applied iteratively to the
input string until the expression is completely resolved. We show that the
proposed system can accurately solve nested arithmetical expressions even when
trained only on a subset including the simplest cases, significantly
outperforming both a sequence-to-sequence model trained end-to-end and a
state-of-the-art large language model.

###### keywords:

deep learning neural networks mathematical reasoning neuro-symbolic systems
formula simplification

##  1 Introduction

Designing systems that are able to learn abstract reasoning patterns from data
is one of the fundamental challenges in artificial intelligence research. In
particular, the capacity to generalize compositionally [1], to reuse learned
rules on unseen algorithmic problems that fall outside of the training
distribution [2], and more generally to exhibit high-level reasoning abilities
are considered long-standing issues by the machine learning community. One
possibility to empower artificial intelligence systems with reasoning
abilities is to combine statistical-based approaches, which can flexibly adapt
to the properties of the observed data, with logic-based modules, which can be
engineered according to a set of predefined rules [3].

In this work, we introduce a novel neuro-symbolic architecture that solves
reasoning problems on sequences of symbols in an iterative fashion. Our goal
is to build a system that can learn to solve compositional tasks by only
observing a subset of problem instances and then generalize the acquired
knowledge to out-of-distribution (possibly more difficult) instances. The
proposed system is made up of two parts: a deep learning module that is
trained to generate candidate solutions that simplify a given input sequence,
and a deterministic component that combines the original input and the output
of the neural module to produce the final output. Thanks to its hybrid nature,
our system can learn the fundamental solution steps for a set of symbolic
reasoning problems, and then apply these operations iteratively to novel
problem instances.

We evaluate our model on the task of simplifying arithmetic expressions, which
is well suited to study systematic reasoning abilities and is still considered
a great challenge even for state-of-the-art deep learning models [4]. The goal
of the system is to generate the final solution of arithmetical expressions
that can involve a variable number of nested elementary operations (sums,
subtractions, and multiplications) delimited by parentheses. The model is
trained on a limited subset of possible problems that contain only up to 2
nested operations. In order to evaluate its extrapolation capabilities, in the
testing phase the model is probed with problems involving up to 10 nested
operations.

Our results show that the proposed hybrid architecture achieves better out-of-
distribution generalization compared to a Transformer encoder-decoder trained
to solve the same problem end-to-end, and to a large language model tested on
the same task, adapting the original inputs to create appropriate
prompts111Our code is available at https://github.com/flavio2018/nesy23..

##  2 The Proposed Hybrid System

The proposed architecture is composed of two parts (Figure 1): a trainable
seq2seq model which we call the ‘solver’, and a deterministic module named the
‘combiner’. The system operates by pipelining the computation of the solver
and the combiner, and then applying the pipeline iteratively.

Figure 1: A visual representation of the hybrid system. The system takes an
arithmetical expression as input. The solver learns to generate a set of
candidate simplifications, which are produced as output according to a
predefined syntax that describes the result of the operation concatenated with
the target substitution. The combiner then filters well-formed outputs,
selects the most frequently generated candidate and applies the corresponding
replacement of the target sub-string. The output of the combiner is then fed
back to the system, enabling the iterative solution of complex problems.

We can define $E$ as the set of nested arithmetical expressions represented as
strings of symbols on which we test our model, and $R\subset E$ as the subset
of expressions that consist only of integer values, and thus represent the
result (or values) of complex expressions. Furthermore, since each $e\in
E\setminus R$ is composed of nested expressions, for each $e$ we can identify
one innermost sub-expression $s_{k}$ (only one in our specific case, see Data
in Section 3) which can be solved independently from the context (we can
define $r_{k}\in R$ as the result of $s_{k}$). Finally, we can define a
function which associates to each $e\in E$ a chain of solution steps:
$chain(e)=(e_{k},e_{k-1},...,e_{0})$, where $e,e_{j}\in E,\
j\in\\{1,\ldots,k\\}$, $e_{0}\in R$ is the final solution of $e_{k}$, and
$e_{j-1}$ can be described as $e_{j}$ where the innermost sub-expression
$s_{j}$ has been solved.

Given the compositional nature of the problem, we can distinguish between the
goal of solving the entire expression $e$, i.e. finding $e_{0}$, and the sub-
goals of reducing sub-expressions, i.e. computing the result $r_{j}$ of each
sub-expression $s_{j},\ j\in\\{1,\ldots,k\\}$.

In our approach, the solver is trained to match arithmetical sub-expressions
in their context to the corresponding numerical solution, by generating as
output a string composed of two parts: a replacement candidate (i.e. the
result of the innermost sub-expression $r_{j}$) and a replacement target (i.e.
the innermost sub-expression itself $s_{j}$), concatenated using the
‘underscore’ symbol. For example, if the model receives as input the
expression ((21-6)*2) it should produce as output the string 15_(21-6). More
formally, the solver can be defined as a function $solver\colon E\rightarrow
R\times E$, $solver(e_{j})=(r_{j},s_{j})$ where $e_{j}\in E$ is the nested
input expression, $s_{j}\in E$ is the innermost sub-expression in $e_{j}$, and
$r_{j}\in R$ is the result of $s_{j}$.

The combiner receives the same string $e_{j}$ provided in input to the solver
together with the solver’s output, i.e. $(r_{j},s_{j})$, and produces
$e_{j-1}$, i.e. the simplified version of $e_{j}$ where the sub-expression
$s_{j}$ has been substituted by $r_{j}$. $e_{j-1}$ can be fed back into the
system until the problem is completely solved (note that the combiner module
is not required during training of the seq2seq model). Formally, the combiner
can be defined as a function $combiner\colon E\times(R\times E)\rightarrow E,\
combiner(e_{j},(r_{j},s_{j}))=e_{j-1}$.

Finally, the whole hybrid system can be defined as a function $hybrid\colon
E\rightarrow E$, $hybrid(e_{j})=combiner(e_{j},solver(e_{j}))=e_{j-1}$. Since
the output domain of $hybrid$ is the same as its input domain, it can be
applied iteratively on its own output to solve arithmetical expressions step
by step. Indeed, the system receives the expression represented as a sequence
of characters as input and outputs a reduced version of the expression, which
is fed back in the system unless the output only contains a positive or
negative integer.

###  2.1 The solver

The solver is a standard Transformer encoder-decoder [5] with a one-layer
encoder and a one-layer decoder. Our version of the model differs from the
standard Transformer only due to the use of label positional encodings [6]
rather than standard sinusoidal positional encodings. Label positional
encodings have recently been proposed as a method to improve out-of-
distribution generalization of a Transformer decoder in simple algorithmic
tasks [6]. In this work, we have applied this technique to an encoder-decoder
Transformer exploring the extent to which these encodings can be applied to
the solution of arithmetic problems, a task that is relatively similar but
slightly more complex than simple algorithmic tasks. Given a sequence of $k$
symbols, the corresponding sinusoidal positional encodings [5] are the first
$k$ vectors in a sequence of $m,m\geq k$ vectors that carry a position signal
which is generated according to the formulas
$PE_{(pos,2i)}=sin(pos/10000^{2i/d_{model}}),\ \
PE_{(pos,2i+1)}=cos(pos/10000^{2i/d_{model}})$, where $pos$ is the position of
the token in the sequence and $i$ is the dimension of the vector. When using
label positional encodings, to associate a position signal to a sequence of
$k$ symbols, rather than considering the first $k$ sinusoidal encodings, we
generate the position signal sampling $k$ integers in the interval $[0,m-1]$,
sorting them in ascending order and then taking the corresponding sinusoidal
positional encodings.

###  2.2 The combiner

The purpose of the combiner is to deterministically replace part of the input
string with the candidate solution proposed by the solver model. To enable the
deterministic substitution in the combiner, the output of the solver must
contain the expression and its numerical solution formatted according to a
specific syntax. However, this may not be the case: we call ‘halted
sequences’, the ones for which the solver output is not compliant with the
required format. Indeed, in such cases the processing of the sequence should
stop because there is no meaningful way to proceed with the simplification.

In order to reduce the number of halted sequences, we have chosen to employ a
multi-output generation strategy. For each input expression, we generate $N$
outputs sampling from the distributions obtained from the softmaxed logits
returned by the solver decoder. Since the Transformer generates the output in
an auto-regressive fashion, for each token in the output sequence we sample
from the distribution and feed back the updated sequence of output tokens to
the decoder. The set of $N$ outputs is then given as input to the combiner,
which first filters well-formed outputs, then selects the most frequently
generated sequence, and finally applies the substitution of the target with
the candidate in the input expression.

##  3 Methodology

Data One of the goals in the design of our hybrid system is to combine the
generalization capabilities of the solver with the deterministic nature of the
combiner, which should allow learning by using a relatively small subset of
the data. Intuitively, this subset should include the minimal amount of
examples necessary for the model to learn the base solution step of a complex
expression. We thus include in the training set only expressions with up to
two nested operations between integers of up to two digits.

For simplicity, in all dataset splits and nesting levels, we build expressions
that have only one operation for each nesting level. Therefore, the model
never faces the ambiguous situation in which there are multiple operations
that could be solved at the same time.

Since at test time the full hybrid system will be evaluated on expressions
with up to $10$ nested operations, it may happen that test expressions have
intermediate or final results with more than two digits. We therefore take
some measures to guarantee that the system will behave with more complex
expressions. In particular, to ensure that the distribution of the expressions
that will be used to test the model is coherent with the one that was used to
train it, we limit both training and testing expressions to the ones that have
intermediate and final results with at most two digits. Furthermore, we ensure
that at training time the Transformer observes examples of a complete solution
path of an arithmetical expression, i.e. all the steps leading to the final
result. Hence, we ensure that the first-level simplification of some training
samples involving two nested operations is also present in the training set.

To test out-of-distribution generalization more easily, we sample batches of
data on-the-fly from the distribution described above, parameterized by the
number of operations and size of operands in the expression. Given the data
generation procedure and the number of expressions that could virtually be
generated, the actual number of training examples observed by the model
depends on the number of learning iterations. To ensure the separation of the
training, validation and test splits, we use both a pre-computed split that
ensures some of the training samples have a full solution path, as well as a
hash-based split that sorts all remaining samples in three different splits
on-the-fly.

Evaluation Metrics We use two metrics in the performance evaluation of all
systems: character and sequence accuracy. Given a batch of target sequences,
we define character accuracy as the percentage of correct characters in the
output of a system, and sequence accuracy as the percentage of output
sequences that match the target exactly. When measuring the performance of the
solver and that of the hybrid system, these two metrics are applied to
different kinds of output, as the solver and the hybrid system solve two
different tasks. Both metrics, in the case of the hybrid system, are computed
considering halted sequences as mistakes, i.e. the output sequence is assumed
to be completely different from the target.

Model training The Transformer is trained in an auto-regressive regime, i.e.
without teacher forcing. We have trained all models for 150k updates using
Adam optimizer with a learning rate of $1e-4$ and batch size of 128.
To choose the best configuration for the solver hyperparameters we performed a
random search on the number of heads and the dimensionality of embeddings. For
both the Transformer encoder and decoder we have compared the performance of
models with 4 and 8 heads, 256, 512 and 1024-dimensional embeddings, and 256,
512 and 1024-dimensional hidden feed-forward layer on the in-distribution
validation set. We finally selected the solver model with 8 attention heads, a
1024-dimensional state and a 1024-dimensional feed-forward layer.

Using the multi-output generation strategy, the number of outputs generated
for each input is an hyperparameter whose choice clearly requires trading
model accuracy for speed. We compared the performance of the hybrid system on
the solution of arithmetical expressions using $N=1,20,40,60,80,100$ generated
outputs per input. We have observed that sampling as few as 20 outputs for
each input already guarantees much better results than a 1-shot output
generation, especially in terms of surviving sequences. Nevertheless, we chose
to generate 100 outputs as we observed marginal performance gains when
continuing to increase the number of outputs.

##  4 Results

| Nesting | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10
---|---|---|---|---|---|---|---|---|---|---|---
Char Acc | small | 57.2±17.5 | 92.1±15.2 | 99.2±1.3 | 97.6±4.9 | 98.4±4.5 | 99.5±1.2 | 99.9±0.2 | 99.3±0.9 | 98.1±2.8 | 98.9±1.6
medium | 72.2±17.4 | 96.8±5.4 | 99.7±1.0 | 100.0±0.0 | 100.0±0.0 | 99.7±0.8 | 100.0±0.0 | 100.0±0.1 | 99.5±1.5 | 99.6±1.2
large | 78.5±12.6 | 96.7±4.6 | 98.8±2.8 | 100.0±0.0 | 98.5±4.5 | 99.5±1.6 | 99.9±0.2 | 99.9±0.1 | 97.6±6.2 | 99.5±0.8
Seq Acc | small | 28.1±25.4 | 82.3±27.8 | 98.5±2.6 | 93.5±12.9 | 97.1±8.0 | 99.2±2.1 | 99.4±1.5 | 98.4±1.9 | 96.2±6.1 | 97.4±3.5
medium | 50.8±27.4 | 93.6±11.0 | 99.1±2.7 | 99.9±0.3 | 100.0±0.0 | 99.2±1.8 | 100.0±0.0 | 99.8±0.6 | 99.3±1.6 | 99.2±2.4
large | 56.7±25.2 | 92.2±11.8 | 97.5±5.0 | 100.0±0.0 | 97.4±7.5 | 98.7±3.3 | 99.8±0.4 | 99.3±1.0 | 96.2±9.8 | 98.7±2.1

Table 1: Character (top rows) and sequence (bottom rows) accuracy of three
different solver models on the sub-expression solution task. The models have
256-, 512- and 1024-dimensional embeddings, respectively. We report average
and standard deviation of both metrics over 10 batches of 100 sequences. The
figures show that the label positional embeddings endow the solver with strong
out-of-distribution generalization capability on the sub-expression solution
task.

Given the hybrid nature of our system, in order to measure its performance it
is meaningful to consider both the trained solver module in isolation, and the
hybrid system as a whole.

We also compare the performance of the hybrid system with that of a
Transformer encoder-decoder trained to directly output the result of
arithmetical expressions. Finally, we compare the performance of the system
with that of a Large Language Model fine-tuned for text completion.

###  4.1 Solver

We hypothesize that the solver module can leverage label positional encodings
to achieve out-of-distribution generalization capacity on the sub-expression
solution task. Therefore, the solver receives at test time complex
arithmetical expressions with up to 10 nested operations, i.e. up to 8 more
nested operations than seen during training. The goal of the model remains to
output the result of the innermost expression contained in the input
(replacement candidate) concatenated to the expression itself (replacement
target).

The sequence accuracy of the solver on the sub-expression solution task is
represented in Figure 2(a), which shows that the use of Label Positional
Encodings enables out-of-distribution generalization. We also report in Table
1 the performance of solver models with different embedding dimensionality to
provide further insight on the impact of label positional encodings. Indeed,
our results show that, independently of model size, a Transformer encoder-
decoder using label positional encodings can generalize to out-of-distribution
samples on this task.

Figure 2(a) shows that using Label Positional Encodings also leads to a lower
performance on test expressions, especially on the nesting level 1. However,
this has no impact on the functioning of the hybrid system when the multi-
output generation strategy is used.

(a) Performance of solver modules trained with Label and Sinusoidal Positional
Encodings. Label PE (multi) refers to a solver that generates 100 outputs per
input, applying the same filtering rules as the combiner.

(b) Performance of hybrid system, end-to-end and LLM baselines. Hybrid alt.
refers to a hybrid system where the combiner selects the most frequent outputs
before selecting well-formed outputs.

Figure 2: Sequence accuracy of all models we consider. The solver modules
(left) are tested on the sub-expression solution task, while the hybrid
systems and baseline models (right) are tested on the task of solution of the
full expression. In all cases we report mean and standard deviation computed
across 10 batches of 100 sequences per nesting value, except for the Davinci
model for which batches contain 10 sequences.

###  4.2 Hybrid System

We then test the entire hybrid system on the arithmetic expressions resolution
task.

Figure 2(b) shows the sequence accuracy of the hybrid system exploiting the
multi-output generation strategy with 100 outputs per input on arithmetical
expressions involving up to 10 nested operations. The performance metric shows
that the combination of the architectural elements in our model allows to
produce exact answers to harder problems than seen during training in a large
fraction of cases. The slow performance decline is proportional to expression
complexity, as it is due to the accumulation of errors committed by the solver
module in several iterations on the same expression. We have also experimented
on a possible alternative combiner mechanism, where the selection of the most
frequently generated output for a given input is done before filtering ill-
formed outputs. Figure 2(b) shows that the method (Hybrid alt.) globally still
achieves superior performance compared to baselines, but has worse performance
with respect to the default combiner mechanism in harder problems due to the
higher percentage of halted sequences, as shown in Table 2. The similar
sequence accuracy of the two methods on expressions with fewer nested
operations is due to the fact that the default combiner mechanism, despite
halting fewer sequences, commits more semantic errors on the final results.

In the Appendix we provide further experimental evidence to shed light on the
functioning of the proposed system. For completeness, we report character
accuracy of the models we consider on the expressions resolution task in Table
3. In Table 4 we provide further insight on the impact of the number of
outputs per input on both the accuracy of the hybrid system and the percentage
of halted sequences. Finally, in Table 5 we report out-of-distribution
performance metrics for hybrid systems built with differently-sized solvers to
provide experimental evidence on the impact of model size on the
generalization capacity of the system.

Nesting | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10
---|---|---|---|---|---|---|---|---|---|---
Hybrid | 0.0±0.0 | 0.0±0.0 | 0.0±0.0 | 0.0±0.0 | 0.1±0.3 | 0.3±0.5 | 0.2±0.4 | 0.8±0.7 | 1.4±0.9 | 2.1±1.4
Hybrid alt. | 0.1±0.3 | 5.1±1.8 | 6.1±2.1 | 5.8±3.2 | 8.3±3.3 | 10.1±3.9 | 12.2±5.0 | 25.6±3.9 | 36.0±5.9 | 47.7±5.3

Table 2: Percentage of halted sequences using two different combiner
mechanisms. The top row is relative to the default combiner mechanism, while
the bottom row refers to a combiner where the most frequently generated
outputs are selected before filtering out ill-formed ones.

###  4.3 Comparison with end-to-end model

To motivate empirically the presence of a deterministic component in our
hybrid system, we compare the results of our system on the solution of
arithmetical expressions with those obtained on the same problem by a
Transformer trained to directly output the result of a given arithmetical
expression. Also in this case, we use label positional encodings on the
Transformer encoder and decoder inputs, in order to control the effect of this
architectural element on the performance of the system. The training
hyperparameters and dataset splits are the same used to train the seq2seq part
of the hybrid system. Furthermore, the Transformer has the same architecture
and model size as the trained component in our system.

Figure 2(b) represents the sequence accuracy of the end-to-end trained system
on this task. It is evident that, while on in-distribution samples the end-to-
end trained Transformer has reasonably good performance, it nevertheless fails
to generalize the learned solution process on longer and more complex
expressions.

###  4.4 Comparison with a Large Language Model

Finally, we compare our hybrid system with a Large Language Model (LLM), since
these models often achieve state-of-the-art performance in sophisticated
reasoning tasks [4]. We consider the outputs provided by a version of GPT-3
[7], more precisely a variant of the model iteration generally referred to as
GPT-3.5. The version of the model we tested is the one referred to as text-
davinci-003 in the OpenAI API at the time of writing. According to OpenAI’s
official website 222https://platform.openai.com/docs/model-index-for-
researchers, the model is an InstructGPT model [8] fine-tuned for text
completion.

We prompt the model with an adapted version of our inputs, first showing the
model an example of a correctly solved expression and then asking to complete
the solution of a new expression. For example, given the expression
(((3*2)-2)+5), a possible corresponding prompt could be
((2+4)*6)=36<END>\n(((3*2)-2)+5)=. We then require via API to stop the
generation of the output string when the model outputs the <END> token. In
this way, we ensure that the vast majority of the model outputs is the
solution of the input expression proposed by the model.

Figure 2(b) shows the performance of the model in solving arithmetic
expressions. Despite the gigantic size of the model and the amount of training
data, the model cannot directly output the solution of complex arithmetical
expressions.

##  5 Related work

In this work, we explored the idea that neural networks can learn to solve
problems that require composition of elementary solution steps, like
arithmetic expressions, by iteratively applying a learned substitution rule on
the input string. Other works have recently explored similar ideas, often in
different kind of problems. In [9] the authors propose a Transformer model
that is trained to iteratively solve arithmetical expressions involving sums
and subtractions. Differently from our system, it requires twice the number of
iterations as it is trained to first highlight and then solve relevant parts
of the input expressions. The authors of [10] propose a Transformer-based
architecture to iteratively solve compositional generalization tasks. In this
work, authors exploit relative positional encodings [11] to enable out-of-
distribution generalization. Differently from our case, the proposed
architecture includes an ad-hoc trainable component named copy-decoder,
designed to facilitate learning to copy parts of the input in the output. The
authors of [12] propose two neural architectures that incorporate ad-hoc
learning biases to learn addition and multiplication generalizing beyond the
training range. However, their approach is limited to arithmetic problems and
cannot be extended to more general symbolic reasoning problems. In [13] the
idea of iteratively processing the input to learn a systematic solution
strategy is applied to the problem of visual navigation with a multimodal
architecture.

Recently, researchers have also focused on studying whether standard seq2seq
models can generalize to out-of-distribution samples in compositional tasks.
In [14] the authors show that relative positional encodings, carefully tuned
early stopping and scaling of encodings can improve the performance of a
Universal Transformer [15] on compositional generalization tasks. In a follow-
up work [16], the same authors propose an approach to the solution of
algorithmic tasks similar to the one we propose in this work. Their proposal
consists of learning step-by-step solution strategies modifying the
architecture of a Transformer encoder. Differently from our case, the authors
propose to recursively modify internal representations, rather than
iteratively manipulating symbolic, external representations.

Another recent approach to exploit deep learning models to solve reasoning
problems is to embed neural networks into existing automatic reasoning
frameworks, such as logic or probabilistic programming languages [17, 18]. In
such frameworks, systematic generalization is achieved by leveraging
constructs in the pre-existing programming languages, supporting theoretical
standpoints arguing that human cognition should be understood as a hybrid of
neural and algorithmic mechanisms [19]. In our work, instead, we are
interested in exploring the possibility that the solution process of symbolic
reasoning problems can be implemented with neural systems, leveraging simpler
additional mechanisms than the ones used in the works mentioned above, and by
injecting learning biases in the neural system to allow the iterative solution
of symbolic reasoning problems exploiting their recursive structure.

##  6 Discussion

In this paper we have proposed a hybrid system that leverages the combination
of a trained module and a deterministic one to achieve strong generalization
abilities on the solution of simple arithmetical expressions. While we have
only considered this specific task, it should be emphasized that the framework
described in section 2 can be used to describe a more general class of
symbolic problems where the solution can be derived iteratively. Indeed, one
can easily imagine cases (such as symbolic mathematics) in which starting from
the initial symbolic expression one can derive a tree - rather than a chain -
of syntactically correct expressions. Furthermore, each expression could be
the result of a more generic transformation than a solution or simplification
step, which may even make the expression longer. As a consequence, the hybrid
system we propose could in principle be adapted to a wider range of symbolic
problems than the one considered here. In future work, we plan to explore this
aspect, experimenting on tasks like symbolic mathematics, algorithmic tasks
and program synthesis.

## References

  * Hupkes et al. [2020] D. Hupkes, V. Dankers, M. Mul, E. Bruni,  Compositionality decomposed: How do neural networks generalise?,  J. Artif. Intell. Res. 67 (2020) 757–795. URL: https://doi.org/10.1613/jair.1.11674. doi:10.1613/jair.1.11674.
  * Mahdavi et al. [2023] S. Mahdavi, K. Swersky, T. Kipf, M. Hashemi, C. Thrampoulidis, R. Liao,  Towards better out-of-distribution generalization of neural algorithmic reasoning tasks,  Transactions on Machine Learning Research (2023). URL: https://openreview.net/forum?id=xkrtvHlp3P.
  * Hitzler [2022] P. Hitzler,  Neuro-symbolic artificial intelligence: The state of the art (2022).
  * Testolin [2023] A. Testolin,  Can neural networks do arithmetic? a survey on the elementary numerical skills of state-of-the-art deep learning models,  arXiv preprint arXiv:2303.07735 (2023).
  * Vaswani et al. [2017] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, I. Polosukhin,  Attention is all you need,  in: I. Guyon, U. von Luxburg, S. Bengio, H. M. Wallach, R. Fergus, S. V. N. Vishwanathan, R. Garnett (Eds.), Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, 2017, pp. 5998–6008. URL: https://proceedings.neurips.cc/paper/2017/hash/3f5ee243547dee91fbd053c1c4a845aa-Abstract.html.
  * Li and McClelland [2022] Y. Li, J. McClelland,  Systematic generalization and emergent structures in transformers trained on structured tasks,  in: NeurIPS ’22 Workshop on All Things Attention: Bridging Different Perspectives on Attention, 2022. URL: https://openreview.net/forum?id=BTNaKmYdQmE.
  * Brown et al. [2020] T. Brown, B. Mann, N. Ryder, M. Subbiah, J. D. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell, S. Agarwal, A. Herbert-Voss, G. Krueger, T. Henighan, R. Child, A. Ramesh, D. Ziegler, J. Wu, C. Winter, C. Hesse, M. Chen, E. Sigler, M. Litwin, S. Gray, B. Chess, J. Clark, C. Berner, S. McCandlish, A. Radford, I. Sutskever, D. Amodei,  Language models are few-shot learners,  in: H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, H. Lin (Eds.), Advances in Neural Information Processing Systems, volume 33, Curran Associates, Inc., 2020, pp. 1877–1901. URL: https://proceedings.neurips.cc/paper/2020/file/1457c0d6bfcb4967418bfb8ac142f64a-Paper.pdf.
  * Ouyang et al. [2022] L. Ouyang, J. Wu, X. Jiang, D. Almeida, C. Wainwright, P. Mishkin, C. Zhang, S. Agarwal, K. Slama, A. Gray, J. Schulman, J. Hilton, F. Kelton, L. Miller, M. Simens, A. Askell, P. Welinder, P. Christiano, J. Leike, R. Lowe,  Training language models to follow instructions with human feedback,  in: A. H. Oh, A. Agarwal, D. Belgrave, K. Cho (Eds.), Advances in Neural Information Processing Systems, 2022\. URL: https://openreview.net/forum?id=TG8KACxEON.
  * Deshpande et al. [2021] R. Deshpande, J. Chen, I. G. Lee,  Rect: A recursive transformer architecture for generalizable mathematical reasoning,  in: International Workshop on Neural-Symbolic Learning and Reasoning, 2021.
  * Setzler et al. [2022] M. Setzler, S. Howland, L. A. Phillips,  Recursive decoding: A situated cognition approach to compositional generation in grounded language understanding,  CoRR abs/2201.11766 (2022). URL: https://arxiv.org/abs/2201.11766. arXiv:2201.11766.
  * Shaw et al. [2018] P. Shaw, J. Uszkoreit, A. Vaswani,  Self-attention with relative position representations,  in: Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers), Association for Computational Linguistics, New Orleans, Louisiana, 2018, pp. 464–468. URL: https://aclanthology.org/N18-2074. doi:10.18653/v1/N18-2074.
  * Trask et al. [2018] A. Trask, F. Hill, S. E. Reed, J. Rae, C. Dyer, P. Blunsom,  Neural arithmetic logic units,  in: S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, R. Garnett (Eds.), Advances in Neural Information Processing Systems, volume 31, Curran Associates, Inc., 2018\. URL: https://proceedings.neurips.cc/paper_files/paper/2018/file/0e64a7b00c83e3d22ce6b3acf2c582b6-Paper.pdf.
  * Ruiz et al. [2021] L. Ruiz, J. Ainslie, S. Ontañón,  Iterative decoding for compositional generalization in transformers,  CoRR abs/2110.04169 (2021). URL: https://arxiv.org/abs/2110.04169. arXiv:2110.04169.
  * Csordás et al. [2021] R. Csordás, K. Irie, J. Schmidhuber,  The devil is in the detail: Simple tricks improve systematic generalization of transformers,  in: Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, Association for Computational Linguistics, Online and Punta Cana, Dominican Republic, 2021, pp. 619–634. URL: https://aclanthology.org/2021.emnlp-main.49. doi:10.18653/v1/2021.emnlp-main.49.
  * Dehghani et al. [2019] M. Dehghani, S. Gouws, O. Vinyals, J. Uszkoreit, L. Kaiser,  Universal transformers,  in: International Conference on Learning Representations, 2019. URL: https://openreview.net/forum?id=HyzdRiR9Y7.
  * Csordás et al. [2022] R. Csordás, K. Irie, J. Schmidhuber,  The neural data router: Adaptive control flow in transformers improves systematic generalization,  in: International Conference on Learning Representations, 2022. URL: https://openreview.net/forum?id=KBQP4A_J1K.
  * Dai and Muggleton [2021] W.-Z. Dai, S. Muggleton,  Abductive knowledge induction from raw data,  in: Z.-H. Zhou (Ed.), Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21, International Joint Conferences on Artificial Intelligence Organization, 2021, pp. 1845–1851. URL: https://doi.org/10.24963/ijcai.2021/254. doi:10.24963/ijcai.2021/254, main Track.
  * Manhaeve et al. [2018] R. Manhaeve, S. Dumancic, A. Kimmig, T. Demeester, L. De Raedt,  Deepproblog: Neural probabilistic logic programming,  in: S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, R. Garnett (Eds.), Advances in Neural Information Processing Systems, volume 31, Curran Associates, Inc., 2018\. URL: https://proceedings.neurips.cc/paper_files/paper/2018/file/dc5d637ed5e62c36ecb73b654b05ba2a-Paper.pdf.
  * Marcus [2001] G. F. Marcus, The Algebraic Mind, The MIT Press, 2001. URL: https://doi.org/10.7551/mitpress/1187.001.0001. doi:10.7551/mitpress/1187.001.0001.

##  7 Appendix

Nesting | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10
---|---|---|---|---|---|---|---|---|---|---
Transformer | 89.1±10.3 | 89.7±4.6 | 56.0±3.3 | 47.4±2.5 | 44.9±2.2 | 43.3±1.9 | 42.2±2.1 | 40.8±2.6 | 40.3±1.9 | 39.7±1.1
Davinci | 98.0±5.0 | 89.0±8.0 | 69.0±10.0 | 59.0±10.0 | 41.0±10.0 | 39.0±12.0 | 34.0±8.0 | 35.0±14.0 | 29.0±9.0 | 31.0±9.0
Hybrid | 100.0±0.0 | 93.8±1.9 | 92.2±2.7 | 91.4±2.5 | 89.8±2.9 | 86.0±2.9 | 85.1±4.7 | 81.6±4.0 | 77.0±4.8 | 74.1±3.6
Hybrid alt. | 99.9±0.2 | 91.0±2.7 | 89.4±3.9 | 88.3±3.5 | 86.9±3.2 | 83.0±4.3 | 81.4±5.0 | 69.0±4.5 | 61.4±4.6 | 53.0±3.1

Table 3: Character accuracy of the three models. We report mean and standard
deviation computed across 10 batches of 100 sequences per nesting value,
except for the Davinci model for which batches contain 10 sequences.

| Nesting | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10
---|---|---|---|---|---|---|---|---|---|---|---
Char Acc | 1-shot | 59.7±21.5 | 44.6±20.4 | 52.1±20.1 | 42.4±19.9 | 33.3±15.6 | 28.8±15.3 | 26.2±10.2 | 24.9±9.8 | 22.5±4.9 | 22.0±10.8
20 samples | 99.5±0.8 | 92.4±2.3 | 89.4±4.1 | 88.4±3.6 | 88.0±4.7 | 85.6±3.9 | 80.8±4.9 | 76.6±3.5 | 72.0±6.0 | 67.3±3.4
40 samples | 99.8±0.4 | 92.4±2.8 | 91.6±2.2 | 90.9±2.9 | 88.0±2.8 | 87.0±3.1 | 83.7±3.4 | 79.6±3.6 | 74.9±4.9 | 70.0±5.0
60 samples | 100.0±0.1 | 92.6±2.2 | 90.4±3.2 | 88.5±4.8 | 89.9±3.4 | 88.3±2.6 | 85.1±2.6 | 83.8±3.7 | 76.9±2.9 | 72.6±5.6
80 samples | 99.9±0.3 | 94.9±1.3 | 91.4±2.4 | 90.8±2.2 | 90.2±2.6 | 89.0±3.7 | 85.5±1.4 | 80.6±3.5 | 79.5±3.9 | 70.8±3.5
100 samples | 100.0±0.0 | 93.8±1.9 | 92.2±2.7 | 91.4±2.5 | 89.8±2.9 | 86.0±2.9 | 85.1±4.7 | 81.6±4.0 | 77.0±4.8 | 74.1±3.6
Seq Acc | 1-shot | 48.1±26.1 | 32.9±24.6 | 41.9±22.3 | 33.7±19.6 | 24.0±16.0 | 18.5±15.0 | 13.7±12.1 | 11.2±10.9 | 9.9±6.1 | 8.9±7.8
20 samples | 98.6±2.1 | 86.8±4.2 | 82.0±5.6 | 78.9±7.2 | 78.3±7.2 | 75.0±6.7 | 66.3±5.8 | 64.3±7.3 | 58.1±7.1 | 55.2±5.5
40 samples | 99.6±0.8 | 86.7±4.6 | 84.7±3.7 | 84.2±4.4 | 78.5±3.8 | 76.9±4.8 | 72.3±4.8 | 65.8±7.4 | 63.6±7.0 | 58.6±6.8
60 samples | 99.9±0.3 | 87.6±4.1 | 82.8±4.3 | 80.5±5.3 | 81.5±5.3 | 77.9±4.7 | 74.7±4.1 | 73.6±6.5 | 64.9±5.8 | 62.0±5.9
80 samples | 99.6±0.9 | 89.7±1.8 | 84.7±3.9 | 83.1±3.4 | 81.8±5.6 | 78.8±5.4 | 74.5±3.3 | 69.2±4.4 | 67.3±5.0 | 58.9±6.3
100 samples | 100.0±0.0 | 89.8±3.2 | 85.2±4.0 | 83.8±2.7 | 80.5±3.6 | 74.8±3.2 | 74.6±6.9 | 69.0±6.0 | 63.8±6.5 | 63.4±5.3
Halted | 1-shot | 47.5±23.8 | 59.3±27.5 | 51.2±24.6 | 50.4±24.5 | 58.9±24.6 | 66.6±27.5 | 81.7±15.3 | 84.5±14.0 | 85.9±8.1 | 76.5±27.2
20 samples | 0.0±0.0 | 0.8±0.7 | 0.7±1.3 | 2.3±2.1 | 1.9±0.8 | 1.7±1.6 | 2.2±1.9 | 5.1±2.1 | 7.4±4.0 | 11.7±3.3
40 samples | 0.0±0.0 | 0.1±0.3 | 0.1±0.3 | 0.1±0.3 | 0.5±0.5 | 0.2±0.4 | 1.0±1.0 | 2.1±1.1 | 4.5±1.8 | 7.6±2.3
60 samples | 0.0±0.0 | 0.0±0.0 | 0.1±0.3 | 0.0±0.0 | 0.2±0.4 | 0.1±0.3 | 0.3±0.5 | 1.9±1.4 | 2.5±1.4 | 4.3±2.0
80 samples | 0.0±0.0 | 0.0±0.0 | 0.1±0.3 | 0.0±0.0 | 0.0±0.0 | 0.1±0.3 | 0.3±0.5 | 0.7±0.9 | 2.3±1.3 | 4.1±2.5
100 samples | 0.0±0.0 | 0.0±0.0 | 0.0±0.0 | 0.0±0.0 | 0.1±0.3 | 0.3±0.5 | 0.2±0.4 | 0.8±0.7 | 1.4±0.9 | 2.1±1.4

Table 4: Comparison of hybrid model performance varying the number of samples
generated using the multi-output generation strategy. Figures show that
increasing the number of generated samples strongly impacts the percentage of
halted sequences, especially for more complex expressions.

| Nesting | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10
---|---|---|---|---|---|---|---|---|---|---|---
Char Acc | small | 98.8±1.1 | 92.9±2.0 | 87.3±2.2 | 83.6±2.2 | 79.4±4.2 | 70.6±2.6 | 61.1±3.6 | 50.7±4.6 | 46.2±4.2 | 39.4±3.4
medium | 100.0±0.1 | 93.9±1.4 | 91.9±1.6 | 90.9±2.5 | 90.0±1.6 | 86.4±2.1 | 78.7±3.7 | 72.1±3.9 | 66.4±5.2 | 62.2±3.6
large | 100.0±0.0 | 93.8±1.9 | 92.2±2.7 | 91.4±2.5 | 89.8±2.9 | 86.0±2.9 | 85.1±4.7 | 81.6±4.0 | 77.0±4.8 | 74.1±3.6
Seq Acc | small | 97.3±2.4 | 84.2±4.0 | 74.8±4.0 | 66.5±4.8 | 61.8±6.0 | 50.2±5.7 | 45.8±4.2 | 33.4±5.2 | 30.1±2.9 | 23.0±4.1
medium | 99.9±0.3 | 85.6±2.4 | 80.6±2.5 | 77.7±4.7 | 74.6±3.7 | 69.9±5.9 | 60.2±5.2 | 55.6±6.2 | 50.1±7.1 | 44.8±6.1
large | 100.0±0.0 | 89.8±3.2 | 85.2±4.0 | 83.8±2.7 | 80.5±3.6 | 74.8±3.2 | 74.6±6.9 | 69.0±6.0 | 63.8±6.5 | 63.4±5.3
Halted | small | 0.0±0.0 | 0.5±0.8 | 1.5±0.7 | 1.3±0.9 | 2.3±1.6 | 7.7±2.6 | 18.5±4.5 | 27.3±3.7 | 39.4±4.9 | 51.9±5.6
medium | 0.0±0.0 | 0.0±0.0 | 0.1±0.3 | 0.1±0.3 | 0.0±0.0 | 0.1±0.3 | 1.2±0.9 | 4.5±2.1 | 11.5±4.0 | 17.5±2.9
large | 0.0±0.0 | 0.0±0.0 | 0.0±0.0 | 0.0±0.0 | 0.1±0.3 | 0.3±0.5 | 0.2±0.4 | 0.8±0.7 | 1.4±0.9 | 2.1±1.4

Table 5: Comparison of hybrid model performance varying the embedding
dimensionality of the solver, using a multi-output generation strategy with
100 outputs per sequences. Smaller models make more mistakes and lead both to
higher percentage of halted sequences and to lower accuracy of the final
results.