# babble: Learning Better Abstractions with E-Graphs and Anti-Unification

arXiv: https://arxiv.org/abs/2212.04596 · HTML: https://mlsanity.com/paper/2212.04596/

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Dec 2022.

## Built on by (most cited first, 23 of 23)

- [LILO: Learning Interpretable Libraries by Compressing and Documenting Code](https://mlsanity.com/paper/2310.19791/) (2023)
- [Learning adaptive planning representations with natural language guidance](https://mlsanity.com/paper/2312.08566/) (2023)
- [ShapeCoder: Discovering Abstractions for Visual Programs from Unstructured Primitives](https://mlsanity.com/paper/2305.05661/) (2023)
- [Improving Unsupervised Visual Program Inference with Code Rewriting Families](https://mlsanity.com/paper/2309.14972/) (2023)
- [Anti-unification and Generalization: A Survey](https://mlsanity.com/paper/2302.00277/) (2023)
- [Learning of Generalizable and Interpretable Knowledge in Grid-Based Reinforcement Learning Environments](https://mlsanity.com/paper/2309.03651/) (2023)
- [Searching for Programmatic Policies in Semantic Spaces](https://mlsanity.com/paper/2405.05431/) (2024)
- [ShapeLib: Designing a library of programmatic 3D shape abstractions with Large Language Models](https://mlsanity.com/paper/2502.08884/) (2025)
- [Refactoring Codebases through Library Design](https://mlsanity.com/paper/2506.11058/) (2025)
- [Bayesian Program Learning by Decompiling Amortized Knowledge](https://mlsanity.com/paper/2306.07856/) (2023)
- [AbstractBeam: Enhancing Bottom-Up Program Synthesis using Library Learning](https://mlsanity.com/paper/2405.17514/) (2024)
- [A Compute-Matched Re-Evaluation of TroVE on MATH](https://mlsanity.com/paper/2507.22069/) (2025)
- [e-boost: Boosted E-Graph Extraction with Adaptive Heuristics and Exact Solving](https://mlsanity.com/paper/2508.13020/) (2025)
- [Learning logic programs by discovering higher-order abstractions](https://mlsanity.com/paper/2308.08334/) (2023)
- [MeMo: Meaningful, Modular Controllers via Noise Injection](https://mlsanity.com/paper/2407.01567/) (2024)
- [Online library learning in human visual puzzle solving](https://mlsanity.com/paper/2603.23244/) (2026)
- [Library learning with e-graphs on jazz harmony](https://mlsanity.com/paper/2605.04622/) (2026)
- [Algebraic anti-unification](https://mlsanity.com/paper/2407.15510/) (2024)
- [Common Benchmarks Undervalue the Generalization Power of Programmatic Policies](https://mlsanity.com/paper/2506.14162/) (2025)
- [LLM-Guided Strategy Synthesis for Scalable Equality Saturation](https://mlsanity.com/paper/2604.17364/) (2026)
- [Prospective Compression in Human Abstraction Learning](https://mlsanity.com/paper/2605.09985/) (2026)
- [Decode-Time Grammars: Constrained LLM Generation over a Refinement Order of Grammar Fragments](https://mlsanity.com/paper/2607.18357/) (2026)
- [Co-DSL: Human-LLM Co-design of Reusable Spatial Concepts for Layout Generation](https://mlsanity.com/paper/2610.15290/) (2026)

## Abstract (arXiv)

Library learning compresses a given corpus of programs by extracting common structure from the corpus into reusable library functions. Prior work on library learning suffers from two limitations that prevent it from scaling to larger, more complex inputs. First, it explores too many candidate library functions that are not useful for compression. Second, it is not robust to syntactic variation in the input. We propose library learning modulo theory (LLMT), a new library learning algorithm that additionally takes as input an equational theory for a given problem domain. LLMT uses e-graphs and equality saturation to compactly represent the space of programs equivalent modulo the theory, and uses a novel e-graph anti-unification technique to find common patterns in the corpus more directly and efficiently. We implemented LLMT in a tool named BABBLE. Our evaluation shows that BABBLE achieves better compression orders of magnitude faster than the state of the art. We also provide a qualitative evaluation showing that BABBLE learns reusable functions on inputs previously out of reach for library learning.