docling-project / docling-project/docling

docling-parse backends lose bookmark target pages, making heading matching quadratic

Open
#4,162 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
Python
Stars
66.4k
Forks
4.8k
Avg merge
2d 21h
Merged PRs (30d)
84

Description

### Bug

On a long PDF with a large table of contents, `HeadingHierarchyModel` dominates
conversion time: the threaded pipeline finishes and then a single thread runs fuzzy
string matching for many minutes.

The cause is that neither docling-parse backend supplies bookmark target pages.
`DoclingParseDocumentBackend.get_document_outline()` and
`ThreadedDoclingParseDocumentBackend.get_document_outline()` both read docling-parse's
native table of contents through `extract_outline_from_docling_parse()`, which carries
titles and nesting only, so every `_PdfOutlineItem` has `page_no=None`.

`_infer_from_bookmarks()` narrows its search by page:

```python
if bm.page_no is not None and page_no is not None and page_no != bm.page_no:
continue
score = _match_score(item.text, title)
```

With no page, that filter never fires, so every bookmark is compared against every
`SectionHeaderItem`/`ListItem` in the document. Each comparison is a fuzzy title match
costing up to four `SequenceMatcher.ratio()` calls, and both operands grow with the page
count, so the cost is quadratic in document length.

This affects the default configuration: `PdfFormatOption.backend` is
`ThreadedDoclingParseDocumentBackend`.

### Measurements

A 2252-page technical manual, first 600 pages converted, on an 8 vCPU + L4 host:

| | |
| --- | --- |
| bookmarks in the outline | 1531 |
| `SectionHeaderItem` + `ListItem` candidates | 6909 |
| `_match_score` calls | ~10.6M |
| six threaded pipeline stages | 188 s |
| `_infer_from_bookmarks` afterwards | 1140 s (86% of wall time) |
| RSS during that phase | flat at 7.7 GB |

py-spy over a 30 s window in that phase: 99.2% of samples in `_infer_from_bookmarks`,
89% inside `difflib`. Only the main thread is running; the pipeline stage threads have
already exited, so the memory the run peaked at stays resident for the whole time.

`extract_outline_from_pdfium()` resolves both the target page and its vertical position
for the same document (1531 of 1531 entries). `DoclingParseDocumentBackend` already
holds a pypdfium2 handle, and the threaded backend already opens a transient
docling-parse document purely for the outline, so both could read it through pypdfium2
and keep the native outline as a fallback.

Restricting matching to the bookmark's own page also looks like the more accurate
behaviour, not just the faster one. Using the PDF's own outline as an independent
reference over the first 200 pages of that manual (237 bookmarks in range), counting
detected headings whose title matches a bookmark on the same page:

| | page-aware | page-less |
| --- | --- | --- |
| heading has a matching bookmark on its own page | 233 | 233 |
| title matches only a bookmark on another page | 35 | 36 |
| no matching bookmark anywhere | 643 | 729 |
| `SectionHeaderItem` / `ListItem` | 911 / 790 | 998 / 703 |

Both resolve the same 233 page-confirmed headings. The page-less run promotes 87 more
list-items to headings, and those extra headings are exactly the ones this check cannot
tie to any bookmark. (The check is a plain 0.85 similarity threshold, without the
marker-stripping and containment boost the real matcher uses, so it undercounts genuine
matches on both sides equally; it is a relative comparison, not a precision figure.)

### Steps to reproduce

Convert a long PDF (hundreds of pages) that has a large embedded table of contents,
with `HeadingHierarchyOptions(enabled=True)`, using the default backend. Profile the
process, or set a breakpoint, once the per-page progress has finished: the run sits in
`heading_hierarchy_model._infer_from_bookmarks`.

### Docling version

2.124.0

### Python version

3.13.15

Contributor guide

Open the contributing guide

Research direction

Start with DoclingParseDocumentBackend.get_document_outline(), ThreadedDoclingParseDocumentBackend.get_document_outline(), and extract_outline_from_docling_parse(); compare their outline handling with extract_outline_from_pdfium(). Reproduce the long-PDF case with HeadingHierarchyOptions enabled and check that both backends provide bookmark page numbers, retain the native outline fallback, and avoid cross-page matching in _infer_from_bookmarks.

Written by the indexing model from the issue text.

Assessment

Tech stack
python
Domain
backend, performance
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
52/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.