# Neurocompositional computing:
From the Central Paradox of Cognition
to a new generation of AI systems

Paul Smolensky,1,2∗ R. Thomas McCoy,1∗ Roland Fernandez,2
Matthew Goldrick,3 Jianfeng Gao2

1Department of Cognitive Science, Johns Hopkins University
3400 N. Charles St., Baltimore, MD 21218, USA
2Microsoft Research; Redmond, WA 98052, USA.
3Department of Linguistics, Northwestern University; Evanston, IL 60208, USA.

∗To whom correspondence should be addressed; Email:
<EMAIL_ADDRESS>
###### Abstract

What explains the dramatic progress from 20th-century to 21st-century AI, and
how can the remaining limitations of current AI be overcome? The widely
accepted narrative attributes this progress to massive increases in the
quantity of computational and data resources available to support statistical
learning in deep artificial neural networks. We show that an additional
crucial factor is the development of a new type of computation.
Neurocompositional computing (Smolensky et al., 2022) adopts two principles
that must be simultaneously respected to enable human-level cognition: the
principles of Compositionality and Continuity. These have seemed
irreconcilable until the recent mathematical discovery that compositionality
can be realized not only through discrete methods of symbolic computing, but
also through novel forms of continuous neural computing. The revolutionary
recent progress in AI has resulted from the use of limited forms of
neurocompositional computing. New, deeper forms of neurocompositional
computing create AI systems that are more robust, accurate, and
comprehensible.

Artificial Intelligence (AI) has been a long time coming of age. It was Ada
Lovelace who recognized in 1843 the profound implications, extending far
beyond numerical calculation, of Charles Babbage’s design for a general-
purpose numerical computer: “in enabling mechanism to combine together general
symbols, in successions of unlimited variety and extent, a uniting link is
established between the operations of matter and … abstract mental processes”
(Bowden, 1953, Note A, p. 368). Now, more than a century and a half later, the
widespread deployment of AI has become a landmark achievement of the 21st
century, a turning point that has been likened to the industrial revolution of
the 18th century (Thomas, 2020). Properly understanding this breakthrough is
critical for controlling how AI develops in the remainder of the century, both
for maximizing its benefits and minimizing its hazards (Grosz and Stone,
2018). Here we present a new analysis of this progress, an analysis which is
yielding a new generation of AI systems.

The recent progress in AI—specifically, AI based on artificial neural networks
exploiting deep learning—has typically been attributed to merely quantitative
technological improvements: greatly increased computing power and data
quantity (Sejnowski, 2018, p. ix). Correct as far as it goes, this view
overlooks a major factor, namely the advent of neurocompositional computing,
which, according to a contemporary theory in cognitive science (Smolensky and
Legendre, 2006), is the form of computing underlying human intelligence. We
argue that, in addition to the critical expansion of computing resources, it
is the unrecognized emergence of neurocompositional computing—albeit only
implicitly, in an acutely restricted form—that has powered the most dramatic
recent advances in AI.

Despite the unprecedented progress, it is generally recognized that
contemporary AI systems still suffer serious deficiencies, including extreme
opacity and weakness in learning general knowledge from limited experience.
Here, we show how these problems are being addressed through a deeper
development of neurocompositional computing, deployed in the new AI systems we
review. In addition to learning more robustly, these new systems are more
comprehensible than standard deep learning networks, diminishing the opacity
which limits both their utility (Turek, 2016) and our ability to control their
sometimes societally-deleterious behaviors (Bender et al., 2021).

The original contributions of this article, presented in successive sections,
are these:

  * •

identifying key contributors to the power of human intelligence—the Continuity
and Compositionality Principles—which together define neurocompositional
computing;

  * •

diagnosing the limitations of 20th-century AI as rooted in the use of
computing architectures that failed to respect both these principles;

  * •

elucidating the recent progress in AI as resulting in significant part from
simultaneous adherence to both principles—achieving neurocompositional
computing to a limited degree;

  * •

presenting a general formalism from cognitive science that allows considerably
deeper realization of neurocompositional computing: Neurally-Encoded
Compositionally-Structured Tensor (NECST) computing;

  * •

showing how new NECST AI models harness the power of neurocompositional
computing to mitigate limitations of previous AI systems;

  * •

illustrating how NECST computing substantially improves both the
generalization  capacity and the comprehensibility—and consequently the
controllability—of AI systems.

The Central Paradox of Cognition and the principles defining
neurocompositional computing
What type of computing enables human intelligence? Because human intelligence
arises from the brain, the obvious answer is: neural computing (Churchland and
Sejnowski, 2016), in which information is encoded in numerical activation
vectors—patterns of activation over groups or layers of neurons (Fig. 1a).
These encodings form a vector space; the coordinates of an encoding in this
space are the numerical activation values of the neurons hosting the
activation pattern (Fig. 1b). The activation vector that encodes an output
results from spreading the activation that encodes an input among multiple
layers of neurons through connections of varying strengths or weights. In a
typical neural network AI model, the values of these weights are set by
training the model on examples of correct input/output pairs. After seeing
many such pairs, the model will ideally converge to connection weights that
produce the correct output when given an input, not only for the inputs seen
during training, but also for novel inputs in a test set.

Figure 1: Neural computing—Encoding information in numerical vector spaces.

Once a computational task is encoded in numerical vectors, solving it becomes
a problem in statistical inference. A neural network is a complex statistical
model with many parameters that are estimated from the statistics of the
training data. During learning, the model can compute, and store in its
weights, the relations between the numbers in the vector encodings produced
when processing the training examples; after learning, during testing, it can
use these learned relations to infer an output vector given an input vector
that encodes a novel input.

Neural computing respects the Continuity Principle: the encoding and
processing of information is formalized with real numbers that vary
continuously, i.e., by amounts that can be arbitrarily small. Continuity means
that knowledge about information encoded in one vector automatically
generalizes to similar information encoded in nearby vectors (Hinton,
McClelland, and Rumelhart, 1986). For instance, standard neural systems can
readily generalize their knowledge about the word lock to the word fasten
(Fig. 1b): these words appear in similar contexts within texts used for
training (they have similar ‘distributional meaning’), so neural-network
learning algorithms will encode them as vectors that are close together; as a
result, neural processing of these two encodings will produce similar
results—similarity-based generalization.

The structure of the vector space can capture other types of relationships as
well, such as having a consistent offset that represents a systematic
difference between pairs of sentences (Fig. 1c). Most importantly, continuity
enables deep learning, in which a model’s connection weights—even those deeply
buried within the network, far from the input and output encodings—can be
modified gradually to smoothly improve the model’s statistical inference of
outputs from inputs in its training set (Rumelhart, Hinton, and Williams,
1986).

Although it appears obvious that cognition deploys neural computing, virtually
all aspects of human intelligence have been formally and precisely described
since antiquity (Kiparsky and Staal, 1969) in terms of a very different type
of computing: compositional-structure processing (Janssen, 2012). In this type
of computing (Fig. 2), complex information is encoded in large
structures—compositional encodings—which are built by composing together
smaller structures that encode simpler information. To process the complex
information encoded in a large structure, it suffices to compose together the
results of processing the simpler information encoded in its smaller
substructures. This is the Compositionality Principle (Szabó, 2012).

