Continual Transformers: Redundancy-Free Attention for Online Inference
Authors: Lukas Hedegaard
Arian Bakhtiarnia
Alexandros Iosifidis
Venue: ICLR 2023 poster (2023)
Keywords: Transformer
Continual Inference Networks
Online inference
Stream processing
Acceleration
Online Action Detection
Audio classification

Abstract: Transformers in their common form are inherently limited to operate on whole token sequences rather than on one token at a time. Consequently, their use during online inference on time-series data entails considerable redundancy due to the overlap in successive token sequences. In this work, we propose novel formulations of the Scaled Dot-Product Attention, which enable Transformers to perform efficient online token-by-token inference on a continual input stream. Importantly, our modifications are purely to the order of computations, while the outputs and learned weights are identical to those of the original Transformer Encoder. We validate our Continual Transformer Encoder with experiments on the THUMOS14, TVSeries and GTZAN datasets with remarkable results: Our Continual one- and two-block architectures reduce the floating point operations per prediction by up to 63x and 2.6x, respectively, while retaining predictive performance.

Published as a conference paper at ICLR 2023
CONTINUAL TRANSFORMERS: REDUNDANCY-FREE ATTENTION FOR ONLINE INFERENCE
Lukas Hedegaard, Arian Bakhtiarnia & Alexandros Iosifidis Department of Electrical and Computer Engineering
Aarhus University
Aarhus, Denmark
{1hm, ari arianbaah,, ai 1 dece. au. dk
ABSTRACT
Transformers in their common form are inherently limited to operate on whole to- ken sequences rather than on one token at a time. Consequently, their use during online inference on time-series data entails considerable redundancy due to the overlap in successive token sequences. In this work, we propose novel formula- tions of the Scaled Dot-Product Attention, which enable Transformers to perform efficient online token-by-token inference on a continual input stream. Importantly, modifications are purely to the order of computations, while the outputs and learned weights are identical to those of the original Transformer Encoder. We val- idate Continual Transformer Encoder with experiments the THUMOS14, TVSeries and GTZAN datasets with remarkable results: Our Continual one- and two-block architectures reduce the floating point operations per prediction by up to 63x and 2.6x, respectively, while retaining predictive performance.
INTRODUCTION
Many real-life usage scenarios such as the perception in self-driving cars and live monitoring of critical resources process a continual stream of inputs and require rearr-nstantaneouss predictions per time-step. This stands in contrast to what many common benchmarks for deep learning evaluate, namely the operation on distinct batches of data with no inter-bated relationships. Consequently, a plethora of methods have been developed (Ji et al. 2013 Carreira & Zisserman, 2017 Varol et al. 2018), Yan et al. 2018,, Heidari & losifidis 2021 Vaswani et al.) 2] Arnab et al. 2021 Bakhtiarnia et al.) 2021b), which focus on batch- wisc information (c.g., video frame token) arrives at each step from a continual input stream, and future information is not available at the current time-step. We need a class of networks, which operate efficiently on both batches of data and continual streams.
wise processing, but fail to optimise for online
operation, where
Accordingly, we propose a reformulation the Transformer Encoder as a Continual Inference Net- work (CIN, Section 2.1 which accelerates the stream processing on time-series data, while retaining weight-compatibiliiy. Specifically, we derive two variants of Continual Scaled Dot-Product Atten- tion (SDA) for the cases where prior output tokes should and should not be updated after observing a new input token. Notably, our attention formulations reduce the per-step cost of SDA (Vaswani al. 2017) from time complexity O(n2d) O(nd) and memory complexity O(n)) to O(nd) and are readily embedded into Continual Multi-Head Attention (MHA) and Continual Transformer Encoder blocks. Finally, we propose the use of Recycling Positional Encoding to accommodate progressive caching of partial attention results for continual data streams.
Due to the interdependence of SDA outputs, Continual Transformers are most efficient for shallow architectures. Shallow Transformers have many applications such as augmentations of CNNs (Tou-) vron et al. 2021), light-weight Natural Language Processing (Cornia et al. 2020), fusion operations in multi-modia (e.g. audio-visual) settings (Chumachenko et al. 2022) and early exit branches in multi-exit architectures (Bakhtiarnia et al. b0) In our experiments we validate their excep- tional efficiency improvements common benchmarks in Online Action Detection (Idrees al. 2017) and Online Audio Classification (Tzanetakis et al. 2001).
Source http:s///ggiiibb..o///oeeeeeeeee
nual -transformers

---

Published as a conference paper at ICLR 2023
Continual Transformer Encoder
Recycling Positional Encoding
Optional
Output
Input taken
CLS
Continual Betrosctive
Trans block
Siugle Out--ut Trans Five binck
TrunsEnc block
Retroective outputs
x1
x
Figure 1: Multi-block Continual Transformer Encoder with Recyeling Positional Encoding. For 2 blocks, regular Transformer Encoder blocks can be added between an initial Continual Retroactive block and a final Single-Output block. A class-token may be used after the initial block.
RELATED WORK
2.1
CONTINUAL INFERENCE NETWORKS
Definition (Continual Inference Network). A Deep Neural Network, which
is capable of continual step inference without computational redundancy,
non-continual Neural Network, produces identical outputs for batch- and step inference given identical receptive fields, uses set of trainable parameters for both batch and step inference.
is capable of batch inference corresponding
These requirements ensure that Neural Network has broad upplicability for both (offline) batch- wise inference (i.c., most research benchmarks) and online stream processing. While non-CINs can operate streams of data by caching prior steps in first-in first-out (FIFO) queue and aggregating them to a full (spatio- temporal input, which is processed similarly to an offline batch, this entails computational redundancy in proportion with the sequence length. CINs perform step-wise infer- ence without such caching and repeat computation. Uni-directional Recurrent Neural Networks are an example of Continual Inference Networks. Their default mode of operation is by time-step and they are easily applied to spatio-temporal batches of data by concatenation of the step-wise out- puts. Recently, modification to the spatio-temporal 3D convolution was proposed (Hedegaard & losifidis 2021], which enables existing 3D CNNs to operate efficiently during continual inference. similar principle was used enhance Spatio-temporal Graph Convolutions as well (Hedegaard al. 2022). In Section 3 we derive CIN formulation for Transformer Encoders.
2.2
TRANSFORMER ARCHITECTURES
Initially proposed for sequence-to-ssquenee modelling in Natural Language Processing, the Trans- former (Vaswani et al. 2017) has become a canonical building block in many applications of Deep Learning, including Computer Vision (Dosovitskiy et al.] 2021 Arnab al.) 202T, Wang al.) 2021 Carion et al. 2020 and Audio Classification (Gong et al. (021). Their success can be partly attributed to reduced inductive bias compared with CNNs and RNNs, which allows better adapta- tions when sufficiently large datasets are available; the Scaled Dot-Product Attention (SDA) maps set of input tokens to set of outputs without inherent preconceptions. However, this many-to-many attention exhibits quadratic growth in time and space complexity with the token count in the set.
great deal of research has sought to improve the efficiency of Transformers TTa et al. 2020). Block-wise or Chunking methods such as Image Transformer (Parmar al.) 2018) and Vision Transformer (Dosovitskiy et al. 202T) group up entities of a local receptive field into a single block, reducing the Onn") complexity to Onz)), where n, is the number of blocks. Techniques such as sliding windows, dilation and pooling can be used to achieve a similar effect (Beltagy et al.) 2020). The Reformer (Kitaev al. 2020 reduces the complexity O(n n) by learning group-
2

