Learning to Solve Constraint Satisfaction Problems with Recurrent Transformer
Authors: Zhun Yang
Adam Ishay
Joohyung Lee
Venue: ICLR 2023 poster (2023)
Keywords: transformer
constraint reasoning
semi-supervised learning

Abstract: Constraint satisfaction problems (CSPs) are about finding values of variables that satisfy the given constraints. We show that Transformer extended with recurrence is a viable approach to learning to solve CSPs in an end-to-end manner, having clear advantages over state-of-the-art methods such as Graph Neural Networks, SATNet, and some neuro-symbolic models. With the ability of Transformer to handle visual input, the proposed Recurrent Transformer can straightforwardly be applied to visual constraint reasoning problems while successfully addressing the symbol grounding problem. We also show how to leverage deductive knowledge of discrete constraints in the Transformer's inductive learning to achieve sample-efficient learning and semi-supervised learning for CSPs.

Published as a conference paper at ICLR 2023
LEARNING TO SOLVE CONSTRAINT SATISFACTION PROBLEMS WITH RECURRENT TRANSFORMER
Zhun Yang', Adam Ishay! & Joohyung Lee 'Scooo of Computing and AI, Arizona State University, AZ, USA
Global AI Center, Samsung Research, S. Korea y ai aishay, joolee @aa
ABSTRACT
Constraint satisfaction problems (CSPs) are about finding values of variables that satisfy the given constraints. We show that Transformer extended with recurrence is viable approach to learning to solve CSPs in an end-to-end manner, having clear advantages over state-of-the-arr methods such as Graph Neural Networks, SATNet, and some neuro-symbol syuoosy models. With the ability of Transformer handle visual input, the proposed Recurrent Transformer can straightforwardly be applied to visual constraint reasoning problems while successfully addressing the symbol grounding problem. We also show how to leverage deductive knowledge of discrete constraints in the Transformer's inductive learning achieve sample- efficient learning and semi- eemi-supervised learning for CSPs.
INTRODUCTION
Constraint Satisfaction Problems (CSPs) are about finding values of variables that satisfy given constraints. They have been widely studied in symbolic AI with an emphasis on designing efficient algorithms deductively find solutions for explicitly stated constraints. In the recent deep learning- based approach, the focus is on inductively learning the constraints and solving them in an end-to-ent -nd manner. For example, the Recurrent Relational Network (RRN) (Pamm al., 2018) uses message passing over graph structures to learn logical constraints, achieving high accuracy in textual Sudoku. On the other hand, uses hand-coded information about Sudoku constraints, namely. which variables are allowed to interact. Moreover, it is limited to textual input. SATNet (Wang et al.) 2019) is differentiable MAXSAT solver that can infer logical rules and can be integrated into DNNs. SATNet was shown to solve even visual Sudoku, where the input is a hand-written Sudoku board. The problem harder because model has to learn how to map visual inputs to symbolic digits without explicit supervision. However, Chang et al.) (2020) observed a label leakage issue with the experiment; with proper evaluation, the performance of SATNet on visual Sudoku dropped to 0%. Moreover, SATNet evaluation is limited to easy puzzles, and SATNet does not perform well on hard puzzles that RRN could solve.
On another aspect, although these models could learn complicated constraints purely from data, in many cases, (part of) constraints are already known, and exploiting such deductive knowledge in inductive learning could be helpful for sample-efficient and robust learning. The problem is challenging, especially if the knowledge is the form of discrete constraints, whereas standard deep learning is mainly about optimizing the continuous and differentiable parameters.
This paper provides a viable solution to the limitations the above models based on the Transformer architecture. Transformer-base widespread applications in language ( (Vaswani et al.) 2017 Zhang et al. 2020 Helwe et al. 202T Li
models have not been shown to be effective for CSPs despite their
et al. 2020) and vision (Dosovitskiy al. [020 Gabeur et al.) 2020). Creswell et al. (2022) asserted large language models (LLMs) tend to perform poorly on multi-step logical
that Transformer-bust reasoning problems. In the case of Sudoku, typical solving requires about 20 to 60 steps of reasoning.
Despite the various ideas for prompting GPT-3, GPT-3 is not able to solve Sudoku. [Nye et al. (2021) note that LLMs work well for system intuitive thinking but not for system logical thinking. Given the superiority of other models on CSPs, one might conclude that Transformers are unsuitable for CSPs.

---

Published as a conference paper at ICLR 2023
We find that Transformer be successfully applied to CSPs by incorporating recurrence, which encourages the Transformer model to apply multi-step reasoning similar to RRNs. Interestingly, this simple change already yields better results than the other models above and gives several other advantages. The learning is more robust than SATNet's. Looking at the learned attention matrices, we could interpret what the Transformer has learned. Intuitively, multi-head attention extracts distinct information about the problem structure. Adding more attention blocks and recurrences tends to make the model learn better. Analogously the Vision Transformer (Dosovitskiy al. 2020). model can be easily extended to process visual input. Moreover, the model avoids the symbol grounding problem encountered by SATNet.
In addition, we present a way to inject discrete constraints into the Recurrent Transformer training. borrowing the idea from (Yang et al. 2022). That paper shows way encode logical constraints as a loss function and use Straight-T Through Estimators (STE) (Courbariaux et al., 2015) to make discrete constraints meaningfully differentiable for gradient descent. We apply this idea to Recurrent Transformer with some modifications. We note that adding explicit constraint loss to all recurrent layers helps the Transformer learn more effectively. We also add constraint loss to the attention matrix so that constraints can help learn better attentions. Including these constraint losses in training improves accuracy and lets the Transformer learn with fewer labeled data (semi-supervised learning).
In summary, the paper makes the following contributions.
Recurrent Transformer for Constraint Reasoning. We show that Recurrent Transformer is viable approach to learning to solve CSPs, with clear advantages over state-of-the-ee methods, such as RRN and SATNet.
Symbol Grounding with Recurrent Transformer. With the ability of Transformers to handle vision problems well, we demonstrate that model can straightforwardly be applied to visual constraint reasoning problems while successfully addressing the symbol grounding problem. achieves 93.5% test accuracy the SATNet's visual Sudoku test set, for which even the enhanced SATNet from TTopan et al. 2021) could achieve only 64.8% accuracy.
Injecting Logical Constraints into Transformers. We show how inject discrete logical con- straints into Recurrent Transformer training to achieve sample-efficient learning and semi-supervised learning for CSPs.
BACKGROUND
2.1 CONSTRAINT SATISFACTION PROBLEMS
is a set of logical variables; D = (D...... } and each D; is finite set of domain values for logical variable X;; and C is a set of constraints. An atom (i.e., value assignment) is of the form X₁ = where v E D, A constraint
constraint satisfaction problem is defined as (X, DD C) where = ..,,..., X.} XG
sequence (X,,..., .z) of variables is mapping: D, x... D, {TRUE, FALSE} that specifies the set of atoms that can or cannot hold at the same time. A (complete) evaluation is a set of t atoms {X; any constraint in C, i.e., it makes all constraints TRUE.
i {I, ...... .t. E D,}. An evaluation is a solution if it does not violate
One of the commonly used constraints is the cardinality constraint:
< X& Us V...... 2,}l v
where 1 and nonnegative integers denoting bounds, and for k ()) X X and 2k E Dr.. Cardinality constraint [ is TRUE iff the number of atoms that are true in it is between / and u. If I = u, constraint (I) can be simplified to
{x; U/ .,,. u; =1
which is TRUE iff the number of atoms in the given set is exactly l. if j j and = constraint can be further simplified to X₁ = U;
Example 1 (CSP for Sudoku) A CSP for Sudoku puzzle is such that X = feelll...., cells1) denotes all 81 cells on a Sudoku board; D
and D. = [1....,9) 1,..., 81)
TTee code is available at httpa//e///itttooooo///ea//eeeea
2

---

