SkipW: Resource Adaptable RNN with Strict Upper Computational Limit
Authors: Tsiry Mayet
Anne Lambert
Pascal Leguyadec
Francoise Le Bolzer
François Schnitzler
Venue: ICLR 2021 Poster (2021)
Keywords: Recurrent neural networks
Flexibility
Computational resources

Abstract: We introduce Skip-Window, a method to allow recurrent neural networks (RNNs) to trade off accuracy for computational cost during the analysis of a sequence. Similarly to existing approaches, Skip-Window extends existing RNN cells by adding a mechanism to encourage the model to process fewer inputs. Unlike existing approaches, Skip-Window is able to respect a strict computational budget, making this model more suitable for limited hardware. We evaluate this approach on two datasets: a human activity recognition task and adding task. Our results show that Skip-Window is able to exceed the accuracy of existing approaches for a lower computational cost while strictly limiting said cost.

Published as a conference paper at ICLR 2021
SKIPW: RESOURCE ADAPTABLE RNN WITH STRICT UPPER COMPUTATIONAL LIMIT
Tsiry Mayet, Anne Lambert, Pascal Le Guyadec, Françoise Le Bolzer & François Schnitzler InterDigital Inc.
Cesson-Sévigné France
[firstname. aastnamm) hiteeeeiittetrttlcccoom
ABSTRACT
We introduce Skip-Window, a method to allow recurrent neural networks (RNNs) trade off accuracy for computational cost during the analysis of sequence. Similarly to existing approaches, Skip-Wing WiindWinowww extends existing RNN cells by adding a mechanism to encourage the model to process fewer inputs. Unlike ex- isting approaches, Skip-Window is able to respect a strict computational budget, making this model more suitable for limited hardware like edge devices. We eval- uate this approach on four datasets: human activity recognition task, sequential MNIST, IMDB and adding task. Our results show that Skip-Winn Window is often able exceed the accuracy of existing approaches for lower computational cost while strictly limiting said cost.
Keywords: Recurrent neural networks, Flexibility, Computational resources.
INTRODUCTION
Since Recurrent Neural Networks (RNN) have been introduced Williams et al. (1986), they have become one of the reference methods to process sequences. A typical architecture is the Long-Short- Term-Memory neural network (LSTM) which allowed improvement in natural language processing such as aageevocabuuarry speech recognition (Sak et al. 2014 Li Wu, 2015). Used with CNNs they have also reached state of the art in automatic image captioning (Vinyals et al. 2015).
Deep learning models are now brought closer to the user rather than running in a distant cloud, helping to reduce latency, network congestion, and improving data security and privacy. However, smartphones and user devices impose additional constraints such as limited computation or energy. Handling these constraints has become active research topic (Zhang et al.) 2017 2018 Howard iet al., 2019 Wu et al. 2019 Cai et al. 2020). User devices can also host multiple processes running at the same time and starting stopping abruptly. modifying the constraints affecting the processes. Few works have considered models that can be modified at run time to adapt to an evolving compu- tational limit (Yu et al. 2019: Yu & Huang. 2019 Guerra et al. 2020 Din et al., 2020). However, none of these focus on sequences and therefore none address the problem of adapting the model in the middle of sequence.
In this context, this paper introduces Skip-Winday (SkipW), a flexible recurrent neural network ar- chitecture: its computational cost can be dynamically adapted during a sequence analysis to meet real time constraints changes. The proposed architecture can be combined with any RNN cell and allows to strictly limit the computational resources used to avoid exceeding a given budget. Further- more, empirical experiments on four data sets (Adding Task, MNIST, IMDB and HAR-2D-POSE) demonstrate that this subsampling architecture interesting in itself. Skip- Window matches or ex- ceed the accuracy of existing approaches for a given computational cost. In addition, measurements on specific processors highlight that SkipW produces real computational and energy savings.
2 RELATED WORK
Typically, RNNs maintain a "state", a vector of variables, over time. This state is supposed to accumulate relevant information and is updated recursively. Each input of the sequence is typically

---

Published as a conference paper at ICLR 2021
processed by some deep layers and b) then combined with the previous state through some other deep layers to compute the new state. Hence, the RNN can be seen as a function taking a sequence of inputs
($...... ST). Each state 8, is computed from 9t-1 and 2t by a cell S of the RNN. As neural networks are increasingly run on limited hardware, recent research has focused controlling their computational cost.
(2) (2)..... 2r) and recursively computing set of states
2.1 FLEXIBLE NEURAL NETWORKS
A few architectures have recently been designed to adapt the computational complexity of a Deep Neural Network (DNN) without reloading the whole model. This can be achieved by remov- ing/adding neurons Yu et al. 2019; Yu & Huang. 2019) or by modifying the quantization of the weights (Guerra et al. 2020 Jin et al., 2020). An efficient embedding a mixture of Convolu- tional Neural Network (CNNs) also allows to add or remove several models the same time, hence changing the computational cost (Ruiz& & Verbeek 2019).
2.1.1 THRRNN
For RNNs specifically, ThrRNN (Lambert et al. 2020) aims to control computation time by not processing some imputs. This is controlled by an update gate uy. The tradeoff between the average accuracy and the average number of updates can be modified during inference by changing a single parameter thr. ThrRNN can wrap any RNN cell S:
= Jiinarize (ūe; Uhr) {1
if ür < thr otherwise
(1)
ج/ = o(Ws, St +b
(2)
dc+1 A ú + (1 ( + min( Aüe, 1-;))
(3)
= ue (8t-1, + (1 u4) )
(4)
When input is processed, update gate computes the quantity Ad that determines how many inputs will skipped. In practice the Au are accumulated in ūn until in 2 thr.
2.2 RECURRENT NEURAL NETWORK WITH LOW COMPUTATIONAL COMPLEXITY
Several architectures have been proposed to limit or reduce the computational cost RNNs. but this cost cannot be adapted at inference. A first class of architectures dynamically reduces computation based on the input. SkipRNN (Campos et al.) 2018) predates and is similar to ThrRNN, except that the binarization function does not change. A similar mechanism has been proposed by Zhang et al. 2019)) Other architectures directly select the next input to process (Yeung et al. 2016 Yu et al.]
Hansen et al. 2019 Song et al., 2018). Early exit has also been investigated by Dennis et al. Tao et al. (2019) also use X; as input to an update gate. So do Seo et al. 2211));Jrmnin et al.
2019
2017
al. 2020). However, they do not skip any input but perform partial state updates.
A second class of architectures focuses on reducing the overal cost the RNN. FastRNN is an RNN augmented with residual connection with extra scalar parameters and FastGRNN is improved FastRNN: the residual connection extended to a gate and RNN matrices are low rank, sparse and quantized (Kusupati al. 2018). Other architectures reduce the RNN length. Chan al. (016)) train an encoder to reduce the input length. Yeung et al. (2016); Shan et al. (2018): Chen al. (218) propose various mechanisms to summarize subsequences of windows of inputs.
2.3 RECURRENT NEURAL NETWORK WITH HIERARCHICAL DEPPNDDEN COMPLEXITY
A class of architectures focuses on hierarchy level concept to reduce the complexity. These methods are mainly used in the context of multi-layer RNNs where each layer is supposed to model a different level in the hierarchy (e.g. for corpus the levels could be documents, paragraphs, sentences, words, letters). These approaches are based on the fact that a hierarchical separation exists within a sequence of inputs, which might not always be the case.
In (Koutnik et al.) 2014), the hidden state is partitioned into different modules, each module has its own clock period, meaning that they will be updated different times. Skipping updates of part of
2

---

