Multi-turn conversation cost optimization: flattening the O(n²) token growth curve in LLM agents

The O(n²) cost growth explained with real numbers

The quadratic growth pattern emerges from a simple mechanic: LLMs are stateless, so your application re-sends the entire conversation history on every API call. At GPT-4o pricing ($2.50/MTok input, $10.00/MTok output), the input token cost per turn scales with the accumulated message count.

• Turn-by-turn cost accumulation. Assuming each turn adds approximately 1,000 tokens to the conversation (a realistic average for a mix of user messages and assistant responses): Turn 1: 1,000 input tokens = $0.0025. Turn 5: 5,000 input tokens = $0.0125. Turn 10: 10,000 input tokens = $0.025. Turn 20: 20,000 input tokens = $0.050. Turn 35: 35,000 input tokens = $0.0875. Turn 50: 50,000 input tokens = $0.125. The total cost of a 50-turn conversation in input tokens alone: the sum of 1,000 + 2,000 + ... + 50,000 = 1,275,000 tokens = $3.19 in input tokens. Output cost is separate and depends on response length.
• The fleet-level impact. An AI support agent handling 100 conversations per day that average 25 turns: total input tokens per day = sum of 1,000 through 25,000 for each conversation = 325,000 tokens per conversation × 100 conversations = 32,500,000 tokens/day. At $2.50/MTok: $81.25/day in input tokens. Monthly: $2,437. If those conversations averaged only 10 turns instead of 25 (through better task decomposition or window management): 55,000 tokens per conversation × 100 = 5,500,000 tokens/day = $13.75/day. Monthly: $412. The difference — $2,025/month — is recoverable with conversation management, not model changes. For a broader view of controlling costs across complex agent deployments, see autonomous agent cost control best practices.
• Why context window truncation is not the solution. If you let conversations grow until they hit the context window limit and then let the provider truncate old messages silently, you get the worst of both worlds: you pay for the full long context on the last N calls before truncation, and you lose the early conversation context without semantic preservation. Explicit, application-level conversation management is always preferable to relying on provider-side truncation. See context window truncation alerts for how to detect when this is happening.
• Claude Sonnet 3.5 at the same scale. Input: $3.00/MTok. A 50-turn conversation: 1,275,000 input tokens = $3.83. Fleet of 100 conversations/day averaging 25 turns: $97.50/day. The absolute numbers differ but the quadratic shape is identical. Rolling summary at 15-turn intervals reduces this to approximately $20/day — an 80% reduction. The strategy is provider-agnostic.

Four strategies ranked by effectiveness and the crossover points where each wins

There is no single best strategy for all agents. The right choice depends on conversation length, semantic requirements, and implementation complexity budget.

