# Differentiable Knapsack and Top-k Operators via Dynamic Programming

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 40 references that are in the map.
- First posted on arXiv 29 Jan 2026.

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

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation](https://mlsanity.com/paper/1308.3432/) (2013)
- [From Softmax to Sparsemax: A Sparse Model of Attention and Multi-Label Classification](https://mlsanity.com/paper/1602.02068/) (2016)
- [Differentiation of Blackbox Combinatorial Solvers](https://mlsanity.com/paper/1912.02175/) (2019)
- [Stochastic Beams and Where to Find Them: The Gumbel-Top-k Trick for Sampling Sequences Without Replacement](https://mlsanity.com/paper/1903.06059/) (2019)
- [Discrete Variational Autoencoders](https://mlsanity.com/paper/1609.02200/) (2016)
- [Learning with Fenchel-Young Losses](https://mlsanity.com/paper/1901.02324/) (2019)
- [Differentiable Ranks and Sorting using Optimal Transport](https://mlsanity.com/paper/1905.11885/) (2019)
- [Implicit MLE: Backpropagating Through Discrete Exponential Family Distributions](https://mlsanity.com/paper/2106.01798/) (2021)
- [MIPaaL: Mixed Integer Program as a Layer](https://mlsanity.com/paper/1907.05912/) (2019)
- [Interior Point Solving for LP-based prediction+optimisation](https://mlsanity.com/paper/2010.13943/) (2020)
- [Learning with Differentiable Perturbed Optimizers](https://mlsanity.com/paper/2002.08676/) (2020)
- [Differentiable Dynamic Programming for Structured Prediction and Attention](https://mlsanity.com/paper/1802.03676/) (2018)
- [Contrastive Losses and Solution Caching for Predict-and-Optimize](https://mlsanity.com/paper/2011.05354/) (2020)
- [SIMPLE: A Gradient Estimator for k-Subset Sampling](https://mlsanity.com/paper/2210.01941/) (2022)
- [PyEPO: A PyTorch-based End-to-End Predict-then-Optimize Library for Linear and Integer Programming](https://mlsanity.com/paper/2206.14234/) (2022)
- [Backpropagation through Combinatorial Algorithms: Identity with Projection Works](https://mlsanity.com/paper/2205.15213/) (2022)
- [Dynamic Assortment Optimization with Changing Contextual Information](https://mlsanity.com/paper/1810.13069/) (2018)
- [Learning Classifiers with Fenchel-Young Losses: Generalized Entropies, Margins, and Algorithms](https://mlsanity.com/paper/1805.09717/) (2018)
- [Fast, Differentiable and Sparse Top-k: a Convex Analysis Perspective](https://mlsanity.com/paper/2302.01425/) (2023)
- [The Limited Multi-Label Projection Layer](https://mlsanity.com/paper/1906.08707/) (2019)
- [Differentiable Top-k Classification Learning](https://mlsanity.com/paper/2206.07290/) (2022)
- [LP-SparseMAP: Differentiable Relaxed Optimization for Sparse Structured Prediction](https://mlsanity.com/paper/2001.04437/) (2020)
- [Differentiable Top-k Operator with Optimal Transport](https://mlsanity.com/paper/2002.06504/) (2020)
- [Multi-Vector Retrieval as Sparse Alignment](https://mlsanity.com/paper/2211.01267/) (2022)
- [Structured Reinforcement Learning for Combinatorial Decision-Making](https://mlsanity.com/paper/2505.19053/) (2025)
- [Fenchel-Young Variational Learning](https://mlsanity.com/paper/2502.10295/) (2025)

## Built on by (most cited first, 1 of 1)

- [Regularized Large Neighborhood Search](https://mlsanity.com/paper/2606.02294/) (2026)

## Abstract (arXiv)

Knapsack and Top-k operators are useful for selecting discrete subsets of variables. However, their integration into neural networks is challenging as they are piecewise constant, yielding gradients that are zero almost everywhere. In this paper, we propose a unified framework casting these operators as dynamic programs, and derive differentiable relaxations by smoothing the underlying recursions. On the algorithmic side, we develop efficient parallel algorithms supporting both deterministic and stochastic forward passes, and vector-Jacobian products for the backward pass. On the theoretical side, we prove that Shannon entropy is the unique regularization choice yielding permutation-equivariant operators, and characterize regularizers inducing sparse selections. Finally, on the experimental side, we demonstrate our framework on a decision-focused learning benchmark, a constrained dynamic assortment RL problem, and an extension of discrete VAEs.