{"abstract":"Insertion order is mistaken for recency, or updating an existing value fails to refresh that recency.","category":"Runtime and resources","checks":7,"contract":"Events are ['put',key,value] or ['get',key]; keys are strings and capacity is nonnegative. A get returns value or None, and only hits refresh recency. Every put refreshes its key. Capacity zero retains nothing. Return [read results,keys ordered least to most recent].","evaluation_group":"model-c8b06dc5d96ad35c","failed_approach":"Refreshing reads alone leaves an overwritten hot entry at the eviction end.","family":"runtime-lru-hit-and-overwrite","id":"FA-261","implementations":{"attempt":{"sha256":"c0134099d058f943b4f8bcf809a31005401c4d8217c4b1e9ce999ea3109b4eb3","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nfrom collections import OrderedDict\nN = 1\nobservations = []\ndef solve(capacity, events):\n    cache, reads = OrderedDict(), []\n    for event in events:\n        kind, key = event[:2]\n        if kind == 'get':\n            reads.append(cache.get(key))\n            if key in cache:\n                cache.move_to_end(key)\n        elif capacity > 0:\n            existed = key in cache\n            cache[key] = event[2]\n            if not existed:\n                cache.move_to_end(key)\n            while len(cache) > capacity:\n                cache.popitem(last=False)\n    return [reads, list(cache)]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\nkeys = ['k'+str(i) for i in range(N+1)]\nputs = [['put', key, i+N] for i, key in enumerate(keys)]\nnew = 'new'\ncheck('hit moves oldest before eviction', solve(N+1, puts+[['get', keys[0]], ['put', new, 99]]), [[N], keys[2:]+[keys[0], new]])\ncheck('overwrite is also recent', solve(N+1, puts+[['put', keys[0], 100], ['put', new, 99]]), [[], keys[2:]+[keys[0], new]])\ncheck('miss leaves recency alone', solve(N+1, puts+[['get', 'absent']]), [[None], keys])\ncheck('zero-capacity cache', solve(0, [['put', 'a', N], ['get', 'a']]), [[None], []])\ncheck('single entry replacement', solve(1, [['put', 'a', N], ['put', 'b', N+1], ['get', 'a'], ['get', 'b']]), [[None, N+1], ['b']])\ncheck('read observes overwrite', solve(1, [['put', 'a', N], ['put', 'a', N+1], ['get', 'a']]), [[N+1], ['a']])\ncheck('empty cache history', solve(N, []), [[], []])\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"},"broken":{"sha256":"f4eeb0d369e92d57698e74e988476fad00d8ac4da1d35426358c2a2479e1ee99","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nfrom collections import OrderedDict\nN = 1\nobservations = []\ndef solve(capacity, events):\n    cache, reads = OrderedDict(), []\n    for event in events:\n        kind, key = event[:2]\n        if kind == 'get':\n            reads.append(cache.get(key))\n            if key in cache:\n                pass\n        elif capacity > 0:\n            existed = key in cache\n            cache[key] = event[2]\n            pass\n            while len(cache) > capacity:\n                cache.popitem(last=False)\n    return [reads, list(cache)]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\nkeys = ['k'+str(i) for i in range(N+1)]\nputs = [['put', key, i+N] for i, key in enumerate(keys)]\nnew = 'new'\ncheck('hit moves oldest before eviction', solve(N+1, puts+[['get', keys[0]], ['put', new, 99]]), [[N], keys[2:]+[keys[0], new]])\ncheck('overwrite is also recent', solve(N+1, puts+[['put', keys[0], 100], ['put', new, 99]]), [[], keys[2:]+[keys[0], new]])\ncheck('miss leaves recency alone', solve(N+1, puts+[['get', 'absent']]), [[None], keys])\ncheck('zero-capacity cache', solve(0, [['put', 'a', N], ['get', 'a']]), [[None], []])\ncheck('single entry replacement', solve(1, [['put', 'a', N], ['put', 'b', N+1], ['get', 'a'], ['get', 'b']]), [[None, N+1], ['b']])\ncheck('read observes overwrite', solve(1, [['put', 'a', N], ['put', 'a', N+1], ['get', 'a']]), [[N+1], ['a']])\ncheck('empty cache history', solve(N, []), [[], []])\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"},"fixed":{"sha256":"2790798c838aa91f59617262bf30abdc6a95b1f2dcac1532d20147b44384696d","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nfrom collections import OrderedDict\nN = 1\nobservations = []\ndef solve(capacity, events):\n    cache, reads = OrderedDict(), []\n    for event in events:\n        kind, key = event[:2]\n        if kind == 'get':\n            reads.append(cache.get(key))\n            if key in cache:\n                cache.move_to_end(key)\n        elif capacity > 0:\n            existed = key in cache\n            cache[key] = event[2]\n            cache.move_to_end(key)\n            while len(cache) > capacity:\n                cache.popitem(last=False)\n    return [reads, list(cache)]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\nkeys = ['k'+str(i) for i in range(N+1)]\nputs = [['put', key, i+N] for i, key in enumerate(keys)]\nnew = 'new'\ncheck('hit moves oldest before eviction', solve(N+1, puts+[['get', keys[0]], ['put', new, 99]]), [[N], keys[2:]+[keys[0], new]])\ncheck('overwrite is also recent', solve(N+1, puts+[['put', keys[0], 100], ['put', new, 99]]), [[], keys[2:]+[keys[0], new]])\ncheck('miss leaves recency alone', solve(N+1, puts+[['get', 'absent']]), [[None], keys])\ncheck('zero-capacity cache', solve(0, [['put', 'a', N], ['get', 'a']]), [[None], []])\ncheck('single entry replacement', solve(1, [['put', 'a', N], ['put', 'b', N+1], ['get', 'a'], ['get', 'b']]), [[None, N+1], ['b']])\ncheck('read observes overwrite', solve(1, [['put', 'a', N], ['put', 'a', N+1], ['get', 'a']]), [[N+1], ['a']])\ncheck('empty cache history', solve(N, []), [[], []])\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"}},"limitations":" This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.","method":"Deterministic executable model with adversarial boundary fixtures.","provenance":{"created_by":"Failure Map","dependencies":"Python standard library","family":"runtime-lru-hit-and-overwrite","generated_at":"2026-09-29T14:36:51.536267+00:00","license":"CC0-1.0","python":"3.12.14","seed":1,"split":"open-access"},"relevance":"Models cache bookkeeping independently of expiration or concurrent locking, covering the difference between recency after a read and recency after replacing an existing value.","repair":"Refresh recency on both successful reads and writes; evict only the least-recent entry after insertion.","root_cause":"Successful accesses and overwrites do not consistently move entries to the most-recent position.","sha256":"a0fecf930a866e1cd351cfa485d57d70a8b8df8133e16bb2aa8118eae05b6e24","title":"A cache evicts the entry it most recently served · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verification":{"attempt":{"elapsed_ms":33.48,"exit_code":1,"observations":[{"actual":[[1],["k0","new"]],"check":"hit moves oldest before eviction","expected":[[1],["k0","new"]],"passed":true},{"actual":[[],["k1","new"]],"check":"overwrite is also recent","expected":[[],["k0","new"]],"passed":false},{"actual":[[null],["k0","k1"]],"check":"miss leaves recency alone","expected":[[null],["k0","k1"]],"passed":true},{"actual":[[null],[]],"check":"zero-capacity cache","expected":[[null],[]],"passed":true},{"actual":[[null,2],["b"]],"check":"single entry replacement","expected":[[null,2],["b"]],"passed":true},{"actual":[[2],["a"]],"check":"read observes overwrite","expected":[[2],["a"]],"passed":true},{"actual":[[],[]],"check":"empty cache history","expected":[[],[]],"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"hit moves oldest before eviction\", \"actual\": [[1], [\"k0\", \"new\"]], \"expected\": [[1], [\"k0\", \"new\"]], \"passed\": true}, {\"check\": \"overwrite is also recent\", \"actual\": [[], [\"k1\", \"new\"]], \"expected\": [[], [\"k0\", \"new\"]], \"passed\": false}, {\"check\": \"miss leaves recency alone\", \"actual\": [[null], [\"k0\", \"k1\"]], \"expected\": [[null], [\"k0\", \"k1\"]], \"passed\": true}, {\"check\": \"zero-capacity cache\", \"actual\": [[null], []], \"expected\": [[null], []], \"passed\": true}, {\"check\": \"single entry replacement\", \"actual\": [[null, 2], [\"b\"]], \"expected\": [[null, 2], [\"b\"]], \"passed\": true}, {\"check\": \"read observes overwrite\", \"actual\": [[2], [\"a\"]], \"expected\": [[2], [\"a\"]], \"passed\": true}, {\"check\": \"empty cache history\", \"actual\": [[], []], \"expected\": [[], []], \"passed\": true}], \"passed\": false}\n"},"broken":{"elapsed_ms":31.38,"exit_code":1,"observations":[{"actual":[[1],["k1","new"]],"check":"hit moves oldest before eviction","expected":[[1],["k0","new"]],"passed":false},{"actual":[[],["k1","new"]],"check":"overwrite is also recent","expected":[[],["k0","new"]],"passed":false},{"actual":[[null],["k0","k1"]],"check":"miss leaves recency alone","expected":[[null],["k0","k1"]],"passed":true},{"actual":[[null],[]],"check":"zero-capacity cache","expected":[[null],[]],"passed":true},{"actual":[[null,2],["b"]],"check":"single entry replacement","expected":[[null,2],["b"]],"passed":true},{"actual":[[2],["a"]],"check":"read observes overwrite","expected":[[2],["a"]],"passed":true},{"actual":[[],[]],"check":"empty cache history","expected":[[],[]],"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"hit moves oldest before eviction\", \"actual\": [[1], [\"k1\", \"new\"]], \"expected\": [[1], [\"k0\", \"new\"]], \"passed\": false}, {\"check\": \"overwrite is also recent\", \"actual\": [[], [\"k1\", \"new\"]], \"expected\": [[], [\"k0\", \"new\"]], \"passed\": false}, {\"check\": \"miss leaves recency alone\", \"actual\": [[null], [\"k0\", \"k1\"]], \"expected\": [[null], [\"k0\", \"k1\"]], \"passed\": true}, {\"check\": \"zero-capacity cache\", \"actual\": [[null], []], \"expected\": [[null], []], \"passed\": true}, {\"check\": \"single entry replacement\", \"actual\": [[null, 2], [\"b\"]], \"expected\": [[null, 2], [\"b\"]], \"passed\": true}, {\"check\": \"read observes overwrite\", \"actual\": [[2], [\"a\"]], \"expected\": [[2], [\"a\"]], \"passed\": true}, {\"check\": \"empty cache history\", \"actual\": [[], []], \"expected\": [[], []], \"passed\": true}], \"passed\": false}\n"},"fixed":{"elapsed_ms":36.941,"exit_code":0,"observations":[{"actual":[[1],["k0","new"]],"check":"hit moves oldest before eviction","expected":[[1],["k0","new"]],"passed":true},{"actual":[[],["k0","new"]],"check":"overwrite is also recent","expected":[[],["k0","new"]],"passed":true},{"actual":[[null],["k0","k1"]],"check":"miss leaves recency alone","expected":[[null],["k0","k1"]],"passed":true},{"actual":[[null],[]],"check":"zero-capacity cache","expected":[[null],[]],"passed":true},{"actual":[[null,2],["b"]],"check":"single entry replacement","expected":[[null,2],["b"]],"passed":true},{"actual":[[2],["a"]],"check":"read observes overwrite","expected":[[2],["a"]],"passed":true},{"actual":[[],[]],"check":"empty cache history","expected":[[],[]],"passed":true}],"passed":true,"stderr":"","stdout":"{\"observations\": [{\"check\": \"hit moves oldest before eviction\", \"actual\": [[1], [\"k0\", \"new\"]], \"expected\": [[1], [\"k0\", \"new\"]], \"passed\": true}, {\"check\": \"overwrite is also recent\", \"actual\": [[], [\"k0\", \"new\"]], \"expected\": [[], [\"k0\", \"new\"]], \"passed\": true}, {\"check\": \"miss leaves recency alone\", \"actual\": [[null], [\"k0\", \"k1\"]], \"expected\": [[null], [\"k0\", \"k1\"]], \"passed\": true}, {\"check\": \"zero-capacity cache\", \"actual\": [[null], []], \"expected\": [[null], []], \"passed\": true}, {\"check\": \"single entry replacement\", \"actual\": [[null, 2], [\"b\"]], \"expected\": [[null, 2], [\"b\"]], \"passed\": true}, {\"check\": \"read observes overwrite\", \"actual\": [[2], [\"a\"]], \"expected\": [[2], [\"a\"]], \"passed\": true}, {\"check\": \"empty cache history\", \"actual\": [[], []], \"expected\": [[], []], \"passed\": true}], \"passed\": true}\n"}},"verified":true,"visibility":"public"}