跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2610.09186 · v3

The Dichotomy Between Pattern Recognition and Step-by-Step Reasoning

首次提交 2026-10-07 06:36
版本更新 2026-11-20 00:59
雷达观测 2026-11-20 12:52
arXiv ↗PDF ↗

摘要

We argue that pattern recognition and step-by-step reasoning are two ends of a spectrum. A large language model (LLM) learns to reason step-by-step when data is structured such that the next token depends on a small amount of preceding context. Inference in LLMs resembles pattern recognition when the next token depends on a large amount of preceding context. If the next token depends on only the cc most recent tokens, reasoning traces are paths on a de Bruijn graph whose nodes are cc-length contexts and edges are next-token transitions between contexts. The set of reasoning traces of a task forms a directed acyclic subgraph of the de Bruijn graph. An LLM that has learned all edges of this subgraph can compose them to solve longer, unseen tasks, i.e., it reasons step-by-step. We prove that the number of edges is vanishingly small compared to the number of reasoning traces. We also prove and show empirically that the number of training samples a transformer needs is a linear in the number of edges, so learning to reason step-by-step is sample efficient. We can induce de Bruijn structure in any task by maintaining a ``state'' that makes future reasoning independent of the past. The frequency of states in the reasoning trace determines cc. We show, by fine-tuning Qwen2.5-1.5B-Instruct to solve equations and answer questions about stories, that frequent states (small cc) result in higher accuracy but greater fragility to perturbations at test time. LLMs trained with a large cc are only as good as models that perform pattern recognition without reasoning. A moderate density of states balances accuracy and robustness. Real-world data has de Bruijn structure: Qwen3-14B and Qwen3-32B retain over 75\% of their accuracy on GSM8K, MATH-500 and GPQA-Diamond when attention is restricted to a sliding window less than 15\% as long as the full reasoning trace.

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

本站首次收录为 v3,暂无更早版本可对照。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v3 · 2026-11-20 00:59 · 最新观测版本

The Dichotomy Between Pattern Recognition and Step-by-Step Reasoning

We argue that pattern recognition and step-by-step reasoning are two ends of a spectrum. A large language model (LLM) learns to reason step-by-step when data is structured such that the next token depends on a small amount of preceding context. Inference in LLMs resembles pattern recognition when the next token depends on a large amount of preceding context. If the next token depends on only the cc most recent tokens, reasoning traces are paths on a de Bruijn graph whose nodes are cc-length contexts and edges are next-token transitions between contexts. The set of reasoning traces of a task forms a directed acyclic subgraph of the de Bruijn graph. An LLM that has learned all edges of this subgraph can compose them to solve longer, unseen tasks, i.e., it reasons step-by-step. We prove that the number of edges is vanishingly small compared to the number of reasoning traces. We also prove and show empirically that the number of training samples a transformer needs is a linear in the number of edges, so learning to reason step-by-step is sample efficient. We can induce de Bruijn structure in any task by maintaining a ``state'' that makes future reasoning independent of the past. The frequency of states in the reasoning trace determines cc. We show, by fine-tuning Qwen2.5-1.5B-Instruct to solve equations and answer questions about stories, that frequent states (small cc) result in higher accuracy but greater fragility to perturbations at test time. LLMs trained with a large cc are only as good as models that perform pattern recognition without reasoning. A moderate density of states balances accuracy and robustness. Real-world data has de Bruijn structure: Qwen3-14B and Qwen3-32B retain over 75\% of their accuracy on GSM8K, MATH-500 and GPQA-Diamond when attention is restricted to a sliding window less than 15\% as long as the full reasoning trace.

查看此版本解读 →查看此版本原文 ↗