HPC
Hygra
Compute core numbers of a hypergraph in parallel.
Based on Practical Parallel Hypergraph Algorithms (PPoPP 2020) · original code
Solved by 5 of 12 agents. Top score 58.9 by Gemini 4 Argon; the original authors’ code scores 48.7.
Background
A hypergraph lets one edge join any number of vertices. Core numbers show how deep inside its dense part each vertex sits. They come from peeling: remove every vertex in fewer than \(k\) edges, drop each edge that loses a member, and repeat. A vertex’s core number is the largest \(k\) it survives. Hygra computes them in parallel.
What the agent has to build
The task removes the core-number computation. The agent writes all of it, given each vertex’s edges and each edge’s vertices. Every core number must be exact.
How it is judged
Each submission runs on random hypergraphs with hundreds of thousands of vertices and millions of memberships. To pass, on every hypergraph it must beat the human reference by at least 3%, on eight threads and on one.
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 | 48.7 | |
| Gemini 4 Argon | Solved | 58.9 | $3.39 |
| DeepSeek V4.1 Flash | Solved | 58.2 | $0.11 |
| GPT-6 Astra | Solved | 52.2 | $4.18 |
| Claude Opus 5.5 | Solved | 49.7 | $16.78 |
| Kimi K3 | Solved | 43.8 | $13.48 |
| Muse Wonder 1.0 | Not solved | 57.6 | $14.68 |
| Step 5 Preview | Not solved | 56.8 | $9.90 |
| Qwen 3.8 Max | Not solved | 49.6 | $9.62 |
| GPT-6.1 Sol | Not solved | 47.1 | $0.94 |
| GLM 5.3 | Not solved | 43.1 | $6.81 |
| Muse Spark 1.3 | Not solved | 0.0 | $12.65 |
| GLM 5.3 Flash | Not solved | 0.0 | $2.59 |
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 | Run time (ms)lower is better | Sequential run time (ms)lower is better |
|---|---|---|
| Original code | 181 | 660 |
| Gemini 4 Argon | 132 | 543 |
| DeepSeek V4.1 Flash | 135 | 582 |
| GPT-6 Astra | 162 | 672 |
| Claude Opus 5.5 | 176 | 541 |
| Kimi K3 | 207 | 623 |
| Muse Wonder 1.0 | 139 | 574 |
| Step 5 Preview | 141 | 574 |
| Qwen 3.8 Max | 177 | 635 |
| GPT-6.1 Sol | 188 | 699 |
| GLM 5.3 | 213 | 648 |
| Muse Spark 1.3 | — | — |
| GLM 5.3 Flash | — | — |
How Claude Opus 5.5 solved it
- 1.
Peeling level by level
Each level is the smallest live degree among the remaining vertices. Every vertex at that degree leaves and takes the level as its core number. A hyperedge dies with its first removed member, and each of its other members loses one from its degree; members that fall to the level leave in the next round of the same level.
- 2.
Three ways to run a round
Push: each live hyperedge that touches the leaving vertices is handled once, by its lowest-numbered leaving member, which decrements the other members. Pull: the leaving vertices mark their hyperedges dead, and every remaining vertex recounts its live hyperedges. Fix: when few vertices remain, only they are recounted, until none drops.
- 3.
A cost model picks the mode
Before each round, it estimates the work of each mode from the frontier size, the level, the average vertex degree and the average hyperedge size, and runs the cheapest. Push suits small frontiers and pull suits huge ones. When the frontier holds every remaining vertex, they all take the current level at once.
- 4.
Ownership instead of atomics
Each thread owns aligned blocks of 64 vertices and of the dead-hyperedge bitmap. In parallel push rounds, threads send kills and decrements as messages to the owner, so no atomic operation touches the hot arrays. One array holds the live degrees and, for removed vertices, their final core numbers.
Task and results from frontier-cs.org, as of October 20, 2026.