Multi-Label Prediction as Learned Constraint Satisfaction

Many classification problems ask a model to output a set of labels at once, for example every object in a photo or every disease in a chest X-ray. The labels depend on each other. A tennis racket usually means a person is present. A child category in a taxonomy requires its parent. Some findings rarely co-occur. Current methods handle these dependencies in one of two ways, and each has a known weakness. Graph networks over a label-to-label co-occurrence matrix learn soft correlations, but those correlations are fixed for the whole dataset, so the models tend to predict a label just because its usual companion is present. Logic layers enforce hard rules exactly, but they cannot express soft tendencies. Neither family represents rules that involve three or more labels at once, and neither checks whether a dependency actually holds for the image being classified.

This note proposes treating each image's label set as a small constraint-satisfaction problem and solving it with the kind of neural network that combinatorial solvers already use. In those solvers the problem is drawn as a graph with three kinds of nodes: variables, the values each variable can take, and the constraints linking them. The edges carry flags that record whether the current partial answer satisfies each constraint. In our version the labels are the variables, present and absent are the values, and both hard rules and mined soft rules of any arity are constraint nodes. The network repeatedly proposes a full label assignment, checks which constraints that assignment violates for this particular image, and revises. Hard rules are finally enforced by pruning infeasible values, so the output is guaranteed to be consistent. Soft rules only influence the answer when the image's own evidence makes them relevant.

Core Claim

The ingredient that is genuinely new for multi-label learning is the per-image, assignment-dependent satisfaction signal on constraint edges. It is not "a graph over labels." In ANYCSP (Tönshoff et al., 2023), a graph network operates on a variable–value–constraint graph whose constraint-to-value edges are relabeled at every step according to whether the sampled assignment satisfies each constraint. This lets one trained network search arbitrary problem instances, and models trained on 100-variable instances scale to 10,000. SeaPearl (Chalumeau et al., 2021; Marty et al., 2025) pairs the same three-part encoding with solver propagation that deletes infeasible values. Both stay inside symbolic optimization benchmarks and never touch perceptual inputs.

We claim that bringing this machinery to multi-label recognition does three things. It lets dependencies of arity three or more be represented sparsely. It makes the dependencies instance-conditioned, so a co-occurrence rule exerts pressure only when the current evidence-driven assignment actually engages it. It unifies hard and soft rules in one network, which neither the co-occurrence networks nor the logic layers do.

We are explicit about one point. With binary labels, the two value nodes per label carry little information beyond a single logit, so the three-part structure is partly a convenience. The claim must therefore stand or fall on the satisfaction flags and the higher-order constraints, and the ablations below are designed to test exactly that.

Relation to Prior Work

Some prior work motivates the proposal. ML-GCN (Chen et al., 2019) runs a graph convolution over a static matrix of conditional label probabilities to produce classifier weights. KSSNet (Wang et al., 2020) superimposes a ConceptNet knowledge graph on that matrix and injects label representations into intermediate CNN layers. Both gain substantially over independent classifiers, and both use one global, pairwise, label-only graph.

Other work constrains the design. ML-VPT (Ma et al., 2026) reports that co-occurrence modeling over-infers correlated labels. It responds by spectrally splitting labels into correlative and discriminative groups that are routed to separate prompts and experts. We take that result as a warning that any soft dependency must be gated by instance evidence. Our response differs: instead of partitioning labels offline, we let every constraint switch on or off per image through the satisfaction flags. FACT (Chen et al., 2026) matches quantized visual tokens to disease anchors learned over a comorbidity graph. It argues that medical labels resist rigid boundaries, which supports keeping soft constraints alongside hard ones.

The hard-constraint side supplies parts of the method. C-HMCNN and CCN (Giunchiglia and Lukasiewicz, 2021) guarantee hierarchical and propositional consistency through a feed-forward max/min layer and a matching loss. They show that building constraints into training beats fixing predictions afterward, because the constraints act as extra supervision. LogicMP (Xu et al., 2024) performs mean-field inference over first-order rule groundings as parallel einsums on the GPU. LogicMP is the closest relative, since mean-field over rule factors is itself message passing on a variable–factor graph. It differs from our proposal in three ways. Its rules have fixed hand-set potentials rather than learned constraint embeddings. It has no signal that depends on a sampled assignment. It does not discover rules from data. We reuse its lesson that constraint message passing must be batched as dense tensor contractions to stay cheap.

Research Program

The model starts with a standard backbone, such as ResNet-101 at 448 pixels to match the reported baselines, and a ViT for modern comparisons. Each label variable node is initialized by cross-attention from a label embedding to the image's patch features. Each label has a present node and an absent node.

Constraint nodes come from three sources. Hard rules come from the dataset's hierarchy or its logical constraint set. Soft implication and co-presence rules of arity two to four are mined as frequent label sets with high lift. Soft exclusion rules are mined as label sets with near-zero co-occurrence despite high individual frequency. Each constraint node carries a learned type embedding (implication, exclusion, or at-least-one) and its empirical strength.

Constraint nodes connect to the value nodes of the labels they mention. The flag on each such edge records whether choosing that value would satisfy the constraint, given the other labels' current values. This follows ANYCSP's construction directly.

Inference runs for T rounds. Each round performs heterogeneous message passing among the three node types and reads out a present-probability per label. It then samples or thresholds an assignment and recomputes the edge flags. After the last round, hard constraints are applied by forward-checking: values made infeasible by hard rules are masked, and the remaining choices are decoded greedily. This guarantees that every output satisfies the hard rules.

