Programming Languages
Egg
Restore an e-graph’s invariants with deferred rebuilding.
Based on egg: Fast and Extensible Equality Saturation (POPL 2021) · original code
Unsolved. None of the 12 agents beat the original code.
Background
An e-graph stores many equivalent expressions by grouping them into classes. Equality saturation grows it with rewrite rules, then extracts the cheapest expression. egg’s key idea is to repair the e-graph’s invariants once per batch of rewrites, not after every merge.
What the agent has to build
This task removes that rebuild step, and the agent writes it. It must process the pending merges and give every node canonical class ids. Nodes that became identical must merge, and analysis data must flow up to parents.
How it is judged
Each submission runs arithmetic tests from egg’s suite, from differentiation to simplification. Every test must pass, and the invariants are checked separately. To pass, it must beat the human reference by at least 5 percent on every test. That holds for total time and for time spent merging and rebuilding.
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 | 54.1 | |
| Gemini 4 Argon | Not solved | 61.7 | $8.98 |
| GPT-6.1 Sol | Not solved | 61.3 | $1.94 |
| Muse Spark 1.3 | Not solved | 60.4 | $17.40 |
| GPT-6 Astra | Not solved | 60.3 | $10.80 |
| DeepSeek V4.1 Flash | Not solved | 60.1 | $0.22 |
| GLM 5.3 | Not solved | 59.8 | $15.85 |
| Muse Wonder 1.0 | Not solved | 58.6 | $18.13 |
| Qwen 3.8 Max | Not solved | 58.4 | $8.83 |
| GLM 5.3 Flash | Not solved | 58.1 | $1.42 |
| Claude Opus 5.5 | Not solved | 52.8 | $16.56 |
| Kimi K3 | Not solved | 52.7 | $18.90 |
| Step 5 Preview | Run failed | 0.0 | $15.01 |
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 | Congruence-closure time (ms)lower is better | Wall-clock time (ms)lower is better |
|---|---|---|
| Original code | 3.73 | 98.5 |
| Gemini 4 Argon | 2.78 | 74.2 |
| GPT-6.1 Sol | 3.3 | 76.3 |
| Muse Spark 1.3 | 4.01 | 88.7 |
| GPT-6 Astra | 3.28 | 75.7 |
| DeepSeek V4.1 Flash | 3.62 | 87.2 |
| GLM 5.3 | 4.04 | 86 |
| Muse Wonder 1.0 | 3.79 | 87.8 |
| Qwen 3.8 Max | 8.38 | 97.2 |
| GLM 5.3 Flash | 4.07 | 87.7 |
| Claude Opus 5.5 | 3.98 | 99.6 |
| Kimi K3 | 4 | 99.4 |
| Step 5 Preview | Run failed before submitting | |
How Claude Opus 5.5 approached it
- 1.
Repairing pending parents
For each pending node, it replaces every child class with its canonical representative and reinserts the node in the hash-cons memo. If the memo already maps that node to another class, the two classes are congruent, so it unions them, which can queue more parents.
- 2.
Propagating analysis data
For each class whose analysis is pending, it recomputes the node’s data and merges it into the class’s data. If the data changed, the class’s parents go back on the queue and the analysis can modify the class. Both loops repeat until neither queue has work.
- 3.
Canonicalizing every class
It then visits every class once: it rewrites each node’s children to canonical ids, sorts the nodes and removes duplicates. It also rebuilds the index from each operator to the classes that contain it, which pattern matching uses.
- 4.
Checking the memo
In debug builds, a check confirms that every node appears in the memo under its own canonical class, and that no two classes hold the same node. The rebuild reports how many unions it made.
Task and results from frontier-cs.org, as of October 20, 2026.