Fast and General Automatic Differentiation for Finite-State Methods
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915795841318912 |
|---|---|
| author | Yang, Lucas Ondel Raissi, Tina Kocour, Martin Riera, Pablo Corro, Caio |
| author_facet | Yang, Lucas Ondel Raissi, Tina Kocour, Martin Riera, Pablo Corro, Caio |
| contents | 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, with minimal effort from the user, our novel library allows computing the gradient of a function w.r.t. to the weights of a finite state automaton orders of magnitude faster than state-of-the-art automatic differentiation systems. Implementations are made available via an open-source library distributed under a permissive license. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_12300 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Fast and General Automatic Differentiation for Finite-State Methods Yang, Lucas Ondel Raissi, Tina Kocour, Martin Riera, Pablo Corro, Caio Formal Languages and Automata Theory 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, with minimal effort from the user, our novel library allows computing the gradient of a function w.r.t. to the weights of a finite state automaton orders of magnitude faster than state-of-the-art automatic differentiation systems. Implementations are made available via an open-source library distributed under a permissive license. |
| title | Fast and General Automatic Differentiation for Finite-State Methods |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2602.12300 |