Solving Composable Constraints for Inverse Design Tasks

Thank you for your detailed review. We would like to address some of your comments, as well as clarify some mis-understandings.

• Q1: First, modelling constraints as SDFs provides several useful properties for constructing complex systems of constraints. For example, we could construct an objective such as $(M_a(x) \geq k_a) \text{ XOR } (M_b(x) \geq k_b) \text{ XOR } (M_c(x) \geq k_c)$. This system of constraints is trivially implemented and solved using SDFs, but is not easily expressed in conventional gradient-based schemes. Additionally, a higher threshold is not universally useful. For example, when designing anti-microbial peptides (AMPs), we would want the peptide to have a helical fraction in a well defined range with a lower and upper bound. Consequently, assuming that we want to unconditionally maximize a model output greatly limits applicability outside a narrow range of classification tasks.
• Q8/Q9: You make the claim that you do not understand why SDFs are intractible and then you provide an example for easily computing an SDF. This comes from a misunderstanding of the SDF formulation in equation 4. The example you provide computes the error in Output Space, while the SDF is the distance in Input Space. Thus, it is not as trivial as measuring the difference between the target and actual values, but rather the distance in feature space. This is a much harder problem as it requires an inversion of the predictive model, making the problem intractable in general.
• Q2: While modern generative models (such as diffusion models) have achieved impressive success in a variety of tasks, VAEs provide several useful characteristics in this setting. In particular, we demonstrate that the introduction of a VAE improves computational performance, as well as generation quality. This is not the case for models such as Flow-matching, as they do not perform dimensionality reduction and do not induce useful latent spaces which can be used to train a classifier.
• Q3: The core focus of this paper is to provide a mechanism for inverting predictive models on arbitrary tasks with arbitrary constraints. As such, the experiments provided are to demonstrate that the theoretical formulation of constraints as SDFs can be used to perform semantic operations. In fairness, it should be possible to apply composable constraints to non-classification tasks such as inpainting or super-resolution. However, this would require additional work for formulating a partially-observed variation of the SDF equations, and thus is out of scope for this work which introduces SDF constraints for the first time.
• Q4: While other methods exist for solving inverse design tasks, we found it difficult to identify methods with similar enough properties to allow for a fair comparison. For example, [1] does not allow for zero-shot addition of arbitrary classifiers, while [4] and [5] does not easily permit complex systems of constraints which include boolean statements or conditional constraints. Consequently, we use GGD as a baseline, as it allows for the most fair comparison, since it is a method which explicitly inverts a classifier for the generation, and can be used in a post-hoc manner in a wide variety of settings.
• Q5: The claim that we need to differentiate through the SDF algorithm is false. The intuition for obtaining the gradient is that algorithm 1 finds the nearest boundary point, thus producing the gradient is trivial since we return $x_0 - p_1$ in addition to $||x_0 - p_1||_2$. Please see algorithm 1 for more detail. Additionally, we have added a section in appendix M giving greater detail on the computational complexity of the SDF algorithms.
• Q6: The claim is that "Results in Figure 3 were extremely poor, It looks as if the classifier has been adversarially attacked..." This is an astute observation, as we included the figure to demonstrate how SDFs constraints are susceptible to adversarial attacks in certain settings. In fact, we note on page 8 that "the ReLU model is liable to generate adversarial samples...". Indeed, we present the figure to point out that increased predictive accuracy does not guarantee improved sample quality, and that ReLU models are particularly susceptible to adversarial attacks.
• Q7: The comment about expensive backpropagation through the SDF algorithm is incorrect (as previous stated). Additionally, the comment that piecewise linear networks are overly limited is odd given that this definition encompasses the majority of neural network architectures as ReLU is a widely used activation function, and we impose limitations on the architecture, only the activations.

We understand that this paper proposes an unusual use of SDFs and that the intuition may be difficult to grasp for reviewers not familiar with domain. As such, we provided additional context in the rebuttal, and would like to point to Appendix B for a detailed 2D walk through of constructing and composing SDFs.

Thank you for your nice comments about the presentation and theory in the paper. Additionally, you raise several valid points in your questions and concerns:

• We have some detailed analysis on the algorithmic complexity of both the SINN/Relu algorithms, and it seems like it was erroneously omitted from the appendices. In short, the SINN algorithm compute complexity is linear in the number of input dimensions and model parameters, and has a very small constant memory requirement. The ReLU SDF algorithm has exponential compute and memory requirements due to using a search heuristic (i.e. BFS/A*) and needing to maintain a stack. A more detailed explanation/proof is attached at the end of this comment. As such, the SINN algorithm is applicable to much larger datasets, while the ReLU algorithm would need some improvements to be practical for larger problems.
• The restrictions for composable constraints are relatively mild. One only need a predictive model with an associated computable SDF. As such, given a suitable formulation of the problems described in [1], [2], composable constraints should be easily applicable. The main challenges we anticipate would be 1) collecting a dataset to suitable train a model and 2) formulating the labels in such a way that the consistency between multiple input sources are visible to the predictive model.
• The core contribution of this paper is an interesting and novel mechanism for inverting a classifier under a system of constraints. While this methodlogy can be applied to other methods (such as diffusion models), this is somewhat outside of the scope of the claims being made.
• Additionally, we find that direct comparisons are somewhat difficult to design. In settings with simple constraints, composable constraints are unfairly penalized as they perform extra compute in order to provide composability on objectives which are not composed. On the other hand, many existing methods cannot accommodate complex constraints such as $(M_a(x) \geq k_a) \text{ XOR } (M_b(x) \geq k_b) \text{ XOR } (M_c(x) \geq k_c)$, and so a comparison is not easy to construct. in fact, this is why we primarily chose to compare our method to guided gradient descent. GGD uses gradient information to invert a classifier given a system of constraints, and thus is a direct counterpart to composable constraints.

Overall, our paper does not aim to outperform existing methods on existing baselines. Rather, we propose a novel mechanism for representing and solving systems of constraints, we then provide theoretical and empirical evidence that the formulation is valid.

Additionally, models such as Diffusion Models, Flow-Matching, etc. are outside of the scope of this work. This work aims to provide a mechanism for efficiently inverting arbitrary classifiers with arbitrary constraints. Whether this method is applied directly on the data, on the latent space of a VAE or in a classifier-guided generation scheme is somewhat orthogonal to the computational and theoretical properties of inverting the classifier in the first place.

Thank you for your detailed review, you raise several interesting points. First, to address the mentioned weaknesses of the paper:

• In the SINN case, the SDF algorithm is actually quite performant, and as described in the paper, can be computed in linear time. We added a revision which expands futher on the algorithmic complexity in Appendix M. However, you are correct that in general, the SDF algorithm may be expensive (such as the case for the ReLU SDF algorithm). Consequently, there is a fundamental tradeoff between the complexity of the model class, and the performance of SDF algorithm. Additionally, we note in the results section that the increased accuracy of a Resnet-based model doesn't necessarily translate to increased generation quality. Furthermore, while we demonstrate practical utility of SDFs for constraint satisfaction, we recognize the necessity to extend this approach to wider families of models to better understand the interactions between models families, network architectures, and generation quality. Such work would be highly technical and theoretical, and thus would be better places in subsequent work.
• Regarding your question about the advantages of local-search versus other approximated solvers, I think that there may be a misunderstanding of Algorithm 2. In general, it is possible to extract the piecewise linear regions of a ReLU network and perform linear optimization. However, as described on page 6 "recent results from tropical geometry indicate that the number of linear domains grows combinatorially with the network depth, and as such it is intractable to enumerate all the domains". Thus we cannot use linear programming as-is, since the number of domains is much too large. In our paper, local search is not a replacement for linear programming, but an extension. We start with the piecewise linear region for the initial point, and then perform linear programming on each of the neighbouring domains. Thus we are not replacing or competing with linear programming solvers, but are using them as a component of a larger search strategy.
• While composable constraints have not been shown to outperform existing methods on existing benchmarks, they provide interesting capabilities not possible with current methods. In particular, we can perform complex, post-hoc and zero-shot constrained generation, with the ability to incorporate multiple predictive models as needed. This is of particular interest in settings where the types of constraints may not be known ahead of time, such as in the case of chemical structure design for industrial chemicals. The rapidly shifting needs would not be well suited to the relatively static generative models which are popular today, and thus a post-method such as composable constraints would provide greater flexibility and tangible benefits in industrial settings.

Overall, I think it would not be unreasonable to view the main concerns with this paper as being related to comparisons to SOTA methods. Your review asks for more detailed comparisons to existing methods, and larger datasets.

While we believe that ZINC-250k and CelebFaceA (224x224) generation are sufficiently scaled-up, we cannot deny that larger datasets exist.

However, we will push-back on the request for more detailed comparisons, as we believe it to be very difficult to construct a fair apples-to-apples comparison. In particular, composable constraints allow for complex boolean predicates to be built up. For example, it would not be unreasonable to have an objective such as $(M_a(x) \geq k_a) \text{ XOR } (M_b(x) \geq k_b) \text{ XOR } (M_c(x) \geq k_c)$. No current methods are able to solve constraints of this form. Thus, we either need compare composable constraints on simpler objectives, which it will be unfairly penalized due to the extra computation to provide the composable properties, or we could simply state that composable constraints work in settings where other models can't be used (and then be penalized for a lack of comparisons).

We compare composable constraints to GGD, since it is the most similar method by virtue of accommodating flexible constraints and explicitely inverting a classifier.

We would urge the reviewers to reconsider this paper in the context of a paper that is proposing a novel methodology from first principles and providing evidence that it functions as intended, with the opportunity to extend the framework to incorporate cutting edge models once the theoretical underpinnings have been established.

Thank you for the detailed review, we are glad to see that the idea of representing constraints as SDFs is received positively.

Now to address the two main concerns with the paper:

• We agree that much of the technical content is relegated to the appendix. However, we explicitly point the reader to the relevant sections in the appendix when applicable (for example on page 5 "The full details are given in algorithm 1 and appendix C."). Unfortunately, the ICLR format only permits 10 pages in the main text and we believe that all of the content in the main body is essential, however we would be grateful for any specific recommendations of section(s) that we could remove or trim.
• We would like to point at the composable constraints do not depend on semantic latent-spaces as such. While relatively small scale, we demonstrated composable constraints in raw-input spcace in the MNIST experiments. The addition of VAEs for the CelebFace A dataset is mostly due to numerical stability and lack of available solvers for augmented lagrangians. However, we do note that the introduction of dimensionality reduction techniques is advantageous in terms of solution quality and runtime. Finally, simple linearization may work, but suffers from a lack of principled methods for balancing quality of solution versus proximity to the initial point. One could construct objectives such as $\mathcal{L}(x) = \alpha\cdot(M_i(x) - y^*)^2 + \beta\cdot||x_0 - x||_2$, but this would open a separate slew of challenges of hyper-parameter tuning and soft versus hard constraint satisfaction. Thus, we believe that this comparison is not trivial.
• Thank you for your comments on the clarity of algorithm 1. We added an updated version to address the typographical error, as well as to show how the gradient is computed. The intuition for obtaining the gradient is that algorithm 1 finds the nearest boundary point, thus producing the gradient is trivial since we can return $x_0 - p_1$ alongside $||x_0 - p_1||_2$
• The closeness of the solution to the initial point is fundamentally tied to the SDF formulation and eqs. 10 and 11. Since the SDF function (and gradient) always point to the nearest solution, then any obtained solution will necessarily be the nearest solution. Thus, the solution produced is a point which is as close as possible to the initial point, while still satisfying the system of constraints.

For your questions:

• Indeed Eq. 2 is not used in the paper, but rather to make a clear distinction and statement of constrained optimization and inverse design.
• In this context, we use the term "Search Algorithm" to denote an algorithm which will somehow search the input space for solutions to the system of constraints. Given the structure of an SINN, we know that the nearest solution will exist on the boundary between the starting point and the SINN nodes. This allows us to provably obtain the minima in linear time (as opposed to a more naive algorithm such as grid search). The augmented gradient step is used as a particular implementation of this theorem. We have added an additional section in the appendix describing the computational complexity of the SDF algorithms (See appendix M).
• The question about feasible solutions is quite astute and we want to address this in more detail. In the single constraint case, it is possible to analytically detect whether a feasible solution exists. As such, if a single constraint is not satisfiable, we can detect this in O(1) time. In the multi-constraint case, this is not possible and we would instead need to either limit the number of iterations of eq. 11, or implement an early stopping mechanism that would detect whether the solution is improving over time.