Published as a conference paper at ICLR 2023
denotes all possible values in each cell; and C consists of constraints cell, = d for each given digit d in cell i, and constraints
Moell, = d, ...,, cell, d]|=1
(3)
for d [1....,9} 9) and any set Ji of cell indices that belong to the same row/column/box, saying that "each digit d should appear exactly once in each row/column/bxx. The solution to the CSP corresponds the solution to the Sudoku puzzle.
2.2 RELATED MODELS
Graph Neural Networks (GNNs). GNNs (Gori et al. 2005 Veličković al. 2018 Kipf & Welling
2017) are closely related to Transformers. They encode graph structures where adjacent nodes affect each other by recurrent message passing. The vanilla Transformer does not have an explicit encoding of the graph structure, In other words, it assumes fully connected graphs and does not exploit the
sparsity of graphs. There have been many recent works bring about the complementary nature of
Transformers and GNNs, such as Dehghann ct al. 2018 8 Dai et al. 2019 Veličković et al. 2018
Yun al. 2019; Rong al. 2020
Lam 2020 et al. 2020 Ying al. 2021 Dwivedi
Bresson 2021).
SATNet. SATNet (Wang et al., 2019) explores semi-definite program relaxations as tool for
solving MAXSAT, which can be employed as layer in deep neural networks to solve composite learning problems, such as visual Sudoku puzzles, that require both visual perception and logical reasoning. SATNet learns to solve visual Sudoku puzzles without any hand-coded knowledge, but
its training relied on the "leakage" of labels, as discovered by Chang et al. (2020) and remedied by 'Topan et al. 2021). The following figure is from (Topaa al. (021) to illustrate the symbol grounding problem the context of 3 portion of Sudoku. The task is identify at given only a visual and ant as the labels (called Ungrounded Dataset). However, the original SATNet training was performed on Grounded Dataset, where the labels also included a so that a digit classifier was trained with the labels in a supervised way. Obviously, learning from the Ungrounded Dataset is harder because learning cannot be broken into two stages, classifying and solving.
8
I
5 9
0 3 4
2
6
0
0 visual
3
7
3
#
a out
a
out
visual
Grounded Dataset
Ungrounded Dataset
Neuro-Symbolic Models for Constraint Reasoning. CLR-DRNet (Bai et al. 2021 is curriculum-
witt-restarts model which leverages a Deep Reasoning Network (DRNet) (Chen al. 2019)
and is applied to visual Sudoku with grounded dataset using rules given as a loss function but cannot be applied Ungrounded Datasets. Neuro-symbolic models such as DeepProbLog (Manhaeve) et al., 2018), NeurASP (Yang et al., (2020). and NeuroLog (Tsamoura et al.) (2211) integrate neural networks with logic programming languages. They perform perception neural networks and logical reasoning in hand-written logic programs. These models have shown that neural network training can benefit from constraints in logic programs.
3 RECURRENT TRANSFORMER FOR CONSTRAINT SATISFACTION PROBLEMS
3.1 RECURRENT TRANSFORMERS
Given a constraint satisfaction problem (x, D. C) such that, for i (I...., 1., 1,11 DD < for a constant c, Recurrent Transformer takes as input the sequence (X1, ...,.... X,) of logical variables and outputs the probability distribution over the values in the domain D; of each X, Let c, be the domain size of X, Without loss of generality, assume that the values in D; represented by their indices, ie., D. = (1...., ). The probability of X; = j is given by the j-th value of the output for X,
A logical variable X; is treated as token whose token embedding is vector of length d, encoding the given information about this logical variable (c.g., some numbers, a textual description, an image, etc.). The positional embedding of X, is randomly initialized vector of length d,, and is to be learned to record data-invariant information for logical variable X, Let Etok, Epos E Ld,, denote the token and positional embeddings of logical variables. The r-th recurrent step in Recurrent Transformer

---

Published as a conference paper at ICLR 2023
with L self-attention blocks and R. recurrences can be formulated follows (r {1...., R)):
(r.0) H (r-1.4)
H blocky (H()-11)
4 {1, ..................... L} E (I,...,4) L}
X (r.)) softmaxx(ayer_norm (..)) Wous)
where the initial hidden embedding H (O.L) is Ezok + Epos and + denotes element-wise addition; H(r.)) E RAxd, denotes the hidden embedding of t logical variables after the /-th (self-attention) block in the r-th recurrent step: block; denotes the (-th Transformer block in the model; layer layer_noma norm denotes layer normalization; denotes matrix multiplication, Wont E Rd is the weight of the output layer; and X (r.4) E [0, 1] denotes the NN output with the hidden embedding (r.0), The figure of the model architecture and the formal definition of block, are given in Appendix A
For logical variable X; and its domain D, = (I...., ). where c; S c, the scalar x(!5)) (i.c., element j.j of matrix X (+()) is interpreted as the probability of atom X; j for j {I,...,G..
6
calo-9
26 0
| I 0
8 0 0 1
Hecurent Iranstormer
0 0
0
0 0 0
0
Token Fosttion Embediing Layer
0 0 3
0 |
0 2
celle
oella
cale1
Figure I: Recurrent Transformer for visual Sudoku problem.
Example 2 (Recurrent Transformer for visual Sudoku) Figure 7 shows how Recurrent Trans- former is used to solve the visual Sudoku problem from (Wang al. 2019). Here, a Sudoku board is represented by 9 x 9 = 81 MNIST digit images where empty cells are represented by images of digit O. The Recurrent Transformer takes as input the sequence (celly,... ...li,...... .eelll. of logical variables, and outputs the probability distribution over atoms cell; = u for (1..... .1), v E {1..... 9}. The information given for each logical variable cell, is the MNIST digit image the i-th cell. Within the Recurrent Transformer, the token, position, and hidden embeddings Eroky Epos, H are in g81x128 and the output X (r.)) in 181x9
Recurrence in Transformers. Adding recurrence to the standard Transformer is not new idea, but its application to CSP novel. Other implementations of recurrence in Transformers (Dehghani et al.) 2018 Hao et al. 2019) apply causal attention make the models predict the next token. In contrast, we use an encoder-only model with full attention and force the Transformer to update all unknown variables every recurrence. Our Recurrent Transformer solves CSP problems incrementally, gradually predicting more unknown variables after it is confident in others. During the inference time, more recurrence steps be used than those used in the training time, which can further boost performance. Furthermore, instead of computing a single loss on the final output as in Universal Transformer (Dehghani al. (2018), we accumulate loss for each output from every attention block at every recurrent step, which yields better performance, as shown in Appendix B.2
3.2 TRAINING OBJECTIVE
Consider labeled data instance (t where is input tokens (which will be turned into the token and positional embeddings Erok, Epos) and E (na, 1, ......c²$ is a label for t, where na denotes an unknown label. Let X (r.1) E Ix be the NN output with input t at recurrent step E {1,... R} and block / E {I,...,L} The cross-entropy loss Leross is defined as follows, where ( denotes element i in I.
Lerose (x(r))) =-
E
(x:(x(()))
(), JE(L....),,.. 1,
For example, in ungrounded visual Sudoku, is a list of = 81 MNIST images and E b,a,1....,9) 9181 is the "ungrounded" solution for the Sudoku puzzle where the label for all given
4

---

Published as a conference paper at ICLR 2023
digits is na. The cross- cross-entropy loss NN output X E R depends only the predictions of empty cells. In other words, no supervision for given digits is provided during training.
The baseline loss Lbase the sum of Leross over the NN output X(n)) from all recurrent steps and blocks.
Dbase
E
Leross ( ,I).
rEf1..... R2, IE(2.....L
Note that we apply the cross-entropy loss to the NN outputs from all recurrent steps and all layers instead of from the very last one. We find that this makes the Recurrent Transformer converge faster.
4 EXPERIMENTS WITH RECURRENT TRANSFORMER
We use LxRyHz to denote our Recurrent Transformer with L = self-attention blocks, R recurrent steps, and z self-attention heads. omitted, the number of heads z is and the embedding size d3 is 128.
4.1 SUDOKU
In this section, we apply Recurrent Transformer to solve Sudoku problem, where a board can be either textual visual.
Dataset. For textual Sudoku, we use the SATNet dataset from (Wang et al. 2019) and the RRN dataset from (Palm al. 2018). The difference is that the RRN dataset is much harder and bigger (with 17-34 given digits in each puzzle and 180k/18k training/test data) than the SATNet dataset (with 31-42 given digits and 9k/1k training/test data). Each labeled data instance in textual Sudoku is (t. where f E {0, (0....,9) 9]81 denotes a Sudoku puzzle (0 represents an empty cell) and 1 E (1,...99] 9]81 the puzzle. For visual Sudoku,
use the ungrounded SATNet-V dataset from (Topan et al., 2021). SATNet-V was created based on the SATNet dataset where (i) each textual input in {0, 10,...... 9) the training (or testing resp.) split is replaced with randomly selected MNIST image in the MNIST training (or testing resp.) dataset, and (ii) the label for each given digit is na, i.e. unknown label that cannot be used to help training. In addition SATNet-V, we created new ungrounded dataset, RRN-V, following the same procedure based on the RRN data set. For faster evaluation of the RRN-V dataset, we randomly sampled 9k/1k training/test data and denoted by "RRN-V (9k/Ik)".
is the solution
Baselines and our Model. We take RRN and SATNet the baselines for textual Sudoku, and take RRN, SATNet, and SATNet* (Topan et al. 2021 (which resolves the symbol grounding issue of SATNet by clustering the input images) as the baselines for visual Sudoku. As RRN was designed for visual Sudoku, we applied the same convolutional neural network (CNN) from (Wang et al. 2019) turn each MNIST image into the initial number embedding of that cell in RRN. For our method on both textual and visual Sudoku, we apply Recurrent Transformer as in Figure I where the only difference is that the token embedding layer is linear embedding layer for textual Sudoku and is the same CNN for visual Sudoku. All evaluations of our model use 32 recurrence steps for training and 64 for evaluation, as done in (Plm et al. 2018).
Table 1:
Whole board accuracy different Sudoku datasets. ERN-hardest consists of copy of the RRN training set, while the testing set consists of only the hardest puzzles with 17 given digits in the RRN test set.
textual Sudoku
visual Sudoku (Ungrounded)
SATNet 31-42
RRN-bardest 17-34 (180k/1k)
SATNet-
RRN-Y
Ngiven (#train/hestt)
17.34 (180k/18k)
31-42
17.34
(9k/Ik)
(9//1))
(9k/1k)
Models
#Purum (lext/visual)
Avcuracy on test data
RRN (Pam et
2018
201k 692k
100%
98.9%
96.6%
0%
0%
SATNer Wany
2019
618k 1029
98.3%
SATNet
Topsin et m 2021
-/ 1049k 13M(TffGGAN
64.8%
0%
LIR32H4
touns)
211k/ 702k
100%
99.5%
96.7%
93.5%
75.6%
Table D shows that our method outperforms the of neural network models for both textual and visual Sudoku in different difficulties. Note that among all methods, only RRN requires prior
5

---

Published as a conference paper at ICLR 2023
knowledge about Sudoku rules (i.e., there is edge in the graph between every 2 nodes if their related cells are in the same row/column/box). Both RRN and SATNet fail on the (ungrounded) SATNet-V V dataset due to the symbol grounding issue. While SATNet" could learn to solve visual Sudoku with the ungrounded dataset, it requires training an InfoGAN with 13M parameters to cluster the inputs. Unlike SATNet". our model works out-of-the-boo on visual Sudoku without carefully adjusting the structure and outperforms SATNet by a large margin.
Although the LIR32H4 model has already achieved the new state-of-the-ar results, can further improve the accuracy by increasing the number L of attention blocks, the number H of heads, or the hidden embedding size du. with trade-off of larger model size. We will analyze the effects of these decision choices on smaller datasets in the following sections.
4.1.1
ABLATION STUDY ON MODEL DESIGN (LXRYHZ) WITH TEXTUAL SUDOKU
80
80
190
'60
spcuracy
40
L64R11
L4R16
60
20 givers
17 givens
L29432
23 givers
20
L1R32
19916
2
26 givens
29 givens
0
L1R16
32
150
200
10
30 num of recurrences
50
60
epoch
Figure 2: (left) Running average of the test accuracy for every 10 epochs of Recurrent Transformer with different and Rt trained the same 8k RRN data. (right) Test accuracy function of the number I of recurrences when testing on different difficulty puzzles in the RRN dataset, using the same I.1R22 model trained on 180k RRN data.
Effeets of Blocks and Recurrences. To analyze the effects of blocks and recurrences, we trained six LxRy(H4) models with different numbers of self-attention blocks L and recurrences R on an 8k/2k (training/tcst) RRN dataset with Lrase. Figure 2 (Ieft) compares the whole board accuracy of these models, showing that more self-attention steps (equal to L R)) lead to higher accuracy. With the same number of self-attention steps, when L is small (e.g.. L I 4), more parameters introduced by a larger L slightly increase accuracy. On the other hand, adding recurrences is essential, and the non-recurrent model L64R1 performs poorly compared to the Recurrent Transformers.
The number of recurrences T during testing can be higher than R during training. Indeed, Figure 2 (right) shows that when T S 64, the more recurrent steps T are, the higher accuracy is achieved with the same LIR32 model trained with 32 steps, and the improvement is bigger for harder puzzles.
What Multi-Head Attentions Look at. Without prior knowledge of the Sudoku game, Recurrent Transformer learns purely from (puzzle, solution) pairs that each cell should pay attention to all cells in the same row, column, and x 3 box through the attention mechanism. We trained an LIR32 model with 1 to 4 self-attention heads on the SATNet dataset with Lrase. We found that the attentions on row, column, and box are clearly separated in different heads if the number of heads is greater or equal to 3 and would merge otherwise. Also, more attention heads help faster convergence, and accuracy may decrease if the number of attention heads is too small to capture different semantic meanings. More details and visualization of the attention matrices are given in Appendix B.1
Effect of Positional Embedding. To evaluate the effect of positional embedding, we trained the LIR32 model without positional embedding the SATNet dataset with Lbase, finding that removing positional embedding decreases the test accuracy from 100% to 0%. This is because positional embedding is essential for CSP as it is the only source to differentiate logical variables (e.g.. cell,.... cellsi) ) with the same given information (e.g., digit in both cell 4 and cell 10 in Figure I).
4.1.2 ANALYSES ON SYMBOL GROUNDING WITH VISUAL SUDOKU
In visual Sudoku, we observed similar effects of different model designs as in textual Sudoku. We refer the reader to Appendix B for more details. In this section, we analyze how the symbol grounding issue is resolved in Recurrent Transformer by applying the same LIR32 model on both the RRN-V dataset and its grounded version (i.e., the label for every given digit is provided instead of na). For each of the two trained models, we evaluate their (i) whole board accuracy, (ii) solution accuracy where a board is counted correct if the prediction on all non-given cells is correct (even when the

---

Published as a conference paper at ICLR 2023
given digits incorrectly classified), and (iii) givens cell accuracy, i.., the per-cell classification accuracy of the given cells.
Whole board and Solution Accuracy
Gell Accuracy
ground solution accuracy ungrouss SOLUEACH socuracy
groves gavens 0ell accuracy
unproin Eivens COlL acceracy
23
Figure 3: (Ieft) The whole board accuracy and solution accuracy of the LIR32 model trained on the grounded or ungrounded RRN-V dataset (9k/Ik). (right) The givens cell accuracy of the same models.
When trained on the grounded dataset, the LIR32 model quickly learns to classify the givens in 1 epoch, as shown in Figure 3 (right). On the other hand, with the ungrounded dataset, the LIR32 model starts to classify the givens correctly at around epoch 85. In Figure (1eft) and (right), the solution accuracy and givens cell accuracy (with the ungrounded dataset) increase around the same time, indicating that digit classification is being jointly learned with solving. Interestingly. our model achieves 99.36% classification (givens cell) accuracy without explicitly training for Furthermore, the solution accuracy 75.5%) is consistently higher than the whole board accuracy (74.8% as shown in Figure 3 (left), meaning that even when givens are not correctly classified, the solution can still be attained. We attribute this to the fact that reasoning is on the latent space instead of classifying and solving in two steps, as SATNet does.
4.2 OTHER EXPERIMENTS
Due to lack of space, we summarize other experiments with Recurrent Transformer below and refer the reader to Appendix D for the details.
16x16 Sudoku. We train our LIR32H8 model (d,, 256) on 16x16 textual Sudoku. We generate two 10k (9k/Ik training/test split) datasets of difficulty "simple" with an average of 111 givens and "medium" with an average of givens. With 64 recurrent steps during inference, we achieved 99.9% accuracy on both test sets, meaning that there is only one wrongly predicted board solution. Due to the absence of 16x16 Sudoku generator that can produce fewer givens, we could not test on harder boards.
MNIST Mapping. The MNIST Mapping problem was proposed (Chang et al. 2020 as simple test for the symbol grounding problem. It requires learning a bijection that maps an image of an MNIST digit to one of the 10 symbolic digits. (Chang et al. 2020) shows that SATNet is sensitive to this task and often fails without delicate tuning. Our Recurrent Transformer achieves 99% accuracy.
a game that consists of an initially empty N x N grid representing a binary image, where each cell must take on a value of or 1. Each row and column have constraints that must be satisfied complete the image successfully. A constraint for a row/column is a list of numbers, where each number corresponds to contiguous blocks of cells with value for row/column. The Recurrent Transformer LIR11644 achieved 97.5% test accuracy on 7x7 grids and 78.3% on 15x15 grids.
Nonograms. Nonogram (attps: : //nn wikipedia
INJECTING LOGICAL CONSTRAINTS IN RECURRENT TRANSFORMER
5.1 INJECTING GENERAL CARDINALITY CONSTRAINTS VIA STE
Although Recurrent Transformer can learn to solve CSPs purely from labeled data, could inject the known constraints to help it learn with fewer labeled data. In this section, we follow the idea from
CL-STE (Yang et al. 2022) and propose lightweight constraint loss method for special family of constraints in CSP, namely the cardinality constraint that restricts the number of atoms in a set that can hold at the same time.
7

---

Published as a conference paper at ICLR 2023
The main idea of CL-STE is to binarization function B to turn continuous values x in NN output (r.)) into discrete values ((x) where ((z) is (denoting TRUE) x 2 0.5 and (denoting FALSE) otherwise. A constraint loss is then defined on these Boolean values and set of propositional formulas in the Conjunctive Normal Form (CNF). Since aB(z) zero almost everywhere, the idea of
Bir
STE is to replace aB(x) with trraightthhoouee estimator Be(z) for some (sub)differentiabbl function Ar s(z) that the constraint loss has non-zero gradient on ((r1).
dz
While CL-STE has successfully injected discrete constraints into NN training, representing cardinality constraints in CNF is tedious. On the other hand, we notice that the binarization function ((x)) enables direct counting on discrete values. Under this observation, for the cardinality constraint
1 5 xxx1= = UI,..., Nyt v S
we construct a vector x: E RR* of probabilities j in æ)) is the probability of Xij- V/ for j E {l....,. ..). and design constraint loss as follows:
atoms in the given set such that æ; (i.e., element
Lu, (az) = [(())<] x (c(x)) - 1)2 c())>o x (c(x)) - u)²
where scalar e(x:) = B(x) = B(r,), and 1 condition is 1 if condition is true, otherwise. Similarly, constraint 1( u1...., , Xx vx}
be encoded in the following loss.
((n) = (c(x: n)
(5)
In constraint losses (4) and ( c(xr) is the number of Is in the binarized vector B(x), which corresponds to counting the number of true atoms in constraints (T) and ( Note that the binarization function B(x) enables the counting, but its gradient dur
(B(a) is always O whenever differentiable, so minimizing (4) and (5) will work in updating NN parameters.
As with CL-STE, we use the identity STE replace the gradient aB(r) 8er with so that the gradient of each constraint loss B(x) becomes the "straight-though estimator" of the gradient æ. In this way, we can do counting on the NN output with meaningful gradients. Although CL-STE could also represent the constraint loss (5) for n (uniqueness and existence of values), the size of the CNF representation could be huge.
Example 3 (Constraint Loss on Output) Cardinality constraint loss 5 can used to define the constraints in Sudoku problem
Sudoku X (x()1))
Σ
Σ (x)))
fE(row, boz) SE(),...811
where (r.I) 8181 the NN output; Xrow "row,Xoo X X E [R81x9 are reshaped copies of ((r)) such that each row in them contains the predictions in the same row/column/box; and X denotes row i of matrix X Intuitively. LSudoka says that "exactly one digit (1...., 9} can be predicted the same row/column/box" Note that, in CL-STE, the same Sudoku constraints are represented by CNF with 729 atoms and 8991 clauses, which requires computation on a big matrix in {-1, 0, 1] 8991 X
Furthermore, since the values in vector these cardinality constraint losses to an attention matrix, representing additional constraints (not in the original CSP) that should be satisfied by the attention.
not limited to probabilities in NN outputs,
apply
Example 4 (Constraint Loss Attention) In Sudoku problem, an attention matrix ((ri)) RS1x81 computed in the 1-th block the r-th recurrence where A(r..) normalized atten- tion weight that can be interpreted as the percentage of attention from cell i cell j. The cardinality
constraint loss (5) can also be used to define the following constraint loss
Lattention
(r())) (x)
where x = E(A O M.5); M is the adjacency matrix in {0, 1181x88 such that Mr.5 is iif cells
i and j are in the same row, column, or box; C denotes element wise multiplication. Intuitively, the i-th element in x E 181 denotes the probability of the i-th cell paying attention its adjacent cells. Minimizing Lattention (A(r.)) makes all 81 cells pay attention to their adjacent cells.
8

---

Published as a conference paper at ICLR 2023
Similarly to the baseline loss Losse, which is the sum of Lerose NN output X ( from all recurrent steps and blocks, the total constraint loss Lconstraint is also accumulated over all NN outputs. The total loss with constraint loss is Liotal Lbase + Lconstraint.
The constraint loss for the Sudoku problem is
Lconstraint
Σ
(aLSsdokkul (X (x(r)) + BLattention (A (A(:)))
rEft..,, (E(......)
where a, are reals in [0, 1] that are arperpparametes specified in Appendix F2
5.2 EXPERIMENTS ON INJECTING LOGICAL CONSTRAINTS IN RECURRENT TRANSFORMER TRAINING
Table 2: Effect of adding constraint losses Lattention (att) and Luudoku (sud) the baseline loss Crase when training the same LIR32 model on 9k RRN or RRN-V training data.
Table 3: Effect of adding constraint loss Lconstraint and thousand Unlabeled data (denoted by z=U)) when training the same LIR32 model 4k Labeled RRN RRN-V training data (denoted by 4KL).
textual Sudoku T=64
visual Sudoku
textual Sudoku 1==32
visual Sudoku
Data
T==32
T==64
atl
sud
T T==64
T=32
T=
4kL
58.0%
62.0%
40.9%
44.0%
80.3%
81.9%
72.0%
75.6%
4XL Leandtrannt
65.4%
69.2%
47.5%
50.4%
80. 1%
84.4% 34.
74.4%
79. 79.3%
4kl.
4kU Coonstraint
65.8%
69.9%
57.2%
61.0%.
83.8%
86.3%
76.4%
79.1%
4k1 SKT Ceonttriin
70.7%
73.3%
60.8%
64.4%
83.3%
87.0%
79.9%
83.6%
To evaluate the effects of different logical constraint losses, we trained the L1R32 model on the 9k IK (training/ / test) RRN dataset and the 9k / 1k RRN-V dataset for 300 epochs until convergence with and without constraint losses. Table shows that the same Recurrent Transformer model can further be improved if, in the total loss, we include Lattention and/or Lsudoka each neural network output, where the accuracy is evaluated with 32 or 64 recurrent steps T during testing. We also observe a better performance gain with Sudoku than with Lattention because the baseline model (trained with Cruse only) already learns the attention matrices well, as shown in Figure5]in Appendix [ Besides, when use 64 recurrences during testing (whereas trained with 32 recurrences). the same Recurrent Transformer model has bigger improvements in the test accuracy when is also trained with constraint losses.
Since constraint loss Coonstraint (accumulated by LSudoku and Lattention) does not require labels, we could use it for semi-supervised learning tasks. Table 3 shows that, with only 4k labeled data, adding Cconstraint increases the whole board accuracy of Ik test data, which can further be improved by adding additional 4k and 8k unlabeled data along with Lconstroint-
The shortest path problem is from (Xu et al. 2018) and is about finding the shortest path given a graph and the two endpoints. The example used in (Xu et al. 20188] Yang et al. 2020 demonstrate the effectiveness of semantic/constraint loss on neural network learning. Our experiment indicates that Recurrent Transformer achieves higher constraint accuracy, confirming the effects of the injected path constraints on Recurrent Transformer (Table in Appendix D.I)
CONCLUSION
With the widespread success of Transformers on system perception tasks, it is intriguing that they could also perform well on system logical reasoning problems. Adding recurrences to the baseline model already outperforms the existing methods, especially on visual Sudoku puzzles with large margins (93.5% over enhanced SATNet's 64.8%). successfully addressing the issue of symbol grounding. We further improve the results by injecting underlying constraints into Transformer training so that the model can learn with fewer data, converge faster, and even improve accuracy. Our experiments show that more recurrences during training tend to yield higher test accuracy and additional recurrences during testing could also help. The number of attention blocks affects the size and modeling power of Recurrent Transformer. More attention heads lead to faster convergence, and the accuracy may decrease if the heads are too few to capture different semantic meanings.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENTS
This work was partially supported by the National Science Foundation under Grant IIS-2006747.
REFERENCES
Yiwei Bai, Di Chen, and Carla P Gomes. CLR-DRNets: Curriculum learning with restarts solve visual combinatorial games. 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Schloss Degstuhl-LeibnnzzzZzntuum für Informatik, 2021.
Deng Cai and Wai Lam. Graph transformer for graph-to-sequence learning. In Proceedings of the AAAI Conference Artificial Intelligence, volume 34, pp. 7464-7471, 2020.
Oscar Chang, Lampros Flokas, Hod Lipson, and Michael Spranger. Assessing SATNet's ability to solve the symbol grounding problem. Advances in Neural Information Processing Systems, 33: 1439,1439, 2020.
Di Chen, Yiwei Bai, Wenting Zhao, Sebastian Ament, John M Gregoire, and Carla P Gomes. Deep reasoning networks: Thinking fast and slow. arXiv preprint arXiv:1906.000: 00855, 2019.
Matthieu Courbariaux, Yoshua Bengio, and Jean-Pierre David. Binaryconnect: training deep neural networks with binary weights during propagations. In Proceedings of the 28th International Conference on Neural Information Processing Systems-Vold 2, pp.
2015.
Antonia Creswell, Murray Shanahan, and Irina Higgins. Selection-inference: Exploiting large language models for interpretable logical reasoning. arXiv preprint arXiv:2205.09711 2022.
Zihang Dai, Zhilin Yang, Yiming Yang, Jaime Carbonell, Quoc V Le, and Ruslan Salakhutdi- nov. Transformer-Xi XL: Attentive language models beyond a fixed-length context. arXiv preprint arXiv:1901.02866 02860, 2019.
Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Eukasz Kaiser. Universal transformers. arXiv preprint arXi::1807.038/9 2018.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint 2rX1::2010.11929, 2020.
Vijay Prakash Dwivedi and Xavier Bresson. generalization transformer networks to graphs. AAAI Workshop Deep Learning Gruphs: Methods and Applications, 2021.
Valentin Gabeur, Chen Sun, Karteek Alahari, and Cordelia Schmid. Multi-modal transformer for video retrieval. In European Conference on Computer Vision, pp. 214-229. Springer, 2020.
M Gori, Monfardini, and F Scarselli. new model for learning in graph domains. In Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005., volume 2, pp. 729-734 IEEE, 2005.
Jie Hao, Xing Wang, Baosong Yang, Longyue Wang, Jinfeng Zhang, and Zhaopeng Tu. Modeling 2019.
recurrence for transformer. arXiv preprint
Chadi Helwe, Chloé Clavel, and Fabian M Suchanek. Reasoning with transformer-based mod- els: Deep learning, but shallow reasoning. In 3rd Conference Automated Knowledge Base Construction, 2021.
Ziniu Hu, Yuxiao Dong, Kuansan Wang, and Yizhou Sun. Heterogeneous graph transformer. In Proceedings of The Web Conference 2020, pp. 2704-2710, 2020.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In Proceedings of the 5th International Conference on Learning Representations, ICLR 2017, 2017.
10

---

Published as a conference paper at ICLR 2023
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient- learning applied to document recognition. Proceedings of the IEEE, 86(11))2278-25 -2224, 1998.
Wenda Li, Lei Yu, Yuhuai Wu, and Lawrence C Paulson. Isarstep: a benchmark for high-level mathematical reasoning. arXiv preprint 2006:20000.09265, 2020.
Robin Manhaeve. Sebastijan Dumancic, Angelika Kimmig, Thomas Demeester, and Lue De Raedt. Deepproblog: Neural probabilistic logic programming. In Proceedings of Advances in Neural Information Processing Systems, pp. 3749-3759, 2018.
Maxwell Nye, Michael Tessler, Josh Tenenbaum, and Brenden Lake. Improving coherence and consistency in neural sequence models with dual-system, neuro-symbolic reasoning. Advances in Neural Information Processing Systems, 34:2119222299992222424 2021.
Rasmus Palm, Ulrich Paquet, and Ole Winther. Recurrent relational networks. Proceedings of Advances in Neural Information Processing Systems, pp. 3368-3378, 2018.
Yu Rong, Yatao Bian, Tingyang Xu, Weiyang Xie, Ying Wei, Wenbing Huang, and Junzhou Huang. Self-supervised graph transformer on large-scale molecular data. Advances in Neural Information Processing Systems, 33:12559-12577 12571, 2020.
Sever Topan, David Rolnick, and Xujie Si. Techniques for symbol grounding with SATNet. Advances in Neural Information Processing Systems, 34, 2021.
Efthymia Tsamoura, Timothy Hospedales, and Loizos Michael. Neural-symbolic integration: A compositional perspective. In Proceedings of the AAAI Conference on Artificial Intelligence, pp- 5051-5060, 2021.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. In Advances neural information processing systems, pp. 5998-6008, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. International Conference on Learning Representations, 2018.
URL httphttttps::/peereeeeee
net./ forum? i id=rJXMp
Po-Wei Wang, Priya L Donti, Bryan Wilder, and Zico Kolter. SATNet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver. In Proceedliggs of the 35th International Conference on Machine Learning (ICMI),, 2019.
Jingyi Xu, Zilu Zhang. Tal Friedman, Yitao Liang, and Guy Van den Broeck. semantic loss function for deep learning with symbolic knowledge. In Proceedings of the 35th International Conference on Machine Learning (ICML), July 2018. (RRLaatt:///aaree
es ucla. edu/ papers/
XuICML18 pdf
Zhun Yang, Adam Ishay, and Joohyung Lee. NeurASP: Embracing neural networks into answer set programming. In Proceedings of International Joint Conference on Artificial Intelligence (ICCAI), pp. 1755-1762, 2020. doi: 10. n..24963/jcaai.2222222
Zhun Yang, Joohyung Lee, and Chiyoun Park. Injecting logical constraints into neural networks via straight-througe estimators. In International Conference on Machine Learning, pp. 25096-25122. PMLR, 2022.
Chengxuan Ying. Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie- Liu. Do transformers really perform badly for graph representation? Advances in Neural Information Processing Systems, 34, 2021.
Scongjun Yun, Minbyul Jeong, Rachyun Kim, Jaewoo Kang, and Hyunwoo Kim. Graph transformer networks. Advances in neural information processing systems, 32, 2019.
Jingqing Zhang, Yao Zhao, Mohammad Saleh, and Peter Liu. Pegasus: Pre-training with extracted gap-sentences for abstractive summarization. International Conference on Machine Learning, pp. 1 11399 PMLR, 2020.

---

Published as a conference paper at ICLR 2023
A RECURRENT TRANSFORMER DETAILS
Figure shows a multi-layer Transformer encoder architecture (a) and the Recurrent Transformer architecture in our work (b), where every dotted box denotes a self-attention block. An output layer consists of a layer normalization, a linear layer, and softmax activation function. (b), all output layers share the same parameters, while every self-attention block has its own parameters.
Oulpul
Oulput
Oulput
Culput
Probabillics
Probabillies
Probebillies
Probabillias
Softmax
Softmax
Softmax
linsar
Linear
Jnear
near
Layer Norm
Layar Nurm
Layer Norm
Layer Norm
Feeo Forward
Feed Forward
Feed Forward
Feod Forward
Layer Norm
Layer Norm
Layer Norm
Layer Norm
Nx
Muli--Haad
Mull--Had
Muli-HHad Altention
Mulli-Haad Attention
ottention
Attencion
Layer Nor
Layer Norn
Laver Norm
Layer Norn
Token Pos
Token Pos
Emoedding
Emrbecdinn
inputs
Imputs
(a)
(b)
Figure 4: (a) Transformer encoder. (b) Recurrent Transformer encoder.
The Recurrent Transformer with I. self-attention blocks and R recurrences can be formulated as follows:
(r,0) (--.L)
Vr E {l...., R}
H (r.)) = block, (x)-1)))
Vr E (1,.... RII...,,),, R), VT (I....,I.) Vr E (I,...,R), V (1.....
(n.) softmax(layer (aaenaallar_noomm(2 (ormnnooooHH
out)
where (r.) E Rxxda denotes the hidden embeddings of L input tokens after the I-th (self-attention) block the r-th recurrent step, bloek, denotes the /-th Transformer block in the model (i.e., the I-th dotted box in Figure
4 (b)). layer aoyer_norm denotes layer normalization, denotes matrix multiplication, Wout E dd is the weight of the output layer for classes, and X E [0. 1 denotes the NN output with the hidden embedding H
Each block, is defined on weights w(O) w(l) w(O) D Rddx (for simplicity, we describe single-head case) and multilayer perceptron MIP, with output size dn.
K (n/) = llayerr wat__norm(HH (
(nr))) = layer norm (1)) w
K
(n)) softmax ((1)))
(K(ND)T
((n) = layer norm norm(H (n.)) ((())
Vdh
V = (A (nd) v(.0)) w + (r.)))
block, (H (n:)) = MLP,
V*)) + V
Here, (r.)), H ((.)), Q(n)), (r.)), V E txd, and A (r.0 e [0, 1
The parameters are in terms of input vocabulary size (v), context size (t), number of classes (c), hidden embedding size (d,), and the hidden layer size (dMLP) of MLP,, which is of shape (dn, dMLP, d,).
12

---

Published as a conference paper at ICLR 2023
Operation
Parameters
Parameter Count
Parameter
Value
Token Embedding Positional Embedding
da. t x dy
X 128 1280
10
81 x 128 10, 368
t
81
Melti-Heed Self-Attention
4(di, da)
4(128* 128)
(Wk) 9 W wi!)
(the dy, for bias)
66, 048
dy 128
Layer normalization MLPP
3 X 2dp.
3 xx2x x 128 768
dMLP
512
dAdMLP dMLP +dMLPdh, + dn.
2 128 x 512 + 512
(a) Parameter Values
(dh, dMs.P, dr.)
+128 131, 712
Output layer Wont
CnC.
128 x 9 1, 152
(b) Parameter Counts
Table 4: Parameter values and counts for LIR32H4 model for symbolic Sudoku.
As shown in Table the parameters and their counts are shown. There are a total of 21 211,328 parameters. For (Wan et al. 2019), the number of parameters for Sudoku is 618,000 in total. This is (n + aux) X m, where auxiliary variables, and m is the rank of the clause matrix. The (Palm et al. (2018) work has total of 201,194 trainable parameters, which come from the row, column, and number embeddings, and the three MLPs used for node updates, message passing, and producing output probabilities.
the number of input variables, aur is the number of
B MORE ABLATION STUDIES ON SUDOKU EXPERIMENTS
B. EFFECTS AND VISUALIZATION OF MULTI-HEAD ATTENTION
Learned altertion with hoads
Leamed attentin with hoads
Leamed attention with hoads
Learned atteniion with hoad
rOW
100
culumm
80
apcuracy
60
1R32H4
40
1R3323
LR3222
20
1R32H11
box
0
100
150
200
250
300
epoch
Figure 5: (left) Heatmaps of the learned 81 81x81 attention matrices in the LIR32 Recurrent Transformer with varying numbers of heads. (right) Test accuracy vs. epochs for these models.
Without prior knowledge the Sudoku game, Recurrent Transformer learns purely from (puzzle, solution) pairs that each cell should pay attention all cells in the row, col- umn, and 3 x box through the attention mechanism. We trained an LIR32 model with to self-attention heads the SATNet dataset with Loase. Figure 5 (left) visualizes the learned attention matrices they correctly pay attention to each row, column, and box, respectively. For example, the first row of the top-left attention matrix in Figure (left) learns purely from data about the 9 atoms to
13

---

Published as a conference paper at ICLR 2023
pay attention in constraint B where {t.....j) f1,....9) and d 1. These attentions are clearly separated into different heads if the number of heads is greater than or equal to and would otherwise merge. Figure 5 (right) compares the whole board accuracy of these models, showing that more attention heads help accelerate convergence. The accuracy may decrease the number of attention heads is too small to capture different semantic meanings.
B.2 RECURRENT TRANSFORMER VS. VANILLA TRANSFORMER
There are two main decision choices in Recurrent Transformer: adding recurrence and applying losses to all blocks at all recurrent steps. To justify our decision choices, compared 3 Transformer designs on the textual Sudoku problem under 3 settings. Figures 7 and@shhow the experimental results textual Sudoku SATNet (9k/1k for training/testing), Palm (9k/1k), and Palm (3k/1k) datasets where
the black line denotes the vanilla Transformer L32R1 with 32 blocks and with the cross- entropy loss applied to the final output;
the yellow line denotes the Recurrent Transformer LIR32 with single block, 32 recurrences, and with the cross-entropy loss applied to the last output; the red line denotes the Recurrent Transformer LIR32 with single block, 32 recurrences, and with the cross-entropy loss applied to 32 outputs.
test_ aac//tettNN_boet
test_ Dest_acc/testNN_bee N_board
100
80
test_acc/testhh_cce
40
40
0
200
100
200
300
400
500
Figure 8: Cell test accuracy on Palm (3k/1k)
Figure 6: Whole-board test ac- curacy on SATNet (9k/1k)
Figure Whole-board test ac- curacy on Palm (9k/Ik)
We can see that
(comparing black and yellow lines) adding recurrences allows the model to achieve higher accuracy (especially for harder problems the Palm dataset) with much fewer parameters in the model (1 block vs. 32 blocks);
(comparing yellow and red lines) applying losses to all blocks makes the Recurrent Trans- former model more stable and achieves higher accuracy than the Recurrent Transformer with a single loss;
(comparing Figure with the other 2 figures) the benefit of recurrence and losses all blocks is greater when the number of data is smaller. Figure g compares the cell accuracy under the above 3 settings when trained only 3k Palm data. In this figure, using recurrent blocks increases the converged cell accuracy from 17.7% to 46.3%, and applying losses to all blocks further improves the cell accuracy to 76.5%. and it has not converged.
B.3 SEMI-SUPERVISED LEARNING WITH CONSTRAINT LOSS
In T we showed how constraint loss helps in a semi supervsuee setting for textual and visual Sudoku. To analyze the effect of constraint loss experiments for both textual and visual Sudoku and recorded the running average of the test accuracy for every 10 epochs in Figures and TO
unlabeled data instances, continued the
We set the batch size to around 64 in the experiments in Figure Soureeaad and to around 128 in the experiments in Figure 10 The batch sizes are slightly adjusted to have integer number split on labeled and
14

---

Published as a conference paper at ICLR 2023
secure (96)
20k base constraint
base constraint
12k base
Ul base constraint
+ U] base constraint
[4k L1 base constraint
base
100
200
epoch
300
400
500
Figure 9: Effect of adding constraint loss Coonstraint and x thousand Unlabeled data (denoted by
rkU) when training the same LIR32 model on 4k Labeled RRN training data (denoted by 4kL).
60
50
40
14k 20k U] base constraint
accuracy (96)
[4k 16k U] base constraint
14k 12k U] base constraint
30
base constraint
4k
base + constraint
20
base + constraint
[4k base
200
400
epoch
600
800
Figure 10: Effect of adding constraint loss Cconstraint and thousand Unlabeled data (denoted by zkU) when training the same LIR32 model on 4k Labeled RRN-V training data (denoted by 4kL).
unlabeled data in each batch. To reduce the effect constraint losses, in all experiments, the weights (a, of the constraint losses Lendoku and Lottention are set to (1, 0), i.e., only the constraint loss Laudoku is used with fixed weight We can see that
tuning on the weights of
adding constraint loss improves the baseline accuracy by large margin when trained with limited labeled data;
with the help of constraint loss, adding more unlabeled data improves the accuracy in beginning but the improvement is getting smaller;
if we don't lower the weight for the constraint loss and keep increasing the number of unlabeled data, adding unlabeled data may lower the accuracy at some point the signals (i.e., gradients) from constraint loss may overwrite the signals from the labels.
B.4 CARDINALITY CONSTRAINT LOSS vs. CL-STE LOSS
The proposed cardinality constraint loss different from constraint loss in CL-STE Yang et al. (2022). We tried the original design of constraint loss in CL-STE but it computes too slowly due to the exponential size of CNF used to represent a cardinality constraint.
In Table we applied the cross-entropy loss, the CL-STE loss, and the cardinality constraint loss to train the same RRN Palm et al. (2018) on the SATNet textual Sudoku dataset Wang et al. (2019). The cross-entropy loss serves as the bascline loss and is used in all four rows in Table 5 during training. Here, Rt is the number of recurrent steps and 32 in the RRN model; N Atom the number of Boolean atoms in Sudoku and is 81 9 729; and N umCllusee is 8991 which is the number of clauses in the CNF for Sudoku. As we can see, the proposed cardinality constraint loss has the same computation size the cross-entropy loss, thus almost does not affect the training time. On
15

---

Published as a conference paper at ICLR 2023
Table 5: Computation Size of Different Losses (R 32, NumAtoo 729, NumClause 8991)
Loss
Applied To
Computation Size
Time/Epoch
Cross Entropy
all recurrent steps
O x N Num.Alom) ( x N NumAtom x N NumCCausee)
120s
CL-STE
first recurrent step
211s
CL-STE
all recurrent steps
O(R x Num x NumClause)
3796s
Cardinality (ours)
all recurrent steps
O(R NumAAto))
122s
the other hand, the constraint loss in CL-STE computes much slower since the computation size is propositional to the number of clauses in CNF, whose size is exponential to represent cardinality constraint. In addition to the cross-entropy loss that is applied to the output from all recurrent steps, if we only apply the CL-STE loss to the output from the first recurrent step as done in the CL-STE paper, the training time per epoch is 21 s.. Note that batch size is not included in the computation size for simplicity. All experiments use batch size of 16 except for the third row (applying CL-STE loss to the outputs from all recurrent steps). If we apply the CL-STE loss to all recurrent steps, we have decrease the batch size by 8 times to fit the GPU memory and the training time per epoch is increased to 3796s.
C DETAILED COMPARISON WITH SOTA MODELS FOR VISUAL SUDOKU
2021) and Chang et al. 2020) showed that the original SATNet implementation failed on symbol grounding, which was not apparent due to a data leakage issue where labels for the input symbols were exposed during training time. Introduced in (Topan et al. (02I), the ungrounded visual Sudoku dataset does not include the symbolic label for the given numbers, while the grounded one does.
Topan et al.
SATNet fails on ungrounded visual Sudoku (SATNet- V), achieving 0% accuracy. To address this, (Topan et al. 2021) alters SATNet by using InfoGAN to cluster the inputs and then jointly trains on MAXSAT to ground the symbols and solve Sudoku. They also slightly boost performance by using an additional linear "proofreading" layer, with a final ungrounded performance of 64.8% + 3.0%. We train improved SATNet from (Topan et al.) (021) using the harder visual Sudoku dataset RRN-V (9k/1k), and it performs poorly, getting 0% whole board accuracy. Unlike the SATNet improved (Topan et al., 202T), our model works out of the box on visual Sudoku without carefully adjusting the structure. Yet, it achieves 93.5% on the same dataset, as shown in Table 6 We also extended (Palm et al.] 2018) to include an image embedding layer for visual Sudoku, denoted as RRN*, Although it performs well on textual Sudoku, it fails at symbol grounding for the same boards as images, achieving no better than random performance.
As described in (Topan et al.) 2021). the SATNet paper (Wang et al. 2019) erroneously argued performance bound of 74.8% (0.99236.2) whole board accuracy based on the input classification accuracy of LeNet (99.2%) ) and the average number of givens (36.2). Our experiments confirm that this is wrong. We use the same CNN architecture that (Wang et al. 2019) uses, except that we change the output size to be the same as our embedding. Note that we achieved higher given cell accuracy with the same CNN 99.77% over 99.2%). Also, to the best of our knowledge, no simple CNN such as this achieves 99.77 79%77 accuracy MNIST if trained for each image separately. Following the argument above, 92.0% (= 06997736.2) would have been the theoretical maximum. However, our model achieves 93.5% whole board accuracy the SATNet's visual Sudoku dataset, which indicates that digit classification learning considers the relational information of Sudoku.
Interestingly, our model's 's solution board accuracies are consistently higher than whole board ac- curacies, meaning that even when the givens are misclassified, the empty cells are filled with the right values. This is because
model does not wait to solve after the classification of givens is completed; rather, the classification and solving are jointly done, which also explains why the accuracy of the givens is on par with more advanced vision models, which use additional techniques like data augmentation, ensembling, etc.
Figure 3 compares our models trained with the grounded and the ungrounded versions of the RRN-V dataset. With the grounded dataset, the input labels are quickly learned, with the model achieving 99.46% givens cell accuracy just after the first epoch, while the ungrounded version takes significantly
16

---

Published as a conference paper at ICLR 2023
Table 6: Results on visual Sudoku (ungrounded)
Mothod
Dataset (#train#tcat) #givens
whole board acc.
solution board acc.
whole board acc.
solution cell acc.
givens
cell acc.
SATNet Wang al.
2019
SATNet- V (9k/Ik)
31-42
0%
11.2%
11.6%
SATNet
Topan
202
SATNet- V (9k/1k)
31:42
64.8%
98.4%
98.9%
RRN
Palm ot al
2018)
SATNet- V (9k/1k)
31-42
0%
11.56%
LIR32H+- (ours)
SATNet- (9k/1K)
31-42
93.5%
93.7%
99.55%
99.37%
99.77%
SATNet
Wang et al.
2019
RRN-V V (9L/1K)
17:34
U%
11.63%
12.70%
SATNe1*
Topan al.
RRN (9k/1)
17:34
31.08%:
74.03%
RRN
(Palm al.
2018
RRN-V (9k/1)
17-34
0%
11.69%
LIR32H4-V (ours)
RRN-V (9k/1k)
17-34
74.8%
75.5%
94, 66.6
92.49%
99.36%
LIR32H8-V (ours)
RRN-V (180k/18K)
17-34
89.52%
89,56
97.50%
96.64%
99.36%
SATNet indicates the altered SeT from Tooan at 2021] and RRN indicates RRN with an image embedding layer for visual Sudoku
computiiliity. Givens well accuracy refers the per clasilication accuracy the given digits. solution cell accuracy refers
per-cell
accuracy of solution cells (initially empty). For solution board accurncy. board is counted as correct when all solution cells are correct. Whole beard cell accuracy refers counted as correct when all givens and empty cells are correct.
combined per-cell accuracy of both given and solution cells. For whole board accuracy, a board
longer, achieving 99.36% after 143 epochs. The grounded dataset appears help improve the whole board accuracy at first but converges at a lower solution board accuracy and whole board accuracy than the model trained with the ungrounded dataset. With the ungrounded dataset, the model starts to learn the givens and solutions at the same time, at around 85 epochs. This indicates that digit classification is being jointly learned during the solving process. However, as shown in Figure 3 (left), the model has a higher solution board accuracy than the whole board accuracy. This behavior is not surprising since it is enough to solve the non-given cells by just having a sufficient embedding of the given cells without classifying them. What is more interesting is that even though the model trained on the ungrounded dataset has no access to classification labels, it still learns to classify over 99% of the givens. The large oscillations of whole board accuracy for the model trained on the unground dataset due to classification errors, mostly due a single given digit being misrecognized. The graph also shows that for the ungrounded version, the solution board accuracy is consistently higher than the whole board accuracy, meaning that the unground version could still solve correctly even when the classification of input digits is wrong. On the other hand, for the model learned with the grounded dataset, the solution board accuracy overlaps with the whole board accuracy, implying a dependency between the solution board accuracy and givens/classification cell accuracy. The difference in the final whole-board board accuracy between grounded and ungrounded is because the grounded version must optimize the classification of the input symbols while the ungrounded version does not.
D MORE DETAILS ABOUT OTHER EXPERIMENTS
D.1 SHORTEST PATHI
Shortest Path in CSP. A shortest path problem can be viewed CSP where X (noder. node edgel..............e.........e.. edgee, denotes all m nodes and n edges in a graph; D = (DI,,..., (D,,...,DD++)) } } and D; (FALSE, TRUE); and C is the set of constraints specifying the two end nodes in the graph and that "the selected edges form a path between the end nodes with a minimum length". The goal is to find solution of this CSP, which represents the solution of the shortest path problem. Here, node; = TRUE (or edge; = TRUE resp.) represents that node (or edge i resp.) is in the shortest path. Let n1, n2 E (1...., m) denote the indices of the 2 end nodes. C contains constraints noden, = TRUE and noden, = TRUE the following constraint for the end nodes E {ni, n2).
Kedgea TRUE edgeæ = TRUE]| =
(6)
and the following constraint for non-end nodes i E m......m]]] \ (mi, from the label).
in the shortest path (given
Medgen1 TRUE ..., TRUE,..,,ddeeu = TRUE]| 2
where (edge,1.... .... ) are the edges connected to node i in the graph. The first constraint says that "each end node should connect to exactly edge in the path" and the second constraint says that "each non-end node in the path should connect exactly 2 edges in the path".
Dataset. We use the shortest path dataset SP4 from (Xu et al. 2018) to illustrate our method where each graph is x 4 grid with 16 nodes and 24 edges. SP4 has 1610 data instances and,
17