---

Published as a conference paper at ICLR 2023
ings in data-driven manner via Locality- Locality-Sensitive Hashing (LSH). A different paradigm aims to derive approximations of the self-attention matrix. Methods such as Linformer (Wang et al. 2020). Nyströmformer (Xiong al. 2021) and Performer (Choromanski et al. 2021) reduce the complex- ity from (n²) to ((n). Unlike these efforts, our approach produces the exact same computational outputs for temporal sequences the original Multi-Head Attention.
3 CONTINUAL TRANSFORMERS
In this work, we examine the use of Transformer Encoders for stream-processingg where we receive one token per time-step. Specifically, the query, key and value inputs constitute continual stream of d-dimensional tokens and we wish to compute the outputs for each step immediately considering prior tokens. We begin our exposition Attention (SDA) for this task. To alleviate the inefficiencies of SDA, we propose two alternative computational sequences in Section 3.2 and Section 3.3 and compare them to SDA in Section 3.4 Finally, sections 3.5 3.8 build up the full architecture, and discuss architectural considerations.
Section 3.1 by considering the Scaled Dot-Product
3.1 REGULAR SCALED DOT-PRODUCT ATTENTION
Denoting query, key, and value sequence matrices by Q, K, V E Raxd the regular Scaled Dot- Product Attention first defined by Vaswani et al. (2017) can be written as:
Att Q K,V) = D-
(QKT) (QKT/VV)
D d (A1,))
(1)
and where A, D E R and I, is row-vector of ones. In each time-step, we can update Q. and
V by discarding their oldest token and prepending new one in FIFO manner. This is common implementation for step-wise inference, e.g. found in the FAIRSEQ library (Ott et al. 2019).
Each time-step results in 2n2d + 2nd multiplications, 2n2d nd n additions, and n² exponen- tiations as accounted for in Appendix A.I which amounts to time complexity of O(n2d) and (n²) memory complexity originating from the transient feature- map A. Furthermore, a constant- sized cache of size 3(n 1)d is needed to store the n 1 latest tokens in Q. K and V. We could avoid considerable redundancy by caching QK directly. However, this comes with a memory penalty of (n 1)2. Fortunately, another computational scheme can be devised.
3.2 CONTINUAL RETROACTIVE SCALED DOT-PRODUCT ATTENTION
We can compute D-IAV in step-wise manner using the latest query, key, and value steps, anew, know, Unew E IR 1xd, alongside appropriately cached partial results. The softmax normalisa- tion with can be efficiently implemented via column-aligned element-wise multiplications (denoted by @ hereafter) of column-vector d AI, If we cache the n 1 values for the prior
step tokens, i.c. dmem = A A n 1- alongside Q and K, we can define the step update as:
(=
- (-n+2:0) exp (ile + exp (Q (Qmem k
mem
( exp
Inew
(K
knoww)
LTT
where Q (Kmem) are the n prior query (key) tokens, kold is the key from n steps ago, and denotes concatenation of matrices along the first dimension. Negative indices indicate prior time- steps. An update for AV can likewise be defined as a function of the n prior values AV Vmmm
A-(-a+l:-1) Av(-n+2:00 exp (Qmemkosaa) Vold + exp (Q (eemm kew) Unew
(4)
memi
()) exp
Inew Vd
(mee || knew
(V || Unew)
(5)
Finally, we compute the Continual Retroactive Attention output in the usual manner:
CoReAu (grew know; Vaow) = d @ AV.
(6)
An visual depiction of these update steps is provided in Appendix A.2 A time-step can now be computed with 7nd + 2n 3d multiplications, 6nd + 3n - 6d additions, and 3n 2 expo- nentials. This time complexity of ((d)) per step and O(nd) memory complexity is a significant improvement over the prior (n?2d) d) and ((n2) complexities in Section 3.1
3

---

Published as a conference paper at ICLR 2023
3.3 CONTINUAL OUGLPT SCALED
ATTENTION
Both the Regular and Continual Retroactive Dot-Product Attentions produce attention outputs for the current step, as well n 1 retroactively updated steps. In cases where retroactive updates are not needed, we can simplify the computation greatly via a Continual Single-Output Dot-Product Attention (CoSiAtt). In essence, the regular SDA is reused, but prior values of and v are cached between steps (as in (Ott et al. 2019)) and only the attention corresponding to a single query token q is computed:
CoSiAtt(q. Know, Vnew) (V mem Unew /al,
exp
q vd
mem knew)) ())c)))
A step output is computed with 2nd + 2d multiplications, 2 d- additions, and exponentials. The time- and memory complexities remain (nd)) per step. Using the (leading) query 4new as input, the attention is purely causal. Alternatively, prior (lagging) query vectors could be cached and used as query input, though this would introduce a network delay.
3.4 COMPARISON OF SCALED DOT- DRODUCT ATTENTIONS
Assuming n - prior q, k and v steps have been calculated by the Continual SDA modules, and that Q (Qmem (new)) ), K mem || kinew), and V = (Vmem Unew ). we have the correspondence:
(u( K, V) CoReAtt (uow know Veew
(()) CoSiAut( qrs Koow Unew
Here, qi is the hth row Q, i.e. (()) During stream processing, the complexity the Continual Retroactive SDA scales significantly more favourably that the regular SDA. For example, the floating point operations (FLOPs) are reduced by 31x when n = d = 100 and 308 when n = d = 1000. If retroactive output updates are not needed, the Continual Single-Outpur SDA reduces FLOPs by respectively x00x and 1000x. The scaling propertics are detailed in Appendix
3.5 CONTINUAL MULTI-HEAD ATTENTION
Continual Scaled
Attentions can replace regular SDA's directly in a Multi-Head Atten- tion (MHA). Given a new query, key, and value, k, v, the Continual MHA is defined as
("11 hh-1
CoMHA(q, k. v)
CoAtt(qWi kWk, K, kww))w)))))))))))))) Wo. 1=0
(9)
where denotes concatenation of heads and W W E Rddd//h Wi e Rdxdv/h, and Wo E Rd xdo are projection matrices of head i. CoAtt can be either CoReAtt CoSiAu.
3.6 CONTINUAL TRANSFORMER ENCODER
Continual MHA block can be integrated in a Continual Transformer Encoder block as follows:
LayerNorm (y FF())), y LayerNorm (Sel(r) + CoMHA ar, x)),
(10)
where corresponds to the newest step input and Sel(:) selects single (last) token of x: if CoSiMHA
used, or selects all tokens otherwise. FF(-) is a two-layer feed-forward network with weights
W,, W2. biases wi, W2, and activation function o(-), i.e. FF(x) ow + wi) W2 w2-
Aside from the residual selection, this is identical to common Transformer Encoder implementa- tions Vaswani al. 2017; Dosovitskiy et al. 2021).
3.7 RECYCLING POSITIONAL ENCODING
Since Transformer Encoder does not provide positional bias, it is common to augment token with a positional encoding p. Lee. E; = 2; o Pi, where could be addition or concatenation. In regular Transformers, the index denotes position in sequence rather than a position in time. However, this static positional assignment is problematic in the context continual inference; the last token at time will be the next-to-last token time f 1, and thus in need of different

