Laughing Hyena Distillery: Extracting Compact Recurrences From Convolutions
Authors: Stefano Massaroli
Michael Poli
Daniel Y Fu
Hermann Kumbong
Rom Nishijima Parnichkun
David W. Romero
Aman Timalsina
Quinn McIntyre
Beidi Chen
Atri Rudra
Ce Zhang
Christopher Re
Stefano Ermon
Yoshua Bengio
Venue: NeurIPS 2023 poster (2023)
Keywords: Long convolutions
recurrence
attention
language models
signal processing
throughput
auto-regressive generation
TL;DR: We refine long convolution sequence models in quality and efficiency: (a) we develop method to distill compact recurrences from large convolutional models without loss in quality, and (b) we introduce architectural improvements.

Abstract: Recent advances in attention-free sequence models rely on convolutions as alternatives to the attention operator at the core of Transformers. In particular, long convolution sequence models have achieved state-of-the-art performance in many domains, but incur a significant cost during auto-regressive inference workloads -- naively requiring a full pass (or caching of activations) over the input sequence for each generated token -- similarly to attention-based models. In this paper, we seek to enable $\mathcal O(1)$ compute and memory cost per token in any pre-trained long convolution architecture to reduce memory footprint and increase throughput during generation. Concretely, our methods consist in extracting low-dimensional linear state-space models from each convolution layer, building upon rational interpolation and model-order reduction techniques. We further introduce architectural improvements to convolution-based layers such as Hyena: by weight-tying the filters across channels into heads, we achieve higher pre-training quality and reduce the number of filters to be distilled. The resulting model achieves 10x higher throughput than Transformers and 1.5x higher than Hyena at 1.3B parameters, without any loss in quality after distillation.

LAUGHING HYENA DISTILLERY
Extracting Compact Recurrences From Convolutions
Stefano Massaroli -1 .Michael Poli Daniel Y. Fu
Hermann Kumbong". Rom N. Parnichkun", Aman Timalsina"
David W. Romero², Quinn McIntyre", Beidi Chen Atri Rudra', Ce Zhang Christopher Re Stefano Ermon2.t, Yoshua Bengiol.t Equal contribution. i Equal senior authorship. Mila and Université de Montréal. Stanford University.
The University of Tokyo. "Purdue University. Vrrije Universiteit Amsterdam. CCarnegie Mellon University and Meta Al (FAIR). University of Buffalo, SUNY. University of Chicago and Together Computer.
Abstract
Recent advances in attention-free sequence models rely on convolutions as alternatives to the attention operator at the core of Transformers. In particular, long convolution sequence models have achieved state-of-the-art performance in many domains, but in- cur significant cost during auto-regressive inference workloads naively requiring a full pass (or caching of activations) over the input sequence for each generated token similarly to attention- based models. In this paper, we seek enable O(1) compute and memory cost per token in any pre-trained long convolution architecture to reduce memory footprint and increase throughput during generation. Concretely, our methods consist in extracting low-dimensional linear state-space models from each convolu- tion layer, building upon rational interpolation and model-order reduction techniques. We further introduce architectural improvements to convolution-based layers such as Hyena: by weight-rying the filters across channels into heads, we achieve higher pre- training quality and reduce the number of filters to be distilled. The resulting model achieves 10x higher throughput than Transformers and 1.5x higher than Hyena at 1.3B parameters, without any loss in quality after distillation.
1 Introduction
Attention-free approaches such long convolation sequence models (LCSMs), e.g., H3 [1], Hyena [2], have shown promise in matching Transformer [3, 4] performance across a wide range of tasks, with sub-quadratic complexity with respect to sequence length. Despite the improved efficiency during training on long sequences, unless the convolution filters are either short or admit low-dimensional state-state-space realization, LCSMs still need process the entire growing sequence at every step of auto-regressive generation, similarly to Transformers.
In this work, we seek to refine LCSMs in both efficiency and quality. First, we study the inference stage, and propose methods to enable a recurrent mode for auto-ret regressieee generation. Recurrent modes pre- scribe the existence of state encoding the past information of the process in fixed-dimension memory, enabling constant per-step time and constant-memot ysis of pre-trained models to develop architectural enhancements for the Hyena block, simultaneously improving model quality and efficiency of the distillation procedure.
in generation. Then, we draw upon anal-
Distilling fast recurrences We introduce LaughingHyena, the first distillation approach for LCSMs that enables recurrent inference without impacting downstream quality. LaughingHyena seeks compact recurrences in the form of state-space models (SSMs) [5, 6] the solution of nonlinear interpolation problem involving the convolution filters of a pre-trained model. Since the total memory cost of SSMs grows linearly in the state dimension d, our distillation procedure enables high throughput by enabling processing of large batches during generation. We identify and address three core challenges related to distillation, including the identification of:
37th Conference on Neural Information Processing Systems (NeurIPS 2023).

---

Target state dimension: we identify candidate state dimensions of our distilled SSMs by analyzing
the spectrum of the Hankel operator associated with each convolution [7].
Parametrization: we address issues with naive parametrizations by introducing a factorized modal
form, inspired by barycentric [8] and Prony-like like [9] methods
Approximation metric: to ensure compatibility with any downstream task, we choose discrepancy metrics on the convolution filter, rather than model outputs.
In auto-regressive workloads, LaughingHyenn-diisinn -istillidd models with state dimension d can generate K tokens in O(dK) time and with constant ((d) memory- improving over the O(K2) time and ((K) memory usage of kv-cached Transformers and naively executed long convolutions. At model sizes above one billion parameters, LaughingHyena achieves 10x higher peak throughput over comparable Transformers (Figure 1.1), and can process larger batch sizes. Constant memory generation enables larger K for given a memory constraint e.g., generating 512 tokens with LaughingHyena requires 3x less memory than with a Transformer. At smaller batch sizes, latency of LaughingHyena is also competitive with Transformers, reaching 2 2x speedups at longer prompt lengths.
Improving pre-training quality We leverage our analysis of the distillation process to open up new avenues of improvement for LCSM ar- chitectures. Indeed, the high compression rates achievable through LaughingHyena hint at sub-
Laughing Hyena 1.38 Hyena 1.3B
Generation Throughput [tok/ s]]
Hybrid Attn. H3 1.38
Transformer 1.38
-10
0.8
utilization of the convolution. We revisit the multi-headed design of H3 [T]: tying weights across channels pushes long convolution filters towards larger effective dimension, and as an ad- ditional advantage reduces the runtime of post- training distillation and inference memory foot- print. Further, multi-head Hyena models improve on pre-training perplexity over regular Hyena and GPT [10] architectures on the language dataset THE PILE [11].
0.6
0.4
0.2
100
200
300
400
500
Batch Size
Figure 1.1: Throughput (in generated tokens) of Trans- formers, H3 and Hyena models. LaughingHyena is a re- current model distilled from a pre-trained Hyena. Work- load involves generating 256 tokens given a prompt of length 512.
2 Preliminaries and Related Work
We discuss convolutions, state spaces and auto rugo-segressive generation workloads for sequence models.
Convolutions Let denote the convolution operator. It is defined as the dual operation to point- wise multiplication under Fourier transform. In signal processing and deep learning alike, one often encounters the causal linear convolution of filter h (which may extend indefinitely) with an input of length L:
(h * u): = Σ ht-s
(2.1)
j=0
Generally, u, E TRD where D is the width of the signal or in deep learning parlance - the number of channels. Without loss of generality, we specialize our analysis to single inpus single output layers, i.e. with D = 1. For the input-output relations of type 12. we use the terms convolution layer and linear system interchangeably. Similarly, the function ~> h, is referred to as both the filter and the impulse response of a linear system. Existing convolution sequence models can be classified in terms the parametrization used for their filters. The class of implicit convolutions represent the filter as a parametric function "o : h4.
State-space realization time-invariant system,
One option is to select ye as the impulse response function of a discrete linear
Le+1 Az; + Bu,
hop 1 / h4 = IA t>
t=
(2.2)
yt Cr2 + houe"
with state 24 E IRd, impur u, E R. and output yı E R. The matrices A E Rdxdd B Rd C I Ixd and hn E IR are the learnable parameters of the model while the initial state xn usually set to zero such that u + is pure convolution. While linear systems (2.2) are the staple of signal processes and control theory, their use as implicit parametrization of convolution filters in deep neural networks have only recently emerged [12, 6]. Other parametrizations [13, 14, 2] select (p(()) as different flavors
2

---

of implicit representation neural networks [15, 16]. The latter are generally more powerful in terms of the class of filters they can represent and flexibility during training, at the cost of losing a fixed state dimension.
T
2.1 Long Convolution Sequence Models
T(k)
The H-family of convolution sequence models [1] and Hyena [2] relies on combination of long convolutions and data- controlled gating to replace attention with sub-quadratic scaling in sequence length'. We use the deep learning convention of nam- ing different projections as query q, key l and value v. Let M2 and M₁ be the L-by-L diagonal matrices whose respective main diagonal entries are the respective entries of length-T, sequences and k. A H-block realizes surrogate attention matrix with a data-controlled, parameterized decomposition in three terms:
T(+)
M
>
T
>
Mg
>y
Figure 2.1: H-block. T(O), T(a), T(M)
are short-convolution operators.
(g. k v) + H(g, k)u, H(q. k) M, T
(2.3)
where Lx is the Toeplitz matrix constructed from the learnable long convolution filter h, i.e., Th= 1-1 The gkv-projections are themselves the output of a convolution between the input sequence and three distinct short filters. The degrees of freedom in H-block design are the three short filters and the long filter h. The long filter can be parameterized using an implicit neural represen- tation [2], state-space model [1]. or explicit values [17]. The threefold decomposition of the attention operator, allows evaluation of (2.3) in just (L)) = OLL log2 L) time (two convolutions 3 and two element-wise products), y;=q (h * kv)e. The overall operator acts on an input u by constructing a third- order multi-variate polynomial of u whose coefficients are controlled (nonlinearly) by parameters of the block.
2.2 ungo-Regressive Generation
A typical workload for sequence models is auto-regressive generation. Given a length-T prompt RTT the model is tasked with producing the following K additional outputs - one at a time for a resulting output sequence y of length T.=7+K.
Convolution sequence models After processing the initial prompt in Ö(T) time and obtaining a length-T' output u + yo. V1- a generic convolution layer can cache the output sequence and generate any additional outputs using (2.1) auto-regressively, i.e. Vj= ر for T-K..,,., It is important to note that auto-regressive generation with generic long con-
volutions is expensive. comes with a quadratic cost in the number K of tokens to be generated and require storing cache of length up to L.
Lemma 2.1. Generating K tokens with long convolution layer (2.1) from length-T prompt has time complexity O(T log, T + TK + K2) and requires (T.) memory.
State-space models When the linear system admits state space realization (2.2), i.e. it is able switch between convolution and recurrent mode, the cost of auto-regressive generation can be dramat- ically reduced. The memory footprint is Od): all we need to cache is the state 2t, d-dimensional vector. With some further machinery that we develop in next section, we can retain ÖTT) time and (I') memory to process the prompt' and initialize the state ØT-1. Each additional generation step only requires (d) time.
Lemma 2.2. Generating tokens with a state-space model from a length-T prompt has time complexity OTTlog, T+KK) and requires O(T + d) memory.
Note that long filters i truncated to length d (i.e. h,=0 for d-dimensional SSMs (see Appendix A.7) where the state (a cache) coincides with the last d inputs.
1) can also be interpreted as
Transformers Self-attention is certainly less efficient than long convolutions in processing the prompt, coming with hefty (TT2) time complexity. However, Transformers can achieve a similar
'In this work, we consider second-order Hyena blocks [2] to automatically extend our findings to H3 [1]. "The short filters are explicill parameterized, see [2].
'The qkv short convolutions can be evaluated in batch with single pass. The second convolution is the one
with the long filter h and performed via Fast Fourier Transform (FFT), hence the (T.)) complexity.
'In $3.4 show that multiple pre-fille mrefiiling strategies exist, with different trade-off's in time and memory.
3

---

