💬 NLP

Causally Evaluating the Learnability of Formal Language Tasks

This paper introduces the binning semiring and a causal framework using formal languages to demonstrate that standard correlational evaluations of language model learnability are flawed due to confounders, thereby providing a rigorous method to accurately measure the data requirements for specific tasks.

Original authors: Vésteinn Snæbjarnarson, Anej Svete, Josef Valvoda, Reda Boumasmoud, Brian DuSell, Ryan Cotterell

Published 2026-06-09

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Vésteinn Snæbjarnarson, Anej Svete, Josef Valvoda, Reda Boumasmoud, Brian DuSell, Ryan Cotterell

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a robot how to speak. You give it a massive library of books (the training data) and ask it to learn everything: how to write code, how to tell jokes, and how to solve math problems.

The big question this paper asks is: How much specific practice does the robot need to learn a specific skill?

For example, if you want the robot to learn a specific type of math puzzle, do you need to show it 10 examples, or 10,000?

The Problem: The "Correlation Trap"

The authors argue that if you just look at the robot's natural learning process, you might get the wrong answer. They call this the Correlation Trap.

The Analogy:
Imagine you are studying how good a chef is at making Spicy Tacos.

The Correlation Method: You look at all the chefs in the world. You notice that the chefs who make the most Spicy Tacos are also the ones who have the best kitchens, the freshest ingredients, and the most experience cooking in general.
The Mistake: You conclude, "Aha! To make great Spicy Tacos, you just need to make a lot of them!"
The Reality: Maybe those chefs are great because of their fancy kitchens, not because they made so many tacos. If you gave a chef with a bad kitchen 10,000 Spicy Tacos to practice, they might still fail.

In the world of AI, "natural" data is messy. If a robot sees a specific pattern (like a math puzzle) often, it usually sees it alongside other helpful patterns (like simple grammar or common words). It's hard to tell if the robot learned the puzzle because it saw it 100 times, or because it saw it alongside 100 easy sentences that helped it learn.

The Solution: The "Causal Intervention"

To fix this, the authors decided to stop watching the robot learn naturally and start forcing the learning environment. They wanted to isolate the variable: "How many times did the robot see this specific thing?"

The Analogy:
Instead of letting the robot wander through a library, you put it in a room with a conveyor belt.

