On the Neural Architecture of Language Models

Abstract

Modern large-scale sequence modeling requires architectures that can represent long-range dependencies while remaining computationally efficient. Transformers dominate many sequence modeling tasks because self-attention enables expressive and highly parallel computation, but its quadratic time and memory costs become prohibitive for long sequences. Recurrent models such as Long Short-Term Memory (LSTM) networks provide nonlinear state updates and strong state-tracking capabilities, however, their sequential dependency structure limits parallel execution. Recent works have proposed a variety of efficient sequence models, though many achieve scalability by simplifying nonlinear transition dynamics, imposing structural constraints, or approximating attention. This thesis asks whether recurrent computation can be reorganized for parallel execution while preserving the nonlinear gated dynamics of LSTMs. To address this question, this thesis introduces the Parallel Recursive LSTM (PR-LSTM), a hierarchical recurrent architecture that replaces sequential recurrence with recursive nonlinear state composition over a balanced computation tree. Input tokens are independently mapped to latent states, which are then recursively merged by a learned gated composition block. Rather than requiring an associative operator, as in parallel scan methods, PR-LSTM uses the reduction tree only to define the order of computation. This preserves gated recurrent state representations while reducing recurrent parallel depth from linear to logarithmic. PR-LSTM is evaluated on formal-language benchmarks that isolate core sequence-modeling capabilities, including finite-state tracking, counting, copying, retrieval, and stack-like memory, with emphasis on out-of-distribution length generalization. Empirically, PR-LSTM generalizes to longer sequences on more tasks than standard RNN, LSTM, and Transformer baselines. These results show that recurrent computation can be reorganized hierarchically to improve parallel execution without restricting transition dynamics to linear or associative forms. Overall, this thesis positions hierarchical recurrence as a promising alternative for scalable sequence modeling, combining nonlinear state composition with logarithmic recurrent execution depth.