On the VC Dimension of Autoregressive Linear Threshold Functions

Ilan Doron-Arad; Idan Mehalel; Elchanan Mossel

cs.LGOct 27, 2026

On the VC Dimension of Autoregressive Linear Threshold Functions

Authors: Ilan Doron-Arad, Idan Mehalel, Elchanan Mossel

Organizations: MIT · The Hebrew University

Abstract

Linear threshold functions (LTFs) are a canonical class of Boolean predictors. In the autoregressive setting, the same LTF reads the most recent $d$ bits, generates the next bit, and returns the bit produced after $T$ steps. While the one-step class has VC dimension $d$ , for general $T$ the counting upper bound is $O(d^2)$ . We prove that the VC dimension is $Θ(d^2)$ for every $T\ge d^2$ , resolving the quadratic gap for deterministic autoregressive LTFs. We then adapt the same technique to show an exponential separation between deterministic and stochastic autoregressive models: replacing the sign of LTFs by logistic sampling can increase the VC dimension of the final majority prediction class from quadratic to exponential in $d$ .

Figures & tables

Panel of Figure 1 — Figure 1: One round of the recursion for $m=5$ , selected row $i=2$ , and encoding $\theta_{2}=21$ , from $t=3$ to $t+1=4$ . Within each region (Row, Test, Output, Pointer), coordinates are ordered by increasing $j$ . The row bits remain unchanged. The current output bits encode $16$ , and the pointer selects position $3$ , whose weight is $2^{3-1}=4$ . Since $21-16\geq 4$ , the new test bit is $1$ , so the third output bit is set to $1$ , while all other output bits remain unchanged. Finally, the pointer shifts from position $3$ to position $2$ , selecting the next digit to test.

Panel of Figure 2 — Figure 2: Transition from $E^{3}$ to $E^{4}$ for $m=5$ , $i=2$ , and $\theta_{2}=21$ . The black $1$ is the first bit of each block, fixed to $1$ by the definition of the encoding in ( 15 ). The same LTF generates all bits of $E^{4}$ from left to right. The row bits remain unchanged. The output bits initially represent $16$ , and the pointer selects $j=3$ , with weight $2^{3-1}=4$ . Since $21-16\geq 4$ , the new test bit is $1$ . As the lower arrow indicates, this new test bit sets the third output bit to $1$ , so the output bits now represent $16+4=20$ . The pointer changes to $j=2$ . Test, output, and pointer bits are each stored twice in adjacent positions. Unmarked positions are zero; spacing is schematic.

Panel of Figure 3 — Figure 3: Choosing inputs for a fixed row $i$ . The three rows correspond to columns $s_{1},s_{2},s_{3}$ ; each repeats the same string $0^{d-p}E_{i}^{0}E_{i}^{1}$ on the left. Each blue frame selects $d$ consecutive bits, forming $x^{i,s}$ . The short arrows show the shift $r_{s}$ from the start of the string to the start of each input. The long arrows represent $T$ generated bits. The blue cell is at position $\pi(\mathrm{out},s)$ in the later block $E_{i}^{t}$ and equals $\lambda_{i,s}$ . Since $E_{i}^{0}$ and $E_{i}^{1}$ are independent of the labels, so are the selected inputs. Shown for $T$ a multiple of $p$ ; spacing is schematic.

VC Dimension

See all 10 papers

The Optimal Sample Complexity of Learning Autoregressive Chain-of-Thought
Jul 8, 2026Zhiyuan LiCoT Reasoning PAC Learning
Toyota Technological Institute at Chicago
Contradiction Graphs Determine VC Dimension
May 19, 2026Jesse Campbell, Daniel Ibaibarriaga, Lev ReyzinStatistical Learning Theory VC Dimension
Department of Mathematics, Statistics, & Computer Science University of Illinois Chicago
Bagging Robustly Learns VC Classes with Linear Sample Complexity
Aug 13, 2026Omar MontasserAdversarial Robustness Classification
Yale University

Jul 8, 2026J/K move · Enter open · S save

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

Zhiyuan Li

Toyota Technological Institute at Chicago

CoT Reasoning PAC Learning Statistical Learning Theory

Open paper AskPDF arXiv

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.

Abstract

VC Dimension

Explore similar work

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

Contradiction Graphs Determine VC Dimension

Bagging Robustly Learns VC Classes with Linear Sample Complexity