Algebraic Positional Encodings
Authors: Konstantinos Kogkalidis
Jean-Philippe Bernardy
Vikas Garg
Venue: NeurIPS 2024 spotlight (2024)
Keywords: positional encodings
transformers
structured attention
group theory
Primary area: deep_learning_architectures
TL;DR: Positional encodings as group homomorphisms: it's beautiful and it works.

Abstract: We introduce a novel positional encoding strategy for Transformer-style models, addressing the shortcomings of existing, often ad hoc, approaches. Our framework implements a flexible mapping from the algebraic specification of a domain to a positional encoding scheme where positions are interpreted as orthogonal operators. This design preserves the structural properties of the source domain, thereby ensuring that the end-model upholds them. The framework can accommodate various structures, including sequences, grids and trees, but also their compositions. We conduct a series of experiments demonstrating the practical applicability of our method. Our results suggest performance on par with or surpassing the current state of the art, without hyper-parameter optimizations or ``task search'' of any kind.
Code is available through https://aalto-quml.github.io/ape/.

Algebraic Positional Encodings
Konstantinos Kogkalidis! kokos. idi
Jean-Philippe Bernardy
Vikas Garg 1.5 vgarg@csail edu
sannphhiippe. www.bbbrrrrreeeeeeeee
Aalto University
University of Bologna
University of Gothenburg
*Chalmers University of Technology Yai Yai Ltd
Abstract
We introduce a novel positional encoding strategy for Transformer-style models, addressing the shortcomings of existing, often ad hoc, approaches. Our framework implements a flexible mapping from the algebraic specification of a domain to a positional encoding scheme, where positions interpreted orthogonal operators. This design preserves the structural properties of the source domain, thereby ensuring that the end-model upholds them. The framework can accommodate various structures, including sequences, grids and trees, but also their compositions. We conduct series of experiments demonstrating the practical applicability of our method. Our results suggest performance on par with or surpassing the current state of the art, without iyper-parameter optimizations or "task search" of any kind. Code is available through https: /aallttoo quml. gi thub. io/ape/.
Introduction
Attention-baan based models inheriting from the Transformer [Vaswani et al., 2017] have become ubiqui- tous in neural computation, supplanting the go-to models of the last decade and driving a continuous stream breakthroughs across diverse domains. Their success is perhaps at odds with the Trans- former's structural lenience. Its key building block, dot-product attention, is by default unable to perceive and utilize the structure and arrangement the input/output tokens being processed. To address this limitation, plethora of works have sought to endow Transformers with appropriate inductive biases. The default strategy is to adjust token representations via so-called positional encodings: vector operations that hint at the structure being modeled. Nonetheless, most positional encoding schemes to date are either empirically motivated, or tailored to specific tasks. This renders their theoretical evaluation challenging, and hinders any prospects of unifying framework.
In this study, we seek to fill this gap with a theory-first approach. Through the lens of group theory, we scrutinize some of the most commonly targeted data structures, and express them by means of inductive definitions that reveal and explicate their structural properties. Leveraging this analysis, modeling strategy invokes homomorphic interpretation that maps each domain into algebraic positional encodings (APE): attention-com compatible vector operations parameterizing (subgroups of) the orthogonal group. In the sequential context, algebraic positional encodings streamline the widely adopted rotary encodings of Su et al. [2023], while also offering clear theoretical insights on their success. More importantly, algebraic positional encodings naturally extend non-sequential domains, such as k-ary trees and multidimensional regular grids, paving the way for a simple and elegant methodology for interpretable and domain-general structurally-refined Transformers. We carry out an experimental evaluation in settings that allow for reproducible and statistically sound conclusions. Across the tasks considered, algebraic positional encodings consistently and significantly outperform strong baselines at an aggregate level, providing initial but compelling evidence that they constitute not just a sensible meta-theon for positional encodings, but also an actionable alternative to the current state of the art.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

CONTRIBUTIONS PAPER STRUCTURE
$2 BACKGROUND
We introduce the problem ()2.1) and the vocahulary of the solution ($2.2).
$3 THEORY
We provide algebraic characterization of positions in the context of different ambient structures. We frame algebraic positional encodings as structure- preserriigg semantic interpretations, and present reference implementations. Concretely:
$3.1 Sequences are an isomorphism of the free group (1) (Le., the integers, Z.), and can be interpreted as a single generator subgroup of the orthogonal group (dd).
$3.2 Rotury Positional Encodings correspond to (quite literally) special case of interpretation: SO(d).
$3.3 k-ary Trees are un isomorphism of the finitely generated group (1.2... n), and can be interpreted as a finitely
generated subgroup of (d).
$3.4 Regular Grids are the group direct sum multiple sequences. They can interpreted as the matrix direct sum their components' interpretations.
$3.5 Extensions can be obtained in multiple directions.
$4 PRACTICE
We carry fair and replicable experiments across all three structures analyzed, namely Sequence Trunsduction (84.1), Tree Transduction ($4.2) and Image Recognition (84.3), and find that algebraic positional encodings consistently match outperform alternative schemes in the tasks considered (84.4).
$5 RELATED WORK
We position our work in the context of the broader literature.
$6 LIMITATIONS
We close with a brief discussion of possible limitations and potential future improvements.
Table 1: A summary of this paper.
2 Background
2.1 The Problem with Dot-Product Attention
All transformer variants employ some variation of the multi-head scaled dot- product attention mechanism of Vaswani al. [2017]. For each attention head, the dot-product attention between queries X E Raad and keys Y E Raxd is defined as:
atn MinnXX, Y) softmax(()) (x)(1) (Y (
Y (T(1))
(1)
Vd
In equation (I), matrices k/4), (x),,
(10)),)) <b(v) Rddd enact linear functions, applied point-wise (broad- casted) across all m and entries of X and Y. The dot-product term (X (Y contains unnormalized attention scores in the Cartesian product of queries and keys. Unmodified, dot-product attention is permutation invariant with respect to its second argument; that is, for any arbitrary permutation Ps, E Sn
atn X. Y) atn X, (Y))
(2)
Unless one is dealing with orderless structures like multisets fully connected graphs, this property generally undesirable. The lack of structural biases is traditionally counteracted by the component- wise addition of unidimensional periodic signals of varying frequencies. These, however, often prove inadequate in data-scarce domains, where extensive pretraining is impossible, and structure-rich domains, where sequense-of-tokens projection is too radical of simplification.
2.2 Recap Group Theory
To address this issue, we propose an algebraic treatment of positional encodings, based principles lent from group theory. For the sake of convenience and accessibility, we provide a brief recap of the notions of interest here. A group G consists of a set of elements and binary operation (.) satisfying four fundamental laws:
The group is closed under the the group operation. For all a, b in G, a is also in G.
The group operation asxociative. For all a, b, G, (a b) c a. (b.c).
The group operation has an identity element e, such that for all in G. e Fach group member has an inverse. For all a G, there exists some element a such that a7 Za e, where is the identity element.

---

