Outcomes become exponentially hard to attribute to early steps: endpoint-only supervision needs exponentially more data past a critical depth, parallelism helps only logarithmically, and strategically placed checkpoints (uniform under homogeneous decay, greedy-optimal under heterogeneity) are the best inspection policy.

Main Finding

Credit assignment from terminal outcomes in deep sequential processes suffers an information-theoretic barrier: the signal tying an early step to the final outcome decays exponentially with the number of intervening stages. There exists a critical horizon Hcrit such that with only terminal supervision, steps within Hcrit of the outcome can be learned with polynomial samples, while steps beyond Hcrit require exponentially many samples (in the gap H − t). This is a structural limit (not an algorithmic bug) driven by per-stage contraction of distinguishability; it explains phenomena like RL “critic collapse” and motivates when and how to allocate expensive step-level supervision.

Key Points

• Signal Decay Bound

  • Distinguishability about a step t seen at the terminal outcome contracts multiplicatively across stages. Roughly, information decays like η^{H−t} where η ∈ [0,1) is a per-stage contraction coefficient defined via χ^2-contraction of the induced Markov kernel on abstract states.
  • Sample complexity for identifying step t from terminal outcomes alone grows exponentially in H − t (tight lower and upper bounds are provided).
  • The critical horizon Hcrit grows logarithmically with sample size n and signal strength Δ^2, and scales inversely with −log η (i.e., the worse the per-stage contraction, the shorter Hcrit).

• Width Limits (Parallel Rollouts)

  • Producing multiple rollouts from the same prefix reduces estimator variance but yields diminishing returns when rollouts are correlated.
  • Effective independent width is capped at ≈ 1/ρ, where ρ is pairwise correlation among rollout outcomes; hence parallel rollouts extend Hcrit only logarithmically.

• Objective Mismatch

  • Additive reward aggregation (sum of per-step rewards) optimizes the wrong quantity when the true correctness requirement is sequential validity (all steps correct), which is multiplicative. High per-step accuracy can still give low probability of full validity (e.g., 99 steps at 99% each → overall ≈ 0.37).
  • The paper proposes curriculum strategies that interpolate between additive (learnable) objectives and multiplicative (correct) objectives as policy quality improves.

• Optimal Inspection Design

  • Checkpoints reset the signal-decay clock; the minimax inspection design seeks to minimize the worst-case sample complexity across steps (i.e., minimize the maximal distance to the next checkpoint in information terms).
  • Under homogeneous contraction (constant η across stages), uniform checkpoint spacing is minimax-optimal.
  • Under heterogeneous contraction, a greedy information-distance placement that places checkpoints where signal loss is fastest is optimal.
  • To retain polynomial sample complexity across deep processes, inspection density must scale nearly linearly with depth (a lower bound of order Ω(H/log H) inspections is noted).

• Practical diagnostics and links to AI

  • In LLM reasoning, the contraction η is controlled by sampling temperature: higher temperature increases downstream overlap and worsens contraction.
  • The observed “critic collapse” in RL value networks is statistically optimal when terminal outcomes carry little information about early steps.
  • Process (step-level) supervision suffices to overcome the critical horizon; outcome-only supervision may be infeasible beyond it.

Data & Methods

• Formal model

  • Episodic finite-horizon MDP with terminal reward R ∈ {0,1}. Abstract-state view: many-to-one mapping from raw observations (tokens, sensors) to abstract validity states (semantic correctness, quality grade).
  • Supervision regimes: outcome supervision (only R observed), process supervision (per-step labels r_t observed), and k-step/partial supervision (labels at regular intervals).

• Information-theoretic tools

  • χ^2-divergence and Le Cam–style hypothesis-testing lower bounds: distinguishing two hypotheses with constant error requires n = Ω(1/χ^2(P‖Q)) samples.
  • Strong Data Processing Inequalities (SDPI): define a χ^2-contraction coefficient ηχ2(K) for a Markov kernel K; successive application gives multiplicative shrinkage of χ^2-divergence.
  • Tensorization of χ^2 over i.i.d. samples converts divergence decay into exponential sample-complexity increases.

• Concrete results

  • Rigorous Signal Decay Bound: information about a step t, measured at terminal outcomes, contracts as ≲ η^{H−t}, yielding closed-form expressions for Hcrit (function of n, η, Δ^2, and target error ε).
  • Width analysis: models rollouts’ correlation and shows effective number of independent samples saturates at ~1/ρ.
  • Objective mismatch analysis: compares additive objective optimizers vs multiplicative (sequential-validity) objective and characterizes failure modes; proposes curriculum transition rules.
  • Inspection design: minimax optimization over checkpoint placements, proofs of uniform optimality under homogeneity and greedy optimality under heterogeneity.

• Empirical validation

  • Numerical experiments on synthetic Markov chains to confirm exponential signal decay and tightness of bounds.
  • Experiments on LLM reasoning chains using GSM8K to illustrate temperature-controlled contraction and benefits of intermediate supervision. (Full experimental details and additional plots are provided in the paper’s appendices/Electronic Companion.)

Implications for AI Economics

• Supervision cost vs feasibility trade-off

  • The paper gives a principled diagnostic: estimate per-stage contraction η (e.g., from adjacent-stage transition overlaps); compute Hcrit for your sample budget n and signal strength Δ^2. If process depth > Hcrit, outcome-only supervision is not merely inefficient — it is infeasible without exponentially more data.
  • This quantifies when investments in step-level annotation (costly human labeling or automated verifiers) are economically necessary versus when they are a cost-saving optimization.

• Resource allocation and inspection budgeting

  • Optimal checkpoint placement (uniform under homogeneous decay; greedy otherwise) offers a cost-efficient way to allocate a limited annotation/inspection budget to maximize learnability across stages.
  • The nearly linear scaling of required inspections with depth implies that deep reasoning chains or deep production lines require proportionally more supervision/inspection resources; planners should budget accordingly rather than assuming occasional checks suffice.

• Design of AI training and evaluation

  • For LLMs and other deep reasoning systems, reducing contraction (e.g., via lower sampling temperature, diversified conditioning signals that preserve upstream distinctions) can extend Hcrit and reduce supervision cost.
  • Parallelization (more rollout width) yields limited mitigation unless rollout correlation can be reduced; investing in decorrelated rollouts or independent perturbations might be necessary for width to help.
  • Reward engineering: systems that optimize additive per-step rewards may boost average quality but fail at end-to-end validity. Economic design of training curricula should move from additive proxies to multiplicative (sequential-validity) objectives as quality improves to align incentives with social/operational value.

• Organizational and strategic takeaways

  • Measurement and auditing: η is auditable from production/log data; managers can use it to decide whether adding checkpoints or increasing sample size is the right investment.
  • Productization: for product teams building reasoning systems, allocate annotation budget strategically (checkpoint placement, partial supervision schedules) to minimize the cost of achieving end-to-end correctness.
  • Policy implications: regulators or safety teams concerned with high-assurance chains (e.g., legal reasoning, medical workflows) should treat terminal-only validation as insufficient beyond the estimated critical horizon and require intermediate verification or stricter controls.

Overall, the paper supplies an actionable, theory-grounded framework connecting information-theoretic limits to concrete supervision and inspection design choices. It turns the vague intuition that “deep chains are hard to supervise” into computable diagnostics (estimate η and Hcrit) and prescriptive strategies (where and how often to inspect; when to use step-level rewards), which are directly relevant to economic trade-offs in AI system deployment and operations.