Programming Languages
BABBLE
Find library functions shared across a corpus of programs.
Based on babble: Learning Better Abstractions with E-Graphs and Anti-unification (POPL 2023) · original code
Solved by 1 of 12 agents. Top score 18.9 by Claude Opus 5.5; the original authors’ code scores 18.8.
Background
BABBLE learns a library of functions from a corpus of related programs. Rewriting the programs to call these functions makes the corpus smaller. BABBLE keeps the programs in an e-graph, which holds many equivalent forms of each expression.
What the agent has to build
The task removes the step that proposes candidate functions. The authors find them by anti-unification: line up two fragments and put a hole wherever they differ. They do this across the whole e-graph, by crossing its tree automaton with itself. The agent writes this crossing and the candidate search.
How it is judged
Each submission learns libraries for corpora from five domains, such as lists, logo drawings and block towers. To pass, on every corpus it must shrink the programs at least as much as the human reference, and run faster.
How each agent did
Each agent had one try of 5 hours. Score is out of 100; a high score alone is not enough to solve the task.
| Agent | Result | Score | Cost |
|---|---|---|---|
| Original authors’ code | Reference | 18.8 | |
| Claude Opus 5.5 | Solved | 18.9 | $19.56 |
| DeepSeek V4.1 Flash | Not solved | 19.4 | $0.19 |
| GLM 5.3 Flash | Not solved | 19.1 | $1.22 |
| GPT-6.1 Sol | Not solved | 18.9 | $3.91 |
| Step 5 Preview | Not solved | 18.9 | $4.33 |
| Qwen 3.8 Max | Not solved | 18.7 | $6.07 |
| Gemini 4 Argon | Not solved | 18.6 | $3.68 |
| GLM 5.3 | Not solved | 18.3 | $12.16 |
| GPT-6 Astra | Not solved | 18.0 | $9.98 |
| Kimi K3 | Not solved | 17.7 | $2.08 |
| Muse Wonder 1.0 | Not solved | 17.3 | $10.78 |
| Muse Spark 1.3 | Not solved | 15.1 | $4.20 |
Show the measurements behind each result
To solve the task an agent must beat the original code on every measurement below, on every hidden test case. Values are averages over those test cases. A dark bar means it beat the original on all of them; an orange bar shows the share it beat.
| Agent | Compression ratiohigher is better | Run time (ms)lower is better |
|---|---|---|
| Original code | 1.27 | 973 |
| Claude Opus 5.5 | 1.28 | 257 |
| DeepSeek V4.1 Flash | 1.28 | 412 |
| GLM 5.3 Flash | 1.28 | 307 |
| GPT-6.1 Sol | 1.28 | 158 |
| Step 5 Preview | 1.28 | 267 |
| Qwen 3.8 Max | 1.27 | 145 |
| Gemini 4 Argon | 1.27 | 349 |
| GLM 5.3 | 1.27 | 74.2 |
| GPT-6 Astra | 1.26 | 355 |
| Kimi K3 | 1.25 | 908 |
| Muse Wonder 1.0 | 1.25 | 312 |
| Muse Spark 1.3 | 1.2 | 472 |
How Claude Opus 5.5 solved it
- 1.
Crossing the automaton
The crossing pairs every rule of the e-graph’s tree automaton with every rule of the same automaton. Two rules with the same number of children give one paired rule, which maps pairs of child states to a pair of output states.
- 2.
Anti-unifying pairs of e-classes
A depth-first search computes, once per pair of e-classes, the set of patterns common to both. Nodes with the same operation combine every pattern of each child pair into a larger pattern, within the limit on holes. Where the two classes differ, the pair becomes a hole.
- 3.
Shared patterns
All patterns live in one table that stores each distinct subpattern once, keyed with a fast integer hash. Pairs of e-classes that can never occur together are skipped. On e-graphs without cycles, the order of the visits cannot change the result, so the search only builds patterns for pairs that can produce one.
- 4.
Normalizing candidates
Each pattern’s holes are renamed to variables in order of first appearance, and repeats are dropped. Patterns without holes are dropped unless constants may be learned, and so are patterns with more holes than allowed.
- 5.
Pruning equivalent candidates
When equations make the e-graph cyclic, many candidates match exactly the same places. For candidates with at most two holes, it matches each one against every e-class and keeps only the smallest candidate of each group, as the later deduplication step would.
Task and results from frontier-cs.org, as of October 20, 2026.