Algebraic Positional Encodings

Warm greetings, and thank you for your review.

The paper is relatively hard to understand.

We are very sorry to hear. To summarize, what we we are basically saying is that:

1. The properties of several common I/O structures in ML literature can be perfectly described using elementary group theory.
2. Group theory offers insights on how to represent elements of these structures as matrices and linear maps.
3. 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.
4. Our results suggest that indeed this seems to be working not just in theory, but also in practice.

What exactly gave you a hard time? Is there something we can perhaps clarify?

could the author provide the pseudo-code or python code

We 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.

Why Algebraic (grid) performance is often better than Algebraic (seq)?

Algebraic (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.

... length extrapolation ...

Great 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).

We 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).

Hope our response satisfactorily addresses your concerns. Otherwise, we'd be happy to engage further.

Following your and reviewer F3X8's suggestions, we ran a series of additional experiments where we seek to account for (i) trainability and (ii) initialization. We find that, on average,

• A frozen APE outperforms a frozen RoPE.
• A frozen APE outperforms a trained APE.
• A trainable RoPE outperforms a frozen APE.
• A trainable APE mimicking the initialization strategy of RoPE outperforms everything else.

Here's the new and old results over the sequential copied verbatim from our response to F3X8. APE: Algebraic (seq), init: RoPE-like initialization, train: trainable. [b]: breadth-first, [d]: depth-first.

So to summarize: APE[init, train] > RoPE[train] > APE > APE[train] > RoPE

In any case, many thanks for encouraging us to do these additional experiments. These empirical findings have helped us consolidate the effect of training and initialization for both RoPE and APE, as well as further reinforce the empirical strengths of Algebraic encodings.

Greetings, and thank you very much for your review.

We appreciate your feedback and are glad you saw merit in our approach. We will try to address your concerns below.

wanting to multiply elements ... remains highly unmotivated

We 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:

1. 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").
2. 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.

The 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.

120: “can asymptotically be obtained using O(⌈log2(p)⌉) matrix steps” requires a clear explanation that this is about computing a single embedding

This 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$).

Please let us know if that helps. Many thanks, again.

Both are fair points. We will include the appropriate remarks as suggested.

Greetings, and many thanks for an insightful review.

We are pleased that you appreciated the clarity of the presentation and the simplicity of the implementation.

Your questions and remarks raise valid points, but we believe there may be a few minor but crucial misunderstandings. We will address these below.

... why the proposed method works better than other baseline methods

Our 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.

...equivalence of RoPE and the proposed (sequential) encoding, but the experimental results given in Table 2 are not equal..

This is a very valid point, and one raised also by reviewer 8qDc, albeit in a different context. There are two different things to consider:

1. Algebraic positional encodings theoretically encompass Rotary ones. We explain why and when in Section 3.2.
2. 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).

The discussion in Section 4.4 is too simple.

We agree. We plan to extend the discussion with relevant remarks and hypotheses if/when given extra space.

...trainable positional encoding

There 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.

..unfamiliar notation

We 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.

Please let us know whether this addresses your concerns. Thanks again!

Thank you for the rebuttal.

Insights

I understand the proposed method has a degree of freedom compared to the ad-hoc ones, and the experiments show better performance empirically. My questions were about the (theoretical and empirical) insights of the proposed positional encoding.

Having more degrees of freedom does not always mean better. That's why ad-hoc positional encodings have been used rather than position embedding, where position vectors are randomly initialized and trained over training. Let's focus on the sequential data, not trees or grids. The proposed encoding method, in this case, is conceptually close to the RoPE with a little more degree of freedom.

we have a smooth way to obtain functional representations that consistently relate positions to one another.

Does it also claim that the proposed method is consistent, but RoPE is not? I assume not (i.e., both are consistent). The better empirical results presented in the experiments indicate that the proposed encoding acquires a better position representation. I'd like the authors to provide any insights obtained from the comparison between the RoPE and the position representation acquired by the proposed method. This also relates to my mention of the distribution of $\theta$. The impact on the training process, as the authors mentioned, is also an interesting point.

Trainability

If the proposed encoding is tested with trainable vectors, then it seems to be fairer to make other position encoding methods trainable in a straightforward way. In addition, from section 3, the proposed method should work without trainability (and trainability makes it better). The contributions of trainability should also be of interest to readers.

