Thoughts about compaction

If we can define what a “good” compaction is, then we can better define its implementation.

Setup:

• You have an agent A, a max context length L. We also have the parameters of the the agent (usually network weights) $\theta$.
• We also have an ordered list of turns, composed of user, assistant and tool calls. We call it the “history” H. We also have a KV-cache K.
  • To be explicit,
    • the history H is stored explicitly in text/tokens.
    • $H=[T_i],i=1\dots n$, where $T_i\in \{U_i,A_i,{\text{tool}}_i\}$ (one step of the history is either assistant, user, or tool).
  • In most settings, len(H) = len(K), and K is defined as prefill(H) = K.
    • Here the function len() will always be implicitly measuring the number of tokens.
  • However, technically, the history H can be unbounded in length, however the the KV-cache cannot grow beyond len(K) < L, because of memory and performance constraints.
  • This is where compaction comes in.
• Finally, we have the state of the world, Z, which is updated by the actions performed during the history. We also have a goal G, which is a specific desired state of the world.

Defining compaction

• Compaction C is an tool necessary to complete goal G where the model needs an horizon longer than its own context length i.e. len(K) > L.

• One can consider compaction as one of the tools available to the model.

• Compaction is a function of the history, and outputs a compaction S of the history (usually in text form), where we have $C_{\theta }(H)=S$. For simplicity, we will assume that compaction is performed by the same neural network used by the agent.

  • It also resets the KV cache for the current model.

• Thus, one can now define the history as $H=[T_i],i=1\dots n$, where $H_i\in \{U_i,A_i,{\text{tool}}_i,S_i\}$ (one step of the history is either assistant, user, tool or a compaction event).

• Compaction events effectively divide the history into “attempts” or “explorations” E, where $E_i=[T_j]\text{ for }j=k,\dots k+n$.

  • If the exploration is not the first one, then the first turn of the exploration must always be a compaction S. (This is a simplification to make the framing easier, one could technically carry over a part of the previous exploration.)

• The history can now be also expressed as a series of explorations.

What is a good compaction (in theory)

• We would like to define what a good compaction is, such that we can optimize the function.

• Let’s assume that the goal G can be verified with a grader function that gives a score to the state, $f(Z)$. The simplest form being $f(H,Z)=1\{Z=G\}$.

• Ultimately, the most end-to-end definition is that compaction is just one of the steps of the exploration, not much different, from other turns from the assistant.

• Thus, the best compaction function is $C_{\theta }={\text{argmin}}_{\theta }f(H,Z)$.

• Ultimately, a good compaction function is ultimately the one that allows the agent to reach the goal state, possibly over a very long horizon, spanning multiple explorations.

  • I think this point is important to further clarify.
  • Indeed, it is quite natural to think that compaction is effectively equivalent to summarization, and that a good compaction function should allow a “lossless” reconstruction of the history H, or at least the last exploration E.
    • A counter-example to this is, for example, if the first exploration $E_1$ was composed of a user prompt U, and then a succession of tool calls (which all suffered from timeouts), up until the exhaustion of the context length.
    • In this case, the optimal compaction result might be $C_{\theta }(E_1)=U$, just reiterating the user prompt.

• A likely useful extension to compaction, to maximize our chances that it will enable the agent to reach its goal, would be to allow our compaction function $C$ to also update the state of the world $Z$.

  • For a more concrete example, compaction could write/update a scratchpad or markdown file, which could contain a summary of the full history H, and then only pick or point to the useful parts in its output $C_i$.
  • This is also necessary to preserve multi-modal inputs.

What I’m advocating for is that:

• old context becomes queryable history → fresh context → agent restores what it needs is a superior implementation to  old conversation → generated summary → next context.

What actually matters, the technical details

How to reward the model?

• Practically, the length of the history can be much longer than the supported context length of the agent.

• However, because compaction also resets the KV-cache, this doesn’t matter, as the agent is “blind” to previous and future explorations.

• Thus, for the model to learn what good compaction, we must have a surrogate grading function $g$ that can grade an exploration.

  • Again, an end-to-end view would be $g(E_i,Z)=1\{Z=G\}$
  • However, this means that a given exploration can only be graded if the agent has finished exploring.

• This raises multiple issues:

  • If such exploration takes many turns, the very first exploration will be stale w.r.t to the latest network weights.
    • This is assuming large scale async RL with many problems being explored at the same time.
  • How does one reward an agent to be “relentless”?
    • Indeed, very hard problems such as curing cancer, may not be within reach of the model capacity (at least at this time $t$). Or some problems may require thousands of explorations, which is practically not feasible to fit within an RL run. (But it may be feasible in isolation, once the model is not training!)
    • We must still be able to reward the model for trying very hard, on very hard problems.

• There may be many optimal compaction functions, we likely also want the compaction function that minimizes e2e latency or minimizes the number of total generated tokens.

Auto-compaction vs manual compaction?

• By manual compaction, I mean any system that triggers a model compaction when it reaches a fixed threshold of its context length e.g. 80%.

• By auto compaction, I mean a system where the agent autonomously decides whether to compact or not. This means compaction may trigger earlier than the max window context

  • Example: OAI with 5.6 Sol (twitter) where OAI seems to be triggering compaction near the 400k token limit, instead of 1M.

• Pros and cons

  • Manual compaction has the advantage of
    • being simple to implement
    • model-agnostic.
  • Auto-compaction has the advantage of
    • optimizable end-to-end and thus being model-aware
    • reduce inference costs (early compaction reduces KV-cache pressure and decoding latency) both at training and inference.

Dealing with multi-modal inputs

• If we are dealing a model that has multiple modalities in, and only text-out, we must make an effort to make carrying over auxiliary state (images, videos, files) a first class citizen, especially if they were provided by the user.

What should one keep from the previous exploration ?

• The most simple formulation is to drop everything but the compaction, when starting a new exploration. This allows the model to choose exactly what to keep or not.

• However, this might prove not controllable enough, and there may be a few invariants that we want to enforce e.g. keeping verbatim copies of the user prompts.

• This is for example, what a few harnesses do.

  • After compaction, the context is rebuilt from near-scratch. Only three things carry over:
  1. Your own messages — real user turns, kept verbatim.
  2. Agent messages under some tokens budget — except the final answer, which is dropped on purpose.
  3. One summary blob, appended at the end.