Theory
Binary Fuse Filter
Write the construction of a binary fuse filter.
Based on Binary Fuse Filters: Fast and Smaller Than Xor Filters (ACM JEA 2022) · original code
Solved by 2 of 12 agents. Top score 57.2 by Claude Opus 5.5; the original authors’ code scores 50.
Background
A binary fuse filter tells whether a key belongs to a fixed set. It never misses a stored key and rarely accepts an absent one. A lookup reads three slots of one array and XORs them. It accepts the key if the result equals the key’s fingerprint, a short hash.
What the agent has to build
This task removes construction, the step that fills the array. The agent writes it for 8-bit and 16-bit fingerprints, so every stored key’s three slots XOR to its fingerprint. It may also reshape the filter and its lookup.
How it is judged
Filters hold 10,000 to 1,000,000 keys and answer streams with different shares of stored keys. To pass, every workload must beat the human reference on memory, construction time and lookup time. The false-positive rate and space overhead must not be measurably worse.
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 | 57.2 | $35.16 |
| GPT-6 Astra | Solved | 52.8 | $10.82 |
| GPT-6.1 Sol | Not solved | 53.9 | $2.38 |
| Muse Wonder 1.0 | Not solved | 53.0 | $14.41 |
| GLM 5.3 | Not solved | 52.9 | $15.35 |
| GLM 5.3 Flash | Not solved | 51.4 | $1.50 |
| Qwen 3.8 Max | Not solved | 50.9 | $10.27 |
| DeepSeek V4.1 Flash | Not solved | 50.6 | $0.12 |
| Kimi K3 | Not solved | 50.4 | $9.67 |
| Gemini 4 Argon | Not solved | 50.1 | $4.13 |
| Step 5 Preview | Not solved | 49.4 | $8.81 |
| Muse Spark 1.3 | Not solved | 49.2 | $7.37 |
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 | Build time (ms)lower is better | False-positive ratelower is better | Lookup time (ns)lower is better | Memory (KiB)lower is better | Space overhead (%)lower is better |
|---|---|---|---|---|---|
| Original code | 18.9 | 0.00196 | 4.17 | 616 | 19.1 |
| Claude Opus 5.5 | 9.24 | 0.00196 | 3.56 | 616 | 19.2 |
| GPT-6 Astra | 14.6 | 0.00196 | 3.81 | 616 | 19.3 |
| GPT-6.1 Sol | 14.9 | 0.00196 | 3.08 | 616 | 19 |
| Muse Wonder 1.0 | 16.5 | 0.00197 | 3.48 | 616 | 19.7 |
| GLM 5.3 | 18.2 | 0.00197 | 3.63 | 615 | 19.1 |
| GLM 5.3 Flash | 16.8 | 0.00196 | 3.42 | 615 | 17.7 |
| Qwen 3.8 Max | 22.6 | 0.00196 | 5.15 | 615 | 18.7 |
| DeepSeek V4.1 Flash | 22.8 | 0.00196 | 3.3 | 616 | 19.1 |
| Kimi K3 | 15.8 | 0.00196 | 3.84 | 616 | 19.2 |
| Gemini 4 Argon | 19 | 0.00196 | 4.1 | 616 | 19.1 |
| Step 5 Preview | 16 | 0.00196 | 3.74 | 616 | 19 |
| Muse Spark 1.3 | 36.7 | 0.00196 | 4 | 611 | 17.3 |
How Claude Opus 5.5 solved it
- 1.
Hash and layout
Each key is multiplied by a random odd seed, and the halves of the 128-bit product are folded together. The high half picks the first slot, and the second and third slots lie in the next two segments. The fingerprint comes from independent bits of the same product, and the filter stores fewer fields, which saves memory.
- 2.
Counting and peeling
Each attempt records, for every slot, how many keys use it and the XOR of their hashes. A slot with one key identifies that key, which is then removed from its other two slots. A queue records the order in which keys are peeled, and is filled without branches so the processor can overlap the work.
- 3.
Segment by segment
Large key sets are first grouped by the segment of their first slot. A segment is complete once its group has been added, so peeling runs right behind the adding, segment by segment, while the data is still in cache. Incomplete segments carry a large extra count so they cannot look peelable.
- 4.
Assigning fingerprints
In reverse peeling order, each key’s peeled slot gets the value that makes the XOR of its three slots equal its fingerprint. The key’s other two slots are already final at that point. Large tables prefetch the next keys’ slots ahead of use.
- 5.
Repeated keys
Repeated keys can never be peeled, but checking for them is slow. It checks only when a failed attempt leaves a slot whose two keys have equal hashes, or after a few failures. It then sorts the keys, removes duplicates and tries a new seed.
Task and results from frontier-cs.org, as of October 20, 2026.