---

Published as a conference paper at ICLR 2023
positional encoding than in the prior time-step. Instead, CINs require dynamic positions. There have been multiple prior works (Shaw et al., [201]] Huang et al. 2019 Dai et al., 2019) which create relative encodings by augmenting the SDA with positional offsets P between query and keys, i.. A exp(QK ( /va + P). While a similar modification to the continual attentions is possible, it is incompatibile with the regular SDA in Eq. @I. Instead, we use a Recycling Positional Encoding (RPE), which lets the positional encoding follow each token in time and recycles old encodings:
E. = 3t + Pro
Tt (T-- + 1) mod T,
(11)
where T is the number of encodings. While RPE does not specify relative encodings explicitly, the absolute positional interpretation of each token changes dynamically when new token arrives. In practice, the network learns relative, shift-invariant positional information by training with random To for each batch. Random shifts during training were recently explored in (Kiyono et al. 202T Likhomanenko et al. 2021 Dehghani et al. 2019) as well. RPE can use either learned or predefined encodings. In the latter case, Cyclic Positional Encoding (Ma al.] (02T). a sinusoidal encoding inspired by Gray code, is good fit. If we reuse the encoding immediately after an old token has "slided out", i.e. T = n, a token will have the same positional encoding relative to another whether it was steps older or n the number of positional tokens to T = 2n - 1. We explore both options in Section 4.1.2
steps newer. The positional ambiguity can be avoided by extending
3.8 ARCHITECTURAL CONSIDERATIONS
Block count In Section 3.4 we observed an exact correspondence between the results of the con- tinual and regular SDA layers. However, the correspondence does not necessarily hold for stacked layers. Consider the result of stacking two Continual Single-Output Transformer Encoder blocks. While the first block outputs step t that is identical to that in a corresponding regular block, the second block would have been initialised with prior step- inputs, which were the result of prior input windows instead of the current one; the correspondence would not hold. Though it is not convertible to/from a regular Transformer Encoder, the stacked Single-Output Transformer Encoder architecture has the merit of efficiency. This was exploited in Transformer-XI XL (Dai et al.) 2019). Given a single step input, the Continual Retroactive Transformer Encoder block produces output tokens corresponding to the entire observed sequence inside the window. Due to this one-to-many input-output mapping, it is not possible to stack multiple such layers. Nevertheless, it can be used in conjunction with Continual Single- former Encoder blocks in between as illustrated in Fig. T The Regular Transformer Encoder blocks in the resulting architecture have a significantly larger computational complexity than the Continual Retroactive and Oungle-Output blocks. Consequently, we recommend that Continual Transformer Encoders be used primarily in lightweight architectures with one or two blocks unless compatibility with non-continual Transformers is not required and only Single-output blocks are used.
Transformer Encoder with optional regular Trans-
Class token is common add a class token as input to transformers (Devlin et al. 2019 Doso- vitskiy et al., 2021), which accumulates information from other tokens prior to classification. How- ever, it cannot be used naïvely with CINs, as this would effectively double the number of input steps. In practice, it can be employed in Continual multi-block Transformer Encoders as input the second block (see Fig. D). but this placement limits class token interaction with downstream layers. It can also be used for ole-block Transformer Encoders if the value token is omitted as input.
Peak memory reduction trick The FLOPs for Ati(Q, K, V) are exactly n times those of CoSiAtt(q. knew: Unew). Comparing their memory complexity, the regular SDA is O(n?), while the Single-output SDA is (nd).. In practical applications where system memory is limited, we may thus reduce the maximum memory requirement of the computational device at inference by up to d/n (assuming n > d) by computing each row of the attention individually. However, this may reduce throughput due to reduced parallelism.
EXPERIMENTS
We provide case studies within two perception disciplines, namely Online Action Detection (Sec- tion 4.1 and Audio Classification (Section 4.2). In each case, we will start with a brief overview of the field, followed by experiments and results.
5

---

Published as a conference paper at ICLR 2023
4.1 ONLINE ACTION DETECTION
Online Action Detection (OAD) (De Geest et al. (016) entails the per-frame classification of human actions in video stream they happen without the ability change prior predictions nor to use future information. This is fundamentally more restrictive than Temporal Action Localisation, where the whole video clip is processed before start and end frames of an action are determined (Shou al., 2016 Xu et al. 2017 Shou et al. 2017: Wu et al. 2019).
The dominant design in OAD works at the time of writing is to employ twO-stream Convolutional Neural Network as backbone for frame-wist feature extraction with RGB images as inputs in one stream and Optical Flow fields in the other (Gao et al., 2017 Xu al., 2019; Eun et al.) 2020) Wang et al. 2021; Xu et al., 2021 On top of these, OAD methods encode temporal information and perform predictions per time-step, e.g. by means of RNNs (Gao et al.) 2017 Xu et al.) 2019 Eun
ett al. 2020) Transformers (Wang et al. 2021 Xu et al. 2021). Alongside the action detection for the current frame, an action anticipation task may be learned in parallel by means of decoder structures, as this has been found to improve the primary OAD task.
Unlike RNNs, an output update for the regular SDA in a Transformer block cannot be naively com- puted for single step by feeding successive video frames. Instead, prior step features must be cached, re-loaded and re- re-processed by the Transformer in each step in correspondence with a prede- fined window-size of prior steps. As laid out in Section 3.8, Continual Transformers are especially efficient when either one or two Continual Transformer Encoder blocks are used. Accordingly, we start our experiments with set ablation studies to simplify a recent transformer-basee
architecture,
the OadTR (Wang et al. (021). We further investigate the impact of ablating class token position and the use of Recycling Positional Encoding and compare different RPE schemes for Continual Transformers. Finally, we evaluate our configurations on two widely used OAD datasets, THU- MOS14 (Idrees et al. 2017) and TVSeries (De Geest et al., 2016).
4.1.1 EXPERIMENTAL SETUP
The THUMOS14 dataset (Idrees et al. 2017) for OAD has 200 and 213 validation and test videos, respectively, with frame-level class annotations across 20 classes. As in prior OAD works, the model is trained on the validation set and evaluated on the test Similar to Wang al. (2021) pre-extracted features from a two-stream Temporal Segment Network (TSN) (Wang et al. 2019) trained on ActivityNet v1.3 (Heilbron et al. 2015) or Kinetics-400 (Carreira & Zisserman 2017).
use
For TVSeries (De Geest et al. 2016), the network learns on the train and validations sets (20 videos) and evaluates on the test set (7 videos) in (Wang et al., 202T). RGB and Optical Flow features were extraced using an MMAction2 (Contributors, 2020) pipeline with ActivityNet v1.3 (Heilbron al. 2015) and Kinetics-400 (Carreira & Zisserman (2017) pretrained TSN ResNet-50 (He al.]
2016 backbones. This is similar to the feature extraction process used by LSTR (Xu et al. 2021)
Following Wang et al. (202T), we use a batch size of 128, sequence length 64, initial learning rate 10- with factor ten reduction each epoch, alongside weight decay 10-4, and dropout with probability 0.1. We report results using two epochs of training on a Nvidia RTX2080 GPU. We track mean Average Precision (mAP) for THUMOS14 and calibrated mean Average Precision (cmAP) (De Geest et al.) 2016) for TVSeries, alongside FLOPs per prediction and parameters the OAD module (feature extraction excluded). We report the mean + standard deviation over five runs.
4.1.2 ABLATION STUDIES
Removing the Decoder As a first step to make an efficient Continual OadTR, we remove the decoder blocks used for action anticipation, which has large impact on computational efficiency and the ease of transformation to a Continual Inference Network. The first two lines of Table Ia present the results of the removal. Contrary to the observations of Wang et al. (2021). we did not find any drop in accuracy when excluding the decoder. We do, however, gain large reduction in FLOPs and model size; they were reduced to 58% and 30%, respectively. Given these computational improvements, we exclude the decoder in subsequent experiments.
'The feature extraction commonly used in Online Action Detection (OAD) works is in itself quite compu- tationally costly. We consider the optimisation of the hackhone orthogonal future work and will follow the feature extraction procedure other OAD works at this time.

---

Published as a conference paper at ICLR 2023
Table 1: Ablation experiments on THUMOS14 with TSN-Anet features. Best metrics are high-
lighted. '-' indicates that particular feature was not used.
(a) Class token variations with OadTR, CLS pos.
is the encoder block into which CLS is input.
(b) Positional encodings variations for CoOadTr.
Enc. blocks
Dec.
CLS
pos.
mAP (%)
FLOPs
(M)
Parums (M)
Enc. blocks
Re- cycling
Learn
Pos. tokens
mAP (%)
FLOPs
(M)
Params
(K)
3
V
57.0
2445.6
74.7
45. 45.3
410.9
15832
57.0em4
1430.6
22.2
56-4su
410.9
15832
$7.3s07
1423.5
22.2
56.0ras
15897
56.7
1417.2
22.2
55.8
410.9
15767
56.830
1410.9
22.2
56.8144
56.5em
1020.7
15.9
V
44.0
55.6 25.6
9.6
9.6
9535
9535
2
56.7
56,6eu
1008.1
1014.5
15.9
15,9
v
2n-1
55.6103
54
9.6
9.6
9599
9469
57.1 ius
611.7
2n-1
56.1
9469
56,3
605.5
9.6
(Re)moving the Class token Class tokens should not be input naively to the first Transformer Encoder layer of CIN (see Section 3.8 Accordingly, we ablate its use and position. In cases where it is removed, we predict on the token corresponding to the last input token. The results of varying CLS pos are noted Table la For the one-block architecture, the removal came with noticeable drop in mAP, while the two-block architecture saw small improvements when removing or introducing the class token later. For the three block model, the use of class tokens in block two achieved the highest mAP. Though it is commonly accepted, that class tokens should be introduced alongside other inputs in the first block, our results indicate that they can accumulate sufficient information with only one two blocks, and that later stage introduction may work better in some applications. In general, the achieved mAP when varying CLS pos. and number of blocks are very similar another, while mre)ng the class token and reducing the block size both reduce computational complexity. This encourages the use of shallow Transformer Encoders over deeper ones well as the removal of class tokens, as we do in the following experiments.
Positional Encodings We can transfer parameters from the simplified one- and two block OadTR to the corresponding Continual architecture, CoOadTR. Here, the one block version (CoOadTR- bl) uses CoSiMHA, and the two block model (CoOadTR-b)) uses CoReMHA in the first block and Single-output MHA in the second. However, a regular positional encoding is not suited for continual inference (see Section 3.7) We evaluate the performance of using non-continual encodings for continual inference, as well as of our proposed Recycling Positional Encodings with fixed or learned parameters. In addition, we explore the impact of extending the number of tokens from to 2n -1 to avoid positional ambiguity. As seen in Table lb). non-continual encoding used in the continual setting result in severe mAP drop. Recycling Positional Encodings alleviate this. Comparing learned and fixed encodings, we find the learned encodings to work better when the number of encoding tokens corresponds the sequence length and the fixed encoding work best when positional ambiguity is alleviated by extending the number of tokens to 2n 1. Fixed encoding with 2n tokens works best overall and is employed in subsequent experiments unless stated otherwise. There is no difference in FLOPs for either strategy, and the difference in parameter count is negligible.
4.1.3 COMPARISON WITH PRIOR WORKS
We evaluate the Oad'R architectures on THUMOS14 14 and TVSeries with two sets of features as described in Section 4.1.1 Since no prior OAD works have reported complexity metrics, we mea- sured the FLOPs for TRN Xu et al. 2019) based on the publicly available source code to serve as point of reference. The results of this benchmark are presented in Table Fig. [ OadTR and our simplified (continual) one-block (b1) and two-block (b2) versions without decoder and class tokens generally achieve competitive precision in comparison with prior works, surpassing all but OadTR and LSTR. On THUMOS14 14 our reproduced OadTR results slightly lower than originally ported [Wang et al. 2021 whereas achieved TVSeries results are higher" The (Co)OadTR-bu
"The reported 58.3% on THUMOS14 14 could not be reproduced using their publicly available code. We attribute higher McAP differences in the feature extraction pipeline.

