cs.LGJan 29, 2026

Differentiable Knapsack and Top-k Operators via Dynamic Programming

Authors: Germain Vivier-Ardisson, Michaël E. Sander, Axel Parmentier, Mathieu Blondel

Organizations: Google DeepMind, Paris, France · CERMICS, ENPC, Institut Polytechnique de Paris, CNRS, Marne-la-Vallée, France

Abstract

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's negative entropy is the unique separable regularization choice that yields permutation-equivariant operators, and characterize regularizers inducing sparse selections. On the experimental side, we demonstrate our framework on a benchmark on learning to predict Knapsack solutions, an extension of discrete VAEs, and a constrained dynamic assortment RL problem.

Figures & tables

Appendix figures & tables9 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. All roads lead to Markov kernel networks: A representation theorem for discretization-stable learning

    Nov 5, 2026S David Mis, Trevor Teolis, Ivan Dokmanić +2Operator LearningNeural Operators

  2. LaPrune: Controllable Differentiable Sparsity at Million Scale

    Aug 4, 2026Jakub Antczak, Joanna Wojciechowicz, Łukasz Struski +1Constrained Optimization