A token-budget allocator takes a pool (budget), a per-consumer starting floor (floor = 256), and a per-consumer rendered token estimate (estimates[i], the tokens the consumer will actually use once its content is escaped/rendered).
I diagnosed the bug, built a runnable reference implementation, and verified it. The working files are in ~/go-budget-fix/ (budget.go, render.go, budget_test.go, SOLUTION.md).
Here is the solution:
A token-budget allocator takes a pool (budget), a per-consumer starting floor (floor = 256), and a per-consumer rendered token estimate (estimates[i], the tokens the consumer will actually use once its content is escaped/rendered).
For the reported configuration it returns
alloc = [2048 1951 256] sum = 4255
budget = 4000
The overshoot is exactly the donor's phantom floor minus its estimate:
4255 - 4000 = 255 = 256 - 1
The inputs that reproduce it exactly:
budget := 4000 // prompt-side share of P=8000
floor := 256
estimates := []int{2048, 1951, 1} // rendered tokens of ~5000/~3000/tiny raw items
The estimates sum to exactly the budget (2048+1951+1 = 4000), so the correct answer is [2048 1951 1], sum 4000. The last consumer is the donor: it only ever uses 1 token, but the floor raised it to 256.
The buggy implementation:
alloc = [256, 256, 256];[2048, 1951, 1] here, since the estimates already fill the budget);256 - 1 = 255 unused tokens, and hands them to the others;alloc[2] back to 1.Steps 3 and 4 both account for the same 255 tokens — once as the donor's kept floor allocation, once as the recipients' top-up. Every token a donor does not use is counted twice:
start: [256 256 256]
+ proportional shares: [2048 1951 1] (estimates already fill the budget)
apply floor: [2048 1951 256] <-- phantom 255 for consumer 2
pool the 255 to others: others already at cap, nothing placed
return: [2048 1951 256] sum 4255 (255 double-counted)
The two tempting "fixes" are both wrong:
sum > budget.256 and never pool the estimate < floor gap. The sub-floor tokens are stranded: the donor overflows its own estimate, or the surplus is dropped and sum < budget while other demand is unmet.The correct shape: the floor is only the STARTING allocation. After the proportional step every donor settles to min(alloc, estimate), its surplus returns to the pool exactly once, and that pooled surplus fills consumers still below their cap in canonical order. Then sum == budget while demand is unmet, and sum <= budget always.
Enforce the invariants:
0 <= alloc[i] <= estimates[i]
sum(alloc) == min(budget, sum(estimates))
sum(alloc) <= budget
budget.gopackage budgetfix
import "sort"
func minInt(a, b int) int {
if a < b {
return a
}
return b
}
// Allocate distributes up to budget tokens across consumers.
//
// - estimates[i] is the number of tokens consumer i will actually use once
// its content has been rendered/escaped. It is a hard upper bound.
// - floor is the STARTING allocation per consumer. It is not an end-state
// invariant. A sub-floor consumer starts there, then settles back down.
//
// Invariants guaranteed on return:
//
// 0 <= alloc[i] <= estimates[i]
// sum(alloc) == min(budget, sum(estimates))
// sum(alloc) <= budget
func Allocate(budget int, estimates []int, floor int) []int {
n := len(estimates)
alloc := make([]int, n)
if n == 0 {
return alloc
}
if budget < 0 {
budget = 0
}
if floor < 0 {
floor = 0
}
totalDemand := 0
for i, e := range estimates {
if e < 0 {
e = 0
estimates[i] = 0
}
totalDemand += e
}
target := minInt(budget, totalDemand)
// 1. STARTING allocation: the floor. Deliberately NOT clamped to the
// estimate here; step 3 settles sub-floor consumers back down.
used := 0
for i := range alloc {
alloc[i] = floor
used += alloc[i]
}
// Budget smaller than the sum of floors: fall back to a fill from zero.
if used > target {
for i := range alloc {
alloc[i] = 0
}
used = 0
}
pool := target - used
for {
// 2. Proportional step over the pool, weighted by remaining headroom.
// Largest-remainder rounding in canonical order keeps it exact.
if pool > 0 {
headroom := 0
for i, e := range estimates {
headroom += e - alloc[i]
}
if headroom > 0 {
type remainder struct {
idx int
num int
}
rems := make([]remainder, 0, n)
distributed := 0
for i, e := range estimates {
room := e - alloc[i]
if room <= 0 {
continue
}
share := pool * room / headroom
if share > room {
share = room
}
alloc[i] += share
distributed += share
rems = append(rems, remainder{idx: i, num: (pool * room) % headroom})
}
leftover := pool - distributed
sort.SliceStable(rems, func(a, b int) bool {
return rems[a].num > rems[b].num
})
for _, r := range rems {
if leftover == 0 {
break
}
if alloc[r.idx] < estimates[r.idx] {
alloc[r.idx]++
leftover--
}
}
pool = leftover
}
}
// 3. Settle donors: keep only min(alloc, estimate); surplus returns to
// the pool exactly once. This is the missing accounting step.
settled := false
for i, e := range estimates {
if alloc[i] > e {
pool += alloc[i] - e
alloc[i] = e
settled = true
}
}
if pool == 0 {
break
}
// 4. Fill consumers still below their cap in canonical order.
moved := false
for i, e := range estimates {
if pool == 0 {
break
}
room := e - alloc[i]
if room <= 0 {
continue
}
add := minInt(pool, room)
alloc[i] += add
pool -= add
moved = true
}
if pool == 0 || !moved || !settled {
break
}
}
// Final safety net: never exceed an estimate and never exceed the budget.
sum := 0
for i := range alloc {
if alloc[i] > estimates[i] {
alloc[i] = estimates[i]
}
if alloc[i] < 0 {
alloc[i] = 0
}
sum += alloc[i]
}
for sum > budget {
for i := n - 1; i >= 0 && sum > budget; i-- {
cut := minInt(alloc[i], sum-budget)
alloc[i] -= cut
sum -= cut
}
}
return alloc
}
Escaping expands the payload (& → &, < → <). If estimates[i] comes from raw source but the prompt receives escaped bytes, the rendered item can exceed its own allowance. Render first, then estimate.
package budgetfix
import (
"html"
"strings"
"unicode/utf8"
)
// Render produces the exact bytes that will be placed into the prompt.
func Render(raw string) string { return html.EscapeString(raw) }
// EstimateTokens is a deterministic stand-in for a real tokenizer.
func EstimateTokens(rendered string) int {
return (utf8.RuneCountInString(rendered) + 3) / 4
}
// CORRECT: render first, then estimate.
func EstimateConsumer(raw string) int { return EstimateTokens(Render(raw)) }
// BUGGY: estimates the raw content, underestimating escaped items.
func EstimateRaw(raw string) int { return EstimateTokens(strings.ToValidUTF8(raw, "")) }
budget_test.go (key cases)package budgetfix
import (
"math/rand"
"strings"
"testing"
)
func sum(xs []int) int {
s := 0
for _, x := range xs {
s += x
}
return s
}
// buggyAllocate mirrors the double-counting implementation under test.
func buggyAllocate(budget int, estimates []int, floor int) []int {
alloc := make([]int, len(estimates))
total := 0
for _, e := range estimates {
total += e
}
if total == 0 {
return alloc
}
for i, e := range estimates {
alloc[i] = budget * e / total // proportional share of the whole budget
}
for i := range alloc {
if alloc[i] < floor {
alloc[i] = floor // floor raises the donor
}
}
surplus := 0
for i, e := range estimates {
if alloc[i] > e {
surplus += alloc[i] - e // BUG: donor keeps alloc[i]
}
}
for i, e := range estimates {
if surplus == 0 {
break
}
if alloc[i] < e {
add := minInt(surplus, e-alloc[i])
alloc[i] += add
surplus -= add
}
}
return alloc
}
// TestReportedRegression is the exact failing case from the report.
func TestReportedRegression(t *testing.T) {
budget := 4000
estimates := []int{2048, 1951, 1} // rendered tokens of ~5000/~3000/tiny raw items
floor := 256
buggy := buggyAllocate(budget, estimates, floor)
t.Logf("buggy = %v sum=%d", buggy, sum(buggy))
if sum(buggy) != 4255 {
t.Fatalf("buggy reproduction changed: %v", buggy)
}
got := Allocate(budget, estimates, floor)
t.Logf("fixed = %v sum=%d", got, sum(got))
if want := []int{2048, 1951, 1}; len(got) != 3 ||
got[0] != want[0] || got[1] != want[1] || got[2] != want[2] {
t.Fatalf("got %v want %v", got, want)
}
if sum(got) != budget {
t.Fatalf("sum=%d want budget %d", sum(got), budget)
}
}
// TestSubFloorSurplusIsRedistributed covers wrong-fix (b): budget == sum of
// floors; the sub-floor surplus must be reinvested, not pinned or dropped.
func TestSubFloorSurplusIsRedistributed(t *testing.T) {
got := Allocate(1280, []int{2464, 654, 1449, 157, 3638}, 256)
t.Logf("allocation = %v sum=%d", got, sum(got))
if sum(got) != 1280 || got[3] != 157 || got[0] != 355 {
t.Fatalf("bad allocation %v", got)
}
}
// TestRenderedEstimate: the estimator must track the escaped size.
func TestRenderedEstimate(t *testing.T) {
raw := strings.Repeat("&", 500)
t.Logf("raw=%d rendered=%d rawEst=%d renderedEst=%d",
len(raw), len(Render(raw)), EstimateRaw(raw), EstimateConsumer(raw))
if EstimateConsumer(raw) <= EstimateRaw(raw) {
t.Fatalf("escaping must not shrink the estimate")
}
}
// TestInvariants randomized over the whole input space.
func TestInvariants(t *testing.T) {
rng := rand.New(rand.NewSource(1))
for iter := 0; iter < 200000; iter++ {
n := 1 + rng.Intn(6)
estimates := make([]int, n)
demand := 0
for i := range estimates {
estimates[i] = rng.Intn(5000)
demand += estimates[i]
}
budget := rng.Intn(12000)
floor := 256
if rng.Intn(2) == 0 {
floor = rng.Intn(400)
}
got := Allocate(budget, estimates, floor)
s := 0
for i := range got {
if got[i] < 0 || got[i] > estimates[i] {
t.Fatalf("bound violated: alloc[%d]=%d est=%d", i, got[i], estimates[i])
}
s += got[i]
}
want := budget
if demand < want {
want = demand
}
if s != want {
t.Fatalf("sum=%d want %d (budget=%d demand=%d)", s, want, budget, demand)
}
}
}
go test -v ./...=== RUN TestReportedRegression
budget_test.go:69: buggy = [2048 1951 256] sum=4255
budget_test.go:78: fixed = [2048 1951 1] sum=4000
--- PASS: TestReportedRegression (0.00s)
=== RUN TestDemandUnmet
budget_test.go:96: allocation = [2516 1483 1] sum=4000
--- PASS: TestDemandUnmet (0.00s)
=== RUN TestBudgetBelowFloors
budget_test.go:111: allocation = [34 33 33] sum=100
--- PASS: TestBudgetBelowFloors (0.00s)
=== RUN TestSubFloorDonorDoesNotStrandTokens
--- PASS: TestSubFloorDonorDoesNotStrandTokens (0.00s)
=== RUN TestSubFloorSurplusIsRedistributed
budget_test.go:140: allocation = [355 256 256 157 256] sum=1280
--- PASS: TestSubFloorSurplusIsRedistributed (0.00s)
=== RUN TestInvariants
--- PASS: TestInvariants (0.05s)
=== RUN TestRenderedEstimate
budget_test.go:199: raw bytes=500 rendered bytes=2500
budget_test.go:200: raw estimate=125 rendered estimate=625
budget_test.go:214: raw-estimated allowance 125 < rendered 625 -> overflow
--- PASS: TestRenderedEstimate (0.00s)
PASS
ok budgetfix 0.051s
go test -race -count=1 ./... also passes.
The minimal change is to make the settle step authoritative:
go
for i, e := range estimates {
if alloc[i] > e {
pool += alloc[i] - e
alloc[i] = e // <-- the missing line in the buggy version
}
}pool to consumers with alloc[i] < estimates[i] in index order, never above estimates[i].estimates[i] from the escaped/rendered bytes that actually go into the prompt, not the raw source.For the reported case this turns [2048 1951 256] (sum 4255) into [2048 1951 1] (sum 4000).
# Evidence - Problem class: go-budget-redistribution-double-counts-unused-tokens - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-09-15T19:48:44.171Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Redistributing unused tokens to other consumers in one pass while leaving the donor allocation counted makes sum(allocations) exceed the budget (5000/3000/tiny, P=8000: got [2048 1951 256] sum 4255 vs budget 4000). Two fixes to avoid: (a) leaving the donor allocation untouched (overshoots the budget), (b) protecting the donor floor as an END-state invariant (strands the sub-floor unused tokens). Correct shape: the 256 floor is the STARTING allocation; after the proportional step, each donor settles to what it actually contributes (min(alloc, estimate)) and the pooled surplus fills consumers still below the cap in canonical order, so sum == budget while demand is unmet and never exceeds it. Also: estimate the escaped/rendered text, not the raw content, or an escape expansion can push a rendered item past its own allowance.", "environment": "", "language": "go", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "go-budget-redistribution-double-counts-unused-tokens", "provider": "openrouter", "solved_at": "2026-09-15T19:48:44.171Z", "version": ""}I diagnosed the bug, built a runnable reference implementation, and verified it. The working files are in ~/go-budget-fix/ (budget.go, render.go, budget_test.go, SOLUTION.md).
Here is the solution:
A token-budget allocator takes a pool (budget), a per-consumer starting floor (floor = 256), and a per-consumer rendered token estimate (estimates[i], the tokens the consumer will actually use once its content is escaped/rendered).
For the reported configuration it returns
alloc = [2048 1951 256] sum = 4255
budget = 4000
The overshoot is exactly the donor's phantom floor minus its estimate:
4255 - 4000 = 255 = 256 - 1
The inputs that reproduce it exactly:
budget := 4000 // prompt-side share of P=8000
floor := 256
estimates := []int{2048, 1951, 1} // rendered tokens of ~5000/~3000/tiny raw items
The estimates sum to exactly the budget (2048+1951+1 = 4000), so the correct answer is [2048 1951 1], sum 4000. The last consumer is the donor: it only ever uses 1 token, but the floor raised it to 256.
The buggy implementation:
alloc = [256, 256, 256];[2048, 1951, 1] here, since the estimates already fill the budget);256 - 1 = 255 unused tokens, and hands them to the others;alloc[2] back to 1.Steps 3 and 4 both account for the same 255 tokens — once as the donor's kept floor allocation, once as the recipients' top-up. Every token a donor does not use is counted twice:
start: [256 256 256]
+ proportional shares: [2048 1951 1] (estimates already fill the budget)
apply floor: [2048 1951 256] <-- phantom 255 for consumer 2
pool the 255 to others: others already at cap, nothing placed
return: [2048 1951 256] sum 4255 (255 double-counted)
The two tempting "fixes" are both wrong:
sum > budget.256 and never pool the estimate < floor gap. The sub-floor tokens are stranded: the donor overflows its own estimate, or the surplus is dropped and sum < budget while other demand is unmet.The correct shape: the floor is only the STARTING allocation. After the proportional step every donor settles to min(alloc, estimate), its surplus returns to the pool exactly once, and that pooled surplus fills consumers still below their cap in canonical order. Then sum == budget while demand is unmet, and sum <= budget always.
Enforce the invariants:
0 <= alloc[i] <= estimates[i]
sum(alloc) == min(budget, sum(estimates))
sum(alloc) <= budget
budget.gopackage budgetfix
import "sort"
func minInt(a, b int) int {
if a < b {
return a
}
return b
}
// Allocate distributes up to budget tokens across consumers.
//
// - estimates[i] is the number of tokens consumer i will actually use once
// its content has been rendered/escaped. It is a hard upper bound.
// - floor is the STARTING allocation per consumer. It is not an end-state
// invariant. A sub-floor consumer starts there, then settles back down.
//
// Invariants guaranteed on return:
//
// 0 <= alloc[i] <= estimates[i]
// sum(alloc) == min(budget, sum(estimates))
// sum(alloc) <= budget
func Allocate(budget int, estimates []int, floor int) []int {
n := len(estimates)
alloc := make([]int, n)
if n == 0 {
return alloc
}
if budget < 0 {
budget = 0
}
if floor < 0 {
floor = 0
}
totalDemand := 0
for i, e := range estimates {
if e < 0 {
e = 0
estimates[i] = 0
}
totalDemand += e
}
target := minInt(budget, totalDemand)
// 1. STARTING allocation: the floor. Deliberately NOT clamped to the
// estimate here; step 3 settles sub-floor consumers back down.
used := 0
for i := range alloc {
alloc[i] = floor
used += alloc[i]
}
// Budget smaller than the sum of floors: fall back to a fill from zero.
if used > target {
for i := range alloc {
alloc[i] = 0
}
used = 0
}
pool := target - used
for {
// 2. Proportional step over the pool, weighted by remaining headroom.
// Largest-remainder rounding in canonical order keeps it exact.
if pool > 0 {
headroom := 0
for i, e := range estimates {
headroom += e - alloc[i]
}
if headroom > 0 {
type remainder struct {
idx int
num int
}
rems := make([]remainder, 0, n)
distributed := 0
for i, e := range estimates {
room := e - alloc[i]
if room <= 0 {
continue
}
share := pool * room / headroom
if share > room {
share = room
}
alloc[i] += share
distributed += share
rems = append(rems, remainder{idx: i, num: (pool * room) % headroom})
}
leftover := pool - distributed
sort.SliceStable(rems, func(a, b int) bool {
return rems[a].num > rems[b].num
})
for _, r := range rems {
if leftover == 0 {
break
}
if alloc[r.idx] < estimates[r.idx] {
alloc[r.idx]++
leftover--
}
}
pool = leftover
}
}
// 3. Settle donors: keep only min(alloc, estimate); surplus returns to
// the pool exactly once. This is the missing accounting step.
settled := false
for i, e := range estimates {
if alloc[i] > e {
pool += alloc[i] - e
alloc[i] = e
settled = true
}
}
if pool == 0 {
break
}
// 4. Fill consumers still below their cap in canonical order.
moved := false
for i, e := range estimates {
if pool == 0 {
break
}
room := e - alloc[i]
if room <= 0 {
continue
}
add := minInt(pool, room)
alloc[i] += add
pool -= add
moved = true
}
if pool == 0 || !moved || !settled {
break
}
}
// Final safety net: never exceed an estimate and never exceed the budget.
sum := 0
for i := range alloc {
if alloc[i] > estimates[i] {
alloc[i] = estimates[i]
}
if alloc[i] < 0 {
alloc[i] = 0
}
sum += alloc[i]
}
for sum > budget {
for i := n - 1; i >= 0 && sum > budget; i-- {
cut := minInt(alloc[i], sum-budget)
alloc[i] -= cut
sum -= cut
}
}
return alloc
}
Escaping expands the payload (& → &, < → <). If estimates[i] comes from raw source but the prompt receives escaped bytes, the rendered item can exceed its own allowance. Render first, then estimate.
package budgetfix
import (
"html"
"strings"
"unicode/utf8"
)
// Render produces the exact bytes that will be placed into the prompt.
func Render(raw string) string { return html.EscapeString(raw) }
// EstimateTokens is a deterministic stand-in for a real tokenizer.
func EstimateTokens(rendered string) int {
return (utf8.RuneCountInString(rendered) + 3) / 4
}
// CORRECT: render first, then estimate.
func EstimateConsumer(raw string) int { return EstimateTokens(Render(raw)) }
// BUGGY: estimates the raw content, underestimating escaped items.
func EstimateRaw(raw string) int { return EstimateTokens(strings.ToValidUTF8(raw, "")) }
budget_test.go (key cases)package budgetfix
import (
"math/rand"
"strings"
"testing"
)
func sum(xs []int) int {
s := 0
for _, x := range xs {
s += x
}
return s
}
// buggyAllocate mirrors the double-counting implementation under test.
func buggyAllocate(budget int, estimates []int, floor int) []int {
alloc := make([]int, len(estimates))
total := 0
for _, e := range estimates {
total += e
}
if total == 0 {
return alloc
}
for i, e := range estimates {
alloc[i] = budget * e / total // proportional share of the whole budget
}
for i := range alloc {
if alloc[i] < floor {
alloc[i] = floor // floor raises the donor
}
}
surplus := 0
for i, e := range estimates {
if alloc[i] > e {
surplus += alloc[i] - e // BUG: donor keeps alloc[i]
}
}
for i, e := range estimates {
if surplus == 0 {
break
}
if alloc[i] < e {
add := minInt(surplus, e-alloc[i])
alloc[i] += add
surplus -= add
}
}
return alloc
}
// TestReportedRegression is the exact failing case from the report.
func TestReportedRegression(t *testing.T) {
budget := 4000
estimates := []int{2048, 1951, 1} // rendered tokens of ~5000/~3000/tiny raw items
floor := 256
buggy := buggyAllocate(budget, estimates, floor)
t.Logf("buggy = %v sum=%d", buggy, sum(buggy))
if sum(buggy) != 4255 {
t.Fatalf("buggy reproduction changed: %v", buggy)
}
got := Allocate(budget, estimates, floor)
t.Logf("fixed = %v sum=%d", got, sum(got))
if want := []int{2048, 1951, 1}; len(got) != 3 ||
got[0] != want[0] || got[1] != want[1] || got[2] != want[2] {
t.Fatalf("got %v want %v", got, want)
}
if sum(got) != budget {
t.Fatalf("sum=%d want budget %d", sum(got), budget)
}
}
// TestSubFloorSurplusIsRedistributed covers wrong-fix (b): budget == sum of
// floors; the sub-floor surplus must be reinvested, not pinned or dropped.
func TestSubFloorSurplusIsRedistributed(t *testing.T) {
got := Allocate(1280, []int{2464, 654, 1449, 157, 3638}, 256)
t.Logf("allocation = %v sum=%d", got, sum(got))
if sum(got) != 1280 || got[3] != 157 || got[0] != 355 {
t.Fatalf("bad allocation %v", got)
}
}
// TestRenderedEstimate: the estimator must track the escaped size.
func TestRenderedEstimate(t *testing.T) {
raw := strings.Repeat("&", 500)
t.Logf("raw=%d rendered=%d rawEst=%d renderedEst=%d",
len(raw), len(Render(raw)), EstimateRaw(raw), EstimateConsumer(raw))
if EstimateConsumer(raw) <= EstimateRaw(raw) {
t.Fatalf("escaping must not shrink the estimate")
}
}
// TestInvariants randomized over the whole input space.
func TestInvariants(t *testing.T) {
rng := rand.New(rand.NewSource(1))
for iter := 0; iter < 200000; iter++ {
n := 1 + rng.Intn(6)
estimates := make([]int, n)
demand := 0
for i := range estimates {
estimates[i] = rng.Intn(5000)
demand += estimates[i]
}
budget := rng.Intn(12000)
floor := 256
if rng.Intn(2) == 0 {
floor = rng.Intn(400)
}
got := Allocate(budget, estimates, floor)
s := 0
for i := range got {
if got[i] < 0 || got[i] > estimates[i] {
t.Fatalf("bound violated: alloc[%d]=%d est=%d", i, got[i], estimates[i])
}
s += got[i]
}
want := budget
if demand < want {
want = demand
}
if s != want {
t.Fatalf("sum=%d want %d (budget=%d demand=%d)", s, want, budget, demand)
}
}
}
go test -v ./...=== RUN TestReportedRegression
budget_test.go:69: buggy = [2048 1951 256] sum=4255
budget_test.go:78: fixed = [2048 1951 1] sum=4000
--- PASS: TestReportedRegression (0.00s)
=== RUN TestDemandUnmet
budget_test.go:96: allocation = [2516 1483 1] sum=4000
--- PASS: TestDemandUnmet (0.00s)
=== RUN TestBudgetBelowFloors
budget_test.go:111: allocation = [34 33 33] sum=100
--- PASS: TestBudgetBelowFloors (0.00s)
=== RUN TestSubFloorDonorDoesNotStrandTokens
--- PASS: TestSubFloorDonorDoesNotStrandTokens (0.00s)
=== RUN TestSubFloorSurplusIsRedistributed
budget_test.go:140: allocation = [355 256 256 157 256] sum=1280
--- PASS: TestSubFloorSurplusIsRedistributed (0.00s)
=== RUN TestInvariants
--- PASS: TestInvariants (0.05s)
=== RUN TestRenderedEstimate
budget_test.go:199: raw bytes=500 rendered bytes=2500
budget_test.go:200: raw estimate=125 rendered estimate=625
budget_test.go:214: raw-estimated allowance 125 < rendered 625 -> overflow
--- PASS: TestRenderedEstimate (0.00s)
PASS
ok budgetfix 0.051s
go test -race -count=1 ./... also passes.
The minimal change is to make the settle step authoritative:
go
for i, e := range estimates {
if alloc[i] > e {
pool += alloc[i] - e
alloc[i] = e // <-- the missing line in the buggy version
}
}pool to consumers with alloc[i] < estimates[i] in index order, never above estimates[i].estimates[i] from the escaped/rendered bytes that actually go into the prompt, not the raw source.For the reported case this turns [2048 1951 256] (sum 4255) into [2048 1951 1] (sum 4000).
# Evidence - Problem class: go-budget-redistribution-double-counts-unused-tokens - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-09-15T19:48:44.171Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Redistributing unused tokens to other consumers in one pass while leaving the donor allocation counted makes sum(allocations) exceed the budget (5000/3000/tiny, P=8000: got [2048 1951 256] sum 4255 vs budget 4000). Two fixes to avoid: (a) leaving the donor allocation untouched (overshoots the budget), (b) protecting the donor floor as an END-state invariant (strands the sub-floor unused tokens). Correct shape: the 256 floor is the STARTING allocation; after the proportional step, each donor settles to what it actually contributes (min(alloc, estimate)) and the pooled surplus fills consumers still below the cap in canonical order, so sum == budget while demand is unmet and never exceeds it. Also: estimate the escaped/rendered text, not the raw content, or an escape expansion can push a rendered item past its own allowance.", "environment": "", "language": "go", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "go-budget-redistribution-double-counts-unused-tokens", "provider": "openrouter", "solved_at": "2026-09-15T19:48:44.171Z", "version": ""}