---

Published as a conference paper at ICLR 2023
Table Online Action Detection results. FLOPs per pre-
diction are noted for inference on THUMOS14, The best and next-best metrics are highlighted.
THUMOS14
TVSeries mcAP (%)
Model
Feat.
mAP (%)
(M)
RED Gao et al. TRN
2017
45.3
79.2
mob0
47.2
83.7
1387.5
FATS
Kim 2 01
202
51.6
81.7
2020
# Dudtt
TFN Tun eI al.
2124
55.7
85.0
THUNDSSRARNE
OadTR Wang et at. 2021
al.
A.Net
58.3
85.4
2445.6
OadTR
57.0gns
88.62n1
2445.6
OadTR-b2!
56.6103
60-
OadTR-b11
56.3+uz
88. +
605.5
CoOndTRR-22 (ours)
16.8
87.7 am
410.9
CoOadTR (ours)
26.
87.6.00
TRN ex al. 2019
62.1
86.2
1462.0
106
10P
FATS
59.0
IDN
Fun et a
2020
60.3
86.1
Figure 2: Visual comparison of
LSTR Xt 407T
69.5
89.1
OadTR Waing
OAD methods on THUMOS14 and TVSeries for backbones trained
Kin.
OadTR
64.2am
88.62a1
2513.5
OadTR h2!
64.5
88.3
1075.7
ActivityNet 1.3 and Kinetics-400.
OudIRRb11
63.9
88.1
673.0
CoOadTR b2 (ours)
64.4jmt
87.6.07
411.9
CoOadTR-b (ours)
64.2gn4
87.7
10.6
'Using official source code or modifications there-off.
architecture largely retain precision and allow significantly reduced FLOPs per prediction. Our proposed continual variants CoOadTR-bl and CoOadTR-h2 reduce F1.OPs by 255x and 6.1 respectively, compared to OadTRR, while either achieving the same performance conceding no more than one percentage point. On average, continual and non-continual (Co)OudTR-bu models achieve similar mAP THUMOS14, while OadTR-b# have slightly higher mcAP on TVSeries. We attribute these discrepancies to differences in positional encoding. All in all, the CoOadTR-ba models provide far-superior computational efficiency to prior works, achieving tiite-of-the-ee art per- formance/efficiency trade-off's by a large margin.
4.1.4 AUDIO-VISUAL ONLINE ACTION DETECTION
To showcase the validity of our method in audio-visual settings well, we explore the addition of audio-features to the Online Action Detection task on THUMOS14. As described Section 4.2 audio-features are extracted using Mel spectrograms and AudioSet pre-trained VGGish net- work (Hershey et al. 2017) (output of the penultimate layer) on 1.0 second windows with step size of 0.2 seconds match the 5.0 FPS sampling rate of the video features.
The audio-features by themselves do not provide enough signal to reach good Online Action Detec- tion performance (yielding only 6.7% mAP with an OadTR network). When concatenated with RGB and Flow they do provide a modest improvement as seen in Table 3 On average, this amounts to +0.6% mAP when combined with ActivityNet features and +0.5% mAP when used with Kinetics- 400 features with shallower models enjoying the largest improvements.
4.2 AUDIO CLASSIFICATION
4.2.1 BACKGROUND
Audio Classification is the categorisation audio waveforms. Though waveform sequences can be used directly (Lee et al.) 2017), it is common to first convert them to spectrograms. Mel spectro- grams are obtained by nonlinear transformation of a frequency scale (Stevens et al. 1937). which designed based empirical knowledge about the human auditory system (Choi al. 2016). By employing spectrograms, audio classification can be approached in the same way as image classifi- cation (Palanisamy et al. 2020).
8

