Where Finite Learners Land on a Limit Point: Norm Budgets and Non-Associative Categorial Grammars

Some grammar classes are provably impossible to learn from example sentences alone. The standard trap is a limit point: an infinite chain of ever-larger languages whose union is also a language in the class. A learner that has seen finitely many sentences cannot tell whether it is looking at one member of the chain or at the union. Béchet and Foret (2003) proved that this trap exists for non-associative Lambek grammars. These are logic-based grammars in which each word carries a type built from left and right "slashes" that say what it combines with, and word grouping is fixed. Their chain is the languages $\{a^k bc \mid k \le n\}$, which converge to $a^*bc$. The result is purely about the limit. It says nothing about what a real, finite, gradient-trained learner does when it sees 200 strings from $L_n$. Does it stay at $L_n$, or jump to the union?

We propose to measure that choice and explain it. Our hypothesis is that a trained learner's side of the limit point is set by its weight-norm budget and not by its width. The budget is the quantity that width-independent generalization theory identifies as the real capacity measure. If this holds, the abstract subset problem of learning theory becomes a measurable crossover curve. It also yields a principled way to probe the open "order 2–4 gray zone" of non-associative learnability. A cheap symbolic pilot finds candidate limit points, and trained learners tell us whether those candidates behave like the provably unlearnable order-5 case or like the provably learnable order-1 case.

Core Claim

Fix a limit-point chain $L_0 \subset L_1 \subset \dots$ with union $L_\infty$. Train a neural type-assigning learner on $N$ strings sampled from $L_n$. Let $\rho$ be the fraction of held-out strings in $L_\infty \setminus L_n$ that the trained grammar accepts. $\rho \approx 0$ means the learner stayed at $L_n$, and $\rho \approx 1$ means it committed to the limit. We claim three things. First, there is a crossover chain index $n^*(B, N)$ above which learners commit to the limit, where $B$ is the norm budget. Second, when the regularizer belongs to the width-independent family of Neyshabur, Tomioka and Srebro (2015), the curves $n^*$ collapse across hidden widths $H$ at fixed $B$. That family consists of group norms $\mu_{p,q}$ with $q \le p^*$, meaning an $\ell_p$ norm on each unit's incoming weights, an $\ell_q$ norm across units, and $p^*$ the Hölder conjugate of $p$. Third, under regularizers outside that family, $n^*$ drifts with $H$.

The reasoning is short. In that paper's analysis, the norm budget, not $H$, bounds the function class. So any simplicity preference the network exerts between $G_n$ and the typically simpler limit grammar $G_*$ should be a function of $B$ alone. The same analysis shows width dependence is unavoidable when $1/p + 1/q < 1$. That gives us a built-in negative control.

Research Program

Stage 1: symbolic pilot. We treat preliminary evaluation as what it should be: a cheap, high-sensitivity filter whose outputs are conjectures, not results. For atom sets of size 2–3, vocabularies of 3–4 words, and type order $r \in \{1,\dots,5\}$, we enumerate rigid product-free non-associative grammars. We compute each grammar's language up to string length $\ell$ (we plan $\ell \le 14$). We then search for chains of grammars whose truncated languages are strictly nested and whose truncated union matches another rigid grammar of the same order.

Two sanity anchors calibrate the search. It must rediscover the order-5 chain of Béchet and Foret, and it must find no stable chains at order 1, where learnability is known. A chain counts as a candidate only if it persists as $\ell$ grows. We pre-register the criterion, persistence across three consecutive values of $\ell$, and we explicitly do not claim that any candidate is a proof. Candidates are handed to formal proof attempts, and failures are reported.

Stage 2: a differentiable non-associative inducer. For each order cap $r$ we precompute, symbolically and once, a finite type inventory and a table of which type pairs reduce to which types under non-associative derivability, including slash-introduction steps. A neural network of width $H$ maps each word to a soft distribution over the inventory. A differentiable inside algorithm over binary bracketings, run on that table, gives string likelihoods, which are trained by gradient descent. Reading off the most likely type per word yields a rigid grammar. So we measure $\rho$ and also exact recovery of $G_n$ versus $G_*$, covering both the semantic and the syntactic notion of learning.

This differs from Clark and Schuler (2023), whose neural categorial inducer uses only classical function application on CHILDES. It also differs from Bhargava and Penn (2021), whose differentiable proof-net parser assumes known lexical types. Our inducer must infer the types, which is exactly where unlearnability bites.

Stage 3: norm and width sweep. We cross $H \in \{16, 64, 256, 1024, 4096\}$ with a grid of budgets $B$ under four regularizers. Two are inside the width-independent family: per-unit $\ell_1$, and ordinary weight decay, which is $\mu_{2,2}$. One is outside it: per-weight max-norm clipping, $\mu_{\infty,\infty}$. The last is no regularization.

Likelihood training on sampled strings carries implicit negative evidence, because long strings are absent. So we run two sampling regimes over $k$: uniform on $\{0,\dots,n\}$, and geometric. Any effect that appears only under one regime is reported as sampling-driven rather than capacity-driven.

Baselines