• Strategy 1: Message window (keep last N turns). The simplest approach: before each API call, truncate the conversation history to the last N turns (typically 10–20). Turn 21 and later never see the context from turns 1–10. This is highly effective for task-focused agents where early context is genuinely irrelevant (e.g., the user asked 15 unrelated questions in sequence). It fails for agents where early decisions constrain later behavior (e.g., a coding agent that set a project structure in turn 3 that turn 25 needs to know about). Cost reduction: roughly linear — if you keep the last 10 turns instead of all 50, input cost per call is capped at 10,000 tokens instead of 50,000. At GPT-4o rates, this caps per-call input cost at $0.025 vs $0.125. Implementation complexity: very low. Recommended for: task-focused agents with stateless or loosely-coupled turns.
• Strategy 2: Rolling summary. Instead of discarding old turns, periodically summarize them into a compact summary message. When the conversation exceeds N turns (typically 15–20), pass the oldest batch to a cheap, fast model (Claude Haiku at $0.25/MTok input and $1.25/MTok output, or GPT-4o-mini at $0.15/MTok input) and replace those turns with a single summary message. The summary might be 200–400 tokens instead of the 1,500–3,000 tokens it replaced — a 65–90% reduction in the historical portion. Cost reduction: 65–90% on tokens older than the summary threshold. Net cost including summary generation: the 1,500-token batch costs ~$0.00075 to summarize with Haiku, saving ~$0.004 in repeated input costs from that point forward. Crossover point: rolling summary beats pure windowing for agents where semantic context from early turns is needed after turn 20. Implementation complexity: medium. Recommended for: support agents, multi-step research agents, longer coding sessions.
• Strategy 3: Retrieval-augmented history. Store all conversation turns as vector embeddings. Before each API call, retrieve the K most semantically relevant prior turns and include only those in context. This approach has the best semantic retention for very long conversations but the highest implementation complexity: you need a vector store, an embedding model, and a retrieval query for each call. Cost reduction: potentially 80–95% on long conversations (>50 turns), because you include only 3–8 relevant turns per call regardless of total history length. Crossover point: retrieval beats rolling summary at approximately 40+ turns for agents where semantic precision matters more than recency. Implementation complexity: high. Recommended for: long-running research assistants, agents with days-long session spans, or agents where any prior turn may be relevant.
• Strategy 4: Semantic deduplication. Before including a turn in context, check if it is semantically similar (cosine similarity > 0.92) to a turn already in the context window. If so, omit it. This handles the common pattern where users repeat themselves (“Can you summarize that again?” appearing six times) or the agent echoes prior statements redundantly. Deduplication alone typically reduces context by 10–20%, which is useful but not transformative. Its real value is as a complement to windowing or summarization, not a replacement. Implementation complexity: low to medium (requires embedding calls for each new turn, but the existing turns are already embedded if you’re using retrieval). Recommended for: combine with windowing or summarization for an additional 10–20% reduction at minimal overhead.

Per-provider conversation caching and the prefix stability requirement

Both Anthropic and OpenAI cache conversation prefixes, which adds a fourth lever to conversation cost control on top of the four strategies above.

• Anthropic 5-minute prefix cache. If consecutive API calls within a session have an identical message prefix, Anthropic caches that prefix at $0.30/MTok instead of $3.00/MTok. For a multi-turn conversation where the first 15 turns are stable and the 16th turn is new, turns 1–15 are cache-read tokens (90% cheaper) and only turn 16 is new input. The key constraint: the prefix must be byte-identical across calls. Even adding a space to the system prompt breaks the cache. Combine this with message windowing by keeping the window anchored to the oldest non-truncated turn: the portion of the window that hasn’t changed between calls will be a cache hit.
• OpenAI automatic conversation caching. OpenAI automatically caches conversation prefixes of at least 1,024 tokens. In a 25-turn conversation where turn 24 is the most recent new turn, turns 1–23 are eligible for the cache if the call is within the cache window. For sequential conversations (each turn follows closely after the previous), cache hit rates of 70–90% are achievable, reducing effective input cost by $1.75/MTok (the difference between $2.50 and $0.75 cached rate). For intermittent conversations (turns spaced hours apart), the cache expires between calls and the full rate applies. For detailed caching strategies with OpenAI, see OpenAI Assistants API budget control.
• Combining caching with windowing. The most cost-effective pattern is message windowing (to cap the growing tail) combined with prefix caching (to discount the stable historical portion). The window anchors the cache prefix: the first N turns of the window are stable between sequential calls, so they are cache hits. Only the newest turn is new input. Effective cost per call in a windowed, cached conversation of 10 turns: 9 turns × cache rate + 1 new turn × standard rate. For a 10-turn window at 1,000 tokens/turn on GPT-4o: (9,000 × $0.75 + 1,000 × $2.50) / 1,000,000 = $0.00925 vs $0.025 without caching — a 63% additional reduction on top of the windowing savings.

Python implementation: RollingConversation with summarization and RunGuard cost tracking

This implementation provides a RollingConversation class with configurable window size, automatic batch summarization using a cheap model, and RunGuard’s ConversationCostTracker for per-turn cost reporting.

import anthropic
import runguard
from dataclasses import dataclass, field
from typing import Callable

# Module-level client reuse (connection pooling — see cold start guide)
_client = anthropic.Anthropic()

# RunGuard per-turn cost tracker
cost_tracker = runguard.ConversationCostTracker(
    on_turn_cost=lambda ctx: print(
        f"[Turn {ctx.turn_number}] input={ctx.input_tokens} output={ctx.output_tokens} "
        f"cost=${ctx.turn_cost_usd:.6f} cumulative=${ctx.cumulative_cost_usd:.4f}"
    ),
    on_budget_exceeded=lambda ctx: (_ for _ in ()).throw(
        runguard.BudgetExceededError(
            f"Conversation budget exceeded at turn {ctx.turn_number}: "
            f"${ctx.cumulative_cost_usd:.4f}"
        )
    ),
    session_budget_usd=2.00,  # Abort conversation if cumulative cost exceeds $2
)


@dataclass
class Message:
    role: str  # "user" or "assistant"
    content: str


@dataclass
class RollingConversation:
    """
    Multi-turn conversation manager with rolling summary and RunGuard cost tracking.

    Strategy:
    - Keep the most recent max_window_turns turns verbatim in context
    - When conversation exceeds summarize_threshold turns, summarize the oldest batch
    - Replace the summarized batch with a compact summary message
    - Use a cheap model (Haiku) for summarization to minimize summary cost
    """
    max_window_turns: int = 20
    summarize_threshold: int = 15
    summarize_batch_size: int = 10
    summary_model: str = "claude-haiku-3-5"
    main_model: str = "claude-sonnet-4-5"
    system_prompt: str = ""
    messages: list[Message] = field(default_factory=list)
    _turn_number: int = field(default=0, init=False)

    def _should_summarize(self) -> bool:
        return len(self.messages) >= self.summarize_threshold

    def _summarize_oldest_batch(self) -> None:
        """Summarize the oldest summarize_batch_size messages and replace them."""
        batch = self.messages[:self.summarize_batch_size]
        remaining = self.messages[self.summarize_batch_size:]

        # Format batch for summarization
        batch_text = "\n".join(
            f"{m.role.upper()}: {m.content}" for m in batch
        )

        summary_response = _client.messages.create(
            model=self.summary_model,
            max_tokens=400,
            messages=[
                {
                    "role": "user",
                    "content": (
                        "Summarize the following conversation excerpt into a concise paragraph "
                        "preserving all key decisions, facts, and context needed for future turns. "
                        "Be specific — include names, values, and conclusions reached.\n\n"
                        f"{batch_text}"
                    ),
                }
            ],
        )

        summary_text = summary_response.content[0].text
        summary_cost = (
            summary_response.usage.input_tokens * 0.25 / 1_000_000 +
            summary_response.usage.output_tokens * 1.25 / 1_000_000
        )
        print(f"[Summary] Compressed {self.summarize_batch_size} turns to {len(summary_text)} chars "
              f"(cost: ${summary_cost:.6f})")

        # Replace the batch with a single summary message
        summary_message = Message(
            role="user",
            content=f"[CONVERSATION SUMMARY — earlier turns]: {summary_text}",
        )
        self.messages = [summary_message] + remaining

    def _build_api_messages(self) -> list[dict]:
        """Build the message list for the API call, applying window truncation."""
        messages = self.messages
        if len(messages) > self.max_window_turns:
            messages = messages[-self.max_window_turns:]
        return [{"role": m.role, "content": m.content} for m in messages]

    def chat(self, user_message: str) -> str:
        """Send a user message and return the assistant response."""
        self._turn_number += 1
        self.messages.append(Message(role="user", content=user_message))

        # Summarize if threshold reached (before building API messages)
        if self._should_summarize():
            self._summarize_oldest_batch()

        api_messages = self._build_api_messages()

        system = [
            {
                "type": "text",
                "text": self.system_prompt,
                "cache_control": {"type": "ephemeral"},  # Cache system prompt
            }
        ] if self.system_prompt else []

        response = _client.messages.create(
            model=self.main_model,
            max_tokens=1024,
            system=system,
            messages=api_messages,
        )

        assistant_text = response.content[0].text
        self.messages.append(Message(role="assistant", content=assistant_text))

        # Report per-turn cost to RunGuard
        cache_read = getattr(response.usage, "cache_read_input_tokens", 0)
        cache_write = getattr(response.usage, "cache_creation_input_tokens", 0)
        standard_input = response.usage.input_tokens - cache_read - cache_write

        input_cost = (
            standard_input * 3.00 / 1_000_000 +
            cache_write * 3.75 / 1_000_000 +
            cache_read * 0.30 / 1_000_000
        )
        output_cost = response.usage.output_tokens * 15.00 / 1_000_000

        cost_tracker.record_turn(
            turn_number=self._turn_number,
            input_tokens=response.usage.input_tokens,
            output_tokens=response.usage.output_tokens,
            turn_cost_usd=input_cost + output_cost,
        )

        return assistant_text


