# Backpropagation through Combinatorial Algorithms: Identity with Projection Works

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

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- Placed in Diffusion reasoning and test-time scaling, one of 17 directions in LLM reasoning.
- Builds on 42 of its 72 references that are in the map.
- First posted on arXiv 30 May 2022.

## Placed in

- LLM reasoning / [Diffusion reasoning and test-time scaling](https://mlsanity.com/lr/diffusion-reasoning-and-test-time-scaling/)

## Builds on (most cited first, 30 of 42)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks](https://mlsanity.com/paper/1703.03400/) (2017)
- [Categorical Reparameterization with Gumbel-Softmax](https://mlsanity.com/paper/1611.01144/) (2016)
- [Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation](https://mlsanity.com/paper/1308.3432/) (2013)
- [The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables](https://mlsanity.com/paper/1611.00712/) (2016)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [OptNet: Differentiable Optimization as a Layer in Neural Networks](https://mlsanity.com/paper/1703.00443/) (2017)
- [Differentiable Convex Optimization Layers](https://mlsanity.com/paper/1910.12430/) (2019)
- [Meta-Learning with Differentiable Convex Optimization](https://mlsanity.com/paper/1904.03758/) (2019)
- [Rapid Learning or Feature Reuse? Towards Understanding the Effectiveness of MAML](https://mlsanity.com/paper/1909.09157/) (2019)
- [Smart "Predict, then Optimize"](https://mlsanity.com/paper/1710.08005/) (2017)
- [Reinforcement Learning for Solving the Vehicle Routing Problem](https://mlsanity.com/paper/1802.04240/) (2018)
- [Learning to Explain: An Information-Theoretic Perspective on Model Interpretation](https://mlsanity.com/paper/1802.07814/) (2018)
- [Understanding Straight-Through Estimator in Training Activation Quantized Neural Nets](https://mlsanity.com/paper/1903.05662/) (2019)
- [Melding the Data-Decisions Pipeline: Decision-Focused Learning for Combinatorial Optimization](https://mlsanity.com/paper/1809.05504/) (2018)
- [Differentiation of Blackbox Combinatorial Solvers](https://mlsanity.com/paper/1912.02175/) (2019)
- [Fast Differentiable Sorting and Ranking](https://mlsanity.com/paper/2002.08871/) (2020)
- [SATNet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver](https://mlsanity.com/paper/1905.12149/) (2019)
- [SPair-71k: A Large-scale Benchmark for Semantic Correspondence](https://mlsanity.com/paper/1908.10543/) (2019)
- [Discrete Variational Autoencoders](https://mlsanity.com/paper/1609.02200/) (2016)
- [Neural Execution of Graph Algorithms](https://mlsanity.com/paper/1910.10593/) (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)
- [Deep Graph Matching via Blackbox Differentiation of Combinatorial Solvers](https://mlsanity.com/paper/2003.11657/) (2020)
- [Learning to Branch](https://mlsanity.com/paper/1803.10150/) (2018)
- [Learning to Infer Graphics Programs from Hand-Drawn Images](https://mlsanity.com/paper/1707.09627/) (2017)
- [Differentiating Through a Cone Program](https://mlsanity.com/paper/1904.09043/) (2019)

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

- [Simple and Effective Masked Diffusion Language Models](https://mlsanity.com/paper/2406.07524/) (2024)
- [The Diffusion Duality](https://mlsanity.com/paper/2506.10892/) (2025)
- [Decision-Focused Learning: Foundations, State of the Art, Benchmark and Future Opportunities](https://mlsanity.com/paper/2307.13565/) (2023)
- [Diffusion Models With Learned Adaptive Noise](https://mlsanity.com/paper/2312.13236/) (2023)
- [A-NeSI: A Scalable Approximate Method for Probabilistic Neurosymbolic Inference](https://mlsanity.com/paper/2212.12393/) (2022)
- [One-step differentiation of iterative algorithms](https://mlsanity.com/paper/2305.13768/) (2023)
- [Differentiating Through Integer Linear Programs with Quadratic Regularization and Davis-Yin Splitting](https://mlsanity.com/paper/2301.13395/) (2023)
- [Benchmarking PtO and PnO Methods in the Predictive Combinatorial Optimization Regime](https://mlsanity.com/paper/2311.07633/) (2023)
- [CaVE: A Cone-Aligned Approach for Fast Predict-then-optimize with Binary Linear Programs](https://mlsanity.com/paper/2312.07718/) (2023)
- [Robust Losses for Decision-Focused Learning](https://mlsanity.com/paper/2310.04328/) (2023)
- [Differentiable Simulation of Hard Contacts with Soft Gradients for Learning and Control](https://mlsanity.com/paper/2506.14186/) (2025)
- [Scalable Coupling of Deep Learning with Logical Reasoning](https://mlsanity.com/paper/2305.07617/) (2023)
- [GenCO: Generating Diverse Designs with Combinatorial Constraints](https://mlsanity.com/paper/2310.02442/) (2023)
- [From Inverse Optimization to Feasibility to ERM](https://mlsanity.com/paper/2402.17890/) (2024)
- [Constraint-Aware Flow Matching: Decision Aligned End-to-End Training for Constrained Sampling](https://mlsanity.com/paper/2605.12754/) (2026)
- [Denoising Diffusion Variational Inference: Diffusion Models as Expressive Variational Posteriors](https://mlsanity.com/paper/2401.02739/) (2024)
- [Minimizing Surrogate Losses for Decision-Focused Learning using Differentiable Optimization](https://mlsanity.com/paper/2508.11365/) (2025)
- [SoftJAX & SoftTorch: Empowering Automatic Differentiation Libraries with Informative Gradients](https://mlsanity.com/paper/2603.08824/) (2026)
- [Differentiable Knapsack and Top-k Operators via Dynamic Programming](https://mlsanity.com/paper/2601.21775/) (2026)
- [Decision-Focused On-Policy Learning for Contextual Linear Optimization with Partial Feedback](https://mlsanity.com/paper/2606.01081/) (2026)
- [A predict-and-optimize approach to profit-driven churn prevention](https://mlsanity.com/paper/2310.07047/) (2023)
- [CF-OPT: Counterfactual Explanations for Structured Prediction](https://mlsanity.com/paper/2405.18293/) (2024)
- [Exploring End-to-end Differentiable Neural Charged Particle Tracking -- A Loss Landscape Perspective](https://mlsanity.com/paper/2407.13420/) (2024)
- [The Differentiable Feasibility Pump](https://mlsanity.com/paper/2411.03535/) (2024)
- [Preference-Based Gradient Estimation for ML-Guided Approximate Combinatorial Optimization](https://mlsanity.com/paper/2502.19377/) (2025)
- [Scaling Neuro-symbolic Problem Solving: Solver-Free Learning of Constraints and Objectives](https://mlsanity.com/paper/2508.20978/) (2025)
- [Decision-focused Sensing and Forecasting for Adaptive and Rapid Flood Response: An Implicit Learning Approach](https://mlsanity.com/paper/2510.16015/) (2025)
- [Managing Solution Stability in Decision-Focused Learning with Cost Regularization](https://mlsanity.com/paper/2601.21883/) (2026)
- [DisjunctiveNet: Neural Symbolic Learning via Differentiable Convexified Optimization Layers](https://mlsanity.com/paper/2605.30456/) (2026)

## Abstract (arXiv)

Embedding discrete solvers as differentiable layers has given modern deep learning architectures combinatorial expressivity and discrete reasoning capabilities. The derivative of these solvers is zero or undefined, therefore a meaningful replacement is crucial for effective gradient-based learning. Prior works rely on smoothing the solver with input perturbations, relaxing the solver to continuous problems, or interpolating the loss landscape with techniques that typically require additional solver calls, introduce extra hyper-parameters, or compromise performance. We propose a principled approach to exploit the geometry of the discrete solution space to treat the solver as a negative identity on the backward pass and further provide a theoretical justification. Our experiments demonstrate that such a straightforward hyper-parameter-free approach is able to compete with previous more complex methods on numerous experiments such as backpropagation through discrete samplers, deep graph matching, and image retrieval. Furthermore, we substitute the previously proposed problem-specific and label-dependent margin with a generic regularization procedure that prevents cost collapse and increases robustness.