cuckoo-filter-zero-fingerprint-sentinel-false-negative
Done. The verified solution is in ~/SOLUTION.md, with the working implementation in ~/cuckoo_fix.py and tests in ~/test_cuckoo_fix.py.
Root cause. Using 0 as the empty-slot sentinel while storing 8-bit fingerprints in 0..255 creates three failures:
1. A fingerprint of 0 matches every empty slot → false positives; delete() clears free slots.
2. alt = i XOR (fp * 0x5bd1e995) collapses to alt == i when fp == 0, so the key has only one candidate bucket → kicks never reach a second bucket and the insert burns through max_kicks.
3. A subtler bug I caught during verification: the alternate-index map must be an involution (alt(alt(i)) == i). A naive i + K mod n is not, and silently produced 11,674 false negatives.
Fix.
- Remap raw fingerprint 0 → 255 consistently on store, lookup, and delete, so 0 is never a stored value.
- Make alt a fixed-point-free involutive bijection: XOR over a power-of-two table, or i → (K − i) mod nb with K forced odd for the general even bucket count used to hit load 0.95.
- Bound kicks and park a homeless fingerprint in a tiny stash (no livelock, no data loss); delete() only clears when fp != 0 is actually present.
Verification (actual run, 4/4 pass under plain Python and pytest):
- Zero-fp key 834: raw 0 → stored 255, i1=98, i2=777, round-trips and refuses absent deletes.
- 100k keys, load=0.9500, stash=0, 0 false negatives.
- FP rate 0.02976 vs theory 0.03125 = 0.952x (limit 1.5x).
- Empty filter on a fingerprint-0 probe: fixed False, pre-fix True.
- Negative control reproduces both the false positive/delete-on-empty and kick exhaustion (64/64 kicks, insert ok=False, alt(i)==i).
# Evidence - Problem class: cuckoo-filter-zero-fingerprint-sentinel-false-negative - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-09-20T10:43:39.228Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement a cuckoo filter (bucket size 4, 8-bit fingerprints, two candidate buckets, bounded kicks) whose `contains()` must have zero false negatives and whose `insert()` must not livelock. The classic failure is the zero fingerprint: if a key hashes to fingerprint 0, an empty slot (zero-initialised) becomes indistinguishable from a stored fingerprint, so `contains()` returns true for keys that were never inserted and `delete()` can clear an empty slot; worse, the alternate-bucket derivation alt = i XOR (fingerprint * 0x5bd1e995) degenerates to alt == i when the fingerprint is 0, so relocation never reaches a second bucket and insert spins until max_kicks. Ship insert/contains/delete magic that remaps the zero fingerprint to a non-zero reserved value on both store and lookup, keep the alternate-index function bijective, and make delete only succeed when the fingerprint is actually present in one of the two candidate buckets. Prove it with tests for: a key whose fingerprint remaps to 0 still round-trips and deletes; 100k keys at load factor 0.95 give zero false negatives across every inserted key and a measured false-positive rate within 1.5x of the theoretical 2*b/2^f; an empty filter returns false for a probe key whose fingerprint is 0; and a negative-control run against the pre-fix (0..255 fingerprint, no remap) code that reproduces the false positive and the kick exhaustion.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "cuckoo-filter-zero-fingerprint-sentinel-false-negative", "provider": "openrouter", "solved_at": "2026-09-20T10:43:39.233Z", "version": "3.11"}Done. The verified solution is in ~/SOLUTION.md, with the working implementation in ~/cuckoo_fix.py and tests in ~/test_cuckoo_fix.py.
Root cause. Using 0 as the empty-slot sentinel while storing 8-bit fingerprints in 0..255 creates three failures:
1. A fingerprint of 0 matches every empty slot → false positives; delete() clears free slots.
2. alt = i XOR (fp * 0x5bd1e995) collapses to alt == i when fp == 0, so the key has only one candidate bucket → kicks never reach a second bucket and the insert burns through max_kicks.
3. A subtler bug I caught during verification: the alternate-index map must be an involution (alt(alt(i)) == i). A naive i + K mod n is not, and silently produced 11,674 false negatives.
Fix.
- Remap raw fingerprint 0 → 255 consistently on store, lookup, and delete, so 0 is never a stored value.
- Make alt a fixed-point-free involutive bijection: XOR over a power-of-two table, or i → (K − i) mod nb with K forced odd for the general even bucket count used to hit load 0.95.
- Bound kicks and park a homeless fingerprint in a tiny stash (no livelock, no data loss); delete() only clears when fp != 0 is actually present.
Verification (actual run, 4/4 pass under plain Python and pytest):
- Zero-fp key 834: raw 0 → stored 255, i1=98, i2=777, round-trips and refuses absent deletes.
- 100k keys, load=0.9500, stash=0, 0 false negatives.
- FP rate 0.02976 vs theory 0.03125 = 0.952x (limit 1.5x).
- Empty filter on a fingerprint-0 probe: fixed False, pre-fix True.
- Negative control reproduces both the false positive/delete-on-empty and kick exhaustion (64/64 kicks, insert ok=False, alt(i)==i).
# Evidence - Problem class: cuckoo-filter-zero-fingerprint-sentinel-false-negative - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-09-20T10:43:39.228Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement a cuckoo filter (bucket size 4, 8-bit fingerprints, two candidate buckets, bounded kicks) whose `contains()` must have zero false negatives and whose `insert()` must not livelock. The classic failure is the zero fingerprint: if a key hashes to fingerprint 0, an empty slot (zero-initialised) becomes indistinguishable from a stored fingerprint, so `contains()` returns true for keys that were never inserted and `delete()` can clear an empty slot; worse, the alternate-bucket derivation alt = i XOR (fingerprint * 0x5bd1e995) degenerates to alt == i when the fingerprint is 0, so relocation never reaches a second bucket and insert spins until max_kicks. Ship insert/contains/delete magic that remaps the zero fingerprint to a non-zero reserved value on both store and lookup, keep the alternate-index function bijective, and make delete only succeed when the fingerprint is actually present in one of the two candidate buckets. Prove it with tests for: a key whose fingerprint remaps to 0 still round-trips and deletes; 100k keys at load factor 0.95 give zero false negatives across every inserted key and a measured false-positive rate within 1.5x of the theoretical 2*b/2^f; an empty filter returns false for a probe key whose fingerprint is 0; and a negative-control run against the pre-fix (0..255 fingerprint, no remap) code that reproduces the false positive and the kick exhaustion.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "cuckoo-filter-zero-fingerprint-sentinel-false-negative", "provider": "openrouter", "solved_at": "2026-09-20T10:43:39.233Z", "version": "3.11"}