The naive reference point is a learner that commits to the smallest grammar consistent with the sample. By construction this gives $\rho = 0$ at every $n$, and it corresponds to the conservative Gold-style learner. Its opposite is the maximally general learner that always outputs $G_*$. Any trained system must be located between these two, and reporting $n^*$ is how we locate it.

The strongest existing learner of formal languages from few examples is MDLRNN from Lan, Chemla and Katzir (2023). It is an RNN chosen by minimum description length through evolutionary search, and it reports a BLISS score of 10 on $a^n b^n$, generalizing from $n \le 20$ to $n = 35{,}000$. Its description-length objective is itself a simplicity prior, which makes it the most direct competitor to our norm-budget account.

We run MDLRNN with its published search on identical sampled strings, with the same number of training strings and a wall-clock budget matched to our largest sweep cell. We also compute its $\rho$ from next-symbol acceptance on the held-out $L_\infty \setminus L_n$ strings. Our account "beats" MDLRNN if two things hold. First, $n^*$ for our norm-controlled inducer is predictable from $B$ alone, with the width-collapse residual below the seed-to-seed spread. Second, MDLRNN's commitment behavior is either matched by a single $B$ or shown to vary unpredictably across seeds. No reported result was found on Lacuna for any learner on the non-associative limit-point languages, so all numbers on those languages will be new.

An LSTM and a small Transformer trained on the same strings, with the same tuning budget of 30 hyperparameter trials each, serve as unstructured neural baselines. We expect them to show the "approximate trap" that Lan et al. report for LSTMs.

The key ablation isolates the capacity measure while holding everything else fixed. It compares the same inducer under in-family versus out-of-family regularizers at matched training loss. A second ablation replaces non-associative derivability with application-only reduction, the setting of Clark and Schuler. This tests whether slash-introduction is what creates the limit-point behavior at low orders.

Why not just…?

Why not just settle the order 2–4 question by symbolic search or a SAT encoding, with no neural learners at all? For the existence of limit points, this is a serious alternative, and Stage 1 adopts it. Symbolic search is the right tool for producing conjectures. It cannot tell us what a finite gradient-trained learner does at a candidate chain, and that is the question Direction 4 says asymptotic proofs leave open. If Stage 1 finds no low-order candidates, the gray-zone part of the proposal shrinks to that negative pilot result. The norm-budget claim is then tested on the order-5 chain alone.

Why not just train a large Transformer or LSTM and measure length generalization, as in BLISS? Unstructured sequence models give an accept/reject behavior but no grammar. So one cannot distinguish "committed to $G_*$" from "approximately tracks string statistics." Lan et al. already show LSTMs fail exact generalization beyond training lengths. We include these models as baselines. If they happen to produce clean width-invariant crossover curves, then the categorial inducer is unnecessary for the capacity claim. We would report that result.

Why not just use weight decay instead of special group norms? Weight decay is $\mu_{2,2}$, which already satisfies $q \le p^*$. The theory therefore predicts it should be width-independent too, and we treat it as a first-class condition rather than a strawman. The claim is about the family, and the contrast that matters is with out-of-family max-norm clipping and with no regularization. If weight decay and per-unit $\ell_1$ give indistinguishable $n^*$ curves, that confirms the account in its simplest form.

Why not argue that per-unit norms, which Neyshabur et al. show push networks toward unshared tree-structured computation, naturally match the tree bracketings of non-associative grammar? We considered and rejected this as a core mechanism. The "tree" in that theorem concerns hidden units not being shared downstream. The tree in the grammar concerns string bracketing. The analogy is verbal, not structural, and no experiment we could design would cleanly separate it from ordinary capacity effects.

Proposed Experiments

The primary experiment uses the Béchet–Foret chain. We sample $N \in \{100, 300, 1000\}$ strings from $L_n$ for $n \in \{2, \dots, 30\}$, train the inducer across the full $H \times B \times$ regularizer grid with five seeds, and estimate $n^*$ as the chain index where $\rho$ crosses 0.5.

The decisive check has two parts. We fit $n^*$ as a function of $B$ pooled across widths, and we test whether adding $H$ as a predictor reduces held-out error for in-family regularizers (predicted: no) and for out-of-family ones (predicted: yes). If $n^*$ shifts systematically with $H$ at fixed in-family $B$, the core claim is falsified.

The secondary experiment repeats the analysis on every Stage-1 candidate chain at orders 2–4, plus the permutation chain of Costa Florencio (2003) as an associative-commutative contrast. We ask whether learners on each candidate show an order-5-like crossover or order-1-like stable recovery of $G_n$. Whenever these signals disagree with a later formal analysis, we record them as false positives of the pilot.

A final grounding check trains the same inducer, with order caps $r = 1$ to $5$, on the CHILDES Adam and Eve sections. There we compare against Clark and Schuler's reported Recall-Homogeneity of 0.59 and unlabeled F1 of 0.76 for their biased model, and RH 0.33 without the bias. We ask whether a norm budget can replace their hand-set English right-branching prior in resolving the split between good and failed runs. This experiment is confirmatory only, and a null result there does not affect the formal-language claims.