FAILURE MAP
← Case archive

FA-73721 / Rate limiter algorithms / Open access

Token bucket with bounded overdraft: no overdraft allowed · case 01

Expensive requests are refused until the bucket fully covers them, starving large callers.

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

ROOT CAUSE

Admission requires the full cost to be available.

VERIFIED REPAIR

Admit whenever the balance is positive and the debt bound holds.

Unsuccessful approach: Admitting at a zero balance lets a client in debt-neutral state overdraw again immediately.

Case contract

Input {capacity, rate (tokens per second), max_debt, requests [[t_s, cost]]} with nondecreasing whole seconds. The bucket starts full; refill is min(capacity, tokens + elapsed*rate) and also repays debt. A request is admitted when the balance is positive and the post-charge balance stays >= -max_debt, so one expensive request may overdraw. Denials change nothing. Return [[decision, balance]].

Why this case matters

Cost-weighted APIs (query units, LLM tokens) let an expensive call overdraw the bucket and repay it from future refill; the overdraft rules decide fairness between cheap and expensive callers.

1 / The failure

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

N = 1
observations = []
def solve(x):
    cap = x['capacity']
    rate = x['rate']
    debt = x['max_debt']
    tokens = cap
    last = 0
    out = []
    for t, cost in x['requests']:
        tokens = min(cap, tokens + (t - last) * rate)
        last = t
        if tokens >= cost and tokens - cost >= -debt:
            tokens -= cost
            out.append(['allow', tokens])
        else:
            out.append(['deny', tokens])
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [5, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 0]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 3]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [3, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 0]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [6, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [22, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[0, 4], [3, 3], [3, 3], [5, 4], [5, 5], [6, 1], [8, 1], [9, 2], [12, 3]]},
   [['allow', 1],
    ['allow', 1],
    ['allow', -2],
    ['deny', 0],
    ['deny', 0],
    ['allow', 0],
    ['allow', 1],
    ['allow', 0],
    ['allow', 0]]]],
 [['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [6, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 1]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 4]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [4, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 1]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [7, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [23, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[0, 4], [2, 1], [2, 2], [3, 5], [6, 1], [7, 4], [9, 5], [10, 2], [11, 4]]},
   [['allow', 1],
    ['allow', 2],
    ['allow', 0],
    ['allow', -4],
    ['deny', -1],
    ['deny', 0],
    ['allow', -3],
    ['deny', -2],
    ['deny', -1]]]],
 [['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [7, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 2]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 5]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [5, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 2]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [8, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [24, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[2, 3], [2, 4], [3, 3], [4, 5], [10, 2], [10, 4], [10, 5], [11, 4], [12, 4]]},
   [['allow', 2],
    ['allow', -2],
    ['deny', -1],
    ['deny', 0],
    ['allow', 3],
    ['allow', -1],
    ['deny', -1],
    ['deny', 0],
    ['allow', -3]]]],
 [['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [8, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 3]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 6]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [6, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 2]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [9, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [25, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[0, 1], [0, 2], [1, 5], [1, 5], [3, 1], [3, 2], [5, 2], [8, 4], [12, 2]]},
   [['allow', 4],
    ['allow', 2],
    ['allow', -2],
    ['deny', -2],
    ['deny', 0],
    ['deny', 0],
    ['allow', 0],
    ['allow', -1],
    ['allow', 1]]]],
 [['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [9, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 3]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 7]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [7, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 2]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [10, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [26, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[1, 5], [3, 3], [3, 3], [5, 1], [5, 3], [7, 3], [8, 1], [8, 5], [12, 1]]},
   [['allow', 0],
    ['allow', -1],
    ['deny', -1],
    ['allow', 0],
    ['deny', 0],
    ['allow', -1],
    ['deny', 0],
    ['deny', 0],
    ['allow', 3]]]]]
