Logic and the 2-Simplicial Transformer
Authors: James Clift
Dmitry Doryn
Daniel Murfet
James Wallbridge
Venue:  (2020)
Keywords: transformer
logic
reinforcement learning
reasoning

Abstract: We introduce the 2-simplicial Transformer, an extension of the Transformer which includes a form of higher-dimensional attention generalising the dot-product attention, and uses this attention to update entity representations with tensor products of value vectors. We show that this architecture is a useful inductive bias for logical reasoning in the context of deep reinforcement learning.


Published as a conference paper at ICLR 2020
LOGIC AND THE 2-SIMPLICIAL TRANSFORMER
James Clift
Dmitry Doryn
Daniel Murfet
James Wallbridge
[[jaesedwardeliff: dmitry. doryn, james wallbridge com Department of Mathematics, University of Melbourne, d. m.rffft @untrfet@uniieelp edu au
ABSTRACT
We introduce the 2-simplicial Transformer, an extension of the Transformer which includes form of higher-dimensional attention generalising the dot-product at- tention, and uses this attention to update entity representations with tensor prod- ucts of value vectors. We show that this architecture a useful inductive bias for logical reasoning in the context of deep reinforcement learning.
INTRODUCTION
Deep learning contains many differentiable algorithms for computing with learned representations. These representations form vector spaces, sometimes equipped with additional structure. recent example is the Transformer (Vaswani et al. (017) in which there is a vector space V of value vectors and an inner product space of query and key vectors. This structure supports a kind of message- passing, where value vector 1 V derived from entity j is propagated to update entity with weight q; kj, where q; E H a query vector derived from entity i, ky E H a key vector derived from entity J. and the inner product on H is written as dot product.
The Transformer therefore represents a relational inductive bias, where a relation from entity j to entity is perceived the extent that qi ky large and positive. However, the real world has structure beyond entities and their direct relationships: for example, the three blocks in Figure [ are arranged in such a way that if either of the supporting blocks removed, the top block will fall. This is a simple 3-way relationship between entities i, & that is complex to represent as a system of 2-way relationships. is natural to make the hypothesis that such higher-order relationships are essential to extracting the full predictive power of data, across many domains.
h
J
Figure 1: 3-way relationship between blocks.
In accordance with this hypothesis, introduce a generalisation of the Transformer architecture, the 2-simplicial Transformer, which incorporates both 2- and 3-way interactions. Mathematically. the key observation is that higher-order interactions between entities can be understood using al- gebras. This is nothing but Boole's 's insight (Boole 1847) which set in motion the development of modern logic. In our situation, an appropriate algebra the Clifford algebra (H) of the space H of queries and keys, which contains that space H C CI(H) and in which queries and keys can be multiplied.
To represent 3-way interaction we map each entity i to triple (p;, (2, 12) of vectors in H consisting of query vector Pi, a (first) key vector 1 and a (second) key vector i4. Given a triple i, & we first form the product p,l) 2 in the Clifford algebra, and then extract scalar quantity npp.d) using natural continuous function 17 CI(H)) - I associated to the Z-grading of CI(H). This scalar
"I Listing order alphabetical. Correspondence mur fet @un me me... edu.

---

Published as a conference paper at ICLR 2020
measures how strongly the network perceives 3-way interaction involving j, k. In summary, the 2-simplicial Transformer learns how to represent entities in its environment as vectors v E V. and how to transform those entities to queries and (pairs of) keys in H, so that the signals provided by the scalars qi ki and r(pdd,1)) are informative about higher-order structure in the environment.
As a toy example of higher-order structure, we consider the reinforcement learning problem in variant of the Box World environment from (Zambaldi et al. (019). The original Box World is played on a rectangular grid populated by keys and locked boxes of varying colours, with the goal being to open the box containing the "Gem". In our variant of the Box World environment, bridge Box World, the agent must use two keys simultaneously to obtain the Gem; this structure in the environment creates many 3- w-w relationships between entities, including for example the relationship between the locked boxes j. k providing the two keys and the Gem entity i. This structure the environment is fundamentally logical in nature, and encodes a particular kind of conjunction; see Appendix !I
The architecture of our deep reinforcement learning agent largely follows (Zambaldi et al.) 2019) and the details are given in Section 4 The key difference between our simplicial agent and the relational agent of (Zambaldi et al. 2019) is that in place of a standard Transformer block we use 2-simplicial Transformer block. Our experiments show that the simplicial agent confers an advantage over the relational agent as an inductive bias in our reasoning task. Motivation from neuroscience for simplicial inductive bias for abstract reasoning is contained in Appendix
Our use of tensor products of value vectors is inspired by the semantics of linear logic in vector spaces (Girard [987, Melliss] 2009] Clift & Murfet 2017] Wallbridge| 2018) in which algorithm with multiple inputs computes on the tensor product of those inputs, but this is an old idea in natural
language processing, used in models including the second-order RNN (Giles al.] 1989; Pollack
1991 Goudreau et al. 1994; Giles et al. 1991). multiplicative RNN (Sutskever et al. [001] 1 Insoy
& Cardie (015)). Neural Tensor Network (Socher et al.] 2013) and the factored 3-way Restricted Boltzmann Machine (Ranzato et al. 2010)), see Appendix A Tensors have been used to model pred-
icates in a number of neural network architectures aimed at logical reasoning (Serafini & Garcez, 2016 Dong et al. (019). The main novelty in our model lies in the introduction of the 2-simplicial attention, which allows these ideas to be incorporated into the Transformer architecture.
2-SIMPLICIAL TRANSFORMER
In this section we first review the definition of the ordinary Transformer block and then explain the 2- simplicial Transformer block. We distinguish between the Transformer architecture which contains a word embedding layer, an encoder and a decoder (Vaswani et al.] 2017), and the Trunsformer block which is the sub-model of the encoder that is repeated. The fundamental idea, of propagating information between nodes using weights that depend on the dot product of vectors associated to those nodes, comes ultimately from statistical mechanies via the Hopfield network (Appendix) B).
The ordinary and 2-simplicial Transformer blocks define operators on sequences c1, CN of entity representations. Strietly speaking the entities are indices 1 S í S N but sometimes identify the entity with its representation 6; The space of entity representations is denoted V, while the space of query, key and value vectors is denoted H. We use only the vector space structure on V. but H = Rd is an inner product space with the usual dot product pairing (h, I() + h-h' h and in defining the 2-simplicial Transformer block we will use additional algebraic structure on H, including the "multiplication" tensor B- : H @ H - H of (TO) (used to propagate tensor products of value vectors) and the Clifford algebra of H (used to define the 2-simplicial attention).
In the first step of the standard Transformer block we generate from each entity e; a tuple of vectors via a learned linear transformation E V - H These vectors are referred to respectively as query, key and value vectors and we write
(gt, k m)) = F((e)-
(1)
Stated differently, qi = W e, A; = W es, 0 = WVe, e; for weight matrices Wº, WK WV, In the second step we compute a refined value vector for each entity
o =
ca.kk 0j
Σ
softmax(g: -k....,q.
q: (uckN))pe kN),uj.
(2)
e=1
2

---

Published as a conference paper at ICLR 2020
Finally, the new entity representation ej is computed by the application of feedforward network ge. layer normalisation and a skip connection
LayerNorm (go(x)) + +e).
Remark 2.1. In the introduction referred the idea that Transformer model learns represen- tations of relations. To be more precise, these representation are heads, each of which determines an independent set of transformations W W W which extract queries, keys and values from entities. Thus head determines not only which entities are related (via W W*) but also what information transmit between them (via W In multiple-hest
attention with K heads, there are K channels along which to propagate information between every pair of entities, each of dimension dim( (H) K. More precisely, we choose decomposition H H1 @ ... @ H so that
F:V.
H
33
and write
(16, (o,(1))),,1))) -.((1):---- (,,(K)) (K)( E(ee).
To compute the output of the attention, we take a direct sum of the value vectors propagated along every one of these K channels, in the formula
NV
e: = LayerNorm 90
softmax((1.(w) k1,0)) -..... (..00) RN (x,w)) + +ei) ==
Σ
(4)
In combinatorial topology the canonical one-dimensional object is the 1-simplex (or edge) j - Since the standard Transformer model learns representations of relations, we refer to this form of attention as 1-simplicial atlention. The canonical two-dimensional object is the 2-simplex (or triangle) which we may represent diagrammatically in terms of indices i,
(5)
In the 2-simplicial Transformer block, in addition to the 1-simplicial contribution, each entity e, is updated as a function of pairs of entities Ej, e using the tensor product of value vectors uj & uk and a probability distribution derived from a scalar triple product (pr, 1..)).12 (2) in place of the scalar product 4s ky. This means that we associate to each entity e, a four-tuple of vectors via a learned H denoted
linear transformation E
(pr, 1. 1,, u.) = E(e;).
(6)
the value. Stated differently, Pi W e; I = W/1 e;, - WLze; and u; = W e, for weight matrices WP, Wh, WL, WU. Definition 2.2. The unsigned scalar triple producr of a, c E H
We still refer to pi as the query, 1 as the keys and
(a, c) = (a b)c - (a c)b + (b. (b-c)all
(7)
whose square is polynomial in the pairwise dot products (a, b, c)2 (a () c) (b (a a) + (a c) b) 2(a b)(a - c).
(8)
This scalar triple product has a simple geometric interpretation in terms of the volume the tetra- hedron with vertices O, a, b, To explain, recall that the triangle spanned by two unit vectors a. in R has an area A which can be written in terms of the dot product a and b. In three dimensions, the analogous formula involves the volume V of the tetrahedron with vertices given by unit vectors a, b, and the scalar triple product as shown in Figure 2
In general, given nonzero vectors a, b, let à, b, è denote unit vectors in the same directions. Then can by Lemma C.10 v) factor out the length in the scalar triple product
(a, b, [|]]|||||]]|]] 6,
(9)
3

---

