CTC prefix beam search, step by step
Optional · supplementary note 1 of 5 for DLCV 06 · Text in Images: OCR and Document Understanding. Nothing in the main text depends on it; citation numbers refer to the reference list at the bottom of this page.
Navigate: this page and this track: Navigate: this page and this track
This note explains how a CTC decoder finds a likely text rather than a likely path, by searching over prefixes instead of alignments.
What is searched. A prefix is a partial transcription, such as “ca”. After reading frames , many alignments collapse to the same prefix. Prefix beam search keeps, for each prefix, two numbers:
- , the total probability of alignments of frames that collapse to and end in a blank;
- , the total probability of those that end in the last label of .
Their sum is the probability that the first frames read as . The split is needed because the next symbol behaves differently in the two cases.
Update rules. For each kept prefix and each symbol at frame , with the network’s probability of :
- Blank (): the prefix does not change, and the alignment now ends in a blank: add to .
- Repeat of the last label ( equals the last label of ): if the previous symbol was that label, the repeat merges and the prefix stays : add to . If the previous symbol was a blank, the repeat starts a new copy: add to . This is how “aa” can be written as “a-a”.
- Any other label: extend the prefix: add to .
After each frame, keep only the prefixes with the largest (the beam width). At the end, return the best prefix. With an unlimited beam the result is exact for the CTC model; with it behaves almost like greedy decoding.
Code · Python · 33 lines
import numpy as np
alphabet = ["-", "c", "a", "t"]
probs = np.array([[0.10, 0.80, 0.05, 0.05],
[0.20, 0.05, 0.70, 0.05],
[0.60, 0.05, 0.30, 0.05],
[0.55, 0.02, 0.03, 0.40],
[0.55, 0.02, 0.03, 0.40]])
def prefix_beam_search(probs, beam=3):
# Each prefix keeps two numbers: p_b (all its alignments end in blank)
# and p_nb (they end in the prefix's last label).
beams = {(): (1.0, 0.0)}
for frame in probs:
nxt = {}
def add(prefix, pb, pnb):
ob, onb = nxt.get(prefix, (0.0, 0.0))
nxt[prefix] = (ob + pb, onb + pnb)
for prefix, (pb, pnb) in beams.items():
add(prefix, (pb + pnb) * frame[0], 0.0) # emit blank
for s in range(1, len(frame)):
p = frame[s]
if prefix and prefix[-1] == s:
add(prefix, 0.0, pnb * p) # repeat merges
add(prefix + (s,), 0.0, pb * p) # blank separated
else:
add(prefix + (s,), 0.0, (pb + pnb) * p) # new label
beams = dict(sorted(nxt.items(), key=lambda kv: -sum(kv[1]))[:beam])
return [("".join(alphabet[s] for s in k), sum(v)) for k, v in beams.items()]
for B in [1, 3, 20]:
top = prefix_beam_search(probs, beam=B)[:2]
print(f"beam={B:2d}: " + ", ".join(f"{t!r} p={p:.3f}" for t, p in top))Output
beam= 1: 'ca' p=0.155
beam= 3: 'cat' p=0.344, 'ca' p=0.179
beam=20: 'cat' p=0.363, 'ca' p=0.179On the chapter’s toy, a beam of 1 returns “ca”, like greedy decoding. A beam of 3 already finds “cat”, with a slightly low probability (0.344) because some of its alignments passed through prefixes that were pruned. A beam of 20 keeps every prefix here and reproduces the exact value 0.363 from the brute-force sum.
Pitfalls. Work in log space for long sequences, since the products underflow. Do not deduplicate by path, only by prefix. When a lexicon or language model is added, its score is usually applied when a prefix is extended by a label, weighted by a tuned factor, and often combined with a bonus per emitted character so that the search does not favor short outputs; the weights are tuned on held-out data, and the same over-correction risk described in the main text applies.
References
- S. Long, X. He and C. Yao, “Scene text detection and recognition: The deep learning era,” International Journal of Computer Vision, vol. 129, pp. 161–184, 2021. doi
- X. Chen, L. Jin, Y. Zhu, C. Luo and T. Wang, “Text recognition in the wild: A survey,” ACM Computing Surveys, vol. 54, no. 2, 2021. doi
- L. Cui, Y. Xu, T. Lv and F. Wei, “Document AI: Benchmarks, models and applications,” arXiv:2111.08609, 2021. arXiv
- Q. Zhang, B. Wang, V. S.-J. Huang, J. Zhang, Z. Wang, H. Liang, C. He and W. Zhang, “Document parsing unveiled: Techniques, challenges, and prospects for structured information extraction,” arXiv:2410.21169, 2024. arXiv
- D. Karatzas, F. Shafait, S. Uchida, M. Iwamura, L. Gomez i Bigorda, S. Robles Mestre, J. Mas et al., “ICDAR 2013 Robust Reading Competition,” in Proc. International Conference on Document Analysis and Recognition (ICDAR), pp. 1484–1493, 2013. doi
- D. Karatzas, L. Gomez-Bigorda, A. Nicolaou, S. Ghosh, A. Bagdanov, M. Iwamura, J. Matas et al., “ICDAR 2015 competition on Robust Reading,” in Proc. International Conference on Document Analysis and Recognition (ICDAR), pp. 1156–1160, 2015. doi
- J. Baek, G. Kim, J. Lee, S. Park, D. Han, S. Yun, S. J. Oh and H. Lee, “What is wrong with scene text recognition model comparisons? Dataset and model analysis,” in Proc. IEEE/CVF ICCV, pp. 4714–4722, 2019. doi
- N. Otsu, “A threshold selection method from gray-level histograms,” IEEE Transactions on Systems, Man, and Cybernetics, vol. 9, no. 1, pp. 62–66, 1979. doi
- J. Sauvola and M. Pietikäinen, “Adaptive document image binarization,” Pattern Recognition, vol. 33, no. 2, pp. 225–236, 2000. doi
- C. K. Ch’ng and C. S. Chan, “Total-Text: A comprehensive dataset for scene text detection and recognition,” in Proc. ICDAR, pp. 935–942, 2017. doi
- Y. Liu, L. Jin, S. Zhang, C. Luo and S. Zhang, “Curved scene text detection via transverse and longitudinal sequence connection,” Pattern Recognition, vol. 90, pp. 337–345, 2019. doi
- X. Zhou, C. Yao, H. Wen, Y. Wang, S. Zhou, W. He and J. Liang, “EAST: An efficient and accurate scene text detector,” in Proc. IEEE CVPR, pp. 2642–2651, 2017. doi
- W. Wang, E. Xie, X. Li, W. Hou, T. Lu, G. Yu and S. Shao, “Shape robust text detection with progressive scale expansion network,” in Proc. IEEE/CVF CVPR, pp. 9328–9337, 2019. doi
- M. Liao, Z. Wan, C. Yao, K. Chen and X. Bai, “Real-time scene text detection with differentiable binarization,” in Proc. AAAI Conference on Artificial Intelligence, vol. 34, pp. 11474–11481, 2020. doi
- Y. Baek, B. Lee, D. Han, S. Yun and H. Lee, “Character region awareness for text detection,” in Proc. IEEE/CVF CVPR, pp. 9357–9366, 2019. doi
- B. Shi, X. Bai and C. Yao, “An end-to-end trainable neural network for image-based sequence recognition and its application to scene text recognition,” IEEE TPAMI, vol. 39, no. 11, pp. 2298–2304, 2017. doi
- A. Graves, S. Fernández, F. Gomez and J. Schmidhuber, “Connectionist temporal classification: Labelling unsegmented sequence data with recurrent neural networks,” in Proc. ICML, pp. 369–376, 2006. doi
- B. Shi, M. Yang, X. Wang, P. Lyu, C. Yao and X. Bai, “ASTER: An attentional scene text recognizer with flexible rectification,” IEEE TPAMI, vol. 41, no. 9, pp. 2035–2048, 2019. doi
- M. Li, T. Lv, J. Chen, L. Cui, Y. Lu, D. Florencio, C. Zhang, Z. Li and F. Wei, “TrOCR: Transformer-based optical character recognition with pre-trained models,” in Proc. AAAI Conference on Artificial Intelligence, vol. 37, pp. 13094–13102, 2023. doi
- D. Bautista and R. Atienza, “Scene text recognition with permuted autoregressive sequence models,” in Proc. ECCV, pp. 178–196, 2022. doi
- S. Fang, H. Xie, Y. Wang, Z. Mao and Y. Zhang, “Read like humans: Autonomous, bidirectional and iterative language modeling for scene text recognition,” in Proc. IEEE/CVF CVPR, pp. 7094–7103, 2021. doi
- Y. Liu, Z. Li, M. Huang, B. Yang, W. Yu, C. Li, X.-C. Yin, C.-L. Liu, L. Jin and X. Bai, “OCRBench: On the hidden mystery of OCR in large multimodal models,” Science China Information Sciences, vol. 67, 2024. doi
- M. Jaderberg, K. Simonyan, A. Vedaldi and A. Zisserman, “Synthetic data and artificial neural networks for natural scene text recognition,” arXiv:1406.2227, 2014. arXiv
- A. Gupta, A. Vedaldi and A. Zisserman, “Synthetic data for text localisation in natural images,” in Proc. IEEE CVPR, pp. 2315–2324, 2016. doi
- X. Liu, D. Liang, S. Yan, D. Chen, Y. Qiao and J. Yan, “FOTS: Fast oriented text spotting with a unified network,” in Proc. IEEE/CVF CVPR, pp. 5676–5685, 2018. doi
- P. Lyu, M. Liao, C. Yao, W. Wu and X. Bai, “Mask TextSpotter: An end-to-end trainable neural network for spotting text with arbitrary shapes,” in Proc. ECCV, pp. 71–88, 2018. doi
- Y. Liu, H. Chen, C. Shen, T. He, L. Jin and L. Wang, “ABCNet: Real-time scene text spotting with adaptive Bezier-curve network,” in Proc. IEEE/CVF CVPR, pp. 9806–9815, 2020. doi
- X. Zhong, J. Tang and A. Jimeno Yepes, “PubLayNet: Largest dataset ever for document layout analysis,” in Proc. ICDAR, pp. 1015–1022, 2019. doi
- B. Pfitzmann, C. Auer, M. Dolfi, A. S. Nassar and P. Staar, “DocLayNet: A large human-annotated dataset for document-layout segmentation,” in Proc. ACM SIGKDD, pp. 3743–3751, 2022. doi
- Y. Xu, M. Li, L. Cui, S. Huang, F. Wei and M. Zhou, “LayoutLM: Pre-training of text and layout for document image understanding,” in Proc. ACM SIGKDD, pp. 1192–1200, 2020. doi
- R. Smith, “An overview of the Tesseract OCR engine,” in Proc. ICDAR, vol. 2, pp. 629–633, 2007. doi
- Y. Huang, T. Lv, L. Cui, Y. Lu and F. Wei, “LayoutLMv3: Pre-training for document AI with unified text and image masking,” in Proc. ACM International Conference on Multimedia, pp. 4083–4091, 2022. doi
- G. Jaume, H. K. Ekenel and J.-P. Thiran, “FUNSD: A dataset for form understanding in noisy scanned documents,” in Proc. ICDAR Workshops (OST), 2019. doi
- G. Kim, T. Hong, M. Yim, J. Nam, J. Park, J. Yim, W. Hwang, S. Yun, D. Han and S. Park, “OCR-free document understanding transformer,” in Proc. ECCV, pp. 498–517, 2022. doi
- K. Lee, M. Joshi, I. R. Turc, H. Hu, F. Liu, J. M. Eisenschlos, U. Khandelwal, P. Shaw, M.-W. Chang and K. Toutanova, “Pix2Struct: Screenshot parsing as pretraining for visual language understanding,” in Proc. ICML, PMLR vol. 202, pp. 18893–18912, 2023. PMLR
- L. Blecher, G. Cucurull, T. Scialom and R. Stojnic, “Nougat: Neural optical understanding for academic documents,” in Proc. ICLR, 2024. OpenReview · arXiv
- U.-V. Marti and H. Bunke, “The IAM-database: An English sentence database for offline handwriting recognition,” International Journal on Document Analysis and Recognition, vol. 5, pp. 39–46, 2002. doi
- C.-L. Liu, F. Yin, D.-H. Wang and Q.-F. Wang, “CASIA online and offline Chinese handwriting databases,” in Proc. ICDAR, pp. 37–41, 2011. doi
- B. Shi, C. Yao, M. Liao, M. Yang, P. Xu, L. Cui, S. Belongie, S. Lu and X. Bai, “ICDAR2017 competition on reading Chinese text in the wild (RCTW-17),” in Proc. ICDAR, pp. 1429–1434, 2017. doi · arXiv
- T.-L. Yuan, Z. Zhu, K. Xu, C.-J. Li, T.-J. Mu and S.-M. Hu, “A large Chinese text dataset in the wild,” Journal of Computer Science and Technology, vol. 34, pp. 509–521, 2019. doi · arXiv
- F. Xue and R. Ishida (eds.), “Requirements for Chinese Text Layout,” W3C Group Note (draft of 7 October 2026). W3C
- N. Nayef, Y. Patel, M. Busta, P. N. Chowdhury, D. Karatzas, W. Khlif, J. Matas et al., “ICDAR2019 Robust Reading Challenge on multi-lingual scene text detection and recognition — RRC-MLT-2019,” in Proc. ICDAR, pp. 1582–1587, 2019. doi · arXiv
- R. A. Wagner and M. J. Fischer, “The string-to-string correction problem,” Journal of the ACM, vol. 21, no. 1, pp. 168–173, 1974. doi
- M. Mathew, D. Karatzas and C. V. Jawahar, “DocVQA: A dataset for VQA on document images,” in Proc. IEEE/CVF WACV, pp. 2199–2208, 2021. doi
- A. Mishra, K. Alahari and C. V. Jawahar, “Scene text recognition using higher order language priors,” in Proc. BMVC, 2012. doi
- K. Wang, B. Babenko and S. Belongie, “End-to-end scene text recognition,” in Proc. IEEE ICCV, pp. 1457–1464, 2011. doi
- L. Ouyang, Y. Qu, H. Zhou, J. Zhu, R. Zhang, Q. Lin, B. Wang, Z. Zhao et al., “OmniDocBench: Benchmarking diverse PDF document parsing with comprehensive annotations,” in Proc. IEEE/CVF CVPR, pp. 24838–24848, 2025. CVF
- H. Wei, C. Liu, J. Chen, J. Wang, L. Kong, Y. Xu, Z. Ge, L. Zhao et al., “General OCR theory: Towards OCR-2.0 via a unified end-to-end model,” arXiv:2409.01704, 2024. arXiv
- J. Poznanski, A. Rangapur, J. Borchardt, J. Dunkelberger, R. Huff, D. Lin, C. Wilhelm et al., “olmOCR: Unlocking trillions of tokens in PDFs with vision language models,” arXiv:2502.18443, 2025. arXiv
- H. Wei, Y. Sun and Y. Li, “DeepSeek-OCR: Contexts optical compression,” arXiv:2510.18234, 2025. arXiv
- C. Wolf and J.-M. Jolion, “Object count/area graphs for the evaluation of object detection and segmentation algorithms,” International Journal of Document Analysis and Recognition, vol. 8, pp. 280–296, 2006. doi