efficiency in auto regreseeee generation by caching the sequences of past keys } and values {vz Specifically, from t= onward, the new projections (gt+1. R4+1 U++1) 1) are evaluated from the current output Vt, and the new output U4++1 can be computed in linear time with two reductions
Ve+1 2,=0 ++1 E p(e+1kk));
where p IR + is usually chosen as xp(x) = e""
Ei plact1kig)
Lemma 2.3. Generating K tokens with self-attention from a length-T prompt has time complexity O(T2+TK+** and requires (T.) memory.
3 The Laughing Hyena Distillery
this section, we introduce our distillation method. We discuss choosing an approximation objective, parametrization for the approximant and setting target state dimension.
Given any pre-trained LCSM, the objective of the distillation procedure is to convert each pre-trained convolution filter into distinct state-space model (2.2). This should be achieved with the smallest state dimension d which preserves, up to a certain tolerance, the input-output characteristics of the convolution layer. Formally, given filter h the distillation problem is defined as follows.
Given the sequence hi....,hy, hr, find a state-space model (2.2) dimension < L, whose input-output behavior approximates the one of the convolution with h over the largest class of input sequences.
The choice of approximation metrics and assumptions on the input sequences yield different distilla- tion objectives. A distillation algorithm constitutes systematic procedure for optimally choosing the systems matrices with respect to particular objective. In instances where the original filter h is itself the impulse response of dimenssnimni state-space model, e-g., when attempting distillation of H3 or S4 [6] filters, the term distillation becomes analogous to model-order reduction. Hence, in such cases, the distillation algorithm should yield a state-space representation of a lower order dimenssio.
There exist several algebraic solutions to the model reduction problem [18, 19, 20J. typically seeking low-rank structures of the state space by inspecting some invariant of the system, e.g. the Grumians balanced truncation [19, Ch. 7J. The lower-order system is then obtained as a projection of the system dynamics onto the found subspace where the system retains desired characteristics, e.g., input-output behavior, stability, etc.
Truncated filters
In theory, implicitly parameterized convolution filters can represent arbitrarily long signals. In practice, these filters are trained on fixed maximum length L. At inference time the model can then be evaluated for sequences longer than L. During distillation it is nonetheless reasonable to treat the pre-trained filters as potentially very long (even beyond L) but finite impulse response functions [21, 22, 23, 24J. We show how this choice is supported by empirical evidence displaying how pre-trained filters typically decay to zero in finite time (see Appendix D)).
Transfer function representation An alternative description of the system (2.2) is its transfer function H, defined as the z-transform of the impulse response H==)= Σ 20 h42 for all zeC where the sum converges. The transfer function is proper rational function of
b + + bba
Hzz) = to + C(2l A) - ho + 1 a-==1++
(3.1)
+ a
In the z-domain, the transfer function defines the input-output map Y()) (z))((z), Here, (z)) is defined outside the C-plane circle of radius p(A), ID (= C: > p(A)) where p(A) is the spectral radius of A, i.c. the amplitude its largest eigenvalue. We can recover all characteristics of given system equivalently from either its transfer function state-space rep- resentations (see Appendix A.3 for further details and derivations). Notably, the transfer function is invariant of the system: if we apply change of variables to the state, the transfer function remains unchanged (Lemma A.3). This alone should discourage attempts at modeling filters by learning dense state-space matrices A, B, C as such: there are infinitely many equivalent state- space realizations that map to the same system. Starting from coefficients (a:) and (b:) of the ra- tional transfer function (3.1), we can compute the impulse response in Ó(L) time (Lemma A.6). Moreover, we can map back the transfer function to special state-space realization the com- panion canonical form whose recurrence has time complexity ((d) (Lemma A.7), compared to

---

Hankel SVD
candidate state dim d
Compute Transfer Function
Pretrain
Distill State-Space
A, ho
Deployment
Conv. Model
Compose Recurrence
Downstream eval.
Fine tuning
Sequence
Get initial value ho
Dataset
Figure 3.1: :: The LaughingHyena long convolution sequence model distillation blueprint.
the (dd) of dense state-space matrices, From Lemmas A.3 and A.7 we can also prove that any stable state-space model can be converted by canonicalization into companion form, and thus be equipped with an efficient recurrence (Thm. A.8).
The distillation problem presents several challenges:
1. Defining the distillation objective. A primary decision involves selecting a distillation objective. We are primarily interested in metrics pure discrepancy between each filter a pre-tratee traindd deep model and its approximator, rather than the expected imput-output loss over distribution of inputs.
2. Choosing state-space parametrization. It is crucial to determine suitable parametrization of the distilled state-space realization. Once this decided, the task is to identify the parameters that minimize the distillation desiderata, which can involve challenging optimization problems in itself.
3. Selecting the target state dimension. Lastly, a challenge is to estimate the degree to which the model's order can be reduced. In other words, we must select the target state dimension of the distillation process to identify the right trade-off between efficiency and accuracy.
the following, we address each these challenges, and provide a comprehensive approach (summa- rized in Figure 3.1) to distill recurrences from convolution-basee architectures.
3.1 Data-Free Distillation Objectives
We focus distillation objectives that are independent of the training data and the overall architecture the neural network under consideration. The distillation loss should be chosen as a pure measure discrepancy between each convolution filter he of the model and their finite-dimensional approxima- tions h, BB. This approach ensures that do not require full sequential inference pass over the pre-trained model at each step of distillation procedure and the distilled model can be more broadly applied to downstream tasks. This choice is supported by Young's convolution inequality [25, 26), which indicates that the output approximation error has bound |yy -ll s ---alllllll/ for properly chosen norms For maximum numerical stability and freedom of parametrization for the approximants, we favor modern unconstrained gradient-based approaches to then solve the resulting distillation pro- gram We design distillation algorithms which either match filters in time domain minimizing the l error (1]hl|2 1Erez 1h,1 12) match their transfer functions optimally with respect to the Hi norm (| la2 = [(1/2x] __, (H (etw)) (dw As the distillation is carried out via gradient methods, E is a natural candidate. H2 eиrоr minimization can instead be used uniformy bound the worst-case discrepancy as ||/ Ro || [|2 (see Appendix A.2 for further details).
3.2 Making Hyena Laugh with Modal Interpolation
Our degrees of freedoms to solve the distillation problem are the matrices A, B. and C of the state-space realization, which determine the filter for all t > 0. In distilled SSMs, the passthrough (residual) term cannot be freely assigned: is simply ho. the value of the original filter at zero. Alternatively, given its
"p > O should satisfy 1/q 1/p 1/r 1. In the case of infinite sequences defined on the all ž, the norms are taken in a lp. Eg E, sense, respectively. The bound is potentially sharp [27, 28]
'For completeness, we also test balanced and modal truncation techniques on a suite of pre-trained H3 and Hyena models in Appendix E.3.
Such norms are always well-defined for tinite sequences of interest which are in Loo.
5

---

appealing invariance properties, we can parametrize proper rational function ((2) (3.1) and fit it to the (truncated) transfer function" of the original filter (= Eizo hy2 (see Appendix B.2).
Modal canonical form Optimizing the full transfer function can be numerically challenging for sev- eral reasons e.g,, ensuring stability", and ill poseedesss for high-order polynomials. A natural solution, inspired by barycentric approaches to rational function approximation [29, 8J, is to assume d distinct roots An in the denominator's 's polynomial, An E roots(poly(n))
Proposition 3.1 (15)). If (oly(a) has distinct roots {>n E C), then the transfer function of the
system can be factorized [=))= Ra/(z Xa), 1/2 (P(A) where {Rn, C) is the residue associated with the pole An.
Computing the inverse transform of the expanded transfer function via, e.g., the Cauchy residue theorem [30], shows that the resulting impulse response h corresponds to truncated basis of exponentially decaying complex sinusoids
d 7 Σ Rn
Ra, An E C 0.
(3.2)
In practice, this corresponds the impulse response of state-space model with diagonal matrix A diag(AA...... Aa) and such that B,C, = R3 for all = I,...,d. The distillation problem can be then defined in terms of the I--point nonlinear least squares interpolation error (squared (2) between
; hr and (3.2) evaluated for t=l,.... L: min(A.. ||á All2 Note that in case of the target filter & being real real-valued, the objective can be replaced by [[ Al12.
Although we find solutions of the distillation (in- terpolation) problem via modern gradient-based op- timization techniques, is worth mentioning that Prony showed how the nonlinear least square solu- tion can be computed solving two linear problems [9]. However, similar to Padé's method for rational approximation [31], these techniques can be numer- ically unstable. We opt for parametrization similar to [32, 33] where each eigenvalue is parameterized in polar form A, and the residues in carte- sian form 10, Note that, with this parametrization we have M(h.] = Σn A 44-1(99RR,, cos(O,. 1))
Modal Interpolation
Rn X--1 -.
hu
0.5
0
-0.5
0
20
40
60
80
100
120
Figure 3.2: Example of modal interpolation. The approximant a linear combination of exponentially- decaying complex exponential basis functions with learned decay rate.
(R.,) ) sin (1 T))]. We can also solve the distil- lation problem in the H2 sense by evaluating hn and h, at t 0. O..... L 1 and taking their respective (discrete) Fourier transform before computing the objective. Efficient evaluation of (3.2) is crucial for distillation. In particular we show the following:
Lemma 3.1. Evaluation of (he)!-) (3.2) can be done in ((LL) time from its modal form and in (L) time from its proper rational form.
3.3 Minimal Distillation Orders
Distilling into lower-dimensional systems is always desirable as they require fewer parameters to be optimized and they yield recurrences that are (linearly) more efficient in terms of time and memory complexity in post- dost-distillation ruto-regressive inference workloads. The dimension of the smallest pos- sible saate-spce model with impulse response exactly (he heN the so-called McMillan degree [34]:
d' arg min d 3A E Cadd B E cdx1 C Clxd with h4 = CA >
(3.3)
Theorem 3.1 Hal-aalman [35, Theorem Corollary]). Let S be the (infinite) Hankel matrix constructed with h, i.e. S = (h;+g))gg Then, d' rank(S).
"s already partially discussed in [6]. the truncation introduces correction term in the approximant transfer function. See Appendix A.4. 91. normalizing denominator polynomial cnefficients to constrain roots within the unit circle.
We report additional details on the nuances of the parametrization in Appendix B.I.

---

A lower bound for d' can be estimated from truncated filter of length L by constructing the L x L principal sub-matrix S,. and using the fact that rank(S) 2 rank(S,,). Inspecting how fast the Hankel singular values (ax)%== decay in pre-trained convolution models can be predictive of the approximation quality at a fixed dimension. As a rule of thumb, d needs to be sufficiently large for dd+1 to suffi- ciently small". Specifically, we can prove that the last singular value da determines the upper bound distillation quality with a SSM of dimension d, in terms of the Hankel norm [19]. This is a direct consequence of Adamjan-Arov Arov-Keen theorem [7] and can be informally stated as follows.
Theorem 3.2 (Informal). Let h be Length-L filter, h distilled filter of order d < L and let Sz. Sy be the respective Hankel matrices. Then infg, |S -Sy dd-
3,4 Deploying the Recurrence
Once all the filters of pre-trained model have been distilled with the proposed modal interpolation technique described above, the model unlocks a recurrent mode which allocates a state E C for each filter and enables fast auto-regressive inference. Deployment of distilled model involves two critical steps: the pre-filling and the recurrent update rule itself.
Fast pre-filling During auto-regressive generation, when a length-T' prompt is fed to the model, we need compute the state 2t start generating new tokens. Using the recurrence, the time complexity initializing Fy would be (dd)) with a (dd memory footprint. One can alternatively distribute the computation d processors with a parallel scan operation [37, 38] to reach a parallel time complexity Od T) while incurring in an increased memory requirement of (dd)) 12 A third option is to use a single FFT convolution to obtain in (T)) time and O(T) memory.
Proposition 3.2. JT (VT...., .T. vd- where vs (g * u)e and g is the filter whose transfer function is 1/den( (z) and can be evaluated ÖTT).
Note that, the fast pre-filling algorithm established by this result requires evaluating the denominator polynomial of / from its roots before deployment. This is equivalent to converting the transfer function from its factrizzed representation to its rational form (3.1).
Recurrent step
The update rule is diagonal, thus efficiently evaluated in O(d) time and memory:
Proposition 3.3. The filter (3.2) has a state space matrices A = diag(A1..... E Cdxdd B = (1...., 1)T E Cdx1, C= (Ri..... Ra) E Clxd whose step can be evaluated in O(d) time and memory.
As we generally want the output yt to be real-valued, we can simply update the complex state xe+1 Ar; + Bu, and then take the real part of the output, = R(CC,,] + hg44.
4 Multi-head Long Convolutions
We can leverage the Hankel spectrum analysis discussed in Section 3.3 to study the dynamics of the effective dimensionality of each convolution filter during LCSMs pre-training. We find that, at ini- tialization, filters correspond to high-dimensional SSMs, and gradually converge to lower-dimensional representations during training. See Appendix E.2 for examples on Hyena and H3 models.
This observation leads to the question: is it advantageous to perform independent long convolutions on each channel, or can we reduce the total number of filters without loss in quality? To answer this, we adapt the multi-head layer design proposed by H3 [1] to Hyena [2]:
1. Given the projections q, ki E LRD, we split them into M chunks of size N=D/M, qth k.m n E L
2. Each chunk is processed by modified Hyena operator: first, we perform the outer product of km and TT along the spatial dimension, =m @ TT E N apply long convolution with filter hm all N X elements independently, then compute y!" - m ) y RLxN shown in Figure 4.
3. Finally, we compose y' "'....y"" into a single output y E LL via concatenation.
"Formally, this is related to low-rank approximation characteristics of the Hankel operator; rigorous bounds can be constructed by application of the Bekart-Young-Minne theorem [36]. This strategy can also be use to evaluate the filter h alternatively to the standard O(LL) method
7

---

An instance of a MultiHyena is equipped with M < D dis- tinct long convolution filters, which leads (a) faster dis- tillation, with less filters to approximate, (b) lower memory footprint, via a total reduction of the states to cache dur- ing generation and (c) faster filter generation, by tying the weights of filter parameters. We note that tying weights key-value projections has also been shown to be effective technique to reduce memory cost in Transformers [39, 40]. Hyena.
km
outer
T - +
Figure 4.1: A single head of multi-heas
Crucially, the multi-head structure of MultiHyena enables to prove favorable scaling in the associa- tive recall synthetic task, which was shown in [2] to be predictive of performance at scale. In associative recall, the model is given sequence of key- key-value pairs and query, and is tasked with matching the query to a key in the sequence by returning its associated value. The difficulty of the task grows with the vocabulary size 8: larger vocabularies necessitate wider models.
Theorem 4.1. The MultiHyena layer, with Olog s) heads and model size O(ys log s) can solve the associative recall problem, where s denotes the vocabulary size.
Appendix E.I, we empirically verify improved scaling in vocabulary size with multiple heads.
5 Experiments
We pretrain a suite of MultiHyena language models on The Pile [11], investigating scaling of perplexity with different amounts of total tokens (5, 10, 15 billion), as well as larger training runs for 300 billion tokens. MultiHyena outperforms Transformers and Hyena.
Pretraining:
Distillation analysis: We investigate the relation between optimal distillation orders, Hankel spec- trum, and errors on the logits of distilled models.
Post-distillation downstreams: We evaluate the downstream impact of distilling long convolutional language models, reporting HELM [41] and LM-Eval-Harness [42] results.
Benchmarking: We benchmark latency, throughput and memory along the different axes of batch size, sequence length, number generated tokens. We include base models, distilled models and equivalent Transformers.
5.1 Pre-training
To validate the multi-head formulation, we train 150 and 350 million parameter MultiHyena models on The Pile [1 ]] using heads and otherwise the same architecture as equivalent Hyena models, following the setup of [2]. Via the multi-head structure introduced in 4, MultiHyena outperforms both Hyena and Transformers, including on data scaling runs with increasing numbers of tokens and full 300B tokens runs (Table 5.
5.2 Distillation Analysis
Next, we verify whether Hankel singular values are predictive of downstream errors, and whether large models can be distilled without loss in quality. We apply LaughingHyena distillation to pre-trained MultiHyena, Hyena and H3 of different sizes. Concretely, for each layer and channel of a model, we parametrize the poles (X,) of the modal canonical forms (Section 3.2) at different orders d, and solve for each & approximation problem.
Approximation errors and spectrum We investigate the magnitude of approximation errors intro- duced by LaughingHyena distillation. Given pretrained MultiHyena model, we compute the errors between original and distilled filters at each layer, averaged across channels. We repeat this process for different distillation orders (state dimension of the model form of Section 3.2). Figure 5.2 visualizes
Model
PERP.
Model
5B
10B
15B
Model
5B
10B
15B
GPT
9.3
GPT (125M)
13.3
11.9
11.2
GPT (355M)
11.4
9.8
9.1
Hyena
9.3
Hyena (153M)
13.3
11.8
11.1
Hyena (355M)
11.3
9.8
9.2
MultiHyena
8.7
MultiHyena (153M)
12.1
11.0
10.6
MultiHyena (355M)
10.6
9,4
8.9
Table 5.1: [Left] Perplexity of small models on THE PILE, after pre-training for 300 billion tokens. [Center and
Right] Perplexity on THE PILE for models trained until total number of tokens c.g., 5 billion (different runs for each token total).
8

---

Relative & Error on Logits
Error Inset
d =
=
109 PM
10-1
10000 20000
30000
40000
50000
2000
4010
6000
800
2
1071
10-2
error
10-3
10000 20000
30000 40000
50000
200
400
600
800
Sorted Logits
Sorted Logits
Figure 5.1: Errors between logits of pretrained and distilled MultiHyena. In blue, we plot (ordered) logits, in light blue the cumulative distribution function, and in black the relative errors. The green dotted line indicates the 99.99% percentile. As the errors grow slowly function of the pereentiles, model outputs do not diverge from the base model.
minimum, maximum and average errors, per-layer errors and the distribution of the singular values of the Hankel operator associated to each filter. We observe distillation orders (> 16) that yield smalls errors to be predicted by the distribution of singular values. Thus, analysis of the Hankel operator's spectrum is verified to be an effective approach to direct estimation of the optimal distillation order. We also note that the optimal order changes across layers, offering options for further optimization.
Output errors Next, we compute relative I error between output logits of pre-trained and distilled models ensure LaughingHyena can be used in generation workloads. The optimal minimal distillation order estimated via Hankel operators (16) is sufficient to keep the output distribution over the vocabulary (> 50k entries) close the pre-trained model, as shown in Figure 5.2. Inspecting the error profile over logits sorted by magnitude reveals our approach to be robust to different sampling strategies for generation, including greedy decoding, top-k, top-p [43]. Indeed, the relative errors are 10 2 up and including the 99.99% percentile of the distribution, meaning c.g., top-p sampling strategy with large p can be used on a distilled model without drift in outputs (mis-classified tokens). We note that the relative errors are maximum on small-norm logits, which are not required by most sampling strategies. In Appendix D.2, we provide a similar distillation error analysis for Hyena and H3 models. We find that Hyena and can be distilled with less than 32 orders and H3 with less than 8.
5.3 Downstream Evaluation
We check how distillation affects downstream performance language benchmarks. We apply distil- lation of order 8, 16 and 32 to our THE Pretrarerr MultiHyena language model and benchmark (Table 5.3) its performance
suite of canonical (zero shot) tasks from L-M [42] and HELM [41]. The results are consistent with our error analysis: distillation orders equal or greater to 16 introduce little-to-no quality degradation.
Model
LAMBADA
Winogrande PIQA acc
HellaSwag acc norm.
OpenbookQA acc norm.
acc
acc
Pythia (160M)
32.8
53.1
61.6
31.6
29.2
MultiHyena (154M)
43.2
52.7
64.6
34.1
29.0
LaughingHyena-Il
43.1
52.6
64.7
34.1
28.9
LaughingHyena-88 Layghing
0.0
51.8
51.5
32.7
28.2
0.0
49.6
53.7
26.4
26.4
Table 5.2: Evaluation of buughingHyena-distillee. models pre and post modal distillation. We test on LM --Eal- Hamness [42] and HELM [41] tasks, reporting Pythia [44] performance a Transformer bascline trained the same data. LaughingHyenn--d MultiHyena model with each filter distilled of order d.

---

Error
Error
Error
Hankel Singular Values
value
dipath
deptth
order
order
order
singular value index
Approximation enror profiles (min, max, average) on the filters of MultiHyena model after distillation at different orders. We also visualize the distribution of Hankel singular values: if the spectrum decays after n singular values, order distillation yiclds low errors.
Figure 5.2:
5,4 Benchmarking
We measure throughput, latency and memory usage of LaughingHyena for auto-regressive generation workloads, with initial prompt length 7 and number of generated tokens K. The throughput is computed as number of generated tokens over latency. For each setting (and additional benchmarks), we provide details in Appendix D.4.
Peak throughput Distilled models do not need kv--aches. This reduces memory requirement dur- ing generation, enabling higher peak throughput in larce-batch workloads. We achieve 10x higher throughput than Transformers at size 1.3 billion parameters (Figure 1.1). Throughput is higher than Transformers even at fixed batch sizes, indicating lower latency.
SSM state dimension and throughput For typical distillation orders (< 100), peak throughput is not greatly affected. We measure 2% reduction in throughput from 32 64.
Prompt length The throughput of LaughingHlyenaddstille.. models is 4x larger than Transformers fixed batch size 64 and prompt length 1536 (Figure 5.3). As prompt length increases, the runtime gap between pre-filling via convolutions LCSMs and pre-filling Transformers widens (e.g., OTT) as detailed in Section 3.4, compared to (TT))..
Memory footprint Recurrent models do not require kvu-caches and use constant memory for genera- tion of an arbitrary number of tokens (Figure 5.4).
6
Conclusion
We study the efficiency and quality of state-of the-t-rrttr long convolutional sequence models. First, introduce LaughingHyena, a novel distillation method inspired by rational function approximation and model-order reduction techniques. LaughingHyena state-space models from each convolutional filter, without loss of quality. Distilled models achieve higher throughput than equivalently-sized Transformers, and can perform auto-regressive generation in constant memory by sidestepping the need to cache previous outputs, We theoretically and empirically investigate the trade-off's of different strategies for fast inference of recurrent models, and introduce architectural improvements to Hyena that improve pretraining quality.
be applied after training extract compact
Laughing Hyena 1.3B Hyena 1.3B
Laughing Hyena 1.3B
Hyena 1.38 1.38
Throughput |tok/s s|
Transformer 1.3B H3 1.3B
Transformer 1.3B
3,000
Memory [GBs]
2,000
20
10
1,000
512
1,024 Prompt Length
1,536
64
256 Generation Length
512
Figure 5.3: Scaling in prompt
Figure 5.4; Peak GPU memory generation.
10

---

Acknowledgments
We would like to thank Together Computer for providing the compute used to train models this paper. We gratefully acknowledge the support of NIH under No. U54EB020405 (Mobilize), NSF un- der Nos. CCF1763315 (Beyond Sparsity), CCF1563078 (Volume to Velocity), and 1937301 (RTML); US DEVCOM ARL under No. W911NF-21-2-025 (Interactive Human-AI Teaming); ONR under No. N000141712266 (Unifying Weak Supervision); ONR 800014-20-15 1-2480: Understanding and Ap- plying Non-Euctidean Geometry in Machine Learning: N000142012275 (NEPTUNE); NXP, Xilinx, LETI-CEA, Intel, IBM, Microsoft, NEC, Toshiba, TSMC, ARM, Hitachi, BASF, Accenture, Ericsson, Qualcomm, Analog Devices, Google Cloud, Salesforce, Total, the HAI-GCP Cloud Credits for Re- search program, the Stanford Data Science Initiative (SDSI). Department of Defense (DoD) through the National Defense Science and Engincering Graduate Fellowship (NDSEG) Program, and mem- bers of the Stanford DAWN project: Facebook, Google, and VMWare. This work is supported by NSF (1651565), AFOSR (FA95501910024), ARO (F-21N2-2))))0125)) ONR, DOE (DE-SC0022222), CZ Biohub, and Sloan Fellowship. The U.S. Govermment is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not nec- essarily reflect the views, policies, or endorsements, either expressed or implied, of NIH, ONR, or the U.S. Government. AR's work is supported by NSF grant# CCF-2247014.
Broader Impact
In this work, we focus advances related to efficient models for long sequences.
high throughput inference in long convo- lution sequence models Ms) can lead energy savings during model deployement, enabling pro- cessing of longer-fone content at a fraction of the cost and reducing environmental impact. Improved efficiency may also affect other aspects of AI safety, as may make it easier produce malicious or harmful content.
Efficiency Our distillation methods for constant-
Accessibility By improving the efficiency of training and generation, Letirattion,CSMMM CSMs and LaughingHyena may contribute to increased accessibility of large language models, lowering the hardware barrier to entry for individuals and organizations with limited resources.
Steerability New method based on LCSMs enable sequence models process long-form prompts previously inaccessible by Transformers, which may lead to increased control over models via e.g., conditioning on additional instructions [45].

