Agent conversation memory: paginated fetch, token budget, eviction

You are building the memory of a conversational agent: the layer that loads a conversation's past messages, keeps what goes to the model under its token limit, and decides which older conversations to forget. The screen comes in parts that build on each other; finish and test each part before the interviewer moves you to the next.

Part 1: load the history page by page

Unless you agree on a different interface with the interviewer, assume:

• Message(id: str, role: str, tokens: int) — one message; role is "system", "user", "assistant" or "tool", and tokens is its given token count.
• fetch_page(cursor: str | None) -> tuple[list[Message], str | None] — given. Returns one page, oldest message first, and the cursor of the next page; the first call passes None. A None cursor or an empty page means there is nothing more. It may raise TransientError.
• load_history(fetch_page) -> list[Message] — yours. Every message, in conversation order.

The loop must always end, even if the store never sends an empty page or hands back a cursor it already gave. Retry a failed call a few times with backoff, without losing or repeating messages.

# None -> ([m1, m2], "c1"),  "c1" -> ([m3], "c2"),  "c2" -> ([], None)
load_history(fetch_page)  -> [m1, m2, m3]        # three calls

Part 2: keep the history under a token limit

• History(limit: int) — the most tokens the model may receive.
• add(message: Message) -> list[str] — appends a message, then drops messages from the oldest end until the total is at most limit. Returns the dropped ids, oldest first. A total equal to the limit fits; a message bigger than the limit on its own leaves the history empty.
• messages() -> list[str] and total() -> int — what would be sent now, in order, and its token total.

Compaction runs after every new message, so it must not re-add the whole history each time.

h = History(100)
h.add(Message("s",  "system",    20))  -> []
h.add(Message("u1", "user",      30))  -> []
h.add(Message("a1", "assistant", 40))  -> []           # total 90
h.add(Message("u2", "user",      25))  -> ["s"]        # 115 is over; dropping s gives 95
h.messages()                           -> ["u1", "a1", "u2"]
h.add(Message("t1", "tool",     120))  -> ["u1", "a1", "u2", "t1"]   # alone over the limit

Part 3: forget whole conversations to cap the listings in context

A shopping agent's context also carries past conversations, oldest first, and each one mentions product listing ids (the same id may appear in many conversations, or twice in one). Too many distinct listings confuse the model.

• evict_conversations(conversations: list[list[str]], max_listings: int) -> list[str] — while the kept conversations mention more than max_listings distinct ids, drop the oldest whole conversation. Return the distinct ids of the conversations left, each once, in the order they first appear.

evict_conversations([["p1", "p2"], ["p2", "p3"], ["p4", "p1"]], 3)  -> ["p4", "p1"]
    # 4 distinct ids. Dropping the first conversation still leaves 4 (p1 is in
    # the third one too); dropping the second leaves p4 and p1.
evict_conversations([["p1", "p1"], ["p1"]], 1)  -> ["p1"]    # 1 distinct id: nothing dropped

Constraints

• Up to 10^5 messages, and up to 10^5 listing mentions across all conversations.
• Token counts are given non-negative integers (no tokenizing).
• add costs amortized O(1) plus the messages it drops; evict_conversations runs in time linear in the number of mentions.

Clarifying questions

• Does the store return pages oldest first or newest first, and in what order within a page?
• Load everything into a list, or stream messages to the caller one page at a time?
• Which failures should be retried, and what happens when a page keeps failing: return what was loaded, or raise?
• Must some messages never be dropped (the system prompt, the newest user turn)? Must a tool call and its result go together?
• What should happen when the newest message alone is over the limit: drop it, keep it, or truncate it?
• In Part 3, does an id stop counting once its oldest mention is dropped, or only once its last one is?

What a strong answer covers

• A pagination loop with one clear exit, a page cap and a set of seen cursors; retries with backoff around a single call, so a retried page is never added twice.
• A deque of messages plus a running total: append on the right, pop on the left in O(1) (unlike list.pop(0)), never re-summing.
• Per-id mention counts for Part 3, so an id leaves the distinct total only when its last kept mention is dropped; one pass to build the counts, one to evict, one to list the ids.
• Edge cases: an empty first page, a total exactly at the limit, an oversized message, a cap of zero, an empty conversation.
• Tests with a fake store (pages, failures, a repeated cursor) and brute-force checks for Parts 2 and 3.

Follow-ups

• Keep the system prompt and the newest user turn always, and drop a tool call together with its results.
• Compaction runs only when the history passes a trigger (say 20,000 tokens) and cuts it to a target (10,000), keeping the longest contiguous run of messages that fits. With counts [9000, 2000, 2500, 3000, 1500, 4000, 2000, 1000], two runs of four fit; which one do you keep?
• Summarize what you drop instead of discarding it, and budget for the summary's own tokens.
• New messages arrive while you are still paging through old ones. How do you avoid gaps and duplicates?