Network
MetaOpt
Find traffic matrices on which a combined heuristic does worst.
Based on Finding Adversarial Inputs for Heuristics using Multi-level Optimization (NSDI 2024) · original code
Solved by 3 of 12 agents. Top score 52 by GPT-6 Astra; the original authors’ code scores 47.8.
Background
MetaOpt finds traffic on which a wide-area network heuristic falls furthest behind the optimal routing. The heuristic here keeps the better of two shortcuts. POP splits demands into three groups, each with a third of every link. Demand pinning sends each small demand along its shortest path.
What the agent has to build
This task removes the search for that traffic, and the agent writes it. For each of 27 source–destination pairs, it picks a demand of 0, 6 or 18, at most nine nonzero. Good choices defeat both shortcuts at once.
How it is judged
Instances use three real networks with perturbed link capacities. Exact linear programs replay the demands to measure the heuristic’s gap from the optimum. To pass, on every instance the gap must be at least as large as with the human reference.
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 | 47.8 | |
| GPT-6 Astra | Solved | 52.0 | $29.64 |
| GPT-6.1 Sol | Solved | 52.0 | $7.55 |
| Claude Opus 5.5 | Solved | 52.0 | $14.65 |
| DeepSeek V4.1 Flash | Not solved | 51.9 | $0.15 |
| Kimi K3 | Not solved | 51.1 | $18.95 |
| GLM 5.3 | Not solved | 49.9 | $13.12 |
| Muse Wonder 1.0 | Not solved | 49.8 | $21.60 |
| Step 5 Preview | Not solved | 43.2 | $17.81 |
| Muse Spark 1.3 | Not solved | 0.0 | $18.96 |
| Qwen 3.8 Max | Not solved | 0.0 | $23.50 |
| GLM 5.3 Flash | Not solved | 0.0 | $2.43 |
| Gemini 4 Argon | Not solved | 0.0 | $4.97 |
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 | Gap foundhigher is better |
|---|---|
| Original code | 26 |
| GPT-6 Astra | 29.4 |
| GPT-6.1 Sol | 29.3 |
| Claude Opus 5.5 | 29.4 |
| DeepSeek V4.1 Flash | 29.3 |
| Kimi K3 | 28.6 |
| GLM 5.3 | 27.6 |
| Muse Wonder 1.0 | 27.6 |
| Step 5 Preview | 22.6 |
| Muse Spark 1.3 | 0 |
| Qwen 3.8 Max | 0 |
| GLM 5.3 Flash | — |
| Gemini 4 Argon | — |
How Claude Opus 5.5 solved it
- 1.
An exact private scorer
It replays every candidate with its own small simplex solver for the path-form maximum-flow program, after a presolve that drops links that can never bind. The gap is the optimal throughput minus the better of POP and pinning. Cached POP results and cheap upper bounds skip the optimal solve when a candidate cannot beat the current best.
- 2.
Iterated local search
From a start vector it descends by first improvement in random order: change one pair’s level, or move a nonzero demand to an empty pair; deeper descents also try changes to two pairs at once. Every move keeps at most nine nonzero demands and the pinned demands within link capacity.
- 3.
Threads and an elite pool
Up to four threads search for three seconds of wall time. They share the best vector so far and a pool of 24 good, distinct vectors. Each round perturbs one to four pairs of a pool vector and descends again; every tenth round restarts from a random vector.
- 4.
A careful final pick
Equal-best vectors can replay to values that differ in the last bits. Among the tied best vectors, it keeps the one that the task’s exact oracle scores highest, and falls back to its own replay’s choice if the oracle fails.
- 5.
Seeds from cuts, its own idea
Before the local search, it enumerates small sets of links that cut the network. A cut makes a strong seed when demands of 18 must all cross it while many small pinned demands crowd it too: pinning then loses throughput that the optimum can recover by rerouting. Each thread scores its share of seeds and descends from the best.
Task and results from frontier-cs.org, as of October 20, 2026.