Published as a conference paper at ICLR 2021
Y2
Yu41
YL42
Y2L
Ww
iw'
W.
Sw
Sw
Sw
Sw
Sw
Sw
5
S-1
SLt1
221-1
X
X2
X1
ML+1
XLx2
X2L
W2
Figure 1: Skip-window computes update gates the beginning of each window inputs.
the hidden state decreases the computational cost. In (Koutnik et al. 2014), the update periods are chosen arbitrarily, for example using an exponential series.
For stacked-RNNs, Chung et al. (2017): Chang et al. (2017) conditionally update each layer based on feature level criterion, by dilating skip connection. Layers close the inputs would model lower feature levels and be updated more frequently. Further layers would model higher level features. In (Chung al., 2017). ), a layer modeling sentences would be updated only when word is processed entirely (in a model fed character by character), from the layer modeling words. Before the end of word is reached, the state of the former layer is copied across input steps.
2.4 RELATIONSHIP TO OUR WORK
ThrRNN is the closest model to SkipW. Both are flexible RNNs and skip some inputs. However, sequences. This induces two variabilities: a) inter-sequence variability: the model will not use the same number of updates for every sequence; and b) intra-sequence variability: the number of updates will not be uniform across time steps, updates may be concentrated in a certain part of the sequence. These two variabilities can cause the model exceed its computational budget and, therefore, either shut down or delay the out- put. SkipW does not have this problem as it strictly enforces computational constraint over each window of inputs.
ThrRNN optimizes computational cost average
Other strategies for flexible models are not straightforward to apply to RNN. They require special- ized training algorithms. They have never been applied models processing inputs of RNN or to make an RNN flexible and it is not clear how they would need to be modified. Furthermore, these models adapt between independent inputs whereas, for sequences, adaptation necessary between orthogonal
time steps. RNN architectures with low complexity offer flexibility. They could be combined with and benefit from our approach. However, SkipRNN (which we based on) and related methods have one big advantage over others: by skipping inputs, they also skip any modification of an input, such as processing by an expensive CNN for images. As SkipW makes decision over window of inputs, it has some superficial similarity to methods summarizing windows or hierarchical RNNs. However, SkipW a) does not summarize windows and b) does not even look at these inputs before deciding what skip.
approach. They do not
SKIP-WING KIID-WINDOWS ARCHITECTURE
Skip-Windows Windows (SkipW) is wrapper for a RNN cell S. Ises conditional computation mechanism to skip some updates. Rather than at each input 2t, update gates are computed at the beginning of windows of inputs, that is, every L time steps (Figure I]. In other words, before any new L-size window of inputs, L-size vector üw is computed. üw [ can be seen as the importance of input i in the window.
Then, the architecture includes a select mechanism. This function takes as input the vector üw and outputs the vector uy. setting K elements to value that ensures the associated inputs are not processed (0 in Figure 2 Therefore, ensures that at most K out of every L inputs will be processed. In other words, it forces the RNN cell skip (I. K) out of every T. inputs. This
3

---

Published as a conference paper at ICLR 2021
Uwws 1-1 {
octivation
Topk
TWe W
fannarie
K W
A
ut
uw
mod
indice window
indice in sequence
(W,
Activattoo_ new
S
N
St
N
[W,6.]]
X
Figure 2: TopK-based Skip-Window cell implementation example.
ensures a strict upper bound on the computational cost of the model for sequence and for each window, therefore alleviating the inter-sequence variability and intra-sequence variability issues.
Similarly to other works, the binary state update L-size vector, uw, is then obtained by binarizing the remaining values as in equation [ For example, by setting all values below a threshold a value that ensures the associated inputs are not processed (0 in Figure 2
example of the Windww cell implementation is represented in Figure 2 select к is implemented updates. The lopk operation keeps unchanged the K highest value in úwAs, and sets the (L - K) others to O.
In this case, topx function. This enforces the strict constraint on the number of
The corresponding architecture can be characterized as follows:
St U4 S(s 2t) + (1 we) 8t-1 úw = 7 (W (s:11,t) + bw)) + (1 - 7) u...
(5)
(6)
{1 ifi==0
(7)
0 otherwise
mod T.
(8)
K W.
top (ūw.))
(9)
44 = foinarize (ūW,, thr) { if [. thr
(10)
otherwise
where W. is a weight matrix of size (N + 1) x L, N is the number of hidden units as defined by the RNN cell S. bw is L-vector bias, is the sigmoid function and mod is the modulo operation. Instead of a topk function for select it is also possible to use a stochastic sampling mechanism that randomly selects (without replacement) K out of L elements of ūw where the probability of
selecting each element of index is proportional to ūw [i]. Some select k alternatives are discussed and evaluated in Appendix H
Including the time step t in equation 6 is also optional and can be replaced by a value ensuring the state is not static no update made window. For example, the number of inputs since the last update or the number of windows already processed.
Training the model The model is trained to minimize a two-part loss, similarly to Campos et al. 2018). The first term measures the accuracy of the task, and the second one penalizes inputs used:
I Lbudget
U1
(11)
1=1
where À is the cost associated to the use single input. More experimental details are provided in Appendix B
4

---

Published as a conference paper at ICLR 2021
The model is differentiable except for the foinarise and topk function. To train the model using standard backpropagation the et al. (2018) for fhinarize.
Error gradients
estimator is used as done in Campos
Other alternatives might involve reinforcement learning such as REINFORCE Williams 1992 or, in the case of the topx function, the usage of a differentiable topk proposed in Xie et al. 20200) Early experiments using a differentiable topx (Xie et al.] 2020) have shown worse results than the straight-through estimator. This suggests that constraining computation may be an interesting approximation for a topx operation.
Adapting computational cost at inference During inference, adapting the tradeoff between model performance and computational cost can be done using two factors: the K in equation 2 and the thr in equation 10 These two parameters can be modified together or one time. Increas- ing/lowering thr parameter in [0, 1| encourages the model to process fewer/more inputs. Changing K {0 L} forces the model to process at most K/ L of the window.
Choice of the window size hyper-parameter By the nature of the model, the task can influence the choice of L. It can be hand tuned or computed using typical hyper-parameter search methods such grid search. Choosing small L allows the model to make update decisions for the near future only but offers less choice in operating points. Similarly a bigger L requires the model to predict its update decisions for bigger time span but offers more flexibility. At the extreme when L each window consists of a single input.
4 EXPERIMENTS
We empirically show that SkipW a) learns accuracy / computational tradeoff's on par with or, surpris- ingly, sometimes better than our baselines SkipRNN and ThrRNN on all data sets; b) upper bounds computational cost with gradual impact on accuracy except on sequential MNIST; c) enables chang- ing the tradeoff in the middle of a sequence. To evaluate the computational benefit induced by skipping part of the input sequence we use the number of inputs processed by the model, as this measure is independent from the hardware and the framework used implement the models. In ad- dition, we also show how a reduction of the number of inputs processed translate into computational and energy savings on tiny devices.
We evaluate our approach on four data sets. Human Activity Recognition (HAR) (Ofli et al. 2013 consists of 2D-position sequences of 18 joints across a 32-frames videos recorded 22Hz 1=5 seconds). Each sequence is labeled by one of the 6 actions performed by 12 subjects filmed from 4 angles. Sequential MNIST (Lecun et al., 1998), the handwritten digits data set, consists of digital picture made of 28 x 28 pixels. Each image is flattened into 784-sequence of one pixel. Adding Task Hochreiter Schmidhuber (997), consists of tuples-sequences (value, marker) E R x {0, 1), where the expected output is >; marker x value. IMDB (Maas et al.) 201 consists of movie reviews with a positive/negative annotation. The reviews were padded or cut to a length of 200 words in our experiment. For HAR, two stacked RNNs are used, but only one for Adding Task, Sequential MNIST and IMDB. More details can be found in Appendix A on Adding Task, HAR and Sequential MNIST are further developed in Appendices D F and
and experimental results
4.1 ACCURACY AND COMPUTATIONAL TRADEOFFS
In Figures 3 to 6 the baselines SkipRNN and ThrRNN are compared to SkipW with various values for L and K for all data sets. Small L values may not offer good tradeoffs when varying K. See for example L = 4 in Figure That's 's not surprising: often the number of inputs processed can be significantly reduced without affecting accuracy. For example, SkipRNN on HAR can process as few as 15% inputs without affecting accuracy. Using L = 4 and K = 1 limits complexity at 20% only. So, for such a small L, varying K has almost no impact on average. Larger window sizes, on the other hand, offer more tradeoff's when changing K. For example, on HAR, for L E {8, 16), K can take more values, and for small K computational gains are traded off for accuracy. For example, for L = 16, reducing K from 4 to 1 more than halves the number of inputs processed for drop of 3.6% in accuracy. A similar behavior can be observed on Adding Task and IMDB, On MNIST (Figure 5) lowering K trades off accuracy for computational cost worse ratio. This is the only
5

---

Published as a conference paper at ICLR 2021
[3-16
K=
thr=0.5
trade-off SkipRNN
1.00
random subsamp.
Accuracy
0.95
K=1
periodic subsamp.
SkipW A=1e-2, L=4
0.90
SkipW 1=1e-2, L=8
SkipW 2=2e-2, L=16
0.85
ThrRNN A=1e-1
0.80
0.0
2.5
5.0
7.5
10.0
12.5
15.0
17.5
20.0
Inputs processed (%)
Figure 3: Impact of the parameter K on accuracy/updates tradeoff for HAR. Comparison between ThrRNN (thr=0.5 1.0), SkipW(L=4,88 thr=0.5, K=1 to L) and SkipRNN (A=le-3 3e-1). For random subsampling, the shaded area corresponds to times the standard deviation on each side of the mean value (50 evaluations).
0.10
Mean square error
trade-off SkipRNN
0.08
random subsamp.
0.06
ThrRNN A-3e-4
K=2
SkipW 4= L=10
0.04
K-4
0.02
K=9
0.00
20
40
60
80
100
Inputs processed (%)
Figure 4: Impact of the parameter K on mean square error and inputs processed for Adding Task. Comparison between ThrRNN (A=3e-4, thr=0.5 to 1.0) and SkipW (A=2e-4, T==10, thr=0.5, K=1 to L). The dotted line corresponds to the performance of individual SkipRNN models trained with different values of À (from λ=le-5 to A=5e-4) and the red line to baseline randomly sampling inputs. The shaded area corresponds to times the standard deviation around the mean (100 evalu- ations).
data set out four where SkipW is unable to match the performance of SkipRNN while changing K. Even in this case, independent SkipW (with fixed K L) provide comparable or better tradeoff's than SkipRNN (Appendix(E) In addition, SkipW performs as well as ThrRNN on MNIST. Figures allo include comparison two naive subsampling strategies selecting set number of inputs. Random subsampling samples inputs based on a uniform distribution. Periodic subsampling selects them at regular interval. On Adding Task, these methods equivalent. Both naive strategies worse than SkipW on both data sets.
SkipW enforces K/ upper bound on the number inputs processed in each window. Even when the average number of updates is not impacted much by change in K, individual sequences can be impacted, Figure 7 illluttraess this impact with violin plot of the number of inputs processed per sequence for various K and L = 8 on HAR. Decreasing K below 3 impacts the maximum observed number updates over the whole sequence. However, even changes above K have an impact. Even though the observed maximum number of updates does not change, the violin changes some sequences have fewer inputs processed. This is due to the fact that computational constraint enforced over each window. So, for K 5. some sequences are prevented from exceeding the computational budget some windows of inputs.
It is perhaps surprising that SkipW can achieve both higher accuracy and lower computational cost than SkipRNN and ThrRNN, as the former decides on the next K inputs to process periodically whereas the baselines decide the next imput whenever has processed one and so decide more often and with more information. They can thus adapt the sampling pattern faster. However, we have observed that these baselines tend process input regularly, if there is no information in

---

Published as a conference paper at ICLR 2021
1.0
trade-off SkipRNN
SkipW L=28
Acouracy
0.9
ThrRNN A-1e-4
SkipW L-28 1e-4
SkipW L-28 A=1e-2
0.8
0.7
0
10
20
30
40 50
Inputs processed (%)
Figure 5: Impact of the parameter K on accuracy and imputs processed for MNIST. Comparison between ThrRNN (A=le-4, Uhr=0.5 to 1.0) and SkipW (A=le-4 and X=le-2, I.=28, Uhr=0.5, K=1 T.). The dotted line corresponds to the performance of individual SkipRNN models trained with different values of X (from A=le-4 to 2ele-2). The dashed line represents the trade-off achieved by different SkipW models (L=28) (from x=0 to >=le-2).
0.9
Accuracy
0.8
trade-off SkipRNN
SkipW, L=10
SkipW 0= L=10
0.7
SkipW A= L=25
ThrRNN A=1e4
GRU
0.6
40
80
100
Inputs processed (%)
Figure 6: Impact of the parameter K on accuracy and inputs processed for IMDB. Comparison between ThrRNN (X=le-4, Ihr=0.5 to 0.9) and SkipW (2=0, L=10 or 25, U/r=0.5, K=1 to L). The dotted (SkipRNN) and dashed (SkipW L=10) lines correspond the performance individual models trained with different values of À (from x=0 to x=le-2)
the signal. This increases the computational cost without benefiting accuracy. We believe this is due to the increment mechanism (Equation 3). To skip C inputs, Au, (Equation 2 must be smaller than 0.5/C. We conjecture that at some point, for large C, the model is unable to differentiate between these small values and so no more than C skips are performed. So both methods are biased in the type of skip patterns they details. The best method depends on the task: in our experiments SkipW seems to work better than SkipRNN on data sets, similarly one and slightly worse on IMDB.
learn, but differently. Please Appendices [J33 and F for more
SkipW is able to learn where relevant inputs are and tends not to use irrelevant inputs. This is best illustrated on AddingTaske Task. Let mi be the index of the first marker, and m2 the index of the second one. The inputs can be divided into four parts p:, E {1, 3, 4}:
pl (z, 0 < m1)
p2 (xy mi
(12)
p3 [z, 25 m2)
p4 = (x. m2 <i< 50)
(13)
Ideally the model should skip all inputs in Pa and Pa where there no marker, while using all the inputs in Pı and in P3 where marker can appear.
Figure illustrates that SkipW skips inputs in different parts of the sequence for various K. For K L (training point), almost no inputs are skipped in Pı and ps, where the markers are, but some are skipped in P2 and p4, where there is no marker. Not all inputs are skipped in p2 and p4. That's not surprising: decisions to skip are taken at the start of window, so even if a marker is present in the first input of the window, SkipW will not update its decision to process other inputs in the window. Skips as the model can no longer process all inputs. Finally, when K < 5, SkipW can no longer process the first 5 inputs and skips in p1 start happening. Values of K smaller than but close to T. force the
still mainly made in part P2 and P4 for these K values but start increasing in ps
7

---

Published as a conference paper at ICLR 2021
30
30
Inputs processed (%)
ThrRNN A=1e-1
L=
25
0.5=
25
20
20
15
Acc=95.7
15
10
10
Acc=97.0
Acc=96.6
3
4
5
0.5
K
thr
Figure 7: Left: Impact of the K parameter on the computational cost upper limit (SkipW: X=6e-2, T==8, thr=0.5). Right: ThrRNN with similar average inputs processed is provided for comparison.
Inputs processed (%)
100
p1
80
p2
p3
60
p4
40
20
2
4
10
K
Figure 8: Proportion of inputs processed in Adding Task for different parts of the sequence defined by equations 12 and 13 while changing K with thr=0.5, for model trained with A=2e-4 and L=10. correspond to the training configuration.
The values K
model to skip some inputs and to 'fail' Adding Task. Note that both the binarization function and the inclusion of the inputs the update gate are necessary for this behavior. Please see the ablation study in Appendix D.4 for more information.
Modifying thr impacts the accuracy processing tradeoff well. Increasing thr gradually reduces both accuracy and average computational cost. This is similar to ThrRNN, Changing thr does not affect the upper bound on computational cost but can provide more accuracy processing tradeoff' points. Some examples are provided in Appendix C
4.2 MODIFYING THE TRADEOFF DURING INFERENCE
Modifying (thr, K) is also possible during the analysis of sequence. Results change between two different pairs of (thr, K) values are shown in Figure The average accuracy and compu- tational cost of the analysis of the test sequences are reported as a function of the position of change. The position at the bottom left (resp. top right) of the graph corresponds to the operating point tradeoffy (resp. tradeoff,) when processes the whole sequence. The accuracy typically remains between the accuracy of the individual models and increases almost monotonically from tradcoff, accuracy to tradcoff, accuracy. This suggests that SkipW can switch between operating points during the analysis of sequence. This behavior observed all data sets, for various training runs and (thr, K) configurations. More details are provided in the supplementary material D and
4.3 REAL TIME EXPERIMENTS
We evaluate the performance SkipW on small hardware to showcase its performance in the setting it is designed for. We implement the full service, from images to activity recognition, Nvidia Jetson Nano platform. the HAR-2D-POSE data set, OpenPose is used to compute poses on images, but the embedded GPU is not powerful enough this OpenPose. Instead, choose
8

---

Published as a conference paper at ICLR 2021
1.0
(%0 posseposd
Accuracy
0.9
100
Accuracy Inguts
0.8
thr=0.65
Ippuu
0.7
40
60
80
100
Position of change (% the sequence)
Figure 9: Modifying (thr, K) during the sequence on HAR for SkipW (A=le-2, L=8); from tradeoff, (thr=0.4, K=8, acc/updates tradeoff 99.3%/15.5%) to (rade K=l, acc/updates tradeoff=73.%%449))
Inputs processed (%)
10
15
20
25
30
[1,0.6]
M
Inputs processed (%)
[1,0.5]
[K,thr]
[2.0.1]
[3,0.1]
O
250
500
750
1000
1250
1500
1750
Sequence latency (ms)
Figure 10: Boxplots of inference latency time for a HAR Service based on SkipW (A=le-2, L=8) coupled with Posenet model running Jetson Nano.
use PoseNet (MobileNetVi architecture with a 0.75 multiplier) model which is much more efficient run on such small platform. In our implementation, PoseNet model running on the embedded GPU takes roughly 120 ms to compute a pose on 640x480 pixel image, while the SkipW model takes around 30 ms perform all state updates for sequence.
Figure 10 presents the individual inference time of 1000 HAR image sequences processed by SkipW coupled with the PoseNet detection model on a Jetson Nano platform. As expected, when K de- creases, the run time decreases sharply. This gain is largely due to the lower number of pose detec- tions that need be computed. By drastically limiting the number of images used as input, SkipW saves a large amount of time, computation and energy. Results on Jetson TX2 and Raspberry Pi4 lead to similar conclusions (Appendix G
5 CONCLUSION
We presented Skip-Window, novel RNN cell architecture that dynamically controls the number of inputs processed during the analysis of sequence. SkipW allows adapt the computational cost during and between sequence analysis without reloading any weight. Unlike existing flexible RNNs, SkipW can enforce strict upper bound on the number of updates performed over a time interval. Therefore, SkipW can operate without exceeding a given computational budget across time interval. Furthermore, our results show that 3Xip-Window is able to exceed the accuracy of existing flexible RNNs for lower computational cost and to actually reduce computation. This makes SkipW well suited for shared hardware with real time constraints.
ACKNOWLEDGMENTTS
This work was supported by the European Commission under European Horizon 2020 Programme, grant number 951911 A14Media.

---

Published as a conference paper at ICLR 2021
REFERENCES
Cagla Deniz Bahadir, Adrian V Dalca, and Mert R Sabuncu. Learning-bast based optimization of the sadee-sampling pattern MRI. In International Conference on Information Processing Medi- cal Imaging, pp. 780-792. Springer, 2019.
Muhammed Fatih Balın, Abubakar Abid, and James Zou. Concrete autoencoders: Differentiable feature selection and reconstruction. In International Conference on Machine Learning, pp. 444- 453, 2019.
Han Cai, Chuang Gan, Tianzhe Wang. Zhekai Zhang, and Song Han. Once-for-all: Train one network and specialize it for efficient deployment. In International Conference Learning Representations, 2020. URL
1x1HHWS
Víctor Campos, Brendan Jou, Xavier Giró Nieto, Jordi Torres, and Shih-Fu Chang. Skip RNN:
Learning to skip state updates in recurrent neural networks. In International Conference on Learn- ing Representations, 2018. URL /ttp://es/////eeeeeeeeeee net/ forum wiwprummmiddd-WWWxyyxyy
William Chan, Navdeep Jaitly, Quoc Le. and Oriol Vinyals. Listen, attend and spell: A neural network for large vocabulary conversational speech recognition. In 2016 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 4960-4964. IEEE, 2016.
Shiyu Chang, Yang Zhang, Wei Han, Mo Yu, Xiaoxiao Guo, Wei Tan, Xiaodong Cui, Michael Withrock, Mark A Hasegawa-Johnson, and Thomas S Huang. Dilated recurrent neural networks. Advances in Neural Information Processing Systems, 30:77-87, 2017.
Mengzhe Chen, Shiliang Zhang, Ming Lei, Yong Liu, Haitao Yao, and Jie Gao. Compact feed- forward sequential memory networks for small-footprint keyword spotting. In Interspeech, pp. 2663-2667, 2018.
Junyoung Chung. Sungjin Ahn, and Yoshua Bengio. Hierarchical multiscale recurrent neural net- works. In 5th International Conference on Learning Representations, ICLR 20/7, 2017.
Don Dennis, Durmus Alp Emre Acar, Vikram Mandikal, Vinu Sankar Sadasivan, Venkatesh Saligrama, Harsha Vardhan Simhadri, and Prateek Jain. Shallow RNN: accurate time-series classification resource constrained devices. In Advances in Neural Information Processing Systems, pp. 12896-12906, 2019.
Stuart put.
Eiffert. 2018
RNN for human activity
recognition
2d pose in-
URL https:://iihhb. com/ stuarteiffert
RNN for- Moor-HmmanAAt...
Input.
Luis Guerra, Bohan Zhuang, Ian Reid, and Tom Drummond. Switchable precision neural networks. arXiv preprint arXiv:2002.02815, 2020.
Christian Hansen, Casper Hansen, Stephen Alstrup, Jakob Grue Simonsen, and Christina Lioma. Neural speed reading with structural-jump--LSTM.. In International Conference on Learning Rep- resentations, 2019. URL https: /ttp:////////eeeeee/ee net wwweeeeeteouuue fwrummiiciioooo F
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8): 1735-1780, 1997.
Andrew Howard. Mark Sandler, Grace Chu, Liang-Chies Chen, Bo Chen, Mingxing Tan, Weijun Wang, Yukun Zhu, Ruoming Pang, Vijay Vasudevan, et al. Searching for mobilenetv3. In Pro- ceedings of the IEEE International Conference on Computer Vision, pp. 1314-1324, 2019.
Iris AM Huijben, Bastiaan S Veeling, and Ruud JG van Sloun. Deep probabilistic subsampling for task ada-tive compressed sensing. In International Conference on Learning Representations, 2019. URL https: httpp:://ppereeiii http////eeee/eeee///////// net www.ee/ooon..dSeeeeeeeee
Yacine Jernite, Edouard Grave, Armand Joulin, and Tomas Mikolov. Variable computation in current neural networks. In International Conference on Learning Representations, 2017. URL
https:://penner/// www.www..eeeeeeeeeeeeeeeeeeeeeee http://eweeeeeeeeeeoooo/oo/////o
10

---

Published as a conference paper at ICLR 2021
Qing Jin, Linjie Yang, and Zhenyu Liao. Adabits: Neural network quantization with adaptive bit- widths. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recogni- tion, pp. 2146-2156 2020.
Jan Koutnik, Klaus Greff, Faustino Gomez, and Juergen Schmidhuber. clockwork RNN. In International Conference Machine Learning, pp. 1863-1871, PMLR, 2014.
Aditya Kusupati, Manish Singh, Kush Bhatia, Ashish Kumar, Prateek Jain, and Manik Varma. Fast- grnn: A fast, accurate, stable and tiny kilobyte sized gated recurrent neural network. In Advances in Neural Information Processing Systems, pp. 9017-9028, 2018.
Anne Lambert, Françoise Le Bolzer, and François Schnitzler. Flexible recurrent neural networks. In Machine Learning and Knowledge Discovery in Databases, 2020.
Quoc Le, Navdeep Jaitly, and Geoffrey Hinton. A simple way initialize recurrent networks of rectified linear units. arXiv preprint FrrXiv:150..00000 2015.
Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. caldient-bassed learning applied to document recog- nition. Proceedings of the IEEE, 86(11):227--2324 1998.
Xiangang Li and Xihong Wu. Constructing long short-term memory based deep recurrent neural networks for large vocabulary speech recognition. In 2015 IEEE International Conference on IEEE, 2015.
Acoustics, Speech and Signal Processing (ICASSP), pp.
Yikang Li, Tianshu Yu, and Baoxin Li. Recognizing video events with varying rhythms. arXiv preprint arXiv:2001.0500 2020.
Andrew Maas, Raymond E Daly, Peter T Pham, Dan Huang, Andrew Y Ng. and Christopher Potts. Learning word vectors for sentiment analysis. In Proceedings of the 49th annual meeting of the association for computational linguistics: Human language technologies, pp. 142-150, 2011.
Daniel Neil, Michael Pfeiffer, and Shih-Chii Liu. Phased LSTM: Accelerating recurrent network training for long or wentt-baeed sequences. In Advances in Neural Information Processing Sys- tems, pp. 3882-3890, 2016.
Ofli, R. Chaudhry, G. Kurillo, R. Vidal, and R. Bajesy. Berkeley MHAD: A comprehensive multimodal human action database. In 2013 IEEE Workshop on Applications of Computer Vision (WACV), pp. 53-60, 2013.
Jeffrey Pennington, Richard Socher, and Christopher D. Manning. Glove: Global vectors for word representation. In Empirical Methods Natural Language Processing (EMNLP), pp. 1532-1543, 2014. URL htt.htt::/ www. awwweb. www.wwwwwwwww..ee..ee.eoee.e.eee oztp/aathologyyDie---11 -162
Adria Ruiz and Jakob J. Verbeek. Adaptative inference cost with convolutional neural mixture models. 2019 IEEE/CVF International Conference on Computer Vision (ICCV), pp. 1872-1881, 2019.
Hasim Sak, Andrew W. Senior, and Françoise Beaufays. Long short-term memory based recur- rent neural network architectures for large vocabulary speech recognition. CoRR, abs/ ftbs//402..128, 2014. URLpttpp: //a //tp///aavvvv////////e//eee/aava wrw. / 1402. 1128
Minjoon Seo, Sewon Min, Ali Farhadi, and Hannaneh Hajishirzi. Neural speed reading via RNim-RNN. International Conference on Learning Representations, 2018. URL https:
//openreview. net. wet.fformm/iii dotp://ooommmm----------------
Changhao Shan, Junbo Zhang, Yujun Wang, and Lei Xie. Attention- end-to-end models for small-footprint keyword spotting. In Proc. Interspeech 2018, pp. 2037-2041, 2018. doi: 10.
21437/Imersppecch.011 2011-pp 1777. URL http: doi www./ogg.1.oo 214377 htt//Inteere Interspeerrr...... 2018-1777
Inchul Song, Junyoung Chung, Taesup Kim, and Yoshua Bengio. Dynamic frame skipping for fast speech recognition in recurrent neural network based acoustic models. In 2018 IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP), pp. 4984 4988. IEEF, 2018.
11

---

Published as a conference paper at ICLR 2021
Jin Tao, Urmish Thakker, Ganesh Dasika, and Jesse Beu. Skipping state updates without training the original model. In Proceedings of the 1st Workshop on Machine Learning on Edge in Sensor Systems, pp. 31-36, 2019.
Oriol Vinyals, Alexander Toshev, Samy Bengio, and Dumitru Erhan. Show and tell: A neural image caption generator. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 3156-3164, 2015.
Ronald J. Williams. Simple statistical gralient- algorithms for connectionist reinforce- ment learning. Mach. Learn 8(3-4))229-256 May 1992. ISSN 0885-6125, doi: 10.1007/ BF00992696. URLhttps:://ott http///i..ogg////////
Ronald J. Williams, Geoffrey E. Hinton, and David E Rumelhart. Learning representations by back-propagating errors. In Nature 1986, pp. 533-536, 1986. doi: 10. 10.10333333333.. URL
https://ui. attps::/ui.adsabs... adsabs. wetteaasshaavaare hwrvaaaraaa.o..aa eed abs http://aaab/996NNttttut 323 533R/ abstract)
Carole-Jean Wu, David Brooks, Kevin Chen, Douglas Chen, Sy Choudhury, Marat Dukhan, Kim Hazelwood, Eldad Isaac, Yangqing Jia, Bill Jia, al. Machine learning at facebook: Understand- ing inference at the edge. In 20/9 JEEE International Symposium on High Performance Computer Architecture (HPCA), pp. 331-344. IEEE, 2019.
Yujia Xie, Hanjun Dai, Minshuo Chen, Bo Dai, Tuo Zhao, Hongyuan Zha, Wei Wei, and Tomas Pfister. Differentiable top-k operator with optimal transport, 2020.
Serena Yeung, Olga Russakovsky, Greg Mori, and Li Fei-Fei. End-to-end learning of action detec- tion from frame glimpses in videos. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 268872687, 2016.
Adams Wei Yu, Hongrae Lee, and Quoe Le. Learning to skim text. Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Pupers), pp- 1880-1890, Vancouver, Canada, July 2017, Association for Computational Linguistics. doi: 10. 18653/v 1P111111111221 URL/ttps:: //ww: wwww aww.wb.ww....... http:w/wwww......./..to..ooo....
Linguttsiis
Jiahui Yu and Thomas Huang. Universally slimmable networks and improved training techniques. In Proceedings of the IEEE International Conference on Computer Vision, pp. 1803-1811, 2019.
Jiahui Yu, Linjie Yang, Ning Xu, Jianchao Yang, and Thomas Huang. Slimmable neural networks. In International Conference on Learning Representations, 2019. URL httl:tttts://peeeiiiiii
ftt.://rummmieee gMCsAqY
Shucong Zhang, Erfan Loweimi, Yumo Xu, Peter Bell, and Steve Renals. Trainable dynamic sub- sampling for end-to-end speech recognition. Proc. Interspeech 2019, pp. 1413-1417, 2019.
Xiangyu Zhang, Xinyu Zhou, Mengxiao Lin, and Jian Sun. Shufflenet: An extremely efficient convolutional neural network for mobile devices. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 6848-6856, 2018.
Yundong Zhang, Naveen Suda, Liangzhen Lai, and Vikas Chandra. Hello edge: Keyword spotting on microcontrollers. CoRR,
128, 2017. htt.:ttp://arxl...rr//bb////////
0 77128
12

---

Published as a conference paper at ICLR 2021
A EXPERIMENTAL SETTINGS DETAILS
We evaluate our approaches on two data sets:
Human Activity Recognition (HAR): HAR is an action recognition dataset consisting
of 2D pose estimations extracted from videos (Eiffert 2018). The 2D pose estimation was performed on a subset of the Berkeley Multimodal Human Action Database (MHAD) dataset (Offi al. 2013). Six actions (Jumping in place. Jumping jacks. Punching (boxing), Waving two hands, Waving one hand, Clapping hands) are considered for a total of 1438 videos recorded at 22Hz. Each action must then be identified based a sequence of 32 frames ( 1.5 sec). Each video gives several sequences by applying an overlapping ratio. A pose extracted from each frame and estimated by 18 body joints expressed in 2D coordinate system. Following the parameter setting defined in (Eiffert) 2018), the dataset is split into 2 independent partitions 22625 sequences for training and 5751 for validation.
The model architecture consists of a two-stacked RNN of 60 GRU cells each followed by a fully connected layer with RELU activation function. The model is trained with batches of 512 sequences using a decaying learning rate for 600 epochs. The best performance was obtained when the model was initialized with a model trained with smaller X.
This architecture was selected by performing an optimization over the hyperparameters. The following parameters were included in the search:
Batch size: 4096 and 512
A E {le - 4, le 3, le - 2}
Cell type: LSTM or GRU
Number of cells E {30, 40, 50, 60) per layer (identical number of cells in each layer)
Window size L E {4, 8, 16) (SkipW only)
The search was performed both for ThrRNN (baseline) and SkipW (our approach). Several combinations of parameters resulted in models that are Pareto optimal with respect to ac- curacy and computational cost. To evaluate SkipW and compare it to ThrRNN, we selected parameter configuration that led to models that were Pareto optimal (or close to Pareto optimal) for ThRNN and for several values of L for SkipW.
This is synthetic dataset consisting of sequences of (value, marker) tuples, where the expected output is Ex marker x value. This dataset is commonly used to evaluate the performance of RNN models [(Hochreiter & Schmidhuber 1997), (Neil et al.) 2016). Camppss et al. 2018)] The value elements are uniformly sampled in the range (-0.5, 0.5) and the marker elements are equal to or O. We reproduced the experimental setup defined in (Neil al. 2016) with sequence of length 50. Two values are marked for addition with the first marker randomly placed in the first 10% of the sequence and the second one in the last half of the sequence. The variance of the task is equal to 1/6: the number of markers times the variance of the value (1/12). The task is considered solved when the average mean square error is lower than 1/100 the variance of the task.
Adding Task:
The model architecture consists of a single layer of 110 LSTM cells and a fully connected layer regressing the scalar output. We train the model with a batch size of 256 and learning rate of 1e - 4. As with HAR dataset, the best performance was obtained when the model was initialized with model trained with a smaller X.
Sequential MNIST: For this task the MNIST handwritten digits (Lecun et al. 1998) are flattened to vectors of length 784 and each pixel is presented sequentially to the RNN network. This becomes challenging task for RNNs and is useful to test long range de- pendencies (Le et al. 2015). We follow the standard data split and set aside 5,000 training samples for validation purposes. The model architecture consists of single layer of 128 GRÚ cells followed by a fully connected layer using the last hidden state to predict the digit. The model is trained for 600 epochs and report results for the models achieving the best performance on the validation images.
IMDB: This is a sentiment analysis task (Maas et al. 2011) using movie reviews extracted from the IMDB website. It consists in 25000 training and 25000 test reviews annotated as positive or negative. We set aside about 15% of training data for validation purposes. For this experiment we use the first 20000 most common words and a review length of
13

---

Published as a conference paper at ICLR 2021
10
SkipW, L-16
Validation loss
SkipRNN
0
1000000
2000000
3000000
4000000
5000000
Training step
Figure 11: Validation loss during training for SkipW and SkipRNN on HAR. These two models use approximately the same number of inputs, respectively 11% and 13%.
200 by cropping or padding sequence accordingly. The model architecture consists in an embedding layer of size 300 initialized with GloVe embeddings (Pennington et al.) (014)) or uniformly random vectors unavailable. The embedded sequence are then passed to 128 cell single layer GRU followed with dropout (rate 0.2) before using fully connected layer for the classification.
B TRAINING SPEED
There does not seem to be major difference between the training speed of SkipW and SkipRNN. illustrated in Figure [ for models using approximately the same number of updates. Convergence speed is however affected by the choice of X. Higher À constrain the models more and therefore lead slower training.
During training, to process inputs in batch, the model uses the implementation described in Section based the multiplication by u, and (1 ux) rather than actually skipping inputs. This allows the use of matrix operations on mini-batches of inputs, which makes training faster than processing sequences one by one and skipping inputs.
C MODIFYING THR
Modifying thr impacts the accuracy processing tradeoff as well. However, changing thr does not affect the upper bound computational cost. Increasing thr gradually reduces both accuracy and average computational cost. This is similar to ThrRNN. Figure [2] illustrates the impact of changing thr for various L on HAR. While this is less interesting in the context of strict limit computation, it increases the variety of the possible tradeoff points. That being said, the thresholding mechanism allows the model to skip uninteresting inputs and is therefore necessary. For example, if this mechanism removed on adding task, SkipW processes inputs in parts of the sequence where there is marker. On the other tasks, removing it similarly increases computational cost without improving accuracy. This is better highlighted in Appendices a.4
D DETAILED RESULTS FOR ADDING TASK
The Adding task dataset penalizes the model when skipping markers. Therefore, a successful model will learn to process as many inputs as possible where the makers can placed and to ignore the parts of the sequence where the markers are never found.
D. ACCURACY AND COMPUTATIONAL TRADEOFFS
As we see in Figure 4 both SkipW and ThrRNN offer operating points that are better than the ones obtained with individual SkipRNN models (dotted line in the figure). SkipW offers results with
14

---

Published as a conference paper at ICLR 2021
1.0
0.9
Accuracy
trade-off SkipRNN
SkipW A=1e-2, L=4
0.7
SkipW ^=1e-2, L=8
0.6
SkipW 2=2e-2, L=16
ThrRNN A=1e-1
0.5
10
20
Inputs processed (%)
Figure 12: Impact of the thr parameter on accuracy/updates tradeoff for HAR. Comparison between ThrRNN (thr=0.5 to 1.0), SkipW (thr=0.5 to 1.0, K L) and SkipRNN (A=le-3 to 3e-1).
0.03
45.0
Mean square error
Mean square error
(%)
0.02
Inputs processed (%)
42.5
passoport sqpuus
thrw0.5
40.0
0.01
37.5
thr 0 k=10
35.0
0.00
32.5
00.01
30.0
0
20
40
60
80
100
Position of change (% of the sequence)
Figure 13: Modifying K during the analysis of sequence on Adding Task for SkipW (A=2e-4, L=10): from tradeoff, (thr=0.5, K=10, MSE/updates = = 3.56c-5/44.4%) to (radeoff K=5, 1SE//paaates11.6662222.22)
lower number of updates and lower error than ThrRNN while adapting thr especially for between 5 and 10. Both models also achieve lower error than model randomly sampling inputs.
D.2 MODIFYING TRADEOFF DURING INFERENCE
We test SkipW adaptability during the analysis of a sequence; switching between a model with a low MSE, high update rate and another model with higher MSE and lower update rate.
As illustrated by Figure I3 the evolution the MSE is not as smooth as the HAR experimentation due to the nature of the task skipping marker greatly penalizes the MSE. We note that changes in MSE and number inputs processed happen when the switch is performed the last 40% the sequence. This is explained by the fact that the distribution of the inputs processed identical for K = 5 and K = 10 at the beginning of the sequence. Both models a) process the first inputs, to find the first marker, b) skip other inputs up 50% of the sequence, as they never contain marker and c) process the last 5 imputs of the window containing the middle of the sequence, as the second marker may be there. This is illustrated in Figure T6 for
10 and Figure 18 for K 5.
As the loss in MSE stays reasonable proportionally to the number of updates skipped, SkipW can be used to reduce the number updates during a sequence fulfill computational restrictions.
D.3 SKIP PATTERNS AND COMPARISON SKIPRNN AND THRRNN
Figure 14 Aillustrates the ability of SkipW to strictly limit the number of inputs processed. The dotted lines corresponds to the K/ theoretical limit imposed. It is worth noting that the model uses a maximum of 60% of inputs for K L. This be explained by the nature of the task where 40% of the sequence does not contain information (no marker) and is also illustrated by the distribution of inputs processed in Figure T6 (SkipW, top row).
15