---

Published as a conference paper at ICLR 2023
Table 3: Audio-Visual result, THUMOS14,
Table 4:
Audio Classification results for
Model
Feat.
mAP (5)
FLOPs (M)
GTZAN.
OadTR
57.6:44
2714.9
OudTR-b2
A.Net
57.5
1277.0
Acc. (%)
FLOPs (M)
Par.
OudTR-bl
57.4
874.1
Method
Pos. Enc.
(K)
CoOudTR-hr h2
AudioSet
56.5211
415.0
CoOadTR-bi
16.81es
13.8
Maj. Voting
92.0
0
Trans-b2
leamed
95.0+aa
47.4
509
OadTR
64.4
2781.9
Trans-b1
leamed
33.8
15.2
286
OudTR-b2
Kin.
65.0se4
1344.1
CoTrans-b2
fixed
94.4+ze
27.0
509
OadTR-bl bl
64.51
941.2
CoTvans-bl
leamed
93.2am1
0.3
286
CoOadTR-ba
AudioSet
64.7
416.0
CoOadTR-bl
64.8=a3
14.8
4.2.2 EXPERIMENTS
We conduct experiments on the Music Genre Classification dataset GTZAN (Tzanetakis & Cook, 2002]. It consists 100 30-second clips for each of ten music genres. Each audio clip is sampled at 22,050 Hz. Since there are predefined splits for GTZAN, we randomly select 10% of the data for validation and 10% for testing. The input transformed to a temporal sequence by sliding a one-sccond window over each 30-second clip with slide step size of 250ms, leading to 120 one- second clips. These are subsequently converted to Mel spectrograms. We then fine-tune a VGGish network, pre-trained
AudioSet (Hershey al. 2017) and use the penultimate layer for feature extraction. A batch size of 64 and the Adam optimizer (Kingma & Ba 2015) are used with an initial learning rate of 10-4 The learning rate is reduced by factor of 0.6 on plateau with a tolerance of two epochs, and an early stopping mechanism, where a maximum of 100 epochs are allowed. The VGGIsh base-network attains an accuracy 86.1% on the dataset of one-second clips with 72.1M parameters and 864.7M FLOPs. Subsequently, the audio features are passed to a (Continual) Transformer Encoder which has 16 attention heads, an embedding dimension of 192 and an MLP dimension of 384. The Transformer Encoder is trained on the whole temporal sequence using a batch size of 32 and the Adam W optimizer (Loshchilov Hutter 2019) with learning rate of 10-3 and weight decay of 10-4 for 50 epochs. Since the Transformer Encoder is trained entire 30-second clips, there are less data points available for this training. Accordingly, the size of the validation set is increased to 18%. All audio classification training procedures Nvidia RTX 2080 Ti GPU. Table presents the accuracy and efficiency regular and Continual Transformers during online inference. As baseline, also include the result of majority voting among the clips to classify the entire sequence. The Continual Transformers obtain similar accuracy regular a Transformers while consuming 1.76x less FLOPs when using blocks and 51.5x less FLOPs when using one Transformer Encoder block.
carried out single
CONCLUSION
In this work, we presented Continual Transformers, redundancy-fres reformulation of Transform- ers tailored for online inference. Central to the Continual Transformer are the Continual Retroactive and Single-Output Attention operations, which produce outputs identical to the original Scaled Dot- Product Attention for continual input sequences, while greatly reducing the time and memory com- plexity per prediction. The applicability of Continual Transformer architectures was experimentally validated in Online Action Detection and Online Audio Classification settings, observing upwards of multiple orders of magnitude reduction in time complexity for lightweight architectures mod- est accuracy concessions. Continual Transformers constitute an algorithmic innovation, which could make possible hitherto unseen precision, speed, and power efficiency in online inference use-cases. With applications spanning enhanced perception and reactivity of robots and autonomous vehicles, weather forecasting, price prediction and surveillance, we hope it will be used for the common good.
ACKNOWLEDGMENTS
This work has received funding from the European Union's Horizon 2020 research and innovation programme under grant agreement No 871 871449 (OpenDR).

---