Published as a conference paper at ICLR 2020
(a b)2 4,22
ba,b,c) = 36V
Figure 2: The geometry of 1- and 2-simplicial attention. Left: the dot product in terms of the area A in RR Right: the triple product in terms of the volume V in R
so that a general scalar triple product can be understood in terms of the vector norms and config- urations of three points on the 2-sphere. One standard approach to calculating volumes of such letrahedrons is the cross product which is only defined in three dimensions. Since the space of rep- resentations is high dimensional the natural framework for the triple scalar product (a. b, c) is instead the Clifford algebra of H (see Appendix C
For present purposes, we need know that (a, b, c) attains its minimum value (which is zero) when b, C are pairwise orthogonal, and attains its maximum value (which is ||a|] [6]l|]|] if and only {a, b, ef is linearly dependent (Lemma C.10p. Using the number (pr, 1), (2) as measure of the degree which entity is attending to (J.k), or put differently, the degree which the network predicts the existence of 2-simplex (i,j.k) k), the update rule for the entities when using purely 2-simplicial attention is
Blu @ un)
(10)
Ea.t (
JAK=1
where B: H H H is a learned linear transformation. Although we do not impose any further constraints, the motivation here is to equip H with the structure of an algebra; in this respect model conjunction by multiplication, an idea going back to Boole (Boole 1847).
We compute multiple-head 2-simplicial attention in the same way in the 1-simplicial case. To combine I-simplicial heads (that is, ordinary Transformer heads) and 2-simplicial heads we use separate inner product spaces 112 1/2 for each simplicial dimension, so that there are learned linear transformations E - (H ) m8 E V - (H²) and the queries, keys and values are extracted from an entity e; according to
kg v1) = (e(),,
(pr, 12, u.) = (²()))
The update rule (for a single head in each simplicial dimension) then:
e kg
Blu @ u))
N 1 cack. 13}
+ LayerNorm
(11)
J.kml Ea, cland
N
LayerNorm (go(e() + +e))
(12)
If there are K1 heads of 1-simplicial attention and K2 heads of 2-simplicial attention, then +
modified in the obvious way using
u=1 H. and H² 0 H H²-
Remark 2.3. Without the additional layer normalisation on the output of the 2-simplicial attention we find that training is unstable. The natural explanation is that these outputs are constructed from polynomials of higher degree than the 1-simplicial attention, and thus computational paths that go through the 2-simplicial attention will be more vulnerable to exploding or vanishing gradients.
The time complexity of 1-simplicial attention as a function of the number of entities is O(N2) while the time complexity of 2-simplicial attention is O(N3) since we have to calculate the attention for every triple j, k) of entities. For this reason we consider only triples (i. k) where the base of the 2-simplex (j, k) is taken from set of pairs predicted by the ordinary attention, which we view as
4

---

Published as a conference paper at ICLR 2020
the primary locus of computation. More precisely, we introduce in addition to the N entities (now referred to as standard entities) a set of M virtual entities eN+1..... CN+M. These virtual entities serve a "scratch pad" onto which the iterated ordinary attention can write representations, and we restrict j, & to lie in the range N < j, S N + M so that only value vectors obtained from virtual entities propagated by the 2-simplicial attention.
With virtual entities the update rule is for 1 SiSN
chik
N+M Σ
cack, U/
+ LayerNorm
28t=1 (iid).1 Blu, @ us)
(13)
N+
and for N <iSN +M
N+M Σ
gack,
N+M eack, 1/3
) LayerNorm(u.).
(14)
The updated representation E/ is computed from 1/, e using 112 as before. Observe that the virtual entities are not used to update the standard entities during 1-simplicial attention and the 2-simplicial
attention is not used to update the virtual entities; instead the second summand in (14) involves the vector u, W e4, which adds recurrence to the update of the virtual entities. After the attention phase the virtual entities are discarded.
The method for updating the virtual entities is similar to the role of the memory nodes in the rela- tional recurrent architecture of (Santoro et al. 2018), the master node in (Gilmer et al., 2017 85.2) and memory slots in the Neural Turing Machine (Graves et al. (014). The update rule has complex- ity M22 and if we take M be of order vN we get the desired complexity O(N2).
RL ENVIRONMENT
The environment in our reinforcement learning problem is a variant of the Box environment from (Zambaldi et al., 2019). The standard BoxWorld environment is rectangular grid in which are situated the player (a dark gray tile) and a number of locked boxes represented by a pair of horizontally adjacent tiles with a tile of colour x, the key colour, y. the lock colour, on the right. There is also one loose key in each episode, which is a coloured tile not initially adjacent to any other coloured tile. All other tiles are blank (light gray) and are traversable by the player. The rightmost column of the screen is the inventory, which fills from the top and contains keys that have been collected by the player. The player can pick up any loose key by walking over it. In order to open a locked box, with key and lock colours F, y, the player must step on the lock while in possession of copy of y, in which case one copy of this key is removed from the inventory and replaced by a key of colour x.
the left and tile of colour
The goal is to attain white key, referred in the sample episode of Figure 3 In this episode, there is a loose pink key (marked 1) which can be used open one of two locked boxes, obtaining in this way either key 5 or key 20 The correct choice is 2, since this leads via the sequence of keys 3, 4 to the Gem
as the Gem (represented by a white square) as shown
Some locked boxes, if opened. provide keys that are not useful for attaining the Gem. Since each key may only be used once, opening such boxes means the episode is rendered unsolvable. Such boxes are called distractors. An episode ends when the player either obtains the Gem (with a reward of 110) or opens a distractor box (reward -1). Opening any non-distractor box, or picking up loose key, garners a reward of +1. The solution length is the number of locked boxes (including the one with the Gem) in the episode on the path from the loose key to the Gem.
Our variant of the Box World environment, bridge BoxWorld, is shown in Figure In each episode two keys are now required to obtain the Gem, and there are therefore two loose keys on the board. To obtain the Gem, the player must step on either of the lock tiles with both keys in the inventory, which point the episode ends with the usual +10 reward. Graphically, Gems with multiple locks are denoted with two vertical white tiles on the left, and the two lock tiles on the right. Two solution
'The agent sees only the colours of tiles, not the numbers which are added here for exposition.
5

---

Published as a conference paper at ICLR 2020
Figure 3: Right: sample episode of the BoxWorld environment. The rightmost column is the player inventory, currently empty. Left: graph representation of the puzzle, with key colours as vertices and an arrow C D key C' can be used to obtain key D.
paths (of the same length) leading each the locks on the Gem are generated with no overlapping colours, beginning with two loose keys. In episodes with multiple locks we do not consider distractor boxes of the old kind; instead there a new type of distractor that we call bridge. This is locked box whose lock colour is taken from one solution branch and whose key colour is taken from the other branch. Opening the bridge renders the puzzle unsolvable. An episode ends when the player either obtains the Gem (reward +00) opens the bridge (reward 1). Opening box other than the bridge, or picking up a loose key, has a reward of +1 as before. In this paper we consider episodes with zero one bridge (the player cannot fail to solve episode with no bridge).
tekdge
Figure 4: Right: a sample episode of the bridge World environment, in which the Gem has two locks and there is a marked bridge. Left: graph representation of the puzzle, with upper and lower solutions paths and the bridge between them. There is a source involving the orange key and sink involving the purple lock.
Standard Box World is straightforward for agent to solve using relational reasoning, because leaves on the solution graph can be identified (their key colour appears only once on the board) and by propagating this information backwards along the arrows the solution graph, agent can identify distractors. Bridge Box World emphasises reasoning about 3-way relationships (or 2- simplices). The following 2-simplex motifs
8
(a) Source
(b) Sink
appear in all solution graphs where a pair of boxes (ax, 3) is a source they have the same lock colour but distinct key colours, and sink if they have the same key colour but distinct lock colours (the 2-simplex leading to the Gem being an example). If a, 3 a source or sink then either a is the bridge 3 is the bridge. If the agent can observe both source and a sink then it can locate the bridge. is less clear how to identify bridges using iterated relational reasoning, because every path in the solution graph eventually reaches the Gem.

---

Published as a conference paper at ICLR 2020
4 RL AGENT ARCHITECTURE
Our baseline relational agent is modeled closely on (Zambaldi et al. 2019) except that we found that a different arrangement of layer normalisations worked better in our experiments. see Remark 4.1 The code for our implementation of both agents is available online (Clift et al. 2019). In the Tollowing we describe the network architecture of both the relational and simplicial agent; we will note the differences between the two models as they arise.
The input to the agent's network is an RGB image, represented as a tensor of shape [R, C 1.3] (i.e. an element of R @ RC+1 @ IR') where R is the number of rows and C' the number of columns (the C + due to the inventory). This tensor is divided by 255 and then passed through 2 x convolutional layer with 12 features, and then 2 x 2 convolutional layer with 24 features. Both activation functions are ReLU and the padding on our convolutional layers is "valid" so that the output has shape [R 2, C 1, 24J. We then multiply by weight matrix of shape 24 x 62 to obtain a tensor of shape [R 2, C - 1, 126. Each feature vector has concatenated to it a two- dimensional positional encoding, and then the result is reshaped into tensor of shape [N, 64] where N = (R (C - is the number of Transformer entities. This is the list (e1, (e1,...,eN) ex) of entity representations e, V R61
In the case of the simplicial agent, a further two learned embedding vectors cN+1. CN+2 are added to this list; these are the virtual entities. So with M 0 in the case of the relational agent and M for the simplicial agent, the entity representations form a tensor of shape [N + M, 64]. This tensor is then passed through two iterations of the Transformer block (either purely 1-simplicial in the case of the relational agent, or including both 1 and 2 2-simplicial attention in the case of the simplicial agent). In the case of the simplicial agent the virtual entities are then discarded, so that in both cases we have a sequence of entities ef, ........ ..N-- Inside each block are two feedforward layers separated by a ReL.U activation with 64 hidden nodes; the weights are shared between iterations of the Transformer block. In the 2-simplicial Transformer block the input tensor, after layer normalisation, is passed through the 2-simplicial attention and the result (after an additional layer normalisation) is concatenated to the output of the 1-simplicial attention heads before being passed through the feedforward layers. The code for the ordinary and 2-simplicial Transformer blocks are:
def tran www.ffomrrrbbbb (e):
def att.iiiiaal.aaasffmrmm......eee. (e):
x = LayerNorm (e)
x = LayerNorm
a = SSmpliciaa al A Attention (x)
al = 1 SSimlicial (x)
b DenseLayer1 (a)
a2 2SimplicialAAttention (x)
DenseLayer2 (b)
a2n LayerNorm (a2)
= Add
ac Concatenate ([a],a2n]] a2n
eprime LayerNorm(n return eprime
b = Denselayerl (ac)
c Densel.ayer2(b)
r Add
eprime LayerNorm (r)
return eprime
Our implementation of the standard Transformer block is based on an implementation in Keras from (Mavreshko) 22019) In both the relational and simplicial agent, the space V of entity representations has dimension 64 and we denote by H H² the spaces of 1-simplicial and 2-simplicial queries, keys and values. In both the relational and simplicial agent there are two heads of 1-simplicial attention, H' = H e H² with dim (H,)) 32. In the simplicial agent there is single head of 2-simplicial attention with dim ( = 48 and two virtual entities.
The output of the Transformer blocks is tensor of shape [N. 64]. To this final entity tensor apply max- moo-ppooling over the entity dimension, that is, we compute a vector v E RR44 by the rule 64. This vector is then passed through four fully-connected layers with 256 hidden nodes and ReLU activations. The output of the final fully-connecte layer is multiplied by one 256 x weight matrix produce logits for the actions (left, up, right and down) and another 256 x 1 weight matrix to produce the value function.
02 maxi<js (e"); for 1
Remark 4.1. There is wide variation in the layer normalisation in Transformer models, compare Vaswani al. 2017 Child al.) 2019; Zambaldi et al.) 2019). In (Zambaldi et al.) 2019) layer normalisation occurs in two places: on the concatenation of the Q, K, matrices, and on the output of the feedforward network go- We keep this second normalisation but move the first from after the
7

