Token-Budget Context Manager

Background

Long agent runs grow the message history past the LLM's context window. The standard fix: prune middle history while keeping (1) the system prompt and (2) the most recent user turn. The system prompt carries instructions; the last turn carries the immediate query. Everything else is evictable when budget pressure hits.

Problem statement

Implement evict_to_budget(messages, budget). Each message is a dict with at least tokens (an int). The output's total tokens must be <= budget. Always retain message at index 0 (system) and index $-1$ (most recent). Evict from the middle, oldest first (index $1$, then $2$, ...). If even system + last together exceed budget, raise ValueError.

Input

• messages — list[dict], in chronological order. Each has at least "tokens": int.
• budget — int >= 0, the token cap.

Output

Returns a list[dict]. Same dict identities (not copies) for the messages that survive.

Examples

Example 1 — all fit, no eviction

Input:  msgs = [{role:"s",tokens:10}, {role:"u",tokens:5}], budget=100
Output: same msgs

Example 2 — evict middle entries oldest first

Input:  msgs of tokens [10, 50, 50, 10] (4 messages), budget=80
Output: messages 0, 2, 3 kept; total = 70

Example 3 — system + last alone exceed budget → ValueError

Input:  msgs of tokens [50, 50], budget=60
Output: ValueError

Example 4 — single message: never evicted

Input:  msgs = [{role:"s", tokens:5}], budget=100
Output: same msg

Constraints

• The system message (index 0) and the most-recent message (index $-1$) are never evicted.
• Eviction order is oldest middle first: index 1, then 2, etc.
• If system + last alone exceed budget, raise ValueError.

Notes

• vs summarisation. A more sophisticated alternative is to summarise evicted middle history into a single condensed message. Heavier; needs a summariser LLM call.
• Tool calls. Real agent histories include tool messages with potentially huge JSON bodies. Often a separate eviction policy keeps recent tool results.