Raven-1/tests/test_token_estimation.py
Dizhan Xue bb8f4e9226
perf: reuse tokenization across history trim estimates (#904)
## Summary

When a long history exceeds its token budget, every dropped group causes
another estimate of nearly the same prompt. Re-encoding all retained
text repeatedly dominates the remaining trim time. Reuse unchanged
tokenization within one synchronous history trim while preserving its
selected messages, IDs, warning sequence, and estimates.

- Split text only at newline-to-non-whitespace boundaries that the fixed
cl100k tokenizer cannot cross. Per-message token counts are not
independently additive, so subtracting whole messages would change
estimates at some joins.
- Count the first prompt with one whole-payload encoding. Reuse an
identical estimate directly; build fragment costs and multiplicities
only when a later prompt differs. A trim that already fits pays no
per-line encoding overhead. Then subtract removed fragments and encode
new fragments or changed joins, retaining only current fragments.
- Scope the cache to one trim, restore enclosing scopes, and release it
on errors. Empty prompts and tokenizer failures clear cached state while
preserving the existing whole-payload fallback. Custom provider counters
keep their existing call path.
- Keep the cl100k encoding name beside its boundary rule and pin a
counterexample that fails if the encoding is changed without revisiting
the split. Test that estimates outside a trim retain no state, and that
empty or failed estimates release the initial unsplit prompt too.
- Correct the indexed group-sweep test's stale explanation.

## Type

- [ ] Fix
- [ ] Feature
- [ ] Docs
- [ ] CI / tooling
- [ ] Refactor
- [x] Other

Performance improvement.

## Verification

- [x] Relevant tests pass locally
- [x] Relevant lint / type checks pass locally
- [ ] User-facing docs or screenshots are updated when needed

Linux, Python 3.12, on current main:

```text
uv run --frozen pytest tests/test_token_estimation.py tests/test_history_trimmer.py tests/test_curator_context_engine.py tests/test_context_engine_factory.py tests/test_default_context_engine.py -q -x --tb=short
```

Result: 125 passed. Tests compare cached and uncached whole-trim results
and real-tokenizer counts, including whitespace, repeated fragments,
reasoning, tool definitions, images, special-token fallback, nested
scopes, exceptions, custom builders, and provider counters. A
performance guard measures characters sent to the encoder rather than
relying on wall-clock timing. The tested source files were verified
against their committed Git blobs.

Full-trim benchmark with the production estimator: 1,200 messages, 123
removed, median of three alternating runs. The control disables only
tokenization reuse; both paths include the group-index optimization
already on main. Returned messages, IDs, warnings, and estimates were
identical.

| Measurement | Uncached tokenization | Scoped reuse |
| --- | ---: | ---: |
| Median trim time | 1.577 s | 0.422 s |
| Python allocation peak, measured separately | 3.462 MiB | 3.308 MiB |

This workload was 3.74 times faster. Prompt construction and structural
selection still run normally, so this is a measured improvement for this
workload, not a constant-time guarantee.

First-estimate control, about 2 MB of unique lines, median of three
alternating runs in one process. All token counts matched:

| Line width | Whole encoding | Previous eager fragments | Deferred
first estimate |
| --- | ---: | ---: | ---: |
| 15 characters | 0.188 s | 0.549 s | 0.184 s |
| 40 characters | 0.111 s | 0.256 s | 0.108 s |
| 80 characters | 0.108 s | 0.183 s | 0.110 s |
| 200 characters | 0.171 s | 0.203 s | 0.158 s |

Four additional isolated mutations were caught: a shared default cache
outside trims, changing only the encoding to o200k, restoring eager
splitting, and leaving the initial prompt behind after clear. The last
mutation exposed a missing test, which was added before publication.
Native Windows token/history/curator tests passed 62 cases before the
two final clear cases; both final cases then passed separately.

Additional checks passed:

```text
uv run --frozen --python 3.12 --extra dev pre-commit run --from-ref origin/main --to-ref HEAD
uv run --frozen ty check raven/context_engine/history_trimmer.py raven/utils/tokens.py
uv run --frozen lint-imports
uv run --frozen python scripts/check_commit_messages.py origin/main..HEAD
commitlint --from origin/main --to HEAD
uv run --frozen python scripts/check_source_language.py origin/main..HEAD
uv run --frozen python scripts/check_large_files.py origin/main..HEAD
git diff --check origin/main...HEAD
```

Import-linter kept all 10 contracts. The full repository suite and
native macOS were not rerun locally. No user-facing documentation or
screenshot applies.

## Risk

- [x] Security impact considered
- [x] Backward compatibility considered
- [x] Rollback path is clear for risky changes

The split relies on the fixed cl100k token-boundary property and is
checked against the real encoder. Text is retained only inside the
current trim; no cache persists across requests. No dependency,
configuration, or persisted-format changes.

Rollback: revert the squash commit.

## Related Issues

#886
2026-10-12 16:08:07 +08:00

489 lines
17 KiB
Python

"""Prompt-token estimation counts tool calls and reasoning fields for consolidation triggers."""
from __future__ import annotations
import asyncio
import random
from unittest.mock import AsyncMock, MagicMock
import pytest
from raven.memory_engine.consolidate.consolidator import MemoryConsolidator
from raven.session.manager import Session
from raven.utils import images, tokens
@pytest.mark.parametrize("after_scope", [False, True])
def test_estimates_outside_a_trim_do_not_share_cached_state(monkeypatch, after_scope) -> None:
calls: list[str] = []
class MeasuredEncoding:
def encode(self, payload):
calls.append(payload)
return list(payload)
monkeypatch.setattr(tokens.tiktoken, "get_encoding", lambda _name: MeasuredEncoding())
history = [{"role": "user", "content": "unscoped estimate"}]
if after_scope:
with tokens.reuse_prompt_tokenization():
tokens.estimate_prompt_tokens(history)
calls.clear()
tokens.estimate_prompt_tokens(history)
tokens.estimate_prompt_tokens(history)
assert calls == ["unscoped estimate", "unscoped estimate"]
def test_reused_prompt_tokenization_matches_whole_payload_counts() -> None:
rng = random.Random(886)
atoms = ["alpha", "123456", "?!", "\n", "\r", "\t", " ", " ", "A\u0301", "\u2603", "{}", "'s"]
histories = [
[{"role": "user", "content": "".join(rng.choices(atoms, k=rng.randrange(1, 60)))} for _ in range(5)]
for _ in range(100)
]
histories += [[{"role": "user", "content": "repeat"}] * count for count in (5, 2, 7, 1, 0)]
expected = [tokens.estimate_prompt_tokens(history) for history in histories]
with tokens.reuse_prompt_tokenization():
assert [tokens.estimate_prompt_tokens(history) for history in histories] == expected
def test_cache_boundaries_match_the_selected_encoding() -> None:
history = [{"role": "user", "content": "!\n/s"}]
expected = tokens.estimate_prompt_tokens(history)
with tokens.reuse_prompt_tokenization():
tokens.estimate_prompt_tokens([{"role": "user", "content": "warmup"}])
assert tokens.estimate_prompt_tokens(history) == expected
@pytest.mark.parametrize("reset", ["empty", "unavailable"])
def test_the_initial_prompt_is_forgotten_when_the_cache_clears(monkeypatch, reset) -> None:
history = [{"role": "user", "content": "The first prompt has more than one token."}]
expected = tokens.estimate_prompt_tokens(history)
with tokens.reuse_prompt_tokenization():
assert tokens.estimate_prompt_tokens(history) == expected
if reset == "empty":
tokens.estimate_prompt_tokens([])
else:
def unavailable(_name):
raise RuntimeError("encoding unavailable")
with monkeypatch.context() as patch:
patch.setattr(tokens.tiktoken, "get_encoding", unavailable)
tokens.estimate_prompt_tokens(history)
assert tokens.estimate_prompt_tokens(history) == expected
def test_reused_prompt_tokens_keep_reasoning_tools_images_and_error_fallback() -> None:
image = {"type": "image_url", "image_url": {"url": "https://example.com/image.png"}}
history = [
{"role": "user", "content": [{"type": "text", "text": "Look.\n"}, image]},
{
"role": "assistant",
"content": " Now.\n\n",
"reasoning_content": "thinking",
"thinking_blocks": [{"thinking": "more"}],
},
{
"role": "assistant",
"content": "",
"tool_calls": [{"id": "c", "function": {"name": "read", "arguments": "{}"}}],
},
{"role": "tool", "tool_call_id": "c", "name": "read", "content": {"answer": "found"}},
]
tool_definitions = [{"type": "function", "function": {"name": "read"}}]
cases = [
(history, tool_definitions),
(history[1:], []),
([{"role": "user", "content": "<|endoftext|>"}], []),
(history, tool_definitions),
]
expected = [tokens.estimate_prompt_tokens(messages, tools) for messages, tools in cases]
with tokens.reuse_prompt_tokenization():
assert [tokens.estimate_prompt_tokens(messages, tools) for messages, tools in cases] == expected
def test_prompt_token_cache_is_nested_scoped_and_drops_removed_text(monkeypatch) -> None:
real = tokens.tiktoken.get_encoding("cl100k_base")
encoded: list[str] = []
class MeasuredEncoding:
def encode(self, payload):
encoded.append(payload)
return real.encode(payload)
monkeypatch.setattr(tokens.tiktoken, "get_encoding", lambda _name: MeasuredEncoding())
first = [{"role": "user", "content": "first"}]
second = [{"role": "user", "content": "second"}]
with tokens.reuse_prompt_tokenization():
tokens.estimate_prompt_tokens(first)
with tokens.reuse_prompt_tokenization():
tokens.estimate_prompt_tokens(second)
before = len(encoded)
tokens.estimate_prompt_tokens(first)
assert len(encoded) == before
tokens.estimate_prompt_tokens(second)
before = len(encoded)
tokens.estimate_prompt_tokens(first)
assert encoded[before:] == ["first"]
for unavailable in ([], [{"role": "user", "content": "<|endoftext|>"}]):
tokens.estimate_prompt_tokens(unavailable)
before = len(encoded)
tokens.estimate_prompt_tokens(first)
assert encoded[before:] == ["first"]
before = len(encoded)
tokens.estimate_prompt_tokens(first)
assert encoded[before:] == ["first"]
def test_prompt_token_cache_is_released_when_the_trim_raises(monkeypatch) -> None:
encoding = _FakeEncoding()
calls: list[str] = []
def encode(payload):
calls.append(payload)
return list(payload)
monkeypatch.setattr(encoding, "encode", encode)
monkeypatch.setattr(tokens.tiktoken, "get_encoding", lambda _name: encoding)
history = [{"role": "user", "content": "unchanged"}]
with pytest.raises(RuntimeError, match="builder failed"):
with tokens.reuse_prompt_tokenization():
tokens.estimate_prompt_tokens(history)
raise RuntimeError("builder failed")
tokens.estimate_prompt_tokens(history)
assert calls == ["unchanged", "unchanged"]
class _FakeEncoding:
def encode(self, payload: str) -> list[str]:
return list(payload)
def test_estimate_prompt_tokens_counts_assistant_tool_calls(
monkeypatch: pytest.MonkeyPatch,
) -> None:
monkeypatch.setattr(
tokens.tiktoken,
"get_encoding",
lambda _name: _FakeEncoding(),
)
msg = {
"role": "assistant",
"content": "",
"tool_calls": [
{
"id": "call_1",
"type": "function",
"function": {
"name": "write_file",
"arguments": "x" * 10_000,
},
},
],
}
prompt_tokens = tokens.estimate_prompt_tokens([msg])
message_tokens = tokens.estimate_message_tokens(msg)
assert prompt_tokens >= message_tokens
assert prompt_tokens > 10_000
def test_estimate_counts_reasoning_fields(
monkeypatch: pytest.MonkeyPatch,
) -> None:
monkeypatch.setattr(
tokens.tiktoken,
"get_encoding",
lambda _name: _FakeEncoding(),
)
base = {"role": "assistant", "content": "answer"}
with_reasoning = {
"role": "assistant",
"content": "answer",
"reasoning_content": "r" * 5_000,
"thinking_blocks": [{"thinking": "t" * 5_000}],
}
assert tokens.estimate_message_tokens(with_reasoning) > tokens.estimate_message_tokens(base)
assert tokens.estimate_prompt_tokens([with_reasoning]) > tokens.estimate_prompt_tokens([base])
assert tokens.estimate_message_tokens(with_reasoning) > 10_000
def test_estimate_prompt_tokens_fallback_counts_tool_calls(
monkeypatch: pytest.MonkeyPatch,
) -> None:
def _raise(_name: str) -> object:
raise RuntimeError("encoding unavailable")
monkeypatch.setattr(tokens.tiktoken, "get_encoding", _raise)
msg = {
"role": "assistant",
"content": "",
"tool_calls": [
{
"id": "call_1",
"type": "function",
"function": {
"name": "edit_file",
"arguments": "x" * 40_000,
},
},
],
}
assert tokens.estimate_prompt_tokens([msg]) > 10_000
def test_consolidator_prompt_estimate_counts_tool_calls_for_trigger(
monkeypatch: pytest.MonkeyPatch,
tmp_path,
) -> None:
monkeypatch.setattr(
tokens.tiktoken,
"get_encoding",
lambda _name: _FakeEncoding(),
)
session = Session(
key="cli:default",
messages=[
{"role": "user", "content": "please write a large file"},
{
"role": "assistant",
"content": "",
"tool_calls": [
{
"id": "call_1",
"type": "function",
"function": {
"name": "write_file",
"arguments": "x" * 70_000,
},
},
],
},
],
)
consolidator = MemoryConsolidator(
workspace=tmp_path,
provider=object(),
model="test-model",
sessions=object(),
context_window_tokens=65_536,
build_messages=lambda **kwargs: [
{"role": "system", "content": "system"},
*kwargs["history"],
{"role": "user", "content": kwargs["current_message"]},
],
get_tool_definitions=lambda: [],
)
estimated, source = consolidator.estimate_session_prompt_tokens(session)
assert source == "tiktoken"
assert estimated > consolidator.context_window_tokens
def test_token_consolidation_triggers_on_tool_call_payload(
monkeypatch: pytest.MonkeyPatch,
tmp_path,
) -> None:
monkeypatch.setattr(
tokens.tiktoken,
"get_encoding",
lambda _name: _FakeEncoding(),
)
session = Session(
key="cli:default",
messages=[
{"role": "user", "content": "please write a large file"},
{
"role": "assistant",
"content": "",
"tool_calls": [
{
"id": "call_1",
"type": "function",
"function": {
"name": "write_file",
"arguments": "x" * 2_000,
},
},
],
},
{"role": "user", "content": "continue"},
],
)
sessions = MagicMock()
consolidator = MemoryConsolidator(
workspace=tmp_path,
provider=object(),
model="test-model",
sessions=sessions,
context_window_tokens=1_000,
build_messages=lambda **kwargs: [
{"role": "system", "content": "system"},
*kwargs["history"],
{"role": "user", "content": kwargs["current_message"]},
],
get_tool_definitions=lambda: [],
)
consolidator.consolidate_messages = AsyncMock(return_value=True)
consolidator.maybe_refresh_hot_tags = AsyncMock(return_value=0)
asyncio.run(consolidator.maybe_consolidate_by_tokens(session))
assert session.last_consolidated == 2
consolidator.consolidate_messages.assert_awaited_once()
sessions.save.assert_called_once_with(session)
def _png(width: int, height: int, *, compress: int = 0) -> bytes:
"""Minimal valid PNG. ``compress=0`` keeps the payload incompressible, which
is what makes a real photo's data URI dwarf its token cost."""
import hashlib
import struct
import zlib
def chunk(tag: bytes, data: bytes) -> bytes:
body = tag + data
return struct.pack(">I", len(data)) + body + struct.pack(">I", zlib.crc32(body))
noise = hashlib.sha256(b"raven").digest()
blob = noise * ((width * 3 * height) // len(noise) + 2)
raw = b"".join(b"\x00" + blob[y * width * 3 : (y + 1) * width * 3] for y in range(height))
return (
b"\x89PNG\r\n\x1a\n"
+ chunk(b"IHDR", struct.pack(">IIBBBBB", width, height, 8, 2, 0, 0, 0))
+ chunk(b"IDAT", zlib.compress(raw, compress))
+ chunk(b"IEND", b"")
)
def _data_uri(png: bytes) -> str:
import base64
return "data:image/png;base64," + base64.b64encode(png).decode()
def test_estimate_image_tokens_matches_anthropic_published_values() -> None:
# Published examples from Anthropic's vision docs (28x28 patches, cap 1568).
assert images.estimate_image_tokens(1000, 1000) == 1296
assert images.estimate_image_tokens(100, 100) == 16
# Beyond the cap the charge saturates rather than growing with area.
assert images.estimate_image_tokens(8000, 8000) == 1568
def test_image_pixel_size_survives_every_real_jpeg_variant() -> None:
"""The SOF walk must not desync on markers that carry no length field.
Reading a standalone marker's payload as a segment length used to abandon the
walk, which silently fell back to charging the per-image ceiling.
"""
import io
from PIL import Image
def jpg(**kw) -> bytes:
buf = io.BytesIO()
Image.new("RGB", (640, 480), (1, 2, 3)).save(buf, "JPEG", **kw)
return buf.getvalue()
plain = jpg()
variants = {
"plain": plain,
"exif": jpg(exif=b"Exif\x00\x00" + b"\x00" * 64),
"progressive": jpg(progressive=True),
"restart_blocks": jpg(restart_marker_blocks=4),
"optimized": jpg(optimize=True),
# Standalone markers: TEM and RST0 have no length field.
"tem_marker": plain[:2] + b"\xff\x01" + plain[2:],
"rst_marker": plain[:2] + b"\xff\xd0" + plain[2:],
# Fill bytes are legal before any marker.
"fill_bytes": plain[:2] + b"\xff\xff\xff" + plain[2:],
}
for label, data in variants.items():
assert images.image_pixel_size(data) == (640, 480), label
def test_image_pixel_size_returns_none_on_malformed_jpeg_without_raising() -> None:
"""Unparseable is fine -- the caller charges the ceiling, which over-estimates
in the safe direction. Raising would not be fine."""
import io
from PIL import Image
buf = io.BytesIO()
Image.new("RGB", (640, 480), (1, 2, 3)).save(buf, "JPEG")
plain = buf.getvalue()
for label, data in {
"truncated": plain[:40],
"garbage_tail": plain[:2] + b"\xff\xe0\x00\x02" + b"\x00" * 5,
"zero_length_segment": plain[:2] + b"\xff\xe0\x00\x00" + plain[4:],
"not_an_image": b"hello world",
}.items():
assert images.image_pixel_size(data) is None, label
def test_image_pixel_size_parses_png_gif_and_jpeg() -> None:
assert images.image_pixel_size(_png(640, 480)) == (640, 480)
gif = b"GIF89a" + (320).to_bytes(2, "little") + (240).to_bytes(2, "little")
assert images.image_pixel_size(gif) == (320, 240)
# SOF0 frame header: precision, height, width, components.
sof = (
b"\xff\xc0" + (11).to_bytes(2, "big") + b"\x08" + (200).to_bytes(2, "big") + (300).to_bytes(2, "big") + b"\x01"
)
assert images.image_pixel_size(b"\xff\xd8\xff" + b"\xe0\x00\x02" + sof) == (300, 200)
assert images.image_pixel_size(b"not an image") is None
def test_estimate_content_part_tokens_ignores_text_parts() -> None:
assert images.estimate_content_part_tokens({"type": "text", "text": "hi"}) is None
assert images.estimate_content_part_tokens("not a dict") is None
def test_estimate_content_part_tokens_charges_ceiling_for_unparseable_image() -> None:
remote = {"type": "image_url", "image_url": {"url": "https://example.com/a.png"}}
assert images.estimate_content_part_tokens(remote) == images._IMAGE_TOKEN_CAP
corrupt = {"type": "image_url", "image_url": {"url": "data:image/png;base64,!!!!"}}
assert images.estimate_content_part_tokens(corrupt) == images._IMAGE_TOKEN_CAP
def test_image_data_uri_is_billed_by_patch_area_not_base64_length() -> None:
"""Regression: counting the data URI as text charged ~2000x the real cost on
a multi-megabyte image, starving the history budget."""
png = _png(1000, 1000)
block = {"type": "image_url", "image_url": {"url": _data_uri(png)}}
message = {"role": "user", "content": [block, {"type": "text", "text": "describe"}]}
# The data URI really is enormous -- the assertion below is not vacuous.
assert len(block["image_url"]["url"]) > 3_000_000
estimate = tokens.estimate_prompt_tokens([message])
assert 1296 <= estimate < 1400
assert tokens.estimate_message_tokens(message) == estimate
def test_image_tokens_survive_the_tiktoken_fallback_path(
monkeypatch: pytest.MonkeyPatch,
) -> None:
"""Images are counted outside tiktoken, so a tokenizer failure must not drop
them -- nor may an image-only message report zero."""
monkeypatch.setattr(
tokens.tiktoken,
"get_encoding",
lambda _name: (_ for _ in ()).throw(RuntimeError("no tokenizer")),
)
block = {"type": "image_url", "image_url": {"url": _data_uri(_png(280, 280))}}
assert tokens.estimate_prompt_tokens([{"role": "user", "content": [block]}]) == 100
assert tokens.estimate_message_tokens({"role": "user", "content": [block]}) == 100