Causal Evaluation of Formal Language Learnability: Why Correlation Fails

Paper: 2606.09822 Authors: Vésteinn Snæbjarnarson, Anej Svete, Josef Valvoda, Reda Boumasmoud, Brian DuSell, Ryan Cotterell Categories: cs.CL, cs.FL

The Gap

Existing work on language model (LM) task learnability relies on correlational analysis: you throw data at a model and measure performance on a task, then plot frequency vs. accuracy. The assumption is that more exposure to a task’s training examples directly causes better performance. But natural language tasks are tangled — learning one task (e.g., subject-verb agreement) can be confounded by learning another (e.g., word order) because they share training data. The field has no way to isolate the causal effect of task-specific data frequency.

This paper attacks that gap with a clean controlled setting: formal languages generated by probabilistic finite automata (PFAs). They show that in this sandbox, correlational evaluation systematically leads to wrong conclusions — tasks that seem easier due to high frequency are actually confounded by other properties. They then introduce a causal intervention method using a binning semiring that lets them precisely control how often a target property appears in a training corpus. The logic chain is:

[PROBLEM]          [ASSUMPTION]          [METHOD]                [EVIDENCE]            [CONCLUSION]
  > Correlation   > Confounders         > Causal intervention     > Decomposed KL      > Correlational
  > in LM eval      exist between         via binning semiring     divergence shows      evaluation is
  > gives wrong     task frequency        to control property       that frequency        fundamentally
  > conclusions     and other features    occurrence in corpus      alone doesn't cause   flawed for
                                              + causal graph        learnability          learnability

The Increment

One sentence: Before this paper, researchers assumed frequency-to-learnability correlation was causal; after this paper, we know that without intervention, confounders can completely invert the true relationship.

Core Mechanism

The method has four components: (1) a probabilistic finite automaton (PFA) that generates strings of a formal language, (2) a binning semiring that tracks how many times a target property (e.g., number of “ab” substrings) occurs in a string, (3) a biased sampling procedure that uses the binning semiring to generate corpora with controlled distributions of that property, and (4) a causal graphical model that formalizes the data-generation process, allowing decomposition of the KL divergence between model and target distribution into contributions from specific sub-tasks.

Data flow: The PFA generates strings, each annotated with a bin count (e.g., count of property). The binning semiring defines a new weighted automaton where weights are polynomials in a variable that tracks the count. By raising or lowering specific monomial coefficients, you can create a distribution that either increases or decreases the average count of the property in a corpus. Then you train an LM on that corpus and measure its performance on predicting the property (e.g., predicting the bin count of a string). The causal graph separates the effect of overall data from the effect of property-specific frequency.

[PFA model] -> [Binning semiring transforms weights] -> [Sampling procedure:
   +- adjust weight of target property by scaling monomials]
   v
[Corpus with controlled property frequency] -> [Train LM]
   |
[Learned distribution] -> [Compare to target via KL divergence]
   |
[Decompose KL into: (1) property-specific loss, (2) other loss]
   |