Compositionality has long been seen as key to the power of human cognition: it
enables strong compositional generalization, enabling us to understand any one
of a potentially infinite number of novel situations by encoding the situation
internally as a novel composition of familiar, simpler parts, and composing
together our understanding of those parts. In virtually all domains of
cognition—from vision and speech to reasoning and planning—empirical
investigation over millennia has consistently shown how cognitive functions
can be well approximated as computation over appropriate compositional
structures, structures with respect to which human cognition exhibits strong
compositional generalization (Hinzen, Machery, and Werning 2012). The parts
which compose to form such encodings are sometimes familiar elements like
objects, words, concepts, and actions, and sometimes scientifically-discovered
units like phonemes—the basic sounds of speech which combine to form words,
each of which is typically denoted by a single letter in alphabetic writing
systems.

Robust compositional generalization is all-pervasive in cognition: it
underlies the power of both fast, automatic, intuitive, largely unconscious
cognition (e.g., visual processing of novel arrangements of familiar objects),
as well as slow, controlled, deliberative, conscious cognition (e.g., playing
chess with a novel initial arrangement of pieces) (Kahneman, 2011).

In sum: human cognition gets tremendous power by understanding that the world
is strongly compositional.

Compositional encodings have for centuries been formalized as intricate
arrangements of symbols—symbol structures like those we use to represent
expressions in algebra or formal logic (Newell, 1980). To take a simple
example, the two symbol structures
$[\mbox{${\color[rgb]{0,0,1}\textsf{un}\color[rgb]{0,0,0}}$}\
[{\color[rgb]{0,0,1}\textsf{lock}\color[rgb]{0,0,0}}\
{\color[rgb]{0,0,1}\textsf{able}\color[rgb]{0,0,0}}]]$ and
$[[{\color[rgb]{0,0,1}\textsf{un}\color[rgb]{0,0,0}}\
{\color[rgb]{0,0,1}\textsf{lock}\color[rgb]{0,0,0}}]\
{\color[rgb]{0,0,1}\textsf{able}\color[rgb]{0,0,0}}]$ formalize compositional
word encodings that correspond to the two meanings of unlockable: not able to
be locked (un-lockable), and able to be unlocked (unlock-able), respectively.

Fig. 2 illustrates symbolic compositional-structure processing with three
functions (notated ‘input $\mapsto$ output’). In the domain of language, Fig.
2a shows the Tree Adjoining function, which here takes as input the phrase-
structure trees for the sentence Kim hates symbols and the adverb really and
inserts the latter into the middle of the former to produce as output the
phrase-structure tree for Kim really hates symbols. This is an operation that
is known to give grammars sufficient power to achieve the level of complexity
displayed by the syntax of sentences in human languages (Joshi, 1985). In the
domain of mathematics, Fig. 2b shows a function that simplifies a ratio of
ratios into a product of ratios. In the domain of logical reasoning, Fig. 2c
shows a function that chains if-then implications: it reads q implies r and r
implies s entails q implies s, e.g., knowing that if it rains then I will
drive ($q\rightarrow r$) and if I drive then I will need to charge my car
($r\rightarrow s$) allows us to conclude if it rains then I will need to
charge my car ($q\rightarrow s$).

Figure 2: Symbolic compositional-structure computing—Encoding information in
symbol structures.

The symbols in these structures are abstract entities that are by definition
inherently discrete: unlike real numerical values, they cannot be modified by
arbitrarily small amounts (although physical drawings of what we perceive as
symbols can be). The identity of a symbol, and its position in a symbol
structure, are all-or-none: a symbol either is an A or it isn’t; it either
occupies the first position of a symbol sequence or it doesn’t.

As the contrast between Figs. 1 and 2 vividly illustrates, discrete symbolic
compositional-structure-processing computers and continuous neural computers
are profoundly different. Yet, somehow, the computer in our heads apparently
is simultaneously a neural computer and a compositional-structure computer
(Marcus, 2001). How can this be? We call this the Central Paradox of Cognition
(Smolensky, 1988).

One tempting approach for resolving this paradox would be to posit a hybrid
system that combines separate symbolic and neural machines (Andreas et al.,
2016; Wang et al., 2020; Marcus and Davis, 2019). However, such an approach is
only viable if the various components of cognition can be cleanly separated
into those that are compositional and those that are continuous. As discussed
below, this is not the case: in central cognitive domains, individual
encodings respect both the Compositionality and the Continuity Principles.
Therefore, a true resolution of the Central Paradox requires a new type of
computing—neurocompositional computing—that simultaneously satisfies both the
Continuity and Compositionality Principles.

20th-century AI limitations: Violating the principles
Evidence that human intelligence requires simultaneously respecting both the
Continuity and Compositionality Principles comes from a perhaps surprising
place: 20th-century AI.

Despite impressive advancements that inspired recurrent optimism, the AI
systems built on symbolic computing have consistently fallen far short of
human general intelligence (Minsky, 1991). The discrete material of symbolic
encodings—e.g., symbols denoting words—have often proved overly rigid to meet
the subtle demands of human cognition; for instance, while such systems can
easily generalize from lock and -able to lockable, they cannot easily
generalize from lock to fasten because those two words must be encoded as
entirely independent discrete symbols. And the discreteness of the structures
themselves also made them insufficiently flexible: even a simple discrete
sequential structure for the basic sounds of speech—roughly corresponding to
individual letters—turns out to be too rigid, as some sounds cannot be pinned
down to a single sequential position but rather simultaneously occupy, to
continuously varying degrees, a blend of multiple positions (Smolensky and
Goldrick, 2016). The strengths and weaknesses of AI systems deploying symbolic
computing (Fig. 3e–h) arise from these systems respecting the Compositionality
Principle, but not the Continuity Principle.

The AI systems (and cognitive models) of the 20th century that employed neural
computing typically did the reverse: they respected the Continuity Principle
but violated the Compositionality Principle. Continuous vector processing
endowed these models with the power to approximate arbitrarily closely any
vector-to-vector function (Hornik, Stinchcombe, and White, 1989); this
suffices for tasks that do not demand a high degree of compositional
processing, such as classifying the texture of a single image patch. But
violating the Compositionality Principle brought serious limitations which
were prominently emphasized by Jerry Fodor and Zenon Pylyshyn (1988) as well
as Gary Marcus (2001). Although neural networks are far less rigid than their
symbolic counterparts (Fig. 3a–b), they typically suffer from complementary
weaknesses (Fig. 3c–d), including striking failures of compositional
generalization (Kim and Linzen, 2020; Baroni, 2020). For instance, as noted
above, standard neural systems can easily generalize their knowledge about
lock to fasten, but these networks cannot readily generalize to novel
compositional structures involving lock, such as lockable: they lack the
compositional encodings that support such generalization.

In sum: traditional neural AI systems suffer because they do not understand
that the world is strongly compositional—they can’t, because they lack the
compositional encodings needed to realize such understanding.

Figure 3: Neural and symbolic compositional-structure computing afford
complementary strengths.

Both symbolic- and neural-based 20th-century AI systems

were non-neurocomposition-al because they violated either the Continuity or
the Compositionality Principle—resulting in serious deficiencies. Human
intelligence is possible because it deploys a type of computing that
simultaneously respects both principles: neurocompositional computing.

21st-century AI successes: First-generation (1G) neurocompositional computing