Published as a conference paper at ICLR 2023
REFERENCES
Anurag Arnab, Mostafa Dehghani, Georg Heigold, Chen Sun, Mario Lucic, and Cordelia Schmid. Vivit: A video vision transformer. In IEEE/CVF Conference Computer Vision and Pattern Recognition (CVPR), 2021.
Arian Bakhtiarnia, Qi Zhang, and Alexandros Iosifidis. Single-layer vision transformers for more accurate early exits with less overhead. preprint, arXiv:2105.09121, 202
Arian Bakhtiarnia, Qi Zhang, and Alexandros Iosifidis. Multi-exit vision transformer for dynamic inference. British Machine Vision Conference (BMVC), 2021b.
Iz Beltagy, Matthew E. Peters, and Arman Cohan. Longformer: The long-document transformer. arXiv:2004.05150, 2020.
Nicolas Carion, Francisco Massa, Gabriel Synnaeve. Nicolas Usunier, Alexander Kirillov, and Sergey Zagoruyko. End-to-end object detection with transformers. In Andrea Vedaldi, Horst Bischof, Thomas Brox, and Jan-Michael Frahm (eds.), European Conference on Computer Vision (ECCV), pp. 213-229, 2020.
J. Carreira and A. Zisserman. Quo vadis, action recognition? a new model and the kinetics dataset. In IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 4733- 2017.
Keunwoo Choi, George Fazekas, and Mark Sandler. Automatic tagging using deep convolutional neural networks. International Society of Music Information Retrieval Conference (ISMIR), 2016.
Krzysztof Marcin Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane. Tamas Sarlos, Peter Hawkins, Jared Quincy Davis, Afroz Mohiuddin, Lukasz Kaiser, David Benjamin Belanger, Lucy J Colwell, and Adrian Weller. Rethinking attention with per- formers. In International Conference on Learning Representations (ICLR), 2021.
Kateryna Chumachenko, Alexandros Iosifidis, and Moncef Gabbouj. Self-attention fusion for au- diovisual emotion recognition with incomplete data. arXiv preprint arXiv:2201.11095, 2022.
MMAction2 Contributors. Openmmlab's next generation video understanding toolbox and bench- Apache 2.0 License., 2020.
mark. https: www...t..h...... com/ caamm/ppen-mmtn mm1--mmmllal hta.b//mmaact....
Marcella Cornia, Lorenzo Baraldi, and Rita Cucchiara. Smart: Training shallow memory-aware transformers for robotic explainability. In 2020 IEEE International Conference on Robotics and Automation (ICRA). pp. 1134, 2020. doi: 1LL.10/9/CRAA444422200000090 9196653.
Zihang Dai, Zhilin Yang, Yiming Yang, Jaime Carbonell, Quoe Le, and Ruslan Salakhutdinov. Transformer-Xe XL:: Attentive language models beyond fixed-length context. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pp. 2978-2988. Associa- tion for Computational Linguistics, July 2019. doi: 18.18653/v 1/199922//
Roeland De Geest, Efstratios Gavves, Amir Ghodrati, Zhenyang Li, Cees Snoek, and Tinne Tuyte- laars. Online action detection. In European Conference on Computer Vision (ECCV), pp. 269- 284, 2016.
Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Lukasz Kaiser. Universal transformers. In International Conference on Learning Representations, 2019. URL https:
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre- Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume I (Long and Short Pupers), pp. 4171-4186 Association for Computational Linguistics, June 2019, doi: 111853//1/N19--1
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszko- reit, and Neil Houlsby. An image worth 16x16 words: Transformers for image recognition at scale. In International Conference Learning Representations (ICLR), 2021.
10

---

Published as a conference paper at ICLR 2023
H. Eun, Jinyoung Moon, Jongyoul Park, Chanho Jung, and Changick Kim. Learning discriminate information for online action detection. JEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 806-815, 2020.
Hyunjun Eun, Jinyoung Moon, Jongyoul Park, Chanho Jung, and Changick Kim. Temporal filtering networks for online action detection. Pattern Recognition, 111:107695, 2021.
Jiyang Gao, Zhenheng Yang, and Ram Nevatia. RED: reinforced encoder-decoder networks for action anticipation. In British Machine Vision Conference (BMVC), 2017.
Yuan Gong, Yu-An Chung, and James Glass. AST: Audio Spectrogram Transformer. In Proc. Interspeech 2021, pp. 571-575, 2021. doi: 0021445/interspecch22011111
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). IEEE, June 2016. doi: 10. 1096
Lukas Hedegaard and Alexandros Iosifidis. Continual 3d convolutional neural networks for real- time processing of videos. In European Conference on Computer Vision (ECCV), 2021. Apache 2.0 Licence.
Lukas Hedegaard, Negar Heidari, and Alexandros Iosifidis. Online skeleton- action recogni- tion with continual spatio-temporal graph convolutional networks. preprint, arXiv: 2203. 11009, 2022. Apache 2.0 Licence.
Negar Heidari and Alexandras losifidis. Progressive spatio-temporal graph convolutional network for skeleton-based human action recognition. In IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP), pp. 3220-3224, 2021.
Fabian Caba Heilbron, Victor Escorcia, Bernard Ghanem, and Juan Carlos Niebles. Activitynet: A large-scale video benchmark for human activity understanding. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 961-970, 2015.
doi: 10. (199/CVR.2011.722955
Shawn Hershey, Sourish Chaudhuri, Daniel P. W. Ellis, Jort F. Gemmeke, Aren Jansen, R. Channing Moore, Manoj Plakal, Devin Platt, Rif A. Saurous, Bryan Seybold, Malcolm Slaney, Ron J. Weiss, and Kevin Wilson. CNN architectures for large-scale audio classification. In IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, March 2017. doi: 10. 10.11099icasp22217779222...
Cheng-Zhi Anna Huang. Ashish Vaswani, Jakob Uszkoreit, Ian Simon, Curtis Hawthorne, Noam M. Shazeer, Andrew M. Dai, Matthew D. Hoffman, Monica Dinculescu, and Douglas Eck, Music transformer: Generating music with long-ter term structure. In International Conference on Learning Representations (ICLR), 2019.
Haroon Idrees, Amir R. Zamir, Yu-Gang Jiang, Alex Gorban, Ivan Laptev, Rahul Sukthankar, and Mubarak Shah. The thumos challenge on action recognition for videos "in the wild". Computer Vision and Image Understanding, 155:1-23, 2017. ISSN 1077-3142.
Shuiwang Ji, Wei Xu, Ming Yang, and Kai Yu. 3d convolutional neural networks for human action recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35(1)2221-231 2013. doi: 10. 10.109//PAM..2012.599
Young Hwi Kim, Seonghyeon Nam, and Seon Joo Kim. Temporally smooth online action detection using cycle-consistent future anticipation. Pattern Recognition, 116:107954, 2021. ISSN 0031- 3203.
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. In Yoshua Bengio and Yann LeCun (eds.), International Conference on Learning Representations (ICLR), 2015.
Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. In
International Conference Learning Representations (ICIR), 2020.

---

Published as a conference paper at ICLR 2023
Shun Kiyono, Sosuke Kobayashi, Jun Suzuki, and Kentaro Inui. SHAPE: Shifted absolute position embedding for transformers. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pp. 3309-3321, Online and Punta Cana, Dominican Republic, November 2021. Association for Computational Linguisties. doi: 10.1 00.18633/1/2021.0 wew.le-mmmpppm.me main.. 266.
Jongpil Lee, Taejun Kim, Jiyoung Park, and Juhan Nam. Raw waveform-based audio classifica- tion using sample-level cnn architectures. NIPS, Machine Learning for Audio Signal Processing Workshop (MI.AAudio), 2017.
Tatiana Likhomanenko, Qiantong Xu, Gabriel Synnaeve, Ronan Collobert, and Alex Rogozhnikov. Cape: Encoding relative positions with continuous augmented positional embeddings. In M. Ran- zato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 16079-16092. Curran Associates, Inc., 2021.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. International Confer- ence on Learning Representations (ICLR), 2019.
Yining Ma, Jingwen Li, Zhiguang Cao, Wen Song, Le Zhang, Zhenghua Chen, and Jing Tang. Learning to iteratively solve routing problems with dual-aspect collaborative transformer. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural In- formation Processing Systems, 2021.
Myle Ott, Sergey Edunov, Alexei Baevski, Angela Fan, Sam Gross, Nathan Ng, David Grangier, and Michael Auli. fairseq: A fast, extensible toolkit for sequence modeling. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics (Demonstrations)), pp. 48-53, Minneapolis, Minnesota, June 2019. Association for Computational Linguisties. doi: 10.18653/v 1/N19-4009.
Kamalesh Palanisamy, Dipika Singhania, and Angela Yao. Rethinking enn models for audio classi- fication. arXiv:2007.11154 2020.
Niki Parmar, Ashish Vaswani, Jakob Uszkoreit, Lukasz Kaiser, Noam Shazeer, Alexander Ku, and Dustin Tran. Image transformer. In Jennifer Dy and Andreas Krause (eds.), International Con- ference on Machine Learning (ICML), volume 80 of Proceedings of Machine Learning Research, pp. 4055-4064. PMLR, 7 2018.
Peter Shaw, Jakob Uszkoreit, and Ashish Vaswani. Self-attention with relative position represen- tations. In North American Chapter of the Association for Computational Linguistics (NAACL), 2018.
Zheng Shou, Dongang Wang, and Shih-Fu Chang. Temporal action localization in untrimmed videos via multi-stage enns. In JEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 1049-1058, 2016.
doi: 10.1 10.1109/CVR.2206.1111
Zheng Shou, Jonathan Chan, Alireza Zareian, Kazuyuki Miyazawa, and Shih-Fu Chang. Cde: patpuuuiinna-ddecoooolutiiiiieie networks for precise temporal action localization in untrimmed videos. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 1417- 1426, 2017.
doi: 10.1109/CVPR.2017.11
S. S. Stevens, J. Volkmann, and E. B. Newman. A scale for the measurement of the psychological magnitude pitch. The Journal of the Acoustical Society of America, 8(3):185-190 1937. doi:
10.1121/1.1915893.
Yi Tay, Mostafa Dehghani, Dara Bahri, and Donald Metzler. Efficient transformers: A survey. 20Xiv:2009.06732. 2020.
Hugo Touvron, Matthieu Cord, Alaaeldin El-Nouby, Piotr Bojanowski, Armand Joulin, Gabriel Syn- naeve, and Hervé Jégou. Augmenting convolutional networks with attention-based aggregation. preprint, arXiv: 13692, abs/2112, 2021.
G. Tzanetakis and P. Cook. Musical genre classification of audio signals. IEEE Transactions on Speech and Audio Processing, 10(5):293-302, July 2002. doi: 10.1
12

