# Structure-Aware Path Inference for Neural Finite State Transducers

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 28 references that are in the map.
- First posted on arXiv 21 Dec 2023.

## Builds on (most cited first, 11 of 11)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Sequence to Sequence Learning with Neural Networks](https://mlsanity.com/paper/1409.3215/) (2014)
- [Fast Inference from Transformers via Speculative Decoding](https://mlsanity.com/paper/2211.17192/) (2022)
- [On the Properties of Neural Machine Translation: Encoder-Decoder Approaches](https://mlsanity.com/paper/1409.1259/) (2014)
- [Importance Weighted Autoencoders](https://mlsanity.com/paper/1509.00519/) (2015)
- [Processing South Asian Languages Written in the Latin Script: the Dakshina Dataset](https://mlsanity.com/paper/2007.01176/) (2020)
- [A Measure-Theoretic Characterization of Tight Language Models](https://mlsanity.com/paper/2212.10502/) (2022)
- [Neural Lattice-to-Sequence Models for Uncertain Inputs](https://mlsanity.com/paper/1704.00559/) (2017)
- [Distributional Reinforcement Learning for Energy-Based Sequential Models](https://mlsanity.com/paper/1912.08517/) (2019)
- [Neural Particle Smoothing for Sampling from Conditional Sequence Models](https://mlsanity.com/paper/1804.10747/) (2018)

## Abstract (arXiv)

Neural finite-state transducers (NFSTs) form an expressive family of neurosymbolic sequence transduction models. An NFST models each string pair as having been generated by a latent path in a finite-state transducer. As they are deep generative models, both training and inference of NFSTs require inference networks that approximate posterior distributions over such latent variables. In this paper, we focus on the resulting challenge of imputing the latent alignment path that explains a given pair of input and output strings (e.g., during training). We train three autoregressive approximate models for amortized inference of the path, which can then be used as proposal distributions for importance sampling. All three models perform lookahead. Our most sophisticated (and novel) model leverages the FST structure to consider the graph of future paths; unfortunately, we find that it loses out to the simpler approaches -- except on an artificial task that we concocted to confuse the simpler approaches.