The unprecedented surge in machine intelligence we have witnessed in the 21st
century is due largely to progress in AI systems exploiting neural computing.
The field has been growing exponentially, and the diversity of network
architectures is enormous. However, we can gain insight into the roots of the
progress by focusing on two of the most successful and widely used types of
networks: Convolutional Neural Networks (CNNs) and Transformers.

CNNs (Fukushima and Miyake, 1982; LeCun et al., 1998) have been enormously
important in systems operating on visual input. Inspired by the neural
structure of mammalian visual systems, CNNs process an input image by
analyzing patches of the image with feature detectors. There are multiple
layers of feature detectors, each computed by a set of neurons with a
preferred stimulus implicitly encoded in its weights. Taking advantage of the
Continuity Principle, a CNN’s filters are learned by slowly tuning the
continuous connection weights that implement them. Each layer is structured as
a 2-d grid that mirrors the 2-d spatial structure of the image patches being
processed. Within a given layer, each feature detector analyzes all patches;
processing is, by design, position-invariant.

Critically, CNN processing also incorporates the Compositionality Principle
using spatial structure. At each layer, the analysis of the whole image is
gotten by composing together—spatially arranging—analyses of larger patches of
the previous layer’s analysis of its smaller patches.

Another, more recent, architecture for neural computing, the Transformer
(Vaswani et al., 2017), has given rise to a quantum leap in machine language
processing (Qiu et al., 2020). A Transformer takes an entire sequence of
symbols as input and produces a sequence of symbols as output. To compute the
activation vector for a given symbol at a given layer, the Transformer
calculates a weighted sum of information from vectors encoding other symbols.
It can be shown that this is equivalent to a graph with weighted links between
symbols: links along which data flows. In state-of-the-art models, these links
partially align with abstract inter-word relations posited in linguistic
theory (Manning et al., 2020).

Thus both of these truly seminal network types—CNNs and Transformers—derive
much of their power from their additional compositional structure (Henderson,
2020): spatial structure and a type of graph structure. However, these first-
generation (1G) neurocompositional computing architectures are insufficient
for general higher cognition (e.g., reasoning, language). In these domains,
compositional structure is not physical but abstract, like a planning
structure in which plans contain sub-plans which contain sub-sub-plans
(Hendler, Tate, and Drummond, 1990). CNNs, limited to spatial structure, are
clearly unable to capture such structure.

Transformers, on the other hand, use graphs, which in principle can encode
general, abstract structure, including webs of inter-related concepts and
facts. However, in Transformers, a layer’s graph is defined by its data flow,
yet this data flow cannot be accessed by the rest of the network—once a given
layer’s data-flow graph has been used by that layer, the graph disappears. For
the graph to be a bona fide encoding, carrying information to the rest of the
network, it would need to be represented with an activation vector that
encodes the graph’s abstract, compositionally-structured internal information.
The technique we introduce next—NECST computing—provides exactly this type of
activation vector.

Deepening neurocompositionality through a solution to the Central Paradox:
NECST computing
1G neurocompositional computing, illustrated by the CNN and Transformer
architectures, has contributed greatly to the progress of AI in the 21st
century. The work we now present pursues neurocompositional computing more
aggressively, aiming for stronger incorporation of the Compositionality
Principle by instilling network capabilities that enable explicit construction
and processing of general, abstract, compositionally-structured activation-
vector encodings—while staying strictly within the confines of neural
computing to respect the Continuity Principle. This is 2G neurocompositional
computing.

Neurocompositionality and compositional generalization. Increasingly deep
implementation of neurocompositionality brings increasingly robust
compositional generalization. To provide a straightforward initial example, we
consider an extremely simple task: taking as input a sequence of five digits
(e.g., $\langle$$\mathbf{\mathtt{3,9,7,4,7}}$$\rangle$), encoding the entire
sequence internally, and then reproducing that sequence as the output (Fig.
4). This copying task demands compositional generalization because it requires
learning that if the digit $\mathbf{\mathtt{4}}$ appears in position n in the
input, then $\mathbf{\mathtt{4}}$ must be placed in position n of the output,
for every possible position n. Similarly, if the digit $\mathbf{\mathtt{n}}$
appears in position 4 in the input, then $\mathbf{\mathtt{n}}$ must be placed
in position 4 of the output, for every possible digit $\mathbf{\mathtt{n}}$.

We test such compositional generalization by withholding from training all
sequences of a certain type: ‘$\mathbf{\mathtt{n}}$-in-n’ sequences, in which
there is a $\mathbf{\mathtt{1}}$ in position 1, or a $\mathbf{\mathtt{2}}$ in
position 2, etc. After training, correctly copying the unseen
$\mathbf{\mathtt{n}}$-in-n sequences requires compositional generalization
because digit $\mathbf{\mathtt{n}}$ has never been seen in position n before.

To see how increasing the degree of neurocompositionality improves
compositional generalization, we train a sequence of successively more
neurocompositional networks on the copying task (withholding
$\mathbf{\mathtt{n}}$-in-n examples): CopyNet-0, a pre-Transformer (long-
short-term memory, LSTM) neural network (Hochreiter and Schmidhuber, 1997)
which has little built-in neurocompositional structure; CopyNet-1G, a
Transformer, which uses a mildly neurocompositional data-flow-graph structure
(1G neurocompositional computing); and CopyNet-2G, a more thoroughly
neurocompositional NECST model (2G neurocompositional computing: a
NECSTransformer, described below).

a.

b.

c.

d.

Figure 4: Successive increases in a model’s degree of neurocompositional
structure bring improvements in compositional generalization.

Fig. 4 gives several illustrations of the improved compositional
generalization that comes with increased neurocompositional structure. Figs.
4a–b show how models with greater degrees of neurocompositionality perform
better with less data—in Fig. 4b, when compositional generalization is
required, and in Fig. 4a when it is not. In the latter case, all models
eventually reach 100% correct, but we see that CopyNet-2G reaches this with an
order of magnitude fewer training examples. Fig. 4c shows that CopyNet-0 does
progressively worse on sequences with more and more digits in positions they
never occupied during training, while CopyNet-1G and CopyNet-2G show little
degradation in performance. Given an $\mathbf{\mathtt{n}}$-in-n input, e.g.,
$\langle$$\mathbf{\mathtt{3,9,7,4,7}}$$\rangle$ (with $\mathbf{\mathtt{4}}$ in
position 4), CopyNet-0 is prone to produce an erroneous output in which
neighboring digits are flipped to move $\mathbf{\mathtt{n}}$ out of position
n, e.g., $\langle$$\mathbf{\mathtt{3,9,4,7,7}}$$\rangle$ (with
$\mathbf{\mathtt{4}}$ now in position 3). In contrast, CopyNet-1G and
CopyNet-2G have no difficulty performing the compositional generalization
required to produce $\mathbf{\mathtt{n}}$-in-n outputs.

How do these neural learners’ final performance levels compare to a symbolic
learner, which would be expected to reach perfect accuracy? We trained 100
distinct instances of each type of model and measured how many of the 100
instances learned the task perfectly (scoring 100% on the set of all possible
digit sequences of length 5—including all $\mathbf{\mathtt{n}}$-in-n
sequences). As Fig. 4d shows, no CopyNet-0 instance performed perfectly; about
one third of CopyNet-1G instances reached perfect performance; and over two
thirds of CopyNet-2G instances attained perfection.