---

Published as a conference paper at ICLR 2023
George Tzanetakis, Georg Essl, and Perry Cook. Automatic musical genre classification of audio signals, 2001. URL http:// http://mmmmrr00.11111 ismir net wttt/p/dtttateettititi .
Gül Varol, Ivan Laptev, and Cordelia Schmid. Long-term temporal convolutions for action recogni- tion. IEEE Transactions on Pattern Analysis and Machine Intelligence, 40(6):151-11517 2018.
doi: 10.1 10.1100/PAMM1220722118888
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, ukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in Neural Infor- mation Processing Systems (NewrIPS), volume 30, pp. 5998-6008, 2017.
Limin Wang, Yuanjun Xiong, Zhe Wang. Yu Qiao, Dahua Lin, Xiaoou Tang, and Luc Van Gool. Temporal segment networks for action recognition in videos. IEEE Transactions on Pattern Anal- ysis and Machine Intelligence, 41(11)):770-2755, 2019, doi: 10.1 10911T9MMM.20001 2066668866..
Sinong Wang, Belinda Z. Li, Madian Khabsa, Han Fang, and Hao Ma. Linformer: Self-attention with linear complexity. (eXiv:2006.047660 2020.
Xiang Wang. Shiwei Zhang, Zhiwu Qing, Yuanjic Shao, Zhengrong Zuo, Changxin Gao, and Nong Sang. Oadtr: Online action detection with transformers, International Conference on Computer Vision (ICCV), 2021. cense.
URL https: wwt.c/om//oaaaa http///aangaaag22//0aaaeaa
MIT Li-
Chao-Yuan Wu, Christoph Feichtenhofer, Haoqi Fan, Kaiming He, Philipp Krähenbühl, and Ross Girshick. Long-term feature banks for detailed video understanding. In IEEE/CVF Conference on Computer Vision and Puttern Recognition (CVPR), pp. 284-293, 2019. doi: 10.1109/CVPR. 2019.00037.
Yunyang Xiong, Zhanpeng Zeng, Rudrasis Chakraborty, Mingxing Tan, Glenn Fung, Yin Li, and Vikas Singh. Nyströmformer: nyström-based algorithm for approximating self-attention. Pro- ceedings of the AAAI Conference on Artificial Intelligence, 2021.
Huijuan Xu, Abir Das, and Kate Saenko. R-c3d: Region convolutional 3d network for temporal activity detection. In IEEE International Conference on Computer Vision (ICCV), pp. 5794-5803, 2017. doi: 10. 10.110///CC22211..6111
Mingze Xu, Mingfei Gao, Yi-Ting Chen, Larry Davis, and David Crandall. Temporal recurrent networks for online action detection. In JEFE//CV International Conference on Computer Vixion (ICCV), pp. 5531-5540, 2019, doi: 10.1109//CC.22099.05555 URL https::/gits pytorch
com/ hwtp//ummnnnneeeee
MIT Licence.
Mingze Xu, Yuanjun Xiong, Hao Chen, Xinyu Li, Wei Xia, Zhuowen Tu, and Stefano Soatto. Long short-term transformer for online action detection. In Conference on Neural Information Process- ing Systems (NeurIPS), 2021.
Sijie Yan, Yuanjun Xiong, and Dahua Lin. Spatial temporal graph convolutional networks for skeleton-based action recognition. In AAAI Conference on Artificial Intelligence, pp. 7444-7452, 2018.
Peisen Zhao, Jiajie Wang, Lingxi Xie, Ya Zhang, Yanfeng Wang, and Qi Tian. Privileged knowledge distillation for online action detection. preprint, urXiv:2011.09155 abs/2011.001155 2020.
A APPENDIX
A.1 SCALING PROPERTIES OF CONTINUAL AND REGULAR MULTI-HEAD ATTENTION
A detailed account for the floating point operations involved in computing Regular-, Continual Retroactive-, and Single-output Scaled Product Attentions is given in Tables 6 and 7
Fig. 3 iillustrates the scaling of FLOPs and memory footprint with increasing sequence length and embedding dimension Here, the Continual Retroactive and Single-Output SDAs spend signifi- cantly less FLOPs than the Regular SDA, which scales Onz²) opposed to ((nd) the continual variants. The Continual Single-Oune Outeett SDA reduces memory footprint for all value combinations, and the Continual Retroactive SDA does so when n 2 d.
13

---

Published as a conference paper at ICLR 2023
Table 5: Floating Point Operations for the Scaled Dot-Product Attention in Eq. ! D (-) be efficiently computed as element-wise multiplication with AV.
can
Mul.
Add
Exp
Eq.
n nd
nd(n 1)
0
Eq.
2)
n&d + nd
n² (d 1)
n²²
Eq.
3)
n(n 1) 0
Table 6: Floating Point Operations for the Continual Retroactive Dot-Product Attention in Eqs. 66. The outputs of the exponentials in Eq. 2 and Eq. (3) can be reused in Eq. and Eq. respectively, and are omitted in the count.
Mul.
Add
Exp
Eq.
2(n - 1)d
2(n 2)d + 2(n 1)
2(n 1)
Eq.
nd +
nd + (n 1)
Eq.
2(n - l)d
2 1)d
Eq.
nd
(n 1)d
Eq.
nd +
Table Floating Point Operations for the Continual Single-Output SDA in Eq.
Mul.
Add
Exp
Eq. Eq.
nd + d
(n 1)d + n(d 1)
1
0
2)
nd + d
n
FLOPs step
200M
100M
100M
50M
0
200
800k
Memory (floats)
600k
600k
400k
200K
D
200
400
200
400
(a) 256
(b) 256
Figure 3: FLOPs/step and memory footprint for Regular, Continual Retroactive, and Continual -. Single- Scaled Dot-Produce Attention at varying sequence length and embedding dimension
d. Column (a) has fixed to 256; Column (b) has n fixed to 256.
14

