Repository navigation
fix(chunking): prevent infinite loop in token-based overlap splitting - #4392
Open
otiscuilei wants to merge 1 commit into
Open
otiscuilei wants to merge 1 commit into
otiscuilei wants to merge 1 commit into
Conversation
Contributor
There was a problem hiding this comment.
No issues found across 4 files
Shadow auto-approve: would auto-approve. Bug fix for token-based chunking infinite loop; adds a shrink-check guard to overlap logic, plus a regression test. Changes are scoped, correct, and no external API or core logic is modified beyond the fix.
Re-trigger cubic
Token-based chunking with overlap could spin forever on a whitespace-free run longer than `max_tokens` (a long URL, hash, base64/JWT blob, filesystem path, or biological sequence). In token mode the splitter prepended the overlap tail plus a synthetic separator space to the remainder, which could regrow it back to the full input; the next split then landed on that inserted space and reproduced the input verbatim, so `PreChunk._iter_text_splits` (`while remainder: split(remainder)`) never terminated. Apply the overlap only when the resulting remainder is strictly shorter than its input, otherwise fall back to the un-overlapped remainder (always strictly shorter), guaranteeing forward progress. Adds a regression test.
otiscuilei
force-pushed
the
fix/chunking-token-overlap-infinite-loop
branch
from
July 26, 2026 12:18
c0194b1 to
61307a0
Compare
cragwolfe
pushed a commit
that referenced
this pull request
Oct 9, 2026
…4501) No open issue covers this. None. Found while reading the three sibling validators in `_validate()` against the parameters they guard. `ChunkingOptions._validate()` at `unstructured/chunking/base.py` rejects a negative `new_after_n_chars` and a negative `new_after_n_tokens`. It never checks `overlap`. A negative overlap then corrupts output two ways, with no error and no warning. `base.py:2731` computes the remainder as `s[maxlen - self._opts.overlap :]`. With `overlap = -5` that remainder starts five characters past the end of the fragment, so five characters of the document disappear at every split boundary. `base.py:755` computes `self._text[-overlap:]`. With `overlap = -5` that is a forward slice, so the tail carried into the next chunk is most of the current chunk. Before, on a 60-character input of unique characters at `max_characters=20`: ``` $ python repro.py overlap= 0: ['ABCDEFGHIJKLMNOPQRST', 'UVWXYZabcdefghijklmn', 'opqrstuvwxyz01234567'] dropped from output entirely: '' overlap= -5: ['ABCDEFGHIJKLMNOPQRST', 'Zabcdefghijklmnopqrs', 'yz01234567'] dropped from output entirely: 'UVWXYtuvwx' ``` The `overlap=0` line is the control: same input, same commit, nothing lost. With `overlap_all=True`, three 10-character elements at `max_characters=12`: ``` overlap= 0 -> ['AAAAAAAAAA', 'BBBBBBBBBB', 'CCCCCCCCCC'] overlap= -4 -> ['AAAAAAAAAA', 'AAAAAA\n\nBBBB', 'BB', 'AA\n\nBBBBBBBB', 'CCCCCCCCCC'] ``` Text duplicated and out of order. Reachable from all three public entry points: `chunk_elements(...)`, `chunk_by_title(...)`, and `partition(filename=..., chunking_strategy="basic", overlap=-5)`. All three drop the same characters. After, the four added lines mirror the existing `new_after_n_chars` check and raise `ValueError`. ``` $ python -m pytest test_unstructured/chunking -q 484 passed, 24 skipped in 15.04s ``` Baseline on `1bedf7b` is `482 passed, 24 skipped`, so the delta is the two new parametrised cases. Reverting `unstructured/chunking/base.py` and keeping the test gives `2 failed, 482 passed, 24 skipped`, both of them `Failed: DID NOT RAISE ValueError`. `ruff check` is clean on both touched files. I did not run `make test` or `make check` in full, and no PDF, image or OCR test ran here: the install was `-e ".[csv,docx,md,pptx,xlsx]"` without the inference extras. `make check-version` passes, with `CHANGELOG.md` and `__version__.py` both at `0.27.10`. Duplicate check: all 130 open pull requests enumerated, 10 touching `unstructured/chunking/`. I grepped each diff for added lines matching `_validate|overlap.*must be|overlap_arg`. The only hit is #4487, which caps `combine_text_under_n_chars` in `title.py::_validate`: different file, different function, different parameter. #4392 is the nearest neighbour and changes `_split_by_tokens` rather than validation, so the two do not collide. @cragwolfe you merged the last chunking change here. Would you rather this raised, or clamped a negative overlap to zero with a warning? <!-- This is an auto-generated description by cubic. --> <a href="https://cubic.dev/pr/Unstructured-IO/unstructured/pull/4501?utm_source=github" target="_blank" rel="noopener noreferrer" data-no-image-dialog="true"><picture><source media="(prefers-color-scheme: dark)" srcset="https://www.cubic.dev/buttons/review-in-cubic-dark.svg"><source media="(prefers-color-scheme: light)" srcset="https://www.cubic.dev/buttons/review-in-cubic-light.svg"><img alt="Review in cubic" src="https://www.cubic.dev/buttons/review-in-cubic-dark.svg"></picture></a> <!-- End of auto-generated description by cubic. -->
1 of 3 tasks
This branch has not been deployed
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Summary
Token-based chunking (
max_tokens+tokenizer) combined withoverlap(oroverlap_all) hangs in an unbounded CPU loop whenever an element contains a whitespace-free run longer thanmax_tokens— a long URL, hash, base64/JWT blob, filesystem path, or biological sequence. It is reachable from the documented publicchunk_elements(basic) andchunk_by_titleAPIs on realistic input, with no error surfaced.Root cause
_TextSplitter._split_by_tokensinunstructured/chunking/base.pydoes not guarantee forward progress whenoverlap > 0. For a long unbroken token:max_tokensfragment and returnsoverlapped_remainder = tail + " " + raw_remainder, inserting a space that was not in the original text.fragment = tail) and re-prependstail + " ", producing a remainder byte-for-byte identical to the input.PreChunk._iter_text_splits(while remainder: s, remainder = split(remainder)) then loops forever. Observed:iter0 -> input=2000, remainder=1990; iter1 -> input=1990, remainder=1990(identical), spinning at 100% CPU.The character-mode path already enforces this invariant (
pos = overlap + 1, plus alen(remainder) >= len(s): continueguard). Token mode was missing it.Fix
In both overlap branches of
_split_by_tokens, apply the overlap only when the resulting remainder is strictly shorter than the input; otherwise fall back to the un-overlappedraw_remainder, which is always strictly shorter thans. Every split now makes forward progress, so_iter_text_splitsalways terminates. Character mode and token mode withoverlap=0are unaffected.Reproduction
Hangs on
main, returns after this fix:Controls that already worked, and still do: the same input with
overlap=0, and character mode withmax_characters=64, overlap=8.Testing
A regression test drives the real split loop with no iteration cap, so it reproduces the true hang on the unfixed code, and asserts termination plus strictly shrinking remainders:
On this branch it passes in under a second. Reverting only
unstructured/chunking/base.pytomainand running the same test undertimeout 25 pytest ...exits 124 (killed by the timeout, i.e. the hang). The fulltest_unstructured/chunking/test_base.pysuite (225 tests) passes, andruff check/ruff format --checkare clean.Changelog