python-beam-search-batch-length-norm
Done. The solution is written to ~/SOLUTION.md and backed by working, verified code.
Deliverable files
- SOLUTION.md — the self-contained writeup (title, root-cause analysis, exact fix, verification, tuning knobs). The two code blocks inside it are byte-identical to the working files below and execute end-to-end.
- beam_search.py — the fix: batch_beam_search(...) (batched, GNMT length normalization, EOS-ejects-from-beam + refill, deterministic generation-ordinal tie-break, top-k sorted by normalized score, early finishers retained).
- verify_beam_search.py — single-file executable proof (reference + randomized equivalence + crafted cases + property checks + 3 deliberately broken decoders).
- test_beam_search.py — the fuller differential harness used during diagnosis (500 random trials, 100 determinism runs).
Root cause — the spec is violated by naive decoders in four classic ways, each reproduced and caught:
- A early-stopping when the finished list fills, losing better late finishers;
- B dropping hypotheses that finished before the last step ("finished before the beam filled" must be retained);
- C ranking by raw cumulative log-prob, ignoring length**alpha (must be applied at every step, GNMT-style);
- D non-deterministic / non-input-order tie-breaking.
Verification (python3 verify_beam_search.py → exit 0):
correct batch_beam_search PASS (should pass)
bug A stop-when-finished-fills PASS (deliberately buggy - must be caught)
bug B drop-early-finishers PASS (deliberately buggy - must be caught)
bug C raw-score-no-length-norm PASS (deliberately buggy - must be caught)
OVERALL: PASS
alpha=0 vs 2 winner flip, immediate EOS, ties, k-truncation, empty batch, max_len=0), and model-recomputed normalized-score/ordering/EOS properties all pass — and the same harness rejects all three injected bugs (117–287 mismatches each).Code is 3.11-compatible (stdlib only, from __future__ import annotations); verified on Python 3.14.4 here since no 3.11 binary was available. Note the documented semantics choices (rangeable knobs): partial-beam ranking uses the normalized score (GNMT), len includes EOS, and non-EOS partials at max_len are force-finished by default.
# Evidence - Problem class: python-beam-search-batch-length-norm - Model: openrouter/deepseek/deepseek-v4-flash-0731 - Solved: 2026-08-31T16:40:52.902Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement batched beam search decoding with GNMT-style length normalization (score = cumulative log-prob / length**alpha). Finished (EOS-terminated) hypotheses must leave the active beam and be collected as candidates while the beam refills from remaining partials, with deterministic tie-breaking by input order. Return the top-k complete hypotheses sorted by normalized score, including sequences that finished before the beam filled.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4-flash-0731", "problem_class": "python-beam-search-batch-length-norm", "provider": "openrouter", "solved_at": "2026-08-31T16:40:52.902Z", "version": "3.11"}Done. The solution is written to ~/SOLUTION.md and backed by working, verified code.
Deliverable files
- SOLUTION.md — the self-contained writeup (title, root-cause analysis, exact fix, verification, tuning knobs). The two code blocks inside it are byte-identical to the working files below and execute end-to-end.
- beam_search.py — the fix: batch_beam_search(...) (batched, GNMT length normalization, EOS-ejects-from-beam + refill, deterministic generation-ordinal tie-break, top-k sorted by normalized score, early finishers retained).
- verify_beam_search.py — single-file executable proof (reference + randomized equivalence + crafted cases + property checks + 3 deliberately broken decoders).
- test_beam_search.py — the fuller differential harness used during diagnosis (500 random trials, 100 determinism runs).
Root cause — the spec is violated by naive decoders in four classic ways, each reproduced and caught:
- A early-stopping when the finished list fills, losing better late finishers;
- B dropping hypotheses that finished before the last step ("finished before the beam filled" must be retained);
- C ranking by raw cumulative log-prob, ignoring length**alpha (must be applied at every step, GNMT-style);
- D non-deterministic / non-input-order tie-breaking.
Verification (python3 verify_beam_search.py → exit 0):
correct batch_beam_search PASS (should pass)
bug A stop-when-finished-fills PASS (deliberately buggy - must be caught)
bug B drop-early-finishers PASS (deliberately buggy - must be caught)
bug C raw-score-no-length-norm PASS (deliberately buggy - must be caught)
OVERALL: PASS
alpha=0 vs 2 winner flip, immediate EOS, ties, k-truncation, empty batch, max_len=0), and model-recomputed normalized-score/ordering/EOS properties all pass — and the same harness rejects all three injected bugs (117–287 mismatches each).Code is 3.11-compatible (stdlib only, from __future__ import annotations); verified on Python 3.14.4 here since no 3.11 binary was available. Note the documented semantics choices (rangeable knobs): partial-beam ranking uses the normalized score (GNMT), len includes EOS, and non-EOS partials at max_len are force-finished by default.
# Evidence - Problem class: python-beam-search-batch-length-norm - Model: openrouter/deepseek/deepseek-v4-flash-0731 - Solved: 2026-08-31T16:40:52.902Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement batched beam search decoding with GNMT-style length normalization (score = cumulative log-prob / length**alpha). Finished (EOS-terminated) hypotheses must leave the active beam and be collected as candidates while the beam refills from remaining partials, with deterministic tie-breaking by input order. Return the top-k complete hypotheses sorted by normalized score, including sequences that finished before the beam filled.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4-flash-0731", "problem_class": "python-beam-search-batch-length-norm", "provider": "openrouter", "solved_at": "2026-08-31T16:40:52.902Z", "version": "3.11"}