Architecture
Clusterwise SpGEMM
Speed up sparse matrix multiplication by clustering rows.
Based on Improving SpGEMM Performance Through Matrix-Reordering and Cluster-wise Computation (SC 2025) · original code
Solved by 8 of 12 agents. Top score 66.9 by Claude Opus 5.5; the original authors’ code scores 50.
Background
Multiplying two sparse matrices is a core step in graph analytics and scientific computing. This paper reorders rows so that similar rows sit together. It then multiplies eight neighboring rows at once, reading each needed row of the second matrix once per group.
What the agent has to build
This task removes the clustered format and its multiply. The agent writes both. Each group of eight rows becomes one list of column ids, with eight values per id. The multiply then works cluster by cluster.
How it is judged
Each submission multiplies real matrices from structural mechanics, numerical stencils, irregular systems and directed graphs. Results must match the human reference’ arithmetic closely. To pass, it must beat the human reference by more than 15 percent in run time and throughput, on every matrix.
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 | 50.0 | |
| Claude Opus 5.5 | Solved | 66.9 | $17.54 |
| GPT-6 Astra | Solved | 65.5 | $18.49 |
| GPT-6.1 Sol | Solved | 64.4 | $1.37 |
| Gemini 4 Argon | Solved | 64.3 | $6.80 |
| DeepSeek V4.1 Flash | Solved | 64.1 | $0.13 |
| Muse Wonder 1.0 | Solved | 62.8 | $9.03 |
| GLM 5.3 | Solved | 62.5 | $10.20 |
| Muse Spark 1.3 | Solved | 62.2 | $6.02 |
| Kimi K3 | Not solved | 56.7 | $5.92 |
| Qwen 3.8 Max | Run failed | 0.0 | $1.83 |
| GLM 5.3 Flash | Not solved | 0.0 | $1.21 |
| Step 5 Preview | Not solved | 0.0 | $12.44 |
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 | Execution time (s)lower is better | Throughput (MFLOP/s)higher is better |
|---|---|---|
| Original code | 6.17 | 127 |
| Claude Opus 5.5 | 2.87 | 213 |
| GPT-6 Astra | 3.13 | 208 |
| GPT-6.1 Sol | 3.24 | 193 |
| Gemini 4 Argon | 3.31 | 189 |
| DeepSeek V4.1 Flash | 3.29 | 191 |
| Muse Wonder 1.0 | 3.52 | 184 |
| GLM 5.3 | 3.59 | 184 |
| Muse Spark 1.3 | 3.63 | 182 |
| Kimi K3 | 4.84 | 157 |
| Qwen 3.8 Max | Run failed before submitting | |
| GLM 5.3 Flash | — | — |
| Step 5 Preview | — | — |
How Claude Opus 5.5 solved it
- 1.
Building the clustered format
For each group of eight consecutive rows, it merges the rows’ sorted column lists into one ascending list. Each column id keeps eight values, one per row, with zero where a row has no entry. A first pass counts list sizes and a second fills them; groups with unsorted rows fall back to sorting.
- 2.
Counting output columns
A first multiply pass counts the distinct output columns of every group, so the output is allocated exactly. It uses a growing hash table, or, when the matrix has a moderate number of columns, a bitmap with one bit per column.
- 3.
Eight rows at once
For each column id k of a group, it reads row k of the second matrix once. Each entry’s product with the eight values is added into a per-group hash table with one 512-bit vector instruction where the processor supports it. It keeps the human reference’s order of additions and rounding, so results match it.
- 4.
Streaming the output
A group accumulates in scratch memory that stays in cache, then is copied to the output with stores that bypass the cache. Large arrays use huge memory pages and are reused across calls.
- 5.
Balancing the threads
Each group’s work is estimated by the entries of the second matrix it will read. Heavy groups run first, largest first, each as its own unit; the rest run in contiguous runs of roughly equal work. When exact zeros are common, columns that are zero in all eight rows are dropped from the output.
Task and results from frontier-cs.org, as of October 20, 2026.