Why were/are LSTMs popular for so long for NLP? Talking with a professor at uni about NLP methods, I asked why LSTMs (and any RNN variant for that matter) were so popular for so long, given the vanishing gradient problem. More specifically, treating each alphanumeric character as a unique token integer {a:1, b:2...} then encoding a text string as such 'cat' -> [3,1,20] in a multilayer perceptron should work well, given that the network is sufficiently deep. He noted that this idea has already been considered using CNNs on such an encoding. I'm curious why RNN/LSTM variants seem to be more popular.
Semi-related transformers seem to address this shortcoming of RNN/LSTM architectures, but this topic creeps the scope of my question.
Anyway, is there a reason that LSTM/RNN architectures were more popular than MLP/CNN approaches to NLP?
 A: There are two parts here: why MLPs are no good and what NLPers like about RNNs.

A multi-layer perceptron can only process fixed-size inputs. In your example up above, you could indeed pass [3, 1, 20] (‘cat’) to an MLP if it has 3 input nodes. But you can’t give the MLP [3, 1, 20, 19] (‘cats’)! You’d need to add another input node (and associated weights), then learn the updated weights. Even if you wanted to do this, the number of parameters you need grows with the length of the sequence. At some point, you have to decide ‘enough is enough’ and put a bound on the length of your sequence.
By contrast, an RNN can handle an input sequence (or, depending on your purpose, output sequence) with unbounded length, reusing only a finite number of weights. You don’t need more weights as the sequence gets longer.


Now that we’ve covered why RNNs are a better fit, I’ll go into some of the aesthetic reasons we like RNNs.
There’s a rich history of models for structured prediction in NLP, like hidden Markov models and finite-state transducers. (Sure, an HMM can be represented by a particular weighted finite-state transducer. Story for another time.)
A major limitation of these is the Markov assumption: these models only let you look back a fixed number of steps. (This is the order of the Markov model.) We accept this Markov assumption because too high-order of a Markov model leads to data sparsity and poor predictions. (After all, how would you train $p(\text{underpants} \mid \text{I}, \text{shot}, \text{an}, \text{elephant}, \text{in}, \text{my})$? The context that you condition on (“I shot an elephant in my”) is so astronomically rare.
RNNs share a lot of similarities with the classical models we’ve used for decades. Just like them, you can perform ancestral sampling to produce a sequence. A fixed number of parameters can handle arbitrarily long sequences. You can compute likelihoods of sequences with the same forward algorithm. The tricks from these classical models lead to natural extensions of RNNs like the sequence-to-sequence model of Sutskever et al.—you can use RNNs for classification, generation of arbitrarily long sequences, or tagging.
An RNN’s state, though, is a digest of the entire sequence observed so far! This breaks the Markov barrier, and the RNN’s continuous state space provides a form of smoothing to get around the sparsity issue.
(A brief note on CNNs. Nothing against them; they’ve got moves. But they can only handle fixed-length contexts, too. You’d have to stack several layers to even be able to learn long-range dependencies, whereas a single-layer RNN can do this.)

Beyond that—and I know this is a silly reason—there’s something that feels natural (to me) about an RNN reading text in the same order that a human would, updating its belief as it sees each next token.
