265 2026 02 02 Token Estimation Overhead Adb63d03

Research: Token Estimation Overhead in Pruning

Date: 2026-02-02 Phase: Research Scope: src/tunacode/core/agents/resume/prune.py:161-238

Structure

Token Estimation Pipeline

RequestOrchestrator.run()
  └─> _prepare_message_history()           [main.py:278]
      └─> _log_pruned_tool_outputs()       [main.py:310]
          └─> prune_old_tool_outputs()     [prune.py:161]
              ├─> estimate_part_tokens()   [prune.py:100]    <-- BOTTLENECK
              │   └─> estimate_tokens()    [token_counter.py:10]
              └─> prune_part_content()     [prune.py:121]
                  └─> estimate_tokens()    [token_counter.py:10]  (redundant)

Directory Layout

src/tunacode/
├── utils/messaging/
│   ├── token_counter.py    # Core heuristic: len(text) // 4
│   └── __init__.py         # Exports estimate_tokens()
└── core/agents/resume/
    ├── prune.py            # Backward-scan algorithm (161-238)
    ├── summary.py          # Compaction trigger (uses estimate_tokens)
    ├── sanitize.py         # Cleanup loop (separate bottleneck)
    └── filter.py           # Calls prune_old_tool_outputs()

Key Files

Core Algorithm

• prune.py:161-238 → prune_old_tool_outputs() - main entry point
• prune.py:100-118 → estimate_part_tokens() - per-part token estimation
• prune.py:121-158 → prune_part_content() - mutation and reclaim calculation

Token Estimation

• token_counter.py:7 → CHARS_PER_TOKEN = 4 constant
• token_counter.py:10-14 → estimate_tokens() function: len(text) // 4

Callers

• main.py:310-312 → _log_pruned_tool_outputs() triggers pruning
• filter.py:74 → prepare_history() triggers pruning

Algorithm Phases (prune.py:161-238)

Phase 1: Collection (Lines 188-203)

# O(M × P × L) - scans ALL messages backward
for msg_idx in range(len(messages) - 1, -1, -1):
    for part_idx in range(len(parts) - 1, -1, -1):
        if is_tool_return_part(part):
            tokens = estimate_part_tokens(part, model_name)  # O(L)
            tool_parts.append((msg_idx, part_idx, part, tokens))

Phase 2: Boundary (Lines 210-218)

# O(T) - finds 40k token protection boundary
for i, (_, _, _, tokens) in enumerate(tool_parts):
    accumulated_tokens += tokens
    if accumulated_tokens > protect_tokens:  # 40,000
        prune_start_index = i
        break

Phase 3: Savings (Lines 224-230)

# O(T) - validates 20k minimum threshold
parts_to_prune = tool_parts[prune_start_index:]
total_prunable_tokens = sum(tokens for _, _, _, tokens in parts_to_prune)
if total_prunable_tokens < minimum_threshold:  # 20,000
    return (messages, 0)

Phase 4: Mutation (Lines 232-238)

# O(T × L) - REDUNDANT token estimation
for _, _, part, _ in parts_to_prune:
    reclaimed = prune_part_content(part, model_name)  # re-estimates tokens!

Complexity Analysis

Time Complexity: O(M × P × L)

Worst case example:

• 200 messages × 3 parts × 10,000 chars = 6,000,000 character scans

Space Complexity: O(M × P)

• tool_parts list stores up to M × P tuples
• No deep copies (references only)

Patterns Found

Pattern 1: Redundant Token Calculation

Location: Phase 1 calculates tokens (line 201), Phase 4 recalculates (lines 144, 149)

# Phase 1 - already calculated
tokens = estimate_part_tokens(part, model_name)
tool_parts.append((msg_idx, part_idx, part, tokens))  # stored here!

# Phase 4 - recalculated from scratch
for _, _, part, _ in parts_to_prune:  # token count in tuple IGNORED
    reclaimed = prune_part_content(part, model_name)
    # prune_part_content calls estimate_tokens() twice more (lines 144, 149)

Pattern 2: No Memoization

• Same content estimated multiple times
• No caching by content hash or part ID
• PRUNE_PLACEHOLDER tokens recalculated per part (line 149)

Pattern 3: Unused Parameter

• model_name passed through all functions
• Never actually used in estimation (heuristic is model-agnostic)

Dependencies

Import Chain

estimate_tokens() defined in:
  └─ utils/messaging/token_counter.py:10

Re-exported through:
  └─ utils/messaging/__init__.py:16

Imported by:
  ├─ core/agents/resume/prune.py:11
  └─ core/agents/resume/summary.py:19

Caller Chain

main.py:278 _prepare_message_history()
  └─> main.py:310 _log_pruned_tool_outputs()
      └─> prune.py:161 prune_old_tool_outputs()

filter.py:74 prepare_history()
  └─> prune.py:161 prune_old_tool_outputs()

Symbol Index

Constants (prune.py)

Constants (token_counter.py)

Functions (prune.py)

Data Structures

tool_parts List (prune.py:190)

tool_parts: list[tuple[int, int, Any, int]]
#                      │    │    │    └─ token_count (calculated)
#                      │    │    └────── part object (reference)
#                      │    └─────────── part_index in message.parts
#                      └──────────────── message_index in messages list

Order: Most recent first (backward scan appends newest to end, but iteration order is newest-first)

Bottleneck Analysis

Primary Bottleneck: Phase 1 Collection

Why it's expensive:

1. Iterates ALL messages regardless of early exit conditions
2. Calls estimate_part_tokens() for EVERY tool return part
3. Each call does len(content) on potentially large strings

Measured complexity:

• 200 messages × 3 tool parts × 5000 char average = 3M character operations
• Called on every agent request

Secondary Bottleneck: Phase 4 Redundancy

Why it's wasteful:

1. Token counts already in tool_parts tuple (index 3)
2. prune_part_content() re-estimates original tokens (line 144)
3. prune_part_content() re-estimates placeholder tokens (line 149)
4. Placeholder is constant - should be pre-calculated once

Optimization Opportunities

1. Use pre-calculated tokens from Phase 1 in Phase 4 instead of re-estimating
2. Cache PRUNE_PLACEHOLDER token count as module constant
3. Early termination in Phase 1 once enough tokens collected (don't scan entire history)
4. Batch token estimation - concatenate contents, single length call
5. Incremental tracking - store token counts on parts, update only when content changes