# Usage example
def run_support_conversation():
    conv = RollingConversation(
        system_prompt=(
            "You are a helpful technical support agent. "
            "Resolve issues efficiently and ask clarifying questions when needed."
        ),
        max_window_turns=20,
        summarize_threshold=15,
        summarize_batch_size=10,
    )

    turns = [
        "I’m having trouble connecting to the database.",
        "The error message is: connection refused on port 5432.",
        "I’m using PostgreSQL 15 on Ubuntu 22.04.",
        "The service is running — I can see it with systemctl status.",
        # ... more turns
    ]

    for turn in turns:
        response = conv.chat(turn)
        print(f"User: {turn}")
        print(f"Assistant: {response}\n")

The critical design decision in this implementation is that summarization happens before _build_api_messages(), not after. This means the summary is immediately available for the current call, not deferred to the next one. The cost_tracker.record_turn() call uses the actual usage fields from the API response — including cache read and write tokens — for accurate per-turn cost reporting. RunGuard’s on_budget_exceeded callback fires if the cumulative conversation cost crosses the session budget before the agent can accumulate runaway spend. For fleet-level cost analysis across many concurrent conversations, see agent workflow orchestration cost analysis.

TypeScript implementation: ConversationManager with window and rolling summary

The TypeScript implementation uses a class-based design compatible with Express, Next.js, and serverless environments, with OpenAI as the provider and RunGuard’s TypeScript SDK for per-turn tracking.

import OpenAI from "openai";
import RunGuard from "@runguard/sdk";

const client = new OpenAI({ maxRetries: 0 });

const costTracker = new RunGuard.ConversationCostTracker({
  sessionBudgetUsd: 2.0,
  onTurnCost: (ctx) => {
    console.log(
      `[Turn ${ctx.turnNumber}] ` +
      `input=${ctx.inputTokens} output=${ctx.outputTokens} ` +
      `cost=$${ctx.turnCostUsd.toFixed(6)} cumulative=$${ctx.cumulativeCostUsd.toFixed(4)}`
    );
  },
  onBudgetExceeded: (ctx) => {
    throw new Error(
      `Conversation budget exceeded at turn ${ctx.turnNumber}: $${ctx.cumulativeCostUsd.toFixed(4)}`
    );
  },
});

interface Message {
  role: "user" | "assistant" | "system";
  content: string;
}

interface ConversationManagerOptions {
  systemPrompt?: string;
  maxWindowTurns?: number;
  summarizeThreshold?: number;
  summarizeBatchSize?: number;
  mainModel?: string;
  summaryModel?: string;
}

