Metastable Dynamics of Chain-of-Thought Reasoning: Provable Benefits of Search, RL and Distillation

This research explores Chain-of-Thought (CoT) reasoning in large language models by viewing it as a metastable Markov process. The authors model easy reasoning steps as dense clusters and hard steps as sparse connections, proving that search strategies rewarding these sparse edges improve efficiency by reducing the time to navigate between concept clusters. The study demonstrates that information from search can be used to fine-tune pretrained models through reinforcement learning and distill this reasoning capability into smaller, more efficient models. Crucially, the paper establishes that solving logical reasoning tasks with this framework requires global search and is intractable with only local information access.