The Setup: You control the belt. You say, "Today, this robot will see exactly 50 Spicy Tacos and nothing else."
The Control: You do this for 10 robots. One sees 50 tacos, one sees 100, one sees 1,000. You keep everything else (the room, the lighting, the robot's brain) exactly the same.
The Result: Now, if the robot gets better at tacos as the number increases, you know for a fact that the number of tacos caused the improvement. You removed the "fancy kitchen" confounders.

The Magic Tool: The "Binning Semiring"

To pull off this conveyor belt trick, the authors invented a new mathematical tool called the Binning Semiring.

The Analogy:
Imagine you are counting marbles rolling down a track. Usually, you just count them as they go. But the authors wanted to count them while they were rolling, and force the track to stop exactly when the count hit a specific number (like 50).

The "Binning Semiring" is like a smart counter built into the track itself.

It doesn't just say "1, 2, 3..."
It says, "If you roll a red marble, add 1 to the count. If you roll a blue one, add 0."
Crucially, it allows the authors to rewind and reroll the track mathematically. They can say, "Show me all the possible paths where the red marble count is exactly 50," and ignore all the paths where it's 49 or 51.

This allows them to generate training data that is mathematically guaranteed to have a specific number of "target" items, without accidentally changing the difficulty of the task or the length of the sentences.

What They Found

The authors tested this on two types of robot brains: LSTMs (an older, simpler type) and Transformers (the powerful type used in modern AI like ChatGPT). They used "formal languages" (strict, rule-based puzzles) instead of real English to keep things simple and controlled.

The Big Discovery:
When they looked at the data naturally (the Correlation Trap), the results were misleading.

Sometimes, the data suggested that a robot learned a task better when it saw it less often.
Sometimes, the data suggested that a robot was bad at a task just because the specific "recipe" of the training data happened to be hard, not because the task itself was hard.

When they used their Causal Intervention (the conveyor belt):

The curves changed completely.
They found that for some tasks (like "Parity," which is checking if there is an odd or even number of items), the older robot (LSTM) actually got much better as it saw more examples.
But the newer robot (Transformer) hit a wall. No matter how many examples they forced it to see, it didn't get significantly better.

The Takeaway

The paper concludes that standard ways of testing AI are flawed because they mix up "seeing a lot" with "seeing the right things."

If you want to know if an AI can truly learn a specific skill, you can't just look at how it performs on a random pile of data. You have to intervene, control the exact number of examples, and see what happens. Otherwise, you might think the robot is smart when it's just lucky, or think it's dumb when it's just confused by the noise.

In short: Don't trust the correlation. Force the experiment to find the truth.

Technical Summary: Causally Evaluating the Learnability of Formal Language Tasks

Problem Statement

Language models (LMs) function as multi-task learners, acquiring diverse abilities from a single training corpus. A fundamental question in understanding LM capabilities is determining how much task-specific data is required to learn a given task. In natural language settings, this inquiry is confounded by the difficulty of delineating specific tasks and the presence of inter-task similarities that introduce confounders. Standard correlational evaluation practices—where one correlates the frequency of a property in a dataset with model performance—often yield flawed conclusions because property frequency is entangled with other structural features of the data distribution (e.g., string length, overall complexity).

The paper argues that to rigorously investigate the relationship between data frequency and learnability, one must isolate these confounders. Using natural language corpora for this purpose is intractable due to the lack of control over data generation. Therefore, the authors propose a controlled setting using formal languages induced from Probabilistic Finite Automata (PFAs) to serve as a methodological testbed.

Methodology

Causal Framework

The authors formulate the experimental pipeline as a Graphical Causal Model (GCM) involving four random variables:

A (PFA): The generating process (the automaton).
D (Dataset): The corpus sampled from $A$ .
L (Learned Model): The neural network parameters resulting from training on $D$ .
M (Performance): The fidelity of $L$ relative to $A$ .

The core distinction lies between conditioning and intervening:

Correlational (Conditioning): Evaluating $P(M | D \in P)$ , where $P$ is a property (e.g., "dataset contains $N$ occurrences of a symbol"). This introduces a dependence between $A$ and $D$ , as PFAs naturally prone to generating such datasets are overrepresented.
Causal (Intervening): Evaluating $P(M | \text{do}(D \in P))$ , where the data generation process is modified to satisfy $P$ while preserving the original marginal distribution of $A$ . This decouples the target property from the rest of the corpus's structural features.

The Binning Semiring

To implement the causal intervention efficiently, the paper introduces the binning semiring, an algebraic structure that allows for the control of target property counts during sampling.

Definition: For a base semiring $K$ and a threshold $R$ , the $R$ -th order binning semiring consists of $(R+1)$ -tuples $v = (v_0, v_1, \dots, v_R)$ .
Operation: Addition is element-wise. Multiplication is an overflow-accumulating convolution: the $n$ -th element of the product represents the weight of paths with exactly $n$ target occurrences (for $n < R$ ), while the $R$ -th element aggregates all counts $\ge R$ .
Application: A PFA is "lifted" to a Weighted Finite Automaton (WFA) over this semiring. By computing backward weights on this lifted automaton, the authors derive the conditional distribution over corpora with a specific count of target transitions. This enables constrained sampling: drawing datasets where a specific property (e.g., a transition or symbol) occurs exactly $N$ times, regardless of the underlying PFA's natural bias.

Experimental Pipeline

Sampling: Generate PFAs (either fixed topologies with resampled weights or random topologies).
Intervention: Use the binning semiring algorithms to sample corpora with exact counts of a target property (e.g., transitions leaving a specific state).
Training: Train LSTMs and Transformers on these corpora.
Evaluation: Measure performance using a decomposed Kullback–Leibler (KL) divergence. Unlike standard KL, which averages over all states, this metric isolates the error contribution of specific transitions or states, allowing for a localized assessment of learnability.

Key Contributions

Binning Semiring: A novel algebraic tool that enables exact control over the frequency of specific features in sampled corpora from PFAs, facilitating causal interventions that were previously computationally intractable (compared to rejection sampling).
Causal Evaluation Framework: A formalization of LM learnability studies as a causal inference problem, distinguishing between correlational observations and causal effects of data frequency.
Decomposed KL Metrics: A method to localize performance metrics to specific sub-tasks (states, transitions, or symbols) within the formal language setting.
Empirical Evidence of Confounding: Demonstrations that standard correlational evaluations can lead to incorrect conclusions about learnability due to uncontrolled confounders.

Results

The authors conducted experiments across three settings:

PARITY + Star-Free Automaton: A controlled setup combining an easy-to-learn star-free language ( $aa^*$ $a a^{*}$ ) and a hard-to-learn PARITY language.
- Finding: In correlational analysis, low counts of PARITY strings were associated with high error, but this trend was non-monotonic and confounded by string length distributions. Causal intervention revealed a monotonic relationship where increased PARITY counts consistently improved learnability, exposing the true difficulty of the task for Transformers versus LSTMs.
Random Topologies (50 states): Sampling 952 random PFAs.
- Finding: Correlational trends often inverted compared to causal trends. For instance, at low occurrence counts, correlational KL divergence was low (suggesting easy learning) because the specific automata that naturally produce few target instances were structurally simpler. Causal sampling removed this bias, showing that learnability actually improved with frequency.
Fixed Topology, Varying Weights: A single 40-state topology with 400 weight configurations.
- Finding: Confounding effects varied significantly even within the same topology. At certain states, the causal curve descended sharply with increased frequency, while the correlational curve remained flat or rose, indicating that the "difficulty" observed in correlational studies was an artifact of the specific weight configurations, not the task itself.

Across all settings, the causal curves (solid lines) diverged significantly from correlational curves (dotted lines). In some cases, the correlational trend suggested a property was easy to learn when it was actually hard, or vice versa.

Significance and Claims

The paper claims that standard correlational methodologies for evaluating formal language learnability are inherently flawed because they fail to control for inter-task confounders. The observed relationship between data frequency and model performance often reflects the sampling procedure and the structural properties of the automata that co-vary with the target property, rather than the intrinsic learnability of the task.

By introducing causal intervention via the binning semiring, the authors provide a tool to disentangle these effects. They argue that this approach is necessary for:

Accurately comparing the inductive biases of different architectures (e.g., Transformers vs. RNNs).
Characterizing scaling behaviors without the noise of confounding structural features.
Attributing difficulty to specific structural features rather than artifacts of data distribution.

The authors position this work as a methodological correction for the field, suggesting that prior correlational findings regarding how language properties affect learnability may require revisiting. They note that while their study focuses on PFAs, the framework extends naturally to richer automata (e.g., pushdown automata) and offers a rigorous alternative to the "black box" evaluation of neural language models on formal tasks.