Fast and General Automatic Differentiation for Finite-State Methods
arXiv:2602.12300v1 Announce Type: new Abstract: We propose a new method, that we coined the “morphism-trick”, to integrate custom implementations of vector-Jacobian products in automatic differentiation softwares, applicable to a wide range of semiring-based computations. Our approach leads to efficient and semiring-agnostic implementations of the backward pass of dynamic programming algorithms. For the particular case of finite-state methods, we introduce an algorithm that computes and differentiates the $oplus$-sum of all paths’ weight of a finite-state automaton. Results show that, […]