class ConversationManager {
  private messages: Message[] = [];
  private turnNumber = 0;
  private readonly systemPrompt: string;
  private readonly maxWindowTurns: number;
  private readonly summarizeThreshold: number;
  private readonly summarizeBatchSize: number;
  private readonly mainModel: string;
  private readonly summaryModel: string;

  constructor(options: ConversationManagerOptions = {}) {
    this.systemPrompt = options.systemPrompt ?? "";
    this.maxWindowTurns = options.maxWindowTurns ?? 20;
    this.summarizeThreshold = options.summarizeThreshold ?? 15;
    this.summarizeBatchSize = options.summarizeBatchSize ?? 10;
    this.mainModel = options.mainModel ?? "gpt-4o";
    this.summaryModel = options.summaryModel ?? "gpt-4o-mini";
  }

  private shouldSummarize(): boolean {
    return this.messages.length >= this.summarizeThreshold;
  }

  private async summarizeOldestBatch(): Promise<void> {
    const batch = this.messages.slice(0, this.summarizeBatchSize);
    const remaining = this.messages.slice(this.summarizeBatchSize);

    const batchText = batch
      .map((m) => `${m.role.toUpperCase()}: ${m.content}`)
      .join("\n");

    const summaryResponse = await client.chat.completions.create({
      model: this.summaryModel,
      max_tokens: 400,
      messages: [
        {
          role: "user",
          content:
            "Summarize the following conversation excerpt into a concise paragraph " +
            "preserving all key decisions, facts, and context needed for future turns. " +
            "Be specific — include names, values, and conclusions reached.\n\n" +
            batchText,
        },
      ],
    });

    const summaryText = summaryResponse.choices[0].message.content ?? "";
    const summaryInputCost = (summaryResponse.usage?.prompt_tokens ?? 0) * 0.15 / 1_000_000;
    const summaryOutputCost = (summaryResponse.usage?.completion_tokens ?? 0) * 0.60 / 1_000_000;
    console.log(
      `[Summary] Compressed ${this.summarizeBatchSize} turns, ` +
      `cost: $${(summaryInputCost + summaryOutputCost).toFixed(6)}`
    );

    const summaryMessage: Message = {
      role: "user",
      content: `[CONVERSATION SUMMARY — earlier turns]: ${summaryText}`,
    };
    this.messages = [summaryMessage, ...remaining];
  }

  private buildApiMessages(): OpenAI.ChatCompletionMessageParam[] {
    let messages = this.messages;
    if (messages.length > this.maxWindowTurns) {
      messages = messages.slice(-this.maxWindowTurns);
    }

    const apiMessages: OpenAI.ChatCompletionMessageParam[] = [];
    if (this.systemPrompt) {
      apiMessages.push({ role: "system", content: this.systemPrompt });
    }
    apiMessages.push(...messages.map((m) => ({ role: m.role, content: m.content })));
    return apiMessages;
  }

  async chat(userMessage: string): Promise<string> {
    this.turnNumber++;
    this.messages.push({ role: "user", content: userMessage });

    if (this.shouldSummarize()) {
      await this.summarizeOldestBatch();
    }

    const apiMessages = this.buildApiMessages();

    const response = await client.chat.completions.create({
      model: this.mainModel,
      max_tokens: 1024,
      messages: apiMessages,
    });

    const assistantText = response.choices[0].message.content ?? "";
    this.messages.push({ role: "assistant", content: assistantText });

    // Extract cost data from response
    const inputTokens = response.usage?.prompt_tokens ?? 0;
    const outputTokens = response.usage?.completion_tokens ?? 0;
    const cachedTokens = response.usage?.prompt_tokens_details?.cached_tokens ?? 0;
    const uncachedInput = inputTokens - cachedTokens;

    const inputCost = (uncachedInput * 2.50 + cachedTokens * 0.75) / 1_000_000;
    const outputCost = outputTokens * 10.00 / 1_000_000;

    costTracker.recordTurn({
      turnNumber: this.turnNumber,
      inputTokens,
      outputTokens,
      turnCostUsd: inputCost + outputCost,
    });

    return assistantText;
  }

