OCR post-processing needs OCR text aligned word by word with its ground truth. Data sets rarely provide that mapping, and a monotone aligner can lose its place when zoning errors permute the reading order. We revisit this problem, the Zoning Problem of our 2019 paper, with a protocol that tests correctness under such permutations. We apply OCR-side reading-order permutations with construction-time word-level gold and score correct-match F1, cascade length and recovery. We compare the 2019 location-aware aligner, a re-anchoring extension of it, a RETAS-style baseline (RETAS-lite), a multi-region aligner that combines unique-word and unique n-gram anchors with chunk-to-window assignment, genalog's RETAS and the original Java RETAS. Experiments use synthetic character noise with block moves, paragraph swaps and column interleaving, historical newspaper reading-order permutations, geometry-derived gold for Tesseract OCR, and a small word-box set. Synthetic tests show where local tracking fails after large displacements and where unique-anchor methods collapse when unique anchors are scarce. On our synthetic boilerplate page the 2019 method had the highest F1 among those tested. Historical newspaper and geometry-derived evaluations carry the limitations of approximate gold and the article-order convention. The first multi-region version has a quadratic scaling cost. Local tracking remains fragile under large reading-order changes; the tested anchor-based methods handle many of those cases but fail when unique anchors are scarce. Approximate gold, the article-order convention, missing residual annotation, and the lack of modern multi-column word-level ground truth remain limitations.
Figures & tables
Aligner
Block move
Paragraph swap
Column interleave
Location-aware (2019)
0.890 [0.865, 0.913]
0.012 [0.003, 0.029]
0.255 [0.242, 0.265]
+ re-anchoring
0.922 [0.907, 0.935]
0.339 [0.338, 0.340]
0.353 [0.348, 0.358]
RETAS-lite
0.998 [0.996, 0.999]
0.977 [0.975, 0.977]
0.907 [0.904, 0.909]
genalog (RETAS)
0.920 [0.920, 0.921]
0.181 [0.164, 0.215]
0.500 [0.499, 0.501]
Multi-region v1
1.000 [0.999, 1.000]
1.000 [1.000, 1.000]
0.983 [0.981, 0.985]
Table 1: Synthetic zoning ablation: word-alignment F1 against gold, mean over 10 seeds with 95% bootstrap CI (medium severity, 6% character noise, 517-token base text). Reading order is permuted on the OCR side only.
Block move
Paragraph swap
Column interleave
Aligner
Cˉ
R10
Cˉ
R10
Cˉ
R10
Location-aware (2019)
25.3
0.33
129.0
0.17
48.8
0.23
+ re-anchoring
18.2
0.53
66.5
0.17
23.6
0.33
RETAS-lite
0.7
1.00
3.3
0.98
1.3
1.00
genalog (RETAS)
13.7
0.67
207.0
0.07
6.3
0.51
Multi-region v1
0.0
1.00
0.0
1.00
0.1
1.00
Table 2: Cascade behaviour on the synthetic ablation of Table 1 : mean cascade length Cˉ (consecutive wrong words after a zoning break) and recovery rate R10 (share of breaks followed by a correct match within 10 words). Means over 10 seeds.
Figure 1: Token-index schematic of an OCR-side paragraph swap. Blocks are labelled by ground-truth index ranges, not by source text. Construction gold maps each OCR token to its original index. The 2019 tracker keeps a local window near the last accepted match ( w=20 ), so after the swap it continues searching near paragraph A while the OCR stream reads paragraph B; the stored mean cascade on the medium paragraph-swap condition is 129 tokens (Table 2 ). Unique-word and n -gram anchors are not bound to that window.
Figure 2: Mean cascade length on the synthetic ablation at medium severity and 6% character noise, the same stored rows that fill Table 2 . No new aligner runs.
Aligner
F1
R10
Runtime (s)
Location-aware (2019)
0.573 [0.435, 0.707]
0.550
0.008
+ re-anchoring
0.578 [0.441, 0.712]
0.552
0.031
RETAS-lite
0.986 [0.972, 0.995]
0.987
0.005
Multi-region v1
0.987 [0.969, 0.999]
0.995
0.009
genalog (RETAS)
0.668 [0.549, 0.792]
0.643
2.544
Java RETAS
0.590 [0.557, 0.623]
0.870
0.102
Table 3: KB IMPACT newspaper pages whose geometric order differs from the stored XML-traversal linearization of PAGE region references (40 of 50 scanned pages). The ground-truth text is used on both sides, so there is no OCR noise; only the reading order differs. F1 with 95% bootstrap CI over pages, recovery R10 and runtime per page.
Aligner
F1 (all gold)
F1 (high-conf. gold)
Multi-region v1
0.432 [0.404, 0.460]
0.650 [0.623, 0.675]
Multi-region v2
0.403 [0.375, 0.432]
0.607 [0.579, 0.634]
RETAS-lite
0.354 [0.326, 0.381]
0.504 [0.477, 0.530]
genalog (RETAS)
0.254 [0.230, 0.277]
0.371 [0.342, 0.399]
Java RETAS
0.176 [0.164, 0.187]
0.273 [0.260, 0.284]
+ re-anchoring
0.042 [0.034, 0.051]
0.059 [0.050, 0.071]
Table 4: Real Tesseract OCR on 200 held-out KB IMPACT pages (seed 42; at most 600 OCR words per page), scored against geometry-derived gold. “All” scores every OCR word that received a gold match; “high-conf.” keeps only words whose gold match is exact or has NED ≤0.15 with IoU ≥0.05 . The gold is approximate (Sect. 5.1 ), with the limitations described there. Mean F1 with 95% bootstrap CI over pages.
Figure 3: F1 on the 200 KB IMPACT pages with Tesseract OCR (Table 4 ), on all and high-confidence geometry gold, with bootstrap intervals.
Figure 4: Page-level all-gold F1 on the 200 KB IMPACT pages with Tesseract OCR. Left: multi-region v1 against RETAS-lite (the diagonal is equality). Right: histogram of the per-page difference, with the mean marked. Recomputed from the stored per-page scores that underlie Table 4 .
Aligner
F1 (all gold)
F1 (high-conf. gold)
Multi-region v1
0.742 [0.687, 0.795]
0.948 [0.918, 0.975]
Multi-region v2
0.735 [0.677, 0.791]
0.947 [0.917, 0.973]
RETAS-lite
0.698 [0.629, 0.765]
0.910 [0.869, 0.949]
Location-aware (2019)
0.483 [0.373, 0.592]
0.694 [0.547, 0.835]
genalog (RETAS)
0.492 [0.341, 0.628]
0.647 [0.437, 0.833]
Java RETAS
0.378 [0.323, 0.436]
0.663 [0.609, 0.712]
Table 5: Fourteen CC0 pages with human word boxes (blackletter and antiqua prints), Tesseract OCR, gold from word-box IoU and NED. Small sample; the gold-matching and domain limitations still apply.
Condition
MR v1
RETAS-lite
Java RETAS
2019
Δ (MR v1 − lite)
p
Noise 0.10
0.972
0.893
0.476
0.264
+0.079 [+0.076, +0.083]
< 0.001
Noise 0.15
0.973
0.889
0.457
0.243
+0.084 [+0.078, +0.091]
< 0.001
Noise 0.20
0.957
0.873
0.436
0.228
+0.084 [+0.077, +0.094]
< 0.001
Noise 0.25
0.962
0.870
0.416
0.268
+0.093 [+0.086, +0.099]
< 0.001
8 regions
0.998
0.981
0.432
0.141
+0.017 [+0.014, +0.021]
< 0.001
15 regions
0.995
0.969
0.385
0.101
+0.027 [+0.022, +0.031]
< 0.001
Table 6: Stress tests with frozen parameters, 10 seeds. Noise rows use column interleave with the given per-word character-noise rate; region rows split the page into k regions; short pages have about 96 words; the boilerplate page has 693 words containing 59 distinct word types. Δ is the paired bootstrap mean of multi-region v1 minus RETAS-lite with 95% CI, and p twice the share of bootstrap means on the other side of zero, capped at one (“ < 0.001” means none of the resamples).
Figure 5: Stress tests of Table 6 : F1 against the character-noise rate on column interleave (left) and against the number of text regions (right). Means over 10 seeds.
Multi-region v1
Multi-region v2
RETAS-lite
Tokens (seeds)
F1
s
F1
s
F1
s
1,000 (5)
0.771
0.021
0.768
0.015
0.504
0.003
5,000 (5)
0.423
0.588
0.418
0.219
0.294
0.011
10,000 (5)
0.334
2.533
0.326
0.036
0.326
0.036
25,000 (3)
0.284
14.7
0.343
0.153
0.343
0.148
50,000 (3)
0.256
61.5
0.341
0.511
0.341
0.507
Table 7: Long documents built from distinct text (no repetition), column interleave, medium severity, 6% noise. Mean F1 over seeds (number of seeds in parentheses; range over seeds in Fig. 6 ) and mean runtime per document in seconds. v1 and RETAS-lite are from the Step-7 scaling study; v2 is from the separate Step-8 re-run. At 8,000 tokens and above, v2 hands the document to RETAS-lite, so its F1 equals RETAS-lite by construction.
Figure 6: Long documents of distinct text (Table 7 ): mean F1 with the range over seeds (left) and runtime per document on a log scale (right).
Evaluation
v1 F1
v2 F1
Δ (v2 − v1)
IMPACT test-200, all gold
0.432 [0.404, 0.460]
0.403 [0.375, 0.432]
− 0.029 [ − 0.032, − 0.026]
IMPACT test-200, high-conf.
0.650 [0.623, 0.675]
0.607 [0.579, 0.634]
− 0.043 [ − 0.048, − 0.038]
Word-box gold, all
0.742 [0.687, 0.795]
0.735 [0.677, 0.791]
− 0.007 [ − 0.012, − 0.002]
TREC synthetic (Step 8)
0.945 [0.935, 0.955]
0.942 [0.933, 0.952]
− 0.002 [ − 0.004, − 0.001]
Boilerplate stress
0.125 [0.118, 0.134]
0.159 [0.151, 0.168]
+0.034 [+0.029, +0.041]
Long document, 50k tokens a
0.256 (0.239 to 0.287)
0.341 (0.320 to 0.363)
+0.085 (+0.077 to +0.096)
Table 8: Multi-region v1 and v2, both frozen, on the held-out evaluations (Step-8 re-runs unless noted). Δ is the paired bootstrap mean of v2 minus v1 with 95% CI. a Three seeds only, so we give the mean and the range over seeds instead of a bootstrap interval. Synthetic and long-document entries are distinct from the newspaper and word-box evaluations. The TREC row uses synthetic character noise and column interleaving, not real OCR.
degrade5 ( ≈ 5% CER)
degrade20 ( ≈ 20% CER)
Aligner
Agreement F1
Matched
Agreement F1
Matched
Location-aware (2019)
0.888 [0.827, 0.933]
0.957
0.102 [0.076, 0.131]
0.740
+ re-anchoring
0.893 [0.834, 0.936]
0.959
0.107 [0.081, 0.137]
0.743
RETAS-lite
0.934 [0.921, 0.945]
0.912
0.378 [0.354, 0.404]
0.375
Multi-region v1
0.944 [0.934, 0.954]
0.933
0.541 [0.521, 0.561]
0.671
Java RETAS
0.450 [0.438, 0.463]
0.311
0.179 [0.170, 0.188]
0.145
Table 9: TREC-5 Confusion Track, 30 randomly sampled Federal Register documents. There is no word-level gold, so we report agreement F1 with genalog’s alignment as a soft reference (genalog scores 1 by definition) and the fraction of OCR words that receive any match (“matched”), the closest analogue we can compute to the 2019 success rate. Neither is a correctness score.
Reading order inference remains a critical bottleneck in the digitization of complex historical manuscripts, where pages contain multiple spatially interleaved reading streams, the canonical example being the Glossa Ordinaria layout, in which a central text is surrounded by commentaries that wrap around it in non-rectangular, non-convex regions. We present a training-free, graph-based framework: each OCR text line becomes a node in a directed candidate-transition graph, edges are scored by a weighted additive ensemble of two lightweight language-model signals (causal language model conditional likelihood and BERT next-sentence prediction, NSP; a third sentence-embedding signal was evaluated but did not improve reading order), and the global reading order is recovered as a degree-constrained directed path cover. To avoid the cascading "edge-theft" failures of greedy edge selection, we propose a max-regret inference rule that prioritizes commitments with high opportunity cost. We evaluate on synthetic Glossa Ordinaria grid layouts, on 23 ALTO page geometries (10 historical source pages plus mirrored and flipped variants), and on a 140-page multi-column English subset of OmniDocBench, comparing our method against the canonical recursive XY-cut (PaddleOCR PP-StructureV3) and two LayoutReader variants (layout-only and text+layout) on identical inputs. On wrap-around Glossa layouts our method recovers 95% of ground-truth successor edges on average vs. XY-cut's 50%; on the OmniDocBench multi-column subset it reaches 88% macro edge accuracy versus XY-cut's 75% and LayoutReader's 25%. The LayoutReader baselines transfer poorly due to a word-level vs. line-level granularity mismatch. We additionally verify mirror-invariance under horizontal and vertical page reflections: Our method changes by less than 1 percentage point, classical XY-cut by 2 points, and LayoutReader-T by up to 8 points.
Iddo Hakim, Sharva Gogawale, Omer Ventura +4
School of Computer Science and AI, Tel Aviv University, Ramat Aviv, Israel
Word alignment has traditionally been studied between sentences, but many cross-lingual tasks increasingly require correspondences across full documents. While recent multilingual embedding models can encode long inputs, we show that applying algorithms designed for sentences directly to documents leads to performance degradation. To address this, we introduce CTFAlign, a lightweight, training-free approach for document-level word alignment. CTFAlign applies a coarse-to-fine refinement strategy that restricts the alignment search space to semantically similar regions. Additionally, we introduce MDPAlign, a simpler alternative that constrains alignments by position with a main diagonal prior. Both approaches operate directly on full documents without relying on sentence segmentation or sentence alignment. We evaluate these methods across six language pairs varying in typological distance, resourcedness, and document length. Averaged over three models, CTFAlign reduces word alignment error rate from 0.412 to 0.326. These gains transfer downstream, leading to improvements in document-level translation coverage evaluation and recognition of semantic differences. We release CTFAlign as a Python package and make the code and data to reproduce our experiments publicly available.
Michelle Wastl, Jannis Vamvas, Rico Sennrich
Department of Computational Linguistics, University of Zurich
Practical text-recognition pipelines for historical documents typically decompose layout analysis into line detection followed by a separate reading-order step, with the latter most often handled by a hand-coded geometric heuristic that struggles with marginalia, multiple columns, tables, and source-specific editorial conventions. This article introduces Orli (Ordered Regression of Lines), an end-to-end model that casts both sub-tasks as a single image-to-sequence problem: from a page image, Orli autoregressively generates text-line baselines directly in reading order. Baselines are represented in a chord-frame parameterization that anchors a line's position, orientation, and extent while encoding local geometry through perpendicular offsets; an iterative refinement head and a local visual refiner produce the final curve. Trained on a heterogeneous corpus of 196,691 pages spanning ten writing systems, Orli marginally exceeds the previously reported state of the art for cBAD line detection without dataset-specific training, reaches near perfect coverage and ordering on multiple reading-order benchmarks zero-shot, and adapts to more specialized out-of-domain layouts with limited fine-tuning. The method's source code and model weights are available under an open license at https://github.com/mittagessen/orli.