---

Published as a conference paper at ICLR 2023
A.2 SUPPLEMENTAL VISUALISATIONS
For the visually inclined, we supply a complementary graphical depictions of the Continual Retroac- tive SDA corresponding Eqs.
(6 in Fig. 4 the Single-Output SDA in Eq. 7 in Fig.
Memory flow
Kold
K Kmen
k
Knew
d mem
Menocy flow
A eXx((Q))
d= A1
Luew/Vd
Vold
AV
D'AV
Menoey Now
AV
V
mem
Figure 4: Continual Retroactive Dot-Product Attention. The query (Q), key (K), and value (V) matrices are aggregated over time by caching the step vectors Qnew knew, and Unew in each their FIFO queue (denoted by mem)). During each step, only the entries of A associated with qnews know and the oldest K step. kold are computed. The diagonal entries of the row normalisation matrix D well as the AV can be updated retroactively by subtracting features corresponding to kasa and adding features related to knew to the cached outputs of the previous step. Dmem and AVmem. respectively.
Metnory Dow
Meuncyy Dow
k
V
new
mem
KI
nnw
dg
1/2
q
1/2 qK a = exp d
V/al
Figure 5: Continual Single-Output Dot-Product Attention. The key (K) and value (V) matrices are aggregated over time by caching the step vectors knew and Vnew in a FIFO queue. During each step, only the attention output associated with g is computed.
A schematic illustration of the Audio Classification experiments architecture is depicted in Fig.
15

---

Published as a conference paper at ICLR 2023
Genre
MLP
Continual Transformer Encoder
Recycling Positional
Encoding
+
4
VGGIsh
VGGIsh
VGGIsh
+
Spectrogram
4
Waveform
Figure 6: Audio Classification Architecture.
16


Reviews:
[{"review_id": "mtedilp6e9", "reviewer": "Reviewer_bhNe", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes an architectural modification of the transformer module, suitable for online predictions. The modification is meant to prevent heavy re-computations when new tokens arrive.\n\nAuthors propose two flavors of the continual transformer: one in which previous outputs are updated (revised), and one focused only on the prediction corresponding to the new token.\n\nThe paper clearly explains the computational gains of the continual transformer and tests it on a battery of online prediction datasets. The results show the benefits of the continual transformers on tasks that require shallow architectures.", "summary_of_the_review": "Online prediction is crucial for a large set of problems, therefore the work is novel and of interest, and I suggest for the paper to be accepted.", "strength_and_weaknesses": "Strenghts:\n - novelty: to my knowledge there are no previous works trying to optimize computation inside the transformer architecture for online predictions\n - well written paper\n - fair discussion of the empriical results and of the limitations (the new architecture benefits more shallow models)", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "f0ZHaZ6VZjn", "reviewer": "Reviewer_RfrZ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this paper, they propose a new formulation of scaled dot-product attention for token by token inference on continual stream. That reduces the time complexity from O(n^2 d) to O(n d) while keeping the outputs and weights identical to the original Transformer outputs and weights.", "summary_of_the_review": "I think the paper's contribution is important for community, it only requires a more clear presentation.", "strength_and_weaknesses": "Strengths:\n- The proposed approach is novel and provides an efficient and simple solution for continual data streams.\n- It is a significant contribution to reduce the time and memory complexity per prediction while keeping the performance on par.\n- To the best of my knowledge, the statements are correct.\n\nWeaknesses:\n- I had difficulties to follow the paper. I think a re-organization or restructuring of the sections is needed. At least in the beginning of the Section 3, there could be an outline of the section, so we can follow the story in the section.\n- Besides, the experiment results could be analysed in more detail. It is difficult to understand whether the proposed method's accuracy is sufficiently close to the baselines or what are the outcomes of the experiments.  ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "JWISmm1xMCv", "reviewer": "Reviewer_DN9Y", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this paper, the authors propose a novel transformer model of the Scaled-Dot-Product Attention. The authors claim that the proposed continual transformers will accelerate the stream processing of transformer architectures on time-series data. The continual transformer architectures were experimentally validated in Online Action Detection and Online Audio Classification.", "summary_of_the_review": "Overall, I think this is an interesting paper even though the reported results are slightly lower than SOTA. The proposed model is still able to reduce the time complexity. I have some concerns related to motivation and the clarity of presenting or reasoning around some points that I explained in the weaknesses section.", "strength_and_weaknesses": "Strength:\n- The paper is well presented and the proposed architecture is explained in detail.\n- The paper is well positioned with respect to prior work\n- The experiments show that the proposed model reduces the time and memory complexity per predictions.\n\t\nWeaknesses:\n- The motivation in some aspects is not clear. For example, the authors suggest the use of Recycling Positional Encoding to accommodate progressive caching of partial attention results for continual data streams. In section 3.7 they said that “There have been multiple prior works (Shaw et al., 2018; Huang et al., 2019; Dai et al., 2019) which create relative encodings by augmenting the SDA with positional offsets between query and keys. While such a modification to the continual attentions is possible, it hinders compatibility with the regular SDA.`` Why is Recycling Positional Encoding more helpful here and how does the previous model hinder the compatibility? \n- The authors said that the proposed model works better with shallow architecture; is it still applicable to deeper architecture?\n- How is the information accumulated from other tokens prior to classification?\n- Uni-directional Recurrent Neural Networks are an example of Continual Inference Networks. How is the proposed model improved upon the Uni-directional Recurrent Network? For example, in SDA prior step features must be cached, re-loaded, and re-processed by the transformer in each step in correspondence with a predefined window-size of prior steps. Don't the authors think this is very complicated compared with RNN?\n- The experiments show that the proposed model performs well in time and memory reduction but it does not outperform SOTA. Can the authors explain more about that?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster