Summarize Old Turns to Save Context

A long-running agent cannot keep every turn forever: the context window is finite and every token costs money and latency. The standard fix is compaction. Once the transcript grows past a budget, you collapse the oldest turns into a short summary and keep only the system prompt plus the last few messages verbatim. This exercise is that control logic.

How compaction works

The history is a list of {"role", "content"} messages. You split it into three regions:

• The system message — if messages[0] has role == "system", it is the durable instruction set and is always kept as the first message.
• The recent window — the last keep_recent messages. These are the live context the model needs and are kept verbatim.
• The old middle — everything between the system message and the recent window. When you are over budget, this whole region is replaced by one summary message.

You only compact when the transcript is actually over budget: sum count_tokens(m) across every message and compare against token_budget. If the history already fits, return it untouched. If it is over budget but the middle region is empty (there is nothing to collapse), also return it untouched — you cannot save space that is not there.

Both count_tokens and summarize are injected callables. That keeps the function deterministic: the same inputs always produce the same compacted list, with no real tokenizer or model in the loop.

Task

Complete compact_history(messages, summarize, count_tokens, token_budget, keep_recent=2):

1. Compute the total token count. If it is not greater than token_budget, return messages unchanged.
2. Peel off the system message: head = [messages[0]] if its role is "system", else head = []. The rest is the body.
3. Split the body into recent (its last keep_recent messages) and old (everything before them). Handle keep_recent == 0, where recent is empty and old is the whole body.
4. If old is empty, there is nothing to summarize — return messages unchanged.
5. Otherwise build summary = {"role": "system", "content": summarize(old)} and return head + [summary] + recent.

Example

messages = [
    {"role": "system",    "content": "You are a helpful assistant."},  # 5 tokens
    {"role": "user",      "content": "one two three four"},            # 4 tokens
    {"role": "assistant", "content": "reply a"},                       # 2 tokens
    {"role": "user",      "content": "five six seven"},                # 3 tokens
    {"role": "assistant", "content": "reply b"},                       # 2 tokens
]

count_tokens = lambda m: len(m["content"].split())        # total = 16
summarize = lambda old: f"earlier conversation ({len(old)} messages)"

compact_history(messages, summarize, count_tokens, token_budget=12, keep_recent=2)
# -> [
#   {"role": "system", "content": "You are a helpful assistant."},
#   {"role": "system", "content": "earlier conversation (2 messages)"},
#   {"role": "user",   "content": "five six seven"},
#   {"role": "assistant", "content": "reply b"},
# ]

# already within budget -> returned unchanged
compact_history(messages, summarize, count_tokens, token_budget=100, keep_recent=2) is messages
# -> True

Constraints

• Compact only when the total token count is strictly greater than token_budget.
• Never drop or rewrite the system message, and never rewrite the recent window — only the old middle is summarized.
• The summary is a single message {"role": "system", "content": <summary string>}.
• keep_recent may be 0 (summarize everything after the system message) and may be larger than the body (then nothing is old, so return unchanged).
• Do not call any real model, tokenizer, or network — summarize and count_tokens are provided.

Approach

Sum the injected token counts first and bail out early when the history already fits — compaction should be a no-op under budget. When over budget, slice the history into three regions: the system head, the recent window (last keep_recent), and the old middle. Collapse only the middle by passing it to the summarize stub, then reassemble head + [summary] + recent. A second guard returns the original list when the middle is empty, since there is nothing to save.

Solution

from typing import Callable, Dict, List

def compact_history(
    messages: List[Dict],
    summarize: Callable[[List[Dict]], str],
    count_tokens: Callable[[Dict], int],
    token_budget: int,
    keep_recent: int = 2,
) -> List[Dict]:
    # 1. under budget -> nothing to do
    total = sum(count_tokens(m) for m in messages)
    if total <= token_budget:
        return messages

    # 2. peel off the durable system message
    if messages and messages[0].get("role") == "system":
        head, body = messages[:1], messages[1:]
    else:
        head, body = [], messages

    # 3. split body into old middle + recent window
    if keep_recent > 0:
        recent = body[-keep_recent:]
        old = body[:-keep_recent]
    else:
        recent = []
        old = body

    # 4. nothing in the middle -> can't save space, return unchanged
    if not old:
        return messages

    # 5. collapse the middle into one summary message
    summary = {"role": "system", "content": summarize(old)}
    return head + [summary] + recent

Walkthrough

On the example, count_tokens is a word count and the messages total 5 + 4 + 2 + 3 + 2 = 16:

1. total = 16 > token_budget = 12, so we proceed past the early return.
2. messages[0]["role"] == "system", so head is the assistant-instruction message and body is the remaining four messages.
3. keep_recent = 2, so recent = body[-2:] is [{"user": "five six seven"}, {"assistant": "reply b"}] and old = body[:-2] is [{"user": "one two three four"}, {"assistant": "reply a"}].
4. old is non-empty, so we do not bail out.
5. summarize(old) returns "earlier conversation (2 messages)"; we wrap it as a system message and return head + [summary] + recent — four messages, with the two oldest turns replaced by one summary.

For the second call, token_budget = 100 and total = 16 <= 100, so step 1 returns the exact same list object — that is why is messages is True.

Complexity & notes

• Time is O(n) over the messages for the token sum plus O(n) for the slices; the summarize call dominates in practice. Space is O(n) for the new list (the early-return path allocates nothing).
• Returning the original object unchanged when under budget lets callers cheaply detect “no compaction happened” with an identity check, and avoids a needless copy.
• The two guards matter: without the budget check you would summarize healthy histories, and without the empty-old check a short transcript (system + only the recent window) would produce a pointless empty summary and could even grow the list.
• Slicing with body[-keep_recent:] fails silently in a good way when keep_recent exceeds the body length — it just returns the whole body, so old is empty and step 4 returns unchanged. The keep_recent == 0 branch is separate because body[-0:] is the whole list, not an empty one.
• Real systems iterate this: after inserting the summary they may re-check the budget and compact again, feed the previous summary back into summarize so it accretes rather than resets, and count the summary’s own tokens. The core three-region split is the reusable skeleton.