Neural Shuffle-Exchange Networks -- Sequence Processing in O(n log n)
  Time
  A key requirement in sequence to sequence processing is the modeling of long
range dependencies. To this end, a vast majority of the state-of-the-art models
use attention mechanism which is of O($n^2$) complexity that leads to slow
execution for long sequences. We introduce a new Shuffle-Exchange neural
network model for sequence to sequence tasks which have O(log n) depth and O(n
log n) total complexity. We show that this model is powerful enough to infer
efficient algorithms for common algorithmic benchmarks including sorting,
addition and multiplication. We evaluate our architecture on the challenging
LAMBADA question answering dataset and compare it with the state-of-the-art
models which use attention. Our model achieves competitive accuracy and scales
to sequences with more than a hundred thousand of elements. We are confident
that the proposed model has the potential for building more efficient
architectures for processing large interrelated data in language modeling,
music generation and other application domains.
