The streaming rollout of deep networks -towards fully model-parallel execution
Deep neural networks, and in particular recurrent networks, are promising candidates to control autonomous agents that interact in real-time with the physical world. However, this requires a seamless integration of temporal features into the network's architecture. For the training of and inference with recurrent neural networks, they are usually rolled out over time, and different rollouts exist. Conventionally during inference, the layers of a network are computed in a sequential manner resulting in sparse temporal integration of information and long response times. In this study, we present a theoretical framework to describe rollouts, the level of model-parallelization they induce, and demonstrate differences in solving specific tasks. We prove that certain rollouts, also for networks with only skip and no recurrent connections, enable earlier and more frequent responses, and show empirically that these early responses have better performance. The streaming rollout maximizes these properties and enables a fully parallel execution of the network reducing runtime on massively parallel devices. Finally, we provide an open-source toolbox to design, train, evaluate, and interact with streaming rollouts.
Update after rebuttal:  I appreciate that the authors addressed my concerns in their rebuttal. I hope that the authors can clarify the exposition + add examples as discussed, which would make the paper significantly more accessible.   ---          Summary:           This paper analyzes different ways to unroll recurrent neural networks with skip connections and self-loops. A main motivation is to increase the efficiency (e.g., response time) of the network during training/inference. A rollout is a graph that captures the functional dependency of network nodes over time. The authors argue that there are different possible rollouts that have different quality (e.g., response time), introduce mathematical definitions to describe rollouts (e.g., validity / model-parallelizable) and analyze rollouts theoretically and experimentally.            In my understanding, the actual conclusion of the paper seems to be: the streaming ("R \equiv 1") is the best, e.g., Theorem in L192 states that the streaming rollout achieves the lowest response time over the entire graph. The experiments seem to support that conclusion. Note that how to obtain the streaming rollout is not clearly stated by the authors, although the Thm in L192 seems to suggest a working rule for obtaining it.          Pro:           Originality/Significance:           - I'm not aware of earlier work that analyzes this low-level implementation issue, but it is worthwhile to analyze this for optimization purposes.           - Overall, the paper is grammatically well written.          Con:             Quality:           - The writing is a bit dense in places and the payoff from introducing all the different mathematical definitions seems to be the Thm in L192.             Clarity:           - It's not so clearly explained what the computational overhead is of the streaming rollout R \equiv 1: is there any since we are using more edges from the functional graph?           - The paper lacks some simple examples to motivate / illustrate the introduced mathematical definitions. E.g., what does R \equiv 1 represent / what is the intuition for (1)? A simple example would be useful. The same for "tableau" and "state": a simple example to elucidate the definitions would be helpful.                    - Why is the sequential ("R \equiv 0") rollout as in the top row in Fig 1? Maybe a detailed discussion / description here would be helpful.           L212: "single images are already sufficient for almost perfect classification results" --> I don't know what is meant here.           - Theorems are not numbered.           - Some formulas are not numbered.             Reproducibility:           - How is this implemented in framework XYZ?            - The authors don't seem to discuss how operationally to obtain the streaming rollout automatically from the functional definition of a computation graph. How do you do that?           - It does not seem straightforward to re-implement this without error.           Typos:           - L122: express -> expressed