Many sequence tasks ask a model to fill a gap. A caption has words missing in the middle, a template sentence needs a phrase that fits an image, a movie description is missing a word. The fill has to agree with the words before the gap and the words after it. Two models are needed for that: a forward model that reads left to right and a backward model that reads right to left. Finding the fill both models accept is computationally hard. The usual tool, bidirectional beam search, alternates between the two directions and can settle on a fill that neither model likes much. We propose decoding gaps with an ant colony. Many randomized "ants" build candidate fills, and each one leaves a shared numerical trace, called pheromone, on the words it used, in proportion to how well its fill satisfies both directions at once. Over iterations the colony concentrates on fills that both models accept.
The second half of the idea is where the effort pays off twice. The amount of pheromone concentrated on a single fill measures how strongly a whole population of independent searches converged. We use that measure to decide which machine-made fills to trust when we self-train on inputs nobody labeled: images with context sentences whose gaps were never filled by a human. Self-training, meaning training a model on its own confident predictions, often reinforces its own errors. Our bet is that requiring both reading directions, sampled many times, to agree is a stricter filter than one model's confidence. In two sentences: an ant colony searches for gap fills that forward and backward models jointly accept, and the colony's degree of convergence becomes the filter for pseudo-labels on unlabeled gap-filling inputs. Both claims are tested against simpler methods run at matched compute.
Core Claim
We make two claims, and each can fail on its own. The decoding claim is that pheromone-guided population search beats bidirectional beam search and plain sample-and-rerank at equal model-call budgets. We expect the advantage to grow with gap length, because long gaps are where a single proposal distribution rarely produces suffix-consistent fills and where adaptive concentration should matter. The learning claim is that pheromone concentration predicts whether a fill is correct better than model likelihood or simple sample agreement does. Self-training filtered by it should therefore improve infilling accuracy under label scarcity more than likelihood-filtered self-training.
Where This Sits in Prior Work
The decoding problem and its standard solution come from Bidirectional Beam Search. That paper shows exact decoding from bidirectional models is NP-hard. It splits a bidirectional network into calibrated forward and backward networks and alternates beam passes in coordinate descent at cost $2BMT$, where $B$ is the beam width, $M$ the number of alternations and $T$ the length. It keeps only beam frontiers and cannot escape a pair of mutually compatible but poor beams. Our method keeps the same two calibrated models and replaces coordinate descent with a population that has shared memory.
Two other bidirectional systems also motivate the design. Asynchronous Bidirectional Decoding conditions a forward beam on a single greedy backward pass. SENSESHIFT unmasks tokens greedily with a bidirectional encoder and reports that predicting all masks at once raises perplexity 5–10x. Each commits to one trajectory, and our method explores many trajectories instead.
The search machinery comes from neural-guided ant colonies. DeepACO replaces hand-designed edge heuristics with a learned network that outputs a fixed heatmap before search. GFACS uses a generative model trained to sample in proportion to reward as the prior and lets pheromone sharpen it. Both build solutions in one direction and train on fully specified optimization instances. In our setting a forward model serves as the prior, as in GFACS. A backward model supplies a lookahead heuristic that depends on what has been built so far, which addresses DeepACO's open problem of fixed heatmaps. We take the bounded pheromone ranges of Max-Min Ant Systems from Simple Max-Min Ant Systems. That analysis shows pheromone keeps moving toward good regions even when the best-so-far solution stalls, and the bounds keep the concentration signal from collapsing early to a meaningless certainty. The closest application of ant colonies to text, Ant Colony System for Multi-Document Summarization, orders sentences with graph-centrality heuristics and has no neural directional models or unlabeled data.
The self-training side is constrained by negative evidence. APLT documents confirmation bias in synchronous pseudo-labeling and fixes it with offline clustering and frozen labels. SMDA needs sharpening, consistency regularization and oversampling to profit from 420,000 unlabeled utterances. Both work on classification. Neither has a structured output that a search can verify from two directions, and that verification is what our filter adds.
Mechanism
Let the gap span positions $1..L$ between a fixed prefix and suffix, with conditioning input $x$ (an image or video clip). Ant $k$ in iteration $i$ builds a fill token by token, left to right, choosing token $w$ at position $t$ with probability
$$ P(w \mid t, w_{<t}) \propto p_f(w \mid \text{prefix}, w_{<t}, x)\; \eta_t(w)^{\beta}\; \tau_t(w)^{\alpha}, $$
where the terms are defined as follows. $p_f$ is the forward model. $\eta_t(w)$ is the backward model's probability of $w$ at position $t$ given the suffix and $x$, which acts as lookahead. $\tau_t(w)$ is the pheromone on placing $w$ at position $t$. The exponents $\alpha$ and $\beta$ weight the two terms.
After building, each fill $y$ is scored jointly as $S(y) = \log p_f(y,\text{suffix}\mid\text{prefix},x) + \log p_b(\text{prefix}, y \mid \text{suffix}, x)$, normalized by length. Including the suffix inside the forward term is what forces suffix compatibility. Pheromone evaporates by a factor $1-\rho$. The iteration's best ants deposit on their (position, token) pairs in proportion to rank-normalized $S$, and the result is clipped to $[\tau_{\min}, \tau_{\max}]$ as in Max-Min Ant Systems.
The confidence of the colony's output fill $\hat y$ is its concentration, written $c(\hat y)$. It is the mean over positions of $\tau_t(\hat y_t)/\sum_w \tau_t(w)$ at the final iteration. We also study a gap-aware deposition variant inspired by exponential deposition rules (Deterministic Model of Ant System; MMAS with Exponential Deposition). In this variant, deposit weight rises toward both gap boundaries, so tokens adjacent to fixed context are pinned first. It is a secondary ablation, not the core claim.
Research Program
The work proceeds in three stages. In the first stage we build the colony decoder on top of the forward and backward recurrent models used in the BiBS setting. We also build it on top of a bidirectional masked-language encoder, where $p_f$ is replaced by single-position masked predictions. This second version tests whether the method helps beyond the recurrent setting. Compute is counted in token-level model evaluations so that every decoder can be matched.
In the second stage we study calibration. On held-out labeled gaps we measure how well three scores separate correct fills from incorrect ones: $c(\hat y)$, the joint score $S$, and agreement among $N$ independent samples. This stage alone decides whether the filter idea deserves to go forward.
In the third stage we run self-training under simulated scarcity, following the low-label protocol style of APLT. We keep human fills for 10%, 25% or 50% of training items and treat the rest as unlabeled inputs: image plus context with the gap left empty. The colony fills the unlabeled items, and we keep fills above a concentration threshold chosen per gap length on a labeled development split. Following APLT's evidence that frozen labels resist drift, the forward and backward models are retrained on labeled plus kept pseudo-labeled data, with pseudo-labels frozen between rounds. We also test a transductive variant that runs the same loop on the test inputs' contexts, which contain no ground truth.
Baselines
The naive reference is a forward-only model with beam search that ignores the suffix. Bidirectional Beam Search reports 6.54 CIDEr for forward-only and 7.12 CIDEr for BiBS on COCO fill-in-the-blank with 25% of words blanked. These are the anchor numbers we must reproduce before any comparison counts.
The strongest existing decoder is BiBS itself. We run it with the same two models and sweep beam width and the number of alternations until its model-evaluation count equals the colony's. Its tuning budget equals the colony's hyperparameter search over $\alpha$, $\beta$, $\rho$ and colony size. Beating it means higher CIDEr at equal compute on 50% and 75% gaps, with the margin growing with gap length; parity at 25% is the expected outcome. The CIDEr comparisons rest on several seeds, with the evaluation-set examples resampled to obtain confidence intervals.
The strongest simple competitor is sample-and-rerank. It draws the same total number of fills from $p_f$ combined with $\eta$, with no pheromone, and returns the one with the highest $S$. This is the ablation that isolates the colony's key ingredient, shared memory across iterations. It uses the identical proposal and score, so any colony gain must come from pheromone.
On the Large Scale Movie Description Challenge (LSMDC) video fill-in-the-blank task, the reference is the forward/backward LSTM with external memory from Video Fill In the Blank. It reports 40.6% single-blank accuracy for one model, 43.4% for an ensemble, and 20.1% on multi-blank. The colony is applied on top of those models. We expect gains mainly on multi-blank, because single-word blanks leave little to search.
For self-training, the baselines are self-training on BiBS outputs filtered by the joint score, which is the standard confidence threshold, and filtered by $N$-sample agreement, each with matched pseudo-label counts. They are also compared with the purely supervised model on the labeled fraction. On Visual Madlibs we found no reported fill-in-the-blank generation number for BiBS on Lacuna. We will therefore report our own BiBS run, alongside the dataset paper's multiple-choice figures of 50–70% for the best models and 75–90% for humans (Visual Madlibs) where the multiple-choice track is used.
Why not just…?
Why not just widen the beam in bidirectional beam search? A wider beam keeps more frontiers but still alternates between fixed opposite beams. It has no mechanism to raise the probability of a token that repeatedly appears in good joint fills across different contexts within the gap. The compute-matched sweep above tests this directly. If BiBS at matched compute closes the gap at 75% blanks, the decoding claim fails and we will say so.
Why not just sample many fills and rerank by the joint score? This is the most serious threat. At short gaps it will probably match the colony, because the proposal already covers good fills. The colony should win only where good fills are rare under the proposal, since pheromone acts as adaptive importance sampling that a fixed proposal lacks. Plotting the colony's advantage against gap length (25/50/75%) settles this. A flat zero curve would mean pheromone adds nothing to decoding. In that case the proposal shrinks to the filtering question, and in stage two we compare concentration with $N$-sample agreement on equal footing.
Why not just filter pseudo-labels by model confidence, FixMatch-style? APLT reports that this style of self-training reaches 42.8% on MA-12 at 50% labels, against 57.3% for its stabilized variant, on micro-action recognition. That is a different domain, so it only suggests that confidence-only filtering is fragile. Our stage-two calibration study measures it for infilling. If joint-score filtering separates correct from wrong fills as well as concentration, we adopt the cheaper filter and the colony's role reduces to decoding.
Why not just use a large pretrained bidirectional encoder with iterative unmasking? Text pretraining already absorbs unlabeled text, and SENSESHIFT shows a 395M-parameter encoder outperforming a far larger causal model through iterative infilling. Our unlabeled resource is different: images and clips paired with context but no fill, which text pretraining cannot use. Our colony also runs on top of such an encoder. The encoder variant in stage one, with and without colony search and self-training, tells us whether the gains survive a strong pretrained model.
Decisive Checks
Three results decide the project. First, on COCO fill-in-the-blank the colony must exceed matched-compute BiBS and sample-and-rerank at 50% and 75% gaps, with a margin that increases with gap length, while reproducing the 7.12 CIDEr anchor at 25%. Second, in held-out calibration on COCO and LSMDC multi-blank, concentration must separate correct fills from incorrect ones better than joint score and $N$-sample agreement. Third, at 10% labels, concentration-filtered self-training must beat both likelihood-filtered self-training and supervised training on the labeled fraction, without the accuracy drift across rounds that signals confirmation bias. Passing the first check without the other two still yields a useful decoder. Passing the second without the first is still a useful filter. Failing all three tells us that shared memory adds nothing over independent samples in bidirectional infilling, which is itself worth reporting given how often population search is proposed for sequence tasks.
References
- Bidirectional Beam Search: Forward-Backward Inference in Neural Sequence Models for Fill-in-the-Blank Image Captioning
- Asynchronous Bidirectional Decoding for Neural Machine Translation
- SENSESHIFT: Continuous Sentiment-Controlled Text Generation via Encoder-based Mask Infilling
- DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimization
- Ant Colony Sampling with GFlowNets for Combinatorial Optimization
- Simple max-min ant systems and the optimization of linear pseudo-boolean functions
- Ant Colony System for Multi-Document Summarization
- Towards Micro-Action Recognition with Limited Annotations: An Asynchronous Pseudo Labeling and Training Approach
- Semi-supervised Models via Data Augmentation for Classifying Interactive Affective Responses
- A Deterministic Model for Analyzing the Dynamics of Ant System Algorithm and Performance Amelioration through a New Pheromone Deposition Approach
- Extension of Max-Min Ant System with Exponential Pheromone Deposition Rule
- Video Fill In the Blank Using LR/RL LSTMs with Spatial-Temporal Attentions
- Visual Madlibs: Fill in the Blank Description Generation and Question Answering