---

Published as a conference paper at ICLR 2021
Inputs processed (%)
50
40
30
10
0
1
2
3
4
5
6
8
9 10
Figure 14: Impact of the K parameter on the computational cost upper limit (SkipW: A=2e-4, L=10, thr=0.5).
During training, there is no restriction on the value of K and no restriction on patterns SkipW can explore and therefore it can discover any skipping scheme. Figure 16 illustrates that an uncon- strained (K L) SkipW has correctly learned that must sample the first 10% of the sequence and then stop (until the second marker appear). It has also learned that it must resume sampling when the second marker can appear. SkipW has also learned that can stop sampling the end of the sequence when the second marker is detected: the proportion of skips increases in each window after the third one.
When computational constraint is enforced and K is set to lower value, some skip patterns forbidden and skipW falls back to other patterns. These restrictions inevitably cause SkipW to miss some markers and therefore fail the task. This is illustrated in Figure [5] If failing the task is not an option, one should not use K < L. Note that SkipW has learned to fall back to interesting sampling patterns: the first marker starts be skipped only when K 5.
This figure highlights the re- spective advantages of each method when flexibility is put aside (K and thr=0.5). Because the skip mechanisms are different for SkipW and SkipRNN, these methods produce different sampling patterns. SkipW determines the inputs to process at the beginning of each window whereas ThrRNN performs decision whenever input is processed. ThrRNN is therefore able to stop sampling in- puts when has detected a marker. For example, the prohability of processing an input gradually decreases after position 25 for ThrRNN making more efficient for the second part of the sequence as shown in Table T The same behavior can be observed for SkipW, but only from one window to another. It is also worth noting that the probability that SkipW processes inputs in window is very close to the probability that ThrRNN processes the first input in the window. On the positive side for SkipW, notice that ThrRNN is unable stop processing inputs for long period, shown by non-zero probability of using inputs between position 5 and 25. In addition, ThrRNN some- times skips the first potential location of the second marker. We believe this explains why SkipW can achieve both a higher accuracy and a lower computational cost than SkipRNN and ThrRNN. Because ThrRNN is dragged down by its inability completely stop sampling where there is formation, when trying to further reduce the number of inputs processed by increasing X, skipRNN stops analyzing interesting inputs.
Figure [6] also compares the SkipW models with ThrRNN/SKipRNN.
This can also been seen by looking at sampling patterns, summarized in Figure 18 for some values of K, or on MNIST in Appendix
D.4 IMPACT OF ARCUITECTURE ELEMENTS ON THE DISTRIBUTION OF INPUTS PROCESSED SEQUENCE
D.4.1 ABLATION OF INDEX IN SEQUENCE (T)
As discussed in Section including the index (t) in the input of the update gate (Equation 6) is necessary to allow the model to skip all inputs a window. We show here the impact of removing by modifying equation 6 üw 7 a (W (8t-1) + bw)) + (1 -7) uw.t-
16

