Transformers satisfy

2021-01-01 · Feng Shi, Chen Li, Shijie Bian, Yiqiao Jin, Ziheng Xu, Tian Han, Song-Chun Zhu

The Propositional Satisfiability Problem (SAT), and more generally, the Constraint Satisfaction Problem (CSP), are mathematical questions defined as finding an assignment to a set of objects that satisfies a series of constraints. The modern approach is trending to solve CSP through neural symbolic methods. Most recent works are sequential model-based and adopt neural embedding, i.e., reinforcement learning with neural graph networks, and graph recurrent neural networks. This work proposes a one-shot model derived from the eminent Transformer architecture for factor graph structure to solve the CSP problem. We define the heterogeneous attention mechanism based on meta-paths for the self-attention between literals, the cross-attention based on the bipartite graph links from literal to clauses, or vice versa. This model takes advantage of parallelism. Our model achieves high speed and very high accuracy on the factor graph for CSPs with arbitrary size.

📄 PDF Abstract BibTeX

Code (0)

등록된 구현이 없습니다.

Methods 이 논문이 사용한 방법론

Linear Layer A Linear Layer is a projection $\mathbf{XW + b}$.

Absolute Position Encodings Absolute Position Encodings are a type of position embeddings for [Transformer-based models] where positional encodings are…

Position-Wise Feed-Forward Layer 설명 없음

Dense Connections Dense Connections, or Fully Connected Connections, are a type of layer in a deep neural network that use a linear operation where every input is connected to every output…

Layer Normalization Unlike batch normalization, Layer Normalization directly estimates the normalization statistics from the summed inputs…

BPE Byte Pair Encoding, or BPE, is a subword segmentation algorithm that encodes rare and unknown words as sequences of subword units. The intuition is that various word…

Multi-Head Attention 설명 없음

Dropout Dropout is a regularization technique for neural networks that drops a unit (along with connections) at training time with a specified probability $p$ (a common value is…

Equivariant non-linear maps for neural networks on homogeneous spaces

2025-04-29 · Elias Nyholm, Oscar Carlsson, Maurice Weiler, Daniel Persson

This paper presents a novel framework for non-linear equivariant neural network layers on homogeneous spaces. The seminal work of Cohen et al. on equivariant $G$-CNNs on homogeneous spaces characterized the representatio…

Number of Attention Heads vs Number of Transformer-Encoders in Computer Vision

2022-09-15 · Tomas Hrycej, Bernhard Bermeitinger, Siegfried Handschuh

Determining an appropriate number of attention heads on one hand and the number of transformer-encoders, on the other hand, is an important choice for Computer Vision (CV) tasks using the Transformer architecture. Comput…

Multi-agent transformer-accelerated RL for satisfaction of STL specifications

2024-03-23 · Albin Larsson Forsberg, Alexandros Nikou, Aneta Vulgarakis Feljan, Jana Tumova

One of the main challenges in multi-agent reinforcement learning is scalability as the number of agents increases. This issue is further exacerbated if the problem considered is temporally dependent. State-of-the-art sol…

Multi-agent Reinforcement Learning

Back Translation Survey for Improving Text Augmentation

2021-02-19 · Matthew Ciolino, David Noever, Josh Kalin

Natural Language Processing (NLP) relies heavily on training data. Transformers, as they have gotten bigger, have required massive amounts of training data. To satisfy this requirement, text augmentation should be looked…

Sentence Survey Text Augmentation Translation

Approximate Nullspace Augmented Finetuning for Robust Vision Transformers

2024-03-15 · Haoyang Liu, Aditya Singh, Yijiang Li, Haohan Wang

Enhancing the robustness of deep learning models, particularly in the realm of vision transformers (ViTs), is crucial for their real-world deployment. In this work, we provide a finetuning approach to enhance the robustn…