ATTENTION NEURAL NETWORKS WITH LOCALITY-SENSITIVE HASHING

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for performing a machine learning task on a network input to generate a network output. In one aspect, one of the systems includes an attention neural network configured to perform the machine learning task, the attention neural network including one or more LSH attention layers, each LSH attention layer comprising one or more LSH attention sub-layers, each LSH sub-layer configured to: receive a sequence of queries derived from an input sequence to the LSH attention layer, the sequence of queries having a respective query at each of a plurality of input positions; determine one or more respective hash values for each of the respective queries at each of the plurality of input positions; generate a plurality of LSH groupings; and generate an attended input sequence.