🤖 AI

Saturating Scaling Laws for Equational Discovery: A Phenomenology of Growth Dynamics in Three Toy Substrates with Two Real-World Replications

This paper investigates growth dynamics in equational discovery across toy and real-world domains, finding that while short-term growth follows a power law, long-term trajectories exhibit substrate-dependent saturation patterns best modeled by a saturating power-law function, with the specific dynamics varying significantly between different computational environments.

Original authors: Fabio Rovai

Published 2026-05-26

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Fabio Rovai

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 running a factory that builds new rules for a game. Every day, your factory tries to invent a new rule, checks if it makes sense, and if it does, adds it to the "Rule Book."

This paper is a study of how fast this Rule Book grows over time. The author, Fabio Rovai, ran this experiment in three different "game worlds" (math, logic, and lists) and looked at real-world examples of how math libraries grow on the internet.

Here is the story of what they found, explained simply.

1. The Two Ways Things Grow

The researchers were looking for a pattern in the growth. They found two main possibilities:

The "Forever Exponential" (Pure Power-Law): Imagine a snowball rolling down a hill. It gets bigger, and because it's bigger, it picks up even more snow faster and faster. It never stops accelerating. This is what happens when you are just starting out.
The "Saturating" Curve: Imagine filling a bucket with a hose. At first, the water level rises quickly. But as the bucket gets full, the water has nowhere to go. The level slows down and eventually stops rising, even if you keep the hose on. The bucket has reached its limit.

2. The Short-Term vs. Long-Term Mystery

When the researchers looked at the short-term growth (the first few days of the experiment), everything looked like the "Forever Exponential." The Rule Book was growing fast, and it fit a simple mathematical curve perfectly.

However, the researchers had a theory: Eventually, the growth must slow down. Why? Because there are only so many possible rules you can invent before you run out of new ideas. Once you've found all the easy rules, finding new ones gets harder and harder.

They proposed a new model: The "Saturating Power-Law." This model says: "Start fast like a snowball, but eventually, you hit a ceiling and slow down."

3. The "One-Size-Fits-All" Trap

Here is the tricky part. The researchers tried to build a "crystal ball" to predict how fast the Rule Book would grow based on the factory settings (like how strict the quality control is, or how many workers are on the line).

Inside one factory: They could predict the growth speed very well. If they knew the settings, they knew the speed.
Across different factories: When they tried to use the settings from the "Math Factory" to predict the speed of the "List Factory," the crystal ball broke completely. It predicted the wrong speed so badly that it was worse than just guessing the average.

The Lesson: The rules for growth depend entirely on the type of game you are playing. You cannot use the same map for every territory.

4. The Real-World Test: Did the Toys Lie?

The researchers tested their "Saturating" theory on their toy factories.

The Result: The toy factories didn't grow long enough to hit the "ceiling." They were still in the "snowball" phase.
The Problem: When they tried to predict the future using the "Saturating" model, it failed. It predicted the growth would stop too soon. The simple "Forever Exponential" model actually predicted the future better because the toys hadn't actually reached their limit yet.

The Analogy: Imagine watching a baby grow. If you only watch for the first month, you might think the baby will grow forever at that speed. If you try to predict their height at age 20 based on that first month, you'll be wrong. You need to see them hit a growth spurt and then slow down to know the pattern. The toy factories were just "babies."

5. The Real-World Proof: Math Libraries

To see if the "ceiling" theory was real, they looked at two massive, real-world math libraries on the internet: Mathlib (for the Lean language) and Mathcomp (for the Coq language).

Mathlib (The Rapid Grower): This library has been growing explosively. The data showed that it is finally starting to bend. The growth is slowing down, just like the "Saturating" model predicted. It looks like it is hitting its ceiling.
Mathcomp (The Steady Grower): This library has been around for decades. It grows steadily, but it hasn't hit a ceiling yet. For this one, the "Forever Exponential" model still works best.

The Conclusion: The "Saturating" model is real, but you can only see it when the project is old enough to have run out of easy ideas.

6. The "Novelty Filter" Paradox

The researchers also found a funny quirk about how they filtered out bad rules.

In simple games (like basic math), being "novel" (finding a new rule) helps the factory grow fast.
In complex games (like high-level lists), being "novel" actually kills the growth. The factory gets so picky about what counts as "new" that it rejects almost everything, and the Rule Book stops growing.

Summary

This paper is a cautionary tale for anyone trying to predict how fast AI or math systems will grow:

Short-term growth looks like it will go on forever.
Long-term growth eventually hits a wall (saturation).
You cannot predict the speed of one system based on another; they have different "physics."
The "Saturation" effect is real, but you only see it in mature systems (like the Mathlib library), not in young, toy systems.

The authors are essentially saying: "We found a new law of growth for discovery systems, but it only shows up when the system gets old enough to run out of easy ideas."

Technical Summary: Saturating Scaling Laws for Equational Discovery

Problem Statement

The paper investigates whether deterministic symbolic discovery systems—specifically those that grow by adding equational rewrite rules—obey empirical scaling laws analogous to those found in large language models (LLMs). While scaling laws for neural models (Kaplan et al., 2020; Hoffmann et al., 2022) are well-established, it remains an open question whether deterministic substrates, such as those used in inductive logic programming, equality saturation, and program synthesis, follow comparable growth dynamics. The authors aim to characterize the phenomenology of growth in these systems, testing whether a simple power-law or a more complex saturating function better describes the accumulation of discovered rules over time.

Methodology

The study employs a controlled experimental framework involving three "toy" deterministic substrates of increasing typing complexity:

