The Deterministic Horizon: When Extended Reasoning Fails and Tool Delegation Becomes Necessary¶

🕒 Published (v1): 2026-05-29 21:35 UTC · Source: Arxiv · Venue: ICML 2026 · link

Why this paper was selected

Theoretical: attention-capacity limits when to delegate to tools vs extend reasoning

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

TL;DR¶

Extended chain-of-thought (CoT) reasoning fails on deterministic state-tracking tasks not due to preference biases but due to an information-theoretic bottleneck in decoder-only attention. The paper derives a closed-form Deterministic Horizon $d^* \in [19, 31]$ beyond which tool delegation is architecturally necessary. Across 12 models and 8 domains, tool-integrated reasoning reaches 86–94% accuracy versus 24–42% for neural CoT.

Problem¶

The prevailing assumption that more test-time compute improves reasoning collapses for deterministic state-space search — tasks requiring exact sequential state maintenance (permutation puzzles, program tracing, multi-table SQL joins, multi-step navigation). Prior work (Wu et al., 2026) attributes performance degradation to "Simplicity Bias" (a preference for shorter outputs) and predicts training interventions can recover accuracy. This paper argues the cause is instead an architectural ceiling: autoregressive attention lacks the substrate to maintain exact state across long reasoning chains.

Method¶

State-Space Jaccard (SSJ) metric distinguishes capability from preference failures by computing $\text{SSJ}(d) = |S^d_{\text{true}} \cap \hat{S}^d_{\text{model}}| / |S^d_{\text{true}} \cup \hat{S}^d_{\text{model}}|$ with precision/recall decomposition — preference failure predicts only recall decays, while capability failure (decoherence) predicts both decay together.

Context-dependent error model: per-step state-tracking error grows linearly with depth, $$\epsilon(d) = \epsilon_0 + \gamma \cdot \frac{d}{L_{\text{eff}}}$$ where $L_{\text{eff}} = O(10^2)$ steps is far smaller than the raw context window $L = O(10^5)$ tokens. Compounding under conditional independence yields super-exponential accuracy decay: $$P(\text{correct at depth } m) \leq \exp\!\left(-m\epsilon_0 - \frac{\gamma m(m+1)}{2L_{\text{eff}}}\right)$$

Attention Bottleneck Theorem: under softmax concentration (each head resolves $O(\sqrt{L})$ positions) and value decorrelation, the number of reliably trackable states is bounded: $$|S_{\text{track}}| \leq c(\delta, \rho_{\max}) \cdot 2^{H \cdot \log_2(L/H) \cdot d_h^{1/2}}$$

Deterministic Horizon: solving $P(\text{correct}) \geq \alpha$ gives $$d^* = \frac{-\epsilon_0 L_{\text{eff}} + \sqrt{\epsilon_0^2 L_{\text{eff}}^2 + 2\gamma L_{\text{eff}} \ln(1/\alpha)}}{\gamma}$$ with empirical scaling $d^* \approx 0.314\sqrt{d_h \cdot H}$.

Validation uses 12 models × 5 conditions × 8 tasks × 500 instances × 3 seeds = 720,000 evaluations ($3,420 cost), plus a fine-tuning ablation on Llama-3.1-8B (5,000 optimal-length traces, 3 epochs) to discriminate architectural from preference explanations.

Key Contributions¶

Attention Bottleneck Theorem with achievability construction (tight in $H$ and $L$; $d_h^{1/2}$ dependence is presented as an achievability result via sparse parity functions)
Context-dependent error model $\epsilon(d) = \epsilon_0 + \gamma d/L_{\text{eff}}$ derived from attention entropy dynamics, yielding the super-exponential decay in Theorem 4.2
Deterministic Horizon $d^*$ with closed-form formula and empirical scaling law $d^* \propto \sqrt{d_h \cdot H}$ validated on open-weight models
SSJ metric with precision/recall decomposition providing empirical discrimination between capability and preference failure
Fine-tuning upper bound (Theorem 4.10): for $d > d^*$, accuracy gain from fine-tuning is bounded by $O(d^*/d)$ regardless of training distribution
Cross-model correlation $r = 0.81$–$0.91$ establishing failures are architectural, not training-specific

Results¶

Tool delegation (C3) vs. neural CoT (C1): 86–94% vs. 24–42% across all models and tasks; Cohen's $d = 2.1$–$3.4$
PermutationProbe: GPT-4o 89.7% (C3) vs. 28.3% (C1); o3-mini 94.2% vs. 42.1%
SWE-Bench-State: GPT-4o 86.4% (C3) vs. 24.1% (C1); Claude-4.5-Opus 91.2% vs. 29.6%
Preference manipulation (C4) yields only +0.7–1.0% over C1; TOST equivalence confirmed ($p < 0.001$)
Fine-tuning (C5) yields only +3.2% over C1 (predicted >30% by Simplicity Bias); benefit vanishes beyond $d^* \approx 20$
Depth degradation: 78% accuracy at depth 10 → 34% at depth 30 → random at depth 50+
Cross-model correlation: $r = 0.81$–$0.91$ per-instance accuracy across model pairs
Architecture scaling validated: $d^* = 20\pm1.3$ (Llama-3.1-8B, predicted 20.1), $28\pm1.5$ (Llama-3.3-70B, predicted 28.4)
Real-world $d^*$ range: SWE-Bench 19–24, WebArena 19–23, SQL-Multi 21–26

Limitations¶

$O(\sqrt{L})$ effective attention window (Assumption 4.4) and value decorrelation (Assumption 4.5) are empirically grounded modeling assumptions, not proven laws; bound shifts <20% under ±20% perturbation
$L_{\text{eff}} \propto d_h \cdot H$ is a phenomenological ansatz not implied by the bottleneck theorem; treated as empirically validated scaling
$d_h^{1/2}$ exponent in the bottleneck theorem inherits a per-head effective-rank ansatz; not proven tight in $d_h$
Scope restricted to deterministic state-tracking tasks; no claims for open-ended generation or short-chain arithmetic (which stay below $d^*$)
Proprietary model architectural parameters (GPT-4o, Claude) are community estimates used only for illustrative calculations; quantitative $d^*$ scaling validated only on open-weight models
Fine-tuning experiment conducted on a single open-weight model (Llama-3.1-8B); generalization of Theorem 4.10 to larger models is not empirically confirmed

Relevance to Agentic AI / LLM Agents¶

This paper provides the first principled, quantitative criterion for when an agent should delegate to external tools versus continue neural reasoning — a core architectural decision in hybrid agentic systems. The Deterministic Horizon $d^* \in [19, 31]$ gives practitioners a concrete routing threshold: tasks requiring more than ~20–30 sequential state-tracking steps should be offloaded to BFS solvers, code interpreters, or symbolic executors rather than extended CoT. Validation on SWE-Bench, WebArena, and SQL-Multi directly grounds this in the agentic workloads (code repair, web navigation, database querying) that modern agent frameworks tackle. The result reframes the design question from "how much reasoning budget to allocate" to "which subtasks are architecturally unsuitable for neural execution," shaping the decomposition and tool-routing logic of future ReAct/tool-augmented agent architectures.