FA-98536 / Beam search bookkeeping / Open access

Beam search: beam stopping ignores the best normalized score a live path can still reach · case 01

beam stopping ignores the best normalized score a live path can still reach.

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

ROOT CAUSE

The stop check compares current live totals with finished scores, although a negative total becomes less negative under the configured length normalization as the path grows.

THE FAILURE

The stop check compares current live totals with finished scores, although a negative total becomes less negative under the configured length normalization as the path grows.

Unsuccessful approach: Normalizing at the current length still stops too early when a live path can improve its normalized rank by extending.

Case contract

Scores are nonpositive upper bounds on cumulative log scores; future token contributions cannot increase them. Active rows are [score_bound,current_generated_length], finished contains already-normalized final scores, width is positive, and max_length is at least each active length. The length factor is 1+alpha*(length-1), alpha>=0. Stop if there are no active paths, or at least width finished paths exist and the best active upper bound normalized at max_length is no better than the width-th best finished score.

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(active, finished, width, max_length, alpha):
    return bool(finished) and max((score for score,length in active),default=float('-inf'))<=max(finished)
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('extension can improve rank',solve([[-3,1]],[-1,-2],2,4,1),False)
check('bounded below kth result',solve([[-10*N,1]],[-N,-2*N],2,4,1),True)
check('pool short of requested width',solve([[-10,1]],[-1],2,4,1),False)
check('empty live set is complete',solve([],[],1,4,1),True)
check('exact optimistic tie can stop',solve([[-4,1]],[-1],1,3,1),True)
check('current length is not the cap',solve([[-1,2]],[-0.5],1,4,1),False)
check('already at maximum length',solve([[-2,4]],[-0.5],1,4,1),True)
check('zero penalty factor',solve([[-1,1]],[-2],1,4,0),False)
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
extension can improve rank	`True`	`False`	Failed
bounded below kth result	`True`	`True`	Passed
pool short of requested width	`True`	`False`	Failed
empty live set is complete	`False`	`True`	Failed
exact optimistic tie can stop	`True`	`True`	Passed
current length is not the cap	`True`	`False`	Failed
already at maximum length	`True`	`True`	Passed
zero penalty factor	`False`	`False`	Passed

SHA-256 / fc1c405e631120e0735356465c6d8c334f2aae054fb87de1597e9b465026ed8b

2 / The unsuccessful fix

Exit 1

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

N = 1
observations = []
def solve(active, finished, width, max_length, alpha):
    if not active: return True
    if len(finished)<width: return False
    threshold=sorted(finished,reverse=True)[width-1]
    return max(score/(1+alpha*(length-1)) for score,length in active)<=threshold
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('extension can improve rank',solve([[-3,1]],[-1,-2],2,4,1),False)
check('bounded below kth result',solve([[-10*N,1]],[-N,-2*N],2,4,1),True)
check('pool short of requested width',solve([[-10,1]],[-1],2,4,1),False)
check('empty live set is complete',solve([],[],1,4,1),True)
check('exact optimistic tie can stop',solve([[-4,1]],[-1],1,3,1),True)
check('current length is not the cap',solve([[-1,2]],[-0.5],1,4,1),False)
check('already at maximum length',solve([[-2,4]],[-0.5],1,4,1),True)
check('zero penalty factor',solve([[-1,1]],[-2],1,4,0),False)
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
extension can improve rank	`True`	`False`	Failed
bounded below kth result	`True`	`True`	Passed
pool short of requested width	`False`	`False`	Passed
empty live set is complete	`True`	`True`	Passed
exact optimistic tie can stop	`True`	`True`	Passed
current length is not the cap	`True`	`False`	Failed
already at maximum length	`True`	`True`	Passed
zero penalty factor	`False`	`False`	Passed

SHA-256 / 94aac97190ba247a490c2cfba3a75539f92ffa5a4ed6e56006feb2085960793b

HELD IN THE MEMBER ARCHIVE

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

This mechanism has 8 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:14.106818+00:00.

Case digest / fa62a7d4ecc8a72a4b9611940644e83ddabfbd4e8759defa6eda2ec919c7f5a3