Blocked Gibbs meets Diffusion Transformers: Unsupervised Learning for Constraint Optimization

• URL: http://arxiv.org/abs/2605.25129v1
• Date: Sun, 24 May 2026 15:17:49 GMT
• Title: Blocked Gibbs meets Diffusion Transformers: Unsupervised Learning for Constraint Optimization
• Abstract summary: Diffusion models have shown promise in learning to solve constraint optimization problems.<n>They are mostly restricted to problems with binary variables and rely on graph neural networks.<n>We investigate the use of Diffusion Transformers to address the aforementioned limitations.
• Score: 38.66247073329942
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Diffusion models have shown promise in learning to solve constraint optimization problems. However, they are mostly restricted to problems with binary variables and rely on graph neural networks, hindering their application to a broader range of problems such as those with general discrete variables or constraint structures that necessitate global rather than local reasoning. We investigate the use of Diffusion Transformers to address the aforementioned limitations. A naive implementation performs poorly due to a fundamental mismatch between the standard diffusion process and constraint solving: while the former applies small, incremental denoising across all variables, the latter requires substantially altering specific subsets of variables to attain feasibility or optimality. Our method, Blocked Gibbs Diffusion Transformer (BloGDiT), is the first to address this limitation by replacing standard joint Gaussian denoising with blocked Gaussian denoising. BloGDiT uses iterative block resampling and anneals the block size over time to facilitate large, targeted edits within a block of variables. Across Sudoku, Graph Coloring, Maximum Independent Set, and MaxCut, BloGDiT matches or outperforms existing methods, demonstrating that blocked Gibbs-style diffusion provides a highly effective inductive bias for Transformer-based constraint satisfaction and optimization.

Related papers

• Efficient Long-Context Modeling in Diffusion Language Models via Block Approximate Sparse Attention [58.484607892210015]
  Diffusion Language Models (DLMs) enable globally coherent, bidirectional, and controllable text generation.<n>Many existing block-sparse attention methods select blocks by fixed sampling patterns over the high-resolution attention space.<n>We propose the Block Approximate Sparse Attention framework (BA-Att) with block-wise pre-downsampled operation.
  arXiv  Detail & Related papers  (2026-05-19T12:01:13Z)
• Guiding a Diffusion Model by Swapping Its Tokens [16.588428780117752]
  We propose a simple method to enable CFG-like guidance for both conditional and unconditional generation.<n>The key idea is to generate a perturbed prediction via simple token swap operations.<n>Our approach selectively exchanges and recomposes token latents, allowing finer control over perturbation.
  arXiv  Detail & Related papers  (2026-04-09T09:54:49Z)
• Sparse QUBO Formulation for Efficient Embedding via Network-Based Decomposition of Equality and Inequality Constraints [0.35331503620315147]
  We propose a method to construct a significantly sparser logical QUBO model for equality and inequality constraints.<n>By adding auxiliary variables based on specific network structures, our approach decomposes the original constraint into smaller, more manageable constraints.<n> Experimental results on D-Wave's hardware show that our formulation leads to substantial reductions in the number of qubits required for embedding.
  arXiv  Detail & Related papers  (2026-01-26T03:40:06Z)
• Efficient Penalty-Based Bilevel Methods: Improved Analysis, Novel Updates, and Flatness Condition [51.22672287601796]
  Penalty-based methods have become popular for solving bilevel optimization (BLO) problems.<n>They often require inner-loop iteration to solve the lower-level (LL) problem and small outer-loop step sizes to handle the increased smoothness induced by large penalty terms.<n>This work considers the general BLO problems with coupled constraints (CCs) and leverages a novel penalty reformulation that decouples the upper- and lower-level variables.
  arXiv  Detail & Related papers  (2025-11-20T20:48:14Z)
• Constraint-Guided Prediction Refinement via Deterministic Diffusion Trajectories [7.279433512595361]
  We propose a general-purpose framework for constraint-aware guided denoising diffusion diffusionDDIMs.<n>Our method iteratively refines it through a diffusion trajectory by a learned prior and augmented by constraint corrections.
  arXiv  Detail & Related papers  (2025-06-15T17:02:07Z)
• Interleaved Gibbs Diffusion: Generating Discrete-Continuous Data with Implicit Constraints [30.624303845550575]
  Interleaved Gibbs Diffusion (IGD) is a novel generative modeling framework for discrete-continuous data.<n>IGD generalizes discrete time Gibbs sampling type Markov chain for the case of discrete-continuous generation.<n>It achieves state-of-the-art results without relying on domain-specific inductive biases.
  arXiv  Detail & Related papers  (2025-02-19T05:51:24Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  Constrained optimization problems abound in industry, from portfolio optimization to logistics. One of the major roadblocks in solving these problems is the presence of non-trivial hard constraints which limit the valid search space. In this work, we encode arbitrary integer-valued equality constraints of the form Ax=b, directly into U(1) symmetric networks (TNs) and leverage their applicability as quantum-inspired generative models.
  arXiv  Detail & Related papers  (2022-11-16T18:59:54Z)
• Maximum Spatial Perturbation Consistency for Unpaired Image-to-Image Translation [56.44946660061753]
  This paper proposes a universal regularization technique called maximum spatial perturbation consistency (MSPC) MSPC enforces a spatial perturbation function (T ) and the translation operator (G) to be commutative (i.e., TG = GT ) Our method outperforms the state-of-the-art methods on most I2I benchmarks.
  arXiv  Detail & Related papers  (2022-03-23T19:59:04Z)
• Cogradient Descent for Bilinear Optimization [124.45816011848096]
  We introduce a Cogradient Descent algorithm (CoGD) to address the bilinear problem. We solve one variable by considering its coupling relationship with the other, leading to a synchronous gradient descent. Our algorithm is applied to solve problems with one variable under the sparsity constraint.
  arXiv  Detail & Related papers  (2020-06-16T13:41:54Z)

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.