Vibe Engines is free, interactive AI engineering & system design — runs in your browser. Pick a learning path →
Trim History to a Token Budget
Every agent turn re-sends the whole conversation, so the history has to fit the context budget. The standard move: keep the most recent messages that fit and drop the oldest. Implement the trimmer at the heart of context management.
The problem
Implement trim_history(counts, budget). counts is a list of the token counts of the messages in a conversation, oldest first. Keep as many of the most recent messages as fit within budget tokens (walking from the end, stopping at the first message that would push the total over budget), and return their counts in original order.
Your turn — write it
Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? open the hints under the problem, or Reveal solution is one click away.
Implement trim_history(counts, budget) — keep the most recent messages that fit the token budget, drop the oldest, and return the kept counts oldest-first.
Examples and constraints 5 examples
counts=[5, 5, 5, 5], budget=12[5, 5]counts=[10, 1, 1, 1], budget=3[1, 1, 1]counts=[8, 3, 4, 2], budget=10[3, 4, 2]counts=[100], budget=50[]counts=[5, 100, 1], budget=10[1]- Keep the most recent messages — walk from the end and stop at the first that would exceed the budget.
- Return the kept counts in their original (oldest-first) order.
- The kept messages form a contiguous suffix of the input.
Hints 3 ideas
- Iterate the list in reverse (newest first), accumulating a running total.
- Stop as soon as adding the next message would exceed the budget.
- Collect the kept counts, then restore their original order before returning.
Approach, complexity & discussion — open after you solve
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].
| step | c | total + c | decision | kept |
|---|---|---|---|---|
| 1 | 2 (newest) | 0 + 2 = 2 | fits, keep | [2] |
| 2 | 4 | 2 + 4 = 6 | fits, keep | [2, 4] |
| 3 | 3 | 6 + 3 = 9 | fits, keep | [2, 4, 3] |
| 4 | 8 | 9 + 8 = 17 > 10 | stop | [2, 4, 3] |
| 5 | none | none | kept.reverse() | [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], andtrim_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)orreverse()on the caller’scounts, 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.
Getting the budget right is half the work. The context window is shared by the prompt and the reply, so the budget for history is the window minus the tokens reserved for the output, minus the system prompt and any tool definitions, which also count as input. The counts must come from the model’s own tokenizer: a word count or a different model’s tokenizer can be off by enough to overflow at the edge. Chat formats also wrap each message in a few tokens for the role and delimiters, so a trimmer that sums only the message text runs slightly over; adding a small per-message overhead, or trimming against a budget a little below the hard limit, absorbs that.
Trimming also interacts with prompt caching. Providers that cache a prompt prefix can only reuse it while the beginning of the prompt is byte-for-byte unchanged, and dropping the oldest turn changes the beginning on every turn. A common compromise is to trim in larger steps: when the history overflows, drop enough old turns to get well under the budget, so the next several turns append to an unchanged prefix instead of re-trimming it each time.
The pattern itself, keep the longest suffix whose sum fits, is not specific to language models. Log viewers that show “the last N kilobytes”, ring buffers that keep recent samples and rate limiters that count events in a trailing window all keep a contiguous recent run under a fixed capacity. The incremental two-pointer version from the follow-ups is how those systems do it without re-scanning.
Check yourself
What does trim_history([2, 9, 1, 3, 4], 8) return?
[1, 3, 4]. Walking from the newest, 4, 3 and 1 bring the total to exactly 8, which still fits because the test is >; the 9 would make 17, so the walk stops and the 2 behind it is never considered.
A “skip and continue” variant uses continue instead of break. What does it return for [1, 7, 2, 6], budget 9, and what does the reference return?
The variant returns [1, 2, 6], filling the budget exactly, while the reference returns [2, 6]. The variant’s answer has a hole where the 7 was, so the model would read the oldest turn followed by turns that were replying to a message it never sees.
Message 0 is a 3-token system prompt that must survive, the turns after it are [5, 4, 2], and the budget is 10. What is sent?
[3, 4, 2]. Reserve the system prompt first, leaving a budget of 7 for the turns; trim_history([5, 4, 2], 7) returns [4, 2], and the system prompt goes in front of it.
An agent runs n turns, calling the reference on the whole history every turn, and the budget is large enough that nothing is ever dropped. What is the total trimming cost, and what fixes it?
O(n²): turn t walks all t messages because none of them stops the loop, and 1 + 2 + … + n is about n²/2. Keeping a running total and a start index, adding each new message once and dropping from the front only on overflow, makes it O(n) over the whole conversation.
Reference solution
Reference solution — Python
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]Reference solution — TypeScript
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]Questions about Trim History to a Token Budget
Why keep the most recent messages and drop the oldest?
Because the next reply depends most on what was just said: the latest question, the last tool result, the most recent correction. Old turns matter less, and much of what they contain has usually been restated or acted on since. Dropping from the oldest end therefore loses the least useful context first. It is a baseline, not the whole policy: real systems also pin the system prompt so it is never dropped, and many summarize the oldest turns instead of discarding them, which keeps facts the conversation still depends on.
Why stop at the first message that does not fit instead of skipping it?
Skipping it would pack more tokens into the budget, but the kept messages would no longer be a contiguous run of the conversation. With counts 5, 100 and 1 and a budget of 10, skipping the 100 would keep 5 and 1 and drop the message between them, so the model would read a reply to something it never saw. A coherent conversation needs every turn between the oldest kept message and the newest one. Stopping at the first message that does not fit guarantees that, and it makes the result easy to predict.
Why trim by token count rather than message count?
Because the context limit is measured in tokens, and messages vary enormously in size. Keeping the last 20 messages can mean a few hundred tokens or far more than the window holds, depending on whether they are short chat replies or pasted documents and tool outputs. Counting tokens makes the limit exact. Count with the same tokenizer the model uses, because different tokenizers split the same text into different numbers of tokens, and an estimate that comes out too low will overflow the window.
Is trimming history the same as context compaction?
Trimming is the simplest form of compaction. It removes whole messages and leaves the rest unchanged, so it is fast and predictable, and it loses whatever the dropped messages said. Other compaction strategies keep some of that information: summarizing old turns into one message, extracting facts into a memory store the agent can query, or shortening large tool outputs. Long-running agents often combine them and fall back to trimming when even the compacted history does not fit. This challenge implements that fallback step.
Explore the topic
See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.
More Challenges
- Retry with Exponential BackoffTools time out and APIs rate-limit — a production agent retries without hammering. Exponential backoff waits longer after each failure (1s, 2s, 4s, 8s…) up to a cap. Compute the delay schedule: delay[i] = min(cap, base·2ⁱ). Solve it in Python or TypeScript.Read →
- Parse a Tool CallWhen a model wants to act, it emits a call like search(query=cats, limit=5). Parse that string into a function name and typed arguments before the harness can dispatch it — the little parser that turns a model's intent into an action. Solve it in Python or TypeScript.Read →
- Run the Goal LoopThe engine of loop engineering: attempt the front task, let an independent verifier judge it, retry failures with state untouched, and stop when the goal is met — or loudly when the cap trips. Implement the whole outer loop as one pure, testable function. Solve it in Python or TypeScript.Read →
- Write a VerifierIn RL from verifiable rewards, the verifier IS the reward — and a gameable one is worse than none, because every false positive is a lie the model learns. Write a verifier a reward-hacking agent can’t fool: recompute the score from ground truth, demand exact task coverage, and compare types-intact. Solve it in Python or TypeScript, with hidden tests.Read →
- Build Your Own Agent LoopStrip an "AI agent" of its mystique and what’s left is a loop: read the model’s next move — tool call or final answer — run the tool, feed the observation back, repeat until it answers or the step cap trips. Implement the whole ReAct inner loop as one pure function. Solve it in Python or TypeScript, with hidden tests.Read →
- Layer NormalizationThe stabilizer wrapped around every Transformer sub-layer: re-center and re-scale a vector to mean 0 and variance 1, then let learned gamma and beta stretch and shift it back — y = gamma·(x−mean)/√(var+eps) + beta. Keeps deep nets trainable. Solve it in Python or TypeScript.Read →