CoT-Depth: Instance-Level Serial Depth Governs Chain-of-Thought Budget

Chain-of-thought (CoT) theory assigns a single worst-case budget to every instance of a problem class, yet sequential difficulty within a class spans orders of magnitude: on $s$-$t$ connectivity, a star graph resolves in one step while a length-$(n-1)$ path demands $\Theta (n)$ steps at the same encoding length. We introduce instance serial depth $d(x)$—the minimum depth of a computation-trace DAG under a canonical rule system—as the first per-instance CoT complexity measure, and prove matching upper and lower bounds on the CoT budget in terms of $d(x)$. A constant-depth log-precision Transformer solves any instance $x$ in $d(x)+O(\log n)$ CoT steps, extending to $\lceil d(x)/L\rceil +O(\log n)$ for $L$ layers. Within the bounded-state, local-prefill class ${\mathcal{M}}_{L,b}^{\mathrm{loc}}$, correctness on pointer-chasing instances forces $\Omega (d(x)/L)$ steps unconditionally across the full depth range, and full prompt-to-prompt attention preserves the linear rate. Class-level budgeting therefore wastes $\Omega (n/\log n)$ steps relative to instance-adaptive allocation—a depth–size separation. Experiments on three synthetic task families ($s$-$t$ connectivity, multi-digit addition, Boolean formula evaluation) confirm $d$-linear scaling in every one of 21 model$\times$task configurations ($p<0.02$), with the per-instance slope reaching $+1.07$ in a $4\times$ wider model. A depth probe on hidden states cuts MAE by up to 67% over length baselines and, plugged into an instance-adaptive allocator, saves 19.6% of inference steps on STCON at 100% accuracy. The law extends beyond training from scratch: a LoRA-fine-tuned Qwen2.5-7B carries $d$-linear step counts to templated multi-hop QA, and off-the-shelf 7–8B instruction models allocate depth-proportional CoT under mere few-shot prompting—Qwen3-8B emits $+0.79$ CoT steps per unit depth ($R^2=0.54$, $p<10^{-100}$), independently reproduced on Qwen2.5-7B ($+0.43$, $p<10^{-43}$).