for label, args, expected in cases[N - 1]:
    check(label, solve(args), expected)
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 fixtureActualExpectedOutcome
overdraft then repay[['allow', 2], ['deny', 2], ['allow', 2], ['allow', 3], ['allow', 3]][['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 0]]Failed
debt limit[['allow', 2], ['deny', 2], ['allow', 3], ['allow', 0]][['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]Failed
exactly zero balance[['allow', 0], ['deny', 0], ['deny', 1], ['allow', 2]][['allow', 0], ['deny', 0], ['allow', -1], ['allow', 0]]Failed
refill repays debt[['deny', 6], ['allow', 5], ['allow', 5], ['allow', 3]][['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]Failed
large cost at full balance[['deny', 2], ['deny', 2], ['allow', 1], ['allow', 1]][['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]Failed
random costs[['allow', 1], ['allow', 1], ['deny', 1], ['deny', 3], ['deny', 3], ['allow', 3], ['allow', 4], ['allow', 3], ['allow', 2]][['allow', 1], ['allow', 1], ['allow', -2], ['deny', 0], ['deny', 0], ['allow', 0], ['allow', 1], ['allow', 0], ['allow', 0]]Failed

SHA-256 / 879d4efb19802cbefacc6c158e676a9f713d457386b059e9c832eeb4b44ec65c

2 / The unsuccessful fix

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

N = 1
observations = []
def solve(x):
    cap = x['capacity']
    rate = x['rate']
    debt = x['max_debt']
    tokens = cap
    last = 0
    out = []
    for t, cost in x['requests']:
        tokens = min(cap, tokens + (t - last) * rate)
        last = t
        if tokens >= 0 and tokens - cost >= -debt:
            tokens -= cost
            out.append(['allow', tokens])
        else:
            out.append(['deny', tokens])
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [5, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 0]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 3]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [3, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 0]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [6, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [22, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[0, 4], [3, 3], [3, 3], [5, 4], [5, 5], [6, 1], [8, 1], [9, 2], [12, 3]]},
   [['allow', 1],
    ['allow', 1],
    ['allow', -2],
    ['deny', 0],
    ['deny', 0],
    ['allow', 0],
    ['allow', 1],
    ['allow', 0],
    ['allow', 0]]]],
 [['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [6, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 1]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 4]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [4, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 1]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [7, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [23, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[0, 4], [2, 1], [2, 2], [3, 5], [6, 1], [7, 4], [9, 5], [10, 2], [11, 4]]},
   [['allow', 1],
    ['allow', 2],
    ['allow', 0],
    ['allow', -4],
    ['deny', -1],
    ['deny', 0],
    ['allow', -3],
    ['deny', -2],
    ['deny', -1]]]],
 [['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [7, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 2]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 5]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [5, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 2]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [8, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [24, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[2, 3], [2, 4], [3, 3], [4, 5], [10, 2], [10, 4], [10, 5], [11, 4], [12, 4]]},
   [['allow', 2],
    ['allow', -2],
    ['deny', -1],
    ['deny', 0],
    ['allow', 3],
    ['allow', -1],
    ['deny', -1],
    ['deny', 0],
    ['allow', -3]]]],
 [['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [8, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 3]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 6]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [6, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 2]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [9, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [25, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[0, 1], [0, 2], [1, 5], [1, 5], [3, 1], [3, 2], [5, 2], [8, 4], [12, 2]]},
   [['allow', 4],
    ['allow', 2],
    ['allow', -2],
    ['deny', -2],
    ['deny', 0],
    ['deny', 0],
    ['allow', 0],
    ['allow', -1],
    ['allow', 1]]]],
 [['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [9, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 3]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 7]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [7, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 2]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [10, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [26, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[1, 5], [3, 3], [3, 3], [5, 1], [5, 3], [7, 3], [8, 1], [8, 5], [12, 1]]},
   [['allow', 0],
    ['allow', -1],
    ['deny', -1],
    ['allow', 0],
    ['deny', 0],
    ['allow', -1],
    ['deny', 0],
    ['deny', 0],
    ['allow', 3]]]]]
for label, args, expected in cases[N - 1]:
    check(label, solve(args), expected)
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 fixtureActualExpectedOutcome
overdraft then repay[['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 0]][['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 0]]Passed
debt limit[['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]][['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]Passed
exactly zero balance[['allow', 0], ['allow', -1], ['allow', -2], ['allow', -1]][['allow', 0], ['deny', 0], ['allow', -1], ['allow', 0]]Failed
refill repays debt[['allow', -4], ['allow', -1], ['allow', 0], ['allow', 3]][['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]Failed
large cost at full balance[['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]][['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]Passed
random costs[['allow', 1], ['allow', 1], ['allow', -2], ['allow', -4], ['deny', -4], ['deny', -3], ['deny', -1], ['allow', -2], ['allow', -2]][['allow', 1], ['allow', 1], ['allow', -2], ['deny', 0], ['deny', 0], ['allow', 0], ['allow', 1], ['allow', 0], ['allow', 0]]Failed

SHA-256 / 57c70aee319de24653af6388271f63bbf694de24b3c57fd20595c83dd8575b50

3 / The verified repair

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

N = 1
observations = []
def solve(x):
    cap = x['capacity']
    rate = x['rate']
    debt = x['max_debt']
    tokens = cap
    last = 0
    out = []
    for t, cost in x['requests']:
        tokens = min(cap, tokens + (t - last) * rate)
        last = t
        if tokens > 0 and tokens - cost >= -debt:
            tokens -= cost
            out.append(['allow', tokens])
        else:
            out.append(['deny', tokens])
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [5, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 0]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 3]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [3, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 0]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [6, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [22, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[0, 4], [3, 3], [3, 3], [5, 4], [5, 5], [6, 1], [8, 1], [9, 2], [12, 3]]},
   [['allow', 1],
    ['allow', 1],
    ['allow', -2],
    ['deny', 0],
    ['deny', 0],
    ['allow', 0],
    ['allow', 1],
    ['allow', 0],
    ['allow', 0]]]],
 [['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [6, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 1]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 4]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [4, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 1]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [7, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [23, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[0, 4], [2, 1], [2, 2], [3, 5], [6, 1], [7, 4], [9, 5], [10, 2], [11, 4]]},
   [['allow', 1],
    ['allow', 2],
    ['allow', 0],
    ['allow', -4],
    ['deny', -1],
    ['deny', 0],
    ['allow', -3],
    ['deny', -2],
    ['deny', -1]]]],
 [['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [7, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 2]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 5]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [5, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 2]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [8, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [24, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[2, 3], [2, 4], [3, 3], [4, 5], [10, 2], [10, 4], [10, 5], [11, 4], [12, 4]]},
   [['allow', 2],
    ['allow', -2],
    ['deny', -1],
    ['deny', 0],
    ['allow', 3],
    ['allow', -1],
    ['deny', -1],
    ['deny', 0],
    ['allow', -3]]]],
 [['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [8, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 3]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 6]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [6, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 2]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [9, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [25, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[0, 1], [0, 2], [1, 5], [1, 5], [3, 1], [3, 2], [5, 2], [8, 4], [12, 2]]},
   [['allow', 4],
    ['allow', 2],
    ['allow', -2],
    ['deny', -2],
    ['deny', 0],
    ['deny', 0],
    ['allow', 0],
    ['allow', -1],
    ['allow', 1]]]],
 [['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [9, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 3]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 7]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [7, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 2]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [10, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [26, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[1, 5], [3, 3], [3, 3], [5, 1], [5, 3], [7, 3], [8, 1], [8, 5], [12, 1]]},
   [['allow', 0],
    ['allow', -1],
    ['deny', -1],
    ['allow', 0],
    ['deny', 0],
    ['allow', -1],
    ['deny', 0],
    ['deny', 0],
    ['allow', 3]]]]]
for label, args, expected in cases[N - 1]:
    check(label, solve(args), expected)
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 fixtureActualExpectedOutcome
overdraft then repay[['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 0]][['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 0]]Passed
debt limit[['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]][['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]Passed
exactly zero balance[['allow', 0], ['deny', 0], ['allow', -1], ['allow', 0]][['allow', 0], ['deny', 0], ['allow', -1], ['allow', 0]]Passed
refill repays debt[['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]][['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]Passed
large cost at full balance[['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]][['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]Passed
random costs[['allow', 1], ['allow', 1], ['allow', -2], ['deny', 0], ['deny', 0], ['allow', 0], ['allow', 1], ['allow', 0], ['allow', 0]][['allow', 1], ['allow', 1], ['allow', -2], ['deny', 0], ['deny', 0], ['allow', 0], ['allow', 1], ['allow', 0], ['allow', 0]]Passed

SHA-256 / 2602f882f7b7bf23e6db51fd290fa8c43c184915e7d9678a08ed13f42d8ff70f

Verification & scope

A deterministic, bounded teaching model with stipulated constants and pre-hashed or explicitly hashed inputs; it is not a production implementation and makes no claim of conformance to any library or paper beyond the stated contract. 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:48:50.082370+00:00.

Case digest / 5e4e3aaca798073f3345a5e77f23daa7acc9751a83fb2c9bc06ec881b1f62f13