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

2025/11/22 by Bochen Lyu, Yiyang Jia, Lyu, Bochen +5
Computer Science · Mathematics · #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Quantum Computing Algorithms and Architecture #Reinforcement Learning in Robotics #cs.LG #stat.ML

paper · pdf · doi:10.48550/arxiv.2511.17852

ICML 2026 final version. 50 pages

openalex publication_date 2025/11/22 · openalex created_date 2025/11/27 · openalex updated_date 2026/07/28 · arxiv created 2026/08/06 · arxiv updated 2026/08/07

Abstract

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 the conditions hold for three 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 depending on supervision: RL learns the whole CoT chain simultaneously, whereas SFT without teacher forcing 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 should consider the intermediate supervision.

Citations

• Multi-head Transformers Provably Learn Symbolic Multi-step Reasoning via Gradient Descent
• Learning Compositional Functions with Transformers from Easy-to-Hard Data
• Minimalist Softmax Attention Provably Learns Constrained Boolean Functions
• How Transformers Learn Regular Language Recognition: A Theoretical Study on Training Dynamics and Implicit Bias
• Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers
• SFT Memorizes, RL Generalizes: A Comparative Study of Foundation Model Post-training
• Theoretical limitations of multi-layer Transformer
• Transformers Provably Solve Parity Efficiently with Chain of Thought
• Training Language Models to Self-Correct via Reinforcement Learning
• Unveiling the Statistical Foundations of Chain-of-Thought Prompting Methods
• Transformers Learn Low Sensitivity Functions: Investigations and Implications
• Training Dynamics of Multi-Head Softmax Attention for In-Context Learning: Emergence, Convergence, and Optimality
• Chain of Thought Empowers Transformers to Solve Inherently Serial Problems
• Why are Sensitive Functions Hard for Transformers?
• BioXP-0.5B: Explainable Medical-AI via RL-GRPO
• Trained Transformers Learn Linear Models In-Context
• Let's Verify Step by Step
• Transformers learn in-context by gradient descent
• Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functions
• Training a Helpful and Harmless Assistant with Reinforcement Learning from Human Feedback
• Sub-Task Decomposition Enables Learning in Sequence to Sequence Tasks
• STaR: Bootstrapping Reasoning With Reasoning
• Training language models to follow instructions with human feedback
• BNAI, NO-TOKEN, and MIND-UNITY: Pillars of a Systemic Revolution in Artificial Intelligence
• Proximal Policy Optimization Algorithms
• Deep reinforcement learning from human preferences
• Failures of Gradient-Based Deep Learning
• Distribution-Specific Hardness of Learning Neural Networks
• Asynchronous Methods for Deep Reinforcement Learning
• The Expressive Power of Transformers with Chain of Thought

Related

• Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functions
• Transformers Provably Solve Parity Efficiently with Chain of Thought
• Transformers Provably Learn Chain-of-Thought Reasoning with Length Generalization
• The Kinetics of Reasoning: How Chain-of-Thought Shapes Learning in Transformers?
• Training Nonlinear Transformers for Chain-of-Thought Inference: A Theoretical Generalization Analysis