[If property-specific loss drops only when we intervene on that property, 
  the correlation is causal; otherwise, it's confounded.]

Structural metaphor: Imagine you’re a biologist studying whether a new fertilizer causes plants to grow taller. You notice that in your garden, plants near the fence are taller, and they also get more fertilizer. Correlational reasoning says “more fertilizer → taller.” But maybe the fence provides shade, which is the real cause. To isolate, you’d use a controlled experiment: you assign plants to receive either high or low fertilizer *regardless of where they sit.

This paper does the same for LM task learnability. The “plants” are training examples; the “fertilizer” is the count of a target property (like the number of verb phrases in a sentence). The “fence” is some other correlated feature (like sentence length). The binning semiring is the biologist’s pipette: it lets you precisely control the “fertilizer dose” for each string, independent of other features. The decomposed KL divergence is the biologist’s ruler that measures height gain from fertilizer alone, subtracting any growth from shade. The causal graph is the experimental design that ensures you’re not fooled by spurious correlations.

Key Concepts

• Binning semiring: An algebraic structure that extends the standard probability semiring (sun, \times) by adding a variable that counts occurrences of a property. Formally, it’s the semiring of polynomials in one variable over the reals: weight = p(x) where coefficient of x^k gives the probability that a string contains exactly k occurrences of the property. When combining strings during generation (e.g., concatenation), the counts add (coefficients convolve). This lets you manipulate the *distribution of counts by adjusting polynomial coefficients.

• Decomposed KL divergence: Standard KL divergence measures how different two distributions are, but it lumps all aspects together. Here, they decompose it into a sum of terms: one term for the specific sub-task (e.g., predicting the property count) and another term for everything else. The sub-task term quantifies how much of the LM’s “knowledge” about that property comes from training data that actually contains that property. If this term drops when you increase property frequency, but the other term stays constant, you have evidence of a causal link.

• Causal graphical model for data generation: They define a DAG where nodes represent: (I) the underlying PFA parameters, (T) the training corpus, (M) the learned model, (P) performance on a sub-task. Edges show causal paths: parameters cause corpus, corpus causes model, model causes performance. Confounders exist when a node (like overall language complexity) affects both the corpus (through shared features) and performance. By intervening on one node (the property frequency in T) while keeping others fixed, they can measure the true causal effect.

Framework Shift

The shift is from observing passive frequency to actively controlling it — from correlation to intervention.

Before (mainstream approach):
   Observe natural corpus -> measure task frequency -> train LM -> measure performance
   (No control; confounders like other features vary freely)
   Result: spurious correlation

After (this paper):
   Design formal language with known structure -> intervene on property frequency via binning semiring -> 
   train LM -> decompose performance into causal and non-causal components
   Result: true causal learnability

One sentence: From passive correlation hunting to active intervention, the core shift is treating frequency as a manipulated variable rather than a natural measure.

Expert Assessment

Problem choice: A real and important gap. The field of LM evaluation is filled with correlational studies that implicitly assume causation. This paper provides a rigorous way to test that assumption, at least in formal domains. It’s placed at the intersection of formal language theory and causal inference — a smart niche.

Method maturity: Clever insight — the binning semiring is an elegant algebraic trick that turns a continuous property (count of a pattern) into a controllable dial. However, the approach is currently limited to properties that can be counted via regular languages (PFAs). Extending to richer tasks (e.g., syntax) would require substantial work. There’s no brute force; it’s mathematically concise.

Experimental integrity: Baselines are fair — they compare correlational analysis (frequency alone) to causal analysis (with intervention) on the same formal languages. The numbers show clear cases where correlation gives opposite sign to causation. One red flag: the formal languages are very simple (small hidden states, limited alphabet). It’s not clear whether the magnitude of confounders in real NLP is as large as their examples show.

Writing quality: The paper is well-structured but dense. The abstract and introduction are clear. The section on the binning semiring could use more concrete examples — it’s easy to get lost in algebra. If they added a walkthrough with a tiny language (like {a,b} with property “contains ‘ab’”) and showed the weight adjustments step by step, the paper would be much more accessible.

Verdict: weak accept — the idea is strong and the causal framing is important, but the direct applicability to natural language is limited; the formal gap is convincingly shown, but the natural-language gap remains to be demonstrated.

Takeaways

• Binning semiring as a general tool: If you ever need to control the distribution of a property in a generated corpus (e.g., for data augmentation or bias mitigation), the binning semiring gives you a principled way to do it without ad-hoc filtering.
• Decomposed KL divergence for debugging LMs: When training a multi-task LM, you can use this decomposition to diagnose which sub-tasks are being learned from which training examples, and whether correlations are misleading you.
• Warning sign for practitioners: If you ever find a strong correlation between training set frequency of a feature and model performance *without a control group (like a held-out set with balanced frequency), be very skeptical — it’s likely confounded.