  getStats(): {
    turnCount: number;
    activeMessages: number;
    estimatedContextTokens: number;
  } {
    return {
      turnCount: this.turnNumber,
      activeMessages: this.messages.length,
      estimatedContextTokens: Math.ceil(
        this.messages.reduce((sum, m) => sum + m.content.length, 0) / 4
      ),
    };
  }
}

// Usage example
async function runAgentConversation(): Promise<void> {
  const manager = new ConversationManager({
    systemPrompt:
      "You are a helpful technical support agent. " +
      "Resolve issues efficiently and ask clarifying questions when needed.",
    maxWindowTurns: 20,
    summarizeThreshold: 15,
    summarizeBatchSize: 10,
    mainModel: "gpt-4o",
    summaryModel: "gpt-4o-mini",
  });

  const turns = [
    "I’m having trouble connecting to the database.",
    "The error is: connection refused on port 5432.",
    "PostgreSQL 15 on Ubuntu 22.04.",
    "The service is running according to systemctl.",
  ];

  for (const turn of turns) {
    const response = await manager.chat(turn);
    console.log(`User: ${turn}`);
    console.log(`Assistant: ${response}`);
    console.log("Stats:", manager.getStats());
  }
}

The getStats() method is a lightweight observability endpoint: it gives you the active message count and an estimated context token size without an API call. Wire this to your monitoring dashboard to track how conversation state grows in production. When estimatedContextTokens climbs unexpectedly between deployments, it typically signals that the summarization threshold has been misconfigured or the summarization model is generating unusually verbose summaries. Combined with RunGuard’s per-turn cost callbacks, you have full visibility into both token volume and dollar spend per conversation turn. For additional context on managing costs in complex multi-agent pipelines, see multi-agent orchestration cost control.

Crossover analysis: when to switch strategies as conversations grow

No single strategy dominates across all conversation lengths. Choosing the wrong strategy for your workload’s typical turn count is a common source of both unnecessary cost and degraded agent performance.

• 1–10 turns: no intervention needed. At fewer than 10 turns, conversation history is small enough that the overhead of summarization or retrieval exceeds the savings. A 10-turn conversation at 1,000 tokens/turn costs $0.025 at GPT-4o input rates. The cost to summarize even 5 of those turns with GPT-4o-mini is ~$0.001 — saving perhaps $0.005 in future calls. The ROI is marginal at this scale. Use simple message passing without management overhead.
• 10–30 turns: message windowing wins. A window of the last 15–20 turns caps input cost while maintaining high recency context. If your agent’s tasks are typically resolved within 20 turns, windowing alone is sufficient. For a 25-turn conversation with a 15-turn window, input tokens per call cap at 15,000 vs the unconstrained 25,000 — a 40% reduction at near-zero complexity cost.
• 30–60 turns: rolling summary outperforms windowing. Beyond 30 turns, the probability increases that early context is semantically relevant to later turns. A rolling summary preserves this context in compact form while keeping the in-context message count bounded. For a 50-turn conversation with batch summarization every 10 turns, the context window contains the current summary (200 tokens) plus the last 15 turns (15,000 tokens), totaling ~15,200 tokens per call vs 50,000 without management. Cost reduction: ~70%.
• 60+ turns: retrieval-augmented history. For agents with sessions spanning dozens or hundreds of turns — long-running research, multi-day coding projects, ongoing customer relationships — a vector store enables retrieval of the K most relevant prior turns for each new message. The context window contains the system prompt, the retrieved relevant turns (500–3,000 tokens), and the recent window (3,000–5,000 tokens), rather than the full accumulated history. This is the most complex implementation but the only approach that scales to truly long conversations without semantic degradation. See AI agent memory consolidation cost optimization for a full treatment of this architecture.