Transformers with RL or SFT Provably Learn Sparse Boolean Functions, But Differently

Transformers can acquire Chain-of-Thought (CoT) capabilities to solve reasoning tasks via fine-tuning. Reinforcement learning (RL) and supervised fine-tuning (SFT) are two primary approaches to this end. In this work, we examine RL with verifiable process rewards and SFT for learning $k$-sparse Boolean functions with a one-layer transformer through intermediate reasoning steps akin to CoT. In particular, we consider Boolean functions that can be recursively decomposed into fixed 2-sparse Boolean functions. We first analyze the learning dynamics of RL fine-tuning with verifiable process rewards and SFT in a unified way, allowing us to identify sufficient conditions under which the transformer provably learns these functions. We then verify that these conditions hold for three basic examples, including $k$-PARITY, $k$-AND, and $k$-OR, thus demonstrating their learnability via both RL and SFT. Notably, we reveal that RL and SFT exhibit distinct learning behaviors: RL learns the whole CoT chain simultaneously, whereas SFT learns the CoT step-by-step. Overall, our findings provide insights on the mechanisms underlying RL and SFT and how they differ in triggering the CoT capabilities of transformers, and suggest that the comparison between RL and SFT may need to consider the reward design and the use of teacher forcing.

Large language models often solve difficult tasks by generating intermediate reasoning steps before producing a final answer. Two common ways to improve this behavior are supervised fine-tuning (SFT), which trains the model on labeled reasoning sequences, and reinforcement learning (RL), which trains the model using rewards. This paper studies how these two approaches induce Chain-of-Thought (CoT) reasoning in transformers from a theoretical perspective. We analyze a simplified setting where a one-layer transformer learns sparse Boolean functions, such as parity, through intermediate reasoning steps akin to CoT. Our main finding is that RL with verifiable process rewards and SFT without teacher forcing exhibit different learning dynamics. RL with verifiable process rewards can learn all CoT reasoning steps simultaneously, because the reward for each step is computed from the model’s generated history and therefore provides a valid local training signal for every step along the sampled trajectory. In contrast, SFT without teacher forcing learns the CoT chain step by step: later steps become reliably learnable only after the model has learned to generate earlier steps correctly. We also show that RL with only final-answer rewards can be hard, while SFT with teacher forcing can recover simultaneous learning. These results suggest that comparisons between RL and SFT should account not only for the training algorithm, but also for reward design and the use of teacher forcing.