{"abstract":"Prefix expansion applies its budget before finding matching terms.","category":"Search retrieval semantics","checks":7,"contract":"For an arbitrary token dictionary return at most k distinct lexical terms beginning with prefix. Empty prefix matches all terms; k is nonnegative.","evaluation_group":"model-dd9b73732092e450","failed_approach":"Substring matching admits terms whose interior contains the query prefix.","family":"z-search-prefix-dictionary-expansion","id":"FA-11886","implementations":{"attempt":{"sha256":"566905450a9acae9aaa06c4937b6246364e985141081bfe048b4b0d7ac66a955","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(terms, prefix, k):\n    return sorted({t for t in terms if prefix in t})[:k]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\np='z'+str(N)\ncheck('matching terms past budget', solve(['a','b',p+'b',p+'a'],p,1),[p+'a'])\ncheck('interior false match', solve(['a'+p,p+'x'],p,3),[p+'x'])\ncheck('duplicate dictionary entries', solve([p,p,p+'x'],p,3),[p,p+'x'])\ncheck('empty prefix', solve(['b','a'],'',2),['a','b'])\ncheck('zero budget', solve([p],p,0),[])\ncheck('empty dictionary', solve([],p,3),[])\ncheck('exact token is prefix match', solve([p],p,1),[p])\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":"0efd9ac2d9a2a770212ae74e35604ed093dd2841f43381d2194c651913e7c3f1","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(terms, prefix, k):\n    return [t for t in sorted(set(terms))[:k] if t.startswith(prefix)]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\np='z'+str(N)\ncheck('matching terms past budget', solve(['a','b',p+'b',p+'a'],p,1),[p+'a'])\ncheck('interior false match', solve(['a'+p,p+'x'],p,3),[p+'x'])\ncheck('duplicate dictionary entries', solve([p,p,p+'x'],p,3),[p,p+'x'])\ncheck('empty prefix', solve(['b','a'],'',2),['a','b'])\ncheck('zero budget', solve([p],p,0),[])\ncheck('empty dictionary', solve([],p,3),[])\ncheck('exact token is prefix match', solve([p],p,1),[p])\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":"0681876d2c6c9b74e323ec4e7bd7dbfad3abd838fca1a6eb94c5f041675f99ce","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(terms, prefix, k):\n    return sorted({t for t in terms if t.startswith(prefix)})[:k]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\np='z'+str(N)\ncheck('matching terms past budget', solve(['a','b',p+'b',p+'a'],p,1),[p+'a'])\ncheck('interior false match', solve(['a'+p,p+'x'],p,3),[p+'x'])\ncheck('duplicate dictionary entries', solve([p,p,p+'x'],p,3),[p,p+'x'])\ncheck('empty prefix', solve(['b','a'],'',2),['a','b'])\ncheck('zero budget', solve([p],p,0),[])\ncheck('empty dictionary', solve([],p,3),[])\ncheck('exact token is prefix match', solve([p],p,1),[p])\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":"Inputs are already tokenized or scored; this model makes no claim about production engine performance or linguistic analysis. 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":"z-search-prefix-dictionary-expansion","generated_at":"2026-09-29T14:38:51.807646+00:00","license":"CC0-1.0","python":"3.12.14","seed":1,"split":"open-access"},"relevance":"An offline deterministic retrieval model isolates this search contract from tokenization, storage, and network behavior.","repair":"Deduplicate the dictionary, select terms beginning with the prefix, then choose lexical first k.","root_cause":"The dictionary is truncated before the prefix range is selected.","sha256":"1c92f71a673ff4a220eafc6ea25f282bedc117e530abc42dac49ef1e861f0d77","title":"Prefix expansion applies its budget before finding matching terms · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verification":{"attempt":{"elapsed_ms":39.508,"exit_code":1,"observations":[{"actual":["z1a"],"check":"matching terms past budget","expected":["z1a"],"passed":true},{"actual":["az1","z1x"],"check":"interior false match","expected":["z1x"],"passed":false},{"actual":["z1","z1x"],"check":"duplicate dictionary entries","expected":["z1","z1x"],"passed":true},{"actual":["a","b"],"check":"empty prefix","expected":["a","b"],"passed":true},{"actual":[],"check":"zero budget","expected":[],"passed":true},{"actual":[],"check":"empty dictionary","expected":[],"passed":true},{"actual":["z1"],"check":"exact token is prefix match","expected":["z1"],"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"matching terms past budget\", \"actual\": [\"z1a\"], \"expected\": [\"z1a\"], \"passed\": true}, {\"check\": \"interior false match\", \"actual\": [\"az1\", \"z1x\"], \"expected\": [\"z1x\"], \"passed\": false}, {\"check\": \"duplicate dictionary entries\", \"actual\": [\"z1\", \"z1x\"], \"expected\": [\"z1\", \"z1x\"], \"passed\": true}, {\"check\": \"empty prefix\", \"actual\": [\"a\", \"b\"], \"expected\": [\"a\", \"b\"], \"passed\": true}, {\"check\": \"zero budget\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"empty dictionary\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"exact token is prefix match\", \"actual\": [\"z1\"], \"expected\": [\"z1\"], \"passed\": true}], \"passed\": false}\n"},"broken":{"elapsed_ms":40.947,"exit_code":1,"observations":[{"actual":[],"check":"matching terms past budget","expected":["z1a"],"passed":false},{"actual":["z1x"],"check":"interior false match","expected":["z1x"],"passed":true},{"actual":["z1","z1x"],"check":"duplicate dictionary entries","expected":["z1","z1x"],"passed":true},{"actual":["a","b"],"check":"empty prefix","expected":["a","b"],"passed":true},{"actual":[],"check":"zero budget","expected":[],"passed":true},{"actual":[],"check":"empty dictionary","expected":[],"passed":true},{"actual":["z1"],"check":"exact token is prefix match","expected":["z1"],"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"matching terms past budget\", \"actual\": [], \"expected\": [\"z1a\"], \"passed\": false}, {\"check\": \"interior false match\", \"actual\": [\"z1x\"], \"expected\": [\"z1x\"], \"passed\": true}, {\"check\": \"duplicate dictionary entries\", \"actual\": [\"z1\", \"z1x\"], \"expected\": [\"z1\", \"z1x\"], \"passed\": true}, {\"check\": \"empty prefix\", \"actual\": [\"a\", \"b\"], \"expected\": [\"a\", \"b\"], \"passed\": true}, {\"check\": \"zero budget\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"empty dictionary\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"exact token is prefix match\", \"actual\": [\"z1\"], \"expected\": [\"z1\"], \"passed\": true}], \"passed\": false}\n"},"fixed":{"elapsed_ms":38.133,"exit_code":0,"observations":[{"actual":["z1a"],"check":"matching terms past budget","expected":["z1a"],"passed":true},{"actual":["z1x"],"check":"interior false match","expected":["z1x"],"passed":true},{"actual":["z1","z1x"],"check":"duplicate dictionary entries","expected":["z1","z1x"],"passed":true},{"actual":["a","b"],"check":"empty prefix","expected":["a","b"],"passed":true},{"actual":[],"check":"zero budget","expected":[],"passed":true},{"actual":[],"check":"empty dictionary","expected":[],"passed":true},{"actual":["z1"],"check":"exact token is prefix match","expected":["z1"],"passed":true}],"passed":true,"stderr":"","stdout":"{\"observations\": [{\"check\": \"matching terms past budget\", \"actual\": [\"z1a\"], \"expected\": [\"z1a\"], \"passed\": true}, {\"check\": \"interior false match\", \"actual\": [\"z1x\"], \"expected\": [\"z1x\"], \"passed\": true}, {\"check\": \"duplicate dictionary entries\", \"actual\": [\"z1\", \"z1x\"], \"expected\": [\"z1\", \"z1x\"], \"passed\": true}, {\"check\": \"empty prefix\", \"actual\": [\"a\", \"b\"], \"expected\": [\"a\", \"b\"], \"passed\": true}, {\"check\": \"zero budget\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"empty dictionary\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"exact token is prefix match\", \"actual\": [\"z1\"], \"expected\": [\"z1\"], \"passed\": true}], \"passed\": true}\n"}},"verified":true,"visibility":"public"}