FA-11886 / Search retrieval semantics / Open access

Prefix expansion applies its budget before finding matching terms · case 01

Prefix expansion applies its budget before finding matching terms.

Verified by executionVariant 1 · 7 checks per implementationDownload source bundle ↓JSON ↗

ROOT CAUSE

The dictionary is truncated before the prefix range is selected.

VERIFIED REPAIR

Deduplicate the dictionary, select terms beginning with the prefix, then choose lexical first k.

Unsuccessful approach: Substring matching admits terms whose interior contains the query prefix.

Case contract

For an arbitrary token dictionary return at most k distinct lexical terms beginning with prefix. Empty prefix matches all terms; k is nonnegative.

Why this case matters

An offline deterministic retrieval model isolates this search contract from tokenization, storage, and network behavior.

1 / The failure

Exit 1

"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(terms, prefix, k):
    return [t for t in sorted(set(terms))[:k] if t.startswith(prefix)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
p='z'+str(N)
check('matching terms past budget', solve(['a','b',p+'b',p+'a'],p,1),[p+'a'])
check('interior false match', solve(['a'+p,p+'x'],p,3),[p+'x'])
check('duplicate dictionary entries', solve([p,p,p+'x'],p,3),[p,p+'x'])
check('empty prefix', solve(['b','a'],'',2),['a','b'])
check('zero budget', solve([p],p,0),[])
check('empty dictionary', solve([],p,3),[])
check('exact token is prefix match', solve([p],p,1),[p])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

Boundary fixture	Actual	Expected	Outcome
matching terms past budget	`[]`	`['z1a']`	Failed
interior false match	`['z1x']`	`['z1x']`	Passed
duplicate dictionary entries	`['z1', 'z1x']`	`['z1', 'z1x']`	Passed
empty prefix	`['a', 'b']`	`['a', 'b']`	Passed
zero budget	`[]`	`[]`	Passed
empty dictionary	`[]`	`[]`	Passed
exact token is prefix match	`['z1']`	`['z1']`	Passed

SHA-256 / 0efd9ac2d9a2a770212ae74e35604ed093dd2841f43381d2194c651913e7c3f1

2 / The unsuccessful fix

Exit 1

"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(terms, prefix, k):
    return sorted({t for t in terms if prefix in t})[:k]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
p='z'+str(N)
check('matching terms past budget', solve(['a','b',p+'b',p+'a'],p,1),[p+'a'])
check('interior false match', solve(['a'+p,p+'x'],p,3),[p+'x'])
check('duplicate dictionary entries', solve([p,p,p+'x'],p,3),[p,p+'x'])
check('empty prefix', solve(['b','a'],'',2),['a','b'])
check('zero budget', solve([p],p,0),[])
check('empty dictionary', solve([],p,3),[])
check('exact token is prefix match', solve([p],p,1),[p])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

Boundary fixture	Actual	Expected	Outcome
matching terms past budget	`['z1a']`	`['z1a']`	Passed
interior false match	`['az1', 'z1x']`	`['z1x']`	Failed
duplicate dictionary entries	`['z1', 'z1x']`	`['z1', 'z1x']`	Passed
empty prefix	`['a', 'b']`	`['a', 'b']`	Passed
zero budget	`[]`	`[]`	Passed
empty dictionary	`[]`	`[]`	Passed
exact token is prefix match	`['z1']`	`['z1']`	Passed

SHA-256 / 566905450a9acae9aaa06c4937b6246364e985141081bfe048b4b0d7ac66a955

3 / The verified repair

Exit 0

"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(terms, prefix, k):
    return sorted({t for t in terms if t.startswith(prefix)})[:k]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
p='z'+str(N)
check('matching terms past budget', solve(['a','b',p+'b',p+'a'],p,1),[p+'a'])
check('interior false match', solve(['a'+p,p+'x'],p,3),[p+'x'])
check('duplicate dictionary entries', solve([p,p,p+'x'],p,3),[p,p+'x'])
check('empty prefix', solve(['b','a'],'',2),['a','b'])
check('zero budget', solve([p],p,0),[])
check('empty dictionary', solve([],p,3),[])
check('exact token is prefix match', solve([p],p,1),[p])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

Boundary fixture	Actual	Expected	Outcome
matching terms past budget	`['z1a']`	`['z1a']`	Passed
interior false match	`['z1x']`	`['z1x']`	Passed
duplicate dictionary entries	`['z1', 'z1x']`	`['z1', 'z1x']`	Passed
empty prefix	`['a', 'b']`	`['a', 'b']`	Passed
zero budget	`[]`	`[]`	Passed
empty dictionary	`[]`	`[]`	Passed
exact token is prefix match	`['z1']`	`['z1']`	Passed

SHA-256 / 0681876d2c6c9b74e323ec4e7bd7dbfad3abd838fca1a6eb94c5f041675f99ce

Verification & scope

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.

Observations recorded using Python 3.12.14 at 2026-09-29T14:38:51.807646+00:00.

Case digest / 1c92f71a673ff4a220eafc6ea25f282bedc117e530abc42dac49ef1e861f0d77