python-paged-kv-block-table-copy-on-write-prefix-sharing
Done. The verified solution is written to ~/pagedkv/SOLUTION.md, with runnable code in paged_kv.py and verify_paged_kv.py.
Root cause. fork aliases the parent's physical blocks (bumping refcounts) to share the prompt prefix. The appended token usually lands in a partially-filled tail block. If append writes that shared block in place (refcount > 1), it mutates the parent's cached prefix — aliasing corruption. A second failure class is refcount accounting: freeing a block while another table still points at it (or leaking a zero-ref block).
Fix.
- fork copies only the block table + incref per shared block — no token bytes copied.
- append on a partial tail calls _ensure_exclusive: if refcount > 1, allocate a new block, copy the prefix, decref the old block, repoint the table. Full shared tails are left shared (next append allocates fresh).
- Every mutation is guarded by if blk.refcount != 1: raise AliasingError, so any leaked shared write fails loudly.
- _decref clears tokens and returns the block to the free list only when the last reader leaves.
Invariant harness (audit, run after every op) checks three things:
1. refcount == number of live block-table entries (no block freed under a reader),
2. free-list ≡ zero-refcount set (no leaks / double frees),
3. materialized logical tokens == naive contiguous ReferenceCache.
Verification (exit 0):
explicit copy-on-write scenario passed
correct implementation passed 10k ops: {...} (seed=1234)
correct implementation passed 10k ops (seed=7/99/2024/31337)
harness caught buggy implementation: AssertionError: seq 6: cache=[727,484,673,961] ref=[727,484,673,811]
full reclaim OK: 256/256 blocks free, all refcounts zero
The harness was validated against a deliberately buggy NoCoWCache (CoW and write guard disabled) and detected the content divergence, confirming it is not a vacuous test.
# Evidence - Problem class: python-paged-kv-block-table-copy-on-write-prefix-sharing - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-09-21T22:30:48.404Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement a paged KV-cache block manager for LLM serving: a fixed pool of physical blocks addressed through per-sequence block tables, copy-on-write fork for shared prompt prefixes, refcount-tracked allocation and eviction, and block-table indirection so a forked sequence can append without mutating its parent's cached prefix. Ship an invariant harness that detects aliasing corruption when a sequence writes into a block it does not exclusively own. Acceptance: after 10k randomized fork/append/free operations interleaved with prefill and decode requests, every live sequence's logical token contents are byte-identical to a naive contiguous-cache reference, no block is freed while a reader holds it, and refcounts return to zero for every reclaimed block.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "python-paged-kv-block-table-copy-on-write-prefix-sharing", "provider": "openrouter", "solved_at": "2026-09-21T22:30:48.404Z", "version": "3.11"}Done. The verified solution is written to ~/pagedkv/SOLUTION.md, with runnable code in paged_kv.py and verify_paged_kv.py.
Root cause. fork aliases the parent's physical blocks (bumping refcounts) to share the prompt prefix. The appended token usually lands in a partially-filled tail block. If append writes that shared block in place (refcount > 1), it mutates the parent's cached prefix — aliasing corruption. A second failure class is refcount accounting: freeing a block while another table still points at it (or leaking a zero-ref block).
Fix.
- fork copies only the block table + incref per shared block — no token bytes copied.
- append on a partial tail calls _ensure_exclusive: if refcount > 1, allocate a new block, copy the prefix, decref the old block, repoint the table. Full shared tails are left shared (next append allocates fresh).
- Every mutation is guarded by if blk.refcount != 1: raise AliasingError, so any leaked shared write fails loudly.
- _decref clears tokens and returns the block to the free list only when the last reader leaves.
Invariant harness (audit, run after every op) checks three things:
1. refcount == number of live block-table entries (no block freed under a reader),
2. free-list ≡ zero-refcount set (no leaks / double frees),
3. materialized logical tokens == naive contiguous ReferenceCache.
Verification (exit 0):
explicit copy-on-write scenario passed
correct implementation passed 10k ops: {...} (seed=1234)
correct implementation passed 10k ops (seed=7/99/2024/31337)
harness caught buggy implementation: AssertionError: seq 6: cache=[727,484,673,961] ref=[727,484,673,811]
full reclaim OK: 256/256 blocks free, all refcounts zero
The harness was validated against a deliberately buggy NoCoWCache (CoW and write guard disabled) and detected the content divergence, confirming it is not a vacuous test.
# Evidence - Problem class: python-paged-kv-block-table-copy-on-write-prefix-sharing - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-09-21T22:30:48.404Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement a paged KV-cache block manager for LLM serving: a fixed pool of physical blocks addressed through per-sequence block tables, copy-on-write fork for shared prompt prefixes, refcount-tracked allocation and eviction, and block-table indirection so a forked sequence can append without mutating its parent's cached prefix. Ship an invariant harness that detects aliasing corruption when a sequence writes into a block it does not exclusively own. Acceptance: after 10k randomized fork/append/free operations interleaved with prefill and decode requests, every live sequence's logical token contents are byte-identical to a naive contiguous-cache reference, no block is freed while a reader holds it, and refcounts return to zero for every reclaimed block.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "python-paged-kv-block-table-copy-on-write-prefix-sharing", "provider": "openrouter", "solved_at": "2026-09-21T22:30:48.404Z", "version": "3.11"}