---

Published as a conference paper at ICLR 2020
linear transformation E of ( to before this linear transformation, that it is applied directly to the incoming entity representations. This ordering gave the best performant relational model in our experiments, with our results diverging even further if direct comparison to the (Zambaldi et al. 2019) architecture was used.
EXPERIMENTS AND RESULTS
The training of our agents uses the implementation in Ray RLlib (Liang et al. 2018 of the dis- tributed off-policy actor-critic architecture IMPALA of (Espeholt et al. 2018) with optimisation algorithm RMSProp. The hyperparameters for IMPALA and RMSProp pendix [ Following (Zambaldi et al., 2019) and other recent work in deep reinforcement learning. use RMSPrrp with large value of the hyperparameter this is effectively RMSProp with smoothed gradient clipping.
given in To Ap-
0.1. As we explain Appendix
First we verified that our implementation of the relational agent solves the Box World environment Zambaldi et al. 2019) with solution length sampled from [1, and number of distractors sampled from [0, 4| on 9 grid. After training for 2.35 x 109 timesteps our implementation solved over 93% of puzzles (regarding the discrepancy with the reported sample complexity in (Zambaldi et al., 2019) see Appendix D). Next we trained the relational and simplicial agent on bridge Box World, under the following conditions: half of the episodes contain bridge, the solution length is uniformly sampled from [1, 3] (both solution paths are of the same length), colours are uniformly sampled from set of 20 colours and the boxes and loose keys arranged randomly
7 grid, under the constraint that the box containing the Gem does not occur in the rightmost column or bottom row, and keys appear only in positions (y, (2r, 3e-11 1) for 1 < S 3, < c < 3. The starting and ending point of the bridge are uniformly sampled with no restrictions (e.g. the bridge can involve
the colours of the loose keys and locks on the Gem) but the lock colour is always on the top solution path. There is no curriculum and no cap on timesteps per episode.
We trained four independent trials of both agents either 5.5 10 timesteps or convergence, whichever came first. In Figure 0 we give the mean and standard deviation of these four trials, showing clear advantage of the simplicial agent. We make some remarks about performance comparisons taking into account the fact that the relational agent is simpler (and hence faster to execute) than the simplicial agent Appendix D The training runs for the relational and simplicial agents are shown in Figure 9 and Figure TO of Appendix F together with analysis and visualization of the 1- and 2 2-simplicial attention in specific examples.
Relational versus agent
1.00
simplicial relacional
simplictal relational
fraction
0.85
0.80
Environment steps
Figure 6: Training curve of mean relational and simplicial agents on bridge Box Shown are the mean and standard deviation of four runs of each agent, including the best run of each.
In the reported experiments we use only two Transformer blocks; we performed two trials a relational agent using four Transformer blocks, but after 5.5 x 10 timesteps neither trial exceeded
8

---

Published as a conference paper at ICLR 2020
the 0.85 plateau in terms of fraction solved. Our overall results therefore suggest that the 2-simplicial Transformer is more powerful than the standard Transformer, with its performance not matched by adding greater depth. This is further supported by the fact on time-adjusted basis, the 2-simplicial model still converges faster than the ordinary model; see Figure of Appendix D
6 ANALYSIS
We analyse the simplicial agent to establish that it has learned to use the 2-simplicial attention, and to provide some intuition for why 2-simplices are useful; additional details are in Appendix The analysis is complicated by the fact that our 2 x 2 convolutional layers (of which there are two) are not padded, so the number entities processed by the Transformer blocks (R-2)(C) 1) where the original game board is R x C' and there is extra column for the inventory (here R is the number of rows). This means there is not a one-to-one correspondence between game board tiles and entities; for example, all the experiments reported in Figure 6 are 7 9 board, so that there are N = 40 Transformer entities which can be arranged on 5 x 8 grid (information about this grid passed to the Transformer blocks via the positional encoding). Nonetheless
found that for trained agents there is strong relation between a tile in position (y, x) and the Transformer entity with index x (C 1) 1) for (v, x) E [1, 2] [1, C 1] [0, R 1] [0, CJ. This correspondence is presumed in the following analysis, and in our visualisations.
Displayed in Figure are attention distributions for simplicial agent of Figure The four images in the top right show the ordinary attention of the virtual entities in the first iteration of the simplicial Transformer block: in the first head, the first virtual entity attends strongly to a particular lock, while the second head of the second virtual entity attends strongly to the corresponding key. Shown at the bottom of Figure 7 is the 2-simplicial attention the second iteration of the simplicial Transformer block. The columns are query entities and rows are key entity pairs (j, k) in lexicographic order (1, 1), (1, 2), (2, 1), (2, 2). Entity 17 is the top lock on the Gem, 25 is the bottom lock on the Gem, 39 is the player. We may therefore infer, from our earlier description of the ordinary attention of the virtual entities, that the agent "perceives" the 2-simplex with query entity 25 as shown. In general observe that the top and bottom locks on the Gem, the player, and the entities 7, 15 associated to the inventory often have a non-generic 2-simplicial attention, which strongly suggests that the 2-simplices in meaningful way.
simplicial agent has learned
Input
First head, vel context
First head. context
Second head, vel in context
Second head, ve2 context
4
2 2-simplicial attention in second block
20
30
Figure 7: Visualization of 2-simplicial attention in step 18 of an episode.
7 DISCUSSION
On general grounds one might expect that in the limit of infinite experience, any reinforcement learning agent with sufficiently deep neural network will be able to solve any environment, in-

---

Published as a conference paper at ICLR 2020
cluding those like bridge Box Borld that involve higher-order relations between entities. In practice, however, we do not care about the infinite computation limit. In the regime of bounded computation it is reasonable to introduce biases towards learning representations of structures that found in wide range of environments that we consider important.
We argue that higher-order relations between entities and that the 2-simplicial Transformer natural inductive bias for 3-way interactions between entities. We have given preliminary evidence for the utility of this bias by showing that in the bridge Box World environment the simplicial agent has better performance than a purely relational agent, and that this performance involves in meaningful way the prediction of 3-way interactions (or 2-simplices). We believe that simplicial Transformers may be useful for any problem in which higher-order relations between entities are important.
important example of such structures,
The long history of interactions between logic and algebra is natural source of inspiration for the design of inductive biases in deep learning. this paper we have exhibited one example: Boole's idea, that relationships between entities can be modeled by multiplication in algebra, may be realised the context of deep learning as an augmentation to the Transformer architecture using Clifford algebras of spaces of representations.
10

---

Published as a conference paper at ICLR 2020
ACKNOWLEDGMENTS
We acknowledge support from the Nectar cloud at the University of Melbourne and GCP research credits. DM thanks Paul Middlebrooks for his excellent podcast "Brain Inspired", where he first learned about cognitive maps.
REFERENCES
Guillaume Alain and Yoshua Bengio. Understanding intermediate layers using linear classifier probes. In Proceedings of the International Conference on Learning Representations, 2016.
Aristotle. Sophistical refutations. In J. Barnes (ed.), Complete works of Aristorle, Volume I: The revised Oxford translation. Princeton University Press, 1984.
David T. Barrett, Felix Hill, Adam Santoro, Ari Morcos, and Timothy Lillicrap. Measuring abstract reasoning in neural networks. In Proceedings of the 35th International Conference on Machine Learning, pp. 4477-4486, 2018.
Timothy E.J. Behrens, Timothy H. Muller, James C.R. Whittington, Shirley Mark, Alon B. Baram, Kimberly L. Stachenfeld, and Zeb Kurth-Nelson. What is cognitive map? Organizing knowl- edge for flexible behavior. Neuron, 100(2):490 509, 2018.
Jacob Bellmund, Peter Gärdenfors, Edvard Moser, and Christian F. Doeller. Navigating cognition: Spatial codes for human thinking. Science, 362, 11 2018.
George Boole. The mathematical analysis of logic: being an essay towards calculus of deductive reasoning. Macmillan, Barclay & Macmillan, Cambridge, 1847.
Rewon Child, Scott Gray, Alec Radford, and llya Sutskever. Generating long sequences with sparse transformers. preprint arXiv:I904. 10509, 2019.
James Clift and Daniel Murfet. 171.:120, 2017.
Cofree coalgebras and differential linear logic. preprint
James Clift, Dmitry Doryn, Daniel Murfet, and James Wallbridge. 2simplicialraassfommer https: cemiiipiiiiee httis/mmmmmiimiaaaraaaaaaaaaaaaa former/ 2019.
Alexandra O. Constantinescu, Jill X. O'Reilly, and Timothy E.J. Behrens. Organising conceptual
knowledge in humans with a gridlike code. Science, 352:1464-1466 2016.
Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Lukasz Kaiser. Universal transformers. In Proceedings of the International Conference on Learning Representations, 2019.
Honghua Dong, Jiayuan Mao, Tian Lin, Chong Wang, Lihong Li, and Denny Zhou. Neural logic machines. In Proceedings of the International Conference on Learning Representations, 2019.
Russell A. Epstein, Eva Zita Patai, Joshua B. Julian, and Hugo Spiers. The cognitive map in humans: spatial navigation and beyond. Nature Neuroscience, 20: 1004-5155,,, 2017.
Lasse Espeholt, Hubert Soyer, Remi Munos, Karen Simonyan, Vlad Mnih, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, lain Dunning, Shane Legg, and Koray Kavukcuoglu. IMPALA: Scalable distributed deep-RL with importance weighted actor-learner architectures. In Proceed- ings of the 35th International Conference on Machine Learning, pp. 1407-1416, 2018.
Gottlob Frege On sense and denotation (über sinn und bedeutung). Zeitschrift für Philosophie und philosophische Kritik, 100:25-50,, 1892.
C. Lee Giles, Guo-Zheng Sun, Hsing- Chen, Yee-Chun Lee, and Dong Chen. Higher order recurrent networks and grammatical inference. In Advances in Neural Information Processing Systems 2, pp. 380-387. 1989.
C. Lee Giles, Dong Chen, Clifford B. Miller, Hsing-Hen Chen, Guo-Zheng Sun, and Yee-Chun Lee. Second-ord order International Joint Conference Newral Networks, volume 2, pp.pp.7. 273-281, 1991.
-oddrr recurrent neural networks for grammatical inference. In LJCNN-91-Seane

---

Published as a conference paper at ICLR 2020
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley. Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning. pp. 1263-1272, 2017.
Jean-Yves Girard. Linear logic. Theor. Comput. Sci., 50(1):1-102, 1987.
Ian Goodfellow, Yoshua Bengio, Aaron Courville, and Yoshua Bengio. Deep learning, volume 1. MIT Press, 2016.
Mark W. Goudreau, C. Lee Giles, Srimat T. Chakradhar, and Dong Chen. First-order versus second- order single-layer recurrent neural networks. IEEE Transactions Neural Networks, 5(3):511- 513, 1994.
Alex Graves, Greg Wayne, and Ivo Danihelka. Neural turing machines, preprint arXiv:1410.5401 2014.
Alex Graves, Greg Wayne, Malcolm Reynolds, Tim Harley, Ivo Danihelka, Agnieszka Grabska- Barwinska, Sergio Gómez, Edward Grefenstette, Tiago Ramalho, John Agapiou, Adrià Puig- domènech Badia, Karl Moritz Hermann, Yori Zwols, Georg Ostrovski, Adam Cain, Helen King, Christopher Summerfield, Phil Blunsom, Koray Kavukcuoglu, and Demis Hassabis. Hybrid com- puting using neural network with dynamic external memory. Nature, 538, 10 2016.
Peter Henderson, Riashat Islam, Philip Bachman, Joelle Pineau, Doina Precup, and David Meger. Deep reinforcement learning that matters. preprint arXiv: 170.006000,6600, 2017.
David Hestenes. New foundations for classical mechanics. Kluwer Academic Publishers, 2nd edition, 2002.
John Hewitt and Christopher D. Manning. A structural probe for finding syntax in word representa- tions. Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume (Long and Short Pa- pers), 2019.
John J. Hopfield. Neural networks and physical systems with emergent collective computational abilities. Proceedings of the National Academy of Sciences, 79(5):2554-2558 1982.
Martin Hyland. Game semantics, pp. 131-184. Publications of the Newton Institute. Cambridge University Press, 1997.
Ozan Irsoy and Claire Cardie. Modeling compositionality with multiplicatiie recurrent neural net- works. In Proceedings of the International Conference Learning Representations, 2015.
Max Jaderberg, Valentin Dalibard, Simon Osindero, Wojciech M. Czamecki, Jeff Donahue, Ali Razavi, Oriol Vinyals, Tim Green, lain Dunning, Karen Simonyan, Chrisantha Fernando, and Koray Kavukeuoglu. Population based training of neural networks. preprint 17X1v:1711.0984/ 2017.
Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In Proceedings of the 34th International Conference on Machine Learning, pp. 1885-1894, 2017.
Eric Liang, Richard Liaw, Robert Nishihara, Philipp Moritz, Roy Fox, Ken Goldberg, Joseph Gonza- lez, Michael I. Jordan, and lon Stoica. Rllib: Abstractions for distributed reinforcement learning. In Proceedings of the 35th International Conference on Machine Learning, pp. 3059-3068, 2018.
Yunzhe Liu, Raymond J. Dolan, Zeb Kurth-Nelson, and Timothy E.J. Behrens. Human replay spontaneously reorganizes experience. Cell, 178(3):640 - 652, 2019.
Alan Macdonald. Sobezyk's simplicial calculus does not have a proper foundation. preprint arXiv:1710.08274. 2017.
David J.C. MacKay. Information theory, inference and learning algorithms. Cambridge University Press, 2003.
Nicholas John Mackintosh. Animal learning. 2019. http::/ttt///tta. https:/www.bitammicc... com/
sci Bscience/anime - ght and reasoning
12

---

Published as a conference paper at ICLR 2020
Chris Martens. Programming interactive worlds with linear logic. PhD thesis, Carnegie Mellon University, 2015.
Kirill Mavreshko, keras-trans transtrrasformmr, htt.s//www...ttttt/////////////s 2019.
Paul-André Melliès. and Program Behaviour, Panoramas et Synthèses 27, Société Mathématique de France 1-196, 2009.
Categorical semantics of linear logic. In Interactive Models of Computation
Anh Mai Nguyen, Jason Yosinski, and Jeff Clune. Multifaceted feature visualization: uncovering the different types of features learned by each neuron in deep neural networks. In Proceedings of the 33rd International Conference on Machine Learning, 2016.
Jordan B. Pollack. The induction of dynamical recognizers. Machine Learning, 7(2):227-23) 1991.
Marc' Aurelio Ranzato, Alex Krizhevsky, and Geoffrey Hinton. Factored 3-way restricted Boltz- mann machines for modeling natural images. In Proceedings of the Thirteenth International Conference Artificial Intelligence and Statistics, volume 9, pp. 121-622188881 628, 2010.
David Raposo. Personal communication, May 13, 2019.
Adam Santoro, Ryan Faulkner, David Raposo, Jack Rae, Mike Chrzanowski. Théophane Weber, Daan Wierstra, Oriol Vinyals, Razvan Pascanu, and Timothy Lillicrap. Relational recurrent neural networks. In Proceedings of the 32nd International Conference Neural Information Processing Systems, pp. 7310-7321 2018.
Luciano Serafini and Artur S. Avila Garcez. Logic tensor networks: Deep learning and logi- cal reasoning from data and knowledge. In Proceedings of the 11th International Workshop Seurrl-SSmbolic Learning and Reasoning (NeSy' 16), 2016.
Avanti Shrikumar, Peyton Greenside, and Anshul Kundaje. Learning important features through propagating activation differences. In Proceedings of the 34th International Conference Ma- chine Learning, volume 70, pp. 3145-3153, 2017.
Karen Simonyan, Andrea Vedaldi, and Andrew Zisserman. Deep inside convolutional networks: Visualising image classification models and saliency maps. In Proceedings of the International Conference on Learning Representations, 2013.
Robin Smith. Aristotle's ' logic. Edward N. Zalta (ed.), The Stanford Encyclopedia of Philosophy. Metaphysics Research Lab, Stanford University, summer 2019 edition, 2019.
Garret Sobezyk. Simplicial calculus with geometric algebra. Fundamental Theories of Physics, vol. 47, 1992.
Richard Socher, Danqi Chen, Christopher D Manning, and Andrew Ng. Reasoning with neural tensor networks for knowledge base completion. In Advances in Neural Information Processing Systems 26, pp. 926-934.20 2013.
Paul Vincent Spade and Jaakko Hintikka. History of logic, 2019. britannica www.co//oooooo http://iittoooooooooooooo/////// attriit/rrrttootooooooooooooo
URL https: www.
stot le
Ilya Sutskever, James Martens, and Geoffrey Hinton. Generating text with recurrent neural networks.
In Proceedings of the 28th International Conference on Machine Learning, pp. 1017-1024, 201 1.
Richard S. Sutton and Andrew G. Barto. Reinforcement learning: An introduction. Adaptive Com- putation and Machine Learning series. MIT Press, 2018.
Christian Szegedy, Vincent Vanhoucke, Sergey loffe, Jonathon Shlens. and Zbigniew Wojna. Re- thinking the inception architecture for computer vision. In 2016 IEEE Conference on Computer Vision and Pattern Recognition, pp. 2818-2826, 2016.
Tijmen Tieleman and Geoffrey Hinton. Lecture 6.5 rmsprop: Divide the gradient by running average of its recent magnitude. [Coursera] Neural Networks for Machine Learning (University of Toronto), 2012.
13

---

Published as a conference paper at ICLR 2020
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Infor- mation Processing Systems 30, pp. 3998-6008 2017.
James Wallbridge. Jets and differential linear logic. preprint arXiv:1811.062355 2018.
James C. R. Whittington, Timothy H. Muller, Shirely Mark, Caswell Barry, and Tim E. J. Behrens. Generalisation of structural knowledge in the hippocampall-ntorhinn system. In Advances in Neural Information Processing Systems 31, pp. 8493-8504, 2018.
Vinicius Zambaldi, David Raposo, Adam Santoro, Victor Bapst, Yujia Li, Igor Babuschkin, Karl Tuyls, David Reichert, Timothy Lillicrap, Edward Lockhart, Murray Shanahan, Victoria Langston, Razvan Pascanu, Matthew Botvinick, Oriol Vinyals, and Peter Battaglia. Deep rein- forcement learning with relational inductive biases. In Proceedings of the International Confer- ence on Learning Representations, 2019.
APPENDIX
A COMPARISON TO THE NTM
The Transformer model and descendents such as the Universal Transformer (Dehghani et al. 2019) can be viewed as general units for computing with learned representations: in this sense they have similar conceptual role to the Neural Turing Machine (NTM) (Graves et al. 2014) and Differentiable Neural Computer (Graves et al. 2016). As pointed out in (Dehghani et al. 2019 (4) one can view the Transformer as block of parallel RNNs (one for each entity) which update their hidden states each time step by attending to the sequence of hidden states of the other RNNs the previous step. We expand on those remarks here in order to explain the connection between the 2-simplicial Transformer and earlier work in the NLP literature, which is written in terms of RNNs.
We consider a NTM with content-base based addressing only and no sharpening. The core of the NTM an RNN controller with update rule
h' = ReLU(M + Wh + Ux +
(15)
where W, U, b are weight matrices, æ is the current input symbol, is the previous hidden state, h is the next hidden state and M is the output of the memory read head
N
M Σ softmax [[gg, Mil..... K/,, (N]),
(16)
where there are N memory slots containing M MN q is query generated from the hidden state of the RNN by a weight matrix Zh, and K[u, e] = (u - (I [||wi]]. We omit the mechanism for writing to the memory here, since it is less obvious how that relates the Transformer; see (Graves et al. 2014 53.2). Note that while we can view M, as the "hidden state" of memory slot j. the controller's hidden state and the hidden states of the memory slots play asymmetric roles, since the former is updated with a feedforward network at each time step, while the latter is not.
The Transformer with shared transition functions between layers is analogous asymmetry removed: there is no longer separate recurrent controller, and every memory slot is updated with a feedforward network each timestep. To explain, view the entity representations el...., ex of the Transformer as the hidden states of N parallel RNNs. The new representation is
NTM with this
= (oyerNorm(gg(A) + es)
(17)
where the attention term is
Σ
softmax(g: kl....,
........0. ge kN)u,
(18)
and 9: = Ze; is a query vector obtained by a weight matrix from the hidden state, the ky = Ke are key vectors and fy Vez is the value vector. Note that in the Transformer the double role of M,
14

---

Published as a conference paper at ICLR 2020
in the NTM has been replaced by two separate vectors, the key and value, and the cosine similarity K| -] has been replaced by the dot product.
Having now made the connection between the Transformer and RNNs, we note that the second-order
RNN (Giles et al. 1989 Pollack] 1991, Goudreau et al. 1994 Giles et al. 1991) and the similar multiplicative RNN (Sutskever al., 2011 Irsoy & Cardie 2015) have in common that the update rule for the hidden state of the RNN involves a term V(r & h) which is a linear function of the tensor product of the current input symbol a and the current hidden state h. One way to think of this is that the weight matrix V maps inputs x to linear operators on the hidden state. In (Socher et al., 2013) the update rule contains a term V(e @ e2) where 61, e2 are entity vectors, and this directly analogous to our construction.
B CONNECTION TO HOPFIELD NETWORKS
The continuous Hopfield network (Hopfield 1982) (MacKay 2003 Ch.42) with N nodes updates in each timestep a sequence of vectors {e, LN by the rules
= tanh Σ (c+ c,)e
(19)
for some parameter The Transformer block may therefore be viewed as a refinement of the Hop- field network, in which the three occurrences of entity vectors in (19) replaced by query, key and value vectors W W ex, W ej respectively, the nonlinearity is replaced by a feedforward network with multiple layers, and the dynamics are stabilised by layer normalisation. The initial representations e; also incorporate information about the underlying lattice, via the positional em- beddings.
The idea that the structure of a sentence acts to transform the meaning of its parts is due to Frege (Frege) 1892] and underlies the denotational semantics logic. From this point of view the Trans- former architecture is an inheritor both of the logical tradition of denotational semantics, and of the statistical mechanics tradition via Hopfield networks.
C CLIFFORD ALGEBRA
The volume of an n-simplex in I2" with vertices O, 01,...,
, Un
1 m!
Vol,-
del(vi......
which is simplex. In our applications the space of representations H is high dimensional, but we wish to speak of the volume of k-simplices for k < dim ()) and use those volumes to define the coefficients of our simplicial attention. The theory of Clifford algebras (Hestenes) 2002 is one appropriate framework for such calculations.
of times the volume of the n-diiennsonnal parallelotope which shares n edges with the n-
Let H be an inner product space with pairing (v,w.) > associative unital R-algebra generated by the vectors e E H with relations
The Clifford algebra CI(H) is the
vw + we 2(v w)
CI(H) is injective, and since 2² ||||2 in CI(H), any nonzero vector v e H is a unit in the Clifford algebra. While as an algebra CI(H) only Zz- graded, there is nonetheless a Z-grading of the underlying vector space which be defined as follows: let {e be an orthonormal basis of H. then the set
The canonical k-linear map H
B = {es, C.me Kim
basis for CI(H), with m ranging over the set (O.....o If we assign the basis element ei ... ein.. the degree m, then this determines a Z-grading [-]x of the Clifford algebra which is easily checked to be independent of the choice of basis.
Definition C.1. [A]; denotes the homogeneous component of A CI(H) of degree k.
15

---

Published as a conference paper at ICLR 2020
Example C.2. Given a, b, H we have [ablo babl22 A and
[abe]] = (a b)e- - (a c)b + c)a, [abe]3 = a abbe.
(20)
There is an operation on elements of the Clifford algebra called reversion in geometric algebra
[Hestenes] 2002, p.45) which arises as follows: the opposite algebra CI(H) admits k-linear map
j CI(H) op with j(v) = e which satisfies j(v)j(w) + j(w)j(() = 2(v - w) 1, and so by
the universal property there is unique morphism of algebras
(-)+ CI(H)) - CI(H)
which restricts the identity on H. Note (u1 (11-... ... = ..... of for 01..... U/ H and (-)t is homogeneous of degree zero with respect to the Z-grading. Using this operation we can define the magnitude (Hestenes) 2002, p.46) of any element of the Clifford algebra.
Definition C.3. The magnitude of A E CI(H) is |A| = V[AiAoo
For vectors "i,..,, Uk E H,
01 1 (p% 01 2k3o |10 112 ... ||0
(21)
and in particular for E H we have ja| = |||||
Lemma C.4. Set n = dim(H). Then for E CI(H) we have
|A|2
[[]..1
0=
Proof. See (Hestenes) 2002 Chapter 2 (1.33)).
Example C.5. For a, b, E H the lemma gives
|a||21|///[|||1 = [[abe]]| 1 + [abc]al2 = (I(a bibe (a c)b bb + (b c)al? landa
and hence
[I(a b)c (a- c)b (b c)all² = 11al"10791ell==aaaaa0 la
Remark C.6. Given vectors vI..... 2/ H the wedge product 81 A ... A Up is an element in the exterior algebra A H. Using the chosen basis B we can identify the underlying vector space of CI(H) with A H and using this identification (set v; = E, Aose))
[0] m....ukk =
(
Aiji
Σ Nusn sk=1
=1=1
Σ
Aiji
Ausia lej, Ejel
Jinodk
Σ
Aijots Akiecal "Bean
1shennche oES
Σ Suisthhss
(-1)l0) A1iocn ...
ABSonr e..j
GESA
Ui
A Uk
where S₁ is the permutation group on & letters. That is. the top degree piece of v e in CI(H) is always the wedge product. is then easy to check that the squared magnitude of this wedge product is
[ ... exl
(Σ Alicco ... -.AAsin))
(22)
OESt
The term in the innermost bracket is the determinant of the k x & submatrix with columns (i......Je and the special case where = n (H) we see that the squared magnitude is just the square of the determinant of the matrix (iij)
16

---

Published as a conference paper at ICLR 2020
The wedge product of v-vectors in H can be thought of as oriented k-simplex, and the magnitude of this wedge product the Clifford algebra computes the volume.
Definition C.7. The volume of a k-simplex in H with vertices O, ,,,..., Up is
1 Voly = kd
[ ... vulal
(23)
Definition C.8. Given ,i,..., Uk E H the k-fold unsigned scalar product is
(01 (1....., Uk)
(24)
By Lemma C.4 and 21 we have
(Ul, vx)² = -| 1|0 ||va|12 - (k:1) Vol
(25)
which gives the desired generalisation of the equations in Figure 2
Example C.9. For k the unsigned scalar product is the absolute value of the dot product,
(a, b) = a b/. For = 3 we obtain the formulas Definition 2.2 from which it is easy to check that
ba,b,c) = |||||||||| ||||c|| cas lob + cos² Obe + cos? 0ac cos Oob cos Pac cos tbe
(26)
where Bac: Pab. Oue are the angles between a, b, c. The geometry of the three-dimensionae case is
more familiar: if dim H) = 3 then [[abe]a| is the absolute value of the determinant by (22), so that
Volg _ la (b x c)| is the usual formula for the volume of the 3-simplex. Recall that la (b c)
||a [|]]|||[ sin(0 (f cos(()) ( where ø the angle between a and the cross product x c. Hence, in
this case the scalar triple product
(a, b, e) = ( =|aa|||bi|dd|| 1-sinn (Onb) (Onb) cos (
(27)
With these formulas in mind the geometric content of the following lemma is clear: Lemma C.10. Let Ui...., Ug H. Then
(i) S (ei...., vn) S || ... ||
(ii) If the v; are all pairwise orthogonal then (Ui...., Up) = O.
(ii) The set (u....., is linearly dependent if and only if (v1,..., vn) ||u1 ... .....--llll
(iv) For any a E Sy we have (vi,..., = (Vo(1): (o(c))))
(v) For AI...., do E R, we have
(1 (EVR) Pall [eel(
Proof. (i) is obvious from 24 25
For (ii) note that
81
2k
Σ (-1)l (a(1) ... (o(k)
(28)
K!
oES,
and hence if the v, are pairwise orthogonal, and therefore anticommute in CI(H), we have in A -..
Wa 11 Uk- But the left hand side is homogeneous of degree ht so this means that [U) ... me]; wedge
for i < l and hence that (01 (m,.... Ug) O. The property (iii) is a standard property
products. Finally, (iv) is clear from 25 and (v) is clear since [AA] [A]| for any A E CI(H). Li
For more on simplicial methods in the context of geometric algebra see (Sobezyk 1992 Macdonald 2017).
17

---

Published as a conference paper at ICLR 2020
D TIME ADJUSTED PERFORMANCE
Experiments were conducted either on the Google Cloud Platform with single head node with 12 virtual CPUs and one NVIDIA Tesla P100 GPU and 192 additional virtual CPUs spread over two pre-emptible worker nodes, or on the University of Melbourne Nectar research cloud with a single head node with 12 virtual CPUs and two NVIDIA Tesla K80 GPUs, and 222 worker virtual CPUs.
The experiments in the original Box BoxWorld paper Zambaldi et al. 2019) contain an unreported cap on timesteps per episode (an episode horizon) of 120 timesteps (Raposo 2019). We have chosen to run our experiments without an episode horizon, and since this means our reported sample com- plexities diverge substantially from the original paper (some part of which it seems reasonable to attribute to the lack of horizon) it is necessary to justify this choice.
When designing an architecture for deep reinforcement learning the goal is reduce the expected generalisation error (Gooddellow et al., 2016] 88.1.1) with respect to some class of similar environ- ments. Although this class is typically difficult to specify and is often left implicit, in our case the class includes range of visual logic puzzles involving spatial navigation, which can be solved with- out memory A learning curriculum undermines this goal, by making our expectations of generali- sation conditional on the provision of a suitable curriculum, whose existence for a given member of the problem class may not be clear in advance. The episode horizon serves as a de facto curriculum, since early in training it biases the distribution of experience rollouts towards the initial problems that an agent has to solve (e.g. learning to pick up the loose key). In order to avoid compromising our ability to expect generalisation similar puzzles which do not admit such a useful curriculum, we have chosen not to employ an episode horizon. Fortunately, the relational agent performs well even without curriculum on the original Box World, as our results show.
In Figure 6 of Section 5 the horizontal axis was environment steps. However, since the simplicial agent has a more complex model, each environment step takes longer execute and the gradient de- scent steps are slower. In a typical experiment run on the GCP configuration, the training throughput of the relational agent is 1.9 x 10 environment frames per second (FPS) and that of the simplicial agent is 1.4 x 10 FPS. The relative performance gap decreases as the GPU memory and the number of IMPALA workers are increased, and this is consistent with the fact that the primary performance difference appears to be the time taken to compute the gradients (35ms vs 80ms). In Figure [ we give the time-adjusted performance of the simplicial agent (the graph for the relational agent is as before) where the r-axis of the graph of the simplicial agent is scaled by 1.9/1.4.
In principle there is no reason for a significant performance mismatch: the 2-simplicial attention can be in parallel to the ordinary attention (perhaps with iterations of the 1-simplicial attention per iteration of the 2-simplicial attention) so that with better engineering should be possible to reduce this gap.
E HYPERPARAMETERS
Hyperparameter
Value
IMPALA entropy
5 10-3
Discount factor y
0.99
Unroll length
timesteps
Ratch size
1280 rimesteps
Learning rate
2 x 10
RMSProp momentum
RMSProp e
0.1
RMSProp docay
0.99
Table 1: Hyperparameters for agent training.
"The bridge is the unique box both of whose colours appear three times on the board. However, this is not reliable strategy for detecting bridges for agent without memory, hecause once the agent has collected some of the keys on the board, some of the colours necessary make this deduction may longer be present.
18

---

Published as a conference paper at ICLR 2020
Adiational simpliciall
urpdoud -addsa Lesticliaeull
0.55
0.
0.75
Tims joted wyvicemett dhece
12
Figure 8: Training curve of mean relational and simplicial agents on bridge Box Borld,,, with time- adjusted r-axis for the simplicial agent.
F FURTHER ANALYSIS
Our experiments involve only a small number of virtual entities, and small number of iterations of the Transformer block: it is possible that for large numbers of virtual entities and iterations, our choices of layer normalisation are not optimal. Our aim was test the viability of the simplicial Transformer starting with the minimal configuration, so we have also not tested multiple heads of 2-simplicial attention. Deep reinforcement learning is notorious for poor reproducibility (Henderson) releasing our agent and
al. 2017). and in attempt to follow the emerging best practices environment code, trained agent weights, and training notebooks (Clift et al. 2019).
The training runs for the relational and simplicial agents are shown in Figure and Figure 10 spectively.
Tra Training turves mishoosi agents
Trudiintt vo2
0.5
0.00
Figure 9: Training curves for the relational agent on bridge Box World.
19

---

Published as a conference paper at ICLR 2020
simgliba
0.5
0.0
Trasten akr2
Envierment stge
Figure 10: Training curves for the simplicial agent bridge Box World.
F.1 ATTENTION
In this Appendix we provide further details relating to the analysis of the attention of the trained simplicial agent in Section 6 Across our four trained simplicial agents, the roles of the virtual entities and heads vary: the following comments are (simplicial agent A of Figure I0) but observe similar patterns in the other trials.
context of the best simplicial agent
F.1.1 1-SIMPLICIAL ATTENTION OF STANDARD ENTITIES
The standard entities are now indexed by 0 < S 39 and virtual entities by 40, 41. In the first iteration of the 2-simplicial Transformer block, the first I-simplicial head appears to propagate information about the inventory. At the beginning of an episode the attention of each standard entity distributed between entities 7, 15, 23, 31 (the entities the rightmost column), it concentrates sharply 7 (the entity closest the first inventory slot) after the acquisition of the first loose key, and sharply on 7, 15 after the acquisition of the second loose key. The second 1-simplicial head seems acquire the meaning described in Zambaldi al. 2019). where tiles of the same colour attend to one another. A typical example is shown in Figure The video of this episode is available
online (Clift al. 2019).
attention head two
Input board
10
25
10
Figure 11: Visualisation of 1-simplicial attention in first Transformer block, between standard en- tities in heads one and two. The vertical axes on the second and third images are the query index 0 < i 39, the horizontal axes the key index ( < j < 39.
20

---

Published as a conference paper at ICLR 2020
F.1.2 2-SIMPLICIAL ATTENTION
The standard entities are updated using 2-simplices in the first iteration of the 2-simplicial Trans- former block, but this is not interesting as initially the virtual entities are learned embedding vectors, containing information about the current episode. we restrict our analysis to the 2-simplicial attention in the second iteration of the Transformer block.
For the analysis, will be convenient organise episodes bridge Box World by their puzzle type, which is the tuple (a, b, c) where 1 I a S 3 is the solution length, 1 s b I a is the bridge source and a + 1 v c S 2a is the bridge target, with indices increasing with the distance from the gem. The episodes in Figures and have type (3, 2, 5).
Imput board
2-
Second head. context
Second head, vež context
2-simplicial attention second block
20
25
Figure 12: Visualisation of the 2-simplicial attention in the second Transformer block in step 13 of an episode of puzzle type (3, 5). Entity is the top lock the Gem, 15 associated with the inventory, 36 is the lock directly below the player. Shown is a 2-simplex with target 15.
board
First head, vel in context
First head, ve2 context
vel context
context
simplicial attenbion second block
15
20
30
Figure 13: Visualisation of the 2-simplicial attention in the second Transformer block in step 29 of an episode of puzzle type (3, 3, 5). Entity 7 is associated with the inventory, 17 is the player. Shown a 2-simplex with target 17.
To give more details must first examine the content of the virtual entities after the first iteration, which is a function of the 1-simplicial attention of the virtual entities in the first iteration. In Figures show these attention distributions multiplied by the pixels in the region [1, R x
22
13
21

---

Published as a conference paper at ICLR 2020
[1,C - 1] of the original board, in the second and third columns of the second and third rows Let fi = εд and fz = 611 denote the initial representations of the first and second virtual entities, before the first iteration. We use the index E {1 to stand for virtual entity. In the first iteration the representations are updated by (14) to
f = LayerNorm
go [
Σ Di [b fz)
(29)
where the sum is over all entities the a are the attention coefficients of the first 1-simplicial head and the coefficients bg are the attention of the second 1-simplicial head. Writing O,, O2 for the zero vector in Hi. H3 respectively, this can be written as
f- LayerNorm go
Σ a (va 02)
Σ b (01 + va)) fz)
(30)
For query entity i the vector propagated by the 2-simplicial part of the second iteration has the following terms, where = (W W
B f1) + Bi2 2 ft) A2, f1) 12, f2).
(31)
Here A3.A is the 2- 2-simplicial attention with logits (pi, J (2) associated to (i, k).
The tuple (Ai. Ai.,, Ab,1, A4, is the ith column in our visualisations of the 2-simplicial attention,
so in the situation of Figure with 25 we have A3. and hence the output of the 2-simplicial head used to update the entity representation of the bottom lock on the Gem is approximately B % () we ignore the layer normalisation, feedforward network and skip connection in 330 then
S en O2 and f/2 R 0, @ to that the output of the 2-simplicial head with target 25 is approximately
B((u @ 02) & (0, $ vo)).
(32)
Following Boole (Boole 1847) and Girard (Grardd 1987) it is natural read the "product" (32) as a conjunction (consider together the entity and the entity () and the sum in (3T) as a disjunction. An additional layer normalisation is applied this vector, and the result concatenated with the in- coming information for entity 25 from the 1-simplicial attention, before all of this is passed through to form 222
12
Given that the output of the 2-simplicial head is the only nontrivial difference between the simplicial and relational agent (with a transformer depth of two, the first 2-simplicial Transformer block only updates the standard entities with information from embedding vectors) the performance differences reported in Figure suggest that this output informative about avoiding bridges.
F.2 THE PLATEAU
In the training curves of the agents of Figure Figure we observe a common plateau at a win rate of 0.85. In Figure we show the per-puzzle win rate of simplicial agent A and relational agent A. on (1, 2) puzzles. These graphs make clear that the transition of both agents to the plateau at 0.85 is explained by solving the (1, 1,2) type (and to a lesser degree by progress on all puzzle types with b 1). In Figure 14fad Figure 15 we give the per-puzzle win rates for small sample of other puzzle types. Shown are the mean and standard deviation of 100 runs across various checkpoints of simplicial agent A and relational agent A.
G LARGE EPSILON RMSPROP
As originally presented in (Tieleman & Hinton 2012) the optimisation algorithm RMSProp is mini-batch version of Rprop, where instead of dividing by different number in every mini-batch
FFor visibility in print the 1-simplicial attention of the virtual entities in these figures has been sharpened, by multiplying the logits by 2. The 2-simplicial attention and 1-simplicial attention of standard entities have not been sharpened. In this connection, we remark that in Figure there is one entity whose unsharpened attention coefficient for the first virtual entity in the first head is more than standard deviation above the mean, and there such entities for the second virtual entity and second head.
22

---

Published as a conference paper at ICLR 2020
Sirpkiill aguet
Poli Rowe
Toctan sale
(1,1,2) bridge
2
(2.2.4) bridge
Figure 14: Simplicial and relational agent win rate on puzzle types (1, 1, 2), (2, 2, 4).
Si Stmplic agurt
inlabcea upair.
(3,3.5) bridge
war
(3.3.6) bridge
Figure 15: Simplicial and relational agent win rate puzzle types (3,
(namely, the absolute value of the gradient) we force this number to be similar for adjacent mini- batches by keeping a moving average of the square of the gradient. In more detail, one step Rprop is computed by the algorithm
Ti x g
KB
3; T;
Vrs +
where x is the learning rate, -; is a weight, gi is the associated gradient and is small constant (the TeosorFlow default value 10 10-10) added numerical stability. The idea of Rprop is update weights using only the sign of the gradient: every weight is updated by the same absolute amount each step, with only the sign gi/ = g./lgal the update varying with i. The algorithm RMSprrpp introduced refinement of Rprop:
f pr: + (1 p)g
KgJ
x - -; Vr: +
where p is the decay rate (in experiments the value is 0.99). Clearly Rprop is the p -> 0 limit of RMMprrp. For further background see (Goodfellow et al. 2016 88.5.2).
In recent years there has been trend in the literature towards using RMSprop with large values of the hyperparameter For example in (Zambaldi al. 2019) RMSProp is used with 0.1. which
23

---

Published as a conference paper at ICLR 2020
is also one of the range of values in (Espeholt et al. 2018 Table D.I) explored by population based
training (Jaderberg et al. 2017). This "large E RMSProp" seems to have originated in (Szegedy
et al. 2016 y8). To understand what large RMSProp is doing, let us rewrite the algorithm
Ts f pr, + (1 p)g
Kgi 1
VTi
VI+E/Ta
Kg
Vra
S
where S' is the sigmoid S(u) - u/ w/vI++ 2² which asymptotes to 1 as u - +os and well- approximated by the identity function for small u. We see a new multiplicative factor S( (Tir/)) in the optimisation algorithm. Note that vr; is moving average of 19il- Recall the original purpose of Rprop was to update weights using only the sign of the gradient and the learning rate, namely kg:/ VTi. The new S factor in the above reinserts the size of the gradient, but scaled by the sigmoid to be in the unit interval.
In the limit & + 0 we squash the outputs of the sigmoid up near and the standard conceptual description of RMSProp applies. But as + 1 the sigmoid S(yr)) has the effect that for large stable gradients we get updates of size x and for small stable gradients we get updates of the same magnitude as the gradient. In conclusion, large e RMSprop is a form of RMSprop with smoothed gradient clipping (Goodfellow et al. 2016 $10.11.1).
H LOGIC AND REINFORCEMENT LEARNING
It is simple matter to define logical reasoning nor to recognise when an agent (be it an animal or a deep reinforcement learning agent) is employing such reasoning (Mackintosh, [201 Barrett ct al. 2018). We therefore begin by returning to Aristotle, who viewed logic as the study of general patterns by which one could distinguish valid and invalid forms of philosophical argumentation; this study having as its purpose the production of strategies for winning such argumentation games Spade& & Hintikka 2019). In this view, logic involves
Aristotle 1984. Smith 2019.
two players with one asserting the truth of proposition and attempting to defend it, and the latter asserting its falsehood and attempting to refute it, and an
observer attempting to learn the general patterns which are predictive of which of the two players will win such a game given some intermediate state.
Suppose we observe over series of games that a player is following an explicit strategy which has been distilled from general patterns observed in large distribution of games, and that by following this strategy they almost always win. A component of that explicit strategy can be thought of as logical reasoning to the degree that consists of rules that are independent of the particulars of the game (Aristotle, 1984, $11.25). The problem of recognising logical reasoning in behaviour therefore twofold: the strategy employed by player typically implicit, and even if we can recognise explicit components of the strategy, in practice there is not always clear way to decide which rules are domain-specific.
thha
In mathematical logic the idea of argumentation games has been developed into theory of math- ematical proof as strutegy in the game semanties of linear logic (Hyland. 1997) where one player (the prover) asserts proposition G and the other player (the refuter) interrogates this assertion
"We cannot infer that behaviour constitutes logical reasoning if we only observe it over the course of single game. For example, while may appear that human proving statement in mathematics by correctly applying set of deduction rules engaged in logical reasoning, this appearance may be false, for if we were to observe one thousand attempts to prove a sample of similar propositions, and in only one attempt was the human able to correctly apply the deduction rules, we would have to retract our characterisation of the behaviour logical reasoning. The concept is also empty if insist that applies only if in every such attempt the deduction rules correctly applied, because human mathematicians make mistakes.
'It is possible for the prover to win such an argument without possessing a proof (for instance if G is the disjunet of propositions A, B and the refuter demands proof of A in situation where the prover knows proof of A but not of B) but the only strategy guaranteed win is play according to proof.
24

---

Published as a conference paper at ICLR 2020
Consider reinforcement learning problem (Sutton & Barto 2018 in which the deterministic envi- ronment encodes G together with a multiset of hypotheses which are sufficient to prove G. Such pair is called sequent and is denoted I H G. The goal of the agent (in the role of prover) is to synthesise a proof of G from I through a series of actions. The environment (in the role of re- futer) delivers positive reward if the agent succeeds, and negative reward if the agent's actions indicate commitment to a line of proof which cannot possibly succeed. Consider a deep rein- forcement learning agent with a policy network parametrised by vector of weights w E IR and a sequence of full-episode rollouts of this policy in the environment, each of which either ends with the agent constructing a proof (prover wins) or failing to construct a proof (refuter wins) with the sequent r + G' being randomly sampled in each episode. Viewing these episodes as instances of an argumentation game, the goal of Aristotle's 's observer is to learn from this data to predict, given an in- termediate state of some particular episode, which actions by the prover will lead to success (proof) or failure (refutation). As the reward is correlated with success and failure in this sense, the goal of the observer may be identified with the training objective of the action- vvauue network underlying the agent's 's policy, and we may identify the triple player, opponent, observer with the triple agent, enviroument and optimisation process. If this process succeeds, so that the trained agent wins in almost every episode, then by definition the weights w are an implicit strategy for proving sequents T
This leads to the question: is the deep reinforcement learning agent parametrised by w performing logical reasoning? We would have no reason to deny that logical reasoning is present we were to find, in the weights w and dynamics of the agent's ' network, an isomorphic image of an explicit strategy that we recognise as logically correct. In general, however, it seems more useful to ask to what degree the behaviour is governed by logical reasoning, and thus to what extent we can identify an approximate homomorphic image in the weights and dynamics of a logically correct explicit strategy. Ultimately this should be automated using "logic probes" along the lines of recent developments in neural network probes (Alain & Bengio, 2016 Koh & Liang 2017 Nguyen et al., 2016 Shrikumar et al. 2017: Simonyan et 2013).
1 STRATEGIES AND PROOF TREES
The design of the Box World environment was intended to stress the planning and reasoning com- ponents of an agent's policy (Zambaldi et al. 2019 p.2) and for this reason it is the underlying logical structure of the environment that is of central importance. To explain the logical structure of Box World and bridge Box World we introduce the following notation: given a colour e, we use C to stand for the proposition that a key of this colour is obtainable. Each episode expresses its own set of basic facts, or axioms, about obtainability. For instance, a loose key of colour c gives C as an axiom, and locked box requiring a key of colour in order to obtain a key of colour d gives an axiom that at first glance appears to be the implication C - D of classical logic. However, since key may only be used once, this is actually incorrect; instead the logical structure of this situation is captured by the linear implication C -o D of linear logic (Girard 1987). With this understood, each episode of the original Box World provides in visual form a set of axioms I such that a strategy for obtaining the Gem is equivalent to proof of l' H G in intuitionistic linear logic, where G stands for the proposition that the Gem is obtainable. There is a general correspondence in logic between strategies and proofs which we recall in Appendix[[ [
To describe the logical structure of bridge Box World we need encode the fact that two keys (say a green key and blue key) are required to obtain the Gem. Once again, it is the linear conjunction @ of linear logic (also called the tensor product) rather than the conjunction of classical logic that properly captures the semantics. The axioms I encoded in an episode of bridge Box World contain a single formula of the form X1 69 X₂ -o G where Ii, 32 are the colours of the keys on the Gem, and again a strategy is equivalent to proof of r + G. In conclusion, the logical structure of the original Box World consists of a fragment of linear logic containing only the connective -o, while bridge Box World captures a slightly larger fragment containing and &.
Next we explain the correspondence between agent behaviour in bridge Box World and proofs in linear logic. For an introduction to linear logic tailored to the setting of games see (Martens 2015 Ch.2). Recall that to each colour c we have associated a proposition C which can be read as "the key of colour e is obtainable". If box 3 appears in an episode of bridge Box World (this includes loose
25

---

Published as a conference paper at ICLR 2020
keys and the box with the Gem) then assume given proof π of sequent associated to the box by the following rules: the sequent X H Yg associated to a loose key of colour c - C, the sequent associated to ordinary box with lock of colour and containing key of colour c' is C } C" and the sequent associated to a multiple lock on the Gem, with key colours c, c' is C & C' F G. In the following identify the box B with its associated sequent, and write for example n xCC for the chosen proof associated to the loose key of colour c. The set of premises (or axioms) in an episode of bridge Box BoxWorld is the multiset I' of proofs x as 3 ranges over all boxes.
Definition I.1. Given formula A (thought of representing the contents of the inventory) and 3 box B define the proof 7 be
AF A
X3 H Y
(33)
A, F A A Ya
ØL
A& Xa A Y
One can think of this proof as the algorithm which acts to update the contents of the inventory upon opening the box 3.
Example 1.2. Consider the episode of Figure and path and then the lower, obtaining the keys in the following order: g (green), (orange), g' (dark green), m (magenta), (purple) and 6 (blue). Then the proof tree whose computational content matches this behaviour is given by:
and suppose that the agent follows the upper solution
G-O
OHG
π
M G
+ G
G
O
MHP G
G'
(34)
PHB
G'
G' G
&M
G
G
COMHGOL
T GOP
G'
& G
F C
where unlabelled deduction rules are cuts. Cutting this proof tree against the proof G a BBG asso- ciated to the final box gives the proof encoding the agent's 's strategy.
This example makes clear the general rule for associating proof tree to agent's 's strategy, as embodied in its behaviour: take the sequence of boxes 31,...,ßy By opened by the agent together with the state of the inventory J1,..., IN the time of each opening, and cut the corresponding sequence of proofs xi; against one another.
MOTIVATION FROM NEUROSCIENCE
The successful examples representations deep learning, those learned by convolutional neural networks, are structured by the scale and translational symmetries of the underlying space (e.g. a dooddmmnniionl Euclidean space for images). It has been suggested that in humans the ability to make rich inferences based on abstract reasoning is rooted in the same neural mechanisms underlying relational reasoning in space (Constantinescu et al. 2016 Epstein et al.) 2017] Behrens al. 2018 Bellmund et al. 2018) and more specifically that abstract reasoning is facilitated by the learning structural representations which serve to organise other learned representations in the same way that space organises the representations that enable spatial navigation (Whittington al.
2018 Liu et al. 2019).
As motivating example take the recent progress natural language tasks based on the Trans- former architecture /Vaswani et al.] 2017) which simultaneously learns to represent both entities (typically words) and relations between entities (for instance the relation between "cat" and "he"
26

---

Published as a conference paper at ICLR 2020
in the sentence "There was cat and he liked sleep"). These representations of relations take the form of query and key vectors governing the passing messages between entities; messages update entity representations flect not just the meaning of words but also their context sentence. There is some evidence that the geometry of these final representations serve to organise word representations in syntax tree, which could be seen as the appropriate analogue to two-dimensional space in the context of language (Hewitt & Manning, 2019).
several rounds of computation until the final representations
The Transformer may therefore be viewed as an inductive bias for learning structural representa- tions which are graphs, with entities as vertices and relations as edges. While graph is discrete mathematical object, there is a naturally associated topological space which is obtained by gluing 1-simplices (copies of the unit interval) indexed by edges along 0-simplices (points) indexed by vertices. There is general mathematical notion of simplicial set which is a discrete structure containing set of n--implices for all n 2 together with an encoding of the incidence relations between these simplices. Associated to each simplicial set is topological space, obtained by gluing together vertices, edges, triangles (2-simplices), tetrahedrons (3-simplices), and so on, according to the instructions contained in the simplicial set. Following the aforementioned works in neuroscience (Constantinescu et al. 2016 Epstein et al., 2017: Behrens et al. 2018| Bellmund et al.) [0188] Whit- tington al. 2018 Liu al. 2019) and their emphasis spatial structure, it natural to ask if a simplicial inductive bias for learning structural representations can facilitate abstract reasoning.
This question partly motivated the developments in this paper.
27


Reviews:
[{"review_id": "rJg7BzyAYS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper is an extension of the Transformer Algorithm used to solve sequential problems such as in NLP and games (such as the BoxWorld environment from Zambaldi et al.), stating that the Transformer Algorithm is an inductive bias for learning structural representations.\nThe authors argue that, the use of simplicial inductive biases over the normal relational inductive bias (provided by the Transformer algorithm) may be a better way to achieve abstract learning; in fact they argue that the “relational inductive bias” used in the normal Transformer is just a 1-simplicial Transformer, thus the more complex topological space provided by the 2-simplicial Transformer should generate better results than the 1-simplicial Transformer.\nWhile technically sound  it’s not obvious whether  this implementation is indeed better than the normal.\n\nFirst of all the significance of the results are heavily determined by the fact that the authors just displayed the results of the proposed algorithm against the “normal Transformer”, using a modified version of the BoxWorld. Moreover  in the paper it is stated that, they tested the new algorithm with the original BoxWorld environment, but they omitted it as the proposed algorithm excelled over the old one in such environments. Also the relational induction algorithm used in this paper does not seem to be the same as the one used by Zambaldi et al.\n\nSecond, Im concerned about the explanation made where they try to justify that the use of the bridge-BoxWorld which is argued to provide a more complex logical structure because of the use of linear logic-formulas using more connectives. In other words, the question arises as to whether the authors thought that a more complex logical structure would i mply a more complex environment, thus justifying the use of the bridge-BoxWorld. \n\nFinally, it is worth reiterating that, although the use of simplices and simplicial complexes is a very interesting idea, especially to provide a mathematical explanation of how attention works in the Transformer, it’s not entirely obvious  whether the implementation of the 2-simplicity Transformer really presents an improvement over the original Transformer, in the learning of abstract representation. ", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "r1erdj7CFB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a transformer block with higher-order interactions. More precisely, instead of computing a dot product between a query vector and a key vector, 2-simplicial attention computes scalar triple product. Instead of computing a weighted average of value vectors, 2-simplicial attention computes the weighted average of tensor products of value vectors. The resulting architecture has improved representation power which is demonstrated using experiments on bridge BoxWorld environment.\n\nThe major gripe I have is a lack of discussion in the main paper of how precisely, 2-simplicial attention can help solve better bridge BoxWorld. I did notice some discussion of this in Appendices F, H and I. But I believe the reader would be better served by having such a discussion in the main body. More generally, what kind of tasks can 2-simplicial attention address better? Answering/discussing this question can go a long way in making the paper more valuable.\n\nIs it possible to evaluate the improved expressivity of 2-simplicial attention on real-world datasets/tasks?", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Skes8yd0FS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "CONTRIBUTIONS:\nC1. Simplicialization of attention. Interpreting standard attention weights of a head as the model’s estimate of the probability of an edge = 1-simplex linking the variables encoded by 2 blocks of the Transformer, representing that the blocks stand in a binary relation encoded in the head, a generalization to 2-simplexes is made: now attention also estimates the probability of a 2-simplex indicating that three blocks stand in an arity-3 relation. \nC2. 2-simplicial attention. The standard query-key matching function, the scalar (dot) product, is related to the area of the 2-simplex determined by the 2 vectors and the origin, and this is generalized to the (unsigned) scalar triple product <a,b,c>, analogously related to the volume of the 3-simplex determined by 3 vectors and the origin. This now serves as the matching function between a query and 2 keys. Each head in each block generates a value vector u and two key vectors k1, k2 and the weight of attention from block(i) (with query p(i)) to the ordered pair (block(j), block(k)), a(i,j,k), is a softmax over <p(i), k1(j), k2(k)>. Attention returns to block(i) a sum in which a(I,j,k) weights B(u(j)*u(k)), with B a learned linear map and * the tensor product. \nC3. Experimental results applying Transformers T1 (with standard 1-simplicial attention) and T2 (with new 2-simplicial attention) to modeling an agent in bridge BoxWorld, trained with deep RL. This game crucially involves 3-way entity interactions, as keys of 2 colors open a box yielding a key of a 3rd color. T2 learns significantly faster than T1 (in the sense that the 1-standard-deviation-neighborhood of the learning curve of T2 becomes better than that of T1, plotted against environmental steps: Fig.4, and also essentially so when plotted against time adjusted steps: Fig 5).\nRATING: Accept\nREASONS FOR RATING (SUMMARY). Generalizing attention from 2nd- to 3rd-order relations is an important upgrade, and the mathematical context in which this is derived is insightful and may lead to further progress in the development of Transformers capable of constructing still richer structures. The experiments yield clear evidence of the value of 3rd-order attention in the context of a game designed to highlight 3rd-order relations.\nStrengths\nThe exposition is clear and situated in a rather sophisticated formal setting. The connection to Clifford algebras may yield further fruit, besides the scalar triple product that is crucial to the definition of 2-simplicial attention. Although I am not an expert in RL, the experiments reported seem sound and the results clear. I believe that the strength of the paper justifies its length of 8.5 pages: the exposition of the key ideas, for this reader, hits a sweet spot between overly concise and overly verbose, and the ideas call for the quantity of space devoted to them. The decisions of what material to place in the Appendix seem well made. Although I have not studied the entire (13-page) Appendix, what I have read is clear and enlightening, another major contribution of the paper.\nWeaknesses\nFuture work testing the value of 3rd-order attention in tasks that are less clearly perfectly designed for it will substantially strengthen the case for it. But in my view it is right to start testing a new architecture by showing it can indeed do what it is designed to do; further tests showing that what it is designed to do is of general utility are a second step. In this case, the first step, including creating of the model itself (consuming 5 non-verbose pages), is substantial enough to warrant publication.\nIn my good-quality printout of the paper, I can’t see curves for best runs in Fig. 4.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper extends the Transformer, implementing higher-dimensional attention generalizing the dot-product attention. The AC agrees that Reviewer3's comment that generalizing attention from 2nd- to 3rd-order relations is an important upgrade, that the mathematical context is insightful, and that this could lead to the further potential development. The readability of the paper still remains as an issue, and it needs to be address in the final version of the paper.
Decision: Accept (Poster)