Text chunking

Deep dive

How it works

In: text (plus optional Markdown/HTML structure), a token budget max, an overlap, a length function · Out: chunks as (start, end, section path) byte ranges · State: none between documents; the heading stack while scanning one · Cost: O(n) splitting, one length call per candidate join; the embedding call per chunk dominates

1. Atomize. Take the separator list from large to small ("\n\n", "\n", ". ", " "). If a piece fits max, keep it whole; otherwise split it on the next separator, keeping the separator on the left piece so offsets stay contiguous. This is LangChain's RecursiveCharacterTextSplitter idea.
2. Pack. Greedily join consecutive atoms while the joined text still fits. Measure the joined text; token counts are not additive across a join.
3. Overlap. Start the next chunk with the trailing atoms of the previous one while they fit overlap and the next new atom still fits max.
4. Attach context. Track the heading stack (# to ######); store the path at the chunk start. Optionally prepend it to the text that is embedded.
5. Structure-aware. Split on headings first (HTML, Markdown), code by syntax-tree depth (syntax trees), keep a table whole or repeat its header row per piece (tables, layout).
6. Semantic. Embed sentences, cut where the distance between neighbours spikes. One embedding per sentence is the price.
7. Late chunking. Run a long-context embedder over the whole document, then mean-pool token vectors per chunk span (Günther et al. 2024). Needs token-level offsets.
8. Contextual headers. An LLM writes 50-100 tokens situating each chunk; prepend them before embedding and BM25 (Anthropic). Prompt-cache the document.

Code

const SEPS: [&str; 4] = ["\n\n", "\n", ". ", " "];

#[derive(Debug, Clone)]
pub struct Chunk { pub start: usize, pub end: usize, pub headings: Vec<String> }

/// Split text[lo..hi] into atoms (contiguous byte ranges, separator kept on the left piece)
/// that each fit `max`, descending the separator hierarchy only where a piece is too big.
fn atoms(t: &str, lo: usize, hi: usize, seps: &[&str], len: &dyn Fn(&str) -> usize, max: usize, out: &mut Vec<(usize, usize)>) {
    if len(&t[lo..hi]) <= max || seps.is_empty() { out.push((lo, hi)); return; } // empty seps: oversized atom
    let (mut from, mut pieces) = (lo, vec![]);
    while let Some(p) = t[from..hi].find(seps[0]) {
        let e = from + p + seps[0].len();
        pieces.push((from, e));
        from = e;
    }
    if from < hi { pieces.push((from, hi)); }
    // one piece = this separator is absent (or only trails): try the next level on the same range
    let next = if pieces.len() == 1 { &seps[1..] } else { seps };
    for (a, b) in pieces { atoms(t, a, b, next, len, max, out); }
}

/// Markdown headings as (byte offset, level, title); `#`..`######` followed by a space.
fn headings(t: &str) -> Vec<(usize, usize, String)> {
    let (mut hs, mut off) = (vec![], 0);
    for line in t.split_inclusive('\n') {
        let n = line.bytes().take_while(|&c| c == b'#').count();
        if (1..=6).contains(&n) && line[n..].starts_with(' ') { hs.push((off, n, line[n..].trim().to_string())); }
        off += line.len();
    }
    hs
}

pub fn split(t: &str, max: usize, overlap: usize, len: &dyn Fn(&str) -> usize) -> Vec<Chunk> {
    let mut a = vec![];
    atoms(t, 0, t.len(), &SEPS, len, max, &mut a);
    let (mut out, mut i) = (vec![], 0);
    let (hs, mut h, mut stack) = (headings(t), 0, Vec::<(usize, String)>::new()); // chunk starts only grow: advance a cursor
    while i < a.len() {
        while h < hs.len() && hs[h].0 <= a[i].0 {
            while stack.last().map_or(false, |(l, _)| *l >= hs[h].1) { stack.pop(); }
            stack.push((hs[h].1, hs[h].2.clone())); h += 1;
        }
        let mut j = i + 1; // greedy: take atoms while the *joined* text still fits (token counts are not additive)
        while j < a.len() && len(&t[a[i].0..a[j].1]) <= max { j += 1; }
        out.push(Chunk { start: a[i].0, end: a[j - 1].1, headings: stack.iter().map(|(_, s)| s.clone()).collect() });
        if j == a.len() { break; }
        // next chunk re-reads the trailing atoms of this one while they fit `overlap`
        // and the next new atom still fits `max`; k > i guarantees progress
        let mut k = j;
        while k > i + 1 && len(&t[a[k - 1].0..a[j - 1].1]) <= overlap && len(&t[a[k - 1].0..a[j].1]) <= max { k -= 1; }
        i = k;
    }
    out
}

fn words(s: &str) -> usize { s.split_whitespace().count() }

fn main() {
    let mut doc = String::from("# Guide\nIntro text. It has two sentences.\n\n## Setup\n");
    for p in 0..4 { doc += &format!("Step {p} is simple. Run the tool and check the output carefully before going on. Then wait a moment. Read the log once more. Fix anything odd.\n\n"); }
    doc += "## Usage\n";
    for p in 0..4 { doc += &format!("Usage note {p} talks about flags and defaults at some length, one sentence after another. Done.\n"); }
    let (max, overlap) = (20, 8);
    let chunks = split(&doc, max, overlap, &words);
    assert_eq!((chunks[0].start, chunks.last().unwrap().end), (0, doc.len()));          // covers the text
    let mut overlaps = 0;
    for (n, c) in chunks.iter().enumerate() {
        assert!(words(&doc[c.start..c.end]) <= max);                                  // never exceeds max
        if n > 0 {
            let p = &chunks[n - 1];
            assert!(c.start > p.start && c.end > p.end && c.start <= p.end);             // in order, no gap
            let ov = words(&doc[c.start..p.end]);
            assert!(ov <= overlap);                                                    // overlap bounded
            overlaps += (ov > 0) as usize;
        }
    }
    assert!(overlaps > 0);
    assert_eq!(chunks[0].headings, ["Guide"]);
    let last = chunks.last().unwrap();
    assert_eq!(last.headings, ["Guide", "Usage"]);
    assert!(chunks.iter().any(|c| c.headings == ["Guide", "Setup"]));
    println!("{} chunks, {} with overlap; ok", chunks.len(), overlaps);
}

A piece that cannot be split further is emitted oversized. Swap words for the embedder's tokenizer (BPE).

Complexity and constants

• Linear apart from length calls: the greedy join re-measures a growing slice. Tokenize once and slice ids to avoid it.
• Index bytes = chunks × dims × bytes, e.g. 5,000 × 1024 × 4 B = 20 MB (arithmetic).
• Overlap factor size / (size − overlap): 1.5 for overlap = size/3. Measured below: words in chunks ÷ words in document = 1.500 at max 60, overlap 20.
• Cost drivers: embedding calls (tokens × factor), the LLM pass for contextual headers, one embedding per sentence for semantic splitting.

Efficiency

• Cost: splitting is not the bottleneck. Measured on an Apple M4 Pro, release build, 20 MB synthetic Markdown, whole-word length function: 79 MB/s with no overlap, 57 MB/s with overlap 20 (max 60 words). The bound is the embedding model's throughput, then vector memory.
• Levers:
  • Small or zero overlap — index and embedding cost ÷ size/(size − overlap); Chroma's recursive 400-token runs scored IoU 3.6 at overlap 0 versus 3.3 at 200, recall 89.5 versus 88.1 (Chroma, text-embedding-3-large, top 5) — when recall is already high.
  • Contextual headers with prompt caching — retrieval failure rate 5.7 % → 3.7 %, 2.9 % with contextual BM25, 1.9 % reranked (Anthropic's post), at $1.02 per million document tokens one-off — when chunks are ambiguous alone (clauses, ticket replies).
  • Late chunking — no extra LLM calls, one pass over the document (Günther et al.) — when a long-context embedder is available and documents fit it.
  • Drop duplicate boilerplate (hash exact repeats, MinHash near repeats) before embedding — fewer vectors, fewer false matches (arithmetic) — headers, footers, licences, signatures.
• Naive → standard → state of the art:
  • Fixed N characters, no offsets · linear, cuts mid-word, size unrelated to the embedder limit
  • Recursive split in tokens, small overlap, offsets and section path · linear, index ×1 to ×1.5
  • Structure-aware split + contextual header or late chunking + hybrid search and reranking · adds one cached LLM pass or one long-context embedding

Implementation notes

• Budget = the embedder's max input minus anything you prepend (title, path, instruction prefix). Over-limit input is truncated or rejected depending on the API.
• Keep offsets from the splitter itself. LangChain's optional add_start_index recovers them afterwards with text.find, a search that can land on a repeated passage.
• Strip boilerplate (navigation, page numbers) before chunking, not after.
• Store text, offsets, path, document id. Expand hits to neighbours or the parent section when answering (context budget).
• Defaults: LangChain 4,000 characters, overlap 200; LlamaIndex core 1,024 tokens, overlap 20. Tune on your own queries.
• Matryoshka embeddings shrink vectors to offset extra chunks.

Pitfalls

• Counting characters or words against a token limit; code and non-English text tokenize worse.
• A # line in a fenced code block is not a heading; the demo would treat it as one.
• A chunk that spans two sections carries the path of its start; the later content is mislabelled.
• Overlap works on whole atoms: if atoms are larger than overlap, none is repeated.
• Semantic chunkers with default settings can lose: Chroma's default Kamradt chunker reached recall 83.6 against 89.5 for recursive 400/0.
• Splitting tables or code mid-row/mid-function.

Variants and alternatives

In production

LangChain and LlamaIndex splitters sit in RAG stacks over legal and policy documents, support tickets and manuals, wikis, and code repositories (syntax-tree splitting). Contextual retrieval is described by Anthropic.

Implementations

Sources

• Michael Günther et al., Late Chunking: Contextual Chunk Embeddings Using Long-Context Embedding Models, arXiv 2024. paper · code
• Anthropic, Introducing Contextual Retrieval, 2024. post
• Brandon Smith, Anton Troynikov, Evaluating Chunking Strategies for Retrieval, Chroma Technical Report, July 2024. report · code
• LangChain, text splitters (base.py, character.py). code
• LlamaIndex, node parser modules. docs
• Ben Brandt, text-splitter. code