# Differentiable Dynamic Programming for Structured Prediction and Attention

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

## Key facts

- Cited by 58 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Feb 2018.

## Built on by (most cited first, 30 of 58)

- [Attention, please! A survey of Neural Attention Models in Deep Learning](https://mlsanity.com/paper/2103.16775/) (2021)
- [Twice regularized MDPs and the equivalence between robustness and regularization](https://mlsanity.com/paper/2110.06267/) (2021)
- [Representation Learning via Global Temporal Alignment and Cycle-Consistency](https://mlsanity.com/paper/2105.05217/) (2021)
- [Maximum Likelihood Reinforcement Learning](https://mlsanity.com/paper/2602.02710/) (2026)
- [SIMPLE: A Gradient Estimator for k-Subset Sampling](https://mlsanity.com/paper/2210.01941/) (2022)
- [Fine-grained Temporal Contrastive Learning for Weakly-supervised Temporal Action Localization](https://mlsanity.com/paper/2203.16800/) (2022)
- [Maximum entropy GFlowNets with soft Q-learning](https://mlsanity.com/paper/2312.14331/) (2023)
- [Learning Discriminative Prototypes with Dynamic Time Warping](https://mlsanity.com/paper/2103.09458/) (2021)
- [Learning to Predict Graphs with Fused Gromov-Wasserstein Barycenters](https://mlsanity.com/paper/2202.03813/) (2022)
- [Learning with Algorithmic Supervision via Continuous Relaxations](https://mlsanity.com/paper/2110.05651/) (2021)
- [Uncertainty-DTW for Time Series and Sequences](https://mlsanity.com/paper/2211.00005/) (2022)
- [Leaving the Nest: Going Beyond Local Loss Functions for Predict-Then-Optimize](https://mlsanity.com/paper/2305.16830/) (2023)
- [Sparse Continuous Distributions and Fenchel-Young Losses](https://mlsanity.com/paper/2108.01988/) (2021)
- [Differentiable Clustering with Perturbed Spanning Forests](https://mlsanity.com/paper/2305.16358/) (2023)
- [Decision-Focused Learning without Differentiable Optimization: Learning Locally Optimized Decision Losses](https://mlsanity.com/paper/2203.16067/) (2022)
- [Deep Time Series Forecasting with Shape and Temporal Criteria](https://mlsanity.com/paper/2104.04610/) (2021)
- [Combinatorial Optimization for Panoptic Segmentation: A Fully Differentiable Approach](https://mlsanity.com/paper/2106.03188/) (2021)
- [TILDE-Q: A Transformation Invariant Loss Function for Time-Series Forecasting](https://mlsanity.com/paper/2210.15050/) (2022)
- [Revisiting Implicit Differentiation for Learning Problems in Optimal Control](https://mlsanity.com/paper/2310.14468/) (2023)
- [Autoregressive Language Models are Secretly Energy-Based Models: Insights into the Lookahead Capabilities of Next-Token Prediction](https://mlsanity.com/paper/2512.15605/) (2025)
- [Latent Topology Induction for Understanding Contextualized Representations](https://mlsanity.com/paper/2206.01512/) (2022)
- [A Unified Perspective on Value Backup and Exploration in Monte-Carlo Tree Search](https://mlsanity.com/paper/2202.07071/) (2022)
- [DOGE-Train: Discrete Optimization on GPU with End-to-end Training](https://mlsanity.com/paper/2205.11638/) (2022)
- [DataSP: A Differential All-to-All Shortest Path Algorithm for Learning Costs and Predicting Paths with Context](https://mlsanity.com/paper/2405.04923/) (2024)
- [To be Closer: Learning to Link up Aspects with Opinions](https://mlsanity.com/paper/2109.08382/) (2021)
- [DWA-KD: Dual-Space Weighting and Time-Warped Alignment for Cross-Tokenizer Knowledge Distillation](https://mlsanity.com/paper/2602.21669/) (2026)
- [Differentiable Spline Approximations](https://mlsanity.com/paper/2110.01532/) (2021)
- [Fixed-Point Automatic Differentiation of Forward--Backward Splitting Algorithms for Partly Smooth Functions](https://mlsanity.com/paper/2208.03107/) (2022)
- [A fast and sound tagging method for discontinuous named-entity recognition](https://mlsanity.com/paper/2409.16243/) (2024)
- [ViterbiPlanNet: Injecting Procedural Knowledge via Differentiable Viterbi for Planning in Instructional Videos](https://mlsanity.com/paper/2603.04265/) (2026)

## Abstract (arXiv)

Dynamic programming (DP) solves a variety of structured combinatorial problems by iteratively breaking them down into smaller subproblems. In spite of their versatility, DP algorithms are usually non-differentiable, which hampers their use as a layer in neural networks trained by backpropagation. To address this issue, we propose to smooth the max operator in the dynamic programming recursion, using a strongly convex regularizer. This allows to relax both the optimal value and solution of the original combinatorial problem, and turns a broad class of DP algorithms into differentiable operators. Theoretically, we provide a new probabilistic perspective on backpropagating through these DP operators, and relate them to inference in graphical models. We derive two particular instantiations of our framework, a smoothed Viterbi algorithm for sequence prediction and a smoothed DTW algorithm for time-series alignment. We showcase these instantiations on two structured prediction tasks and on structured and sparse attention for neural machine translation.