A method of generating an output sequence comprising a neural network output at each of a plurality of time steps from an input sequence comprising a respective neural network input at each of the plurality of time steps, the method comprising: processing the input sequence using a recurrent neural network implemented by one or more computers, wherein the recurrent neural network is a speech recognition model configured to receive the respective neural network input at each of the plurality of time steps and to generate a respective neural network output at each of the plurality of time steps, wherein the input to the neural network is features of a spoken utterance and the output generated by the neural network is a score for each of a set of pieces of text, each score representing an estimated likelihood that the piece of text is the correct transcription for the utterance, and wherein the recurrent neural network comprises: a first long short-term memory, LSTM, layer, wherein the first LSTM layer is configured to, for each of the plurality of time steps, generate a new layer state and a new layer output by applying a plurality of gates to a current layer input, a current layer state, and a current layer output, each of the plurality of gates including a recurrent parameter matrix and an inter-layer parameter matrix and being configured to, for each of the plurality of time steps, generate a respective intermediate gate output vector by multiplying a gate input vector and a gate parameter matrix, and wherein the recurrent and inter-layer parameter matrices for at least one of the plurality of gates are each a Toeplitz-like structured matrix that is described by fewer parameters than the product of its dimensions, and the neural network is compressed by at least 75% of an uncompressed version of the neural network and a word error rate of the neural network is within 0.3% of a word error rate of an uncompressed version of the neural network. processing the input sequence using a recurrent neural network implemented by one or more computers, wherein the recurrent neural network is a speech recognition model configured to receive the respective neural network input at each of the plurality of time steps and to generate a respective neural network output at each of the plurality of time steps, wherein the input to the neural network is features of a spoken utterance and the output generated by the neural network is a score for each of a set of pieces of text, each score representing an estimated likelihood that the piece of text is the correct transcription for the utterance, and wherein the recurrent neural network comprises: a first long short-term memory, LSTM, layer, wherein the first LSTM layer is configured to, for each of the plurality of time steps, generate a new layer state and a new layer output by applying a plurality of gates to a current layer input, a current layer state, and a current layer output, each of the plurality of gates including a recurrent parameter matrix and an inter-layer parameter matrix and being configured to, for each of the plurality of time steps, generate a respective intermediate gate output vector by multiplying a gate input vector and a gate parameter matrix, and wherein the recurrent and inter-layer parameter matrices for at least one of the plurality of gates are each a Toeplitz-like structured matrix that is described by fewer parameters than the product of its dimensions, and the neural network is compressed by at least 75% of an uncompressed version of the neural network and a word error rate of the neural network is within 0.3% of a word error rate of an uncompressed version of the neural network.