Recursive Chunking with Overlap

Background

Production RAG retrieval depends on the unit of indexing as much as on the embedding model. Chunking with overlap is the canonical move: split each document into windows of ~$N$ tokens, sharing $k$ tokens between adjacent windows so a sentence that spans a boundary still survives in both. It is the most-cited "fixable RAG bug" — fixed chunking with no overlap loses any fact that straddles a window, and quality drops measurably.

Problem statement

Implement chunk_with_overlap(tokens, chunk_size, overlap) that splits a token list into a sequence of overlapping windows. Each window is at most chunk_size tokens long, and adjacent windows share exactly overlap tokens. The final window may be shorter than chunk_size.

$$\text{step} \;=\; \text{chunk\_size} - \text{overlap},\qquad \text{window}_k \;=\; \text{tokens}\bigl[k\cdot\text{step}\,:\,k\cdot\text{step} + \text{chunk\_size}\bigr]$$

Stop after the first window that ends at or past the end of the token list.

Input

• tokens — list[str] of tokens (or any sliceable sequence).
• chunk_size — int, max tokens per window. Must be $\ge 1$.
• overlap — int, tokens shared between adjacent windows. Must satisfy $0 \le \text{overlap} < \text{chunk\_size}$ (an overlap equal to chunk_size would loop forever).

Output

• list[list[str]] — the windows, in order. Empty input or chunk_size <= 0 returns [].

Examples

Example 1 — typical overlap

Input:  tokens = ["a","b","c","d","e","f","g","h","i","j"], chunk_size = 5, overlap = 2
Output: [["a","b","c","d","e"], ["d","e","f","g","h"], ["g","h","i","j"]]

Explanation: step = $5 - 2 = 3$. Windows at indices $0,3,6$. The third window extends to index 10 which is past the end, so it stops there with 4 tokens.

Example 2 — overlap = 0 gives non-overlapping windows

Input:  tokens = ["a","b","c","d","e","f"], chunk_size = 3, overlap = 0
Output: [["a","b","c"], ["d","e","f"]]

Example 3 — chunk_size exceeds input -> one short window

Input:  tokens = ["a","b","c"], chunk_size = 10, overlap = 3
Output: [["a","b","c"]]

Constraints

• chunk_size >= 1; raise ValueError if overlap >= chunk_size (would never terminate).
• The final window may be shorter than chunk_size when the token list doesn't divide evenly.
• Each window is a fresh sublist (slice); do not alias the original list.

Notes

• Why overlap. Without it, a fact like "Q3 2025 revenue: $1.2B" can fall across the boundary between two chunks. Each chunk individually fails to embed the fact + its context together; retrieval misses both.
• Why a token list, not characters. Real RAG chunkers respect token budgets (the embedding model's context window). Using characters or sentences as the unit is a different problem; this one isolates the indexing geometry.
• Recursive separator variant. Production chunkers add a separator hierarchy (paragraph -> sentence -> word) and pick the largest separator that fits the budget. That's the next level of detail; the windowed-overlap kernel here is the core of it.