# Optimized Table Tokenization for Table Structure Recognition > A 5-token table structure representation with backward-only syntax rules for efficient autoregressive table structure recognition - Authors: Hunter Heidenreich - Published: 2023-05-05 - Updated: 2026-03-12 - Paper: Preprint (arXiv) - Paper: Published (ICDAR 2023) - Source: Bevaya Labs, --- ## TL;DR OTSL replaces HTML with a 5-token language for autoregressive table structure recognition. Its backward-only syntax rules enable on-the-fly validation, cut sequence length roughly in half, and yield consistent improvements in both accuracy and inference speed across three public benchmarks when evaluated with the TableFormer architecture. ## What kind of paper is this? **OTSL (Optimized Table Structure Language)** proposes a tokenization language with syntactic constraints for table structure recognition. * **Dominant Basis:** $\Psi_{\text{Method}}$ * The paper proposes a new representation language (OTSL) to replace HTML in Image-to-Sequence (Im2Seq) models. It redesigns the output vocabulary to enforce structural validity and improve efficiency. * **Secondary Basis:** $\Psi_{\text{Evaluation}}$ * It systematically compares HTML versus OTSL representations across multiple datasets (PubTabNet, FinTabNet, PubTables-1M) and model configurations, focusing on efficiency (latency) and accuracy (TEDs, mAP). ## Motivation: The HTML Bottleneck Image-to-Markup-Sequence (Im2Seq) table structure recognition typically reuses general-purpose HTML tokenization. However, HTML was not designed for autoregressive decoding efficiency and presents several challenges for neural models: * **Large Vocabulary:** Requires at least 28 tokens to cover common rowspan/colspan attributes. The skewed token frequency distribution complicates learning. * **Variable Row Lengths:** Rows with complex spanning produce longer token sequences. This variance makes positional encoding and attention mechanisms less effective. * **Late Error Detection:** Invalid HTML outputs are difficult to detect early during generation. Partial sequences often violate structural consistency (e.g., missing closing tags) but remain syntactically valid markup until the end. * **Attention Drift:** Long sequences on large tables cause output misalignment. This is particularly damaging for bounding box predictions in later rows. ## Novelty: The 5-Token OTSL Vocabulary The core innovation is **OTSL**, a minimal vocabulary representing a table as a rectangular grid. ### 1. Minimal Vocabulary The language reduces the problem to just 5 tokens: * **C**: New cell (anchor for cell region top-left). * **L**: Merge with left neighbor (horizontal span continuation). * **U**: Merge with upper neighbor (vertical span continuation). * **X**: Merge with both left and upper (2D span interior). * **NL**: End-of-row marker. ### 2. Syntactic Constraints The representation enforces specific structure via backward-only syntax rules. Each token can be validated using only previously generated tokens, enabling incremental constraint enforcement during decoding: 1. Left neighbor of **L** must be **C** or **L**. 2. Upper neighbor of **U** must be **C** or **U**. 3. Left neighbor of **X** must be **U** or **X**; upper neighbor must be **L** or **X**. 4. First row allows only **C** and **L**. 5. First column allows only **C** and **U**. 6. All rows have equal length and are terminated by **NL**. ### 3. Error Mitigation Invalid token predictions signal decoding errors immediately. The authors propose a heuristic that replaces the highest-confidence invalid token with the next-highest valid candidate until syntax rules are satisfied. ## Methodology: TableFormer Evaluation The authors evaluate OTSL using the **TableFormer** architecture, an encoder-decoder transformer with separate decoders for structure (HTML/OTSL) and cell bounding boxes. ### Experiments * **Hyperparameter Sweep:** Compared HTML vs. OTSL on PubTabNet with varying encoder/decoder depths (2-6 layers). * **Cross-Dataset Evaluation:** Validated the best configuration (6 encoder, 6 decoder, 8 heads) on three major benchmarks: * **PubTabNet:** 395K samples (Scientific). * **FinTabNet:** 113K samples (Financial). * **PubTables-1M:** ~1M samples (Scientific/Digital). ### Metrics * **TEDs (Tree Edit Distance):** Structural accuracy, reported separately for simple/complex/all tables. OTSL outputs are converted back to HTML for fair comparison. * **mAP@0.75:** Mean Average Precision at 0.75 IoU threshold for cell bounding boxes. * **Inference Time:** Measured on a single-core CPU (AMD EPYC 7763 @ 2.45 GHz). ## Results: Efficiency and Accuracy The results suggest that optimizing the representation yields consistent improvements without architectural changes. ### 1. Speed OTSL achieves approximately **$2\times$ inference speedup** across configurations, primarily due to shorter sequence lengths. The authors report that OTSL reduces sequence length to roughly half that of HTML on average (e.g., 30 tokens vs. 55 for the example in Figure 1). * **PubTabNet:** 2.73s (OTSL) vs. 5.39s (HTML). * **PubTables-1M:** 1.79s (OTSL) vs. 3.26s (HTML). ### 2. Accuracy * **PubTabNet:** Similar all-TEDs (0.955); improved mAP (0.88 vs. 0.857). * **FinTabNet:** Large gains observed: all-TEDs **0.959** vs. 0.920; mAP **0.862** vs. 0.722. * **PubTables-1M:** Gains on both metrics: all-TEDs 0.977 vs. 0.966. ### Limitations * **Syntactic vs. Structural:** While OTSL guarantees a valid *grid*, it does not guarantee the *correct* grid. A valid OTSL sequence can still represent an incorrect table structure. * **Heuristic Reliance:** The token replacement strategy is a heuristic. The paper does not compare this against formal constrained decoding or beam search. * **Architecture Specificity:** The evidence is limited to TableFormer. It is unclear if these gains transfer to graph-based or object-detection-based TSR pipelines. ## Reproducibility The work is **partially reproducible**. The evaluation datasets are publicly available, but the authors do not release code, model weights, or the OTSL-format dataset conversions (promised in the paper but no public link is provided). Reimplementation requires building both the OTSL tokenization logic and the TableFormer architecture from the paper description alone. ### Models - The architecture used is **TableFormer**, an encoder-decoder transformer with separate decoders for structure tokens and cell bounding boxes. - The best configuration uses 6 encoder layers, 6 decoder layers, and 8 attention heads. Smaller configurations (4/4, 2/4, 4/2) are also evaluated. - No parameter counts are reported. No pretrained weights are released. ### Algorithms - Training procedure details (optimizer, learning rate, batch size, epochs) are **not reported** in the paper. - The error-mitigation heuristic replaces the highest-confidence invalid token with the next-highest valid candidate until OTSL syntax rules are satisfied. No comparison is made against constrained decoding or beam search alternatives. ### Data - **PubTabNet:** 395K samples of scientific tables, semi-automatically generated from PubMed Central. - **FinTabNet:** 113K samples of financial tables. - **PubTables-1M:** Approximately 1M samples of scientific/digital tables. - Ground truth from all datasets was converted to OTSL format. The authors state these conversions will be made publicly available, but no download link is provided in the paper. ### Evaluation - **TEDs (Tree Edit Distance score):** Measures structural accuracy. OTSL predictions are converted back to HTML before computing TEDs for fair comparison. Reported separately for simple tables, complex tables (those with spanning cells), and all tables. - **mAP@0.75:** Mean Average Precision at $0.75$ IoU threshold for cell bounding box predictions. - Baselines are HTML-based TableFormer models with identical architecture configurations, making the comparison controlled. - No error bars, significance tests, or multi-run statistics are reported. ### Hardware - **Inference:** All timing results measured on a single core of an **AMD EPYC 7763 CPU @ 2.45 GHz**. - **Training:** GPU type, count, and training duration are **not reported**. ## BibTeX ```bibtex @inproceedings{lysak2023optimized, title={Optimized Table Tokenization for Table Structure Recognition}, author={Lysak, Maksym and Nassar, Ahmed and Livathinos, Nikolaos and Auer, Christoph and Staar, Peter}, booktitle={Document Analysis and Recognition -- ICDAR 2023}, pages={37--50}, year={2023}, publisher={Springer}, doi={10.1007/978-3-031-41679-8_3} } ```