Estimating Token Count

Before you send a conversation to a model you need to know, roughly, how big it is — a context window is a hard budget, and blowing past it truncates or rejects the request. A real tokenizer (BPE, tiktoken) gives the exact count, but it is model-specific and pulls in a dependency. A cheap, deterministic approximation is enough for a pre-flight budget check: a string is about len(text) / 4 tokens for typical English text.

How the estimate works

Two pieces:

1. Per-string estimate. estimate_tokens(text) returns ceil(len(text) / 4). The ceiling means a 1-3 character string still costs 1 token, and an empty string costs 0.
2. Per-conversation estimate. Chat models do not just concatenate content; each message also spends a few tokens on its role tag and message delimiters. Model that with a fixed PER_MESSAGE_OVERHEAD (3 here) added once per message. The conversation total is the sum of estimate_tokens(content) + PER_MESSAGE_OVERHEAD across all messages.

This is an approximation on purpose. Real tokenizers split on sub-word units, so code, rare words, and non-English text can be well off 4 chars/token. Treat the result as a guardrail, not an exact count.

Task

Implement two functions:

1. estimate_tokens(text) -> ceil(len(text) / 4).
2. fits_budget(messages, budget) -> True if sum(estimate_tokens(m["content"]) + PER_MESSAGE_OVERHEAD for m in messages) <= budget, else False.

Example

messages = [
    {"role": "system", "content": "You are a helpful assistant."},  # 28 chars -> 7 tokens
    {"role": "user", "content": "Hi!"},                             # 3 chars  -> 1 token
]

estimate_tokens("You are a helpful assistant.")  # -> 7   (ceil(28/4))
estimate_tokens("Hi!")                           # -> 1   (ceil(3/4))

# total = (7 + 3) + (1 + 3) = 14
fits_budget(messages, budget=20)  # -> True
fits_budget(messages, budget=10)  # -> False

Constraints

• Use only the standard library. Do not import a real tokenizer or call any network/model.
• The estimate must be deterministic: the same input always yields the same count.
• estimate_tokens("") is 0; any non-empty string is >= 1.
• The budget check is inclusive: a total exactly equal to budget fits.
• Assume every message dict has a string "content" field.

Approach

Approximate a string’s token count with ceil(len(text) / 4), a deterministic, dependency-free stand-in for a real sub-word tokenizer. For a conversation, sum that estimate over each message’s content and add a fixed PER_MESSAGE_OVERHEAD per message to account for role tags and chat delimiters, then compare the total against the budget with an inclusive <=.

Solution

from math import ceil
from typing import List, Dict

# Extra tokens each chat message spends on role tags and formatting.
PER_MESSAGE_OVERHEAD = 3

def estimate_tokens(text: str) -> int:
    return ceil(len(text) / 4)          # ceil => any non-empty string costs >= 1

def fits_budget(messages: List[Dict[str, str]], budget: int) -> bool:
    total = sum(
        estimate_tokens(m["content"]) + PER_MESSAGE_OVERHEAD
        for m in messages
    )
    return total <= budget

Walkthrough

On the example:

1. estimate_tokens("You are a helpful assistant."): the string is 28 characters, ceil(28 / 4) = 7.
2. estimate_tokens("Hi!"): 3 characters, ceil(3 / 4) = ceil(0.75) = 1.
3. fits_budget sums (7 + 3) + (1 + 3) = 14.
4. 14 <= 20 -> True; 14 <= 10 -> False.

estimate_tokens("") is ceil(0 / 4) = 0, so empty content contributes only its per-message overhead.

Complexity & notes

• Time is O(N) in the total number of characters across all messages (each is counted once by len). Space is O(1) beyond the input.
• Using ceil rather than integer // division is what guarantees the >= 1 floor for short non-empty strings; len(text) // 4 would report "Hi!" as 0 tokens.
• The chars/4 rule is calibrated for typical English prose. Real tokenizers (BPE / tiktoken) split on sub-word units, so dense code, long rare words, whitespace, and non-Latin scripts can diverge from 4 chars/token by a wide margin. Treat this as a guardrail for a pre-flight budget check, not an exact accounting — when you need precision, call the model’s actual tokenizer.
• PER_MESSAGE_OVERHEAD is a coarse constant; different chat formats spend different amounts on message framing. The point is to remember that the per-message cost is nonzero, so a long list of tiny messages is not free.