Pseudo-Boolean d-DNNF Compilation for Expressive Feature Modeling Constructs

• URL: http://arxiv.org/abs/2505.05976v1
• Date: Fri, 09 May 2025 12:00:43 GMT
• Title: Pseudo-Boolean d-DNNF Compilation for Expressive Feature Modeling Constructs
• Authors: Chico Sundermann, Stefan Vill, Elias Kuiter, Sebastian Krieter, Thomas Thüm, Matthias Tichy,
• Abstract summary: We provide a pseudo-Boolean encoding for feature models, which facilitates smaller representations of commonly employed constructs.<n>We also propose a novel method to compile pseudo-Boolean formulas to Boolean d-DNNF.
• Score: 2.4497587364567925
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Configurable systems typically consist of reusable assets that have dependencies between each other. To specify such dependencies, feature models are commonly used. As feature models in practice are often complex, automated reasoning is typically employed to analyze the dependencies. Here, the de facto standard is translating the feature model to conjunctive normal form (CNF) to enable employing off-the-shelf tools, such as SAT or #SAT solvers. However, modern feature-modeling dialects often contain constructs, such as cardinality constraints, that are ill-suited for conversion to CNF. This mismatch between the input of reasoning engines and the available feature-modeling dialects limits the applicability of the more expressive constructs. In this work, we shorten this gap between expressive constructs and scalable automated reasoning. Our contribution is twofold: First, we provide a pseudo-Boolean encoding for feature models, which facilitates smaller representations of commonly employed constructs compared to Boolean encoding. Second, we propose a novel method to compile pseudo-Boolean formulas to Boolean d-DNNF. With the compiled d-DNNFs, we can resort to a plethora of efficient analyses already used in feature modeling. Our empirical evaluation shows that our proposal substantially outperforms the state-of-the-art based on CNF inputs for expressive constructs. For every considered dataset representing different feature models and feature-modeling constructs, the feature models can be significantly faster translated to pseudo-Boolean than to CNF. Overall, deriving d-DNNFs from a feature model with the targeted expressive constraints can be substantially accelerated using our pseudo-Boolean approach. Furthermore, our approach is competitive on feature models with only basic constructs.

Related papers

• Every Step Counts: Decoding Trajectories as Authorship Fingerprints of dLLMs [63.82840470917859]
  We show that the decoding mechanism of dLLMs can be used as a powerful tool for model attribution.<n>We propose a novel information extraction scheme called the Directed Decoding Map (DDM), which captures structural relationships between decoding steps and better reveals model-specific behaviors.
  arXiv  Detail & Related papers  (2025-10-02T06:25:10Z)
• Sequential-Parallel Duality in Prefix Scannable Models [68.39855814099997]
  Recent developments have given rise to various models, such as Gated Linear Attention (GLA) and Mamba.<n>This raises a natural question: can we characterize the full class of neural sequence models that support near-constant-time parallel evaluation and linear-time, constant-space sequential inference?
  arXiv  Detail & Related papers  (2025-06-12T17:32:02Z)
• Accelerated Test-Time Scaling with Model-Free Speculative Sampling [58.69141724095398]
  We introduce STAND (STochastic Adaptive N-gram Drafting), a novel model-free speculative decoding approach.<n>We show that STAND reduces inference latency by 60-65% compared to standard autoregressive decoding.<n>As a model-free approach, STAND can be applied to any existing language model without additional training.
  arXiv  Detail & Related papers  (2025-06-05T07:31:18Z)
• Compilation and Fast Model Counting beyond CNF [31.620928650659586]
  This paper strengthens our theoretical knowledge of what classes of functions can be efficiently transformed, or compiled, into d-DNNF.<n>The constraints in question are all functions representable by constant-width ordered binary decision diagrams (OBDDs) for all variable orderings.<n>We give a more efficient FPT algorithm for model counting that applies to a sub-family of the constraints and does not require compilation.
  arXiv  Detail & Related papers  (2025-02-01T14:00:04Z)