Arithmetic (arith): Equational identities over a typed grammar with addition, multiplication, and free variables.
Boolean (bool): Identities over logical operators (and, or, not).
Higher-Order List (list): A DreamCoder-inspired domain with primitives like map, fold, and cons.

The Discovery Loop:
The system grows a substrate $S$ (a set of rewrite rules) over discrete steps $t$ . At each step:

A generator proposes candidate equations based on the current state of $S$ (using strategies like random, compositional, frequency-weighted, or MDL-greedy).
Candidates are tested for semantic soundness via random instantiation.
Accepted pairs are generalized (replacing free variables with pattern variables).
A configurable acceptance filter (either "any" or "novelty") determines if the rule is committed to $S$ .

Data Collection:
The authors generated 592 independent discovery trajectories across these substrates, varying five architectural features: generator type, filter strictness, recursion depth, batch size, and random seed. They measured the total rule count $|S(t)|$ over time.

Modeling Approach:
The authors propose a heuristic mean-field closure model derived from assumptions of uniform coverage and approximate independence. This yields a differential equation for growth:
$\frac{dN}{dt} = K \cdot N^k \cdot e^{-\mu N}$
where $N$ is the substrate size, $k$ relates to the generator's recombination depth, and $\mu$ represents the coverage fraction of the candidate space.

Short-range ( $\mu N \ll 1$ ): The equation approximates a pure power law $N(t) \propto t^b$ , where $b = 1/(1-k)$ .
Long-range ( $\mu N \gtrsim 1$ ): The exponential term induces saturation, modeled by a logistic-power-law form.

The study fits three candidate models (pure power-law, stretched-exponential, saturating power-law) to the data using AIC for model selection and gradient-boosted regression to predict the exponent $b$ from architectural features.

Key Contributions and Results

1. Short-Range Power-Law Dynamics

Across 592 trajectories, the growth of the substrate size $|S(t)|$ at short ranges (up to 30 epochs) consistently fits a power-law form $t^b$ . The exponent $b$ varies continuously between 0 and 1.15 depending on the domain and architecture.

Architecture Sensitivity: Within a single substrate, the exponent $b$ is highly sensitive to architectural choices. A gradient-boosted regressor using five architectural features predicts $b$ with a cross-validated $R^2 \approx 0.82$ for both arithmetic/boolean and list domains.
Cross-Substrate Transfer Failure: A model trained to predict $b$ on arithmetic and boolean data fails completely when applied to the list domain ( $R^2 \approx -0.84$ ). The optimal architecture for compounding growth in flat-typed substrates (e.g., novelty filters) suppresses growth in higher-order typed substrates. This indicates that growth dynamics are substrate-conditional, not universal.

2. Long-Range Saturation Hypothesis

The authors tested whether the growth eventually saturates as predicted by their closure model.

Toy Data (List Domain): Extending five list-domain trajectories to 500 epochs, the saturating power-law model wins in-sample AIC comparisons for trajectories longer than 200 epochs. However, out-of-sample forecasting (fitting on the first 100 epochs and predicting the next 400) is won by the pure power-law in all 5 cases. The authors conclude that the toy trajectories do not actually reach the saturation regime within 500 epochs; the saturating model's preference in-sample is likely a fitting artifact that extrapolates poorly.
Real-World Data (Mathlib4): Analysis of monthly new .lean file additions in the Mathlib4 library (60 months, 9,701 files) supports the saturating form. The saturating model outperforms the pure power-law in out-of-sample forecasting by a factor of $\sim 7\times$ (RMSE 3,279 vs 23,896), suggesting Mathlib4 has reached a saturation regime.
Real-World Data (Coq Mathcomp): Analysis of monthly commits in the Coq Mathcomp library (129 months) favors the pure power-law. The saturating parameter $\mu$ collapses to zero, and the pure power-law outperforms the saturating model in out-of-sample forecasting by $\sim 67\times$ . This suggests Mathcomp has not yet reached a saturation regime.

3. Phenomenological Framing

The paper proposes a working framing: "Saturating power-law growth with substrate-conditional $(k, \mu)$ , observable when the substrate has reached its saturation regime." The dynamics are conditional at two levels:

Architectural parameters predicting the growth exponent do not transfer across different substrate types.
The functional family describing growth (pure vs. saturating power-law) depends on the specific lifecycle stage of the substrate.

Significance and Claims

The paper positions itself as a first empirical and theoretical investigation into the scaling laws of deterministic equational discovery, offering a phenomenology rather than a definitive theory.

Modest Scope: The authors explicitly state that the evidence is limited to three toy substrates and two real-world proxies (which are coarse, relying on commit/file counts). They acknowledge that the long-range toy results are "consistent with, not confirmed" due to the failure of out-of-sample forecasting on the toy data.
Key Insight: The primary finding is that symbolic discovery dynamics are substrate-conditional. Unlike neural scaling laws which often assume universality across architectures, the growth behavior here depends heavily on the specific "closure geometry" (coverage parameter $\mu$ ) of the substrate's type system.
Future Directions: The authors identify three concrete upgrades required to elevate this work from "toy phenomenology" to a "genuine phenomenon":
1. Replication on a non-toy substrate with trajectory-level granularity (not just commit counts).
2. Successful out-of-sample predictive forecasting for the saturating model.
3. A theoretical derivation of the saturation parameter $\mu$ from substrate combinatorics (e.g., type entropy) to make cross-substrate transfer falsifiable.

The paper concludes that while the saturating power-law framework is consistent with the observed data in regimes where saturation is plausible, it is not a universal law for all symbolic discovery systems. The work serves as a starting point for a potential "statistical mechanics of symbolic discovery."