Budgeted compaction

A strong answer

Sum the history first. If it fits the budget, return no fold and every label: compaction costs a summariser call and a cache write of the whole new prefix, and a planner that compacts a history that fits pays both for nothing.

Otherwise find the cut. The newest keep_last turns stay verbatim. An earlier summary is never one of them and is always folded first, because dropping it forgets every turn before it, which is the turn-50 bug. Everything before the cut is folded. The slot is the budget minus the kept tokens: in the first example 37,000 − 10 × 3,500 = 2,000, so the context after compaction is 6,000 + 37,000 = 43,000 tokens, and the next compaction is (105,000 − 37,000) ÷ 3,500 ≈ 19.4, so twenty turns away, on turn 50.

Refuse with None in two cases: nothing to fold, or a slot of zero or less. A zero-token summary is a deletion, and a negative one is the rejected call. Refusing hands the decision back to the harness, which can stub old tool results first, since editing needs no model call, or keep fewer turns. The planner never cuts a kept turn to fit, because half a tool result reads to the model as a whole one.

The harness sends the folded turns to the summariser with the slot as its output cap and an instruction to keep identifiers and figures verbatim; the plan itself needs no model, which is how a harness in 200 lines tests it. If kept turns overflow often, count keep_last in tokens rather than turns.

Rubric

• returns no fold when the history already fits, so no summariser call or cache write is spent
• folds an earlier summary first and never keeps it verbatim
• keeps the newest keep_last turns, or all of them when there are fewer, and folds everything older
• sets the slot to the budget minus the kept tokens, matching the 2,000 of the examples
• returns None when nothing can be folded or the slot would be zero or negative, and never cuts a kept turn

Where answers go wrong

"Fold every turn except the last ten." Written over the turns alone, it skips the summary entry: the second example folds turns 21 to 40, and turns 1 to 20 are gone from the run's memory with no trace that they existed.

"Give the summary a fixed 2,000 tokens." The first example passes. With larger kept turns the history after compaction is over the budget: on the run with three 20,000-token results it is 86,500 tokens against 37,000, the trigger fires again six turns later instead of twenty, and the run pays a summariser call and a cache write each time.

"When the kept turns overflow, cut the largest tool result down to fit." The model then reads a truncated result as complete, and nothing in the context says a cut was made.

Solution

"""Budgeted compaction — keep the newest turns verbatim and give the summary what is left."""


def solve(turns, budget, keep_last):
    """turns: [(label, tokens), ...], oldest first; a first entry labelled
    "summary" is the summary an earlier compaction left.
    budget: the tokens the history may hold after compaction, summary included.
    keep_last: how many of the newest turns stay verbatim.
    Returns (fold, keep, slot): the labels sent to the summariser, oldest first,
    with an earlier summary always among them; the labels kept verbatim; and
    the summary's token cap, budget minus the kept tokens. A history that
    already fits returns ([], every label, 0). Returns None when there is
    nothing to fold or the kept turns leave no room for a summary."""
    labels = [label for label, _ in turns]
    if sum(tokens for _, tokens in turns) <= budget:
        return ([], labels, 0)              # nothing to do: no summariser call, no cache write
    first = 1 if turns and turns[0][0] == "summary" else 0
    cut = len(turns) - min(keep_last, len(turns) - first)   # first kept index; an old summary is never kept
    slot = budget - sum(tokens for _, tokens in turns[cut:])
    if cut == 0 or slot <= 0:
        return None                         # refuse: never drop or cut a kept turn to make room
    return (labels[:cut], labels[cut:], slot)   # invariant: fold + keep is every label, in order


T30 = [(f"t{i}", 3500) for i in range(1, 31)]
SECOND = [("summary", 2000)] + [(f"t{i}", 3500) for i in range(21, 51)]

TESTS = [
    # the examples on the page
    ((T30, 37000, 10), ([f"t{i}" for i in range(1, 21)], [f"t{i}" for i in range(21, 31)], 2000)),
    ((SECOND, 37000, 10), (["summary"] + [f"t{i}" for i in range(21, 41)], [f"t{i}" for i in range(41, 51)], 2000)),
    (([("t1", 20000), ("t2", 20000), ("t3", 20000)], 37000, 2), None),
    # a history that fits is left alone
    ((T30[:5], 37000, 10), ([], ["t1", "t2", "t3", "t4", "t5"], 0)),
    # kept turns that exactly fill the budget leave a zero-token summary, which is a deletion
    (([("t1", 5000), ("t2", 10000), ("t3", 10000)], 20000, 2), None),
    # one large tool result inside the kept window shrinks the slot, not the kept set
    (([("t1", 3000), ("t2", 3000), ("t3", 3000), ("t4", 24000), ("t5", 2000)], 30000, 2),
     (["t1", "t2", "t3"], ["t4", "t5"], 4000)),
    # keep_last 0 folds everything
    (([("t1", 30000), ("t2", 30000)], 37000, 0), (["t1", "t2"], [], 37000)),
    # fewer turns than keep_last: only the old summary can be folded
    (([("summary", 6000), ("t1", 1000), ("t2", 1000)], 5000, 5), (["summary"], ["t1", "t2"], 3000)),
    # nothing older than the kept turns, and it does not fit
    (([("t1", 50000)], 37000, 3), None),
    (([], 1000, 3), ([], [], 0)),
]