Training is supervised. Binary cross-entropy is applied at every round, and CCN's constraint loss is applied to the hard rules. Because the flags are inputs rather than outputs, they need no gradient. During training, flags are computed from assignments sampled from the model's own previous-round predictions, with some noise, so the network learns to repair its own mistakes rather than only gold-adjacent ones.

Edge count scales with the summed arity of the constraints, not with the square of the label count. This is what makes the 365-label Objects365 setting tractable without the dense matrices that ML-GCN-style models require.

Beyond accuracy, the program has two analyses. The first measures over-inference on out-of-context images. The second tests whether constraints added only at test time are respected and helpful without retraining. This mirrors ANYCSP's instance-agnostic generalization, transferred from new problem instances to new rules.

Baselines

The naive reference point is binary relevance: the same backbone with independent sigmoid outputs and binary cross-entropy, trained with the same schedule and augmentation. Chen et al., 2019 reports 77.1% mAP for the SRN baseline on MS-COCO. Wang et al., 2020 reports KSSNet 6.4 points above plain ResNet-101. We rerun binary relevance ourselves rather than relying on those figures.

The strongest reported co-occurrence methods are KSSNet, at 83.7% mAP on MS-COCO and 44.9% mAP on Charades, and ML-GCN, at 83.0% mAP on MS-COCO and 94.0% mAP on VOC07 (Chen et al., 2019). These are the strongest competitors on accuracy because they model the same dependencies we target and share our ResNet-101 setting. We compare against the published numbers at matching resolution and also reproduce both methods under our training budget.

ML-VPT is the strongest method aimed at over-inference specifically. We found no reported per-backbone result on Lacuna for ML-VPT on any benchmark, only relative gains of 1.2 to 8.7 points. We therefore rerun it on a shared ViT backbone with an equal tuning budget.

On hard-constraint benchmarks, the strongest baseline is CCN, which Giunchiglia and Lukasiewicz, 2021 report as best on 17 of 20 hierarchical datasets. No per-dataset number is reported on Lacuna, so we rerun CCN with its released configuration on the same splits. We also build a LogicMP layer fed the identical mined soft rules and hard rules as a fair comparison of inference mechanisms. No reported result was found on Lacuna for LogicMP on multi-label image benchmarks.

The ablation that isolates the key ingredient freezes the edge flags at their initial values. This turns the model into a static variable–factor graph network over the same constraints. Two further ablations restrict constraints to arity two and fold the value nodes into a single logit. Every variant gets the same backbone, epochs, and hyperparameter search of equal trial count.

Beating the field means three things. On COCO and VG256, mAP must at least match the reproduced KSSNet and ML-GCN. On the out-of-context split, the false-positive rate on partner labels must fall significantly below theirs. On the hierarchical and logical benchmarks, the model must match CCN while also improving on the soft-dependency datasets.

Why not just…?

Why not just use independent classifiers on a strong modern backbone? Large pretrained backbones may already absorb most dependency information, which would shrink the reported 6-point gaps that were measured on ResNet-101. This is a real threat. We test it by reporting all gains on both ResNet-101 and a ViT. If the gap over binary relevance on the ViT falls below one point everywhere except the out-of-context and hard-constraint evaluations, the contribution narrows to consistency and robustness, and we will report it as such.

Why not just use ML-GCN or KSSNet? Their single static pairwise matrix applies the same pressure to every image. ML-VPT (Ma et al., 2026) documents that this causes over-inference, and such models cannot guarantee hard-rule consistency. The out-of-context COCO split described below measures the first failure directly. Coherence-violation rates on the hierarchical datasets measure the second.

Why not just put a CCN layer or a LogicMP layer on top of a backbone? CCN enforces hard rules but ignores soft ones. LogicMP handles both but with fixed potentials and no assignment-dependent feedback. The frozen-flag ablation together with the matched LogicMP baseline settles whether the iterative satisfaction signal matters. If LogicMP with mined rules matches us, the three-part representation adds nothing, and we will say so.

Why not just let a transformer attend over label tokens? Self-attention among label queries can learn dense, instance-dependent dependencies with no explicit constraints at all. It is the most serious alternative, and we found no paper in the file that reports it on these benchmarks. We include it as a matched baseline. Our expected advantages are guaranteed hard-rule consistency and the ability to accept new rules at test time, since attention offers neither. On raw mAP it may tie us.

Proposed Experiments

The accuracy study covers MS-COCO, VOC07, NUS-WIDE, VG256, and Objects365, reporting mAP, per-class F1, and overall F1. Objects365 tests scaling to 365 labels.

The over-inference check builds an out-of-context subset of MS-COCO by selecting, for each of the top-lift label pairs, the test images containing one label but not the other. The metric is the false-positive rate on the absent partner. The model should beat ML-GCN and KSSNet here by a clear margin while staying no worse on the full test set. If it does not, the instance-conditioning claim fails.

The hard-plus-soft study uses the 20 hierarchical and 16 logically constrained datasets from Giunchiglia and Lukasiewicz, 2021. It reports their metrics alongside the fraction of outputs violating any rule, which should be zero for our model and for CCN.

The medical study runs on ODIR-5K and NIH-Chest and adds calibration error. Chen et al., 2026 report that FACT reduces calibration error on ODIR from 27.51% to 16.22% with a 2.92-point mAP gain. FACT is the comparison point there.

The decisive generalization test withholds half of the hard rules during training on the hierarchical datasets and inserts them only at inference. We measure whether violations drop to zero and accuracy rises without retraining.

Finally, we report wall-clock inference cost against binary relevance and ML-GCN across the number of rounds T. The method is worth adopting only if two to four rounds capture most of the gain at a small multiple of a linear head's cost.