FA-73730 / Rate limiter algorithms / Member archive

Token bucket with bounded overdraft: debt bounded by capacity instead of the debt limit · case 05

The overdraft limit follows the bucket size rather than the configured debt bound.

Member previewVariant 5 · 3 implementations · 6 checks per implementation

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.

One recorded failure

Sample boundary fixture

This sample comes from the broken implementation of a controlled reproducer.

Boundary fixture	Actual	Expected	Outcome
large cost at full balance	`[["deny", 2], ["deny", 2], ["allow", 1], ["allow", 1]]`	`[["allow", -7], ["deny", 2], ["allow", 1], ["allow", 1]]`	Failed

MEMBER ARCHIVE

The complete case is available to members.

This record includes three runnable implementations, regression fixtures, execution results, and source hashes.

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