The Dimension of Nonterminating Resampling Computations

Yunbei Xu

cs.CCJul 20, 2026

The Dimension of Nonterminating Resampling Computations

Authors: Yunbei Xu

Organizations: National University of Singapore

Abstract

A randomized algorithm may terminate almost surely even though exceptional random tapes make it run forever. This paper studies the survival tail, the Kolmogorov complexity of one such tape, and the Hausdorff dimension of all of them. For each $s>0$ at which the powered repair matrices commute, the main theorem bounds $\sum_wP[w]^s$ over surviving prefixes $w$ , uniformly over deterministic nonanticipating selectors. The case $s=1$ controls termination; the full family gives weak-source and dimension bounds. The source powers contain information absent even from the ordinary repair kernel and the complete stopping-time law. Under one common finite tape source, two overlapping disagreement-repair rules on a four-vertex path have the same ordinary kernels and the same stopping-time law for every selector, yet their nontermination dimensions can be arbitrarily close to zero and one. At one common source-power level, the same dominated tape source makes one rule run forever but gives the other an exponential stopping tail. The separation is caused by action labels that produce the same state transition and are therefore invisible at power one. For bounded-dependence $k$ -SAT, conditional block min-entropy above the trace-growth threshold gives exponential termination, and the effective dimension of an individual infinite run is bounded by the trace growth induced by the clauses repaired infinitely often. Tree formulas asymptotically attain the maximum-degree dimension and global source bounds, while clique formulas attain the graph-specific one-step threshold in the stated regime. An exact backward likelihood identity complements these setwise results with tail and coding bounds for each run.

Explore similar work

Jul 8, 2026cs.LG

The Optimal Sample Complexity of Learning Autoregressive Chain-of-Thought

We prove that, in the realizable PAC setting, the sample complexity of exact-trace learning for full autoregressive Chain-of-Thought traces is upper bounded by the standard multiclass rate of the local next-token class, where this rate is governed by the Daniely--Shalev-Shwartz dimension. Under exact-trace loss, one wrong action makes the whole trace incorrect; nevertheless, for every stopping rule

\mathtt{halt}

and every pointwise

\mathtt{halt}

-halting local class

\mathrm{H}

n_{\mathrm{PAC}}^{\varepsilon,δ}(\operatorname{Roll}_{\mathtt{halt}}(\mathrm{H}))=O((\operatorname{DSdim}(\mathrm{H})+\log(1/δ))/\varepsilon)

, with no dependence on rollout length. The dependence on

\operatorname{DSdim}(\mathrm{H})

is worst-case optimal, since one-step stopping recovers ordinary multiclass learning of

\mathrm{H}

. The proof introduces parity dimension, a rollout-stable refinement of DS dimension based on even pseudo-cubes. It controls one-inclusion density via a low-coordinate spanning theorem on finite restrictions and, unlike DS dimension itself, does not increase under autoregressive rollout. We also show why this detour is necessary: DS dimension can increase under rollout.

Zhiyuan Li

Optimal Sample Complexity Sample Complexity Autoregressive Rollout

Ask PDF

Sep 22, 2026cs.LG

When Recursive Models Finish Computing

Recursive models can continue updating their latent states beyond their nominal inference budget, so an incorrect output at that budget does not show whether computation is unfinished or has entered a persistently unsuccessful regime. We study the dynamics of completion in attention- and MLP-based Tiny Recursive Models (TRMs) on 1,000 hard Sudoku puzzles. Extending recurrence from the nominal 16 steps to 512 steps increases cumulative exact-solve accuracy from 59.2% to 87.5% for the attention model and from 74.4% to 91.9% for the MLP model, solving more than two-thirds of the puzzles unsolved in the nominal budget. Across both architectures, latent-state motion drops sharply after the first exact solution. Completed states are typically locally contractive along the trajectory direction, even though the same local Jacobian retains strongly expanding directions. We characterize this phenomenon as trajectory-conditioned anisotropic stability. Perturbation experiments confirm this directional stability across both models. The multi-step fate of the maximally expanding direction differs: it is absorbed within 16 steps in the attention model but persists longer in the MLP model. The anisotropic-stability pattern also holds for a second attention checkpoint. Together, these results distinguish nominal-budget failure from completed computation and identify a common dynamical signature of completion across two recurrent architectures.

Hare Krishna, Shubham Singh, Stephen Ebert +1

Continuation

Ask PDF

Sep 14, 2026cs.LG

Learning CNF Formulas from Uniform Random Solutions: Near-Tight Sample Complexity for Valiant's Algorithm

We revisit Valiant's algorithm (Commun. ACM'84) for learning

n

-variable CNF formulas with clause size

k

and variable degree

d

from i.i.d. uniform random solutions in the local lemma regime. For fixed

t\geq1

, under

k\gtrsim(1+1/t)\log d

, Valiant's algorithm achieves total variation error

\varepsilon

with

\widetilde{O}(n^{\lceil t \rceil}/\varepsilon)

sample complexity. For

t>1

, we prove a matching lower bound for Valiant's algorithm. At

t=1

(covering

0<t<1

), we show Valiant's algorithm has optimal sample complexity up to logarithmic factors by an information-theoretic lower bound

\widetildeΩ(n/\varepsilon)

Weiming Feng, Yixiao Yu, Yiyao Zhang

Optimal Sample Complexity Normalizing Flows

Ask PDF