PEAL: Probabilistic Edit Alignment Loss for Discrete Sequence Prediction

Discrete sequence prediction requires models to identify the correct elements and capture their sequential dependencies. However, position-wise cross-entropy (CE) can encourage local corrections that disrupt a correct subsequence when it is shifted relative to the target—a limitation we call CE's myopia. We introduce Probabilistic Edit Alignment Loss (PEAL), which formulates alignment between predicted and target sequences as cost optimization over monotone edit paths. Substitution costs decrease with the probability assigned to the aligned target class, while insertion and deletion incur fixed penalties. PEAL aggregates the costs of all valid paths using a differentiable soft minimum. These edit paths allow correctly ordered subsequences to remain aligned despite positional shifts. Our gradient analysis shows that the resulting gradient is a Gibbs-weighted combination of path-cost gradients, with lower-cost paths receiving larger weights. We further establish conditional empirical $H$-consistency: under specified conditions, any model minimizing empirical PEAL risk within a fixed model class $H$ is also optimal for structured prediction within that class, as measured by empirical edit-distance risk. Experiments on automatic speech recognition, temporal action segmentation, and long-term action anticipation demonstrate improvements across multiple backbone architectures. Further analyses associate these gains with better relative-order preservation and longer correctly aligned subsequences.