In sum, greater neurocompositionality brings faster learning (Fig. 4a–b), more
robust compositional generalization (Fig. 4c), and an increased chance of
learning the task perfectly (Fig. 4d). All of these improvements lie in areas
that have traditionally been strengths of symbolic systems yet weaknesses of
neural systems (as exhibited by CopyNet-0). These results, along with findings
on more complex tasks reported below, support the conclusion that
neurocompositionality endows neural models with some of the strengths of
symbolic models while retaining the power of deep learning.

So how, exactly, has neurocompositional computing progressed to 2G?

NECST computing defined. At the foundation of 2G neurocompositional computing
is the question: How can fully general, abstract compositional structures be
encoded in neural activation vectors so that compositional-structure
processing can be carried out on these encodings using only continuous neural
computing? The answer we adopt from cognitive science—NECST (Smolensky and
Legendre, 2006)—is a solution to the Central Paradox of Cognition: How can our
own cognitive encodings simultaneously be neural encodings and compositional
encodings (Hofstadter, 1979)?

The first insight exploited by NECST is that buried within compositional
structures are two distinct types of information that are tightly bound
together: what information and where information. Crucially, where refers to a
position in an abstract structure, not literally a position in physical space.

Consider a simple, discrete compositional structure: a sequence of two
symbols, i.e., an ordered pair. In
$[\mbox{${\color[rgb]{0,0,1}\textsf{lock}\color[rgb]{0,0,0}}$}\
\mbox{${\color[rgb]{0,0,1}\textsf{able}\color[rgb]{0,0,0}}$}]$, the what
comprises two symbols, lock and able; the where comprises two abstract
positions: L (left) and R (right). L and R are structural roles, and they
define a structural type: the ordered pair. We can visualize L as $\left[\
\boxed{{\color[rgb]{1,1,1}x}}\ \textrm{---}\ \right]$ and R as $\left[\
\textrm{---}\ \boxed{{\color[rgb]{1,1,1}x}}\ \right]$. In [lock able], role L
is filled by lock and role R is filled by able. This structure comprises two
filler-role bindings, each of which we write as filler:role. Our pair can be
written as lock:L & able:R and visualized as $\left[\
\boxed{{\color[rgb]{0,0,1}\textsf{lock}\color[rgb]{0,0,0}}}\ \textrm{---}\
\right]$ & $\left[\ \textrm{---}\
\boxed{{\color[rgb]{0,0,1}\textsf{able}\color[rgb]{0,0,0}}}\ \right]$; the two
bindings are aggregated (by the & operator) to form a single structure. In
NECST computing, this formal characterization of the structure is neurally
encoded as a kind of vector, as follows.

Each filler symbol is encoded by an activity vector, a list of real numbers
(potentially resulting from deep learning). This is commonplace in neural
network modeling: as previously observed, replacing discrete symbols with
continuous vectors is at the heart of the 21st-century revolution in machine
language processing. A key innovation of NECST is that each structural role is
similarly encoded by an activity vector. Then the two operations, : for
binding each filler to its role and & for aggregating the bindings, are
realized as operations on vectors. The aggregation operation & becomes the
summation of vectors, +. The binding operation : is a little more complex; it
becomes the tensor product $\otimes$ (possibly compressed).111The tensor
product yields encodings that are a special kind of vector: a tensor, which we
can take to be a set of real numbers that can be visualized as forming a
multi-dimensional grid. For the tensor product of a filler vector
$\mathbf{f}=(f_{1},f_{2},\mathellipsis)$ and a role vector
$\mathbf{r}=(r_{1},r_{2},\mathellipsis)$, this is a 2-D grid; the number in
the $i^{\textrm{th}}$ row and $j^{\textrm{th}}$ column is simply $f_{i}r_{j}$.

The resulting neural encoding is called the Tensor Product Representation
(TPR) of the compositional structure (Smolensky, 1990). Hence the name,
Neurally-Encoded Compositionally-Structured Tensor (NECST) computing. There
are several neurocompositional architectures known by different names (Gayler,
2003; Eliasmith, 2013; Garcez et al., 2019), but many of these turn out to be
based on TPRs that have been compressed by a linear transformation (Smolensky
and Legendre, 2006, Ch. 7).

Crucial to the power of symbol structures is that symbols maintain their
identity as they play different roles (Mitchell and Lapata, 2010, p. 1394).
The role R of $[\mbox{${\color[rgb]{0,0,1}\textsf{un}\color[rgb]{0,0,0}}$}\
\mbox{${\color[rgb]{0,0,1}\textsf{lock}\color[rgb]{0,0,0}}$}]$ and the role L
of $[\mbox{${\color[rgb]{0,0,1}\textsf{lock}\color[rgb]{0,0,0}}$}\
\mbox{${\color[rgb]{0,0,1}\textsf{able}\color[rgb]{0,0,0}}$}]$ are filled by
the same symbol, lock; in a symbolic language-processing model, this is why
lock contributes the same meaning to both unlock and lockable—making
compositional generalization possible. This critical property also holds for
the continuous, explicitly compositional vector encodings provided by TPRs,
because the same vector that encodes lock appears in the vectors that encode
the binding lock:R and the binding lock:L. TPRs successfully disentangle the
what and the where information carried by compositional structure; these very
different types of information are thoroughly fused in traditional non-
compositional neural models.

All types of compositional structures comprise a set of filler:role bindings
(Newell, 1980): TPRs provide a fully general method for neurally encoding
compositional structure. Further, the mathematical operations that underlie
TPRs enable systematic, compositional generalization, so that TPRs do not just
encode compositional structure but specifically do so in a way that
facilitates the behavioral benefits of compositional structure. In fact,
mathematical results show that with inputs and outputs encoded as TPRs, neural
networks can be designed to precisely compute many complex compositional-
structure processing functions—including the types of functions shown in Fig.
2 (Smolensky, 2012). Thus the intricate structure-sensitive processing that
empowers symbolic computing (Fodor and Pylyshyn, 1988) can be performed by
networks using TPR encodings. In cognitive science, theories of language based
in TPRs have given rise to new computational architectures for grammars; these
have significantly advanced linguistic theories explaining the compositional
structure of language (Pater, 2009; Prince and Smolensky, 1997). Networks
processing TPRs can enforce the strong kind of constraints on compositional
processes that are imposed by grammars.

Thus NECST does indeed provide an answer to the Central Paradox: it provably
allows neural computing to carry out important types of compositional-
structure processing previously only computable by discrete symbolic
computing. But NECST goes beyond symbolic computing, reaping the benefits of
the Continuity Principle. TPRs provide a new type of encoding: continuous
compositional structure (Goldrick, Putnam, and Schwarz, 2016; Smolensky,
Goldrick, and Mathis, 2014). Returning to the example of the ordered pair
structure, halfway between the two vectors encoding the discrete roles L and R
is a vector which encodes a continuous role; this blend of the L and R roles
can be bound to a filler such as t to produce the TPR for a binding we can
visualize as $\left[\ \boxed{\mbox{\scriptsize\ \ \ {t} \ \ \ }}\ \right]$.
Here, t fills a weak, half-strength role that spans both the left and right
halves of the pair: t is half-present in both places at once. Moreover, TPRs
enable a single role like L to be filled with a blend of symbols, each
simultaneously present (or active) to a continuously variable degree.

