Myosotis: structured computation for attention like layer

Evgenii Egorov, Hanno Ackermann, Markus Nagel, Hong Cai · 2025

Read Myosotis: structured computation for attention like layer by Evgenii Egorov, Hanno Ackermann, Markus Nagel, Hong Cai (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-20503.txt.

Introduction

Attention layers compare every element of a sequence with every other, so their cost grows quadratically. Evgenii Egorov and three co-authors propose a structured alternative called Myosotis in a 2025 arXiv paper. Existing escapes either drop most comparisons through sparsity or force the sequence through a recurrent state model. Each escape gives something up. The authors aim to keep the advantages of both.

Their algorithm rests on the efficient inversion of tree-structured matrices. That structure lets pairwise interactions be handled without materializing the full quadratic cost. The design targets the same sequence-to-sequence role that attention plays inside modern networks. The paper is brief and presents the algorithm as a foundation. Efficiency claims are framed at the level of the method's design, awaiting the fuller benchmarking the authors leave open.

Catalog record

CREATOREvgenii Egorov, Hanno Ackermann, Markus Nagel, Hong Cai
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE38 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-20503

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Myosotis: structured computation for attention like layer Thanks: Qualcomm AI Research is an initiative of Qualcomm Technologies, Inc. Evgenii Egorov, Hanno Ackermann, Markus Nagel, Hong Cai Abstract Attention layers apply a sequence-to-sequence mapping whose parameters depend on the pairwise interactions of the input elements. However, without any structural assumptions, memory and compute scale quadratically with the sequence length. The two main ways to mitigate this are to introduce sparsity by ignoring a sufficient amount of pairwise interactions or to introduce recurrent dependence along them, as SSM does. Although both approaches are reasonable, they both have disadvantages. We propose a novel algorithm that combines the advantages of both concepts. Our idea is based on the efficient inversion of tree-structured matrices. 1 Introduction Modeling interactions in high-dimensional objects efficiently has been a long-standing challenge in machine learning, particularly when short-range dependencies are insufficient and long-range interactions must be captured. The Transformer architecture vaswani2017attention was a breakthrough in addressing long-range dependencies, but it suffers from quadratic computational complexity with respect to input length. To mitigate this, numerous efficient Transformer variants have been proposed, exploiting sparsity or hierarchical structure. Examples include BigBird zaheer2020bigbird , Longformer beltagy2020longformer , Performer choromanski2021rethinking , and Swin Transformer liu2021Swin , each designed to handle longer sequences or high-dimensional inputs. An alternative approach is offered by State-Space Models (SSMs), which recast sequence modeling as linear dynamical systems, allowing exact or approximate recurrent computation over long sequences gu2020hippo ; gu2021combining ; gu2022efficiently ; gu2023hippo . SSMs have been extended to multidimensional signals, audio and video tasks, demonstrating strong performance while maintaining linear complexity nguyen2022s4nd ; goel2022sashimi . Variants like S4 gu2021s4 and S5 smith2023simplified further improve parameterization and initialization, leading to robust training and effective long-range dependency modeling. Building on advances in graphical models and deep learning architectures, we introduce a new structural state-space layer, Myo, illustrated in Fig. 2 . Myo retains the linear complexity of existing SSM layers but explicitly leverages structural assumptions about token interactions, connecting sparsity patterns with recurrence constraints via matrix inversion. This framework allows SSM layers to emerge as a special case and enables direct inheritance of initialization schemes from the SSM literature gu2022s4d ; gu2023hippo . The layer is straightforward to implement (see Sec. A ) and can incorporate domain knowledge in the form of graphs. 2 Background In this section, we review two related sequence-to-sequence layers: the state space model layer (SSM) and self-attention. As our goal is computational complexity, we focus on the core components of the layer and ignore mapping from input sequence to the parameters of the layer. We identify a gap between two approaches that motivates our solution. We denote tuples of length L by s_{1:L} or s , when the length is clear. If all elements of the sequence belong to the same space V , then we write s\in V^{L} , otherwise specify per element s_{k}\in V_{k} . The first index of sequence is 1 . We denote the input sequence of the layer as a tuple u\in\mathbb{R}^{L\times M} and the output sequence as a tuple x\in\mathbb{R}^{L\times N} . We index elements of a tuple with lower index, for example, u_{t}\in\mathbb{R}^{M},x_{k}\in\mathbb{R}^{N} are the t -th and the k -th elements of the sequences x and u . Both self-attention and state space layers are parametrized of the sequence-to-sequence mapping K:\mathbb{R}^{L\times M}\to\mathbb{R}^{L\times N} , which itself can be input dependent. We refer to its matrix as the kernel matrix. 2.1 State Space Model (SSM) Layer Given an input sequence u_{1:L} and parameter sequences A_{1:L} and B_{1:L} , with A_{k}\in\mathbb{R}^{N\times N} , B_{k}\in\mathbb{R}^{N\times M} . A state space layer maps an input sequence to the output x_{1:L} by the following recurrence: \displaystyle x_{1} \displaystyle=B_{1}u_{1}, \displaystyle x_{k} \displaystyle=A_{k-1}x_{k-1}+B_{k}u_{k}\quad\mbox{for}\;k\in\{2,\dots,L\}. (1) As matrix multiplication is an associative operation ((AB)(CD)=((A(B(C(D)))) , the above recurrence can be computed in parallel by reusing intermediate computations using associative scan operations. As differentiation is a linear operation, the same is applicable for differentiation through the associative scan on a backward pass. The time complexity on T processors is O((L/T+\log_{2}T) and the space complexity is linear over the sequence length L . 2.2 Attention Layer We are given the input sequence u_{1:L} and parameter sequences q_{1:L},k_{1:L} , q_{k}\in\mathbb{R}^{N} , k_{k}\in\mathbb{R}^{N} and a nonlinearity \sigma . We call the composition of the non-linearity and inner product the kernel k(x,y)=\sigma(\langle x,y\rangle) of the attention. The attention layer maps the input sequence u_{1:L} to the output sequence x_{1:L} as follows: \displaystyle k\in\{1,\dots,L\}, \displaystyle x_{k}=\sum_{n=1}^{L}u_{n}\cdot\dfrac{\sigma(\langle q_{k},k_{n}\rangle)}{\sum_{n^{\prime}\in\{1,\dots,L\}}\sigma(\langle q_{k},k_{n^{\prime}}\rangle)}. (2) Hence, the complexity over both time and space of the self-attention layer is quadratic with respect to the length of the sequence L . To reduce it, additional assumptions about a function k(x,y) should be made. Two common approaches are the separability and sparsity assumptions. Separability assumption We consider the following parameterization of a fixed or learnable dictionary of functions \{\phi_{p}\}_{p=1}^{P},\phi_{p}:\mathbb{R}^{N}\to\mathbb{R}^{N_{p}} . Using it, we define a separable kernel: \displaystyle k(x,y)=\sum_{p=1}^{P}\langle\phi_{p}(x),\phi_{p}(y)\rangle,x,y\in\mathbb{R}^{N}. (3) As \sum_{p=1}^{P}\langle\phi_{p}(x),\phi_{p}(y)\rangle=\langle(\phi_{1}(x),\dots,\phi_{P}(x)),(\phi_{1}(y),\dots,\phi_{P}(y))\rangle , we consider the feature stacking map \psi:\mathbb{R}^{N}\to\mathbb{R}^{\sum_{n=1}^{P}N_{p}},\psi(x)=(\phi_{1}(x),\dots,\phi_{P}(x))) and hence the "linear" self-attention map: Q_{k}=\psi(q_{k})\in\mathbb{R}^{D},\;\;K_{k}=\psi(k_{k})\in\mathbb{R}^{D},\;\;D=\sum_{n\in\{1,\dots,P\}}N_{p}\;\;\mbox{for}\;\;k\in\{1,\dots,L\} (4) \displaystyle x_{k}=\sum_{n=1}^{L}u_{n}\cdot\dfrac{\langle Q_{k},K_{n}\rangle}{\sum_{n^{\prime}=1}^{L}\langle Q_{k},K_{n^{\prime}}\rangle}=(\langle Q_{k},\sum_{n^{\prime}\in\{1,\dots,L\}}K_{n^{\prime}}\rangle)^{-1}\sum_{p=1}^{D}\left(\sum_{n=1}^{L}u_{n}\cdot(K_{n})_{p}\right)(Q_{k})_{p}. (5) As a result, for fixed P\ll L , we obtain a desirable linear complexity solution over the length of the sequence. If we keep only the lower triangular part ( n\leq k) , the relation to the state-space model can be made more explicit. Consider x_{k} before scaling and summating over p and denote it by x_{k}^{p} : \displaystyle x^{p}_{k}=q^{p}_{k}\sum_{n\leq k}u_{n}\cdot k^{p}_{n}=\frac{q_{k}^{P}}{q_{k-1}^{p}}x^{p}_{k-1}+(k^{p}_{k}q_{k}^{p})u_{k}, (6) which reassembles the recurrence. Note that the separability assumption on the kernel reduces the number of free parameters of the kernel matrix K from L^{2} to L\times D . Although the kernel matrix K is generally dense, this reduces computational costs from quadratic to linear over the sequence length. Sparsity assumptions Another way to reduce complexity is to introduce a structural sparsity pattern in the attention kernel computation. It is convenient to represent a sparsity assumption by a graph. Consider a directed graph G(V,E) , where V=\{1,\dots,L\} is a set of vertices, and E is a set of directed edges over V . Vertexes of the graph correspond to the sequence elements, and the directed edges are present if we assume a nonzero attention value for a general input. For each pair (n,m)\in V\times V , we have the following matrix element: \displaystyle k_{nm}=\sigma(q_{n},k_{m}), \displaystyle\text{if }(n,m)\in E, \displaystyle\text{ otherwise }0. (7) If the graph has structured sparsity, it can be used to reduce the computation cost. A simple example is a pattern of edges present in sliding windows E=\{(n,m):~|n-m|\leq T\} , for some constant T . The kernel matrix K will be a band matrix, with block size T and therefore the computational and memory complexity will be O(TL) . We illustrate some sparsity patterns and the corresponding attention matrices in Figure 1 . 1 1 1 1 1 1 1 2 2 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 5 5 5 5 5 5 5 6 6 6 6 6 6 6 7 7 7 7 7 7 7 1 2 3 4 5 6 7 (a) Sliding window 1 2 3 4 5 6 7 1 2 3 4 5

Read the complete text