Learning Bounded Context-Free-Grammar via LSTM and the Transformer: Difference and the Explanations

Long Short-Term Memory (LSTM) and Transformers are two popular neural architectures used in natural language processing tasks. Theoretical results show that both are Turingcomplete and can represent any context-free languages (CFLs). In practice, it is often observed that the Transformer models have better representation power than the LSTM. But the reason is barely understood. We study such practical differences between LSTM and the Transformer and propose an explanation based on their latent space decomposition patterns. To achieve this goal, we introduce an oracle training paradigm, which forces the decomposition of the latent representation of LSTM and the Transformer, and supervises with the transitions of the corresponding Pushdown Automaton (PDA) of the CFL. With the forced decomposition, we show that the performance upper bounds of LSTM and the Transformer in learning CFL are close: both of them can simulate a stack and perform stack operation along with state transitions. However, the absence of forced decomposition leads to the failure of LSTM models to capture the stack and stack operations, while having a marginal impact on the Transformer model. Lastly, we connect the experiment on the prototypical PDA to a real-world parsing task to re-verify the conclusions. 1