Modeling Reasoning as Markov Decision Processes: A Theoretical Investigation into NLP Transformer Models
Zhenyu Gao · 2025
Transformer-based models have achieved state-of-the-art performance across a broad spectrum of natural language processing (NLP) tasks, including translation, summarization, and question answering. Despite this success, a theoretical understanding of how these models perform reasoning over multiple steps remains elusive. This paper introduces a novel perspective: reasoning within transformers can be formally framed as a Markov Decision Process (MDP). By treating hidden states as MDP states, token predictions as actions, and attention-guided transitions as state dynamics, we reinterpret the transformer architecture through the lens of sequential decision-making. We develop a theoretical formulation of this mapping, propose multiple task-agnostic reward functions to quantify reasoning quality, and explore the internal attention patterns as a proxy for policy learning. Using synthetic and natural datasets involving multi-step logical inference, we show that certain transformer behaviors align with MDP planning policies. Our framework offers new tools for analyzing, evaluating, and potentially improving transformer reasoning, serving as a bridge between reinforcement learning and deep NLP.