# Bidirectional Beam Search: Forward-Backward Inference in Neural Sequence Models for Fill-in-the-Blank Image Captioning

arXiv: https://arxiv.org/abs/1705.08759 · HTML: https://mlsanity.com/paper/1705.08759/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 May 2017.

## Built on by (most cited first, 8 of 8)

- [Meet in the Middle: A New Pre-training Paradigm](https://mlsanity.com/paper/2303.07295/) (2023)
- [Controllable Summarization with Constrained Markov Decision Process](https://mlsanity.com/paper/2108.03405/) (2021)
- [Discovering Non-monotonic Autoregressive Orderings with Variational Inference](https://mlsanity.com/paper/2110.15797/) (2021)
- [Beyond Greedy Search: Tracking by Multi-Agent Reinforcement Learning-based Beam Search](https://mlsanity.com/paper/2205.09676/) (2022)
- [Bidirectional Awareness Induction in Autoregressive Seq2Seq Models](https://mlsanity.com/paper/2408.13959/) (2024)
- [Surveying the Landscape of Image Captioning Evaluation: A Comprehensive Taxonomy, Trends and Metrics Analysis](https://mlsanity.com/paper/2408.04909/) (2024)
- [Distilling Specialized Orders for Visual Generation](https://mlsanity.com/paper/2504.17069/) (2025)
- [Towards Probabilistically-Sound Beam Search with Masked Language Models](https://mlsanity.com/paper/2402.15020/) (2024)

## Abstract (arXiv)

We develop the first approximate inference algorithm for 1-Best (and M-Best) decoding in bidirectional neural sequence models by extending Beam Search (BS) to reason about both forward and backward time dependencies. Beam Search (BS) is a widely used approximate inference algorithm for decoding sequences from unidirectional neural sequence models. Interestingly, approximate inference in bidirectional models remains an open problem, despite their significant advantage in modeling information from both the past and future. To enable the use of bidirectional models, we present Bidirectional Beam Search (BiBS), an efficient algorithm for approximate bidirectional inference.To evaluate our method and as an interesting problem in its own right, we introduce a novel Fill-in-the-Blank Image Captioning task which requires reasoning about both past and future sentence structure to reconstruct sensible image descriptions. We use this task as well as the Visual Madlibs dataset to demonstrate the effectiveness of our approach, consistently outperforming all baseline methods.