A group is characterized as finite or infinite depending on the number of elements it has. If all elements of a group G can be expressed as a combination of a subset 5 of the group elements (combined by means of the group operation, applied either on the elements themselves or on their inverses), we write G = (S). We say that G is generated by S, and we call the elements of S the generators of G. group with a single generator is called cyclic.
3 The Algebra(s) of Positions
Our objective is to establish framework that offers general and extensible semantics for positions across various structures what we commonly encounter in the litcrature as positional encodings. Most existing proposals adopt a rather parochial stance, relying maneuvers or heuristies tailored to specific applications and driven, predominantly, by extensive empirical investigations. As such, they fall short with respect accommodating or reflecting the properties of the underlying structure. We follow a different approach. We adopt Montague's 's perspective, succinctly paraphrased as:
"syntux is an algebra, semantics is an algebru, and meaning is a homomorphism between them" [Janssen, 2014].
We begin by noting that "positions" do not exist in isolation, but only in the context of some underlying ambient structure. We contend that reasonable positional encodings (semantics) may only be reliably obtained by taking into account exactly this structure, its formation rules and properties (syntax), and then applying an appropriate interpretation (meaning). This is not just an academic exercise: a careful syntactic specification is a prerequisite if we aim for semantics that adhere to certain properties, which is arguably preferable to searching for these properties in the wild.
3.1 Sequences
Syntax We start from the simplest structure, and incidentally also the most standard one: the sequence. The full range of positions a token can occupy within a sequence coincides exactly with the naturals, IN. Relative paths P between any two positions then be seen the integers, Z, with positive (resp. negative) numbers denoting forward (resp. backward) offsets. Using this insight, is handy to inspect how the standard inductive definition of the integers provides the building blocks for path formation. We start with two constants: the empty path (0), which relates any given point to itself, and the unit path (1), which relates any point its immediate next. We may compose simple paths into complex ones with the aid of a binary operation +p. This already suffices to specify all forward offsets. In order construct backward offsets, we need unary operation (-)p, such that denotes the inverse of p. We can summarize the above by the grammar:
P= P
(3)
For this to make sense, the operations must be coherent; that is, all ways to start from point P and end up in point /22 should be equivalent, even if apparently distinct. The needed equivalences exactly correspond to the group laws, with closure internalized by the inductive definition of (3):
(pi +P P2) + P3 P1 +r (02 + Ps)
(L.1)
ptr 0
0 +rp
(L2)
P p+v (-p) =
(L3)
The (unsurprising) insight here is that paths in a sequence form a free group, generated by a single generator (1) the uniqueness of the generator exceptionally also makes the group abelian (i.e., commutative). For convenience, we adopt the notational shorthand 1P, where:
1 +p tp1
p p20 0
1P
(4)
(-(-1) P<0
Semantics The syntactic specifications of the previous paragraph impose constraints on the can- didate semantic targets. Among these candidates, we isolate and focus on (W), the subgroup of the orthogonal group (d) that is generated by a single orthogonal matrix W. This semantics is not only sound with respect to the structure under scrutiny, but also a familiar object in machine
It is also complete except for the odd case where W I for some p. In practice, this kind of periodic behaviour does not arise randomly, and can think of (W) being isomorphic to P.
3

---

learning literature [Arjovsky al., 2016, Bernardy and Lappin, 2022, inter alia]. Note that for (W). the group axioms are obtained for free from the orthogonal group, and the additional requirement of commutativity is again satisfied by the uniqueness of the generator.
To illustrate the correspondence between the two structures (and at risk of being pedantic), we spell out the homomorphism [.], which maps paths P to elements of (W), and path operations to operations on orthogonal matrices of size d. For the primitives, we have [0] := Ia and [1] == W. Path composition amounts to matrix multiplication, f.e., [p] tr P2
[p1 [22]. while path inversion [p] The fact that orthogonal matrices
corresponds to matrix transposition, iee, [-pl pl == [p] form a group under multiplication is folklore; one can easily verify that the group laws hold also for the semantics. ?
Implementation In practice, we have [12] + WP; a norm-preserving bilinear form R4 x R + R which can be used to mediate the dot-product between a query q and a key & offset by a relative distance of p. The representation of all paths up length p can thus be implemented as matrix collection W...... W?], which can asymptotically be obtained using products (of exponentially larger matrices), and taking up the storage space equivalent of (pd=) floats. Transposed, the same matrices also serve to represent backwards paths [W-P.- ..... W Storing the representations of all relative paths between queries and keys in a tensor T Rmxxxdxd we may then substitute the dot-product term of equation (I) for the tensor contraction:
matrix
Σ
(TT X ma 03 mnyy a,B
Y, nd
(5)
Albeit transparent, this reduction strategy is computationally unappealing due to the doubly quadratic nature of T. We can do better by noting that Tmn is (definitionally) equal to:
T T
(X) A Σ
(X) Any9
(6)
where (X) and A are the matrices containing representations for the absolute positions of the entries in X and Y, respectively. Concretely, a single relative representation is built by composing the inverted representation of the source with the representation of the target. Intuitively, each query follows the path that takes it back to the origin, which then allows it to directly combine with each forward-offset key; see Figure la for a visual example. This insight allows us to keep the memory footprint of equation (1) unchanged, replacing expression (5) with:
Σ 0,,.,y
(a) as
(X)
Y Φ
m any
This version decomposes the tensor contraction into two matrix multiplications, essentially transform- ing (rotating or reflecting) the entries of X and Y independently according their positions.
3.2 Intermezzo: Equivalence with ROPE
The story so far should be reminiscent of the rotary positional encoding scheme of Su et al. [2023, ROPE]. Not unlike our approach, RoPE substitutes the vanilla dot- dot-product for a position-dependarn bilinear form. Underlying the form is d x d-dimensional matrix R with block-diagonal structure, where each 2 x 2-sized block corresponds to a rotation matrix that acts on a 2-dimensional subspace of Rd. These independent rotations are parameterized by (fixed) set of base angles θ = [0],- , 00/2] To incorporate position-deppendenee, i.e., for a query/key pair at relative distance of p. the base angles multiplied by p. effectively altering the rotations applied.
At first glance, rotary encodings appear to be under- paadeerprrmmterizedd, and thus strictly weaker than orthogonal ones. However, any orthogonal matrix W E ((d) admits canonical form W PQP where P is an orthogonal change of basis, and Q is block-diagonal, with the x 2-sized blocks being, once again, 2 2-dimensional rotation matrices [Murnaghan and Wintner, 1931]². f Owing to the orthogonality of P, raising W to its pth power is equal to PQ" PT (i.e., it leaves the change of basis unaffected). In turn, raising Q to its pth power is equivalent to simply multiplying the rotation
"The story no different for W unitary, with the group structure provided by the unitary group (d), and path inversion interpreted as the matrix conjugate transpose.
We alert the reader that constructive proof of this decomposition has proven surprisingly difficult find.

---

angles of its blocks by p. Finally, given the linearity of the transformations (69) and ((k), their compositions with P are also linear. By identifying Q with ROPE's R. we can then see that, for any given collection of angles O, APE and ROPE coincide under the substitutions:
(q) ROPE
+ (4)
Q and
(k) KOPE
& (k)
Q
(8)
In practical terms, and uniquely for the sequential case, APE is equivalent to a trainable version of ROPE, where the rotation angles θ may vary and be optimized during training."
Which of the two parameterizations is preferable debatable. On the one hand, APE'S formulation is FLOP -ptimizt (being just matrix multiplications), and obviates the need for backpropagating through trigonometric functions (which are periodic, non-monotonic, and prone to gradient instabili- ties). On the other hand, RoPE's diagonalized form gives access to memory memory-efficient contraction that does away with the matrix multiplications of expression (7) altogether; we direct the interested reader to Su et al. [2023, Section 3.4.2] for a reference implementation.
In either case, the equivalence between the two confined the sequential setup; we will now move on to generalize our strategy to other, previously inaccessible, structures.
3.3 Trees
Syntax In the previous section, we characterized the structure of relative paths on sequence as the free group with one generator, and uncovered a (practically) isomorphic interpretation in the subgroup of orthogonal matrices with a single generator. Upon closer inspection, we note that sequence can be viewed as a special case of the more general structure of K-ary branching trees, where the branching factor k just so happens to be 1. Denoting the more general case as Px,, we must first extend the set of primitives to include all branching options, 1, K. Px- Each primitive now denotes choice of branch (except for 0 which is again the empty path). Paths now form free group with x distinct generators. The presence of multiple generators means that commutativity no longer holds; +p. 2 is distinct from 2 +p. (the former prescribes descent down branch then branch 2, whereas the latter prescribes a descent down branch 2 then branch 1). Inversion is as before: for every path from each local root some descendant down the line, there is also an inverse path from that descendant up to its ancestor. Perhaps more interestingly, upwards and downwards paths can be joined, allowing the precise specification of relative paths between any two nodes, even when the two do not share a single line of descent (think nephews, aunts and all other sorts of distant relatives, see Figure 1b for an example). Adjusting grammar (3) accordingly, we have:
Px = 0 1 ... K PA tP. Px Pr
with laws LI, L2 and L3 still in effect.
Semantics The interpretation follows along the same lines as before. This time around, however, we cannot make do with a single orthogonal matrix W we need a collection of k matrices, one for each branch option. As a consequence, the semantic target is now (W1, W Wx). Note that the target is no longer commutative (exactly in alignment with the source).
Implementation For a tree structure of depth 6 and branching factor K. let v denote the number of unique absolute positions occupied (upper bound by x in the case of complete tree). Their representations can be computed in ōτ steps of parallel matrix-matre multiplications and a memory cost of vd?. as follows. First, we can build up collection of all unique absolute paths, each repre- sented as a padded) word of length ó from the vocabulary of primitives. Their corresponding representations constitute a tensor of size iterate across these words in parallel, one primitive per step (i.e., depth) I, selecting all words that take the same branching direction at the current depth, and fightmmultplying their representations by the corresponding orthogonal generator. Finally, absolute paths can be composed into relative ones using the modified dot-product attention of expression (7), just like before.
d x d, initialized as v identity matrices. We can then
'An alternative reading is that even though orthogonal matrices are generally more expressive than rotation matrices (allowing just rotations but also reflections), the Transformer's 's architecture makes up for ROPE's reduced expressivity by supplying free change of basis through trainable weights 4. For more practical insights on initializing and parameterizing APE and translating between APE and RoPE, please refer to Appendix A.
5

---

3.4 Grids
The generalization from sequences to trees rests on the observation that a sequence is a tree with deficit of choices. An altogether different axis of generalization can be obtained by recalling that composite groups can be constructed by joining together two or more elementary groups. Moreover, it just so happens that the original groups were abelian, then so is their composition; in that case, we call the composite group direct sum. This construction provides access to an extension from sequences to multidimensional regular grids.
For the sake of simplicity and without loss of generality, we consider a standard instance of two- dimensional grid: an image. An image is a collection of pixels (or pixel patches) that inhabit coordinate system (h, w). Each of h and w is the product of grammar (3), inheriting all path path-related notions discussed earlier. Since is an abelian group, the coordinate system also constitutes an abelian group IPa := IP t P. The new group and inversion operations are +p and (-)pa, and denote the act of joining and inverting woo-dimensional paths, respectively. Both are canonically defined component-wise wise, on the basis of their one- counterparts:
(2, y) +p2 (z, w) == (x + y: 2 +p w)
(10)
(xx == == (- z, y)
(11)
with 0² : (0,0) 0) as the new neutral element. Intuitively, + corresponds to vector addition, and (-)pz to a reflection about the origin with respect to both axes.
Semanties The specifications above allow us to reuse the notions from Section 3.1 in order to interpret the components and operations of P What is left unspecified is the interpretation of the group elements themselves; that is, we have yet to explicate what an object of [P + P1 looks like. The quest is a short one; the notion of a direct sum carries over to matrices, and is defined as:
A B A
0 B
(12)
From this, get the (rather straightforward) interpretation [(p1. + [p1] 4 [p2]_
Implementation In practice, we now split the vector space in two independent parts. The first part is modulated by orthogonal matrices from (H), and the second part by orthogonal matrices from (W). For a query q and a key le that reside at a relative distance of (h, w), their attention score is computed as q( H @ W see Figure Ic for an illustration. Each axis contributes an additive but separable factor to the attention score, forcing the model to learn contextual alignments between token pairs on the basis of their coordinate- wise distances. Not much else is different: we can still compute all matrices in parallel, temporally bound by logarithmic complexity of log2 (max(h, w)) and max(h, (h, w){)) storage space, given grid of size (h, w). Subquadratic memory complexity can once more be achieved by virtue of diagonalization, just as in the sequential case.
3.5 Variants& Extensions
The structures that have seen far are not the only ones that our methodology can tackle in fact, many other group-like structures are amenable to similar interpretations. We sketch out some enticing examples below.
Our analysis has so far focused on paths relative to positions. Fixing the point of origin allows a straightforward simplification to absolute positions. The new structure is that of monoid: there's s no longer an inversion, and laws LI and L2 only are now in effect. The framework remains largely unchanged: one can still use subgroups of matrices represent positions, except this time applying them on either the queries or the keys (rather than both).
Absolute Positions
Periodic Domains Under addition, the integers form an infinite cyclic group. An interesting twist would be to consider the positional encodings of finite cyclic groups instead. Such structures are not uncommon; in chemistry, for instance, a benzene molecule comprises six carbon atoms arranged in ring. The semantics of such structure would need to be of matching period; that is, we would need a generator W such that T = Such a parameterization is straightforward; we simply need to fix the orthogonal matrix so as to have it implement rotations at angle-multiples of n/3.
Time Series & Subsampling Our sequential case analysis assumed dense sequence with a uniform sampling rate. However, our strategy also applies to any series, even if sparsely sampled, as long as the sampling rate is quantized (i.e., a multiple of some constant step). That is, positional indices (and their representations) do not need to match the placement of tokens in the sequence.

---

W
W
12
13
W W W
(a) The half-axis of absolute positions sequence, with visualization of the directions of relative paths between points and 4. either case, the interpretation is the matrix multiplication inverted source against the target.
11
12
21
22
(W2Wi)-WWWW W.W2
(b) The space of paths on binary branching trees, an illustration the relative path from 12. Same as before, the interpretation is the matrix multiplication of the inverted source against the target
(13,0)
2 + W
H + W
(1, 13)
(c) The quarter-planc of absolute positions a 2-dimensional grid, with visualization of the two directions of relative paths between points (3, 0) and 31, The interpretation now block-diagonal matrix consisting of the blocks interpreting the path over each coordinate.
Figure 1: Example paths and their interpretations across the structures examined.
The direct sum interpretation of Section 3.4 is applicable for arbitrary groups that can described as products, commutative or otherwise. This allows the representation of positional encodings for several other kinds of composite structures that can be concocted using the same principles, such as sequences trees, trees of grids, etc.
Composite Groups
Beyond Dot-Product Attention Throughout the previous sections, we have adopted a dot-product formulation for the attention weight function. Nonetheless, APE can be readily integrated into any other attention mechanism, such linear (Katharopoulos et al., 2020], cluster [Vyas et al., 2020] and "softmax-fiee free" [Lu et al., 2021] variants, inter alia.
4 Experiments
To assess the viability of our approach, we conduct series of experiments across range of tasks, in setups that allow for replicable and reliable comparisons with alternatives. When using APE, we follow Wu et al. [2021] in scaling the dot- fot-pro score between two tokens at distance of (i.e., steps away) by pf; here, we set e = 0.98. This serves to stabilize training by introducing a locality bias (or long-distance decay) factor. For the sake of parameter compression, we share the orthogonal matrices between the different encoder/decoder layers, but use a distinct matrix (or collection of matrices) per head. To isolate and quantify the effect of initialization, report results two
7

---

different initialization strategies: one where the orthogonal operators set mimic ROPE rotations (default), and one where they are set to be close to the identity (no init). Similarly, to isolate and quantity the effect of trainability when comparing to ROPE, we report results over both fixed (frozen) and trainable (tuned) rotation angles.
We provide extensive account of our experimental setups in Appendix B.
4.1 Sequence Transduction
Machine Translation First, we follow Vaswani al. [2017] in training Transformersase model on machine translation over WMT 14 EN -NE [Bojar et al., 2014].
To provide comprehensive comparison, pit our proposed methodology against standard positional encoding schemes from the literature: the vanilla Sinusoidal encodings of Vaswani et al. (2017], the Absolute encodings of Gehring et al. [2017]. the Relative encodings of Shaw et al. [2018] and the Rotary encodings of Su et al. [2023]. To ensure a fair comparison, we allow all models the exact same budgets (both memory and time).
Synthetic Tasks We further examine three standard sequence transduction tasks: sequence copying, sequence reversal, and sequence repetition. These are meant to directly assess each model's capacity for algorithmic induction, in setups where explicit position-based addressing, both absolute and relative, is required.
4.2
Tree Transduction
Next, we consider four algorithmic transduction tasks on binary branching trees: tree copying, recursive tree rotation up to a fixpoint, algebraic reduction of C3 expressions, and self-referential tree manipulation; see Appendix B for details.
In addition to previous sequential baselines, compare model to the encodings of Shiv and Quirk [2019, Tree-SQ). For all four tasks, we experiment with both breadth-firs. and depth-first decoding.
4.3 Image Recognition
Finaly, we train Compact Convolutional Transformer [Hassani et al., 2021] on CIFAR-10 [Krizhevsky et al., 2009].
Typically, attention-based architectures for vision rely additive positional encoding schemes, applied on the image prior to being sequentialized (row-by-row flattened). Here, we compare fixed [Wang and Liu, 2019, Sinusoidal 2D) and parametric [Gehring al., 2017, Absolute) variants of the above against both the sequential and the grid-structured versions of our scheme.
4.4 Results
We repeat each experiment three times, varying the seeds used for weight initialization and optimiza- tion, but fixing the data across repetitions. We report means and 95% CIs in Table 2. We highlight each category's 's best (in green), and underline scores where the CI spans the mean of the respective best.
At the macro level and consistently across modalities, appooi-ap algebraic interpretations match or surpass strong and specialized baselines without any syper-parameter tuning search. Specifically, across the 13 setups considered, APE is the uncontested top performer in 8, ranks among the best in 3, and falls within the confidence margin the top performer one. Exceptionally. in the breadth-fing version of the tree-copy task, tree algebraic encodings are surpassed by a handful of sequential alternatives; this no surprise, since this case the tree structure is practically task-irrelevant syntactic confound. Perhaps more surprisingly, in the breadth- tree-manipulation task, tree algebraic encodings are surpassed only by their non-initiann non-initialized, sequential version; an anomaly likely due to a single repetition with an unusually low perplexity score.
version of the
We also note three general trends. First, initializing APE to match ROPE frequency bands at the start of training consistently and significantly improves performance, possibly because ROPE rotary primitives have undergone empirical tuning for stability and performance. Second, given identical initialization, a sequential APE generally outperforms trainable ROPF, despite their theoretical equivalence. This might due to the difficulty of optimizing periodic signals (i.e., ROPF's ss trigonometric functions) compared to APE's (orthogonal) matrix multiplications. Third, frozen ROPE performs comparably to
8

---

Scheme
Sinusoidal
Absolute
Relative
Rotary
Algebraic
Task
(frozen)
(tuned)
(/v init)
(w/o inir)
WMT14 EN
14.57 10.12
22.09
23.15
24.03 10.06
23.92 20.20
23.93 10.10
23.84 1:010
(BLEC/1) /1)
COPY
1.01=0.00
1.11=00000
1.00+0.00
1.00+0.00
1.00=0.00
0.00=0.00
1.00=0.00
REPEAT
1.85=0.0
3.66
1.44=00.16
1.08+0.12
1.00=0.00
1.00=0.00
1.02+0.000
REVERSE
3.92=0.99
4.62:40.67
4.08
1.09+0.02
1.01 +0.00000
1.01 +0.00
1.03+0.02
(PPL./4)
(a) Performance results on neural machine translation and synthetic sequence transduction.
Task/Regression
COPY
ROTATE
C3
TREE-OPS
Scheme
breadth
depth
breadth
depth
breadth
depth
breadth
depth
Sinusoidal
1.0610.01
5.68
6.93
1..3
2.66=0.10
2.78 20.08
20.53
64.86 6.44
Tree-SQ
1. 1.29::0.01
1,07+0.00
2.60=0.16
1.87=0.21
2.27=0.59
2.29
19.18=3.25
16.41=6.11
Absolute
6.64::0.12
7.02:t0.17
7.77
7.24:0.20
2.77=0.21
2.79-0.22
37.78-0.72
48.91
Relative
1.01
6.12:+0.06
6.00=0.25
7.72:0022
1.70=0.07
2.43=0.04
2.36=0.02
16.86=11.27
Rotary (frozen)
1.42:00.88
2.46:0.399
4.58=00.0
4.97=11.79
1.55=0.31
2.15=0.22
2.53=0.08
33.54+9900
Rotary (luned)
1.00+0.00
1.70++0.05
4.07=1034
2.60:t0.11
1.08=0.02
1.90=0.22
2.55
20.87
Algebraic (seq)
10.00
L.63 1..06
2.48.10.22
=.07
10.02
2.30.
20.05 10.36
w/o init
1.00+0.00
2.36::0.68
5.18:00.10
5.72:11.23
1.45=0.00
2.20=0.00
1.75:#0.71
29.26:19.15
Algebraic (tree)
1.01
1.00
1.05++.00
1.01:0.00
1.00=0.00
1.00=0.0m
2.24
1.83+00
w/o init
10.00
1.04.0.08
1.415
1.27
1.05 10.10 1.00
2.42 L0.01
1.86.10.01
(PYL.. ()
(b) Performance results on algorithmic tree manipulation tasks.
Epoch
Scheme
<150
<300
Sinusoidal 2D Absolute
91.57:10.01
92.79.10.20
90.86:10.19
92.68
Algebraic (seq) w/o init
92. 02.66880022 24
94.59++0.15
88.93.10. 19
91.09:1:.20
Algebruic (grid) w/o init
93.13++0.38 33
94.67-t0.00 .6
92.95=t0.07
94.48-t0.18
(ACC./1) (t)
(c) Best-by-epoch top-1 accuracy scores on image recognition CIFAR-10 --..
Table 2: Experimental results and baselines across the tasks considered.
randomly initialized APE in most tasks considered, suggesting that adjusting rotoreflection angles during training is not necessarily better than adjusting rotation planes while keeping the angles fixed. Contrary all the above, a frozen ROPE weakly outperforms both tunable ROPE and an initialized APE in the neural machine translation task; likely an artifact of attention overfitting to specific positional patterns.
5 Related Work
Dense attention is by now a foundational component of various problem- and domain-general architectures. Combined with its structural indifference, this underscores the pressing need for learning strategies capable of injecting structural biases directly at the representation level. As such, positional encodings have garnered significant community attention in recent years too much, in fact, to permit an exhaustive enumeration here. An extensive survey and meta-review is provided by Dufter al. [2022] who group and rank these works on the basis of several criteria. Our work presents a universal, intuitive and formally grounded recipe that meets all these criteria: it is trainable, amenable to problem-specine and data-driven tuning; reference-udjustaie absolute and relative positional specifications; wnbounded, capable of representing enumerably infinite positions irrespective of model instantiation and/or the targeted data size; contextual, implementing a dynamic effect that varies depending token content; effective, consistently matching or surpassing
allowing both

---

baselines in the tasks considered; and, finally, efficient, exhibiting generally favorable asymptotic complexities.
We must point out that the concept of positional encodings as sequence homomorphisms has already been hinted at, first by Wang al. [2020] and later by Su et al. [2023], even if not explicitly formulated as such. Despite approaching the problem from different angles, both approaches interpret positions multiplicative, norm-preserving (rotation-like) operations. Our proposal expands upon these two, first in providing a proper algebraic framing of the problem, and second in extending the interpretation from rotations around the axes to rotations and reflections about arbitrary planes. In the case of single generator matrix (i.e., sequences), this difference turns to be non-essential, being practically neutralized by the Transformer's trainable weights. This no longer holds, however, in the case of multiple generator matrices (i.e., grids or trees), where each generator should be able to rotate and reflect different sets of planes. In that sense, algebraic positional encodings offer an appealing unifying perspective of multidimensional generalization to the aforementioned rotation based frameworks. This sentiment shared by Lim al. [2023] who, in parallel to our work, similarly advocate for positional encodings as group homomorphisms, there framed as irreducible group representations. Modulo presentation, the two approaches are variations on a common theme; theirs is technically concerned with post-hoe representation of symmetries and equivariances at a per-datum scale, whereas ours focuses on the interpretation of domain signatures the dataset scale.
More generally, algebraic manipulations are not uncommon in modern machine learning literature. The recogmition of abstract algebra as practical tool for imposing structural well bell-behaveddess has led its increased adoption as the go-to recipe for structure-informed neural architectures, largely obsoleting the inefficient and ad hoc augmentation routines of the past. This line of work can be traced back to the group equivariant convolutions of Cohen and Welling [2016], which have by now bloomed into a field of their own; see Weiler et al. [2023] for an up-to-date overview.
6 Limitations
We recognize weaknesses and limitations across three fronts. On the theoretical front, have limited our scope to simple inductive groups, consciously ignoring potential interpretations of more complex constructions. We defer this to future work. On the empirical front, having recompute positional encodings once per batch increases a model's 's temporal complexity during training. While this is barely noticeable in sequential and grid constructions, which scale logarithmically, it becomes evident when dealing with complete trees, which scale linearly and require explicit for-loops. On the epistemic front, conducted a limited of experiments, focusing primarily on replicability and fairness. We leave more exhaustive empirical comparisons on practical downstream tasks to future work or interested parties.
7 Conclusion
We have presented a theoretically motivated approach towards constructing positional encodings for variety of structures. Without any significant modification overhead, our methodology can capture sequences and their (multi-dimensional as well as multi-branching) generalizations. In doing so, it reconciles powerful but structurally oblivious models with their missing inductive biases, permitting sauucture-warr architectural refinements across a range of tasks and setups (see also Kogkalidis al. [2024] for parallel work employing the methodology in a neurosymbolic representation learning setup). Beyond that, our approach grants full control over how these biases are to be implemented, while also being amenable to adjustments and extensions. Our work indicates that generality and extensibility are not in spite of, but rather due to structural discipline and abstraction. We perceive it important step towards data-efficient, general, and transparent models of neural computation.
Acknowledgments and Disclosure of Funding
KK and VG were supported by Saab-WASP WASP via the project "Neurodynamic Programming and Reinforcement Learning" (grant 41 1025). VG also acknowledges the support from Academy of Finland (grant 342077) for "Human-steered next-generation machine learning for reviving drug design", and the Jane and Aatos Erkko Foundation (grant 7001703) for "Biodesign: Use of artificial intelligence in enzyme design for synthetic biology".
10

---

References
M. Arjovsky, Shah, and Y. Bengio. Unitary evolution recurrent neural networks. International conference machine learning, pages 1120-1128. PMLR, 2016.
J. Bernardy and S. Lappin. Unitary recurrent networks: Algebraic and linear structures for syntax. In Algebraic Structures in Natural Language, pages 243-278. CRC Press, 2022.
O. Bojar, Buck, C. Federmann, B. Haddow, P. Koehn, J. Leveling, C. Monz, Pecina, M. Post, H. Saint-Amand, et al. Findings of the 2014 workshop on statistical machine translation. In Proceedings of the ninth workshop on statistical machine translation, pages 12-58, 2014.
T. Cohen and M. Welling. Group equivariant convolutional networks. In International conference on machine learning, pages
PMLR, 2016.
P. Dufter, M. Schmitt, and H. Schütze. Position information in transformers: An overview. Computational Linguistics, 48(3)733--633 Sept. 2022. doi: 10.1162/coli_a a 00445. URL
httpss///cllanthol.og org 2022.2022222 c1-3.7.
Gage. new algorithm for data compression. The Users Journal, 12(2):23-38, 1994.
J. Gehring, M. Auli, D. Grangier, D. Yarats, and Y. N. Dauphin. Convolutional sequence to sequence learning. In International conference on machine learning, pages 1243-1252. PMLR, 2017.
A. Hassani, S. Walton, N. Shah, A. Abuduweili, J. Li, and H. Shi. Escaping the big data paradigm with compact transformers. arXiv preprint arXiv:2104 05704, 2021.
T. Janssen. Foundations and applications of Montague grammar. PhD thesis, University of Amster- dam, 2014. Originally published: April 1983 (UvA).
A. Katharopoulos, A. Vyas, N. Pappas, and F. Fleuret. Transformers are mns: Fast autoregressive transformers with linear attention. In International conference machine learning, pages 5156- 5165. PMLR, 2020.
K. Kogkalidis, O. Melkonian, and J.-P. Bernardy. Learning structure-aware representations of dependent types. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
A. Krizhevsky, G. Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Y. Li, R. Zemel, M. Brockschmidt, and D. Tarlow. Gated graph sequence neural networks. In Proceedings of ICLR' 16, 2016.
D. Lim, H. Lawrence, N. T. Huang, and E. H. Thiede. Positional encodings group representations: A unified framework. 2023.
I. Loshchilov and F. Hutter. Decoupled weight decay regularization, arXiv preprint 15100017 2017.
J. Lu, J. Yao, J. Zhang, X. Zhu, H. Xu, W. Gao, C. Xu, T. Xiang, and L. Zhang. Soft: Softmax-free transformer with linear complexity. Advances in Neural Information Processing Systems, 34: 21297-21309, 2021.
Murnaghan and A. Wintner. canonical form real matrices under orthogonal transformations. Proceedings of the National Academy of Sciences, 17(7):417-420, 1931.
M. Post. A call for clarity in reporting BLEU scores. Proceedings of the Third Conference on Machine Translation: Research Papers, pages 186-191, Belgium, Brussels, Oct. 2018. Association for Computational Linguistics. URL https: / http://wwww/////////// aclweb. org/ thtoooggooooott 6319.
R. Sennrich, B. Haddow, and A. Birch. Neural machine translation of rare words with subword units. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pages 1715-1725, 2016.

---

Shaw, J. Uszkoreit, and A. Vaswani. Self-attention with relative position representations. In Proceedings of NAACI-HILT, pages 464-468, 2018.
V. Shiv and C. Quirk. Novel positional encodings to enable tree-based transformers. Advances in neural information processing systems, 32, 2019.
J. Su, M. Ahmed, Y. Lu, S. Pan, W. Bo, and Y. Liu. Roformer: Enhanced transformer with rotary position embedding. Neurocomputinng, page 127063, 2023.
A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, t.. Kaiser, and I. Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
A. Vyas, A. Katharopoulos, and F. Fleuret. Fast transformers with clustered attention. Advances in Neural Information Processing Systems, 33:21665-21674, 2020.
B. Wang, Z. Donghao, L. Christina, Q. Li, Z. Peng. J. G. Simonsen, et al. Encoding word order in complex embeddings. In ICLR 2020- Proceedings of Eighth International Conference on Learning Representations, 2020.
Z. Wang and J.-C. Liu. Translating math formula images latex sequences using deep neural networks with sequence-level training, 2019.
M. Weiler, P. Forré, E. Verlinde, and M. Welling. Equivariant and coordinate independent convolu- tional networks. A Gauge Field Theory of Neural Networks, 2023.
C. Wu, Wu, and Huang. DA-Transformer: Distance-aware transformer. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 2059-2068, 2021.
Y. WU, M. Schuster, Z. Chen, Q. V. Le, M. Norouzi, W. Macherey, M. Krikun, Y. Cao, Q. Gao, K. Macherey, et al. Google's neural machine translation system: Bridging the gap between human and machine translation. arXiv preprint
2016.
12

---

A
Parameterizing APE
A.1
Orthogonalization
The orthogonal primitives underlying APE can be procured by matrix-cxponentiatng skew-symmetric bases. Concretely, for some cyclic group (C):
Start with an upper triangular matrix A; this matrix parameterizes the entire group. 2.
Obtain the skew symmetric B A A
Obtain the matrix exponent := expin B); the resulting matrix orthogonal, and acts as the group's generator.
A.2 Switching between APE and ROPE
In the commutative (direct sum of finitely many cyclic groups) case, it is possible to switch freely between APE and RoPE. Doing so might be useful, e.g., for initializing APE, for inspecting the learned rotoreflections post-training, or for making use of ROPE's 's memory-optimize formula in system originally trained with APE. Note that here we consider the purely real-valued version of ROPE (and APE).
pector-muliilicattin
ROPE + APE
To convert ROPE to APE for some collection of angles θ = [01,...00 On]:
1. Expand @ into rotation matrix C,
cos91 sin0
sin0 cos01
C
0
cos
sin82
0
sin02
cos02
Note: Stop here if not interested in parameterizing C.
2. Use solver to approximate the matrix logarithm of C, B = logm(C).
3. Find a matrix A such that mse( B, A - A S e.g., using a numerical optimizer. Matrix A can be used parameterize the group, cf. A.1.
APE ROPE
To convert APE to ROPE for some cyclic group (W):
1. Find the normal form W = PQPT.
Extract the angles in each block of Q: the resulting collection of angles is ROPE's θ
3.
For each attention head involved, roght-compose the Transformer's Φ(1) and (k) with P.
B Experimental Setups
B.1 Machine Translation
For machine translation experiments, we use the official dataset breakdown (including the extended evaluation set). We tokenize training and evaluation sets with MOSES, using the standard pipeline: punctuation normalization - unicode normalization -> language-specific tokenization." We apply byte-pair encoding [Gage, 1994, Sennrich et al., 2016] using the subword-nmt package." We apply 32k merges across the source and target training corpora, without truncating the resulting (shared) vocabulary (of size 35 533). Our loss term is given as the cross-entropy between the teacher-foreed predictions and the ground-true labels, smoothed by 10%. We train in distributed environment consisting of GPUs, with a batch size of 3 072 target tokens per GPU. We average gradients and update parameters once every 2 GPU iterations (or: 8 batches). We optimize using Adam with a learning rate dictated by the schedule prescribed by Vaswani et al. [2017]. We stop optimizing after 150 parameter updates or 16 hours, whichever comes first. Throughout training, we circularly store the 10 best checkpoints, ranked on the basis of dev set loss (evaluated once every 500 updates). During inference, average the 10 checkpoints into single model, and select hypotheses from a beam of width 4 and length penalty of 0.6 [Wu et al., 2016]. We report BLEU scores over the test set (newstest22 2201ttttt)))))) 4), comparing the BPE-merged and detokenized output against the raw references using sacrebleu [Post, 2018].
http://w.w...o.eeeeoe///eeeeeeee "See https://github wwtp://eerrcch/suuuooooooooo "Signature: nrefs: case: ic I nn tok: 13a smooth:exp version:2 2.2
"See
13

---

Experiment/ Value
Parameter
NMT
Transduction
Image
Convolution Size
(3.3)
Convolution Stride
Embedding Size
512
512
256
Feedforward Size (enc)
2048
512
512
Feedforward Size (dec)
2048
1024
Feedforward Activation
ReLU
ReLU
GELU
# Layers (enc, dec)
6)
(2,2)
(7, 0)
# Heads
8
8
4
Norm
LayerNorm Post
LayerNorm
LayerNorm
Norm Position
Pre
Pre
Table 3: Hyperparameter setups, grouped by experiment.
B.2 Synthetic Transduction
Tree Task Descriptions The tree copy task morally identical to its sequential version the tree structure (and its positional specification) is practically confound.
In the tree rotation' task, the output tree is the result of recursively right-rotating all subtrees of the input. The task is challenging but purely structural, in the sense that its resolution requires no real interaction between content and position.
For the algebraic expression reduction task, we consider input trees that specify a complex expression from the cyclic group C3, and task the model with producing the result of a single reduction step (i.e., reducing all subtrees of depth I into a leaf). This time around, the model has to identify reducible subtrees, match operators to their argument and collapse the three into single node depending on their content.
The tree operations task, finally, combines the aspects of the other three, requiring content-based addressing, structure manipulation and dynamic semantics resolution. Concretely, we generate an input tree consisting of unique nodes, and randomly select one of its subtrees as well as one of four operators. We then construct a deeper tree, where the new root corresponds to the chosen operator, its left branch corresponds the numerical index of the selected subtree, and the right branch is the original tree in its entirety. The model is then tasked with producing the correct output given this combination of an operator, a tree, and an index. We consider four operations: extraction (i.e., return the indexed subtree), flip-extraction (i.e., return the indexed subtree, rotated), truncation (i.e., return the full tree with the indexed subtree removed) and no-op (i.e., return the full tree as-is, ignoring indexing).
Hyperparameters For all synthetic tasks, we generate disjoint train, dev and test sets of sizes 600, 2 000 and 2 000. We train small Transformer model, optimizing with AdamW [Loshchilov and Hutter, 2017] for 400 epochs and a batch size of 64, using linear warmup cosine decay schedule. For the sequential tasks, we populate the datasets with words of random lengths from (100,, 10) and a vocabulary size of 20 (to ensure token repetition and diffuse the possibility for leaning on content-based addressing). For the tree tasks, we populate the datasets with non-uniform trees of random depths sampled from (7, 1). For the tree-ops task, exceptionally, we set the vocabulary size 128 as have enough unique nodes to allow content-based addressing.
When using a positional encoding scheme that requires fixing the size of the structure being modeled (i.e., the Tree, Relative, and Absolute schemes), we fix it at approximately the maximum training size, practically ensuring the most stringent comparison.
In all experiments, we share source and target embedding weights between both the encoder-decoder embedding layers, and the decoder's classification head.
B.3 Image Recognition
For our image recognition experiments, we largely rely on the setup of Hassani et al. [2021]] Concretely, we apply a small-step "tokenizing" convolution on the input image, downsample the result with max pooling and flatten the result into sequence. After we pass the sequence through the encoder, we apply a global soft attention [I. et al., 2016, inter alia] (rediscovered by Hassani al. [2021], there dubbed "sequence pooling")) to aggregate into a single vector prior to applying the classifier. To attain competitive scores, we apply standard CIFAR-10 10 data augmentations and
14

