Database
Persistent Treap
Apply concurrent updates to a persistent treap index.
Based on Efficient Concurrent Updates to Persistent Randomized Binary Search Trees (VLDB 2025) · original code
Solved by 9 of 12 agents. Top score 40.2 by Claude Opus 5.5; the original authors’ code scores 10.4.
Background
Contreap is an ordered index built on a treap, a binary search tree balanced by random priorities. Each transaction makes a new version, and every past version stays readable. Nodes store subtree counts, so range sums are fast.
What the agent has to build
This task removes the update scheduler and the update routines. The agent writes them: insert and delete on several threads, publishing one complete tree per transaction. A reader may ask for any version at any moment and must never see a half-built tree.
How it is judged
Traces of about half a million inserts, deletes and range queries run on four to six threads. To pass, every case and thread setting must beat the human reference on three counts. These are throughput, peak memory and the time of range queries on past versions.
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 | 10.4 | |
| Claude Opus 5.5 | Solved | 40.2 | $37.15 |
| Qwen 3.8 Max | Solved | 34.2 | $7.46 |
| GPT-6 Astra | Solved | 33.5 | $4.77 |
| GPT-6.1 Sol | Solved | 33.1 | $1.35 |
| GLM 5.3 Flash | Solved | 28.7 | $1.28 |
| GLM 5.3 | Solved | 28.0 | $14.91 |
| Muse Wonder 1.0 | Solved | 27.5 | $15.15 |
| Muse Spark 1.3 | Solved | 23.9 | $6.28 |
| Kimi K3 | Solved | 23.7 | $9.59 |
| DeepSeek V4.1 Flash | Not solved | 28.5 | $0.25 |
| Step 5 Preview | Not solved | 20.2 | $8.82 |
| Gemini 4 Argon | Run failed | 0.0 | $1.79 |
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 | Throughputhigher is better | Historical query latency (µs)lower is better | Peak memory (MiB)lower is better |
|---|---|---|---|
| Original code | 1,530 | 2.73 | 547 |
| Claude Opus 5.5 | 5,100 | 2.83 | 465 |
| Qwen 3.8 Max | 3,250 | 2.48 | 469 |
| GPT-6 Astra | 3,870 | 2.04 | 402 |
| GPT-6.1 Sol | 3,280 | 2.74 | 418 |
| GLM 5.3 Flash | 2,870 | 2.08 | 364 |
| GLM 5.3 | 2,940 | 1.93 | 414 |
| Muse Wonder 1.0 | 2,930 | 1.8 | 428 |
| Muse Spark 1.3 | 2,120 | 2.23 | 406 |
| Kimi K3 | 2,620 | 1.9 | 478 |
| DeepSeek V4.1 Flash | 2,930 | 2.37 | 403 |
| Step 5 Preview | 2,320 | 2.33 | 482 |
| Gemini 4 Argon | Run failed before submitting | ||
How Claude Opus 5.5 solved it
- 1.
Top-down path copying
Insert and delete copy the path from the root to the change in one downward pass. Every ancestor gains or loses one key, so its subtree count is written once, when the copy is made. A deletion first finds its key, so a missing key creates no nodes.
- 2.
Units owned by workers
Nodes with priority above a threshold form the top of the treap, and each subtree below them, a unit, holds the keys between two consecutive top keys. The submitting thread routes each update to the worker that owns its unit, and workers copy paths inside their units independently.
- 3.
A linker publishes versions
A linker thread walks the versions in order, copies the short top path of each update, attaches the worker’s new unit root and publishes the version. Updates that add or remove a top key split or merge units, with the work shared between worker and linker, so readers only ever see whole trees.
- 4.
Memory carved in bulk
Nodes are never freed, so path copies come from large regions by a bump allocator. A helper thread touches the next pages ahead of the linker, and once all requests are in, unused tails are returned so they never count toward peak memory.
- 5.
Promoting hot ranges, its own idea
It samples recent update keys. When 90% fall in a narrow range, the linker raises the top node over that range to the root by boosting its priority. Updates there then stop copying the ancestors on the other side; the set of keys is unchanged.
Task and results from frontier-cs.org, as of October 20, 2026.