Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: The authors proposes a new framework skipW to strictly limit the computation in RNN. 

Pros: 
1. The idea of strictly limiting the computation in RNN is new.
2. The summary of related works is clear.

Cons:
1. The motivation why the authors wants to enforces the strict constraint on the number of updates is unclear:
a. What if a consequent subsequence in a sequence is important? Then limiting processing only the K of L elements will omit this subsequence.
b. 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).
2. 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.
3. ThrRNN did one experiment in MNIST. I would like to see the comparison on the MNIST dataset.

Clarity:
1. The paper is clearly written in general.

Originality:
1. As far as I know, the paper is novel.

Minor:
1. 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?

review_title: Interesting paper, but lack of motivation

final_score: rating: 5: Marginally below acceptance threshold
review_content: 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.

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

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

review_title: Official Review

final_score: rating: 6: Marginally above acceptance threshold
review_content: 
This 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.

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

This work empirically demonstrates the benefit of SkipW  over several baselines on two data sets. There are, however, some points that need to be addressed.





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

In 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]  


In 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?


Figure 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 ?
 

Figure 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? 


It 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?


Perhaps 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.
review_title: Interesting work

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary:
The 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. 

Pros:
1. 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. 
2. Related work section is very thorough and the claims are grounded.
3. The architecture is easy to understand along with the aspects of training
4. The experimentation on both datasets reveals interesting insights and showcase the advantage of SkipW over other methods in both accuracy and computational budget. 
5. 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.
6. Plots are very clean and appendix and ablation are good. 

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

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

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

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

Decision:
Even 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. 

I am very much willing to increase the score based on discussion and the improvements on the experimentation front.
--------------------------------------------------------------------
Edit after rebuttal and discussion.

I 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). 
review_title: A simple and effective idea which can have real-world impact - can benefit from stronger experimentation

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)