Token-aware chunking with overlap and structure-safe splits #12

Activity

1. harrymove-ctrl

   added this to the Sui Overflow milestone on Jun 16, 2026
2. harrymove-ctrl

   added

   P0Demo-blocking: required for a working Sui Overflow demoDemo-blocking: required for a working Sui Overflow demo

   featureUser- or agent-facing capabilityUser- or agent-facing capability

   crawlingWeb/Walrus crawling and context-extraction qualityWeb/Walrus crawling and context-extraction quality

   on Jun 16, 2026
3. harrymove-ctrl commented on Jun 19, 2026

   

   harrymove-ctrl

   on Jun 19, 2026

   OwnerAuthor

   More actions

   Implementation Plan

   Approach
   Replace the char-cap splitLong() in packages/core/src/chunks.ts:126-146 with a two-phase, structure-aware splitter: (1) segment each heading-section's markdown into atomic blocks (a fenced code block from ``` open→close is one block; a contiguous run of | table rows is one block; prose paragraphs split on blank lines→sentences), then (2) pack blocks greedily up to an approximate token budget (~512-800 tokens via a cheap chars/4 heuristic, no tokenizer dep), prepending the trailing ~12% of the previous part as additive overlap. The key design decision: the new splitter keeps the exact same string[] signature and emits exactly one entry per logical part, so buildChunks's partCounters/chunkId location-key scheme (chunks.ts:25-29) is untouched — overlap is baked into the part text but never creates a new partIndex, keeping chunkId deterministic and planMemoryWrite/chunkGraphDigest stable. This is a single-file core change; both pipelines (Worker worker.ts:2186/2674/2790, CLI cli/src/index.ts:218) lift automatically because both call buildChunks.

   Prerequisites & dependencies

   • None blocking. Issue is foundational (roadmap §3 P0, M1). The hybrid-retrieval issue builds on this but is downstream.
   • No new deps / bindings / creds. Explicit non-goal: do NOT add js-tiktoken/gpt-tokenizer (Worker bundle/CPU budget). Pure-JS heuristic only.
   • Buffer.byteLength (used at chunks.ts:36) already works in the Worker under nodejs_compat (wrangler.jsonc); keep it.
   • Test runner is already wired: root package.json:23 → vitest run; core tests live in packages/core/src/*.test.ts.

   Step-by-step

   1. Add tunable constants at top of packages/core/src/chunks.ts (replacing MAX_CHUNK_CHARS at line 4): CHARS_PER_TOKEN = 4, TARGET_TOKENS = 600, MAX_TOKENS = 800, OVERLAP_RATIO = 0.12. Add function estimateTokens(text: string): number { return Math.ceil(text.length / CHARS_PER_TOKEN); }. Comment that these are heuristic and the band is 512-800.
   2. Write a block segmenter function segmentBlocks(text: string): string[] — walk text.split("\n") tracking state: a line matching /^\s*(```|~~~)/ toggles inFence (accumulate the whole fence, opener→matching closer, as ONE block — never split inside); a line whose trimmed form starts with | starts/extends a table run accumulated as ONE block; blank line flushes the current prose block; other lines accumulate into the current prose block. Returns ordered atomic block strings (newlines preserved). Defensive: an unterminated fence at EOF flushes as a single block.
   3. Write the packer function packBlocks(blocks: string[]): string[] — greedy accumulate into buffer; before appending block b, if buffer non-empty and estimateTokens(buffer + "\n\n" + b) > MAX_TOKENS, flush buffer and start new. If a single block alone > MAX_TOKENS: if it is a prose block, sub-split it at paragraph (\n{2,}) then sentence boundaries (reuse the sentence regex pattern style from text.ts; fall back to whitespace/word boundary, hard-slice only as last resort); if it is a code/table block, keep it whole even when oversized (boundary-safety wins over budget — required by the acceptance criterion). Aim to flush near TARGET_TOKENS but tolerate up to MAX_TOKENS to avoid orphaning a block that just nudges past target.
   4. Write the overlap helper function tailOverlap(prev: string): string — return the trailing ~OVERLAP_RATIO of prev measured in chars, snapped backward to a sentence/newline boundary so the overlap is a clean prefix (no mid-word/mid-fence). Because parts always end on a block boundary, the tail can never contain an unbalanced ```.
   5. Replace splitLong() with function splitSection(text: string): string[] returning final part strings: const body = packBlocks(segmentBlocks(text.trim())); for each part index k>0, prepend tailOverlap(body[k-1]) + "\n\n" to body[k]; part 0 stays raw (no overlap, so short single-part sections return [trimmed] byte-identical to today — preserves existing tests). Keep raw newlines in returned text (code fences/tables must render; validateQuote normalizes whitespace on both sides so grounding is unaffected).
   6. Rewire buildChunks at chunks.ts:20: change for (const part of splitLong(section.text, MAX_CHUNK_CHARS)) → for (const part of splitSection(section.text)). Leave lines 25-38 (locationKey, partCounters, chunkId = sha256Hex(\${locationKey}\n#${partIndex}`).slice(0,16), contentHash = sha256Hex(normalizeText(part)), byteLength) **unchanged** — overlap is inside part` so it flows into text/contentHash/byteLength but the part count (hence partIndex sequence) is purely a function of section content.
   7. Leave normalizeText (chunks.ts:122), splitMarkdownByHeadings, chunkGraphDigest, planMemoryWrite untouched. No edits to facts.ts, worker.ts, cli/src/index.ts, mcp — they consume buildChunks/renderChunksNdjson unchanged.
   8. Extend packages/core/src/chunks.test.ts with the new cases (see Test plan).

   New / changed files

   • packages/core/src/chunks.ts — replace MAX_CHUNK_CHARS + splitLong() with estimateTokens, segmentBlocks, packBlocks, tailOverlap, splitSection; one-line call swap in buildChunks.
   • packages/core/src/chunks.test.ts — add code-fence / table / overlap / token-budget / determinism cases.
   • (No other files change.)

   Test plan

   • Existing must stay green (regression gate): chunks.test.ts 4 cases (deterministic ids, id-stable-on-edit, planMemoryWrite add/change/remove, chunkGraphDigest) and facts.test.ts (validateQuote + grounded-substring suite, which builds facts from the same buildChunks(PAGES)). All PAGES there are short single-part sections → splitSection returns [trimmed] byte-identical to old output, so they pass unmodified.
   • New unit cases in chunks.test.ts:
     1. Code-fence safety: a section with a large fenced ```js … ``` block; assert every chunk's text has an even count of fence markers (no chunk splits a fence) and the full code block appears intact within exactly one chunk.
     2. Table safety: a markdown table (header + |---| separator + many rows); assert no chunk boundary falls between two | rows of the same table (the table run lands wholly in one chunk).
     3. Overlap: a long multi-paragraph prose section yielding ≥2 parts; assert the tail of chunk k is a prefix substring of chunk k+1 and overlap length is within ~10-15% of the prior part.
     4. Token budget: assert each prose chunk's estimateTokens(text) <= MAX_TOKENS (plus overlap) and that long input no longer produces 4000-char monoliths; assert an oversized indivisible code block is allowed to exceed budget (documents the deliberate boundary>budget rule).
     5. Determinism on long input: buildChunks(long) twice → identical chunkId arrays; and chunkGraphDigest equal across two runs of the long page.
     6. partIndex stability: edit only the body of a single-part section inside a multi-section page → that chunk's chunkId stable, contentHash changed (extends the existing edit test to confirm overlap didn't perturb ids).
   • Run: bun run check (typecheck + vitest run) from repo root; proves both chunks.test.ts and facts.test.ts green.
   • Manual integration proof: run the CLI extract→memwal remember delta path (cli/src/index.ts:218-262) on a page containing a code block + table; confirm context/chunks.ndjson chunks are budget-sized with overlap and that a re-run with unchanged content yields an identical chunkGraphDigest (i.e. planMemoryWrite reports all-unchanged), proving the */30 freshness diff stays stable.

   Risks & gotchas

   • Worker bundle/CPU: keep it pure-JS + Buffer.byteLength; no tokenizer import — that is the whole point of the heuristic. No risk to the nodejs_compat Worker path.
   • partIndex drift on structural edits: if an edit changes how many parts a section yields, later partIndexes shift → those chunks read as removed+added in planMemoryWrite. This already true of the current splitter; the new block-aware packing makes part counts more stable (boundaries snap to blocks), but call it out — boundary semantics changed, so the first re-extraction after this ships will show a one-time diff churn (acceptable; not a migration, no stored schema change).
   • Overlap double-counts content: a boundary quote now appears in two chunks → validateQuote still passes against whichever chunk is cited (intended per issue notes); just don't dedupe chunks by content.
   • Oversized indivisible blocks: a single code fence/table bigger than MAX_TOKENS is emitted whole (over budget) by design — boundary-safety beats budget. Tests must assert this rather than fight it.
   • No network/mainnet/testnet or D1 migration impact — ContextChunk shape (types.ts:726-736) is unchanged; NDJSON wire format unchanged.

   Acceptance-criteria mapping

   • Token budget ~512-800, cheap heuristic, no heavy tokenizer → Steps 1, 3, 5; Test 4.
   • ~10-15% overlap so boundary facts survive → Steps 4-5; Test 3.
   • Never split inside code fence / table; prefer sentence/paragraph boundaries → Steps 2-3; Tests 1-2.
   • chunkId location-based & deterministic; planMemoryWrite/chunkGraphDigest stable → Steps 5-6 (partIndex/locationKey untouched, one logical-part-per-entry); Tests 5-6 + existing suite.
   • normalizeText stays shared; facts.test.ts + chunks.test.ts green w/ new fence/table/overlap cases → Step 7 (no facts.ts edit) + Step 8; full Test plan.

   Effort
   M — ~1.5-2.5 person-days. ~0.5d for segmentBlocks/packBlocks/tailOverlap/splitSection, ~0.5-1d for the new tests + edge-case hardening (fence/table interplay, sentence sub-split), ~0.5d verifying regression green and the CLI round-trip digest stability.

   ---

   Implementation plan generated for execution (planning phase). Part of the roadmap (#4).