---

References
[1] Daniel Y Fu et al. "Hungry Hungry Hippos: Towards Language Modeling with State Space Mod-
els". In: 2023 (cit. pp. 1-3, 73)..
[2] Michael Poli et al. "Hyena Hierarchy: Towards Larger Convolutional Language Models". In:
(2023). arXiv: 2302. 10866 (cit. on pp. 1-3, 7, 8, 31, 35, 43).
[3] Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. "Neural machine translation by jointly learning to align and translate". In: (2014), arXiv: 1409. 0473 (cit. on p. 1).
[4] Ashish Vaswani et al. "Attention is all you need". In: Advances in neural information processing systems 30 (2017) (cit. on p. 1).
[5] Chi-Tsong Chen. Linear system theory and design. Saunders college publishing, 1984 (cit. on
Pp. 1, 6, 19,
[6] Albert Gu, Karan Goel, and Christopher Ré. "Efficiently modeling long sequences with structured state spaces". In: (2021). arXiv: 2111.00396 (cit. on pp. I, 2, 4, 6, 20, 24).
[7] Vadim Movsesovich Adamyan, Damir Zyamovich Arov, and Mark Grigor' 'rich Krein. "Analytic properties of Schmidt pairs for Hankel operator and the generalized Schur-Takagi problem".
In: Matematicheskii Sbornik 128.1 (1971), pp. 34-75 (cit. on pp. 2, 29)..
[8] Yuji Nakatsukasa, Olivier Sête, and Lloyd N Trefethen. "The AAA algorithm for rational approx- imation". In: SIAM Journal on Scientific Computing 40.3 (2018), A A1494-A1522 (cit. on pp. 2,
[9] GRB Prony. "Essai experimental et analytique les lois de la dilatalrlite de fluids elastiques sur cells de la vapeur de l'alcool, à différents tempoeratures". In: Journal de I l'Ecole Polytech- nique (París) 1 (1795), pp. 24-76 (cit. on pp. 6).
[10] Alec Radford et al. "Language models are unsupervised multitask learners". In: OpenAl blog 1.8 (2019), p. 9 (cit. on p. 2).
[11] Leo Gao et al. "The pile: An 800gb dataset of diverse text for language modeling". In: (2020).
arXiv: 2101 2101.00027 0002000027 (cit. on pp. 2, 8, 35).
[12] Albert Gu et al. "Hippo: Recurrent memory with optimal polynomial projections" ". In: Advances in Neural Information Processing Systems 33 (2020), pp. 1474-1487 (cit. on pp. 2, 24).
[13] David W Romero et al. "Ckconv: Continuous kernel convolution for sequential data". In: (2021).
arXiv: 2102. 02611226111 (cit. on 2).
[14] David W Romero al. "Flexconv: Continuous kernel convolutions with differentiable kernel
sizes". In: (2021). arXiv: 2110.08059 (cit. on p. 2).
[15] Vincent Sitzmann et al. "Implicit neural representations with periodic activation functions". In: Advances in neural information processing systems 33 (2020), pp. 7462-7473 (cit. on on p. 3).
[16] Rizal Fathony et al. "Multiplicative filter networks". In: International Conference on Learning
Representations. 2020 (cit. on p. 3).
[17] Daniel Y. Fu et al. "Simple Efficiet-Efffcient Long Convolutions for Sequence Modeling". In: International Conference on Machine Learning (2023) (cit. on pp. 24).
[18] Kemin Zhou and John Comstock Doyle. Essentials of robust control. Vol. 104. Prentice hall Upper Saddle River, NJ, 1998 (cit. on p. 4).
[19] Athanasios C Antoulas. Approximation of large-scale dynamical systems. SIAM, 2005 (cit. on pp. 4, 7, 2,9).
[20] Wilhelmus HA Schilders, Henk A Van der Vorst, and Joost Rommes. Model order reduction: theory, research aspects and applications. Vol. 13. Springer, 2008 (cit. on 4).
[21] Sun-Yuan Kung. "A new identification and model reduction algorithm via singular value decom- position"". In: Proc. 12th Asilomar Conf. on Circuits, Systems and Computer. 1978, pp. 705-714 (cit. on p. 4).
[22] D Friedman. "On approximating FIR filter using discrete orthonormal exponentials". In: IEEE Transactions on Acoustics, Speech, and Signal Processing 29.4 (1981), pp. 923-926 (cit. on p. 4). [23] J Bednar. "On the approximation of FIR by IIR digital filters". In: IEEE Transactions on Acous- tics, Speech, and Signal Processing 31.1 (1983), pp. 28-34 (cit. on p. 4).
[24] Bartlomiej Beliczynski, Izzet Kale, and Gerald D Cain. "Approximation of FIR by IIR digital filters: An algorithm based on balanced model reduction". In: IEEE Transactions Signal Pro- cessing 40.3 (1992), pp. 532-542 (cit. on pp. 4, 44).
12

---

[25] William Henry Young. "On the multiplication of successions of Fourier constants". In: Proceed- ings of the Royal Society of London. Series A, Containing Papers of a Mathematical and Physical Character 87.596 (1912), pp. 331-339 (cit. on p)
[26] William Beckner. "Inequalities in Fourier analysis Rn". In: Proceedings of the National Academy of Sciences 72.2 (1975), pp. 638-641 (cit. on 5).
[27] John Fournier. "Sharpness in Young's inequality for convolution". In: Pacific Journal of Mathe- matics 72.2 (1977), pp. 383-397 (cit. on p. 5).
[28] Tong S Quek and Leonard YH Yap. "Sharpness of Young's 's inequality for convolution". In: Math-
ematica Scandinuvica 53.2 (1 (1983), pp. 221-237 (cit. on 5). [29] Jean-Paul Berrut and Lloyd N Trefethen. "Barycentric lagrange interpolation". In: SIAM review
46.3 (2004), pp. 501-517 (cit. on p. 6).
[30] Marcos Vicente Moreira and João Carlos Basilio. "Fair and Square Computation of Inverse Z- Transforms of Rational Functions". In: IEEE Transactions on Education 55.2 (2011). pp. 285- 290 (cit. on 6).
[31] Henri Padé. "Sur la représentation approchée d'une fonction par des fractions rationnelles". In: Annales scientifiques de I' l'Ecole normale supérieure. Vol. 9. 1892, pp. 3-93 (cit. on pp. 6, 27).. [32] Ankit Gupta, Albert Gu, and Jonathan Berant. "Diagonal state spaces are as effective as structured state spaces". In: Advances in Neural Information Processing Systems 35 (2022), pp. 22982- 22994 (cit. on pp. 6, 24).
[33] Antonio Orvieto et al. "Resurrecting Recurrent Neural Networks for Long Sequences". In:
(2023). arXiv: 2303. 06349 (cit. on pp. 6, 24, 26).
[34] Jeffrey M Hokanson. "A data-driven McMillan degree lower bound".. In: SIAM Journal on Sci- entific Computing 42.5 (2020), A3447-A3461 (cit. on p. 6).
[35] L Ho and Rudolf E Kalman. "Effective construction of linear state-variable models from in- put/output functions". In: ul-Auutomatisierunsseeche 14.1-12 (1966), pp. 545-548 (cit. on p. 6). [36] Carl Eckart and Gale Young. "The approximation of one matrix by another of lower rank". In: Psychometrika 1.3 (1936), pp.
(cit. on p. 7).
[37]
Guy E Blelloch. "Prefix sums and their applications". In: (1990) (cit. on p. 7).
[38] Jimmy TH Smith, Andrew Warrington, and Scott W Linderman. "Simplified state space layers for sequence modeling". In: (2022). arXiv: 2208. 04933 (cit. on p. 7).
[39]
Noam Shazeer. "Fast transformer decoding: One write-head is all you need". In: (2019). arXiv: 1911. 02150 (cit. on p. 8).
[40] Joshua Ainslic al. "GQA: Training Generalized Multi Qutti--uerry Transformer Models from Multi-
Head Checkpoints". In: (2023). arXiv: 2305. 13245 (cit. on p. 8).
[41] Percy Liang et al. "Holistic evaluation of language models". In: (2022). arXiv: 2211 09110 (cit.
on pp. 8, 9, 96).
[42] Leo Gao et al. A framework for sew- language model evaluation. Version v0.0.1. Sept. 2021. /0/g//0..000 DOr: 10. 5281/ zenodo. 5371628. URL: https / doi org/ 10. 5281122111111 / zenodo. 5371628
(cit. on pp. 8, 96)
[43] Ari Holtzman et al. "The curious case of neural text degeneration". In: (2019). arXiv: 1904.
09751 (cit. on p. 9).
[44] Stella Biderman et al. "Pythia: A suite for analyzing large language models across training and scaling". In: (2023). arXiv: 2304. 01373 (cit. pp. 9, 36).
[45] Yuntao Bai et al. "Constitutional AI: Harmlessness from AI Feedback". In: (2022). arXiv: 2212. 08073 (cit. on p. 11).
[46] Alan V Oppenheim. Discrete-time signal processing. Pearson Education India, 1999 (cit. on 21).
p.
[47]
Lennart Ljung. System identification. Springer, 1998 (cit. on p. 21).
[48] RP Guidorzi. "Certain models from uncertain data: the algebraic case". In: Systems & control letters 17.6 (1991), pp. 415-424 (cit. on p. 21).
[49] Irwin W Sandberg. "On the theory of linear multi-loop feedback systems". In: Bell System Tech- nical Journal 42.2 (1963), pp. 355-382 (cit. on p. 22).
[50] Michael Zhang al. "Effectively Modeling Time Series with Simple Discrete State Spaces". In: (2023). arviv: 2303. 09489 (cit. on 24).
13

---

[51] Luca Perotti and Michal Wojtylak. "Matrix methods for Padé approximation: Numerical calcula- tion of poles, zeros and residues", In: Linear Algebra and its Applications 548 (2018), pp. 95-122 (cit. on p. 27).
[52] Amer Abu-Omar and Fuad Kittaneh. "Estimates for the numerical radius and the spectral radius of the Frobenius companion matrix and bounds for the zeros of polynomials". In: Annals of Functional Analysis 5.1 (2014), pp- 56-62 (cit. p. 27).
[53] Julia Eaton et al. "Polynomial root radius optimization with affine constraints". In: Mathematical Programming 165 (2017), pp. 509-528 (cit. on p. 27).
[54]
Gerlind Plonka and Vlada Pototskaia. "Application of the AAK theory for sparse approximation of exponential sums". In: (2016). arXiv: 1609. 09603 (cit. on p. 29). Jimmy Ba et al. "Using fast weights to attend to the recent past". In: Advances in neural infor- mation processing systems 29 (2016) (cit. on p. 31).
[55]
[56]
William B Johnson. "Extensions of Lipschitz mappings into Hilbert space". In: Contemp. Math.
26 (1984), pp. 189-206 (cit. on p. 31).
[57] Devdatt P Dubhashi and Alessandro Panconesi. Concentration of measure for the analysis of randomized algorithms. Cambridge University Press, 2009 (cit. on p. 34).
[58] Nya Loshchilov and Frank Hutter. "Decoupled weight decay regularization". In: (2017). arXiv: 1711 05101 (cit. on p. 35).
[59] Dale F. Enns. "Model reduction with balanced realizations: An error bound and a frequency weighted generalization". In: The 23rd IEEE Conference Decision and Control (1984), pp. 127-132 (cit. on p. 44).
14

---

LAUGHING HYENA DISTILLERY
Supplementary Material
Contents
1
Introduction
2
Preliminaries and Related Work
2
2.1
Long Convolution Sequence Models
3
2.2
Auto-Regressive Generation
3
3
The Laughing Hyena Distillery
4
3.1
Data-Free Distillation Objectives
5
3.2
Making Hyena Laugh with Modal Interpolation
3.3
Minimal Distillation Orders
6
3.4
Deploying the Recurrence
7
4
Multi-head Long Convolutions
7
5
Experiments
8
5.1
Pre-training
8
5.2
Distillation Analysis
5.3
Downstream Evaluation
5.4
Benchmarking..
10
6
Conclusion
10
A Linear Systems
17
A.I
Extended Notation and System Theory Preliminaries
17
A.2
Systems Norms
17
A.3
Transfer Function of State- State-Space Models
18
A.4 Truncated Transfer Functions...
19
A.5
From Transfer Function to State-Space
20
A.5.1 Isolating the hotterm from Transfer Function by Long division
21
A.5.2 Construction of the State Srate-Space from the Transfer Function
21
A.6
From State-Space to Transfer Function.
22
A.7
State-Space Representation of Truncated Filters.
23
A.8
Efficient Computation of State-Space Models
23
A.8.1 Fast Evaluation of the Transfer Function
23
A.8.2
Fast Companion Recurrence Canonization of State-Space Models
24
A.8.3
24
B LaughingHyena: Further Details
26
B.1 Parametrization of Modal Interpolators..
26
B.2 Distillation as Rational Interpolation
26
C Proofs
28
C.I Proof of Lemma 2.1
28
C.2 Proof of Lemma 2.2
28
C,3 Proof of Lemma 2.3
28
C.4 Proof of Proposition 3.1
28
C.5 Proof of Lemma 3.1
29
C.6 Proof of Theorem 3.2
29
C.7 Proof of Proposition 3.3
29
C.8 Proof of Proposition 3.2...
30
C.9 Proof of Theorem 4.1
31
15

---

D Experimental Details
35
D.1 Pre-training
35
D.2
Distillation Analysis
35
D.2.1 Pretrained Filters: Effective Dimension
35
D.3
Downstream Evaluation
36
D.4
Benchmarking
36
E
Additional Experiments
43
E.1
Associative Recall with MultiHyena
43
E.2
Analysis of Hankel Singular Values of Pretrained Large Convolution Sequence Models
43
E.3
Model Order Reduction of H3
43
E.3.1 Modal Truncation
43
E.3.2
Balanced Truncation
44
Authors Contribution
S.M.
Conceptualized the research; coordinated collaborations; lead theory development; conducted distillation experiments. Conceptualized the research; coordinated collaborations; lead the experimental (model pre- tre-training, distillation, benchmarks, downstream evaluation) efforts; coordinated writing and conference submission; optimized inference stack.
M.P.
D.Y.E.
Assisted in development of MultiHyena: assisted in pre-training and subsequent benchmarking of distilled models; assisted in writing. Developed benchmarking suite and interpreted results; assisted in writing.
H.K.
R.N.P.
Assisted in theory and algorithmic development;
performed model-order reduction experiments of H3 models; assisted in writing.
A.T.
Conceived and proved Theorem 4.1;
assisted in writing. Assisted in Hankel operator spectral analysis; Assisted in writing.
D.W.R.
Q.M.
Assisted in theory development. Supervised development of benchmarking suite and model deployment. Supervised theory development (solving associative recall with MultiHyena, Th. 4.1).
B.C.
A.R.
C.Z.
Supervised research; secured compute resources.
C.R.
Supervised research; reviewed manuscript;
secured compute resources.
S.E.
Supervised research; reviewed manuscript.
Y.B.
Supervised research; reviewed manuscript.
Stefano Massaroli, Michael Poli, and Dan Fu contributed equally to this work. Christopher Ré, Stefano Ermon, and Yoshua Bengio share equal senior authorship. All authors read and approved the final manuscript.
16

---

A Linear Systems
A.1 Extended Notation and System Theory Preliminaries
We first introduce the notation and some mathematical concepts that will be used throughout the paper. By & we denote the set of integers, by R the set of reals, and by C the of complex numbers. The variable t stands for time. fp(Z) denotes the Banach space of complex-valuee sequences (2t)tez with finite energy, i.e. ||æ||pp- == 1Erez | < oc for some 1 S P < co. (Z) is instead is the space of sequences for which ||]|| = suPtez [zel < 0c. With S denoting the unit circle in the complex plane, S == {= E C
1} we define H,(S) as the space of functions X from C to itself such that 1 ((12mm [ (((e))) 1/p < oo and (S) the space for which =
|X = sup (x) < co. Particularly, K2 is a Hilbert space with inner product (X, Y) = (1/2n) X (((e"))Y((" (Y (e"")dw dd where "=" denotes complex conjugation. Although we acknowledge we are using the same notation for norms in both (Z) and (S), the correct meaning will always be made clear by the context. The Z-transform of sequence x (2z) is (x) [[x](z) -iez Tx= We embrace the system theory convention of using capital letters to identify transformed sequences. The Z-transform
projection of the sequence onto basis of powers e = r- r-ciur This basis is not orthogonal unless r = 1. That is the basis of the discrete-time Fourier transform F. Hence, F is defined as
(e (ex) X x)) == Eiez Zye twt, The discrete-time Fourier transform is an isometric isomorphism between (Z) and Lz)... We say that sequences live in the time domain and their Z (or F) transforms in the frequency domain.
A linear system is linear operator transforming an input sequence u an output sequence y. If the sequences have continuous support, i.e. t raagees over a continuous set (e.g. R), we have a continuous- time system. Conversely, if the sequences have discrete support, i.e. t ranges over discrete set (e.g. Z). we have discrete-ting -imce or digital system. In this manuscript we restrict ourselves to discrete-time systems. Systems can be single-input single-output (SISO) if u and y are scalar functions or multi- input multi-oulput if either u or y are vector-valued. We limit our discussion to SISO systems. The impulse response of a system is the output sequence y when the input sequence u is the Kronecker delta function 6, and is usually denoted by the letter h. The values h2 of the impulse response sequence are also known as the Markov parameters of the system. The most common mathematical representation of a linear system is its convolution form: y h * u, i.e. V1 = Ejez h Ejez hyUe-j, t E Z. In matrix form the input-output relation is given by the Toeplitz operator T corresponding to the (possibly infinitely long) sequence h, i.e. y = Tw.. Taking the Z-transforms, we can write the input-output relation (2) (z) (this is just the Fourier convolution theorem extended outside the unit circle). (x) is called the transfer function of the system. When 2 = e² ((e")) is just the discrete- time Fourier transform of h which is called the frequency response of the system. A linear system is causal if hT = 0 for t < 0. A system is called stable if the T is a bounded operator. If u, y E (z(Z), then stability implies h E foo. In the following, mainly focus on causal stable systems.
A.2 Systems Norms
When quantitatively characterizing linear systems, several norms play crucial role. These norms provide measures of various characteristics of the systems, which are essential in both analysis and filter design.
The l2 and H2 norms As defined above, the l norm represents the energy of a signal h,
|AAll2 = |m]]] 1/2
while He is the energy of the (continuous) spectrum of h.
|||l = 2n /
[X ddw 1/2
By Parseval's 's theorem, the & and Hg norms are equal, ||Al|2 = || Further these norms are useful study the approximation of convolutional filter. The following holds:
Lemma A.1 (Log output error), Consider the class of lg measurable inputs such that ||ull2 S S. for all H, H H2,
ly - Ó11o0 S S - f111
17

---

Proof.
sup
1tt
8: = =sup
y(e - 8 ) eiul dw
t>0
1>0
2T
-1
[Y() - -((e
$ 2T -1
[" [H()l) -H -E((ee)
2m
1/2
] 1/2
(H(e ()
1
/
(U(e(r) [dw
Hölder Inequality
2T
2m
1/2
[H(e - /e
||1/12
Parseval Theorem
2T
C| - H1 1196
u the unit impulse function dn = 6, then Ç = 1. The results also holds for finite sequences of length L using the discrete Fourier transform.
Lemma A.2 (Impulse response error on finite sequences). Consider filters h, h with finite length L.. Then, the following holds.
||- 1h-hllos S || l]2
where H and H denote the discrete Fourier transforms of h and h, respectively.
Proof.
L-1
lly V1100 sup t>0
1
del
sup
Yn Pn
elennt/L
1>0
2n
n=0
1-1
1
Σ
Σ
Yn - Yn1
2n n=0
L-1
1
Hn H UU
2T ==0
1/2
1/2
1
HH, H2)
U2
Hölder Inequality
2x
2x
n=U
1/2
(Hn H3
||u//2
Parseval Theorem
2x
H A1l
using ||u||e =
A.3 Transfer Function of State-Space Models
The transfer function (3.1) is derived by taking the z-transform of input and state, U(2)
X(() = [x). Plugging (z), X in the state equation (2.2), it holds
xx(=) = (x (z) + (U) + X(z) = (2l BU
Substituting in the output equation yields
Y(z) C(zl - A)- A)- U()
The transfer function is then defined as
(() H(z) U(2) C(2l A)-
B + hn-
(A.1)
The transfer function can also be derived by direct z-transform of the impulse response fú, of the system. This derivation is useful to highlight the region of convergence of the transfer
Alternative derivation
18

---

function.
2
H(z) = hoo
- CA'
C
ho pulled out via h2zz ho
= ho -
A A 1-1
B
multiplication distributes over sum.
1=1
(A.2)
ho
- -
(t-1)
A1-1
B
multiply by z/2
00
ho x c
A)
B change of index and collect like terms
1=0
We look at the convergence of the series
>
t= ||
AA We have
||> ||2 - ||= ||2|||||2
||r iw |2|||112
using = = re EG, r,wRR
||Al2 rr p(A)
The series converges to 1/(1 - r- exterior of the disk with radius p(A), PP(()) = {z C |2| > p(A)), Eizo A2) converges
((1---(p(AA) p(A)) if and only if ((rr1((A) < <.i.. for > p(A). Thus, in the
(I 1----Ap (A)=-AA)-1 and
ho + C(al A)- The transfer function (=) = ho + C(al - -B of a stable lumped discrete-time system is defined outside the disc in the complex plane that encloses all the eigenvalues of A.
2 E P(A) = H(2) ho + + --
(2) as defined in (A.1) 1) is a proper rational function of z. In case hg 0, (2) 2) is strictly proper and the denominator monic:
Invariance of the transfer function
ba--d
H(2) 11ta2 +
(A.3)
0,2 Specifically, the denominator could be derived from A with det(z1 - A). and the numerator is det(2l A BC) det(21 - A). We provide a detailed derivation below in Section A.6. While state-space representation involves the analysis and synthesis of model matrices A, B, C, the transfer function is entirely characterized by the coefficients a (am))==1 polynomials. Notably, the transfer function is an invariant of the system: if we apply a change of variables to the state, the transfer function remains unchanged.
(b,) of numerator and denominator
Lemma A.3. Coefficients a, are invariant under any invertible change of variables.
Proof. The proof can be found in [5, pp.95] and follows from the definition of equivalence transforma- tion. Consider the space matrices of under change of variables á Kr.
À = KAK-1 B = KB, C CK-1 ho = hg- The resulting transfer function H (2) can then be computed
(2) C(2l - + ho CK CK- A)K--IJ----- + ho (2)
A.4 Truncated Transfer Functions
the case of generic truncated (finite) impulse response filters, such that h, = 0 for all t greater than a certain value I. (which refer to the length of the filter), the transfer function is simply polynomial in the complex variable z of order I., i.e.
H(2) Σ h,2
ho + h12 + h
(A.4)
t
t=
In case the filter is generated by a finite dimensional (lumped parameters) system, i.e. h4 = CAt-1B t 1, I...., L, then (A.4) can still be represented exactly by rational function of order d.
Le. such that the denominator's order is not less than the numerator's one.
19

---

Lemma A.4 (Truncated rational transfer functions). Consider the L-truncated impulse response he E (2) of a lumped-parumeter filter (A, B, ho),
ho t=0
he CAL-IB
1565b.
t>L.
Then its truncated transfer function is
(z(z)= = (z) ho + 2(1)2= AB
Proof. By definition of z-transform we have
80
HT(z)
Σ h4z = ho +
Σ
BB
(A.5)
1
L-11
= ho + C
Σ
B = ho + -C
Σ
A=
B
The sum E1=0 (z A)* a partial Neumann series and can be manipulated follows.
1-11
L-1
L-1
Σ
(2
Σ A) E(=
= (2 AA)
Thus,
L-1
Σ (x= = (1 (1- 21---~A-77 -2
1=0 which plugged in (A.5) gives (z) ho C(I (=) - A)-LB, proving the result.
Because of truncation, evaluating the transfer function (z) on the T. roots of unity elwk, WK 2 for k O.... gives the length-T. discrete Fourier transform (DFT) of the filter:
---1
H = (c(ww = Σ h 12tk/L
1: O....,
practice, this means that H E Ch. is the FFT of h, H = 2 If we can find an efficient and stable algorithm to evaluate H from the system matrices (A, B, C, ho), then the FFT-based convolution of truncated filter with input sequence RL can be evaluated in Ö(T) time.
Reparametrization Assume training LCSM equipped with SSM filters with input/target sequences to be all of length L (smaller sequences can be padded with zeros to the maximum length). Thus, for training purposes, we are only interested in evaluating H for the FFT-based convolution.
The truncated transfer function H2 is equal to the original one with a correction term - 2 -LA on the numerator polynomial. As already noted in S4 [6], 2
conveniently equal to one on the roots of unity, zina = e 12nk 1 for all k O...., L - 1. Hence, the correction term due to truncation becomes constant: H₃ C(I (exp(( behaves the infinitely long one with a perturbed C matrix
L)I - A) in DFT domain the truncated filter
C= C CA-
If aas assumed- the SSM is stable p(A) 1, (i) the transfer function is defined on the unit circle, term CA- will go to zero exponentially fast as T. - оo and C = C (as expected). As advised in [6]. it is desirable to parametrize directly C; the expensive computation of the correction term C(I A4) never carried out during training. Instead, the real C matrix can be retrieved for recurrent inference by inverting the correction term C C(I A A -1, always invertible for stable systems although possibly ill conditioned by eigenvalues too close to the stability margin (the unit circle).
A.5 From Transfer Function to State-Space
Suppose the coefficients of the numerator and denominator polynomials a proper transfer function H is given:
(z)) = by + b + ba2-d
(A.6)
1 a12-1+
aqz-dd
A state-space representation of the form (2.2) can be rapidly realized in two steps:
20

---

1. Get delay-free path From (A.6) we first notice that the bias term fu is ho = by. We thus want to isolate by from the rest of the numerator. This can be obtained via long division (see $A.5.1) and results in
H(=) 31= + + BN== bo, Bn = bn. by 012
(A.7)
+ ad2
2. Get state-space matrices Given the transfer function (=)) with the isolated pass-through coeffient by as in (A.7), we can construct the state-space matrices by companion canonical realization:
Q1
a2
0d-1
0d
1
1
0
0
0
0
1
0
0
(A.8)
foo
81 _3
Ba-1
Bd
bu
Details on the complete la [5] derivation can be found in $A.5.2. linear system with finite- dimensional state can be equivalently characterized: by its state-space matrices (A, B, C, ho), by its impulse response function h, or by the coefficients a, b (or 3) of the transfer function. A fourth repre- difference equation form
sentation is its
Σ b3
Σ aşbt-s. n=1
==0
typically used in signal processing literature in the theory of infinite impulse response filters (see [46]) and known, in the context system identification of error-in-variables models, as auto-regressive moving-averen filters [47, 48].
A.5.1 Isolating the ho-term from Transfer Function by Long division
If the rational transfer function (=) accounts for the ho term, then simply proper (order of nu- merator equals the order of denominator), ho is necessarily ho by (the delay-free path). Given the transfer function in this form, we can isolate the bo term and the strictly rational term of (A.3) by long division. We start by expanding the fraction
q(2) bo
biz + + baz
((2)
p(=)
p(z)
p(2)
and
bo
bozdd
p(2)
2d + a1 2d
ad
We then use the long division method to compute bo/ p(=):
bo
d + a1zdd11 + + au b
b
bba d-1 + boad byus
bnu12d11 pd-1
(reminder)
finally get
boarz d + + bood
+ b1z
+ baaz
(22) bn 2d aj
+ ad
p(2)
bo (bi bnai )= -1
(ba booa)=-d
+ 01 + ... + 022
Note that the coefficients b, in (A.3) correspond to b, - bya, (A.6), bn + bn - boa is indifferent parameterize the coefficients of the transfer function in either forms. However, if choose the simply proper representation (A.6), we need to apply the derived correction factor to the numerator coefficients when separate the ho term and strictly proper part of H()).
A.5.2 Construction of the State-Space from the Transfer Function
Chen's derivation The derivation is based on the steps reported for the continuous-timm multi-inpur multi-output case [5]. First, define pseudo-state such that
(z))V(z) = (2)
V(2) p(z) (z).
(A.9)
21

---

Then, we define the state = (a).....,,2
x4) E R as
= It = (V/-1, 01-1, Ub-d) + =(z)(2)=X()))
V(z).
(A.10)
From (A.9) have
(z) + a1 (z)) ... add ((z) Uz) $
((z) - Vz)) -... 0,d a V2) + (z) +
0y = 1118
0,114 + ut e
time-delay prop. of Z-transform
1++ = -
ag d + U2
+
by def. of state (A.10).
Thus, we have the overall recurrence
"41 a1
azal + ute
2 z
d-1
T f+1 2t
which can be written in matrix form
02
NN
0
0
T++1
Itt +
The output spectrum is then given by
((2) = (=))U(=)) = g(2) U()) + bot(2)
p(z)
= =<==V((2)+ + (x)
by def. of V(2).
Therefore,
2
((=) (<))V(() (z)(2) [81 32
BN]
v(z) boU(22
= [3 82 and the output equation in time-domain is given by = [3 32
Ba] X()) + bbU(2)
Ba] xe + boue.
yielding state-space matrices (A.8).
A.6 From State-Space to Transfer Function
We detail an implementation oriented method to compute the coefficients (a,))= (bw) of SSM's transfer function. Recall that
(2) Clzl - ho Cddj A)B + det(21 A)/o
(A.11)
det(=l A)
Hence, the denominator coefficients (a,)) are simply the coefficients of the characteristic polynomial of matrix A. They can be casily obtained by 1. computing the eigenvalues of A and 2. calculating the coefficients of the polynomial whose roots are such eigenvalues. On the other hand, the numerator apparently involves more complex symbolic manipulation. This can be simplified recalling classic matrix-determinant identity:
Lemma A.5 ([49]). Let M, B, and C. respectively denote matrices of orders d x d, d x 1, and 1 x d. Then,
det(M + BC) = det(M) + Cd)
Applying Lemma A.5 to (A.11) we obtain
det(zl A BC) + det(22 - () 1)
H H(2)=
det(2l - A)
22

---

Let poly(r) denote the coefficients of the polynomials with roots (r1....,,aa) Then poly(eig(A)). Since A and A BC are of equal dimension, their characteristic polynomials have equal order and therefore
poly(eig(A BC)) (o)) -)
Listing 1: State-space - transfer function conversion code
def get tf_frfffffs___eeeeoeees_ss_s_ss BA,,,C, = poly(eig (A))
b poly(eig(A) outer(B.C)) (h0-1)*a return a, b
A.7 State-Space Representation of Truncated Filters.
A truncated filter ho,...,,u hr as the ones found in any standard convolutional neural network can be represented by I-dimmeniooal companion canonical SSM. The filter's transfer function (7)) ho + 1 ...... + , is polynomial, i.e. a rational function with the denominator's coefficients set to zero. Following the canonical realization process detailed in Section A.5, the truncated filter has state-space form:
0
0 0
1
0
0
1
T++1
Dt +
0 0
hh h2 If so O2 and un for negative t, then at each t >> 0 the state is shifted copy of the input sequence
hr] De + hggt-
= (ur-1,... 1)) ) E 4R Nonetheless, the asymptotic complexity of computing one recurrent step is (L) requires only shift operation and a length-L dot product
1t+ u
rt+
2:L shift(x;)
(A.12)
Y1 (h1.t, 2t) houe.
The memory footprint is also ((T.). In [1] it is proposed the use of shift-type SSMs to parametrize one the filters of the H3 block.
A.8
Efficient Computation of State-Space Models Fast Evaluation the Transfer Function
A.8.1
Computing (z) at any point= 2 E C concerns the evaluation of the d-order polynomial of numerator and denominator,
((3)
E
b
H(2)
p==)
1+ an
In practice, we are mainly interested in a fast algorithm that allows computing H on the L roots of unity to obtain the DFT of the filter. The DFT of the filter can be then readily used to perform a FFT-based convolution with length-T. input sequence u or to recover the impulse response function via inverse DFT. We prove the following:
Lemma A.6. Given the coefficients a, of the transfer function, the frequency and impulse re- sponse of the filter can be evaluated ((L) time.
Proof. The result proven showing that the transfer function can be evaluated in Ö(L) time on the roots of unity. The fastest method to evaluate polynomials on L arbitrary points 2 of the complex plane is generally the Horner's scheme. This method based on a sequence of nested multiplications and computes the polynomial from its vector of coefficients, delivering time complexity of O(dL). More explicitly, Horner's scheme determines p(z) as p(2) = ((-.- ((a.z- + ag-1)² Each step involves multiplication and an addition, making total of 2d operations per evaluation point. Thus, for points, the total number of operations amounts to OdLL).
+
Effectively, Horner's approach implements the matrix-vector product of an L-by-(d + 1) Vandermonde matrix V (4x(1+1) constructed by L evaluation points (2o...., ZL-1) with the vector of coefficients
23

---

a = ad)
p(=0) (=1)
1
0
0
0
d
R1
2
21
Q1
Va
((2--1)
2- 2--1
Significantly, if the polynomial is required to be evaluated at the roots of unity, the Vandermonde matrix simplifies corresponds to the L (d 1) DFT matrix. Further, zero-padding the coefficient vector length I,, enables the use single length-I. FFT to compute the matrix- product in ( time. Thus, the numerator and denominator polynomials of the transfer function can evaluated, on the roots of unity, in (L) time by taking the FFT of the padded numerator / denominator coefficients a, b and subsequently dividing element-wise the sequences FFT [b) [b)/FFFF..l The overall time complexity obtain the impulse response is also (L) since h can be recovered taking an inverse FFT of the frequency response.
A.8.2 Fast Companion Recurrence
The recurrent step of a generic SSM (2.2) with dense system matrices usually requires (dP) operations due to the matrix-vects vector product Az, We show how the recurrence SSMs companion canonical form, i.e. with system's ss matrices (A.8), requires only (d) operations.
Lemma A.7. The recurrent step of state-space model companion canonical form (A.8) can be evaluated in (d) time and memory.
Proof. The companion state matrix A can be broken down into a lower shift matrix Ly and low-rank term. Particularly, with er the first element the canonical basis of R-N and a (01,..., aN), we have
A = LN e1 X a.
It follows that the recurrent update can be simplified
x++1 (Ln e @ a) de + Bu,
1/1 Cz, + boue
The peculiarity of this formulation is that we never need to construct the matrices to perform the recur- rence. In particular have:
12+1 U1 a Te 2 = shift(wxx)
= B3 xe + byyet
Thus, each step only requires two inner products (d multiplications and sums each) and one shift operation, totaling (d) operations.
The proof of Lemma A.7 yields the practical implementation of the recurrence:
Listing 2: Python implementation of the companion canonical recurrence
def sx, alpha, beta, bo):
y dot dbeta, x) + b0
Ir = dot x) x rxll(x) x[0] lr return x,
A.8.3 Canonization of State-Space Models
The companion canonical form discussed in Section A.5 is the ideal representation to deploy SSM-based convolutional layers: i) comes with a (d) fast recurrence and ii) allows swiftly switch between time and frequency domains with a direct mapping between state-space matrices and coefficient of the transfer function (which in tum allow ((L) fast convolutions).
layers companion canonical form, all the other parameterizations [12, 6, 32, 17, 33] can be converted (canonized), under mild assumptions.
Aside from [50], which directly parametrizes

---

Lemma A.8 (Canonization of SSMs). Any state-space model (2.2) with proper transfer function can be converted in companion canonical form.
Proof. The result can be proved following the two-step conversion process.
1. Get the coefficients of the transfer function: Given the original state-space matrices (A, B, C, ho), the transfer function is given by (z) C(zl A) + ho- A proper ra- tional function has the form (z) = (<2)/p(2) where the numerator g(z) has coefficients (an) (0g = since p monic). As shown in Section A.6, the coefficients of the transfer function can be extracted in closed-form hoy) and = poly(eig(A))"*:
= (b,) and the denominator has coefficients
as b = poly(eig(A BC)) + poly(eig(A))(1
2. Construct companion matrices Given the coefficients a and b a new set of canonical state- space matrices which realize the transfer function can be obtained following the recipe of Section A.5.
The resulting companion SSM is equivalent the the original since they share the same transfer function.
(A) contains the eigenvalues poly(r) yields the coefficients the polynomial whose roots are the elements of r Cd.
25

---

B LaughingHyena: Further Details
B.1 Parametrization of Modal Interpolators
Complex-conjugate states Assuming even distilling dimension d, we pick poles An and residues R., in complex-conjugatt pairs:
A diag(A1, Aa/2, Xi. ;
.1a/2)
C 1 [R, ... Ra/2, Ri Ra/22
(B.1)
2
which allow partitioning the state-space matrices as
X
A =
- R R*) X
(B.2)
where
== diag (11 Aaa2) and R = [R Ray2]
(B.3)
If we also partition the state as x (z, R), H, C//22 the resulting recurrence has the form
Tz+1 XT: 14/2
(B.4)
i++1 X x= + 2/22 14
We have
t-1
32 = X 8o + Σ
X 1
4/2 f = (2
1a/2
(B.5)
j=0
J=0
Thus, if To T.. then _n = o for all > 0. Hence, at inference time we only need to propagate
forward half of the state say x and then compute the output as
Yt = Du, + [RT, + R));)
(B.6)
= Du; + ((RE,))
Du, R( (()))(E - {
This parametrization allows to update only half of the state, reducing the time and memory cost com- pared to unconstrained linear system with complex coefficients. However, the implicitly achieved realness of the output (assuming D = bu E IR and i E R) comes at a cost of expressivity: such a system is equivalent to an unconstrained complex linear system of dimension d/2 of which we only keep the real part of the output.
Poles and residues For the modal interpolation, the parametrization is analogous to the one of a diagonal state space model [33]. Poles Å, and residues R. need both be complex numbers. In [33] the authors suggest parametrizing real and imaginary components of B and C matrices while representing the eigenvalues An polar form, An Tne e with rn and an being themselves exponential functions of the actual trainable parameters, Fn = e e-e" On = ecn leading to
An = exp(- cxp(-cxp(f%) + cxp(Cn)) This ensures stability of the poles [Aml < and positive-only phases an, For the purpose of distillation we propose simplified parametrization as follows:
(xp
Vns Sn ER
(B.7)
1. We only parametrize the C vector. Parametrizing both and C redundant and increases the computational cost of performing each step of the recurrence. The residues R, correspond in fact to R2 = C,, B, of a diagonal state space model. Setting B = 1a saves parameters without harming expressivity. Further if B is different from 1 needs to be multiplied u, each recurrence step. C, = Rr = R[A] + iJ [..] and R[n,], [[R.] are the trainable parameters of the residue.
2. For the purpose of distillation we have no benefit in forcing the eigenvalues of the model to be stable, ie. constrained to lie strictly inside the unit circle. Instead, such constrain may actually harm the expressivity of the approximant. We choose the the simpler parametrization
An = e"" Tn, On E R.
B.2 Distillation Rational Interpolation
Distillation as rational interpolation Approximating filter with an SSM can be thus achieved by fitting a proper rational function to the (truncated) transfer function of the original filter -1)==EE ht That is.
26

---

Find a, such that hg h,= +
= ho P
(B.8)
A modern" 15 way solve this problem by H2 error minimization via gradient descent We use the Fast Fourier Transform (FFT) to evaluate both the target and distilled transfer functions and solve:
min a.DERd
Σ DIFFT - ho (FFTT())/FFTT..44)
(B.9)
k=0
To ensure stability of the distilled filters and well-conditioned gradient descent dynamies, the roots of the denominator polynomial must strictly lie inside the unit circle (p(A) < 1). This, in tum, requires constraining the coefficients a into the region {a poly(a) stable) which is by itself open research problem [52, 533. Experimentallyy we observe that standard coefficient normalization techniques overly restrict the parameters space and lead to poor distillation performances at reasonable order.
In the late 19th century, Henri Padé had already proposed closed-form solution of the above problem that achieves o(2 o(2-1) "' error for + oc using I=2dd samples of impulse response. His method [31] solves a dimensional linear problem that, however, is known to often become numerically ill-conditioned even with small d [51]
IIn the case of finite sequences, the H, norm becomes standard Euclidean metric evaluated on the L+1 roots of unity.iee. ( [d (1(()rt((++))))))
27

---

Proofs
C.1 Proof of Lemma 2.1
Generating K tokens with long convolution layer (2.1) from length-7 prompt has time com- plexity OTog,, T+TK+KK +2) and requires (T. memory.
Proof. We compute the time complexity memory of a length-7 prompt processing (pre-filling) and subsequent auto-regressive decoding of K tokens. The auto-regressive generation of long convolution computes the next token as by
= T
1/- bz
(C.1)
j=0
The pre-filling step is needed to prime this recurrence by computing the first T outputs till yr-1 from the length-T prompt u. This just a convolution between two length-T signal and requires ( log, T) time and linear memory. The auto-regressive decoding of K tokens requires K steps (C.1) with the length of the sequences increasing by at each step. Thus we have total asymptotic complexity of
1 TK K(K + +).
Σ (T
(C.2)
and requires worst (k K 1) to store the length T + K L generated output sequence, i.c. OL)) memory. In the limit we thus have total time complexity of O(T log, T TK + K²) and (L) memory.
C.2 Proof of Lemma 2.2
Generating K tokens with a SSM (2.2) from a length-T prompt has time complexity O(Tlog, T+dK) and requires (dd memory.
Proof. In autoregressive mode, the cost of generating one token is the cost of evaluating the state re- currence (2.2). Each step then requires (d) time and memory for the class of SSMs considered in this work (see Lemma A.8). Hence, generating K tokens costs (dd)) time and constant ((d) memory (we only need store the current state).
The recurrence is initialized for autoregressive generation with the post-prompt state TT- and output
Vr-1- The latter can be recovered in linear time and memory OTT)) by definition yr-1 Σ/= hリー (assuming to have the impulse response h available) and state TY-1 in ((T)) time and d memory through the recurrence. The overall asymptotic cost therefore (dL) time and ((d) memory.
Note that, for prompts and SSMs of practical sizes we usually have d > log, T. In such case the state 2T-1 can be computed in T Tolog2 T time rather than d'' by Proposition 3.2.
C.3 Proof of Lemma 2.3
Generating K. tokens with self-attention from a length-T prompt has time complexity O([++TK+k*) and requires (L) memory.
Proof. The proof is identical to the one of Lemma 2.1, with the only difference of a quadratic asymptotic cost (TT2) to process the prompt obtain the kv cache.
Self-attention suffers with long contexts: it is significantly more expensive in prefilling than long convo- lutions and SSMs due its quadratic cost. Nonetheless, in autoregressive mode, self-attention reaches the same overall asymptotic complexity O(TK + K2) as long convolutions (with the memory overhead of having cache and v).
C.4 Proof of Proposition 3.1
has semi-simple eigenvalues An E C. then the transfer function the system can be de- composed as H())= Σam1 Rn/(z Xn)) where R, E is the residue associated with the pole
Ap-
28

---

Proof. If A is semi-simple, then is diagonalized by a basis V of eigenvectors; it admits an eigenvalue decomposition (A VAV where À (AI..... Aa) C contains the eigenvalues of A. Pro- jecting the state onto the basis of eigenvectors, = modal form:
Vx, the state space model is is transformed into
St+1 = VAV 3t + VBu 1/ CV- 8t
s++ = diag(A): + Bu
Vt Cst
where B VB (6m) and C = CV-1 = (cn d n=1- In modal form, the state equations are decoupled, i.c.
8111 An + b
V1 Σ Sn
Taking the z-transform of the output equation and each state equation yields bn
(x(2) (=)
I...., d (())
An
((=) = Σ SnSa(z)
Thus, the overall transfer function is n=1
Y(2) H(=) U(z)
2 An
Letting R, = Cn, proves the result.
C,5 Proof of Lemma 3.1
The distilled filter in modal form (3.2) can be computed in (dL) time from its modal form and in ((T)) from its rational form.
Recalling (3.2), h = Σ Ra>;11 Rn, An E C, 0, the OdL) complexity of the impulse response is apparent: for each of the t= 1..... L. h4 can be computed in (d) time. The (LL) cost from the rational form follows by Lemma A.6.
C.6 Proof of Theorem 3.2
Let be length-T. filter, à distilled filter of order d < T. and let Sr, S₁ be the respective Hankel matrices. Then infg, ||, Sr.12 = ad.
Proof. The theorem characterizes the best-case scenario in terms of approximation error the distilled SSMs or a certain order d where it is clear that rank < d. This theorem a direct application of the Adamyan-Arov-KKrt (AAK) theory of infinite Hankel operators [7]. Let $;, = arg infs, ||S - S ll the AAK theorem says that every causal system can be optimally approximated by another causal system of lower dimension. Optimal here means
inf ||S $ inf SSS K||
where the first infimum is taken over all Hankel matrices S and the second over all arbitrary matrices K (see [19, Chapter 8) and [54] for further details and references).
C.7 Proof of Proposition 3.3
The filter (3.2) has state space matrices = diag(Ai...., de) E Cddd B (1....,1)² 1)T Cdx1, C = (RI,..., Ra) E clxd ho whose step can be evaluated O time and memory.
29

---

D is set to hg by default. The result is proven showing that (3.2) can be written in the form hn = CA for t > O. choose A diag(A) then the impulse response becomes
h Σ R C[diag(A))*
Σ C.B.A
The choice B, 1 for all n 1,.., d. space realization of the distilled filter. The (dd) time complexity of the corresponding recurrent step is guaranteed by the decoupling of each state equation from another,
B la and Cn R. finalizes modal canonical state-
................................
F++1 An + ut n2 ma=1... ln.....,
d
/1 Σ
Rac + haue-
==1
Each of the d state equations can be computed (in parallel) O(1) time. The output equation is a dot product requiring d multiplications and d additions, hence the (dd) time compexity of the recurrence.
C.8 Proof of Proposition 3.2
Fr (er...., or-2) where = * u and is the filter whose transfer function is 1/den( (H) and can be evaluated in (
Without loss of generality, let assume have converted the distilled filter in canonical form (i.e. have unrestricted access to the coefficients of the rational transfer function) and let D = 0. We use the notation of Section A.5. In z-domain, the state-to-input relation is given by 3d] (()
(=) Cx [31
On the other hand Y(=) (=) = (())/p(=)U(()) Therefore,
[3| Xa) g(2)
U(2)
p(2)
<> 131 Xx) 13
Bd]
p(z) (()
2
+ X(z)
U(z)
p(=)
Let U())p(( From the shift property of the z-transform it holds,
=(x)(=)= X(===
V(2)
(1- 12 . ve-a) 1i > 0.
can be obtained in ((L) time via an FFT-convolution of the input and g, the filter resulting from inverse transforming 1/p(z). The proof is convoluded setting =
30

---

C.9 Proof of Theorem 4.1
Notation. We will be denoting the all row vector of size k. given by [1 row vector of size k, given by [0
1], and the all 0 0J. as 1st and 0", respectively. We will also construe the standard basis vector e; column vector in these notes. Next, we will adhere the following matrix indexing convention: Azj is the entry in the ith row and the jth column, A[i, E Fixn denotes the ith row, and A|::j] E F=xx denotes the jth column of A E Fm Here, we also use 0n E _ and In to denote the matrix of all zeros and the identity matrix of dimension n, respectively. Moreover, we extend the outer product between two vectors to a tensor product using the symbol @, the computation of which is carried out batch- match-wise with some dimension of one or both of the imput tensors. Finally, we express the binary encoding of e [n] in row vector form, given by B, E Zz"", where Py is the closest power of 2 to n.
Language and Model Description. The language A has s keys and values: LK == (ki,-..,k, Lv == (UI,..., ). Formally, the language A consists of sequences x E (Ix x Ivv)*
L. where there is an associated mapping fa : I.K + Lv For each sequence, the odd indices in [T.] belong to L,K, for 33, JL, and we define
(C.3) The last item æt E { 23.,2...... ,.,...,,,IIII,, IL-1J, called the query, must be one of the keys that has appeared in x already. Our goal is to produce (x() at the end of the sequence, which we refer as the associated value. This problem is termed as the associative recall problem [55].
T2.4 = (=
We will now outline the Hyena layer [2] with multiple heads as follows.
Algorithm 1 Hyena
Require: Input sequence E RLLDD from the previous layer, long convolution filter The number of heads M.
1: q"h, kmm vm +- Projection(u) for m E [M]]
2: for m m......, M do
3: Perform the outer product = + 1m @ VTTh E RLNNNN where N D/M,
4: Apply the convolution independently and compute yft <- (2] )0 E RLLN
5: Average the output y < (Em) /yMMMM
6: Retrieve the value f(k) of the key kg from :[.
In order to prove Theorem 4.1, we need the following technical statement concerning sparse recovery of heavy-hitter.
Proposition C.1 (Heavy- Hitter Recovery). Let x E R' be a vector with one entry bounded by + 3.. refeerre as the heavy-hitter and the rest of the entries bounded by 1 Then, there exists a matrix 5(m) E TRexO((alog e) such that the position of the heavy-hitter in x can be inferred from the average of M measurements with S 5(m) given by
/M with probability of error S 1
Before presenting the proof of Proposition C.I, we use it to prove Theorem 4.1 as follows.
Proof of Theorem 4.1. We take D O(v' 8) and M- 243 log so that N Olv's log s) and use the same projections and filters for each head, We will start by describing the projections of the input. To this end, let E [4] + 2s define a map from the row indices of to the keys kÜ and values fa (k,) given by
t odd, It = ki, E(t) 1 lits, t even, xt-1 ks.
(C.4)
Here, we note that we also have
F((1) F(t - 1)+ even
(C.5)
as the even indices are defined as x; = (=( )) for t even (C.3), whence Tz-1 E T.K as a - 1 is odd. Next, we can separate the keys q. queries q and values from the input sequence u. For keys and queries, we will be using the Johnson-Lindenstraus embedding [56]. We state its guarantee here.
For a set of points P C R2, let e, 8 > with k > 21n (2x) /62, and ʃ R + R2 be the randomly constructed linear map from [56]. then with probability of error S 8, we have
(f(x), - (z, (x. Se
31

---

for all x. P.
More precisely, we take R E (oo(vllog))) x)x* to be the matrix representation of f with =
and
3
8 == for some e that R[:, f(e,). Thus, we define
R|: E(t - 1)}, 1tt-1)5
q [t.
(C.6)
0, For values, we use the heavy-hitter recovery matrix as described in Proposition C.I so that we have (5(m) (Et),))
otherwise.
E(t) >
[t,:]]
(C.7)
otherwise,
Further, using DDConv (equivalently, in terms of polynomials, h(X) == X), we can shift the queries get the projection for keys k so that we have kn [t [t 1,
The Hyena filters, along with the specific convolution being performed by Tı are specifically described in terms of polynomial multiplications, for all m E .,...: ., as follows.
Tx(X) = E
x
==0 Here, we note that (T) takes the cumulative sum over the input. That is, for all i, we have
[u( = Σ w
==
We will now compute TMh as follows
km nm
Further, applying the convolution, we get
Tn(2;")
km hn
09 [t,:]
i=0
For inference, it suffices to show that the last row of the output y recovers the output with high prob- ability. Indeed, let l' E [L] denote the row index of the value associated to the query such that the corresponding key has the following relation
u1-1 = un-
(C.8)
Finally, we multiply by the query q across L. Specifically, we now look the computation of the Lth row of y:
[L, =
[t :] 2 00 [t, [t,
(0T [[L,; [t, [t,;:
(9 [t' 1,:1 n [t :l:) 8. [t.:
(C.9)
1=0
Σ
((R); E(t' - 1)1) TR; 1)]) ((m)
(C.10)
<E[L]
Σ
Re Re 5(m)
(C.11)
KEIL]
Here, we are using the fact that k.T 1, = [T,:] due to (C.8) in (C.9). We then change the indexing from (C.9) and (C.11) by observing that all the odd entries corresponding to values are zeroed out in K (cf. C.6). Finally, we simply substitute (C.6) and (C.7) in (C.10) and (C.11), respectively. Next, we define x E 12+1 with
TJ = Re 1) where with / E [T.] and l even. Here, x Rn-1 is vector size + 1 as there are + such even numbers in [L]. Note that is the vector with heavy-hitter from Proposition C.I. To see
(C.12)
32

---

this, observe that we have | 11 S
and |zyl S 3
for all j * E(t' 1). Using (C.11),
3
with probability 2 1 ge. we then have
y/ [L, : = 25(
(C.13)
By Proposition C.I, we can then infer the position of the key at t' with probability of error 1 union bound, we can then retrieve the corresponding value with probability at least 1 - ( + )
:. By the
We will now prove C.I as follows.
Proof of C.I. We will assume that s is a power of 2 for the sake of simplicity. We first specify how we will construct such an ((m) E Rogg)))logo), Let h [s] - [Vs] be a hash function. We define
S E R to be
SI.. = Σ Cj-
J:AO)=
That is, each column of is the sum of the standard basis vectors oj such that j is mapped by h to i. In other words, the locations of the non-zero entries in column correspond to the preimage of i under h. We then multiply each non-zero entry of S independently at random by =1. Next, replace the kth row in $ by multiplying all non-zero +1 entries at index i with the binary representation of to get matrix 56m) (ex(vxxlog=)) That is, for non-zero entry index in row k, we replace the ith entry with +1 B. Note here that each column still has at most vs non-zero entries. Finally, we stack 243 log 8- s-many copies of ((m) as heads so that each copy produces independent measurements (m()) Here, we want emphasize that each such copy uses fresh randomness for multiplying the non-zero entry of independently at random by +1.
Now, will show that the average of the measurements with matrices ((m) E /Rexvalog e can locate the heavy-hitter in æ, where x is the vector of inner products from (C.12). For this purpose, we first specify the algorithm for decoding the heavy-hitter.
Algorithm 2 Decoder
Require: The vector such that y = ..S.
I: Split into 243 log blocks y(()) E Rvolo, each of which is a result of multiplying æ by 5im)), m E [243- log
2: Take the average y + 243 Exy(m
3: e I, ((V)) E R cf. (C.14).
4: Retrieve b by isolating the binary representation of the position of the heavy-hitter in æ.
Here, we define the function I, RRVElog - Z,y Zyōlogg to [c:S]m that rounds each entry of its input to the nearest integer:
([=Smm) (mm) [i,
(C.14)
That is, in both cases, we retrieve the row in ((m) that corresponds to the heavy-hitter in z. Since the rows in ((m) are distinct, we can also infer the position of the heavy-hitter in with probability 1.
We now show that y = .tS, which consists of 243 log many independent copies of ((()) 25(mm) Instead, notice that we can analyze ÿ . since each is the replacement of non-zero entries of Š with the binary representation of their indices times y. We will drop the superscript for now to avoid cluttering the notation. We can then make the following claim:
(C.15) For the above claim, we note that the first part follows from the latter as suffices to show that all the non-zero heavy-hitters contribute (ce interacts with /s sized sub-vector of x, each ūj for non-heavy hitters can be expressed as
|ix - + O(c V/s) and, for j & i, |ūاl O(c Vss)
the sum it (I.Si: d]; Since each column in Š only
J (z. 5,) with x, ERV
where 5, E R contains the non-zero entries of S, and x is obtained by extracting the entries with corresponding indices from æ. Here, we have | lg Σ < since each entry associated with the non-
heavy hitter is bounded as x; S e, and thus, | = VE x e2, VVo e/.
Consequently, as 5, is independently random +1, we then must have
1
(z. 5, < 3
(C.16)
33

---

with constant probability for j * i. To see this, note that
[[ 5
Bl Sye] -2. Ij
| 22
where the last equality follows since y| Syel = òR,e by the distribution entries of Sy. Now, we use Jensen's inequality [57] to get the following bound on the expectation of Sz))
E (2,, [ V (x,, S S V
(C.17)
We then use the expectation above to bound the relevant probability follows:
Pr
(z. S -
2 1 Pr (T. S 2 3
3
2 1 - 3E [1 (x., 5,>1]
(C.18)
2 -1-3 3e V/s
where we apply Markov's inequality [57] in (C.18). That is, we have shown that Øj is bounded by 1/3 with constant probability for j * i, and y: is thus bounded by 1 3. Note here that each of the m-copies
(m) will have identical guarantees.
Now, define the average Øn = 243-logs s Σm g(m) so that y, (line in Decoder) is the corresponding replacement of the non-zero entries with the binary representation of their indices. now claim that
this average y, 4/9 < 1/2 with high probability for + i. To this end, we employ the multiplicative
Chernoff bound [57] on the independent random variables (o,h))a to get
J,, with E
Σ m,m"]] 81 log
Pr
4
Pr
(m)
+ 1)
243 log
(m)
Pr
Uj
2
+
81 log
1
exp
81
log
/3
32
Therefore, have shown that the average y is less than 1/2 with probability least 1 1 1 for j * i. Consequently, we will have 3i bounded by + 2. Using the union bound over each j * i and the log s bits in the binary representation of j. we can then show that jj+m < 1/2 for each j * i.m E [0, log s) with probability
log 8² >
34

---

D Experimental Details
D.I Pre-training
To verify the effect of introducing heads to Hyena as described in Section 4, train series of models on THE PILE [11]. All MultiHyena models are set to 8 heads, and otherwise use the same hyperpa- rameters of Hyena models of equivalent size. We set weight decay of Hyena filter parameters to O and lower the frequency of sine activations in the implicit MLP to 4. We follow the setup of [2], and first train models for 10 and 15 billion tokens, adjusting the learning rate scheduler accordingly. Then, we train for 300 billion tokens. The results are reported in Tables 5.1 and 5.1.
D.2 Distillation Analysis
Distilling pre-trained long convolution sequence models (LCSM) with LaughingHyena can introduce errors on the convolution filter, which then propagate to the outputs.
Setup We perform series of extensive experiments on all variants of LCSM, including pre-trained H3 models of sizes 125 million, 355 million, 1.3 billion and 2.7 billion parameters; Hyena of size 153 million parameters, and MultiHyena of size 153 million parameters. For H3 models, we report approximation errоrs on both shift as well as diagonal SSMs (reported as IIR and FIR). Each point corresponds to distillation carried out at a particular order, using LaughingHyena modal interpolation. To optimize the parameters of the modal form, we use gradient-based optimization and minimize the lg discrepancy between filters in time domain. In particular, we use the ADAMW [58] optimizer with learning rate 3- 10-1, and cosine annealing decay schedule down to 10-6 after 30 thousand iterations. Each individual filter of every layer distilled in the same way.
Discussion
The errors are shown in Figures D.1, D.1, D.2, D.3, D.4 and D.5. We observe H3 filters to be easier to distill into recurrences with small state without introducing significant errors, whereas Hyena variants learn filters with larger effective dimensions. This provides further evidence that training with implicit convolutions may yield in general more expressive filters.
Distillation Error H3 125M
IIR Emrrr
IIR Emror
IIR c... Error
IIR Hankel Singular Values
0.0126
0.00020
1.00
0.0100
0.00015
0.75
0/0075
0.15
0.50
0.00100
6,0050
0.06
0.0000G
6.0025
6.00
FIR Error
FIR 6 Error
100
FIR f.p Error
FIR Hankel Singular Values
0.0025
0.010
0.5
0.00200
0.008
0.2
0.006
0.0010
0.004
0.1
0.000G
Order
Order
Singular Value Index
Figure D.1: Mean, lower and upper bounds across channels and layers of the distillation errors on 125M H3 model for both its IIR and FIR filters.
D.2.1 Pretrained Filters: Effective Dimension
Visualizations We qualitatively investigate LCSM filters initialization and after pretraining. This visual inspection (Figures D.6, D.7 and D.8) complements the distillation error analysis of Section D.2.
Distribution of Hankel singular values We further compute the distribution of Hankel singular val- ues of each long convolution filter in different models. The decay in the spectrum quantifies how easy it is to find a compact modal form with LaughingHyena, and serves as a proxy measure of effective dimension of the convolution. The results shown in Figures D.9 and 10
35

---

Distillation Error of H3 355M
IIR Emrr
IIR
100
c.y.
Singular Values
0000030
0.008
0.10
0100004
0.000
0.00006
0.06
0.00
27
2"
27
FIR is Enror
-10
FIR Hankel Singular
0110125
20-
0.15
0.06
0.0115
1.0
0.000
0.5
0.06
0.004
2
27
27
2'
Ordar
Order
Singular Value
Figure D.2: Mean, lower and upper bounds channels and layers of the distillation errors 355M H3 model for both and FIR filters.
Distillation Error of H3 1.3B
IIR Error
IIR Error
IIR Esp Error
IIR Hankel Singular Values
01000111
0.012
0.00012
0.000
0 0.00010
0.00008
0.00006
2-
0.044
FIR Error
FIR 6 Error
FIR c.. Error
FIR Hankel Singular Values
0.008
10-
0.30
0.5
22
Singular
Figure D.3: Mean, lower and upper bounds across channels and layers of the distillation errors on 1.3B H3 model for both its IIR and FIR filters.
D.3 Downstream Evaluation
We benchmark the downstream performance of MultiHyena and distilled MultiHyena standard lan- guage modeling tasks from the L.M-Eal-Harness, [42] and HELM [41] suites. As a reference baseline, we evaluate Pythia [44] 160M.
Our objective is to quantify the absolute performance MultiHyena and the downstream impact of distillation. We use the same procedure outlined in Section D.2 to distill MultiHyena.
D.4 Benchmarking
To demonstrate the superior performance of Laughing Hyena for autoregressive generation, we conduct series of experiments benchmark its latency, throughput, and memory usage for autoregressive generation with initial prompt length T and number of generated tokens K. For each experiment, we compare the performance Laughing Hyena against Transformer, a hybrid H3-attention model with 2 attention layers and a Hyena model. The latter two have been shown to match or achieve lower perplexity than Transformers on standard datasets (WIKITEXT 103 and THE PILE). All experiments are carried out NVIDIA A100 with 80GB in f precision. Missing measurements for any model indicate Out of Memory (OOM) errors while doing autoregressive inference for that particular model.
36

---

Distillation Error of H3 2.7B
IIR Emar
100
Singular Values
0.0125
1.0
0.10
0.5
0.007
0.65
0.00010
0.000
2"
FIR is Enror
6
x30-
Hankel Singular
01021
0.0090
0.000
0,0025
2
0.00
0,0010
22
27
27
27
Order
Order
Singular Value
Figure D.4: Mean, lower and upper bounds across channels and layers of the distillation errors 2.7B H3 model for both and filters.
Distillation Error Hyena 155M (150B tokens)
Error
6 Error
Co Error
Hankel Singular Values
0.01
0.033
0.000
Order
Distillation Error of MultiHyena 155M (300B tokens)
Eg Error
Eg Error
to
Error
Hankel Singular Values
20-
0.2
Erorr
Exror
20-
50
0
21
2
2
2'
27
Figure D.5: Mean, lower and upper bounds across channels and layers of the distillation errors on Hyena and MultiHyena models.
Peak throughput We first evaluate the throughput (number of tokens generated per second) across different batch sizes, using typical generation workload consisting of prompt of length 512 and generating 256 tokens. Figure 1.1 measures peak throughput of different models. Since Laughing Hyena does not require caching intermediate kv-projections during generation, reduced memory requirements at a fixed model size allow it to process larger batch sizes.
Prompt length Autoregressive generation in Laughing Hyena is achieved through a two-step process: an initial prefill step that uses the length prompt to initialize the state IT and that generates all K tokens. In Figure 5.3 demonstrate how the prefill step scales for different prompt lengths, keeping batch sizes fixed at 64. Since prefilling in Laughing Hyena is carried out efficiently via convolutions (as described in Section 3,4), throughput scales more favorably than Transformers. Other models capable of prefilling via convolutions also achieve higher throughputs than Transformers but are ultimately slower than Laughing Hyena during the generation phase.
State throughput measure the impact of SSM state dimension on the throughput of Laughing Hyena. Keeping batch sizes fixed reveals minimal impact for all dimensions smaller than
37

---

FIR Filters of H3 125M
Normalood Fites hellAellAe Nema Fitess by/
Layer 0
Layer 1
Layer
Layer
Layer
Layer
Inisalization Prentrained
Attention Layer
Layer
Layer
50
50
50
60
IIR Filters of H3 125M
Nomoklzd iiees hu h//Diiie Normaliedd Fitess buj (A
Layer
Layer
Layer 2
1 aayr 3
Laer 4
Layer
Intiaalontion Prentnirned
2000
2000
2000
2000
2000
2000
Attention
Layer
ayer
ayer
Layer
2000
3000
20:00
20000
3000
2000
Figure D.6: Initialized and pre-trained convolution filters of H3.
100, which are sufficient to distill all models discussed in this work. All other measurements provided in this Section carried out with standard order 16. We note that it may be possible further increase peak throughput by leveraging reduced memory footprints achieved by extremely small SSMs.
Latency over sequence length We benchmark the time taken to generate variable number of to- kens, starting from a prompt of length 512 tokens at batch size 1 (Figure D.I Laughing Hyena tracks highly optimized Transformers. We note that Laughing Hyena asymptotically more efficient than Transformers; however, this regime is bottlenecked by hardware-specifis implementation details and optimizations. We expect optimized, platform-specifte implementations of Laughing Hyena to outper- form Transformers even batch size 1. When the prompt is long, the prefilling step becomes the bottleneck, and all convolutional models outperform Transformers.
Parameter scaling To better understand how the performance of Laughing Hyena scales, bench- mark its latency, throughput, and peak memory utilization for autoregressive generation and 125M, 355M, 1.3B, 2.7B and 6.7B parameters. We compare the performance that of Transformers, Hybrid- H3, and Hyena at the same number of parameters and report the results in Figure 1. For the latency measurement, we use batch size of and benchmark the time taken to generate 128 tokens, starting from a prompt of length 512 tokens. For throughput and peak memory scaling against the number of parameters, we use a batch size of 64 and measure the throughput for generating 256 tokens starting with prompt of length 512.
38

---

Filters of MultiHyena 155M (300B tokens)
Nomolted Fiters by (Mi
Layer 0
Layer
Layer
Layer
Layer
Layer
Init mitisization
2000
90000
2000
20000
20000
2030
Nomakes FiterAA
Layer 6
Layer
Layer
Layer
Layer
Layer 11
Nomolzed Fiters Nud
Jayr 12
13
1 Jayr 14
Layer 15
I aayr
Layer 17
0
2000
2000
2000
2000
2000
2000
Figure D.7: Initialized and pre-trained long convolution filters of MultiHyena.
39

---

Filters of Hyena 355M (200B takens)
Nomokzer Fiber MM// Normalted Fiee de lelo Nomokeer Fiters h. (kll
Layer
Layer
Layer
Layer
Initulizaiion Prestrained
Layer 6
Layer
Layor 8
Layer 9
Layer 10
Layer 11
2000
2000
2000
Layer 12
Layer 13
Layer 14
Layer 15
Layer 16
Layer 17
2000
2000
Noralted Hows bid bile Nomakee Filees ha/ Nomalted Fiee 1bbb
Layer 18
Layer
Layer
Layer 21
Layer
Layer 23
2000
2000
2000
2000
2000
2000
Layer
Layer
Layer
Layer 27
Layer
Layer 29
2000
2000
2000
20000
2000
2000
Layor
Layer
Layer
Layer
Layer
Layer
2000
2000
2000
2000
2000
2000
Figure D.8: Initialized and pre-trained long convolution filters of Hyena (355 M))
40

---

Hankel Singular Values of Hyena and MultiHyena Filters
Layer
Layer
Layer
Layer
Layer
Layer
Hanil Hinki Value
MuloH
10-
308
109
Singile
Hyona
10"
10
LO
60
1G
24
24
Layer 6
Layer
1. ayer 8
aayer
Layer 10
Layer 11
Hontel Singute Valu
102
102
109
102
109
100
100
100
307
100
107
100
10-
10
10
10
10
10-
10
10
10
10
100
Layer 12
Layer
Layer 14
Layer 15
Layer 16
Layer
Harial Snggtar Vaken
10-2
10-2
10-
10--
10-
10-2
10m4
10
10-1
10
10-4
24
21
21
2
24
21
24
Figure D.9: Distribution of Hankel singular values for Hyena and MultiHyena long convolution filters. MultiHyena filters have larger effective dimension, as evidenced by slower decay.
Hankel Singular Values H3 (125M) FIR Filters
Hontel Singiter Valu
Layer
Layer
Layer
Layer
Layor 4
Layer
In
10-2
Predrainnd
10-2
10-2
10m2
10-2
10-3
10
10
10
10
20
2*
Honter Sigila Voun
Attention Layer
Layer
Layer
Layer
Layer
Layer
10
10
9
0.0
0.2
1.0
2
2
2
Hankel Singular Values of H3 (125M) IIR Filters
Singibe Value
Layer 0
Layer
Layer
Layer
Layer 4
Layer 5
Inmisiration
Haniel SinieSSigiie
10
Pre-trained
10
10
10
10
10
10
10
L0
Horbel Sngiirr Values
Attention Layer
Layer?
Layer
Layer
Layer 30
Layer 11
10-2
10-2
10-3
10-2
10-2
10-5
10-5
10-5
10-5 44
10-5
2
Figure 10 Distribution of Hankel singular values for H3 long convolution filters. The values decay rapidly.
41

---

Laughing Hyena Hyena
Hybrid Attn. H3 * Transformer
Peak Memory [GBs]
Gener. throughput [tok/s] x10* Full gener. latency
40
60
40
20
20
0
0
1,000
2,000
0
2
4
6
Output sequence length
Number Parameters x10
Full gener. latency (S)
6
4
4
2
2
0
2
0
2
4
6
Number of Parameters x x10"
Number of Parameters x x00
Figure D.11: Generation latency, throughput and peak memory of Transformers, H3, Hyena and Laughing Hyena.
42

---

E Additional Experiments
E.1 Associative Recall with MultiHyena
We follow the setup of [2] and train 2-layer Hyena and MultiHyena (with 8 heads) to solve associative recall via standard next-token prediction objective. We focus the sequence length 64k, high vocab- ulary size setting, and push vocabulary sizes past the maximum values considered in [2]. At vocabulary size 60, difference between MultiHyena and Hyena can be observed (Table E. experimental support for Theorem 4.1.
Model
Accuracy
Hyena
65
MultiHyena
98
Table E.1: Associative recall accuracy, sequence length 64k, vocabulary size 60.
E.2
Analysis of Hankel Singular Values of Pretrained Large Convolution Sequence Models
E.3 Model Order Reduction of H3
The H3 model is constructed with a combination of diagonal SSMs and shift SSMs. There exists various classical model order reduction techniques for these different types of SSMs. The following sections aim present the formulation and effectiveness of two classical approaches on obtaining the compressed representation of H3 model. More specifically, we study modal truncation and balanced truncation for compressing diagonal SSMs and shift SSMs respectively.
E.3.1 Modal Truncation
Aa), B E Odx1, and C E Clxd) can be directly converted into residue-pole transfer function as follows:
A discrete diagonal SSM (A = diag( ,
(AB,C)+HIL
Σ
(E.1)
where residue B,C,, Modal truncation aims compress such transfer function by essentially reducing the summation over d to n < d, the n most influential modes. The influence from each node can be isolated by expressing it using the 1o norm of the system as follows:
(x)] Σ -
(E.2)
Aall
Each mode i can be ranked using the bound formulated above. Subsequently. the - n lowest modes could be discarded form reduced order model. Figure E. illustrates the monotonically decreasing loo error with the increase system order. However, this model reduction approach is only suitable for diagonalizable SSMs.
Modal Truncation Model Reduction Error H3
Momatedd Ererr
Layer
Layer
Layer
Layer
1.0
Mean
6.6
0.5
0.5
0.5
0.6
0.5
0.0
0.0
0.0
0.0
0.0
0.0
2
24
20
Nornatzed f. Entrr
1.0
Layer
1.0
Layer
3.0
Layer
1.0
Layer
1.0
Layer
1.0
Layer
0.5
0.-
0.5
0.5
0.5
0.3
0.0
0.0
0.0
25 Order
2'
Order
Order
Figure E.1: Modal truncation model reduction error ((|((()) An, (4) |oo) across all diagonal SSM layers of the trained H3 125M model.
43

---

E.3.2 Balanced Truncation
A balanced SSM realization is in which the observability P and controllability Q gramians equal and diagonal. Such a realization can be formulated with the following Lyapunov equations [24]]
AEA
+ BB =
(E.3)
A C
where P= Q = - = (i.... od) and oj 2 4+1
Results from [59] shows that the order model reduction error is bounded by:
Ex [1((s) (s)l 2 D2.
(E.4)
s=d-n Therefore, an ororderr partition of the full balanced realization can be chosen, such that the discarded orders are the d - n lowest contributor to the error. The steps taken by [24], computes the n order partition of the balanced realization as follows:
1. Form a Hankel matrix Sa from the impulse response him of the shift SSM.
2. Obtain the eigenvector matrix V E Cdxd, and the eigenvalues À via the eigen- decomposition of Sa.
3. Choose the truncated model's 's order n d, based on the bound in Equation E.4.
4. Compute the state-space matrices as follows:
V2 1m V1.d-1,1:mn
V1,1m C= Ii Viad
ho- (E.5)
This model reduction technique was applied to trained 125 million parameter H3, MultiHyena, and Hyena models as shown Figures E.2, E.3, and E.4 respectively. It could be noted that the all models encountered an undesirable non-monotonic error reduction with the increase in order. Moreover, order reduction configurations such as one in Figure E.3 layer 15 display signs numerical instability.
Balanced Truncation Model Reduction Error of H3
Normal leed Ex Erer
Layer 0
Layer
Layer
Layer
Moon
0.6
0,3
0.5
0,5
0.5
0.5
0.0
0.0
0,0
0.0
0.0
2
Layer
Layer
Layer 11
Mornatzed f. Ener
1.0
1.0
1.0
1.0
1.0
6.01
0.5
0.5
0.5
0.5
0.5
0.00
0.0
0.0
0.1
2'
2'
2
2'
2
Order
Order
Order
Order
Order
Figure E.2: Balanced truncation model reduction error (|(((t) h (o) across shift SSM layers of the trained H3 125M model. Note that Layer is an Attention layer, therefore balanced truncation model order reduction not possible.
44

---

Balanced Truncation Model Reduction Error of MuitiHyena
Layer
4
Noraaaddd Ererr
3.0
Msan
27
2'
21
Layer
Layer
Layer 8
Layer
Layer 10
Layor
Marnabed f.. Brer
1.0
1.0
1.0
0.5
0.5
0.5
0.5-
0.5
6.0
0.0
0.0
0.0
0.0
27
Layer 14
Layor
Nomateed.. f.. Erarr
1,0
1.0
1.0
1.0
1.0
27
21
21
Figure E.3: Balanced truncation model reduction enror (()((() hr, (1)) across all convolutional layers of the trained MultiHyena 155M model.
Balanced Truncation Model Reduction Error of Hyena
Layer
Layer
Layer
Layer
Nomalaadd t. Eror
Moon
24
Layer
Layer
Layer 8
Layer
Layer 10
Layer
Normaloed f., Ererr
1.0
1.0
1.0
1.0
0.5
0.5
0.5
0.5
0,5-
00.5
6.0
0.0
0.0
0.0
01.0
Layer
Layer 14
15
Layer
Nomaaledd f., Erer
1.0
2²
21
24 Order
Figure E.4: Balanced truncation model reduction enror ((((()) h (t)ll) across all convolutional layers of the trained Hyena 155M model.
45


Reviews:
[{"review_id": "6duvpfMvPF", "reviewer": "Reviewer_4kyN", "summary": "This paper proposes an approach that enables constant-memory, recurrent inference for long convolution architectures. They introduce LaughingHyena, a distilation approach that consists of extracting compact linear SSMs from each convolution layer. Combined with weight-tying, it results in state-of-the-art performance and efficiency (i.e. throughput) without any drop in quality. ", "questions": "Is it possible to benchmark against more recent open source models such as Llamma?", "limitations": "Broader Impacts section is missing.", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper is well structured and written.\n\nThe approach seems sound, reasonable and is performant", "weaknesses": "The models used in most experiments are small.\n\nThe helm evaluation is not very convincing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and feedback.\n\n>  The models used in most experiments are small\n\nOur main objective with this work has been to verify whether it is possible to distill pertained long convolution language models into a recurrent form, and investigate the trade-offs induced by different distillation methods. However, we certainly agree that it is also valuable to evaluate whether scaling affects the optimal choices of distillation procedures. To check performance at larger scale, we pretrain larger Hyena models (**~350M** and **1.5B**, with **3B** and **7B** still in training) on The Pile, then distill following the procedure outlined in the paper (with the addition of a truncation baseline suggested by reviewer 6dqz). We observe no degradation with distillation into the proposed modal parametrization with at least 16 states. Please see the general response for additional details on these results.\n\n| **Model**      | **Hellaswag** | **PIQA** |**OpenbookQA** |\n| ----------- | ----------- |  ----------- | ----------- |\n| Pythia 410M      | 39.2       | 66.8       |25.2       |\n| LLaMA 360M   | 40.4        | 67.2      | 27.5      |\n| MultiHyena 410M  | 41.3        | 69.2       |27.4       |\n| LaughingHyena-16  | 41.4        | 69.1       |27.3       |\n| LaughingHyena-8   | 32.5        | 58.4       |24.8       |\n| LaughingHyena trunc.  | 0.0        | 50.4       |21.4       |\n\n > The HELM evaluation is not very convincing.\n\nThank you for the feedback, and are open to suggestions and clarifications on specific aspects of the evaluation. We highlight that the evaluation has been designed primarily to verify whether distillation without quality degradation is possible, and as a secondary goal to confirm that long convolution language models (e.g., Hyena) are competitive with Transformers across tasks. For the benchmarks in Table 5.3, we follow the standard HELM (or LM-Harness) evaluation procedure. We welcome further questions and would be happy to have the chance to further clarify with additional details.\n\n\n> Is it possible to benchmark against more recent open source models?\n\nPlease see the general response for direct comparisons to a model using the LLaMA architecture.\n\n> Broader Impact is missing\n\nThe Broader Impact section can be found in the supplementary material, below the table of contents."}, {"review_id": "Iu8cEcmJ8M", "reviewer": "Reviewer_wEPT", "summary": "This paper proposes LaughingHyena - an improvement to the Hyena model that can perform long-convolutions instead of attentions in transformers to avoid the quadratic scaling issues. One of the issues with the convolution sequence models is that they incur significant cost due to autoregressive inference. To avoid this, this paper seeks to come up with a techinique to have constant memory recurrent inference to increase generation thoroughput. This is achieved using the use of compact linear SSM and weight tying the filters across heads in Hyena architecture. The resulting performance improvements are impressive - 1.5x throughput improvement compared to Hyena. The model also achieves SOTA in the PILE dataset.", "questions": "- What assumptions do you use for the state-space model in Eq 3.1 to yield a good distillation results (d<<L)?\n", "limitations": "I think the writing can be improved to provide a simple explanation of the method for readers who don't have a strong understanding of state-space models. Else, the text is hard to follow.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The perplexity on small-scale models on Table 1 and Table 2 outperform GPT, Hyena and establishes a new SOTA.\n- The peak memory usage is also constant for different sequence lengths in Table 5.4", "weaknesses": "- The writing is a bit hard to follow.\n- The performance of the model is still lacking compared to full transformer baseline such as Pythia in Table 5.3. Can the authors comment on this? Any idea on how much the performance degradation will be on very large scale models and datasets?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your thoughtful critique and questions and are happy to are happy to see positive feedback on the performance improvements.\n\n> Any idea on how much the performance degradation will be on very large scale models and datasets?\n\nIt is certainly a fruitful to investigate whether distillation is still possible at larger scale. We pretrain larger models (~350M and 1.5B) and provide the results below. Please see the general response for more details. \n\n| **Model**      | **Hellaswag** | **PIQA** |**OpenbookQA** |\n| ----------- | ----------- |  ----------- | ----------- |\n| Pythia 410M      | 39.2       | 66.8       |25.2       |\n| LLaMA 360M   | 40.4        | 67.2      | 27.5      |\n| MultiHyena 410M  | 41.3        | 69.2       |27.4       |\n| LaughingHyena-16  | 41.4        | 69.1       |27.3       |\n| LaughingHyena-8   | 32.5        | 58.4       |24.8       |\n| LaughingHyena trunc.  | 0.0        | 50.4       |21.4       |\n\n> Writing is a bit hard to follow\n\nThis is important feedback for us - we would be happy to address this. Section 2 was designed to be a self-contained introduction to long convolution and state-space models, and many of the technical details of Section 3 have been moved to the Appendix. We would be grateful if the reviewer could point out specific Sections that could use reorganization or simplification.\n\n> The performance of the model is still lacking a bit compared to Pythia\n\nThe pertained model performs on par or better than Pythia on most of the HELM and LM-Harness tasks. Since the original pertaining runs at smaller scales, we have been able to optimize Hyena and MultiHyena parameters further, please see the results in the general response.\n\n> What assumptions do you use for the state-space model in Eq 3.1 to yield a good distillation results ($d << L$)?\n\nIf you want to distill a length-$L$ ($L>> 1$) convolutional filter $h_t$ into a linear-time-invariant state-space model with a state dimension $d$ much smaller than $L$, you'd be looking to approximate the convolutional filter using a smaller, more compact representation. We know that with $d=L$ we can obtain a perfect state-space representation. When $d< L$, we are looking at representing the filter with \n\n$\n  \\hat{h}_t = c^* A^{t-1}b,~~ B,C \\in \\mathbb{C}^d, A \\in \\mathbb{C}^{d \\times d}\n$\n\ni.e. we are assuming that there exists a set of $d$ complex exponential basis functions which can approximate $h_t$. \n\nSeveral further practical considerations come into play:\n\n1. *Smoothness of $h_t$*: If $h_t$ is smooth in $t$, and doesn't have high-frequency components, it is usually easier to approximate it with a lower-dimensional state-space model whose parameters are trained via gradient descent. The Hyena filters are the output of a shallow neural network with smooth nonlinearities (e.g. complex exponential positional encoding and sinusoidal activation).  \n\n3. *Low-rank Structure*: If the filter can be decomposed such that most of its energy / information is contained within a few modes or components (similar to principal component analysis), then a reduced-order approximation can capture most of the filter's behavior. This can be *numerically assessed on real filters* by inspecting the singular values of the Hankel operator constructed with the filter. The Ho-Kalman theorem [1] (reported in text as Theorem 3.1) establishes that the minimum dimension $d$ (the *Mc Millan degree*)  is equal to the rank of the Hankel operator while the AAK theory [2] leads to rigorous bounds on the best-case approximation error for a given filter and target state-dimension. \n   \n   In our experiments, we show how the Hyena filters lose rank during pre-training and we can reliably use a state dimension $d << L$, predicted by the Hankel SVD, to distill the filters. \n\n4. *Stability*: Hyena filters are implicitly regularized for recency bias by a learnable exponential window function: $h_t = e^{-a t} g(t)$. This practically leads the filters to be convergent for $L -> \\infty$. In the context of distillation, this means that the state-space representation should be stable, i.e. that its poles should lie inside the unit circle. While we usually don't enforce it LRU-style [3] in our parametrization, we initialize the poles inside the unit circle.\n\n6. *Error Tolerance*: Depending on the application, you'll need to decide how much error is acceptable between the convolutional filter $h_t$ and its state-space representation. A model with $d << L$ may not perfectly reproduce $h_t$ for all the Hyena filters, so you'll need to find a balance between approximation quality and dimensionality reduction. For example, we see that the filters in certain layers require higher state dimensions than others. \n\n7. *Nature of Inputs*: If the filter $h_t$ is primarily used with a certain type or class of inputs, it's possible to optimize the state-space representation for that specific input. Knowing the typical input characteristics could help in achieving a good approximation with fewer states. However, our distillation methods want to be agnostic on the input characteristics.\n\n[1] Ho, B. L., and R. E. Kalman. \"Effective construction of linear state-variable models from input/output functions.\" REGELUNGSTECHNIK (1966).\n\n[2] V.M. Adamjan, D.Z. Arov, M.C. Krein, \"Analytic properties of Sc~nidt pairs for a Hankel operator and the generalized Schur-Takagi problem\", Mat. USSR Sbornik, vol. 15, p. 31-73, 1971.\n\n[3] Orvieto, Antonio, et al. \"Resurrecting recurrent neural networks for long sequences.\" arXiv preprint arXiv:2303.06349 (2023).\n"}, {"review_id": "5UxT5nq09x", "reviewer": "Reviewer_6dqz", "summary": "The paper proposes distilling convolutional models for autoregressive sequence generation into recurrent (state-space) models. A key limitation of recently proposed convolutional models is that they use convolutional filters that extend potentially infinitely into the past, and the same techniques that yield efficient training do not transfer over to token-by-token generation. This paper proposes a post-training and data-free distillation step that replaces such convolutional models with a recurrent approach that uses constant time and memory at each step of generation during inference.", "questions": "How well does the LaughingHyena architecture perform on the associative recall task, especially as compared to Hyena (or MultiHyena)? Is the point beyond which the models fail to perform the task (in terms of sequence length or vocabulary size) different between the two?\n\nFor LM-Eval-Harness and HELM, have you tried a baseline of taking the impulse response from Hyena/MultiHyena and truncating it to a finite impulse response? A sliding window seems like one of the simplest approximations to try in the world of convolutions, and it would be helpful to know if maybe some defect of the tasks or the base model results in nothing more being required. This would, in fact, be a useful baseline to have in the paper.", "limitations": "The paper could be improved with a little bit of additional discussion regarding limitations of the distillation/approximation.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "The key strength of the paper is that proposes a novel and theoretically grounded distillation method, which achieves good approximation bounds without being tied to specific data or involving what amounts to an additional round of training.\n\nAlso, convolutional and state space models as a whole are an underexplored area in recent work when compared to Transformers and attention, and this paper puts forward a novel method of linking the two, both of which contribute to the originality of the paper.", "weaknesses": "My biggest reservation based on my understanding of the paper is that I didn't get a qualitative sense of what might be lost as part of the distillation process. Is there some intuition of what is the worst-case qualitative behavior of a convolutional filter that can't be tightly approximated with LaughingHyena?\n\nThis question comes to mind because in the world of Transformers, it is no secret that most of the computational power spent on quadractic attention goes to waste. Just a small subset of the efficiency work there includes pruning entire heads, limiting each head to a head-specific attention context window, or even doing sliding-window attention with a fixed context length for the entire model. More in line with the present paper, work like Performer has developed an approximation for converting attention-based models into recurrent models -- at a cost. Notwithstanding the theory of the tightness of that last approximation, and equivalent performance of many to the Transformer that is demonstrated in some of the papers introducing these methods, there inevitably arises some situation where none of the approximations match the Transformer in quality. I worry that the present approach might fall into a similar pattern. A recurring theme in this area is that any method that sacrifices the ability to have long context, or to perform associative recall, is suspect. That's why when it comes to these approximations of convolutions, it would helpful to know whether the approximation is effectively some form of context-truncation in disguise, and if not what the qualitative cost is.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for insightful comments and questions. We particularly appreciated the suggestion of a specific additional baseline (FIR truncation). \n\n> Is there some intuition of what is the worst-case qualitative behavior of a convolutional filter that can’t be tightly approximated with LaughingHyena?\n\nAny approximation error on the convolutional filters is propagated through the depth of the neural network to the logits (in the case of language). If such an error is above a certain threshold, we have the worst-case scenario of token misclassification. Nonetheless, this is not a problem in practice: if a filter cannot be tightly approximated by our distillation procedure, we can chose not to distill that specific filter and assign to it a state-dimension $d=L$. While we wouldn't get any speedup in that convolution, we can make sure we don't have any degradation in performance. It is also worth mentioning that in all the models we distilled, we have yet to experience the impossibility of reducing the approximation error sufficiently not to cause token misclassification with more than a few state dimensions.\n\n> Notwithstanding the theory of the tightness of that last approximation, there inevitably arises some situation where none of the approximations match the Transformer in quality.\n\nThese are important points we are happy to elaborate upon. The proposed modal parametrization is capable of implementing associative recall over long sequences, even when trained from scratch (see results in general response and below). In [1] Hyena models have already been shown to match Transformer performance up to 350M scale. In this work, we investigate whether distillation of Hyena models into a recurrence is possible, without affecting downstream performance. Our perspective is that pretraining with implicit long convolutions and then distilling may be a more fruitful avenue that designing approximate or sparse variants of attention to train from scratch. \n\n> How well does the LaughingHyena architecture perform on the associative recall task, especially as compared to Hyena (or MultiHyena)? Is the point beyond which the models fail to perform the task (in terms of sequence length or vocabulary size) different between the two?\n\nWe provide additional ablations on the *associative recall* task to investigate the performance difference on recurrent models trained from scratch. We note similar results of this type i.e. associative recall benchmarking with long convolutions (Hyena) and state-space models (H3), and finite-length filters (Conv1D), are also provided by [1].\n\n| **Model**      | **10, 2k** | **40, 2k** |**10, 64k** | **40, 64k** |\n| ----------- | ----------- |  ----------- | ----------- |----------- |\n  |MultiHyena | 100 | 100 | 98 | 99 |  \n  |LaughingHyena-16 | 100 | 82 | 98 | 85 |  \n  |LaughingHyena-8 | 100 | 86 | 99 | 87|  \n  |LaughingHyena trunc | 81 | 48 | 21 |12 |  \n  |MultiHyena -> LaughingHyena-8 | 100 | 100 | 98 | 99 | \n\nWhere the first number indicates vocabulary size, the second one sequence length. Some observations on the above: (a) direct truncation performs much worse on associative recall, (b) pretraining with the proposed modal parametrization can solve challenging associative recall but is outperformed by MultiHyena, and (c) pretraining a MultiHyena and then distilling incurs in no accuracy cost.\n\n> For LM-Eval-Harness and HELM, have you tried a baseline of taking the impulse response from Hyena/MultiHyena and truncating it to a finite impulse response? A sliding window seems like one of the simplest approximations to try in the world of convolutions, and it would be helpful to know if maybe some defect of the tasks or the base model results in nothing more being required. This would, in fact, be a useful baseline to have in the paper.\n\nWe reran benchmarks with the suggested FIR-truncation baseline. Please see the results below (and additional details in the general response)\n\n| **Model**      | **Hellaswag** | **PIQA** |**OpenbookQA** |\n| ----------- | ----------- |  ----------- | ----------- |\n| Pythia 410M      | 39.2       | 66.8       |25.2       |\n| LLaMA 360M   | 40.4        | 67.2      | 27.5      |\n| MultiHyena 410M  | 41.3        | 69.2       |27.4       |\n| LaughingHyena-16  | 41.4        | 69.1       |27.3       |\n| LaughingHyena-8   | 32.5        | 58.4       |24.8       |\n| LaughingHyena trunc.  | 0.0        | 50.4       |21.4       |\n\n[1] Hyena Hierarchy: Towards Larger Convolutional Language Models"}, {"review_id": "gbNKMcHjnN", "reviewer": "Reviewer_n6Pj", "summary": "This article addresses two issues:\n\n1. The low efficiency of the LonvConv-based model during inference.\n2. Whether it is advantageous to perform independent long convolutions on each channel or reduce the total number of filters without loss in quality.\n\nTo tackle problem (1), the authors propose distilling the LonvConv into a Diagonal State space model and train it using the $\\ell_2$ loss function.\n\nFor problem (2), the authors suggest sharing long convolution coefficients across multiple channels, resulting in the MultiHyena structure.\n\nThe effectiveness of the proposed methods is validated on multiple datasets.", "questions": "1. The method for determining the hidden dimension of the State Space Model needs to be explained in more detail. I referred to Appendix E.3.2, and I'm wondering if the core idea is to perform an SVD decomposition and then select the dimension for dimensionality reduction based on the eigenvalues?\n\n2. The solution to Equation 3.4 requires a more detailed algorithm description or pseudocode to help readers follow along. I attempted to replicate it following Appendix B.1, but the results were not quite good. Could you provide the training configurations and an estimate of the training time?\n\n3. The motivation behind the design of MultiHyena should be included in the main text, and ablation studies (sharing coefficients vs not sharing coefficients) should be conducted to validate the design's rationale. The experiments should compare the effects and speeds.\n\n4. Does MultiHyena utilize the Local conv + Global conv structure of Hyena? If so, how many layers are used? This should be mentioned in the experiments.\n\n5. Is the Algorithm 1 on page 28 is the implementation of Figure 4.1?\n\n6. Regarding the implementation of MultiHyena, in Algorithm 1 on page 28, for $z^m_t \\in \\mathbb R^{L\\times N\\times N}$, what does the subscript $t$ represent? On the other hand, is the shape of $T_h$ $L$ (all features share one set of convolution coefficients) or $L\\times N\\times N$ (each feature has independent convolution coefficients)?\n\n7. Continuing with the implementation of MultiHyena, in Algorithm 1 on page 28, is the shape of $T_hz^m_t$ ${L\\times N\\times N}$? If so, does $T_h(z^m_t)  q_t^m$ mean performing matrix multiplication between $[T_h(z^m_t)]_i \\in \\mathbb R^{N\\times N}$ (for $i=0,\\ldots,L-1$) and $q_t^m\\in \\mathbb R^{N}$, resulting in an output of shape $\\mathbb R^{N}$? If not, what is the computation like?\n\n8. The algorithm's output is $\\bar{y} \\leftarrow\\left(\\sum_m\\right) y^m / M\\in \\mathbb R^{L\\times N}$, while the input has a shape of $L\\times D$. Is this inconsistency problematic, or did the algorithm omit something?\n\n9. Algorithm 1 has several ambiguities. It is suggested to reorganize it for better clarity.", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Distilling LonvConv into a Diagonal State space model is indeed a novel and meaningful approach. The conclusion of sharing long convolution coefficients across multiple channels is also innovative.", "weaknesses": "I think the main issue with this article lies in the focus of the writing. From Equation 3.4, it is clear that the ultimate goal is to represent the LonvConv coefficients using a Diagonal State Space Model. However, a significant portion of the article is spent describing unrelated aspects. The most crucial part, determining the hidden dimension of the State Space Model, is merely brushed over, even though it is the key factor that affects the quality of the distillation and the efficiency of the final inference. On the other hand, the motivation behind the design of MultiHyena should be addressed in the main text since it is of utmost importance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed feedback and insightful questions. Please see the general response for additional details and experiments.\n\n> The method for determining the hidden dimension of the state space model needs to be explained in more detail. I referred to Appendix E 3.2, and I’m wondering if the core idea is to perform an SVD decomposition and then select the dimension for dimensionality reduction based on the eigenvalues.\n\nWe thank the reviewer for the feedback. The core idea is indeed to perform an SVD decomposition of the Hankel operator constructed with the filter. We can then look at the decay of the singular values and select the dimension for distillation. Note that however we often select state dimensions well below the actual rank of the Hankel operator (Ho-Kalman [1]). Luckily, the AAK theory [2] gives us a bound on the approximation error (in terms of the Hankel norm) for a given state dimension. In particular the $d$th singular value is equal to the approximation error with the optimal $(d-1)$-dimensional state-space model. The eventual rationale for the choice of state dimension is however the performance of the distilled model in downstream tasks. Appendix E 3.2 mainly contains the details for classic model-order reduction methods (balance truncation) which we test as baseline distillation procedure on state-space models in the H3 architecture. You can also find further details in the reply to Reviewer wEPT.\n\n> The solution to Equation 3.4 requires a more detailed algorithm description or pseudocode to help readers follow along. I attempted to replicate it following Appendix B.1. but the results were not quite good. Could you provide training configurations and an estimate of the training time?\n\nWe are happy to clarify and elaborate on the method. In [gist](https://gist.github.com/neurips2310098/8bb0869e9bb6f083df9bab240ea47376) ([checkpoint](https://drive.google.com/file/d/1tnLzWAlB4In0nUDsiT3w_w_rnL5MGhf6/view?usp=share_link)) we provide a self-contained notebook where we showcase the distillation procedure with our modal approximants for a small MultiHyena (125M). On a single RTX3090 GPU the distillation takes about one minute per layer with an order 16 state-space model. We are happy to provide further details on the training procedure and hyperparameters.\n\n> The motivation behind the design of MultiHyena should be included in the main text, and ablation studies (sharing coefficients vs not sharing) should be conducted to validate the design’s rationale. The experiment should compare effects and speeds.\n\nThis is an important point. The design of MultiHyena, as mentioned in Section 4, is motivated by the observation that the effective dimensionality of long convolution filters in Hyena shrinks during training. Then, it can be advantageous (reducing the number of parameters) to share a smaller number of independent filters across \"heads\". Below, we provide an additional ablation that shows how sharing filters has a minimal impact on pretraining perplexity. Note that in the models below, we do not perform the multi-head computation outlined in Section 4; we only share filters in a vanilla Hyena model. \n\n| **Model (~155M)**      | **10B** | \n| ----------- | ----------- |  \n| Hyena-4     | 11.8     |\n| Hyena-8   | 11.9      | \n| Hyena-16  | 11.9      | \n| Hyena-32  | 12.1      | \n\nWhen we combine weight-sharing with the proposed multi-head layer structure (which itself is motivated by Theorem 4.1), we obtain significantly lower perplexity:\n\n| **Model (~155M)**      | **10B** | \n| ----------- | ----------- |  \n| MultiHyena-4     | 10.8     |\n| MultiHyena-8   | 10.4        | \n| MultiHyena-16  | 10.1      | \n| MultiHyena-32  | 9.6       | \n\n\n>  Does MultiHyena utilize the local convention + global convolution structure of Hyena? If so, how many layers are used? This should be mentioned in the experiments.\n\nAt the scales we tested so far (125M, 355M, 1B), MultiHyena utilizes the same exact structure of Hyena, with the notable exception of having to parametrize only $D / H$ long convolutional filters. \n\n> Is the Algorithm 1 on page 28 is the implementation of Figure 4.1\n\nWe will move it to the main text in the revised version of the paper to clarify the differences between Hyena and the proposed multi-head version.\n\n> Dimensions in MultiHyena\n\nWe thank the reviewer for the chance to clarify. $T^m_h$ in this case is $L \\times L $, and $q^m$ is $L \\times N \\times N$. The convolution is applied over the sequence length dimension ($T^m_h q^m$), in **parallel** for all the $N \\times N$ \"sequences\" in $q^m$. The result is also a $N \\times N \\times L$, which is then collapsed to $N \\times L$ via a dot product, and finally concatenated with the other $M$ chunks to produce $D \\times L$.\n\n> Question on algorithm output dimensions\n\nIn the standard model, we concatenate the $M$ chunks of size $N$ instead of averaging, yielding the desired $L \\times D$ dimensions. The construction described in the comment is a special case (concatenation followed by a dense layer with specific weights) used for the proof of the Theorem.\n\n[1] Ho, B. L., and R. E. Kalman. \"Effective construction of linear state-variable models from input/output functions.\" REGELUNGSTECHNIK (1966).\n\n[2] V.M. Adamjan, D.Z. Arov, M.C. Krein, \"Analytic properties of Sc~nidt pairs for a Hankel operator and the generalized Schur-Takagi problem\", Mat. USSR Sbornik, vol. 15, p. 31-73, 1971.\n\n[3] Orvieto, Antonio, et al. \"Resurrecting recurrent neural networks for long sequences.\" arXiv preprint arXiv:2303.06349 (2023)."}]

Author rebuttal:
**General Response**

We thank all reviewers for their comments and valuable questions. In this work, we study long convolution language models (H3 [1], Hyena [2]) and propose a novel methodology to distill recurrences for fast inference at generation time. Insights on the structure of the learned convolutional filters further reveal improvements to the general Hyena architecture, validated empirically (Tables 5.1, 5.2) and theoretically (Theorem 4.1).

We are happy to have received positive feedback on **execution, experiments and empirical evaluation** ("*sound, reasonable and performant*" **4kyN**, "*impressive improvements*" **wEPT**), **novelty** ("*novel and meaningful*" **n6Pj**, "*novel method of linking convolutions and state-space models*" **6dqz**) and **theorical contributions** ("*theoretically grounded distillation*" **6dqz**).

In this response, we address the main comments related to presentation, technical details of distillation, and scaling. 

**Distillation at larger scale** 

Below, we are excited to share some additional experiments on larger models ("*[...] how much does performance degrade at a larger scale?*" **wEPT**, "*Is it possible to benchmark against more recent open source models*" **4kyN**). All models are trained on The Pile, for 300B tokens, same tokenizer, with LLaMA 360M trained from scratch using the LLaMA architecture:

| **Model**      | **Hellaswag** | **PIQA** |**OpenbookQA** |
| ----------- | ----------- |  ----------- | ----------- |
| Pythia 410M      | 39.2       | 66.8       |25.2       |
| LLaMA 360M   | 40.4        | 67.2      | 27.5      |
| MultiHyena 410M  | 41.3        | 69.2       |27.4       |
| LaughingHyena-16  | 41.4        | 69.1       |27.3       |
| LaughingHyena-8   | 32.5        | 58.4       |24.8       |
| LaughingHyena trunc.  | 0.0        | 50.4       |21.4       |


Direct truncation techniques for distillation ("*have you tried a baseline of taking the impulse response from Hyena/MultiHyena and truncating it to a finite impulse response?*" **6dqz**) do not preserve downstream performance, further motivating distilling onto a different basis. We truncate at 64 values, a 4x increase over the 16 states required by LaughingHyena-16. We also tested distillation on a 1.5B parameter MultiHyena trained for 180B tokens, and observe once again that 16 states are sufficient to preserve downstream performance.

**Direct associative recall with modal and truncated parametrizations**
Further, we provide additional ablations on the *associative recall* task ("How well does the LaughingHyena perform on the associative recall task", 6dqz), to investigate the performance difference on recurrent models trained from scratch. We note similar results of this type i.e. associative recall benchmarking with long convolutions (Hyena) and state-space models (H3), and finite-length filters (Conv1D), are also provided by [2].

| **Model**      | **10, 2k** | **40, 2k** |**10, 64k** | **40, 64k** |
| ----------- | ----------- |  ----------- | ----------- |----------- |
  |MultiHyena | 100 | 100 | 98 | 99 |  
  |LaughingHyena-16 | 100 | 82 | 98 | 85 |  
  |LaughingHyena-8 | 100 | 86 | 99 | 87|  
  |LaughingHyena trunc | 81 | 48 | 21 |12 |  
  |MultiHyena -> LaughingHyena-8 | 100 | 100 | 98 | 99 | 

Where the first number indicates vocabulary size, the second one sequence length. Some observations on the above: (a) direct truncation performs much worse on associative recall, (b) pretraining with the proposed modal parametrization can solve challenging associative recall but is outperformed by MultiHyena, and (c) pretraining a MultiHyena and then distilling incurs in no accuracy cost.

**Effect of head dimension on pretraining perplexity**

Finally, we investigated the effect of the head dimension on Pile pretraining (results are improved over numbers presented in Table 5.2 due to further hyperparameter optimization).

| **Model (~155M)**      | **10B** | 
| ----------- | ----------- |  
| MultiHyena-4     | 10.8     |
| MultiHyena-8   | 10.4        | 
| MultiHyena-16  | 10.1      | 
| MultiHyena-32  | 9.6       | 

[1] Hungry Hungry Hippos: Towards Language Modeling with State Space Models

[2] Hyena Hierarchy: Towards Larger Convolutional Language Models

Meta-review: All reviewers find the paper interesting and has sufficient contributions extending long convolution based alternatives to attention. There were concerns around small scale and limited experiments and writing clarity. Authors response sufficiently addressed these concerns with additional experimental results. All reviewers agree for acceptance. One high level comment is about lack of discussion and comparisons with efficient attention approaches such as sparse attention and memorizing transformers. Currently the paper only focuses on comparison to similar approaches, and adding more discussion/comparison with other efficient attention approaches will make it easy for readers to better appreciate the results. Including results on more long context benchmarks like scrolls, can also help strengthen the paper.
Decision: Accept (poster)