• Explainable AI using expressive Boolean formulas [0.6323908398583082]
  We implement an interpretable machine classification model for Explainable AI (XAI) based on expressive Boolean formulas. Potential applications include credit scoring and diagnosis of medical conditions.
  arXiv  Detail & Related papers  (2023-06-06T19:18:46Z)
• Bayesian Prompt Learning for Image-Language Model Generalization [64.50204877434878]
  We use the regularization ability of Bayesian methods to frame prompt learning as a variational inference problem. Our approach regularizes the prompt space, reduces overfitting to the seen prompts and improves the prompt generalization on unseen prompts. We demonstrate empirically on 15 benchmarks that Bayesian prompt learning provides an appropriate coverage of the prompt space.
  arXiv  Detail & Related papers  (2022-10-05T17:05:56Z)
• Language Model Cascades [72.18809575261498]
  Repeated interactions at test-time with a single model, or the composition of multiple models together, further expands capabilities. Cases with control flow and dynamic structure require techniques from probabilistic programming. We formalize several existing techniques from this perspective, including scratchpads / chain of thought, verifiers, STaR, selection-inference, and tool use.
  arXiv  Detail & Related papers  (2022-07-21T07:35:18Z)
• Space-Efficient Representation of Entity-centric Query Language Models [8.712427362992237]
  We introduce a deterministic approximation to probabilistic grammars that avoids the explicit expansion of non-terminals at model creation time. We obtain a 10% relative word error rate improvement on long tail entity queries compared to when a similarly-sized n-gram model is used.
  arXiv  Detail & Related papers  (2022-06-29T19:59:50Z)
• Indeterminacy in Latent Variable Models: Characterization and Strong Identifiability [3.959606869996233]
  We construct a theoretical framework for analyzing the indeterminacies of latent variable models. We then investigate how we might specify strongly identifiable latent variable models.
  arXiv  Detail & Related papers  (2022-06-02T00:01:27Z)
• Low-Rank Constraints for Fast Inference in Structured Models [110.38427965904266]
  This work demonstrates a simple approach to reduce the computational and memory complexity of a large class of structured models. Experiments with neural parameterized structured models for language modeling, polyphonic music modeling, unsupervised grammar induction, and video modeling show that our approach matches the accuracy of standard models at large state spaces.
  arXiv  Detail & Related papers  (2022-01-08T00:47:50Z)
• Goal-directed Generation of Discrete Structures with Conditional Generative Models [85.51463588099556]
  We introduce a novel approach to directly optimize a reinforcement learning objective, maximizing an expected reward. We test our methodology on two tasks: generating molecules with user-defined properties and identifying short python expressions which evaluate to a given target value.
  arXiv  Detail & Related papers  (2020-10-05T20:03:13Z)
• Exchangeable Neural ODE for Set Modeling [13.582728834152062]
  We propose a more general formulation to achieve permutation equivariance through ordinary differential equations (ODE) Our proposed module, Exchangeable Neural ODE (ExNODE), can be seamlessly applied for both discriminative and generative tasks. We also extend set modeling in the temporal dimension and propose a VAE based model for temporal set modeling.
  arXiv  Detail & Related papers  (2020-08-06T14:11:36Z)
• Interpretable Entity Representations through Large-Scale Typing [61.4277527871572]
  We present an approach to creating entity representations that are human readable and achieve high performance out of the box. Our representations are vectors whose values correspond to posterior probabilities over fine-grained entity types. We show that it is possible to reduce the size of our type set in a learning-based way for particular domains.
  arXiv  Detail & Related papers  (2020-04-30T23:58:03Z)
• Improve Variational Autoencoder for Text Generationwith Discrete Latent Bottleneck [52.08901549360262]
  Variational autoencoders (VAEs) are essential tools in end-to-end representation learning. VAEs tend to ignore latent variables with a strong auto-regressive decoder. We propose a principled approach to enforce an implicit latent feature matching in a more compact latent space.
  arXiv  Detail & Related papers  (2020-04-22T14:41:37Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.