Trim a Message History to a Token Budget

Problem Statement

An agent's context window is finite. Before every model call the runtime must decide which of the accumulated messages still fit. Naively slicing the last N messages corrupts the conversation: you can end up starting mid-turn, with an assistant message answering a user message that is no longer present.

Write the trimmer that a production agent loop would use.

Background

A chat transcript is a list of messages, each with a role (system, user or assistant) and a pre-computed tokens count. Two invariants must survive trimming:

1. System messages are pinned. They carry the agent's instructions and tool definitions, so they are never dropped and their tokens are spent first.
2. Turns are atomic. A turn starts at a user message and includes every message after it up to (but not including) the next user message. You drop whole turns from the oldest end, never half a turn. This guarantees the retained history always begins on a user message.

Any non-system messages appearing before the first user message belong to no turn and are discarded.

Your Task

Implement:

def trim_history(messages, max_tokens):

• messages: list of dicts {"id": str, "role": str, "tokens": int}, in chronological order.
• max_tokens: int, the budget for the whole kept set.

Algorithm:

1. Sum the tokens of all system messages. This is the base cost.
2. Group the remaining messages into turns as described.
3. Starting from the full history, while the total (base + kept turns) exceeds max_tokens, drop the oldest remaining turn.
4. If, after dropping every turn, the system messages alone still exceed the budget, return only the system messages.

Input/Output Format

Return the kept messages as a list of the original dicts, in the original chronological order (system messages keep their original positions).

Sample

msgs = [
    {"id": "s0", "role": "system", "tokens": 20},
    {"id": "u1", "role": "user", "tokens": 30},
    {"id": "a1", "role": "assistant", "tokens": 30},
    {"id": "u2", "role": "user", "tokens": 25},
    {"id": "a2", "role": "assistant", "tokens": 25},
]
print([m["id"] for m in trim_history(msgs, 100)])
# ['s0', 'u2', 'a2']

Full history costs 20 + 60 + 50 = 130 > 100. Drop the oldest turn (u1,a1, 60 tokens) leaving 70, which fits.