AIエージェントのループに隠されたO(N²)の課金 — 測定とベンチマークMost AI agents resend their full transcript each loop iteration, causing O(N²)…

Autonomous coding and reasoning agents have become a standard way to automate multi-step work, but a recent benchmark highlights a cost pattern that many teams overlook: most AI agents resend their entire conversation transcript on every loop iteration, which drives token consumption to grow quadratically, or O(N²), as a task gets longer. For anyone paying per token, this matters because both the bill and the latency can balloon well before an agent finishes a complex, multi-session job.

The mechanism is straightforward. An agent works by repeatedly calling a language model in a loop: it sends the current context, receives an action or a piece of reasoning, executes it, appends the result, and calls the model again. Because most large language models are stateless between calls, the conventional way to preserve continuity is to include the full running transcript each time. If each step adds roughly a fixed amount of text, then step one sends a short prompt, step two sends that plus the new content, and so on. Summed across N steps, the total tokens processed scale with the square of the number of steps. That quadratic curve is why the analysis frames the problem as O(N²) rather than a linear cost.

The reported measurement compares that naive resend approach against a compact memory strategy, in which the agent stores a condensed representation of prior work and recalls only what is relevant instead of replaying everything. According to the benchmark, calling compact memory in realistic multi-session tasks used 62.8 to 85.9 percent fewer context tokens than full retransmission. The write-up presents the measurement results, the method used to obtain them, and an offline component, which suggests the comparison was run under controlled conditions rather than inferred from theory alone.

The compact memory idea is not new in spirit, but the contribution here appears to be quantifying the savings on concrete tasks. Memory in agent frameworks typically takes a few forms: summarizing older turns into shorter notes, storing facts in an external store such as a vector database and retrieving them on demand, or maintaining a structured scratchpad that captures decisions and state without every intermediate token. Each approach trades some fidelity for a much smaller working context, and the benchmark's wide range likely reflects how different task types and memory designs recover different amounts of that overhead. Multi-session workloads, where an agent returns to a project across separate runs, are an especially clear case, because a fresh session would otherwise reload a long history that a compact memory can compress.

This tension is relevant to agentic coding tools such as Cursor, which is the context in which the analysis was published. Editors and assistants that iterate over a codebase run exactly the kind of loops described here, accumulating file contents, diffs, test output, and tool results across many steps. As those transcripts grow, the effective context sent per iteration grows with them, so the choice between replaying everything and recalling a summary has a direct effect on cost and responsiveness.

It is worth noting that the industry already offers partial mitigations that operate alongside memory design. Prompt caching, offered in various forms by major model providers, lets repeated prefixes be reused so that resending a long transcript is cheaper than paying full price each time. Longer context windows reduce the risk of truncation but do not by themselves flatten the O(N²) curve, since the tokens still have to be processed on every call. Compact memory addresses the growth at its source by keeping the working context small, which is a different lever than caching or window size, and the approaches can be combined.

Readers should treat the specific 62.8 to 85.9 percent figures as results from one benchmark rather than a universal guarantee, since outcomes depend on the tasks, the memory implementation, and how much of the transcript is genuinely needed for correct behavior. Aggressive compaction can drop details an agent later requires, so the practical goal is usually to balance token savings against reliability. Even so, the underlying point is well grounded: naively resending the full transcript scales poorly, and measuring the alternative gives teams a concrete basis for deciding when a memory layer is worth the added engineering complexity. For cost-sensitive deployments running long or repeated agent sessions, that measurement is a useful starting point for optimization.