Notation

Personally, I don't think that logic/functional programming notation is very common among most people interested in positional encoding, from researchers to practitioners. I suggest the authors define it or replace it with reader-familiar notations to maximize the impact of the paper.

Apologies for the delay, and thank you for your patience.

angles and periodicity become implicit

Intuitively, RoPE optimizes over trigonometric functions, the derivatives of which are also trigonometric functions, which are (i) not monotonic and (ii) periodic. This should, in theory at least, pose optimization issues. In contrast, APE optimizes over (parameterized) orthogonal matrices, the derivatives of which should be better behaved.

insights

We have conducted the experiment you requested (i.e., turning RoPE trainable naively and, vice versa, freezing APE). To our dismay, we found that:

• RoPE diverged only twice across experiments.
• In most cases, a frozen APE outperformed a trained APE.
• In most cases, a trained RoPE outperformed a frozen APE.

To provide an empirical correspondence between RoPE and APE, as requested, we then devised a back-and-forth algorithm between the two in the sequential case. We detail the process below.

Parameterizing APE

First, our parameterization of orthogonal primitives follows the standard matrix exponentiation trick on skew symmetric matrices:

1. Start from an upper triangular square matrix $A$. (your trainable parameter)
2. Obtain a skew symmetric $B := A - A^\top$.
3. Take the matrix exponent $C := e^{B}$. $C$ is orthogonal.

RoPE to APE

To go from RoPE to APE:

1. Start from a sequence of RoPE angles $\Theta := [\theta_1, \theta_2, \theta_3, \dots, \theta_n]$.
2. Block-diagonalize $\Theta$ into

3. Stop here if not interested in parameterization. Otherwise, obtain the matrix logarithm of $C$, $B:= \mathrm{log}(C)$ using a numerical solver.
4. Find $A$ such that $\mathrm{MSE}(B, A - A^\top)$ is minimized. $B$ is not positive-definite so it does not admit a Cholesky decomposition -- this means you have to use an iterative approximation. We find it's easy to obtain one with minimal error within seconds using gradient-based optimization.

APE to RoPE

To go from APE to RoPE (this is a practical variant of what's described in Section 3.2)

1. Start from orthogonal matrix $C$.
2. Perform the polar decomposition $C = UP$. Since $C$ is invertible, $U$ is unique, and denotes a rotation/reflection along the axes specified by $P$. For $P \equiv 1$, $U$ is block-diagonal and corresponds to $C$ above (i.e. the absolute angles of its eigenvalues correspond to $\Theta = [\theta_1, \theta_2, \dots]$).

Results

Besides explicating the relation between APE and RoPE, this back-and-forth allows us to do something more: we can now initialize APE with a parameterization that produces the angles used by RoPE! Doing so allows us to examine the effects of trainability in juxtaposition with initialization. We find that in almost every setup a trainable APE initialized as RoPE outperforms all other models. Together, these results empirically confirm both your claim that RoPE can do better if trained, and our claims that (i) gains are also due to initialization, and (ii) RoPE has been "tuned" offline.

For the sake of comparison, we summarize all results in the table below. APE: Algebraic (seq), init: RoPE-like initialization, train: trainable. [b]: breadth-first, [d]: depth-first. We do not include the 2 diverging RoPE runs so as not to obfuscate the results.

So to summarize: APE[init, train] > RoPE[train] > APE > APE[train] > RoPE

To us this seems like a very interesting find. Does this help answer your questions?

In any case, many thanks for encouraging us to do these additional experiments. These empirical findings have helped us consolidate the effect of training and initialization for both RoPE and APE, as well as further reinforce the empirical strengths of Algebraic encodings.

Many thanks for your thoughtful and constructive review.

We are very glad you found our framework interesting and the results promising, and that you appreciated the potential for future directions.

We 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.

To 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.

There's two gotchas unique to the tree case:

1. 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.
2. 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).

For 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):

Evidently, 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.

When 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.

Thanks again, and we hope this answers your questions.

Thank you so much for your feedback.

We 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.

You’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:

1. 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.
2. 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.
3. 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.

We hope this clarifies your question. Thank you once again for your review and engagement.