Such continuous structures may seem odd, but recent work in linguistics (e.g.,
Rosen, 2019; Zimmermann, 2019) has shown how they make possible theories that
cover bodies of data that no single theory using discrete structure can. For
example, basic speech sounds can fill continuous roles: the t sound appearing
in the middle of the French phrase petit ami (literally, ‘small friend’)
simultaneously resides both at the end of the first and the beginning of the
second word (Smolensky, Rosen, and Goldrick, 2020): exactly a case of $\left[\
\boxed{\mbox{\scriptsize\ \ \ {t} \ \ \ }}\ \right]$. Such continuous
compositional structure can explain observed complex sound patterns that can
be explained by no single theory—even a probabilistic one—that forces such
sounds into discrete roles.

Progress from early NECST AI: 2G neurocompositional computing
To illustrate 2G neurocomputing, we present the NECSTransformer (Schlag et
al., 2019). Recall that the original Transformer constructs its own implicit
data-flow graph for each input symbol sequence, for each layer; this
determines, for a given symbol, the extent to which other symbols are
consulted for information to determine the vector that encodes the given
symbol at that layer. In the NECSTransformer, this vector has explicit
compositional structure: it is the TPR for a continuous structure composed
from a given number—$n_{r}$—of parts determined by $n_{r}$ roles, roles which
vary across symbols, layers, and inputs, and result from deep learning. To
create its TPR at a given layer, each symbol generates $n_{r}$ vectors to
encode its roles, and computes a filler for each of these roles. Each filler
is a weighted sum of encodings of other symbols in the same layer.

This model generates a graph at each layer, but goes beyond the plain
Transformer by labeling each link with a vector that encodes a relation: a
relation that holds between the symbol that sends a filler and the symbol
receiving it, which binds it to the corresponding role vector it has
generated. Crucially, this relationship is no longer merely implicit in the
information flow: it is inserted explicitly into the TPR activation vector
that encodes the symbol, making it information that is fed directly to
subsequent layers for further processing. For example, in a math-problem-
solving application, the TPR created to encode a digit in a divisor includes a
role interpretable as ‘denominator’, bound to a filler sent from a numerator
digit.

Interpreting structural relations invented through deep learning. The explicit
encoding of relations computed by the NECSTransformer enables it to learn
general abstract graph structures; in fact, each NECSTransformer model uses
deep learning to invent its own type of compositional structure to optimally
perform its task. On math problem solving, when encoding a ratio of ratios,
the invented structures implicitly exploit the inference rule in Fig. 2b,
assigning the same role to the denominator-of-a-denominator as to a numerator-
of-a-numerator (respectively v and x in Fig. 2b) (Schlag et al., 2019).

Two other NECST models that process English invent structures that are
partially interpretable in grammatical terms, although no information is given
to the models about grammar in general or the structure of English in
particular. In a model that learns to answer questions about Wikipedia
articles, QANet, the roles learned for TPR encodings of English questions
partially align with recognizable linguistic structural properties, at levels
ranging from small features of words (such as plural), to general semantic
categories like predicate (expressed by verbs and adjectives) to an invented
type of multi-word sequence that could be called a wh-restrictor-phrase, like
what famous event in history (Palangi et al., 2018). Another model,
CaptionNet, learns to generate image captions, in the process inventing roles
that are highly predictive of the sequence of parts of speech (noun,
adjective, etc.) in the captions it generates (Huang et al., 2018, 2019).

Improved compositional generalization. StoryNet (Schlag and Schmidhuber, 2018)
is a NECST model that answers questions about short synthetic narratives
(Weston et al., 2015), such as the one shown in Fig. 5b. To test compositional
generalization, during training certain character names were allowed to appear
in only some fraction of the multiple subtasks in this dataset; the model was
then tested on all subtasks using these withheld character names. The smaller
the fraction of subtasks in which a given name was seen during training, the
more compositional generalization is required, and as the plot shows, the more
StoryNet decisively dominates the previous state-of-the-art system.

On two highly challenging natural tasks involving much more than simple
compositionality, NECST models achieved new state-of-the-art performance. One
is CaptionNet: image captioning requires learning an extremely complex
relationship between the two very different, approximately compositional,
natures of images and sentences. Another is a NECSTransformer model that
generates text summaries (Jiang et al., 2021), SummaryNet. Without being told
to do so, the model invents structure that parcels syntax—sentence
structure—into roles, and semantics—meaning—into fillers.

Figure 5:  NECST models showing improved compositional generalization over
previous models from designed, symbolically-motivated inductive
biases—ProgNet: Chen et al. (2020); StoryNet: Schlag and Schmidhuber (2018).

Benefits of improved comprehensibility from 2G neurocompositional
computing
In addition to improved compositional generalization, closer alignment with
the type of computing underlying human cognition renders NECST AI systems more
human-comprehensible, as already illustrated by QANet and CaptionNet. Because
2G neurocompositional AI systems are significantly less opaque than previous
neural models, they deliver several important benefits for overcoming serious
problems facing the development of  more explainable, trustworthy, and
controllable AI systems (Adadi and Berrada, 2018) .

Informing deep structure learning. Centuries of successful analysis of
cognition as compositional-structure processing have given cognitive science
and traditional symbolic AI powerful symbolic theories for computing cognitive
functions, but the computational chasm separating symbolic compositional
processing from traditional non-compositional neural computing has rendered
this wealth of insight largely unusable for constructively informing the
development of contemporary, deep-learning-based AI. Neurocompositional
computing opens the door to using such theories to inform—i.e., improve the
inductive bias of—neural learning.

An example is provided by the NECST-generation AI model, ProgNet (Fig. 5a),
which learns to take a problem stated in English and produce a computer
program that solves the problem; one version solves math word problems,
another, Lisp-programming problems (Chen et al., 2020). Like CaptionNet and
SummaryNet above, ProgNet solves a task requiring far more than identifying
compositional structure. Computing the linguistic subparts of the English
problem statement (e.g., in Fig. 5a, the number in the range from 1 to b
inclusive that has the maximum value when its digits are reversed) is an
important first step, but translating such English expressions into the
corresponding sequence of Lisp commands requires rich knowledge of how the
syntax and semantics of English expressions correspond to the syntax and
semantics of Lisp operations, and knowledge of how composition of the English
subparts relates to composition of the Lisp subparts.

Previous models for such program-generation tasks produce the output program
one symbol at a time, but NECST enables models that take advantage of the
structure inherent in the programs: a sequence of commands, each a tuple
consisting of an operation and the arguments it operates upon, such as (add,
x, 5) or (append, list1, list2). ProgNet is designed to bias learning towards
producing not a sequence of individual symbols, but a sequence of TPRs, each
decodable as such a tuple of symbols comprising a command. Informing the model
in this way about the structure of its outputs allowed it to set a new state
of the art for both problem-solving tasks, generating Lisp programs as long as
55 commands perfectly. And the similarity structure of the learned vector
encodings of symbols can be partially interpreted: for example, arithmetic
operators cluster together, as do geometric functions like area, and
operations for processing character sequences.

A second example, already introduced, is StoryNet (Schlag and Schmidhuber,
2018), which was provided with valuable biases for compositional learning
(recall Fig. 5b). This network learned to encode abstractions of entities and
relations as vectors and to use built-in operations to bind them together into
a TPR that explicitly encodes a continuous graph structure capturing knowledge
of the events in the narrative. The learning bias provided to this network was
a set of useful built-in operations for updating, as each sentence of the
narrative arrives, the vector encoding the continuous knowledge graph, and for
sequentially extracting information from the graph to answer questions. The
model successfully learned how to use these operations.