---

aggressive regularization: 10% attention weight dropout, stochastic depth of 10% for each consecutive layer, and a weight decay of 3 10-2 The above settings and the hyperparameter setup taken without modification from Hassani et al. [2021].
15

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We carefully summarize our contributions and refrain from making any claims that cannot theoretically empirically support.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We have a dedicated limitations section ($6), and openly and explicitly discuss algorithm complexity and experimental scope in the relevant sections.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best
16

---

judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Our algebraic connections make no assumptions and fully explicit in their presentation. The equivalence with ROPE clarifies all assumptions it makes.
Guidelines:
The answer NA means that the paper does not include theoretical results.
the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Answer: [Yes]
Justification: We provide the reviewers with both an extensive appendix detailing our experimental setup, and the code used to implement our methodology and conduct our experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
17

---

(a) If the contribution is primarily algorithm, the paper should make it clear how to reproduce that algorithm.
If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c)
If the contribution is either be way to access this model for reproducing the results or way to reproduce the model (c.g.. with an open-source dataset instructions for how to construct the dataset).
model (e.g., a large language model), then there should
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
Yes - see answer above. Our training scripts are provided virtually unchanged.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co for more details.
sublic/guides/ http://oodSuummmsiiooooooooo
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to reproduce the results. See the NeurIPS code and data submission guidelines (https: hhips.cc/publ.... htwbbbl///h/ dewggeiddeeeeeubbmeeee ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question:
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Yes, see above.
Guidelines:
The answer NA means that the paper does not include experiments.
18

---

The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We take extra care to conduct our experiments openly and transparently as deliver statistically sound results and draw solid conclusions. We repeat all experiments multiple times, and report means and 95% confidence intervals. For each experiment, we visually mark all models that overlap with the best performer the category.
Guidelines:
The answer NA means that the paper does include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [No]
While we do report hardware infrastructure, do report memory con- sumption or clock times. With the exception of machine translation, our experiments are moderately cheap to run, requiring specialized hardware other than GPU accelaration.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
19

---

The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: http://urrr....cooooo//////tttna
Answer: [Yes]
Justification: Checked and done.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We do, albeit briefly. We do not see possible negative implications.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
20

---

Justification:
We perceive risks that would require safeguards of any kind.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
We cite all software libraries and datasets use, and comply with their licenses.
Justification:
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g.. website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paper swi thcode. com/ hom/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [No]
Justification: While do provide reference implementations, do not them assets per se, neither do we hand them out as ready-to-use integrations.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/codeemmodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
21

---

The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: No human subjects were involved in this study.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: See above.
Guidelines:
The answer NA means that the paper does involve crowdsoureing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
recognize that procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
22


Reviews:
[{"review_id": "X6m9G0f9uk", "reviewer": "Reviewer_xNaW", "summary": "This paper presents a framework to derive positional encodings based on algebraic specifications for various structures such as sequences, grids, trees, and their compositions. The approach is evaluated on multiple training tasks involving sequence, image, and tree inputs, demonstrating performance that is comparable to or better than existing positional encodings.", "questions": "Is there any impact on the inference times? It is not clear from the description how computationally hard it is to compute the different algebraic encodings and the size of the encodings compared to the existing encodings. \n\nHow does the complexity of the encoding scale with the size of the input?", "limitations": "Yes, the authors discuss the limitations of this work.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "- Unlike many papers that focus on a single type of positional encoding for a specific data structure, this paper offers a unified framework applicable to multiple structures. This is a significant contribution as it provides a versatile tool for handling diverse data types.\n\n- The experimental results are promising, particularly with algebraic (tree) and algebraic (grid) encodings significantly outperforming existing methods. \n\n- The paper also discusses the applicability of the framework to other structures beyond sequences, grids, and trees. This is definitely very promising and looking forward to future directions in this space.", "weaknesses": "One thing to further improve the paper is to have some experiments with compositional structures. For example, the authors can consider some table based tasks that combine grid with time series data.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for your thoughtful and constructive review.\n\n---\n\nWe are very glad you found our framework interesting and the results promising, and that you appreciated the potential for future directions.\n\nWe acknowledge your remark about (more complex) compositional structures. This is something we have discussed also internally, but ended up refraining from, for one main reason: the comparative evaluation would require us to make some subjective design choices on the \"competing\" frameworks (because they are not meant to handle such structures). This would give room for a critical counter-argument along the lines of \"why did you try this and not that\", which could easily derail the discussion into an exhaustive evaluation of *how* and *how not* to use foreign works properly.\n\nTo answer your question regarding inference times: assuming that, after training, positional encodings are precomputed and stored in a buffer (as they should), the computational cost is just an extra two matrix-vector multiplications per transformer layer: between queries/keys and their respective encodings.\n\nThere's two gotchas unique to the tree case:\n1. The number of unique positions grows very fast for dense and large trees, which might necessitate dynamically computing representations *given* a tree. Practical workarounds would be to store most common/shallow positions and only compute rare/deep ones as needed.\n2. If the tree is sparse (i.e., not all of its positions are filled), building up the matrix of positional encodings will require an additional indexing step that pieces together all of the occupied positions (think like the forward pass of an embedding layer).\n\nFor the sake of clarity and transparency, we report **inference times** for the test set of WMT14 under the same settings and hardware for all sequential encoding models below (average of 3 repetitions):\n\n| Sinusoidal | Absolute | Relative | Rotary | Algebraic |\n|------------|----------|----------|--------|---------|\n|     105.1     |    108.1 | 112.9     |   127.9     |   112.7   |\n\nEvidently, inference time is only marginally affected, and is in fact better than RoPE; the latter uses a vector-vector formulation that is optimized for memory efficiency, but requires additional slicing operations. Inference in the remaining experiments is not auto-regressive so there's no insights on asymptotic behavior to gain from them. \n\nWhen it comes to **memory complexity**, and assuming all encodings are precomputed (rather than dynamically generated), the parameter count scales quadratically with attention dim, and linearly with number of *unique* positions in the ambient structure. Additionally, there's a linear dependency on number of attention heads and transformer layers, assuming no weight sharing. In our experimental setup, we share positional encodings across transformer layers but not across attention heads.\n\n---\n\nThanks again, and we hope this answers your questions.", "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": "", "extra_scores": {}}, {"review_id": "3uc9xzWE1D", "reviewer": "Reviewer_8qDc", "summary": "This paper provides a group-theoretic framework to generate positional encodings which reflect and preserve the underlying algebraic structure of the data by instantiating homomorphisms between a syntactic denotation of the data structure and a semantic interpretation using orthogonal matrices.  The authors demonstrate that their methodology is able to encode a variety of structures, including sequential data,  grids, and trees.  They demonstrate that in the case of sequential data, they recover the rotary positional encoding scheme.  The authors provide a thorough empirical evaluation of their framework against multiple baselines, demonstrating the efficacy.", "questions": "I have no specific questions.", "limitations": "The authors have sufficiently addressed the limitations of the work.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- The paper is excellently written and provides many fascinating group-theoretic insights into how to effectively encode structured data for use in a language model.\n- The work is original in that it provides a universal group-theoretic framework for generating encoding schemes for various positional encodings that reflect various structural forms of the data.  It demonstrates how their framework subsumes some existing works, such as the rotary encoding scheme of Su et al.\n- I believe the framework is a very important contribution to the sound and systematic construction of encoding schemes that preserve the structure of various data types, and that the framework facilitates lots of interesting future work.", "weaknesses": "- I believe it would benefit the paper to provide a few explanations of the empirical results regarding when other encoding schemes outperform the algebraic encoding or achieve the same scores (e.g. why might this be the case that rotary outperforms algebraic in row 1 of Table 2a) and why might relative, rotary, and algebraic have the same performance on the copy task in Table 2a) ?).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for your feedback. \n\n---\n\nWe are thrilled that you found our work insightful and original, and that you consider it an important contribution to the field; this means a lot.\n\n\nYou’re absolutely right that we did not provide an in-depth explanation of the findings in Table 2. We plan to address this in a future iteration or the camera-ready version. For clarity, here are the main takeaways:\n\n1. The (sequence) copy task is somewhat trivial—it mainly tests if the PE system learns position-based addressing without relying on content. This is essentially a sanity check, and all systems pass it except for Absolute (Sinusoidal performs only marginally worse than perfect). We hypothesize that Absolute lags behind due to overfitting: it assigns a unique representation to each position, which over-parameterizes the system without offering any real inductive biases.\n2. This hypothesis is supported by the tree copy experiment. When teaching a transformer to copy-paste, the structure of the content becomes a confound. Because structure is a confound, point-wise ad hoc position representations are likely to lead to overfitting. Indeed, Absolute fails to provide a sufficiently general position representation strategy and achieves the worst performance once more.\n3.  We highlight in red the numbers corresponding to the best-in-class setups and underline those within a 95% confidence margin of the best-in-class. Apart from random variations, we consider red and underlined setups as equally effective. Notably, Rotary and Algebraic are closely aligned in the sequential case (as expected). The slight advantage of Rotary in WMT and the preference for Algebraic elsewhere might be due to an implicit **selection bias** in the hyper-parameters of Rotary. We suspect that RoPE authors conducted iterative experiments, which could make it implicitly tuned for this specific task and dataset. In contrast, our experiments are not fine-tuned with a specific benchmark in mind; our contribution is first and foremost theoretical, and the experiments serve as a first empirical proof-of-concept meant to showcase the methodology's strength rather than compete in a *specific* benchmark.\n\n---\n\nWe hope this clarifies your question. Thank you once again for your review and engagement.", "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": "", "extra_scores": {}}, {"review_id": "DJZ8RnqwRV", "reviewer": "Reviewer_F3X8", "summary": "This study proposes a generalized positional encoding for sequential, tree, and grid-structured data. The high-level view of encoding is algebraically framed, while the implementation of encodings remains simple; roughly, positions are embedded in linear subspaces spanned by the column space of orthogonal matrices. Numerical experiments show its empirical superiority over baseline methods on diverse tasks.", "questions": "I'd like the Authors to answer the weaknesses raised above. Plus, \n- I'm interested in the case of trainable positional encoding (i.e., position embedding). In image classification tasks, it is also common to use position embedding, which learns a proper encoding over the training process (mentioned in [line 269]?). The proposed algebraic encoding can be readily made trainable, and it'd be interesting to see the impact of trainability on performance.", "limitations": "Limitations are adequately presented. For the potential improvements, see Weakness and Questions.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- This study presents a clear, high-level (algebraic) view of positional encoding, covering various settings. \n- The implementation of the proposed encodings is simple and, thus, accessible to a wide range of practitioners. \n- The empirical performances of the proposed encodings are better than baseline methods on most tasks. The gain is very evident for several tasks.", "weaknesses": "**Major comments**\n\nThe main weakness of this work is that it does not offer why the proposed method works better than the other baseline methods. Section 3.2 presents the equivalence of RoPE and the proposed (sequential) encoding, but the experimental results given in Table 2 are not equal. Particularly, (b) shows there is a noticeable performance gap between Algebraic (seq) and Rotary. The discussion in Section 4.4 is too simple. One possible reason is the difference in the distribution of $\\theta_i$. In RoPE, the angles are selected from low to high accordingly, while those of a random orthogonal matrix may be different (probably concentrating around some value). \n\nI suggest that the Authors remove Table 1 and instead include more elaboration on the potential difference between RoPE and the proposed encoding and experimental results. \n\n**Minor comments**\n- [line 117] Unfamiliar notation $W^p\\ :\\ \\langle W \\rangle$; possibly  $W^p \\in \\langle W \\rangle$? \n- [line 120] Unfamiliar notation $[W^0\\cdots W^p]$; a little confusing with a matrix product.\n- [line 178] Comma missing; $\\langle W_1, W_2, \\ldots, W_L\\rangle$. See also [line 140].", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Greetings, and many thanks for an insightful review.\n\n---\n\nWe are pleased that you appreciated the clarity of the presentation and the simplicity of the implementation.\n\nYour questions and remarks raise valid points, but we believe there may be a few minor but crucial misunderstandings. We will address these below.\n\n> `... why the proposed method works better than other baseline methods`\n\nOur method parameterizes the entire ambient space (e.g., an infinite sequence, grid, or tree) using a few primitives and their compositions. What this means in practice is that we have a smooth way to obtain functional representations that **consistently** relate positions to one another. This is arguably better than ad hoc encoding schemes -- not just for interpretability or epistemic justification, but also (as the resuts suggest) for concrete performance, at least in the settings investigated. Put simply, we think it works better because it should work better.\n\n> `...equivalence of RoPE and the proposed (sequential) encoding, but the experimental results given in Table 2 are not equal..`\n\nThis is a very valid point, and one raised also by reviewer 8qDc, albeit in a different context. There are two different things to consider:\n1. Algebraic positional encodings *theoretically* encompass Rotary ones. We explain why and when in Section 3.2.\n2. That said, the two approaches are *implemented* differently, and are subject to different training dynamics. RoPE uses a fixed distribution of angles (as you correctly point out). Why \"*these* angles specifically\" is subject to interpretation; we hypothesize that the decision is the product of implicit task- and dataset-specific tuning (see also our response to reviewer q8Dc). This might also explain the minimal but evident disparity in performance across tasks. Our system parameterizes the rotation angles in the orthogonal primitives, and allows them to change during the course of training -- this might indeed have a significant effect on the training process (and therefore final performance). A minor remark here is that we do not opt for `random` angles, but rather initialize our primitives to be close to Identity (see Appendix A.1).\n\n> `The discussion in Section 4.4 is too simple.`\n\nWe agree. We plan to extend the discussion with relevant remarks and hypotheses if/when given extra space.\n\n> `...trainable positional encoding`\n\nThere seems to be a bit of confusion here and the blame is likely on us. The encodings we use **are** actually trainable (see lines 26, 153, 295, Appendix A.1, *i.a.*). We will make this more explicit in a future version.\n\n> `..unfamiliar notation`\n\nWe borrow the notation `x : A` from logic/functional programming to denote that `x` is of type `A`, or a member of set `A` if you will. We will add the missing commas in the set builder notation, thank you.\n\n---\n\nPlease let us know whether this addresses your concerns. Thanks again!", "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": "", "extra_scores": {}}, {"review_id": "ikMp9jJdZq", "reviewer": "Reviewer_18aa", "summary": "Current techniques for specifying relative position encodings are often ad-hoc or clearly fit to specific problems. This paper attempts to resolve this by creating theoretically grounded positional encodings via describing the underlying algebraic structure of the positions in the input as a group and then finding some subgroup of the group of invertible matrices that is isomorphic to the position group. This results in more effective positional encodings than current approaches.", "questions": "Is there any connection between these encodings and the sinusoidal encodings often used for absolute positional encoding?", "limitations": "Limitations are adequately explained.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 4, "strengths": "Reconstructing the existing approach towards relative positional encodings for sequences is a strong sign of the effectiveness of this approach.\n\nEvaluation is done fairly with “same budgets (both memory and time).” The empirical results are strong.", "weaknesses": "Major clarity issue: while the concepts of a group and group homomorphism are both well explained, the specific reasoning behind wanting to multiply elements in an dot product attention with elements of a matrix group corresponding to the algebraic structure of the underlying data remains highly unmotivated. More explanation provided for this would substantially help the clarity and motivation of the paper. I believe lines 76-79 are attempting an explanation along these lines, but the reference was too oblique to be easily understood by readers who have not yet read the rest of the paper (at least it was to me).\n\n120: “can asymptotically be obtained using O(⌈log2(p)⌉) matrix steps” requires a clear explanation that this is about computing a single embedding\n\nMinor issues\nClarity: On line 49, it might be easier to understand if you write A(p_x X, p_y Y) has the same evaluation as p_x A(X, Y). I was a bit confused at first when reading it.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Greetings, and thank you very much for your review.\n\n---\n\nWe appreciate your feedback and are glad you saw merit in our approach. We will try to address your concerns below.\n\n>  `wanting to multiply elements ... remains highly unmotivated`\n\nWe hear your criticism. The multiplicative approach is the de facto standard ever since RoPE. We see our paper as basically (i) a necessary theoretical justification of why this really is appropriate, and (ii) a guideline for how to go from here. Here's a brief and condensed explanation:\n1. A positional encoding $\\mathrm{PE}$ is a function $\\mathrm{PE} : \\mathrm{position} \\to \\mathrm{content} \\to \\mathrm{vector}$. In words, given a position (in the ambient space) and a content-vector, it returns a position-and-content-vector. The additive approach suffers from a key conceptual limitation: it is commutative (there's no separation between content and position). That is, content and position are mixed as if being \"on an equal basis\". The multiplicative approach is making the functional dependency clearer. Given a position, you have a linear map, *i.e.,* a function, from content vectors to content-and-position vectors. As you smoothly change position on the ambient space, so does the *function*. The change is such that the effective difference between two positions (and their functions) depends not on what the positions are, but what the relation between them is (where \"relation\" is more than just \"distance\").\n2. Matrices and linear algebra are a folklore target for groups in representation theory. Upon noticing that the structures we are mostly working with are actually just groups in disguise, matrices make for a very natural modeling choice -- you can't preserve these really meaningful properties with vectors. But now you're left with a positional representation that's a matrix, and a content representation that's a vector. And since the rest of the model works on vectors, you can't but end up with a positions-as-functions interpretation.\n\nThe ideas above are extensively detailed in Section 3. So, to put things in context, we sort of start from the fact that multiplicative positional encodings *work*, and we seek to provide insights on *why they do*. Because of that, we didn't think it necessary to explicitly motivate them against additive ones.\n\n\n> ` 120: “can asymptotically be obtained using O(⌈log2(p)⌉) matrix steps” requires a clear explanation that this is about computing a single embedding`\n\nThis is incorrect -- it takes $O(\\lceil \\mathrm{log}_2(p) \\rceil)$ steps to obtain **all** embeddings; let us explain how. Suppose you have a matrix $W$ of size ($n$, $d$) where $W_i$ contains the representation of the $i$-th position. The matrix $W' := W_nW^\\top$ is of size ($n$, $d$), where $W'_j$ contains the representation of position $n+j$. Concatenate $W$ with $W'$ to obtain a matrix of size ($2n$, $d$) containing the representations of positions 1 to 2n, and repeat the same process. By induction, after k vector-matrix multiplications you will have a matrix of size ($2^k$, $d$).\n\n--- \n\n\nPlease let us know if that helps. Many thanks, again.", "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": "", "extra_scores": {}}, {"review_id": "M3iRYkYozZ", "reviewer": "Reviewer_PGKE", "summary": "The paper presents a groundbreaking positional encoding strategy named  Algebraic Positional Encodings for Transformer-style models, The paper offers a versatile mapping technique that translates the algebraic specifications of a domain into orthogonal operators. By doing so, it preserves the fundamental algebraic characteristics of the source domain, ensuring that the model maintains its desired structural properties. The author also conducts experiments to validate the performance of Algebraic Positional Encodings.\n\n--------------------------------------------------------------------------------------------------------------------------------------------------------------------------\nUpdate 08/Aug/2024: I increase the score from 5 to 6 and the confidence from 2 to 3, after checking author rebuttal.\n\n--------------------------------------------------------------------------------------------------------------------------------------------------------------------------\nUpdate 08/Aug/2024: I increase the confidence from 3 to 4, after checking experiments of trainable RoPE.", "questions": "please see the above weakness.", "limitations": "Yes, the authors have discussed the limitations.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper proposes Algebraic Positional Encodings, which provide a flexible mapping from the algebraic specification of a domain to an interpretation as orthogonal operators.\n* The paper has experiment results to prove the effectiveness of Algebraic Positional Encodings", "weaknesses": "* The paper is relatively hard to understand. If possible, could the author provide the pseudo-code or python code of the proposed Algebraic Positional Encodings? Or is there any other way that may help the reader to understand the implementation of the method?\n\n* Why Algebraic (grid) performance is often better than Algebraic (seq)? If possible, could the author explain it?\n\n* What is the length extrapolation performance of Algebraic Positional Encodings? For example, what is the performance of Algebraic Positional Encodings when the training length is smaller than the validation length, such as when training on length 128 and testing on length 256? One potential code base is https://github.com/google-deepmind/randomized_positional_encodings/tree/main. And author may also choose other potential base, as long as it can conduct the length extrapolation experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Warm greetings, and thank you for your review.\n\n---\n\n> `The paper is relatively hard to understand.`\n\nWe are very sorry to hear. To summarize, what we we are basically saying is that:\n1. The properties of several common I/O structures in ML literature can be perfectly described using elementary group theory.\n2. Group theory offers insights on how to represent elements of these structures as matrices and linear maps.\n3. Using these representations as general recipe for structure-aware positional encodings, we arrive at various generalizations of RoPE, which is the mostly widely adopted strategy and the current state of the art.\n4. Our results suggest that indeed this seems to be working not just in theory, but also in practice.\n\nWhat exactly gave you a hard time? Is there something we can perhaps clarify?\n\n> `could the author provide the pseudo-code or python code`\n\nWe have already made **all of our code** available for review. Please check the supplementary material. We'd be happy to provide clarifications if/as needed.\n\n> `Why Algebraic (grid) performance is often better than Algebraic (seq)?`\n\nAlgebraic (grid) treats the image as a grid of distinct ($x$, $y$) positions, where up/down and left/right transitions are kept semantically separate. Algebraic (seq) flattens the image into a sequence, which obfuscates the semantics: a right(/left) transition could signify **either** the immediately adjacent pixel to the right(/left), **or** the first(/last) pixel of the next(/previous) image row. This is **not a weakness** but the **intended behavior**; we are precisely arguing for structure-aware positional encoding schemes.\n\n> `... length extrapolation ...`\n\nGreat question! We don't expect astonishing extrapolation results out-of-the-box. That said, all insights that apply for RoPE should carry over to our approach -- see for instance *rerope*, *yarn*, *position interpolation*, *etc*. For the sake of transparency, we present length extrapolation results for the synthetic sequence tasks below. We do training and model selection on sequences of length 100±7, and evaluate on sequences of length 200±7. We report PPL scores (so less is better).\n\n| Task     | Sinusoidal | Absolute | Relative | Rotary | Algebraic |\n| ---------|------------|----------|----------|--------|---------|\n| Copy     |  18.9      | 22.3     | 1.0      | 1.0    | 1.0     |\n| Reverse  |  18.3\t| 18.3\t   | 4.5      | 14.6   | 4.8     |\n| Repeat   |  18.1      | 22.2     | 21.8     | 1182.7 | 262.3   |\n\nWe see all models struggling with the length extrapolation of all tasks. Exceptionally, Algebraic, Rotary and Relative still achieve perfect performance in Copy. Algebraic and Relative (but *not* Rotary) still remain competitive in Reverse, and all three diverge in Repeat (where basically the length extrapolation required of the decoder is $\\times 4$ of the input).\n\n---\n\nHope our response satisfactorily addresses your concerns. Otherwise, we'd be happy to engage further.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: At this point transformers have been applied to a wide variety of data, which frequently have some underlying structure.  E.g. 1D (sequence), 2D (image), or 3D (video) cartesian spaces, as well as syntax trees (code).  This paper addresses an important gap in the literature, namely how practitioners should systematically design position encodings to handle these spaces, or new spaces that might arise.  The authors base their analysis in group theory, and show how position encodings for a variety of spaces can be constructed from orthogonal matrices.  As a bonus, the widely used ROPE encodings can be realized as a special case of the more general construction.

All of the reviewers agreed that this was important theoretical work with practical applications, and was well-presented.  Several reviewers commented that the experimental evidence was not as strong as the theory.  I concur with this opinion, but the experiments are strong enough to make this paper a clear "accept".  I hope the authors make a stronger experimental case in future work.  The technique is also somewhat difficult and/or costly to implement for trees, which IMO is the biggest weakness. 

I am recommending this paper for a spotlight because I think it will be of immediate practical interest to a wide variety of NeurIPS attendees.  I am tempted to recommend it for an oral, but I don't think the experimental evidence quite justifies that.
Decision: Accept (spotlight)