---

Published as a conference paper at ICLR 2021
Proportion of skips
Marker 1
0.8
Marker 2
0.4
0.2
0.0
8
K
Figure 15: Impact of the K parameter the proportion of markers skipped. (SkipW: X=2e-4, I=10, thr=0.5).
1.0
Prob. to procees imput
SkipW
0.8
0.6
SkipW no t
0.4
ThrRNN SkipRNN
0.2
0.0
40
Position in the sequence
Figure 16: Distribution of the inputs processed for Adding Task using different models with thr
0.5. From top to bottom: SkipW К L 10 and X=2e-4, SkipW with no index in sequence K 10 and A=3e-4, ThrRNN A=3e-4.
Figure 16 shows that, without I, the model forced to process an additional input in the second window even though this part of the sequence contains no marker. Processing this input enables the model to change its hidden state and therefore to obtain a different activation vector uw,411 in the third window and to continue processing the second part of the sequence where the second marker found. Without this update, the model would stop processing the inputs at the end of the first window since the state and therefore the activation vector would not change. Including t in the input of the activation gate ensures that different activation vector may be computed even without processing input in window.
D.4.2 ABLATION OF THRESHOLD (THR 0)
A second experiment threshold is set to the inputs are selected sorely on the basis the parameter K. There- fore exactly K inputs selected in each window using equation g and equation TO becomes u4 = ( (.. = a w. [+] > O, otherwise.
done to show the importance of the threshold parameter. When the
Figure shows the distribution of the inputs each window for different values of K when thr and Figure 18 when thr 0.5. The importance of thr is clearly highlighted when comparing the two figures. For example, for K = and thr = (Figure 17). there no difference in the first window and the model finds the first marker. However, the model is forced use inputs per window, processes inputs in the second window and this impacts the choice made in the third
Table 1: Inputs processed in different part of sequence for Adding Task Architecture
first half second half
SkipW (T. 10, À
20%
69%
ThrRNN (A = 3e 1--0 4))
31%
54%
17

---

Published as a conference paper at ICLR 2021
1.0
Prob. to procees input
K 9 thr 0
0.8
0.6
K 5 thr 0
0.4
0.2
thr
0.0
10
20
30
40
50
Position in the sequence
Figure 17: Distribution of the inputs processed for Adding Task using SkipW model trained with thr=0.5, L=10 and A=2e-4; inference performed with thr=0 and different values of K.
1.0
Prob. to process imput
K thr=0.5 0.5
0.8
0.6
K thr 0.5
0.4
K=1 1
0.2
0.5
0.0
10
20
30
40
50
Position in the sequence
Figure 18: Distribution of the inputs processed for Adding Task using SkipW model trained with L=10 and X=2e-4 with t/r=0.5 and different values K.
window as the model processes inputs the beginning of this window instead of the last which could contain the second marker. This behavior is to be compared with Figure 18 (thr 0.5) where the inputs processed are effectively located in the second half of the third window. noted that for K 1, thr has discernible effect. The model selects only one input in the first window and this affects the performance (the model will miss the first marker 80% of the time) but also which inputs are selected for processing in subsequent windows.
should be
E DETAILED RESULTS FOR SEQUENTIAL MNIST
To better assess the performance of Skip W on long sequences, we apply it to sequential MNIST. In this data set, pixels of 28 28 images processed sequentially. We selected 28, which means each window corresponds to a line the image. Some results are available in Table Figure [9] The first part of the table contains methods processing pixels sequentially. The second part reports recent results from feature selection methods. SkipRNN by Campos et al. (2018) was reported with an accuracy of 97.6% when processing half the pixels in the original paper. We generated additional tradeoff results with SkipRNN by gradually increasing X.
We report results for skipW models using different from lc-4 to le-1. For K L, skipW achieves similar tradeoff's to skipRNN models. The number of inputs and accuracy can be modified with However, on this dataset, SkipW accuracy decreases faster with K and the resulting tradeoffs do not stay above the ones achieved by other SkipRNN models. For example, SkipRNN (A=le- 3) achieves both a better accuracy and computational cost than SkipW (L=28, K=9, x=le-4). reloading the model is option, selecting another model may be better than modifying K. However, doing so with SkipRNN would not enforce any computational constraint while SkipW can enforce rather tight constraints. For example, using SkipW (L=28, >=le-4) K can be decreased to 11 before significantly affecting accuracy. Similarly, SkipW (L=28, >=le-2) processes on average only 4.5% inputs achieve 86.7% accuracy and can be limited to 3 pixels per line without impacting
18

---

Published as a conference paper at ICLR 2021
Table 2: Comparison of various subsampling methods MNIST. The first part of the table contains
methods processing pixels sequentially. The second part contains some results from recent feature
selection methods. These are not sequential.
Model
Source
Accuracy (%)
Inputs processed (%)
RNN (pskip = 0.5)
Campos et al.
2018
91.2
50
SkipRNN () =le-4)
Campos et
2018
97.6
50
SkipRNN (A =le-4)
97.8
32.5
SkipRNN () =le-3)
96.1
15.6
SkipRNN (A =le-2)
89.7
9.5
SkipRNN =le-])
10.0
0.7
SkipW (I.=28, K=28, 11e44
96.9
26.9
SkipW (I=28, K=11, le-4)
96.4
26.8
SkipW (L=28, K=10, À le-4)
95.8
26.4
SkipW (L=28, K=9, À le-4)
92.2
25.4
SkipW (I=28, K=8, À le-4)
76.7
23.7
SkipW (L=28, K=7, le-4)
57.5
21.3
SkipW (L=28, K=28, le-3)
96.0
15,1
SkipW (I.=28, K=28, =1=-]]
86.7
4.5
SkipW (I=28, K=3, =
86.7
4.5
SkipW (L=28, K=2, == le-2)
83.0
4.3
SkipW (L=28, K=28. le-l)
10.0
0.1
Uniform sampling
Huijben et al. (0019)
71.4
3.2
DPS-topK
Hurjben et al. 2019
93.4
3.2
LOUPE (Bahadir et al. 2019
Hujben et al. 2019
80.1
3.2
Concrete Autoencoders
Balm et al. 2019
90.6
6,4
accuracy much. That being said, its operating range is bit smaller than the first model. To put the performance of this model in perspective, the second part of Table contains results achieved by recently published feature selection methods on the MNIST data set. These methods consider all pixels at the same time for both feature selection and classification. They are therefore not directly comparable but they offer an interesting point of comparison. The accuracy (86.7%) and inputs processed (4.5% achieved by the SkipW model (7.=28, X=le-2) are not as good as the best of these methods (DPS-TOPK). They are however much closer to these results than to these based on uniformly sampled pixels and arguably better or similar to the 80. 1% accuracy for 3.2% inputs processed of LOUPE.
This dataset also further shows that the skip patterns learned by SkipW and SkipRNN can be biased. Figures 23 26 illustrate skip patterns realized by SkipW some digits. They be compared to the results achieved with SkipRNN, displayed Figures 20 22 few interesting observations can be made about SkipW. First, are located. No pixels are looked at in the top, left or right of the pictures but several are considered the bottom. SkipRNN on the other hand samples few pixels in the top and bottom of the figures and lot on the sides.
pixels sampled in the middle of the image, where the digits
Then, SkipW patterns characterized by vertical lines: the same positions tend be sampled in each window. These positions are not all static and vary depending on the particular sequence. Furthermore, when K is small, the pixels sampled tend be spread out in the image. Finally, Figures 23 and 26 further support that SkipW has learned interesting patterns in the data. For example, for digits and sampling almost exclusively takes place one column, with some additional pixels next to the top of that line. We presume these are useful to check for vertical or horizontal line there. This would indicate the digit is not I or 0. For other digits, more pixels are sampled at the left of the main line. This can be compared with the SkipRNN sampling patterns. They also display a periodic behavior, but that periodicity at the pixel rather than at the window level. While this bias seem shared by both methods, conjecture that SkipW suffers less because takes place at a larger scale. This may also explain why this behavior was not present for SkipW in Adding Task.
19

---

Published as a conference paper at ICLR 2021
1.0
..... trade-off SkipRNN
SkipW L=28
Accuracy
0.9
ThrRNN A=1e-1
SkipW L= 1-11
SkipW L=28 1=1e-2
0.8
0.7
0
10
20
30
40
50
Inputs processed (%)
Figure 19: Comparison of SkipRNN and SkipW and impact the
the K parameter on accuracy/updates tradcoff for MNIST. For both SkipW (L=28) and SkipRNN several values of À were tested: from X=le-4 to x=le-2. This figure is the same as Figure illustrate some results listed in Table 2
2
Figure 20: Examples of skip patterns by SkipRNN on MNIST with X=le-4. Blue pixels are skipped. This figure is from (Campos et al. 2018).
6
6
3
8
2
7
Figure 21: Examples of skip patterns by SkipRNN on MNIST with A=le-4. Blue pixels are skipped.
20

---

Published as a conference paper at ICLR 2021
Figure 22: Examples of skip patterns by SkipRNN on MNIST with X=le-3. Blue pixels are skipped.
Figure 23: Examples of skip patterns by SkipW (A=le-4) on MNIST with L-28 and K=28. This particular model achieves an accuracy of 96.9% and uses on average 26.9% inputs. Blue pixels are skipped. All images are correctly classified.
21

---

Published as a conference paper at ICLR 2021
Figure 24: Examples of skip patterns by SkipW (A=le-4) on MNIST with L=28 and K=7. This particular model achieves an accuracy of 57.4% and uses on average 21 of inputs. Blue pixels skipped. The predicted label is top of each image.
4
2
4
8
9
6
7
9
Figure 25: Examples of skip patterns by SkipW (A=le-2) on MNIST with L=28 and K=28, This particular model achieves accuracy of 86.7% and average 4.5% of inputs. Blue pixels skipped. The predicted label is on top of each image.
22

---

Published as a conference paper at ICLR 2021
6
4
7
8
9
1
7
Figure 26: Examples of skip patterns by SkipW (A=le-2) MNIST with L=28 and K=2. This particular model achieves an accuracy of 83% and uses on average 4.3% of inputs. Blue pixels are skipped. The predicted label is top of each image.
1.000
thr-0.5, k-16
Accuracy
0.975
10
thr=0.5,
0.950
0.925
ippuis
Accuracy Inputs (%)
0.900
40
80
100
Position of change (% of the sequence)
Figure 27: Modifying (thr, K) during the sequence on HAR for SkipW (A=2e-2, L=16); from tradeoffi: (thr=0.5, K=16, acclupdates 98.5%/9.5%) to tradeoffz: (thr=0.5, K=1, acc/updates 94.4%/5.1%)
ADDITIONAL RESULTS FOR HAR
F.1 MODIFYING TRADEOFF DURING INFERENCE
Figure 27 and 28 show the adaptability of SkipW during the analysis of a sequence when switching
between different tradeoffs. We present here results for SkipW wih 16 and X=2e-2 with different tradeoffs. As with previous experiments (Figure 9 and Figure 13). the performance is bounded by the individual performance of the two configurations evaluated.
G REAL TIME EXPERIMENTS
G.1 LATENCY EXPERIMENTS
In order to explore the impact of the HW platform on the latency of HAR Services based on SkipW/PoseNet,, we measure the latency of the HAR Service on 2 other small platforms: a Jet- TX2 (similar the Jetson Nano platform (Figure I0), but more powerful) and Raspberry Pi (better CPU, but lacking compatible GPU for model acceleration). The hardware specification of these different devices is provided in Table Figure 29 compares the performances of the HAR
23

---

Published as a conference paper at ICLR 2021
15.0
1.00
thr-0.4 k=3
(% pessaooad supuis
12.5
Accuracy
0.95
10.0
Accuracy
Inputs (%)
0.85
5.0
1hr-0.504 k=]
0.80
0.0
20
40
60
80
100
Position of change of the sequence)
Figure 28: Modifying (thr, K) during the sequence on HAR for SkipW (A=2e-2, L=16); from tradeoff;; (thr=0.4, K=3, acc/updates 99. (9.1%%/33)%% to tradeoffy; (thr=0.504, K'=,, acc/updates 80.8%/3.1%)..
Table 3: Specifications of hardware devices
Jetson TX2
Nano TFLOSS
Raspberry 0.0135 TFLOPs
Al performance
1,33 TFLOPs
GPU
256-core NVIDIA Pascal
128-core NVIDIA Maxwell 4-core ARM A57 (@) 1.2GHZ)
4-core ARM A57 (#12))H
4-core ARM A72 (Ø 1.5GHz)
CPU
2-core NVIDIA Denver (#854MHz)
4 GB 128-bit LPDDR4
4 GB 64-bit LPDDR4 25.6 GiB/s
4 GB LPDDR4-3200
Memory
51.2 GB/Ss
Only AI cupuble GPUs reported
Services on the selected platforms. It is worth noting that the impact of the different tradcoff's thrl) the latency are very similar.
G.2 ENERGY CONSUMPTION
When SkipW coupled with a CNN model set appropriately, can enable huge reduction in amount of computation. This can have an immediate impact on the energy consumed to deliver a Service, an important feature for battery powered systems. As an illustration, we measure the power consumed the HAR analysis when rumning the Jetson boards. This analysis is designed to run at 22Hz. The energy consumption is measured by pulling periodically (every 100 ms) the instantaneous power consumption indicator available at the board level. We report here average of these instantaneous values over a minutes period. [igure[30proviiii for the Jetson Nano and the Jetson TX2. Those two platforms display the same behavior: when K decreases, the consumption decreases significantly. The gain is especially noticeable for the Jetson Nano platform, where can reach up 50% of energy gain.
those energy consumption
Platform Jetson TX2
Platform Jetson Nano
Platform
Raspberry P14
600
1250
6000
latency (in ms)
1000
RNN
400
750
4000
250
2, 1, 0.5 thr
0.6
2, 0.1 K,
1,
0.5
1, 0.6
3. 0.1
2,
0.1
1,
0.5 1, 0.6
Figure 29: Sequence latency for different devices when processing HAR Service using SkipW (A=le-2, L= coupled with PoseNet (MobileNerVI 0.75). Individual contribution of models (CNN: PoseNet, RNN: SkipW) are also reported.
24

---

Published as a conference paper at ICLR 2021
Platform Jetson Nano
Platform Jetson TX2
Power consumption (mW)
1000
3, 0.1
2,0.1 1, 0.5 1, 0,6.
0.1
2, 0.1
0,0.5
0,6
K, thr
K. thr
Figure 30: Average energy consumption for the analysis of a HAR sequence using SkipW (A=le-2, I==) and PoseNet (MobileNet 0.75) on a Jetson Nano and Jetson TX2. The dotted line corresponds to the energy level for no activity and the dashed one to the maximum instantancous level measured when models are running.
(=13-16)
K=(3-
thr=0 0.5
trade-off SkIpRNN
random subsamp.
Accuracy
K-1
periodic subsamp.
K,
SkipW A=1e-2, L=4
SkipW A=1e-2, L-8
SkipW A=2e-2, L=16
0.0
2.5
5.0
10.0
12.5
15.0
17.5
20.0
Inputs processed (%)
Figure 31: Impact of the К parameter on accuracy/updates tradeoff for HAR. Comparison between ThrRNN 0.5 to 1.0), SkipW(I==4,8, 16; thr=0.5, K=1 to L.) and SkipRNN (A=le-3 to 3e-1 1). For random subsampling. the shaded area corresponds to times the standard deviation on each side of the mean value (50 evaluations).
H WOULD OTHER SAMPLING MECHANISMS WORK JUST AS WELL?
The main purpose of SkipW is to upper bound the computational complexity of the model dynami- cally during inference. This has been illustrated in the experiments. Here, we study whether naive approaches would work just as well or whether some parts of the model can be modified. We con- ducted three sets of experiments on HAR. In the first one, SkipW is compared to naive models with complexity, such random subsampling. In the second and third ones, modify the skip mechanism of SkipW to generate other flexible models. To do so, we replace the sampling mechanism by random sampling variants and respectively keep discard the selection by the binarization function.
We selected HAR because SkipW works best on this data set. Furthermore, as information lo- cated in only some parts of the sequence for Adding Task and MNIST, it seems obvious that naive sampling strategies would not work well on these data sets.
H.1 NAIVE RANDOM SAMPLING
Figure 31 compares the models presented in the main experimental section to additional baselines.
In addition to ramdomly sampling inputs, we also consider sampling inputs at set locations, such as the K first inputs of each window periodic sampling. When the number of inputs subsampled is small, no variant considered in this section achieves an accuracy similar to SkipW for set number of inputs processed. However, they
accurate than SkipRNN.
25

---

Published as a conference paper at ICLR 2021
1.00
0.95
Accuracy
0.90
SkipW, L=8
random subsamplig
0.85
first inputs
last K inputs
0.80
25
35
K/L
Figure 32: Replacing the sample mechanisms by other variants (without the binarization function) decreases accuracy on HAR with K=8.
1.00
0.95
Accuracy
0.90
ShipW, L-8
random subsampiig
first K inputs inputs
10
15
20
25
30
35
40
Inputs processed (%)
Figure 33: Replacing the sample mechanisms by other variants (without the binarization function) negatively impact the number of inputs processed on HAR with K=8.
H.2 OTHER SAMPLING MECHANISMS. WITHOUT THE BINARIZATION FUNCTION
In this section we compare the SkipW architecture described in Section to variants where the sampling mechanisms modified to sample K inputs within each window random or by selecting the first or the last elements of the window. The results are displayed in Figures 32 and 33 for two different SkipW models (L=16 and 2=2e-2; L=8 and >=le-2). No variant matches the accuracy of the original SkipW over the whole range of K, although taking the first or last element achieves a similar performance for K=1 and so does random sampling for K between and when 1=16. That being said, SkipW can process fewer than K inputs in every window thanks to the importance vector and the binarization function. Not using these negatively impacts the number of imputs processed, as shown in Figures 33 and 35| This leads to a big difference between the original SkipW architecture and the other variants studied here. Even in the most favorable case where L 16 and К 1, skipW processes 5.06% of inputs whereas the other variants process 6.25%. We expect this computational advantage to be even larger on tasks such as Adding Task and sequential MNIST, where lot of windows contain useful information.
The fact that no method matches accuracy SkipW for K, that for some no method matches the accuracy of SkipW and that SkipW also process fewer samples than these variants show the interest of using the weight vector to select future inputs.
H.3 OTHER SAMPLING MECHANISMS, WITH THE BINARIZATION FUNCTION
Finally, in this section we compare the SkipW architecture additional variant where the selecl mechanism is modified to select the first K inputs of the window whose associated value is > thr. In other words, the main difference with the previous section is that only TopK replaced but the binarization function is kept. Figures 36 and 37 illustrate the results for L = 8 and 16 respectively. The previous section has shown that using the importance vector is necessary. This section suggests that the method used to select inputs from these that beat the threshold can change without impacting the accuracy when thr = 0.5. However, one should note that selecting inputs within each window without using the binarization function (previous section) is equivalent to using thr = 0. As the alternative selectx variants were less effective than TopK for this configuration, we advice against not using TopK when modifying thr.
26

---

Published as a conference paper at ICLR 2021
1,00
0.95
Accuracy
SlipW, L-16
random subsampling
lirst K inpuls
inputs
10
15
20
25
35
40
K/L (%)
Figure 34: Replacing the sample mechanisms by other variants (without the binarization function) decreases accuracy on HAR with ==16.
1.00
0.95
Accuracy
0.90
SlipW, L-16
subsamphing
0.85
first K inputs imputs
0.80
0
10
15
20
25
30
35
40
Inputs processed (%)
Figure 35: Replacing the sample mechanisms by other variants (without the binarization functiion negatively impact the number of inputs processed on HAR with K=16.
1.00
0.95
Accuracy
0.90
0.85
SkipW. L==8
first K inputs with value thr
0.80
10
15
25
30
35
40
K/L (%)
Figure 36: Other variants of selectK do not affect accuracy on HAR with L=8.
1.00
0.95
Accuracy
0.90
0.85
SkipW, L=16
first inputs value
0.80
0
10
15
20
25
30
35
40
K/L (%)
Figure 37: Other variants of KelecIK do not affect accuracy on HAR with L=16.
27


Reviews:
[{"review_id": "uYj3g5Bw5gW", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This submission presents an extension of SkipRNN, Skip-Window, that splits input sequences into windows of length L from which only K samples can be used. This guarantees that the computational budget is never exceeded. Skip-Window implemented this inductive bias by predicting L updating probabilities in parallel at the beginning of each window. L needs to be set prior to training, whereas K can be modified at test time. The model is evaluated in two tasks, namely a synthetic adding task and human activity recognition. Authors report latency and energy consumption in small platforms, showing the impact of this research direction in real applications.\n\nMy main concern regarding the proposed architecture is that it limits the types of skipping patterns that can be discovered -- whereas the original SkipRNN can in principle learn any such pattern. For instance, Skip-Window cannot produce the skipping patterns shown in Figure 6 in Campos et al. (2018) unless K=L or L=1 (in both cases, Skip-Window reduces to SkipRNN). This can even be seen in the results for the adding task, where Skip-Window is actually *not* solving the task for most values of K (c.f. Figure 4). Recall that the output distribution has a variance of 0.166, and Campos et al. define solving the task as achieving an MSE two orders of magnitude below such variance. The reason for this is that Skip-Window with 5<K<L will miss the second marker in some sequences, as it needs to guess its position -- which is random within the second half of the sequence. For K<5, there’s a chance that Skip-Window will miss the first marker as well. As a sanity check, I suggest that authors report the percentage of first and second markers that are missed in the adding task as a function of K. Plotting the MSE of an LSTM or GRU that skips inputs randomly, and varying the fraction of skipped inputs as in Campos et al., would also provide context for the presented error rates.\n\nDespite the imposed constraints in terms of skipping patterns, Skip-Window can be useful in tasks where the input signal can be downsampled more uniformly. After all, the adding task is a challenging problem for RNNs that skip input samples as missing one of the markers will massively increase the error rate. This potential is shown in the human activity recognition (HAR) results. However, I believe that more experimental evaluation is needed before this paper can be published at ICLR. First, the input sequences for HAR are extremely short (32 timesteps), which makes it difficult to draw strong conclusions. Second, since the Skip-Window architecture limits the types of skipping patterns that the model can discover, it is difficult to claim that Skip-Window is a generic RNN architecture unless experiments on more domains are reported (e.g. sequential MNIST, NLP).\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "lr5ezuCEch4", "reviewer": "AnonReviewer3", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors proposes a new framework skipW to strictly limit the computation in RNN. \n\nPros: \n1. The idea of strictly limiting the computation in RNN is new.\n2. The summary of related works is clear.\n\nCons:\n1. The motivation why the authors wants to enforces the strict constraint on the number of updates is unclear:\na. What if a consequent subsequence in a sequence is important? Then limiting processing only the K of L elements will omit this subsequence.\nb. Playing with lambda in equation (11) may also give you a tradeoff in computation and model performance and it will not omit the consequent subsequence example I give in (a).\n2. Is the training harder if we use less inputs and use error gradients than the training with the whole sequence? Although the computation time is less for a forward process, the training may be harder and take more time. This detail needs to be included.\n3. ThrRNN did one experiment in MNIST. I would like to see the comparison on the MNIST dataset.\n\nClarity:\n1. The paper is clearly written in general.\n\nOriginality:\n1. As far as I know, the paper is novel.\n\nMinor:\n1. It somehow sounds mysterious to me that the SKipW model can learn the adding task. The $\\tilde{u}_{W,t+1}$ only takes inputs at the beginning of the length L subsequence. It may not see the inputs where the marker is. Then how can the model learn to not to skip the inputs where the marker is?\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "LK601scLtSB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThe paper proposes Skip-Window or SkipW an abstraction encapsulating RNN cells to actively skip updates similar to some earlier works like Skip-RNN, Skim-RNN, and ThrRNN. The novelty of the method comes is in having control over the total updates to control the overall computational budget compared to previous methods which didn't provide deterministic upper bounds and varied depending on the inputs. The idea is very simple and straightforward and can be looked at as a logical extension to the Skip-RNN line of work combined with a windowed approach on time series as used in ShaRNN (Dennis et al., NeurIPS 2019). The entire time series is divided into Windows of length L (which is a tunable parameter) and each window has a precomputed (from the final hidden state of the previous window) per-time step (update inside the window) importance vector which can be used as an indicator to update or not to update following the binarization as done in previous methods. The strict sparsification of this per-window importance vector to have only K non-zeros per window helps reduce compute to an upper bound ratio of K/L. The method further uses another threshold term over the sparsified importance vector to control finer budget requirements if needed. The experimentation is done on 2 tasks HAR-2D-Pose (with 32 time steps) and Adding task with 50 timesteps. The evaluation shows that Skip-Window shows good performance./accuracy compared to previous flexible RNNs with a reduction in the total number of updates. Finally, the impressive part of the paper is the real-world evaluation on Jetson Nano with a more complex workflow involving pose estimation from images for HAR-2D-Pose. \n\nPros:\n1. Simple and elegant idea. SkipWindow solution is in theory generalizable to multiple RNNs without much hassle. The abstraction could be thought of as an independent outer layer over RNNs similar to most other works in the space. \n2. Related work section is very thorough and the claims are grounded.\n3. The architecture is easy to understand along with the aspects of training\n4. The experimentation on both datasets reveals interesting insights and showcase the advantage of SkipW over other methods in both accuracy and computational budget. \n5. I highly commend the deployment experiments and evaluating it with complex workflow and showing how skipping updates and inputs can help compute latency and resources.\n6. Plots are very clean and appendix and ablation are good. \n\nWeaknesses:\n1. While I feel the idea works well and is elegant. It still is a combination of a couple of known techniques (mentioned in summary) which limits the novelty somewhat. But that doesn't stop the method from being useful.\n2. Figure 2 is not required or needs redesigning as the equations were much clearer than the figure and the gates just made it hard to understand. \n3. I understand while K/L upper bound is guaranteed, the authors want to use thr for finer control, I just feel, it might not be required for super long sequences. - Just a comment.\n4. My major issues are with experiments. While I like the work on HAR-2D-Pose and agree it is a good choice of dataset. I also want to see the success of Skip W on long term dependency tasks. I wouldn't count adding tasks as it can be trivially solved using good initialization (Henaff et al., ICML 2016). While I appreciate the efforts, I would like to see results on at least one or two (at least two preferred but I understand the time limitations, so one good dataset also works for the discussion phase) more real-world datasets to check the generalization. It can be Keyword spotting, phoneme detection, or even noisy-CIFAR. Something around 100 timesteps or more would be great\n\nI am asking the authors to add these things during rebuttal or give reasoning corresponding to it. This is a key question to be addressed during the discussion. Note that I do not need deployment for these datasets but would like to see these numbers in the paper for more datasets to make the paper stronger. The reasoning for the long-range is because the gains would be more profound there than in 32 time steps. \n\n5. While the K/L based on importance makes sense per window. Sometimes, RNNs tend to identify signatures randomly. I suggest the authors add a comparison with random K choice instead of top K choice per window and have multiple variants of it like periodic sampling or all inputs being from start or end (these are deterministic for prediction time). This experiment will help us determine if the importance vector actually contributes to the decision making on skipping updates. The rationale behind this comes from the action recognition literature where people have shown that random sub-sampling works decently well compared to intelligent sub-sampling. Another thing to add here is because the importance vector per window is chosen based on the previous window it might not be optimal and maybe random selection might work fine. If random sampling (even not so random like periodic etc.,) works well, then I am not sure about using importance vectors anymore.\n\nWithout these baselines, it is hard to argue otherwise. I strongly suggest authors pursue this to make the claims more solid. This is another thing that needs to be addressed during the discussion.\n\nDecision:\nEven though the novelty is slightly limited, I like the idea for its ease, decoupled natured and potential generalizability along with the control on computational budgets. I appreciate the authors for ablation and on-device experiments which are very thorough. The only issue I found with the paper is the experimentation and baselines. I want to see at least one long term dependency task (real-world) and baselines that evaluate if the importance vector is even needed with the simple sampling strategies among each window. \n\nI am very much willing to increase the score based on discussion and the improvements on the experimentation front.\n--------------------------------------------------------------------\nEdit after rebuttal and discussion.\n\nI thank the authors for extra experimentation to showcase the effectiveness of SkipW. While most reviewers here agree that the novelty is limited (that doesn't stop it from being useful), I strongly think the impact due to SkipW will be translated to the real-world. There has been some discussion on the datasets, which I agree are not extensive making the initial experimentation weak. However, the new experiments compensate to an extent and I would like to recommend a weak acceptance with a score of 6 (I am still between 6 and 7, waiting for other reviewers to pitch in). ", "extra_scores": {}, "extra_text": {}}, {"review_id": "AvbdZBrqud", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nThis work introduces Skip-Window (SkipW), an approach that allows RNNS to have improved computational efficiency at the cost of accuracy. SkipW adds a procedure to existing RNN cells that allows them to process fewer inputs while remaining in a strict computational budget. This work demonstrates the benefits of SkipW through experiments on multiple data sets.\n\nThis work proposes a structured procedure to process fewer inputs during inference while abiding by a computational budget. Each skip seems to be calculated over a window of inputs in a sequence, thereby minimizing inter and intra sequence variability in computation. This work does seem to have merit in a practical setting where the availability of computational resources can vary. The ability to manage dynamic budget, though not totally novel (ThrRNN also has the thr param), does provide an advantage with SkipW being perhaps more flexible with both K and thr usage.\n\nThis work empirically demonstrates the benefit of SkipW  over several baselines on two data sets. There are, however, some points that need to be addressed.\n\n\n\n\n\nFigure 2 and equations 5-10 seem to be a bit unclear. Figure 1 and the first two paragraphs of section 3 seem to imply that  \\hat{u}_{W} is calculated once as an L length vector at the beginning of an L sized window.   Here \\hat{u}_{W}^{K}  are the selected K entries for the whole L sized window. Therefore what does \\hat{u}_{W,t}^{K}  denote. \n\nIn Figures 3 and 4 what is input processed % ? Is it K/L. For example, in Figure 3 and in the case of L=8, the setup K=1 implies K/L = 0.125 , but the K=1 point for SkipW is at less than 10% mark on the xaxis. Furthermore, how is it that K=[3-8] all have roughly the same input processed % ? Its the same case for K=[1-4] and K=[3-16]  \n\n\nIn Figure 4, the number of points for ThrRNN seem to be much more than SkipW. This seems to imply much more finer control over computational cost for ThrRNN as compared to SkipW (more coarser control). What are the authors' thoughts about this?\n\n\nFigure 6 seems to imply that the inputs in p3 and p4 can be more easily dropped as compared to p1 and p2. What are the  authors' thoughts about the connection of this ease of dropping inputs to the various attention mechanisms that are available in literature. Furthermore, is it the case that later inputs will typically always have more tendency to be dropped in SkipW ?\n \n\nFigure 7 seems to be a bit unclear. Is the accuracy being depicted the relative accuracy as compared to thr=0.4 and K=8? Furthermore, how is the accuracy being calculated as the thr,K are changing on the fly as time/sequences go on? This might imply that different thr,K values see different data? Is the same exact sample being used to calculate the accuracy? \n\n\nIt seems that L-K denotes the minimum number of inputs that will be skipped (as there is a further 'binarize' that runs on the K inputs). Therefore, it seems that the system will under utilize the available computational capacity. This might not be desirable as any loss in accuracy might have been reduced if all available computational capacity was used. What are the authors' thoughts about this?\n\n\nPerhaps a text processing task in NLP would have made the results stronger as in practical scenarios, this is one of the common modalities where RNNs are used.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors did a good job responding to reviewer concerns.   While the reviewers still consider the method described in the paper to not be especially novel, at least one is impressed by the practicality.  imo the authors' attention detailed ablations and analysis post-review makes the paper worth including in the conference.
Decision: Accept (Poster)