Network
BBQ
Generate the per-level logic of a hardware priority queue.
Based on BBQ: A Fast and Scalable Integer Priority Queue for Hardware Packet Scheduling (NSDI 2024) · original code
Solved by 3 of 12 agents. Top score 42.2 by Claude Opus 5.5; the original authors’ code scores 26.
Background
BBQ is a hardware priority queue that schedules network packets by integer priority. It keeps a first-in first-out bucket per priority under a tree of bitmaps. A set bit means its subtree holds packets, so the smallest priority lies along the first set bits.
What the agent has to build
The task removes the bitmap-level logic from a program that generates the queue’s hardware. The agent writes that logic. Each level must serve enqueue, dequeue-min and dequeue-max, even when operations arrive back to back.
How it is judged
Each design is simulated on operation traces at several tree depths, bitmap widths and capacities. Its responses must match a correct queue, and synthesis sets its clock rate. To pass, it must beat the human reference on operations per second at every configuration. Its worst response latency must be no longer.
Wenhao Chai discusses this task in the interview.
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 | 26.0 | |
| Claude Opus 5.5 | Solved | 42.2 | $25.91 |
| Gemini 4 Argon | Solved | 37.4 | $44.79 |
| GPT-6.1 Sol | Solved | 36.7 | $9.64 |
| GPT-6 Astra | Not solved | 40.4 | $83.21 |
| Muse Spark 1.3 | Not solved | 20.2 | $36.90 |
| Kimi K3 | Not solved | 19.0 | $35.76 |
| Muse Wonder 1.0 | Not solved | 17.9 | $16.59 |
| DeepSeek V4.1 Flash | Not solved | 15.5 | $0.08 |
| GLM 5.3 Flash | Not solved | 8.2 | $8.74 |
| GLM 5.3 | Not solved | 0.0 | $23.23 |
| Qwen 3.8 Max | Not solved | 0.0 | $15.07 |
| Step 5 Preview | Not solved | 0.0 | $23.05 |
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 | Latency (ns)lower is better | Throughputhigher is better |
|---|---|---|
| Original code | 37.3 | 2.28×10⁸ |
| Claude Opus 5.5 | 20.7 | 3.71×10⁸ |
| Gemini 4 Argon | 24.1 | 3.28×10⁸ |
| GPT-6.1 Sol | 22 | 3.22×10⁸ |
| GPT-6 Astra | 20.5 | 3.55×10⁸ |
| Muse Spark 1.3 | 37.1 | 1.78×10⁸ |
| Kimi K3 | — | — |
| Muse Wonder 1.0 | 56 | 1.57×10⁸ |
| DeepSeek V4.1 Flash | 41.4 | 1.36×10⁸ |
| GLM 5.3 Flash | — | — |
| GLM 5.3 | — | — |
| Qwen 3.8 Max | — | — |
| Step 5 Preview | — | — |
How Claude Opus 5.5 solved it
- 1.
Every bucket in registers
Each level keeps three registers per bucket: its bit, a flag that says its count is one, and the count. The counter memories go unused, so no step waits on a memory read.
- 2.
One stage per level
In one stage a level finds the first or last set bit of the operation’s row and updates every row at once. A dequeue clears a bit when its flag is set, and the new flag says whether the count was two. The next operation sees the new state a cycle later, so nothing is forwarded.
- 3.
The digit off the loop
The stage also records which bucket the operation hit, one flag per bucket. A later stage ORs these flags across rows into the digit the next level needs, outside the loop between back-to-back operations.
- 4.
Wide trees
A bottom level of more than 1,024 buckets keeps its rows in a register file instead. It reads the operation’s row, takes the row of the operation just ahead when they match, decides and writes back. Trees of more than 8,192 priorities are not served.
Task and results from frontier-cs.org, as of October 20, 2026.