# ADR-0009: Token-Budget-Aware Batch Planning

## Status

✅ Accepted

## Context

omni-dev's `twiddle` and `check` commands process a branch's commits by sending them to an
AI model. A single branch may contain anywhere from one commit to dozens, and commit sizes
vary enormously: a one-line typo fix may occupy a few hundred tokens while a large
refactoring diff may consume tens of thousands.

Two naive approaches were considered first:

- **One AI request per commit.** Correct and simple, but wasteful: the model receives no
  cross-commit context, and the number of API round-trips equals the number of commits.
  For a branch with twenty commits, twenty sequential API calls add significant latency even
  with parallelism, because each round-trip incurs network and model startup overhead.

- **One AI request for all commits.** Minimises round-trips, but fails when the total
  token cost of all commits exceeds the model's input context window. Commit diffs are
  unbounded in size; a branch touching many large files may produce hundreds of thousands
  of tokens of diff content. Sending everything in one request is not reliably possible.

The core tension is between *minimising round-trips* (favouring large batches) and *staying
within the model's context window* (requiring bounded batches). The right batch boundary is
not a fixed commit count but a function of each commit's actual token cost.

Three batching strategies were evaluated:

- **Fixed-count batching** (the original `--batch-size` flag). Simple to implement and
  explain, but ignores commit size. A batch of five large commits may exceed the context
  window while a batch of five small commits wastes most of it. The flag has been removed.

- **Token-budget-aware bin-packing.** Groups commits by estimated token cost so that each
  batch fits within the model's context window. Requires token estimation, but produces
  batches that are as large as possible without overflowing.

- **Dynamic splitting at request time.** Send all commits in one request; if it fails,
  bisect and retry. Simpler planning but results in wasted AI calls on predictably oversized
  inputs.

## Decision

We will plan batches in `src/claude/batch.rs` using a **first-fit-decreasing bin-packing
algorithm** driven by per-commit token estimates. This runs before any AI calls are made,
so no tokens are wasted on requests that are certain to exceed the context window.

### Token estimation

Each commit's token cost is estimated without reading diff files into memory. The
`estimate_commit_tokens` function uses `fs::metadata` (a single `stat` syscall) to get the
diff file size, then sums it with the lengths of the diff summary, original message, and
proposed message fields. The character count is converted to a token estimate using a
conservative ratio of 2.5 characters per token with a 20% safety margin — code diffs
tokenise less efficiently than prose due to short tokens (operators, brackets, whitespace)
with observed ratios as low as 2.0 characters per token. A fixed per-commit metadata
overhead of 120 tokens (`PER_COMMIT_METADATA_OVERHEAD_TOKENS`) is added to account for
YAML field formatting.

The available batch capacity subtracts the system prompt token count and a fixed
`RepositoryViewForAI` envelope overhead of 150 tokens (`VIEW_ENVELOPE_OVERHEAD_TOKENS`)
from the model's input context limit, then applies a 10% headroom factor
(`BATCH_CAPACITY_FACTOR = 0.90`) to absorb YAML serialisation variance (indentation,
literal block markers) that shifts actual token counts beyond the character-based estimate.
Both overhead constants are `pub(crate)` so that the split dispatch layer (ADR-0017) can
reuse them for consistent capacity calculations. A third constant,
`USER_PROMPT_TEMPLATE_OVERHEAD_TOKENS` (1000 tokens), accounts for instruction text in the
user prompt template and is used by split dispatch when computing per-chunk capacity.

### Bin-packing algorithm

`plan_batches` sorts commits largest-first (first-fit-decreasing order), then places each
commit into the first existing batch with sufficient remaining capacity. If no batch fits,
a new solo batch is created. This greedy approach produces near-optimal packing for typical
commit distributions without requiring an exponential search.

Commits that individually exceed the batch capacity receive solo batches. These trigger
per-file split dispatch at request time (see ADR-0017) to fit the payload within the
model's limits.

### Map-reduce execution

The batch plan drives a two-phase execution in `twiddle` and `check`:

**Map phase:** batches are processed in parallel, bounded by a Tokio semaphore whose size
is the `--concurrency` flag (default 4). Each batch becomes a single AI request, returning
amendments (`twiddle`) or a check report (`check`).

**Reduce phase (twiddle only):** after all batches complete, an optional cross-commit
coherence pass refines the amendments for consistency in terminology and scope naming across
commits. The coherence pass is skipped when all commits fit into a single batch (the AI
already saw all commits together and produced a coherent result), and can be disabled
explicitly with `--no-coherence`.

### Concurrency control

`--concurrency` (default 4) controls the number of simultaneous AI requests. It replaced
the now-removed `--batch-size` flag. The two flags are not equivalent: `--batch-size`
controlled how many commits were grouped per request (count-based); `--concurrency`
controls how many requests run in parallel. Batch membership is now determined entirely by
token budget, not by a count.

## Consequences

**Positive:**

- **Context window is respected without manual tuning.** The batch planner adapts to the
  model in use and the actual sizes of commits. A branch with one large commit and ten small
  ones produces two batches without any user configuration.

- **Round-trips are minimised within constraints.** The bin-packing algorithm groups as
  many commits as possible into each request. For typical branches where all commits fit in
  one batch, the tool makes a single AI call regardless of commit count.

- **Cross-commit context is preserved within batches.** When multiple commits share a
  batch, the AI sees them together and can apply consistent reasoning (e.g. unified scope
  naming, related change descriptions). The coherence pass extends this across batch
  boundaries.

- **Planning is cheap.** Token estimation uses `stat` syscalls, not file reads. For a
  branch with fifty commits, planning completes in milliseconds before any AI call is made.

**Negative:**

- **Estimates are approximate.** The character-to-token ratio varies by language and diff
  content. The conservative 2.5 chars/token ratio with 20% safety margin and 10% batch
  headroom absorb typical variance, but an unusually token-dense commit (e.g. a diff of
  minified JavaScript) could still exceed the context window despite a passing estimate.
  Per-file split dispatch (ADR-0017) handles this at request time.

- **Bin-packing order differs from commit order.** The first-fit-decreasing sort reorders
  commits by size before placing them, so the batches do not necessarily contain commits in
  chronological order. The original commit indices are preserved in `CommitBatch` to
  reconstruct the correct order for output.

- **Solo batches for oversized commits receive no cross-commit context.** A commit that
  exceeds the budget by itself is sent alone, so the AI cannot reason about it in relation
  to adjacent commits.

**Neutral:**

- **The coherence pass is a separate AI call.** It adds one additional API round-trip for
  branches with multiple batches. The cost is accepted because consistency across batch
  boundaries is otherwise lost.