Diagnosing errors. Recall that the NECST model QANet, in the service of
learning to answer questions about Wikipedia articles, invents a number of
roles that can be interpreted grammatically. In addition, some learned fillers
can be interpreted semantically (Fig. 6b). The word Who has several meanings,
and which filler is assigned to a particular instance of Who correlates with
which meaning is appropriate for the specific context of that instance. In the
articles’ many mentions of the TV character named Dr. Who, the model sometimes
assigns Who the filler that would be appropriate for a question word, as in
Who died? (although QANet made this error at a considerably lower rate than a
state-of-the-art probabilistic symbolic system designed for analyzing English
sentences, Manning 2017). When the model made this internal filler error, it
was 5 times more likely to produce an incorrect output—an output that would
have been appropriate had Who actually been a question word rather than a
character name (Palangi et al., 2018).

Figure 6: Example NECST analyses demonstrating new capabilities enabled by
greater comprehensibility: Controlling output and diagnosing errors—RoboNet:
Soulos et al. (2020); QANet: Palangi et al. (2018).

Controlling output. The incomprehensibility of contemporary black-box non-
compositional neural AI models severely limits our ability to control them.
This lack of control is problematic; for example, it makes it challenging to
address the socially toxic biases the outputs of these models often display
(Bender et al., 2021). In contrast, the relative comprehensibility of NECST
encoding vectors can enable direct intervention—precision surgery—on internal
activation patterns in order to control the output of a network.

Our illustration of this introduces a discovery revealed by NECST analysis
techniques about the internal encodings learned by standard neural networks
(McCoy et al., 2019). (For a demo, see http://rtmccoy.com/tpdn/tpr_demo.html.)
One case study concerned a simple hypothetical robot: given an input
description of a maneuver in highly simplified English, the task of the
network (which we dub RoboNet) is to produce an appropriate output sequence of
basic commands to carry out that maneuver (Lake and Baroni, 2018).

When RoboNet is given extensive training data that widely exemplifies the
compositional possibilities inherent in its highly compositional artificial
task, it achieves good compositional generalization. A NECST-based analysis
revealed that in this case the key internal encoding can be extremely well
approximated by a TPR encoding of the input, with appropriate role assignments
to input words and appropriate vector encodings of these words and their roles
(Soulos et al., 2020). As depicted in Fig. 6a, this understanding of RoboNet’s
learned encodings as TPRs of approximately-discrete structures allows us to
write a closed-form expression for the learned vector [2] that internally
encodes any given input [1], which in turn tells us exactly how to take the
internal encoding of an input such as jump twice and directly modify it into
the encoding that would be produced by jump thrice: we subtract the vector
hidden in this encoding that encodes twice and add the vector that encodes
thrice [4]—in the process, changing the activation level of every neuron by a
precisely-determined amount. Now the output of the model changes from jump
jump [3] to jump jump jump [5]; that is, the alterations that we have made to
the model’s internal encodings produce exactly the behavioral alteration we
intended to make, illustrating how the interpretable structure of TPRs
facilitates control of a model’s behavior.

Considerably more complex modifications, and extended sequences of successive
modifications, can also be successfully effected in this way. The eight-word
input in [6] produces the encoding vector [7] and output [8]. We can change
this encoding to match that of a virtual input that differs from it in five
words [12] by taking five steps of subtracting the encoding of an existing
word and adding in the encoding of a new virtual word [9]. (TL, TR denote
Turn-Left and Turn-Right;
$\overrightarrow{\mathsf{{\color[rgb]{0,0,1}\textsf{twice}\color[rgb]{0,0,0}}_{\color[rgb]{0,0,1}\textsf{8}\color[rgb]{0,0,0}}}}$
is the vector encoding of twice:8, the binding of filler twice to role 8.) The
resulting encoding produces the output [11] that correctly corresponds to the
virtual new input [12]: the original 13 output commands have been replaced by
30 new ones. The plot shows how, even after many such successive
substitutions, the internal modifications specified by our NECST analysis
continue to control behavior with high accuracy.

Current limitations: The road to 3G neurocompositional computing
The deployment of TPRs in AI has already led to significant progress, but the
gains are clearly still short of those expected from full compositional
abilities. Why is that? The work to date is only the first step towards fully
achieving NECST computing, falling short in several respects. Identifying
these shortcomings, and proposing techniques for addressing them, provides a
road to 3G neurocompositional computing.

First, while the TPRs of 2G systems successfully disentangle the what and
where aspects of compositional structure, there is nothing to explicitly bias
the model to learn processing that takes advantage of this disentanglement to
promote compositional generalization. Building such a bias into the network
structure will be a key component of 3G neurocompositional computing.

Second, the mathematics of TPRs allows them to embed inside one another just
as $[{\color[rgb]{0,0,1}\textsf{lock}\color[rgb]{0,0,0}}\
{\color[rgb]{0,0,1}\textsf{able}\color[rgb]{0,0,0}}]$ can be embedded within
$[\mbox{${\color[rgb]{0,0,1}\textsf{un}\color[rgb]{0,0,0}}$}\
[{\color[rgb]{0,0,1}\textsf{lock}\color[rgb]{0,0,0}}\
{\color[rgb]{0,0,1}\textsf{able}\color[rgb]{0,0,0}}]]$. The corresponding
neural operations are beyond 2G NECST computing, but are now in development,
and will be integral to 3G.

Third, the transformative advances in grammatical theory derived from NECST
center on the innovation that grammatical expressions are encoded in
activation vectors that optimally satisfy grammatical constraints which are
encoded in the strengths of connections joining neurons (Prince and Smolensky,
1993/2004, 1997) . To go beyond the relatively modest gains in natural
language processing observed in 2G neurocompositional computing, incorporating
such optimization-based processing into 3G neurocompositional computing may
set the stage for major breakthroughs in language processing, as it did in
linguistic theory. An initial step in this direction shows how NECST can
strengthen inference ability by enabling the meaning of symbols denoting
particular entities and relations to adapt continuously to—to be optimized
for—their structural context within a knowledge graph of facts (Lalisse and
Smolensky, 2019).

The research program reviewed here aspires to a reconvergence of AI and
cognitive science through a unified theory of the computing underlying both
human and machine intelligence. Recognizing the importance of such a synergy
is not new: it was already envisioned nearly two centuries ago by Ada
Lovelace, who saw that in the general purpose computer, “not only the mental
and the material, but the theoretical and the practical, are brought into more
intimate and effective connexion with each other” (Bowden, 1953, Note A, p.
369). It is our hope that the development of neurocompositional computing will
ultimately contribute to the realization of her remarkably prescient vision of
intelligent machines.

## References

  * Adadi and Berrada (2018) Adadi, A., and Berrada, M.  2018\.  Peeking inside the black-box: A survey on explainable artificial intelligence (XAI).  IEEE Access 6:52138–52160.
  * Andreas et al. (2016) Andreas, J.; Rohrbach, M.; Darrell, T.; and Klein, D.  2016\.  Neural module networks.  In IEEE Conference on Computer Vision and Pattern Recognition, 39–48.
  * Baroni (2020) Baroni, M.  2020\.  Linguistic generalization and compositionality in modern artificial neural networks.  Philosophical Transactions of the Royal Society B: Biological Sciences 375(1791):20190307.
  * Bender et al. (2021) Bender, E. M.; Gebru, T.; McMillan-Major, A.; and Shmitchell, S.  2021\.  On the dangers of stochastic parrots: Can language models be too big?  In ACM Conference on Fairness, Accountability, and Transparency, 610–623.
  * Bowden (1953) Bowden, B. V.  1953\.  Faster than thought: A symposium on digital computing machines.  Pitman Publishing, Inc.
  * Chen et al. (2020) Chen, K.; Huang, Q.; Palangi, H.; Smolensky, P.; Forbus, K. D.; and Gao, J.  2020\.  Mapping natural-language problems to formal-language solutions using structured neural representations.  In International Conference on Machine Learning, 1566–1575.  PMLR.
  * Churchland and Sejnowski (2016) Churchland, P. S., and Sejnowski, T. J.  2016\.  The computational brain.  MIT press.
  * Eliasmith (2013) Eliasmith, C.  2013\.  How to build a brain: A neural architecture for biological cognition.  Oxford University Press.
  * Fodor and Pylyshyn (1988) Fodor, J. A., and Pylyshyn, Z. W.  1988\.  Connectionism and cognitive architecture: A critical analysis.  Cognition 28(1-2):3–71.
  * Fukushima and Miyake (1982) Fukushima, K., and Miyake, S.  1982\.  Neocognitron: A self-organizing neural network model for a mechanism of visual pattern recognition.  In Competition and Cooperation in Neural Nets. Springer.  267–285.
  * Garcez et al. (2019) Garcez, A. d.; Gori, M.; Lamb, L. L. S.; Spranger, M.; and Tran, S. N.  2019\.  Neural-symbolic computing: An effective methodology for principled integration of machine learning and reasoning.  Journal of Applied Logics 6(4):611–632.
  * Gayler (2003) Gayler, R. W.  2003\.  Vector symbolic architectures answer jackendoff’s challenges for cognitive neuroscience.  In Joint International Conference on Cognitive Science.
  * Goldrick, Putnam, and Schwarz (2016) Goldrick, M.; Putnam, M.; and Schwarz, L.  2016\.  Coactivation in bilingual grammars: A computational account of code mixing.  Bilingualism: Language and Cognition 19(5):857–876.
  * Grosz and Stone (2018) Grosz, B. J., and Stone, P.  2018\.  A century-long commitment to assessing artificial intelligence and its impact on society.  Communications of the Association for Computing Machinery 61(12):68–73.
  * Henderson (2020) Henderson, J.  2020\.  The unstoppable rise of computational linguistics in deep learning.  In Association for Computational Linguistics.
  * Hendler, Tate, and Drummond (1990) Hendler, J. A.; Tate, A.; and Drummond, M.  1990\.  Ai planning: Systems and techniques.  AI magazine 11(2):61–61.
  * Hinton, McClelland, and Rumelhart (1986) Hinton, G. E.; McClelland, J. L.; and Rumelhart, D. E.  1986\.  Distributed representations.  In Rumelhart, D. E.; McClelland, J. L.; and the PDP Research Group., eds., Parallel Distributed Processing: Explorations in the microstructure of cognition: Vol. 1, Foundations. MIT Press.  77–109.
  * Hinzen, Machery, and Werning (2012) Hinzen, W.; Machery, E.; and Werning, M., eds.  2012\.  The Oxford Handbook of Compositionality.  Oxford University Press.
  * Hochreiter and Schmidhuber (1997) Hochreiter, S., and Schmidhuber, J.  1997\.  Long short-term memory.  Neural Computation 9(8):1735–1780.
  * Hofstadter (1979) Hofstadter, D. R.  1979\.  Gödel, Escher, Bach: An Eternal Golden Braid.  Basic Books.
  * Hornik, Stinchcombe, and White (1989) Hornik, K.; Stinchcombe, M.; and White, H.  1989\.  Multilayer feedforward networks are universal approximators.  Neural Networks 2(5):359–366.
  * Huang et al. (2018) Huang, Q.; Smolensky, P.; He, X.; Deng, L.; and Wu, D.  2018\.  Tensor product generation networks for deep NLP modeling.  In North American Association for Computational Linguistics.
  * Huang et al. (2019) Huang, Q.; Deng, L.; Wu, D.; Liu, C.; and He, X.  2019\.  Attentive tensor product learning.  In American Association for Artificial Intelligence, volume 33, 1344–1351.
  * Janssen (2012) Janssen, T. M. V.  2012\.  Compositionality: Its historical context.  In Hinzen, W.; Machery, E.; and Werning, M., eds., The Oxford Handbook of Compositionality. Oxford University Press.
  * Jiang et al. (2021) Jiang, Y.; Celikyilmaz, A.; Smolensky, P.; Soulos, P.; Rao, S.; Palangi, H.; Fernandez, R.; Smith, C.; Bansal, M.; and Gao, J.  2021\.  Enriching transformers with structured tensor-product representations for abstractive summarization.  In North American Chapter of the Association for Computational Linguistics, 4780–4793.
  * Joshi (1985) Joshi, A. K.  1985\.  Tree adjoining grammars: How much context-sensitivity is required to provide reasonable structural descriptions?  In Dowty, D. R.; Karttunen, L.; and Zwicky, A. M., eds., Natural language parsing: Psychological, computational, and theoretical perspectives, Studies in Natural Language Processing. Cambridge University Press.  206–250.
  * Kahneman (2011) Kahneman, D.  2011\.  Thinking, fast and slow.  Macmillan.
  * Kim and Linzen (2020) Kim, N., and Linzen, T.  2020\.  COGS: A compositional generalization challenge based on semantic interpretation.  In Empirical Methods in Natural Language Processing.
  * Kiparsky and Staal (1969) Kiparsky, P., and Staal, J. F.  1969\.  Syntactic and semantic relations in Pāṇini.  Foundations of Language 83–117.
  * Lake and Baroni (2018) Lake, B. M., and Baroni, M.  2018\.  Generalization without systematicity: On the compositional skills of sequence-to-sequence recurrent networks.  In International Conference on Machine Learning, 2879–2888.
  * Lalisse and Smolensky (2019) Lalisse, M. R., and Smolensky, P.  2019\.  Augmenting compositional models for knowledge base completion using gradient representations.  In Society for Computation in Linguistics, 257–266.
  * LeCun et al. (1998) LeCun, Y.; Bottou, L.; Bengio, Y.; and Haffner, P.  1998\.  Gradient-based learning applied to document recognition.  Proceedings of the IEEE 86(11):2278–2324.
  * Manning et al. (2020) Manning, C. D.; Clark, K.; Hewitt, J.; Khandelwal, U.; and Levy, O.  2020\.  Emergent linguistic structure in artificial neural networks trained by self-supervision.  Proceedings of the National Academy of Sciences 117(48):30046–30054.
  * Manning (2017) Manning, C. D.  2017\.  Stanford parser.  nlp.stanford.edu/software/lex-parser.shtml.
  * Marcus and Davis (2019) Marcus, G., and Davis, E.  2019\.  Rebooting AI: Building artificial intelligence we can trust.  Pantheon.
  * Marcus (2001) Marcus, G.  2001\.  The algebraic mind: Integrating connectionism and cognitive science.  MIT press.
  * McCoy et al. (2019) McCoy, R. T.; Linzen, T.; Dunbar, E.; and Smolensky, P.  2019\.  RNNs implicitly implement tensor product representations.  In International Conference on Learning Representations.
  * Minsky (1991) Minsky, M.  1991\.  Logical vs. analogical or symbolic vs. connectionist or neat vs. scruffy.  AI Magazine 12(2):34–51.
  * Mitchell and Lapata (2010) Mitchell, J., and Lapata, M.  2010\.  Composition in distributional models of semantics.  Cognitive Science 34(8):1388–1429.
  * Newell (1980) Newell, A.  1980\.  Physical symbol systems.  Cognitive Science 4(2):135–183.
  * Palangi et al. (2018) Palangi, H.; Smolensky, P.; He, X.; and Deng, L.  2018\.  Question-answering with grammatically-interpretable representations.  In American Association for Artificial Intelligence, 5350–5357.
  * Pater (2009) Pater, J.  2009\.  Weighted constraints in generative linguistics.  Cognitive Science 33(6):999–1035.
  * Prince and Smolensky (19932004) Prince, A. S., and Smolensky, P.  1993/2004.  Optimality Theory: Constraint interaction in generative grammar.  Blackwell Publishers.
  * Prince and Smolensky (1997) Prince, A. S., and Smolensky, P.  1997\.  Optimality: From neural networks to universal grammar.  Science 275(5306):1604–1610.
  * Qiu et al. (2020) Qiu, X.; Sun, T.; Xu, Y.; Shao, Y.; Dai, N.; and Huang, X.  2020\.  Pre-trained models for natural language processing: A survey.  Science China Technological Sciences 1–26.
  * Rosen (2019) Rosen, E. R.  2019\.  Learning complex inflectional paradigms through blended gradient inputs.  In Society for Computation in Linguistics, 102–112.
  * Rumelhart, Hinton, and Williams (1986) Rumelhart, D. E.; Hinton, G. E.; and Williams, R. J.  1986\.  Learning internal representations by error propagation.  In Rumelhart, D. E.; McClelland, J. L.; and the PDP Research Group., eds., Parallel Distributed Processing: Explorations in the microstructure of cognition: Vol. 1, Foundations. MIT Press.  318–362.
  * Schlag and Schmidhuber (2018) Schlag, I., and Schmidhuber, J.  2018\.  Learning to reason with third order tensor products.  In Advances in Neural Information Processing Systems), 9981–9993.
  * Schlag et al. (2019) Schlag, I.; Smolensky, P.; Fernandez, R.; Jojic, N.; Schmidhuber, J.; and Gao, J.  2019\.  Enhancing the transformer with explicit relational encoding for math problem solving.  In NeurIPS Workshop on Context and Composition in Biological and Artificial Neural Systems.  arXiv:1910.06611v2.
  * Sejnowski (2018) Sejnowski, T. J.  2018\.  The deep learning revolution.  MIT press.
  * Smolensky and Goldrick (2016) Smolensky, P., and Goldrick, M.  2016\.  Gradient symbolic representations in grammar: The case of French liaison.  Rutgers Optimality Archive 1552\.
  * Smolensky and Legendre (2006) Smolensky, P., and Legendre, G.  2006\.  The harmonic mind: From neural computation to Optimality-Theoretic grammar. Vol. 1: Cognitive architecture; vol. 2: Linguistic and philosophical implications.  MIT press.
  * Smolensky et al. (2022) Smolensky, P.; McCoy, R. T.; Fernandez, R.; Goldrick, M.; and Gao, J.  2022\.  Neurocompositional computing in human and machine intelligence: A tutorial.  Microsoft Technical Report MSR-TR-2022-5.  https://www.microsoft.com/en-us/research/publication/neurocompositional-computing-in-human-and-machine-intelligence-a-tutorial/.
  * Smolensky, Goldrick, and Mathis (2014) Smolensky, P.; Goldrick, M.; and Mathis, D.  2014\.  Optimization and quantization in gradient symbol systems: A framework for integrating the continuous and the discrete in cognition.  Cognitive Science 38(6):1102–1138.
  * Smolensky, Rosen, and Goldrick (2020) Smolensky, P.; Rosen, E.; and Goldrick, M.  2020\.  Learning a gradient grammar of French liaison.  In Annual Meeting on Phonology, volume 8.
  * Smolensky (1988) Smolensky, P.  1988\.  On the proper treatment of connectionism.  Behavioral and Brain Sciences 11(1):1–23.
  * Smolensky (1990) Smolensky, P.  1990\.  Tensor product variable binding and the representation of symbolic structures in connectionist systems.  Artificial Intelligence 46(1-2):159–216.
  * Smolensky (2012) Smolensky, P.  2012\.  Symbolic functions from neural computation.  Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences 370(1971):3543–3569.
  * Soulos et al. (2020) Soulos, P.; McCoy, R. T.; Linzen, T.; and Smolensky, P.  2020\.  Discovering the compositional structure of vector representations with role learning networks.  In Third BlackboxNLP Workshop on Analyzing and Interpreting Neural Networks for NLP, 238–254.
  * Szabó (2012) Szabó, Z.  2012\.  The case for compositionality.  In Hinzen, W.; Machery, E.; and Werning, M., eds., The Oxford Handbook of Compositionality. Oxford University Press.  64–80.
  * Thomas (2020) Thomas, R.  2020\.  How AI is driving the new industrial revolution.  Forbes.
  * Turek (2016) Turek, M.  2016\.  Explainable Artificial Intelligence (XAI).  DARPA website.  www.darpa.mil/program/explainable-artificial-intelligence.
  * 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 et al. (2020) Wang, B.; Shin, R.; Liu, X.; Polozov, O.; and Richardson, M.  2020\.  RAT-SQL: Relation-aware schema encoding and linking for text-to-SQL parsers.  In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, 7567–7578.  Online: Association for Computational Linguistics.
  * 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.
  * Zimmermann (2019) Zimmermann, E.  2019\.  Gradient symbolic representations and the typology of ghost segments.  In Annual Meeting on Phonology, volume 7.

