Trim History to a Token Budget

Start from brute force

The obvious approach drops the oldest message until the rest fits: copy the list, then while sum(counts) > budget: counts.pop(0). It is correct: token counts are non-negative, so it stops at the same longest suffix the reference finds. But each iteration re-adds every remaining count and pop(0) shifts every remaining element, so it costs O(n²) time for n messages, plus O(n) space for the copy; without the copy, it destroys the caller’s list. For a history that grows every turn and is trimmed every turn, re-summing everything from scratch is wasted work.

The approach

Token counts are non-negative, so a suffix’s sum only grows as it reaches further back. The answer is therefore the longest suffix that fits, and one walk from the newest message finds it. The reference iterates reversed(counts) with a running total. For each count c, if total + c > budget it stops; otherwise it adds c to total and appends it to kept.

Stopping, rather than skipping the message and continuing, is what keeps the result a contiguous suffix: a history with a hole in it reads as if a turn never happened. Since kept was built newest-first, kept.reverse() restores oldest-first order before returning. The invariant after each step: kept holds the newest messages seen so far, total is their sum, and total ≤ budget. The TypeScript reference prepends with unshift instead of reversing at the end, with the same result.

Walk through an example

Trimming [8, 3, 4, 2] to a budget of 10 walks backward from the newest message, stops at the 8, and reverses the kept counts back to [3, 4, 2].

Complexity

One backward walk that stops at the first message that does not fit: O(n) time in the worst case and O(k) space for the k kept counts. The TypeScript reference’s unshift moves every element already in the array, so it is O(k²) in the worst case; pushing and reversing once keeps it linear. The pop-from-the-front loop is O(n²).

Edge cases to test

• A huge message in the middle ends the walk: trim_history([5, 100, 1], 10) returns [1], not [5, 1]. Skipping the oversized message to keep an older one would leave a gap in the conversation.
• The newest message alone exceeds the budget: trim_history([1, 1, 20], 5) returns [], even though the two older messages would fit together.
• An exact fit is kept, because the test is >, not >=: trim_history([4, 6], 10) returns [4, 6].
• Zero-token messages always fit: trim_history([0, 0], 0) returns [0, 0], and trim_history([1, 0], 0) returns [0].
• An empty history returns [], and so does any history with a negative budget.

Common mistakes

• Skipping a message that does not fit and continuing to older ones. It packs in more tokens, but the kept messages are no longer a contiguous suffix, and the model reads a conversation with a turn missing.
• Returning the kept counts newest-first. The walk runs backward, so the list has to be reversed before it is returned.
• Using >= in the budget test, which drops a message that fits exactly.
• Trimming by message count instead of token count, so you blow the budget on a few long messages.
• Calling pop(0) or reverse() on the caller’s counts, which silently rewrites the conversation the caller still holds.

Follow-ups an interviewer asks next

The first message is a system prompt that must always survive. What changes?

Reserve it first: subtract its tokens from the budget, trim the remaining turns with the same backward walk, and return the system message followed by the kept suffix. If the system message alone exceeds the budget, fail loudly; sending a truncated or missing system prompt changes the model’s behavior without any error.

Tool calls and their results must stay together. How do you trim then?

Trim in units, not messages: group each assistant tool call with the tool results that answer it, then walk the groups from newest to oldest, keeping or dropping each group whole. The contiguous-suffix rule still holds, now at group boundaries, so a result is never left without the call that produced it.

Can you keep the information in the dropped turns?

Summarize them. When the history overflows, replace the oldest turns with one short summary message and keep the recent turns verbatim. Budget for the summary’s own tokens, and summarize incrementally, folding newly dropped turns into the existing summary, so the cost does not grow with the length of the conversation.

Trimming runs on every agent turn. Can it avoid re-walking the history?

Yes. Keep a running total and a start index. Each new message adds its count to the total; then, while the total exceeds the budget, subtract the count at the start index and advance it. Every message enters and leaves once, so each turn is amortized O(1), the same two-pointer idea as a sliding window.

Where this shows up

Token-budget trimming is core context engineering: every long-running agent has to fit its history inside the context window, and dropping the oldest turns first is the baseline policy. Production versions add rules on top of this one: pin the system prompt and trim only the turns after it, keep each tool call together with its result, since chat APIs generally reject a tool result whose call was trimmed away, and often summarize the dropped prefix instead of discarding it.

Reference solution

def trim_history(counts, budget):
    kept = []
    total = 0
    for c in reversed(counts):      # newest first
        if total + c > budget:
            break
        total += c
        kept.append(c)
    kept.reverse()                  # back to oldest-first
    return kept


print(trim_history([5, 5, 5, 5], 12))   # -> [5, 5]
print(trim_history([10, 1, 1, 1], 3))    # -> [1, 1, 1]

function trimHistory(counts: number[], budget: number): number[] {
  const kept: number[] = [];
  let total = 0;
  for (let i = counts.length - 1; i >= 0; i--) {  // newest first
    if (total + counts[i] > budget) break;
    total += counts[i];
    kept.unshift(counts[i]);                       // prepend → oldest-first
  }
  return kept;
}

console.log(trimHistory([5, 5, 5, 5], 12));   // -> [5, 5]
console.log(trimHistory([10, 1, 1, 1], 3));    // -> [1, 1, 1]