---

Published as a conference paper at ICLR 2023
as in (Xu et al. 2018 we split the dataset into 60%/20%/20% training/test/vliidtttie examples. In addition, we created a more challenging dataset SP12 where each graph is 12 12 grid with m 144 nodes and n 264 edges. SP12 has 22k data instances, split into 20k/Ik/Ik training/test/validatto examples. In each problem, two end nodes are randomly picked up, and R. removed to increase difficulty. A labeled data instance is (t, 1) where t E {0, 1 such that & = denotes "node is terminal node" when I m, and denotes "edge "i mm' is not removed" when ? > m; and E {0,1}" such that 4 = denotes "edge i in the shortest path."
3 edges are randomly
Loss
e0ge1 = True
edge1 False
Recurrnt Transfomeer (L1R322)
...
Token
Rosition Embedding Leyer
0 0000 1 011 100000000 3 3833822333233332222
node1
n 6 edge1
edge24
Figure 11: The representation used for the shortest path.
Figure 11 shows how Recurrent Transformer used to solve the shortest path problem in a 4 x 4 grid with 16 nodes and 24 edges. The information given for each logical variable node; (1...., 16)) is a single digit or 0 denoting that node is an end node or not. The given information for edge; (i E {1, (1..... 24)) is single digit 2 or 3 denoting that the edge i is removed not. Given NN output (r.)) TR. 10x2 for 40 logical variables, we construct the vector R21 such that 0; = X(rd) 1 denoting the probabilities of edge, TRUE for {l...., , 24). Let I e {0, 1 denote the label, i... 4 = 1 iff edge i is in the shortest path. The cross-entropy loss is defined on and I.
For the optional constraint loss, let M be the matrix in {0, 1) [0.1]16x24 16x624 such that M., - 1 iff node i is connected with edge j in the graph. Let c E 10,1, 4] be M L. Intuitively, c, denotes the number of edges in the shortest path containing node and e; >> 0 means that node is in the shortest path. Then, constraints (6) and 77 can be encoded as follows:
pptth (ontti(X((r (x
Σ
(fu
SE (
Σ
(less x 41 (M, + u)).
(E. 16
where the non-zers values in M1. ② E R2 are the probabilities of edge, TRUE for all edge that contains node
Table 7: Constraint accuracy on SP4 test data for the shortest path problem
Method
Constraint accuracy
Path
No removed edges
Shortest path
MLP
28.3%
32.9%
23.0%
MLP- + Semantic Loss (uu et al. 2018
69.9%
MI.P + NeurASP YYang et al. 2020)
96.6%
36.3%
33.2%
LIR32 (ours)
84.5%
100%
83.5%
L1R32 Lpath (ours)
91.9%
100%
91.0%
Table 7 compares the constraint accuracy achieved by (i) the bascline Multi-Layer Perceptron (MLP) introduced in (Xu et al. 2018) for the shortest path problem, (ii) the NeurASP method that encodes a path constraint to help train the MLP, (iii our Recurrent Transformer (LIR32), and (iv) the same Recurrent Transformer enhanced by the constraint loss Lpath- The constraint accuracy are the percentage of the predictions that (i) form valid path between end nodes, or (ii) do not include
18

---

Published as a conference paper at ICLR 2023
removed edges. or (iii) form shortest path between end nodes. Table shows that Recurrent Transformer significantly outperforms the baseline MLP. Besides, the constraint loss ppat further improves the accuracy of the same Recurrent Transformer for predicting valid path (or shortest path resp.) from 84.5% (or 83.5%) to 91.9% (or 91.0%).
Furthermore, we applied the same LIR32 model to the more challenging SP12 dataset. After 2,000 epochs of training, we achieved 72.3% accuracy when trained with cross-entropy loss only and 76.0% when trained with both cross-entropy loss and constraint loss Lpath-
D.2 NONOGRAMS
is game consisting of an initially empty N x grid representing a binary image, where each cell must have value of 0 or Each and column have constraints that must be satisfied to complete the image successfully. constraint for a row/column is a list of numbers, where each number corresponds to contiguous blocks of cells for row/column. We created two datasets for 7x7 and 15x15 grids, each having 9k/1k training/test split. We use the same Recurrent Transformer model as in previous experiments. sample N N grid input as N22 long sequence, where each element is concatenated representation of the row and column constraints associated with the element. For example, for 15x15 grids, a given cell with column constraint [1,7,4] and row constraint [2,2,4,1] would have corresponding sequence element of the concatenation of the two constraint vectors 1,7,1 and [0,2,2,4,1] (assuming the maximum constraint length 5). With this simple input encoding only, our Recurrent Transformer L L1R16H4 achieved 97.5% test accuracy on 7x7 grids and 78.3% test accuracy on 15x15 grids.
Nonogram
E CODE & DATASETS
Our Recurrent Transformer implementation is based on Andrej Karpathy's minGPT repository under MIT license. We extend minGPT (a smaller version of GPT-3) to allow full attention, add recurrences, apply additional losses, and alter embeddings.
E.I DATASET CREATED BY OTHERS
SATNet and SATNet-V Datasets,
The SATNet and SATNet-V datasets from SATNet (Wang 2019) repository (attps://githun cotp/ocuaaac//b SATNet) under MIT license.
ct al.
RRN Dataset. The RRN dataset is from Recurrent Relational Networks (all et al. 2018 repository (https: / hhb...t.t...... where no license information is provided.
networks)
MNIST. We use MNIST images (LeCun et al., 1998) (ht:p://yann. lewun.eennnncmmm coccunccom//xbb/..// mnist/), ) which are available under the Creative Commons Attribution-Saare Alike 3.0 license.
SP4. We use 4 shortest path grids from (Xu et al. 2018 (https://github) com/ UCLA StarAI/Semanttiata Losss, where no license information is provided.
E.2 DATASETS CREATED BY Us
RRN-V. The RRN-V dataset is created using the RRN dataset and MNIST images, similar to the way how SATNet- V dataset was created in SATNet repository. We construct the visual versions of RRN training/test datasets in which each board cell is represented by a randomly selected MNIST image.
16x16 Sudoku. We generate 16x16 Sudoku boards using the generator here: htttp::/sudok
smike. ru ww/hexsudkku htm, where no license is found. Though "medium" boards are actually labeled "hard" in their program, we label them "medium" since baseline performance is very high, and the percentage of givens is not low relative to the hardest 9x9 Sudoku hardest problems (1 (17-givens,
21 % of board).
19

---

Published as a conference paper at ICLR 2023
Nonograms. For Nonograms dataset, generate grids using the program "pattern.exe", avail- able under the MIT license available here: wttp///wwwc.......////// http:://www..ccaa...eeeeeeeeneee gww.nendeeeeeddddeo.o..o org. ragtattham/pure pttpaaammpuzieesss
SP12. We generate 12 x 12 shortest path grids using the answer set solver CLINGO
F
EXPERIMENTAL DETAILS
COMPUTING
All of our experiments were done on Ubuntu 18.04.2 LTS with two 10-cores CPU Intel(R) Xeon(R) CPU E5-2640 v4 @ 2.40GHz and four GP104 [GeForce GTX 1080].
F.2 TRAINING DETAILS
We used fixed random seed 0 for all experiments. The values of the weights and of the constraint losses Lradoku and Lattention are selected from 0.1, 0.5, 1 to achieve the highest training accuracy.
Textual Sudoku. For the weights (a, B) of the constraint losses Landoka and Lattention we used (0, (0, 1), (1, and (0.5, 0.5) in the 4 textual Sudoku experiments in Table 2 The model structure and hyperparameters are shown in Table g
Table 8: Model Structure and Hyperparameters for Textual Sudoku Experiments
Dataset
SATNET.RN (9k/Ik)
RRN (180k/(10k/1k))
Model Structure
Value
Value
Number of attention heads
Number layers
Number of recurrences (training/inference)
32/64
32/64
Embedding dimension
128
256
Token Embedder
Linear
Linear
Sequence length
81
81
Hyperparameter
Value
Value
Batch size
16
16
Learning rate Dropout
6e-4
6e-5
0.1
visual Sudoku. For the weights (a. (3) of the constraint losses L.uuoku and Lattention we used (0,0), (0, 0.1), (1, and (1, 0.1) in the 4 visual Sudoku experiments in Table The model structure and hyperparameters are shown in Table 9
16x16 Sudoku. The model structure and hyperparameters used for 16x16 Sudoku experiments
shown in Table I0
Shortest Path. The model structure and hyperparameters used for shortest path experiments shown in Table
MNIST Mapping. The model structure and hyperparameters used for MNIST Mapping experiments are shown Table
Nonograms. A sample 7x7 Nonogram grid and solution is shown in Figure 12
The model structure and hyperparameters used for Nonograms experiments are shown in Table I3
20

---

Published as a conference paper at ICLR 2023
Table Model Structure and Hyperparameters for visual Sudoku Experiments
Model Structure
Value
Number of attention heads
Number layers
Number recurrences (training/interencc))
32/64
Embedding dimension
128
Token Embedder
CNN
Sequence length
81
Hyperparameter
Value
Batch size
16
Learning rate
6e-4
Dropout
0.1
Table 10: Model Structure and Hyperparameters for 16x16 Sudoku Experiments
Model Structure
Value
Number of attention heads
8
Number of layers
Number of recurrences (training/inference)
32/64
Embedding dimension
256
Token Embedder
Linear Embedding
Sequence length
256
Hyperparameter
Value
Batch size
24
Learning rate
6e-4
Dropout
0.1
Table 11: Model Structure and Hyperparameters for Shortest Path Experiments
Dataset
4x4 (10k/2k)
12x12 (20k/1k)
Model Structure
Value
Value
Number of attention heads
4
Number of layers
Number recurrences (training/inference)
32/64
32/64
Embedding dimension
128
128
Token Embedder
Linear
Linear
Sequence length
40
408
Hyperparameter
Value
Value
Batch size
128
32
Learning rate
6e-4
6e-4
Dropout
0.1
0.1
Table 12: Model Structure and Hyperparameters for MNIST Mapping Experiments
Model Structure
Value
Number of attention heads
Number layers
Number recurrences (training/inferencc)
32/32
Embedding dimension
128
Token Embedder
CNN
Sequence length
Hyperparameter
Value
Batch size
256
Learning rate
6e-4
Dropout
0.1
21

---

Published as a conference paper at ICLR 2023
3 3
4
3
3
3
3
3
1
3
1
1
3
3
3
Figure 12: A sample 7x7 Nonogram grid (left) along with its solution (right).
Table 13: Model Structure and Hyperparameters for Nonograms Experiments
Model Structure
Value
Number of attention heads
Number of layers
Number of recurrences (training/inferencce)
16/32
Embedding dimension
128,320 (7x7.15x15)
Token Embedder
Linear Embedding
Sequence length
49,225 (7x7,15x15)
Hyperparameter
Value
Batch size
16
Learning rate
6e-4
Dropout
22


Reviews:
[{"review_id": "WzND7537RQ", "reviewer": "Reviewer_V9ce", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a recurrent architecture using Transformers to solve instances of a Constraint Satisfaction Problem with unknown constraints.  Weight sharing between the recurrent transformer layers allows it to create a much deeper network, which is required for solving combinatorial problems like sudoku. It also adapts the formulation of CL-STE (Yang et al 2022) to convert cardinality constraints on Boolean variables to a loss function on the probabilities of those Boolean variables being true. It experiments on symbolic as well as visual sudokus and achieves state-of-the-art results on ‘ungrounded-visual sudoku’ in which output symbols for only the empty cells are given in the training data.", "summary_of_the_review": "Overall, I like the paper for its clever use of existing ideas for demonstrating the effectiveness of transformers in learning constraints and solving combinatorial problems.  The experimentation is very thorough and extensive. \nThey achieve state-of-the-art performance on ungrounded visual sudoku and beat the baseline by a huge margin.\n\n\nQuestion for the authors:  \n1.  For 16 x 16 sudokus, are the experiments on textual, or ungrounded visual sudokus? I couldn’t find this detail in the paper.\n2. Table 1, L1R32H4 on RRN-V achieves 74.8% board accuracy. Is this using the constraint loss terms? Why don't we have this number in Table 2? \n3. Did you try to train RRN with the constraint loss terms? I would encourage you to do so and report it in the paper.\n4. \"As RRN was not designed for Visual Sudoku...\" (Pg 7): this claim is not true. Just because RRN authors didn't experiment with visual sudoku, it doesn't imply that RRN wasn't designed for it. As you have demonstrated, RRN can be easily plugged in as a reasoning component in a neural architecture.\n5. Is it possible to extend transformers architecture to learn first-order rules instead of grounded CSPs, like NLM (Dong et al 2019) does? Specifically, can we extend recurrent transformers to train using 9 x 9 sudokus, but test on 16 x 16, like (Nandwani et al 2022) extend RRNs to do so? Given that positional embeddings are critical for training transformers, you may no longer be able to use fixed positional embeddings and may have to try something like ALiBi (Pres et al 2021), or relative positional embeddings (Shaw et al 2018).\n\n[Dong et al 2019] Neural Logic Machines\n[Nandwani et al 2022] Neural Models for Output-Space Invariance in Combinatorial Problems\n[Shaw et al 2018] Self-Attention with Relative Position Representations\n", "strength_and_weaknesses": "As the authors have pointed out, the idea of recurrence in Transformers is not novel, but they have been able to successfully apply it to learn the constraints of a CSP. \n\nThe idea of computing loss using the output of every recurrent step has already been used to train RRNs. \n\nAlso, there is a lot of work on using Soft Logic to convert constraints on discrete symbols to equivalent constraints on the symbols’ probabilities computed by a neural network. For example, see Li et al. 2019.  Some of the formulations may give a similar loss term as the proposed constraint loss.\n\nThe task is to solve CSP by implicitly learning the underlying constraints in the network’s weights, but on the other hand, the constraint loss term assumes explicit knowledge of the same unknown constraints.  Though I agree that it is not clear how the knowledge of rules can be used with the ungrounded datasets, but for textual sudokus, if we know the constraints, we can create unlimited training data by using a symbolic solver. Maybe the authors should clarify this in the paper.  Also, the paper points out (almost criticizes) at a couple of places that RRN uses additional knowledge of which variables are allowed to interact, but the proposed constraint loss term uses almost similar knowledge. \n\nHaving said that, the paper does a good job of bringing together all of these ideas and proposing architecture for solving combinatorial problems.\n\nIt archives s-o-t-a performance on difficult ungrounded visual sudoku datasets, beating the baseline by a huge margin. \n\nThe authors have done extensive analysis and ablations to demonstrate the effectiveness and workings of the proposed approach.\n\n\n[Li et al 2019] A Logic-Driven Framework for Consistency of Neural Models. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "UPaC3q8rKw", "reviewer": "Reviewer_SH5d", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In a constraint satisfaction problem (CSP), we are given a set of variables and a set of constraints. Each variable takes values in some discrete domain, and each constraint specifies the allowed combinations of values for some list of variables. The problem is to find an assignment of variables to values that satisfies all constraints. In this setting, the aim of this paper is to handle CSP instances using recurrent transformers. The overall architecture is defined using self-attention blocks, recurrent steps, and self-attention heads. Constraints can be injected using the CL-STE technique. Experiments are performed on visual 9x9 and 16x16 Sudoku tasks, shortest path problems, MNIST Mappings, and Nonogram puzzles.   \n", "summary_of_the_review": "To sum up, the main message of this paper is that recurrent transformers are amenable to “some” CSP tasks, with good performances in comparison with other neural architectures. Yet, I am not convinced that the paper can be accepted in its current state. Besides clarity issues, one important weakness is the lack of comparisons with standard solvers on various classical CSPs. Another weakness is the need for dedicated knowledge in order to adjust hyper-parameters and to inject constraints in the model. \n", "strength_and_weaknesses": "As we know, constraint satisfaction problems have been a subject of extensive research for almost fifty years in AI. Nowadays, modern constraint solvers are able to efficiently solve a wide variety of constraint satisfaction tasks. So, the key question here is: why do we need another neural (or neuro-symbolic) architecture? \n\nI would say that if the constraint satisfaction task involves some sub-symbolic components (images, etc.) then the use of a neural architecture is indeed relevant. To this very point, the experimental results reported in the paper indicate that recurrent transformers can handle visual Sudoku tasks in an end-to-end manner, which is a significant improvement with respect to existing neural models, such as RRN and SATNet. \n    \nOn the other hand, for most constraint satisfaction tasks, the problem is symbolic in nature: it is defined using a set of discrete variables, a set of discrete domains, and a hypergraph of constraints. So, for those classical CSPs, there is no real need of using recurrent transformers, **unless they are in position to outperform standard solvers.**  From this perspective, the experiments should also include a comparison with standard solvers (e.g. FlatZinc, GeCode, Ace, etc.) on various CSP instances. Note here that the Shortest Path problem is easy (the problem is in P); I would recommend making comparisons on NP-hard tasks, such as, for example, resource allocation, scheduling or planning problems.\n\nBeyond that, it seems that recurrent transformers require a lot of tuning in order to solve CSPs. Notably, the overall architecture involves up to 10 hyper-parameters, including the number of recurrences, the number of layers, the number of allocation heads, etc. Although recurrent transformers can learn to solve CSP instances using only labeled instances, their performance can be significantly improved by injecting logical constraints in the training objective (Sections 3.3 & 4.2). Yet here, we need to carefully design an appropriate loss function for each constraint type, which essentially means that the overall architecture is dedicated to the task at hand. \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "OPCO6wZozr", "reviewer": "Reviewer_KSwb", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes an architecture for solving CSPs based on a transformer network. The transformer makes multiple passes over the inputs, keeping information across different passes in the form of a recurrent state. The network is also augmented with a constraint loss that injects problem knowledge into the training process. The results are evaluated on visual Sudoku as well as other benchmarks showing substantially improved results. ", "summary_of_the_review": "An application paper where known techniques are combined to yield substantial improvements over SOTA. Low novelty is somewhat offset by results, so there is an argument that this should be published.", "strength_and_weaknesses": "Strengths:\n* the presented architecture is fairly generic and applicable to many different types of input and problem structures;\n* the results show substantial improvements over existing algorithms;\n* generally well-written and reasonably evaluated;\n\nWeaknesses:\n* the novelty is not particularly high;", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Gp9RsDSQfLv", "reviewer": "Reviewer_wMfd", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors consider the problem of learning to solve constraint satisfaction problems. This entails finding values of a set of variables that satisfy given constraints. The authors propose using a transformer model, extended with recurrence, to perform this variable assignment.\n\nExisting work has shown that transformers produce subpar performance on constraint reasoning tasks, such as Sudoku. The authors incorporate recurrence into transformers to be able to successfully apply them to CSPs. Additionally, the authors add an explicit constraint loss to all recurrent layers.", "summary_of_the_review": "My impression is that the authors do not fully understand the architecture they have built or why it performs the way it does. It seems to me that they have simply encoded the logical constraints of the domain into the architecture of the network itself. I don't think the recurrence has anything to do with the improved performance of the system.", "strength_and_weaknesses": "I am confused about what is gained by adding recurrence to a transformer model. Large language models prior to transformers consisted of recurrent networks of various architectures that included attentional mechanisms, and can thus be described as recurrent transformers.\n\nIn my opinion, much of the gain found by the authors is likely due to the explicit constraint loss added to the intermediate layers, or due to injecting the logical constraints. In fact, it seems that the constraint loss on attention does a lot of the work of encoding the problem directly into the computation graph of the transformer.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster