arXiv:2604.24737 · v2
Learning to Think from Multiple Thinkers: How Chain-of-Thought Heterogeneity Affects Efficient Learnability
摘要
Chain-of-thought (CoT) supervision makes computationally hard learning problems tractable by exposing intermediate steps that are easy to learn via next-token prediction. However, in practice, CoT datasets draw on heterogeneous sources with different reasoning styles, and substantial effort goes into curating supervision suitable for next-token training. What role does this curation play in enabling the computational advantage of CoT supervision? In this work, we take a first step toward understanding this question from a learning-theoretic perspective. We introduce several models of $heterogeneous$ $CoT$ $supervision$ from multiple sources, each providing correct traces with the same final answer but different intermediate steps. Assuming that fitting a next-token predictor to $homogeneous$ traces from any single source is computationally tractable, we ask when this suffices for efficient learning from heterogeneous supervision. We show $cryptographic$ $hardness$ of learning from $passively$ collected traces from multiple sources, even though learning from homogeneous CoTs is easy. This hardness can stem either from $hard$-$to$-$learn$ $contribution$ $biases$ determining which sources contribute traces on different parts of the domain, or from receiving an $unfiltered$ heterogeneous mixture (though a filtered subset of homogeneous traces is sufficient for efficient learning). On the positive side, inspired by iterative and adaptive fine-tuning of language models, we give a computationally efficient learning algorithm that $actively$ and $adaptively$ collects CoTs from multiple sources with a per-source CoT budget completely independent of the target error $\varepsilon$. We argue that our results illuminate data collection and curation practices central to making CoT supervision effective for learning.
作者备注：Comments are welcome. Revised the presentation to highlight the connections of the main theorems to practice with conceptual messages