## Acknowledgments

We gratefully acknowledge, for support and valuable conversations, Johannes
Gehrke, Li Deng, Qi Lu, Yi-Min Wang, Harry Shum, Eric Horvitz, Susan Dumais,
Xiaodong He, Aslı Çelikyılmaz, Chris Meek, Hamid Palangi, Qiuyuan Huang,
Nebojsa Jojic, Imanol Schlag, Kezhen Chen, Shuai Tang, Laurel Brehm, Najoung
Kim, Matthias Lalisse, Paul Soulos, Eric Rosen, Caitlin Smith, Coleman Haley,
Géraldine Legendre, Jason Eisner, Ben Van Durme, Alan Yuille, Hynek Hermansky,
Tal Linzen, Robert Frank, Jürgen Schmidhuber, Ken Forbus, Gary Marcus, Yoshua
Bengio, Steven Pinker, Jay McClelland, Alan Prince, Ewan Dunbar, Dapeng Wu,
Randy O’Reilly, François Charton, Guillaume Lample, Peter beim Graben, Daniel
Crevier, and all our collaborators on the papers reviewed here. The work
reported here was supported in part by NSF (GRFP 1746891, BCS-1344269,
DGE-0549379) and by Microsoft Research. Any opinions, findings, and
conclusions or recommendations expressed in this material are those of the
authors and do not necessarily reflect the views of the National Science
Foundation or Microsoft.