Differentiable Integer Programming is not Differentiable & it’s not a mere technical problem.
Thanawat Sornwanee · 2026
Read Differentiable Integer Programming is not Differentiable & it’s not a mere technical problem. by Thanawat Sornwanee (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-17800.txt.
Introduction
Thanawat Sornwanee argues that a recent claim in optimization rests on a math error. His 2026 preprint examines a 2025 paper on differentiable integer linear programming. Integer programs choose whole-number values, and making them smooth enough for gradient methods is a prized trick. The earlier paper claimed such a method in its fifth theorem. Sornwanee shows that the proof of that claim is wrong.
The stakes go past one paper. Later work has already built on the same flawed step, so the error spreads. A clear notice of the fault helps others avoid building on sand. Work of this kind is part of how a field keeps its results sound. Readers get a warning plus a close look at where the proof fails.
Catalog record
| CREATOR | Thanawat Sornwanee |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 34 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-17800
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Differentiable Integer Programming is not Differentiable & it’s not a mere technical problem. Thanawat Sornwanee Abstract We show how the differentiability method employed in the paper “Differentiable Integer Linear Programming”, Geng, et al., 2025 [ 5 ] as shown in its theorem 5 is incorrect. Moreover, there already exists some downstream work that inherits the same error. The underlying reason comes from that, though being continuous in expectation, the surrogate loss is discontinuous in almost every realization of the randomness, for the stochastic gradient descent. The paper “Differentiable Integer Linear Programming”, Geng, et. al., 2025 [ 5 ] suggests a reformulation of an integer linear program from \displaystyle\min_{x\in\{0,1\}^{d}:Ax\preccurlyeq b}c^{\top}x, (1) where A\in\mathbb{R}^{m\times d} , b\in\mathbb{R}^{m} , and c\in\mathbb{R}^{d} for some m,d\in\mathbb{N} , to \displaystyle\min_{\hat{x}\in[0,1]^{d}:\sum_{i=1}^{m}\mathbb{E}_{x\sim P_{\hat{x}}}\left[\max\left(\left\{a_{i}^{\top}x-b_{i},0\right\}\right)\right]=0}c^{\top}\hat{x}, (2) where the distribution P_{\hat{x}}:=\bigotimes_{i=1}^{d}\text{Bernoulli}\left(\hat{x}_{i}\right) for all \hat{x}\in[0,1]^{d} . This probabilistic reparameterization method is commonly used to relax the integer nature of combinatorial problem [ 8 ] , while still preserving the correctness of the result. The paper itself [ 5 ] outlines the result into 2 theorems (theorem 1 and theorem 2 of the paper). We summarize the main result of the 2 theorems as the following theorem. Theorem 1 (Summarization of Theorem 1 and Theorem 2 of [ 5 ] ) . \displaystyle\mathop{\arg\min}_{x\in\{0,1\}^{d}:Ax\preccurlyeq b}c^{\top}x=\left[\mathop{\arg\min}_{\hat{x}\in[0,1]^{d}:\sum_{i=1}^{m}\mathbb{E}_{x\sim P_{\hat{x}}}\left[\max\left(\left\{a_{i}^{\top}x-b_{i},0\right\}\right)\right]=0}c^{\top}\hat{x}\right]\cap\{0,1\}^{d} This suggests that we can solve the problem 1 by solving the problem 2 . Note that the searching set of the problem 2 is not necessarily convex nor connected, so the paper [ 5 ] suggests the reformulation from constrained optimization (as in 2 ) into an unconstrained one: \displaystyle\min_{\hat{x}\in[0,1]^{d}}c^{\top}\hat{x}+\mu\sum_{i=1}^{m}\mathbb{E}_{x\sim P_{\hat{x}}}\left[\max\left(\left\{a_{i}^{\top}x-b_{i},0\right\}\right)\right], (3) and have the theorem 3, which is incorrect. However, the incorrectness of this theorem arises from that the problem 2 can be infeasible, and can be considered as a mere technical pathology. 1 1 1 A detailed explanation on how the theorem 3 of [ 5 ] is incorrect and how the proof in the paper [ 5 ] goes wrong is in the appendix A , and can likely be attributed to some mathematical typos. We can easily correct the theorem as well as adding more detail, making it becomes the following theorem: Theorem 2 (Corrected Theorem 3 of [ 5 ] ) . If there exists some x\in\{0,1\}^{d} such that Ax\preccurlyeq b , then, for any \mu>\frac{2\sqrt{d}\left\|c\right\|_{2}}{\min\left(\{1\}\cup\left(\bigcup_{i=1}^{m}\left\{a_{i}^{\top}x-b:x\in\{0,1\}^{d}\right\}\cap(0,\infty)\right)\right)} , we have that \displaystyle\mathop{\arg\min}_{\hat{x}\in[0,1]^{d}}c^{\top}\hat{x}+\mu\sum_{i=1}^{m}\mathbb{E}_{x\sim P_{\hat{x}}}\left[\max\left(\left\{a_{i}^{\top}x-b_{i},0\right\}\right)\right]=\mathop{\arg\min}_{\hat{x}\in[0,1]^{d}:\sum_{i=1}^{m}\mathbb{E}_{x\sim P_{\hat{x}}}\left[\max\left(\left\{a_{i}^{\top}x-b_{i},0\right\}\right)\right]=0}c^{\top}\hat{x}. Proof. The proof follows almost from the proof of the theorem 3 of [ 5 ] in the appendix of [ 5 ] but with some correction as shown in our appendix A.1 . ∎ For a fixed \mu , we have that the objective function c^{\top}\hat{x}+\mu\sum_{i=1}^{m}\mathbb{E}_{x\sim P_{\hat{x}}}\left[\max\left(\left\{a_{i}^{\top}x-b_{i},0\right\}\right)\right] is infinitely differentiable with respect to \hat{x} (in multidimensional sense). However, we can see that the dependence on \hat{x} of the second term goes in as a probability weight over \{0,1\}^{d} . This makes it computational hard to calculate the derivative with respect to \hat{x} if there is no further assumption 2 2 2 For example, the paper [ 8 ] considers problem such as max clique and graph-partitioning, allowing the combinatorial cost to only require local structures of the graph solution. on the sparsity of the matrix A . The paper then uses the reparameterization so that, for each i\in\{1,2,\dots,m\} , \displaystyle\mathbb{E}_{x\sim P_{\hat{x}}}\left[\max\left(\left\{a_{i}^{\top}x-b_{i},0\right\}\right)\right] \displaystyle=\mathbb{E}_{\epsilon\sim\text{Unif}\left((0,1)^{d}\right)}\left[\max\left(\left\{a_{i}^{\top}\left[\mathbf{1}_{\sigma^{-1}\left(\hat{x}_{j}\right)+\sigma^{-1}(\epsilon_{j})\geq 0}\right]_{j=1}^{d}-b_{i},0\right\}\right)\right] \displaystyle=\mathbb{E}_{\epsilon\sim\text{Unif}\left((0,1)^{d}\right)}\left[\mathbf{1}_{a_{i}^{\top}\left[\mathbf{1}_{\sigma^{-1}\left(\hat{x}_{j}\right)+\sigma^{-1}(\epsilon_{j})\geq 0}\right]_{j=1}^{d}-b_{i}>0}\left(a_{i}^{\top}\left[\mathbf{1}_{\sigma^{-1}\left(\hat{x}_{j}\right)+\sigma^{-1}(\epsilon_{j})\geq 0}\right]_{j=1}^{d}-b_{i}\right)\right], where \sigma is a cumulative distribution function (CDF) of a standard logistic distribution, making \sigma^{-1}(p)=\log\frac{p}{1-p} for all p\in(0,1) . Note that this is correct since the random variable \displaystyle\left[\mathbf{1}_{\sigma^{-1}\left(\hat{x}_{j}\right)+\sigma^{-1}(\epsilon_{j})\geq 0}\right]_{j=1}^{d}\sim P_{\hat{x}} when \epsilon_{j}\overset{\text{iid}}{\sim}\text{Unif}((0,1)) , which is equivalent to lemma 1 and theorem 4 of the original paper [ 5 ] . This changes make the probability measure independent from \hat{x} and shifts the dependence on \hat{x} to be only through \sigma^{-1} and \mathbf{1}_{\cdot\geq 0} functions. Note that, for each realization \epsilon\in(0,1)^{d} , we have that the function 3 3 3 Note that our \tilde{\phi}_{i}\left(\hat{x},\epsilon\right) is the same as \phi_{i}\left(\psi\left(\hat{x},\epsilon\right)\right) in the original paper [ 5 ] . \displaystyle\tilde{\phi}_{i}\left(\hat{x},\epsilon\right):=\mathbf{1}_{a_{i}^{\top}\left[\mathbf{1}_{\sigma^{-1}\left(\hat{x}_{j}\right)+\sigma^{-1}(\epsilon_{j})\geq 0}\right]_{j=1}^{d}-b_{i}>0}\left(a_{i}^{\top}\left[\mathbf{1}_{\sigma^{-1}\left(\hat{x}_{j}\right)+\sigma^{-1}(\epsilon_{j})\geq 0}\right]_{j=1}^{d}-b_{i}\right) is differentiable almost everywhere \hat{x}\in\text{int}\left([0,1]^{d}\right)=(0,1)^{d} . However, such derivative, if exists, will be 0 , since the step function \mathbf{1}_{\cdot\geq 0} has zero-derivative almost everywhere. Since the function is not a constant function and is, in fact, differentiable, we then have that \displaystyle\nabla_{\hat{x}}\mathbb{E}_{\epsilon\sim\text{Unif}\left((0,1)^{d}\right)}\left[\tilde{\phi}_{i}\left(\hat{x},\epsilon\right)\right]\neq\mathbb{E}_{\epsilon\sim\text{Unif}\left((0,1)^{d}\right)}\left[\nabla_{\hat{x}}\tilde{\phi}_{i}\left(\hat{x},\epsilon\right)\right]. The paper [ 5 ] aims to find a near-optimal and feasible solution to the integer linear program 1 by using a graph neural network (GNN) method for finding a near-optimal solution to the unconstrained problem 3 with some appropriate value of \mu . The paper plans to train the GNN using a standard machine learning technique requiring a gradient information (such as stochastic gradient) and backpropagation to update the neural weight parameters in GNN. Thus, if we use the stochastic gradient \nabla_{\hat{x}}\phi_{i}\left(\hat{x},\epsilon\right) in the machine learning training system, then it will be 0 most of the time making the learning impossible. The paper [ 5 ] then seeks to find a surrogate loss \displaystyle\varphi_{i}\left(\hat{x},\epsilon\right)\approx\tilde{\phi}_{i}\left(\hat{x},\epsilon\right) such that \displaystyle\nabla_{\hat{x}}\mathbb{E}_{\epsilon\sim\text{Unif}\left((0,1)^{d}\right)}\left[\varphi_{i}\left(\hat{x},\epsilon\right)\right]=\mathbb{E}_{\epsilon\sim\text{Unif}\left((0,1)^{d}\right)}\left[\nabla_{\hat{x}}\varphi_{i}\left(\hat{x},\epsilon\right)\right]. 1 Incorrect Attempt in [ 5 ] The paper suggests the use of \displaystyle\varphi_{i}\left(\hat{x},\epsilon\right):=\mathbf{1}_{a_{i}^{\top}\left[\mathbf{1}_{\sigma^{-1}\left(\hat{x}_{j}\right)+\sigma^{-1}(\epsilon_{j})\geq 0}\right]_{j=1}^{d}-b_{i}>0}\left(a_{i}^{\top}\left[\sigma\left(\sigma^{-1}\left(\hat{x}_{j}\right)+\sigma^{-1}(\epsilon_{j})\right)\right]_{j=1}^{d}-b_{i}\right) in place of \displaystyle\tilde{\phi}_{i}\left(\hat{x},\epsilon\right):=\mathbf{1}_{a_{i}^{\top}\left[\mathbf{1}_{\sigma^{-1}\left(\hat{x}_{j}\right)+\sigma^{-1}(\epsilon_{j})\geq 0}\right]_{j=1}^{d}-b_{i}>0}\left(a_{i}^{\top}\left[\mathbf{1}_{\sigma^{-1}\left(\hat{x}_{j}\right)+\sigma^{-1}(\epsilon_{j})\geq 0}\right]_{j=1}^{d}-b_{i}\right). Recall that \sigma is the CDF of standard logistic distribution, so \sigma(x)=\frac{1}{1+e^{-x}} for all x\in\mathbb{R} . It is also easy to see that, similar to \tilde{\phi}_{i} , the function \varphi_{i} is differentiable for all \epsilon\in(0,1)^{d} for almost every \hat{x}\in(0,1) . The choice of using the CDF \sigma(\cdot) in place of the step function \mathbf{1}_{\cdot\geq 0} is common differentiability technique that one can see in classification literature. This often involves convolution either analytically or empirically [ 18 ] 4 4 4 If it is used in empirical sense, then the gradient has to be done in a monte-carlo manner and ain a finite-difference manner [ 2 , 18 ] , meaning that we cannot use expected gradient approximates gradient of expectation, since the former is almost surely 0 . in order for the global structure of the piece-wise function to be passed into a gradient quantity. However, that normally happens without an additional indicator function. 5 5 5 Which is a feature of a straight-through estimator. The paper claims that differentiability almost everywhere is a crucial property allowing \displaystyle\nabla_{\hat{x}}\mathbb{E}_{\epsilon\sim\text{Unif}\left((0,1)^{d}\right)}\left[\varphi_{i}\left(\hat{x},\epsilon\right)\right]=\mathbb{E}_{\epsilon\sim\text{Unif}\left((0,1)^{d}\right)}\left[\nabla_{\hat{x}}\varphi_{i}\left(\hat{x},\epsilon\right)\right]. However, as we have seen earlier, the function \tilde{\phi}_{i} itself is also differentiable almost everywhere, but does not satisfy the interchangeability between expectation and differentiation. The paper provides the following incorrect theorem: Incorrect Theorem 1 (Restated Theorem 5 of [ 5 ] ) . For almost every \hat{x}\in(0,1)^{d} , \displaystyle\nabla_{\hat{x}}\mathbb{E}_{\epsilon\sim\text{Unif}\left((0,1)^{d}\right)}\left[\varphi_{i}\left(\hat{x},\epsilon\right)\right]=\mathbb{E}_{\epsilon\sim\text{Unif}\left((0,1)^{d}\right)}\left[\mathbf{1}_{a_{i}^{\top}\left[\mathbf{1}_{\sigma^{-1}\left(\hat{x}_{j}\right)+\sigma^{-1}(\epsilon_{j})\geq 0}\right]_{j=1}^{d}-b_{i}>0}\left(a\odot\left[\frac{\partial}{\partial x_{j}}\sigma\left(\sigma^{-1}\left(\hat{x}_{j}\right)+\sigma^{-1}(\epsilon_{j})\right)\right]_{j=1}^{d}\right)\right], where \odot denotes elementwise multiplication. This theorem primarily suggests that we can interchange the expectation and differentiation. We can see that, if we can do so, then, for each realization of \epsilon , we can compute the differentiation term of each dimension in a parallel manner before multiply it by the indicator \mathbf{1}_{a_{i}^{\top}\left[\mathbf{1}_{\sigma^{-1}\left(\hat{x}_{j}\right)+\sigma^{-1}(\epsilon_{j})\geq 0}\right]_{j=1}^{d}-b_{i}>0} to see whether the i^{\text{th}} constraint is violated. Unlike the incorrectness in the theorem 3 of [ 5 ] , the incorrectness of the theorem 5 of [ 5 ] is not merely a technical problem. This happens primarily because the function \varphi itself is not continuous. 6 6 6 Although continuity and differentiability almost everywhere may not be a sufficient condition, other additional conditions can be thought of as a technical conditions (such as absolute