FA-98506 / Beam search bookkeeping / Open access

Beam search: equal beam scores depend on incidental input order · case 01

equal beam scores depend on incidental input order.

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

ROOT CAUSE

No deterministic secondary ordering is used for score ties.

THE FAILURE

No deterministic secondary ordering is used for score ties.

Unsuccessful approach: Sorting only by token leaves ties dependent on parent insertion order.

Case contract

Rows [score,id] sort by descending score then ascending identifier.

Why this case matters

Beam decoders rely on consistent hypothesis state while expanding and ranking candidates.

1 / The failure

Exit 1

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

N = 1
observations = []
def solve(rows):
    return sorted(rows,key=lambda r:-r[0])
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('reverse input tie',solve([[N,'z'],[N,'a']]),[[N,'a'],[N,'z']])
check('score before name',solve([[N,'a'],[N+1,'z']]),[[N+1,'z'],[N,'a']])
check('already ordered',solve([[2,'a'],[1,'b']]),[[2,'a'],[1,'b']])
check('empty candidates',solve([]),[])
check('single candidate',solve([[N,'x']]),[[N,'x']])
check('three tie order',solve([[0,'c'],[0,'b'],[0,'a']]),[[0,'a'],[0,'b'],[0,'c']])
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
reverse input tie	`[[1, 'z'], [1, 'a']]`	`[[1, 'a'], [1, 'z']]`	Failed
score before name	`[[2, 'z'], [1, 'a']]`	`[[2, 'z'], [1, 'a']]`	Passed
already ordered	`[[2, 'a'], [1, 'b']]`	`[[2, 'a'], [1, 'b']]`	Passed
empty candidates	`[]`	`[]`	Passed
single candidate	`[[1, 'x']]`	`[[1, 'x']]`	Passed
three tie order	`[[0, 'c'], [0, 'b'], [0, 'a']]`	`[[0, 'a'], [0, 'b'], [0, 'c']]`	Failed

SHA-256 / 52dcc90abf9e355104b27d9bb7a1d84ec0248116fe38c6e1602619661b0a31be

2 / The unsuccessful fix

Exit 1

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

N = 1
observations = []
def solve(rows):
    return sorted(rows,key=lambda r:(-r[0],tuple(-ord(c) for c in r[1])))
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('reverse input tie',solve([[N,'z'],[N,'a']]),[[N,'a'],[N,'z']])
check('score before name',solve([[N,'a'],[N+1,'z']]),[[N+1,'z'],[N,'a']])
check('already ordered',solve([[2,'a'],[1,'b']]),[[2,'a'],[1,'b']])
check('empty candidates',solve([]),[])
check('single candidate',solve([[N,'x']]),[[N,'x']])
check('three tie order',solve([[0,'c'],[0,'b'],[0,'a']]),[[0,'a'],[0,'b'],[0,'c']])
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
reverse input tie	`[[1, 'z'], [1, 'a']]`	`[[1, 'a'], [1, 'z']]`	Failed
score before name	`[[2, 'z'], [1, 'a']]`	`[[2, 'z'], [1, 'a']]`	Passed
already ordered	`[[2, 'a'], [1, 'b']]`	`[[2, 'a'], [1, 'b']]`	Passed
empty candidates	`[]`	`[]`	Passed
single candidate	`[[1, 'x']]`	`[[1, 'x']]`	Passed
three tie order	`[[0, 'c'], [0, 'b'], [0, 'a']]`	`[[0, 'a'], [0, 'b'], [0, 'c']]`	Failed

SHA-256 / 526845696bd3b99d7accc4e661488f73479f1bc8345971c360cbd7b7a2b5c40c

HELD IN THE MEMBER ARCHIVE

The verified repair and its recorded checks are member-only.

This mechanism has 6 recorded checks per implementation. The open-access tier publishes the failure and the unsuccessful fix; the repaired source that passes every check, and the observations that prove it, are available to members.

Every case sharing this mechanism uses the same contract and the same repair, so this one record is held back for all of them.

Member access is invitation-based. Sign in with your invited account to inspect the repair.

Verification & scope

This is a finite toy beam-state contract and makes no claim about neural model quality or production decoding. 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-30T16:48:13.668771+00:00.

Case digest / f4e3345114e6e8d6921e38840700a943642f325b3f166eb02974c8f938411b07