REVIEW 3 major objections 5 minor 41 references
Improving Out-of-Distribution Detection with Markov Logic Networks
T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read The paper shows that adding a Markov logic network that scores inputs against weighted logical constraints over human-understandable concepts improves out-of-distribution detection across a range of existing detectors, backbones, and…
desk verdict A genuinely useful neuro-symbolic OOD method with a real but fixable error in the fusion formula; deserves reviewing. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The core mechanism is the MLN outlier score $D_M(x) = -\sum_i w_i \varphi_i(x)$, which sums the weights of all constraints satisfied by the input's semantic representation and negates the sum; this ranking is identical to using the full MLN probability because the partition function is constant across inputs. This score is combined with a base OOD detector by first converting the base score into a survival function $p_D(D(x)) = P(D(X) \ge D(x))$, estimated on in-distribution data with a generalized extreme value distribution, and then multiplying: $D'_M(x) = D_M(x) \times p_D(D(x))$. A greedy constraint-search algorithm (Alg. 2) builds a set of logical formulas by adding candidates that improve validation AUROC by at least a threshold $\delta_{\min}$, trading rule-set complexity against detection performance.
What would settle it
Run the GTSRB or CelebA concept classifiers on OOD images and measure their accuracy against human-provided semantic labels; if accuracy on OOD data is near chance while the MLN still improves detection, the claimed semantic signal is not doing the work. Alternatively, randomly permute the MLN's concept predictions during inference on OOD data while keeping the base detector fixed: if the combined AUROC stays the same, the semantic layer is irrelevant.
Extended reading notes
Core claim
The central claim is that an MLN-based semantic score, defined as the negative weighted sum of violated logical constraints over a low-dimensional, human-interpretable semantic representation, can be combined with any existing OOD detector to improve detection. The combination works by normalizing the base detector's scores with an estimated survival function and multiplying the normalized value by the MLN score. Experiments on GTSRB and CelebA show that the combined detector outperforms both the base detector and the standalone MLN, with AUROC gains on nearly every tested detector (for example, MLN+Mahalanobis on CelebA raises AUROC from 95.12 to 96.01 and cuts FPR95 by roughly 20 percent), and that a supervised variant that learns an in-distribution predicate yields further gains. The paper also claims that a greedy search over candidate constraints, using AUROC on a validation set as the selection criterion, discovers interpretable and effective rules, and that the MLN's constraint-based scores provide explainability because each violation contributes a traceable, weighted penalty.
Load-bearing premise
The neural networks used to interpret predicates and functions (such as color, shape, age, and gender) provide accurate semantic labels for both in-distribution and out-of-distribution inputs; the paper does not measure concept-classifier accuracy on OOD data, so if those classifiers fail on OOD inputs, the MLN's constraint violations would reflect model artifacts instead of genuine semantic anomalies.
Editorial extensions
If this is right
- If the central claim holds, any existing OOD detector can be upgraded by appending an MLN layer, and the upgrade yields consistent AUROC and FPR95 improvements without retraining the base detector.
- The semantic constraints provide a built-in explanation mechanism: when an input is flagged OOD, the specific violated rules and their weights tell a human which concepts were implausible.
- The greedy constraint search means that prior knowledge is not strictly required; useful, human-readable rules can be mined directly from a dataset with ID and OOD examples.
- The approach's modularity means that supervised outlier exposure can be added simply by learning an extra predicate, without altering the rest of the detection pipeline.
- Because the MLN score is cheap to evaluate (no partition function), the combined detector keeps inference overhead small even for large batch sizes.
Reading between the lines
- A natural extension would be to test whether the MLN layer helps most when the base detector is weak on semantically-grounded anomalies (e.g., a blue stop sign that still yields high softmax confidence); the paper's CelebA results suggest that detectors with poor baseline AUROC benefit the most, but this pattern is not stated explicitly.
- The failure case with Gaussian noise as the OOD source during constraint search hints that the semantic layer may add little when OOD inputs are completely uninterpretable; a reader could investigate whether the MLN is only useful when concept classifiers produce meaningful outputs on OOD data.
- The authors do not evaluate concept-classifier accuracy on OOD inputs; a testable prediction of the paper's own logic is that the MLN's contribution should vanish or become negative when the concept classifiers are systematically wrong on OOD data, because the constraint violations would then reflect classifier artifacts rather than genuine semantic anomalies.
- One could extend the framework to temporal or relational data by moving from unary predicates to multi-object predicates, which the paper explicitly leaves out, and test whether the same survival-function combination still holds.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes augmenting existing out-of-distribution (OOD) detectors with a Markov logic network (MLN) defined over human-interpretable concepts. A DNN-based interpretation maps each input to a semantic vector; the MLN assigns an outlier score as the negative weighted sum of violated logical constraints. This MLN score is then combined with a baseline detector by multiplying it with the survival function of the baseline score on in-distribution data. The authors also introduce a greedy constraint-search algorithm for automatically learning such logical constraints from data. Experiments on GTSRB and CelebA, with multiple detectors, backbones, ten random seeds, and several ablations, report consistent AUROC/FPR95 improvements over the baselines and moderate computational overhead.
Significance. If the claims hold, the paper makes a useful neuro-symbolic contribution to OOD detection by showing that semantic constraints over human-understandable concepts can complement purely representation-based detectors. The empirical study is extensive: ten seed replicates, multiple detectors and backbones, an open-source implementation, runtime measurements, and ablations covering constraint count, normalization family, parameter sharing, and the influence of the OOD source used during constraint search. The explicit discussion of potential bias in learned constraints is also a strength. However, the probabilistic justification of the fusion rule contains a mathematical error, and the reliability of the concept classifiers on OOD data is not assessed; these issues need to be resolved before the contribution can be fully credited.
major comments (3)
- [Section 3.2, Eq. (8)] The statement that omitting the partition function Z does not affect the overall ranking of outlier scores is incorrect for the product rule. Since pD(D(x)) varies across inputs, adding log Z to DM(x) before multiplication can change the ranking. For example, with log Z = 10, an ID input with DM = -2 and pD = 0.9 and an OOD input with DM = 2 and pD = 0.1 yield unnormalized product scores -1.8 and 0.2 (OOD ranked higher), while the normalized product scores are 7.2 and 1.2 (ID ranked higher). The omission of Z is benign for the standalone MLN ranking in Eq. (6), but not for the combined score in Eq. (8). The authors should either define the combination using the properly normalized MLN probability or explicitly present Eq. (8) as a heuristic and remove the invariance claim.
- [Section 3, 'Connecting DNNs and FOL Semantics'; Section 5] The DNNs that serve as the interpretation I for the logical predicates and functions are trained only on in-distribution data, but the paper does not measure or report their accuracy or calibration on OOD inputs. If these classifiers produce semantically meaningless labels for out-of-distribution images, the constraint violations detected by the MLN reflect classifier artifacts rather than genuine semantic anomalies, which would undermine the paper's explainability and 'semantic OOD' claims. This is a load-bearing gap because the method's mechanism depends on the semantic labels being meaningful for both ID and OOD inputs. Please report per-attribute accuracy or calibration on OOD test data, or provide systematic qualitative evidence beyond the few examples in Fig. 7, and discuss how interpretation errors propagate to the final score.
- [Section 4, Algorithm 2] The prose and the pseudocode for the greedy constraint search are not fully aligned. The text says a candidate is drawn from the 'remaining pool' and that the search requires only |T| evaluations, but Algorithm 2 iterates over all constraints in T without any removal of accepted constraints, and each loop calls 'Train detector with φ′ on Dtrain' without specifying how the MLN weights are set (e.g., optimized via Eq. (11) or simply kept at the initial value -1). The reader cannot tell whether the detector is retrained from scratch at each step, whether accepted constraints are excluded from later consideration, or what the actual computational cost is. This ambiguity affects the reproducibility of a central contribution and should be clarified by aligning the text with a precise search procedure.
minor comments (5)
- [Table 3] The table reports only point estimates without standard errors, despite the paper's emphasis on statistical replication; adding standard deviations or error bars would make the comparisons more informative.
- [Figure 4] The |φ| axis in Figure 4 appears garbled in the submitted version, with repeated digits that make the number of identified constraints impossible to read; the figure should be regenerated with a standard axis.
- [Eq. (7)] The survival function pD is defined as P(D(X) ≥ D(x)) over ID samples; please clarify whether this is estimated empirically on the validation set and how ties between scores are handled.
- [Section 5.4, 'Computational Overhead'] The runtime comparison would benefit from error bars or a confidence band, since the text states that inference time is averaged over 100 batches but no variability information is provided.
- [Section 3.1, Eq. (6)] The paper notes that weights can be negative, which would make a constraint violation decrease the score; however, the interpretation in terms of 'violation increases the score' is used throughout the text. It would be helpful to report whether the learned weights were always positive in practice and, if not, how negative weights should be interpreted.
Circularity Check
No significant circularity: the MLN weights are fit to ID data and the combined detector is evaluated on held-out OOD sources; self-citations are background and baseline comparisons, not load-bearing.
full rationale
The derivation chain is not circular. The MLN weights w in Eq. (11) are optimized on in-distribution training data only, and the standalone outlier score in Eq. (6) is the negative weighted constraint sum. The combined score in Eq. (8) multiplies this by a survival-function normalization of an existing detector, and the reported results are measured against held-out OOD sources. On GTSRB the constraints come from a priori traffic-sign domain knowledge; on CelebA the constraints are selected by validation AUROC on the Textures OOD set, and that OOD source is excluded from the reported evaluation. No fitted parameter is renamed as a prediction: the learned weights are ID likelihood parameters, and the constraint selection is an explicit model-selection step with separate validation and test sets. The self-citations to LogicOOD and PyTorch-OOD are used as baselines and background, not as an unverified premise on which the central claim rests. One non-circular correctness concern is that Section 3.2's claim that omitting the MLN partition function does not affect the overall ranking is mathematically questionable, because multiplying by the input-dependent survival function makes the omitted additive constant input-dependent in the product; however, this is a flaw in the fusion formula and not a reduction of the result to its inputs by construction. The empirical claims remain supported by external benchmarks and held-out evaluation.
Assumptions & free parameters
free parameters (5)
- MLN weights w =
learned via Eq. (11) on ID data
- GED parameters for p_D =
fitted to ID detector scores
- delta_min =
0.01 for CelebA
- Initial MLN weight =
-1
- Constraint set for GTSRB =
43 hand-crafted rules
assumptions (6)
- standard math MLN distribution over semantic space Z (Eq. 2) as defined by Richardson & Domingos (2006)
- domain assumption The semantic space Z is finite and small enough for exact partition function evaluation
- domain assumption Concept classifiers (interpretation I) are accurate on ID and OOD inputs
- domain assumption Outlier scores of baseline detectors follow a generalized extreme value distribution
- ad hoc to paper Product fusion of MLN score and normalized baseline score is an effective combination
- domain assumption Validation AUROC on an OOD dataset is a good proxy for generalization to unseen OOD sources
Cite this review
Pith. "Pith review of Improving Out-of-Distribution Detection with Markov Logic Networks." pith.science (2026). https://pith.science/paper/ZOOUTL6Z
@misc{pith2026250604241,
author = {Pith},
title = {Pith review of: Improving Out-of-Distribution Detection with Markov Logic Networks},
year = {2026},
howpublished = {\url{https://pith.science/paper/ZOOUTL6Z}},
note = {Machine review of arXiv:2506.04241}
}
read the original abstract
Out-of-distribution (OOD) detection is essential for ensuring the reliability of deep learning models operating in open-world scenarios. Current OOD detectors mainly rely on statistical models to identify unusual patterns in the latent representations of a deep neural network. This work proposes to augment existing OOD detectors with probabilistic reasoning, utilizing Markov logic networks (MLNs). MLNs connect first-order logic with probabilistic reasoning to assign probabilities to inputs based on weighted logical constraints defined over human-understandable concepts, which offers improved explainability. Through extensive experiments on multiple datasets, we demonstrate that MLNs can significantly enhance the performance of a wide range of existing OOD detectors while maintaining computational efficiency. Furthermore, we introduce a simple algorithm for learning logical constraints for OOD detection from a dataset and showcase its effectiveness.
Figures
Figures from the paper (3 more)
Reference graph
Works this paper leans on
-
[1]
write newline
" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...
-
[2]
write newline
" write newline "" before.all 'output.state := FUNCTION fin.entry add.period write newline FUNCTION new.block output.state before.all = 'skip after.block 'output.state := if FUNCTION new.sentence output.state after.block = 'skip output.state before.all = 'skip after.sentence 'output.state := if if FUNCTION not #0 #1 if FUNCTION and 'skip pop #0 if FUNCTIO...
-
[3]
Besold, T. R., d Avila Garcez, A., Bader, S., Bowman, H., Domingos, P., Hitzler, P., K \"u hnberger, K.-U., Lamb, L. C., Lima, P. M. V., de Penning, L., et al. Neural-symbolic learning and reasoning: A survey and interpretation 1. In Neuro-Symbolic Artificial Intelligence: The State of the Art, pp.\ 1--51. IOS press, 2021
work page 2021
-
[4]
Unreproducible research is reproducible
Bouthillier, X., Laurent, C., and Vincent, P. Unreproducible research is reproducible. In International Conference on Machine Learning, pp.\ 725--734, 2019
work page 2019
-
[5]
Describing textures in the wild
Cimpoi, M., Maji, S., Kokkinos, I., Mohamed, S., and Vedaldi, A. Describing textures in the wild. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp.\ 3606--3613, 2014
work page 2014
-
[6]
R., G \"u nther, M., and Boult, T
Dhamija, A. R., G \"u nther, M., and Boult, T. Reducing network agnostophobia. In Advances in Neural Information Processing Systems, pp.\ 9157--9168, 2018
work page 2018
-
[7]
Extremely simple activation shaping for out-of-distribution detection
Djurisic, A., Bozanic, N., Ashok, A., and Liu, R. Extremely simple activation shaping for out-of-distribution detection. International Conference on Learning Representations, 2023
work page 2023
-
[8]
An image is worth 16x16 words: Transformers for image recognition at scale
Dosovitskiy, A., Beyer, L., Kolesnikov, A., Weissenborn, D., Zhai, X., Unterthiner, T., Dehghani, M., Minderer, M., Heigold, G., Gelly, S., et al. An image is worth 16x16 words: Transformers for image recognition at scale. International Conference on Learning Representations, 2021
work page 2021
Show all 41 references
-
[9]
and Ghahramani, Z
Gal, Y. and Ghahramani, Z. Dropout as a B ayesian approximation: Representing model uncertainty in deep learning. In International Conference on Machine Learning, pp.\ 1050--1059. PMLR, 2016
2016
-
[10]
Deep residual learning for image recognition
He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learning for image recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp.\ 770--778, 2016
2016
-
[11]
Mask R-CNN
He, K., Gkioxari, G., Doll \'a r, P., and Girshick, R. Mask R-CNN . In Proceedings of the IEEE International Conference on Computer Vision, pp.\ 2961--2969, 2017
2017
-
[12]
and Gimpel, K
Hendrycks, D. and Gimpel, K. A baseline for detecting misclassified and out-of-distribution examples in neural networks. International Conference on Learning Representations, 2017
2017
-
[13]
Deep anomaly detection with outlier exposure
Hendrycks, D., Mazeika, M., and Dietterich, T. Deep anomaly detection with outlier exposure. In International Conference on Learning Representations, 2018
2018
-
[14]
Scaling out-of-distribution detection for real-world settings
Hendrycks, D., Basart, S., Mazeika, M., Mostajabi, M., Steinhardt, J., and Song, D. Scaling out-of-distribution detection for real-world settings. International Conference on Machine Learning, 2022
2022
-
[15]
PyTorch-OOD : A library for out-of-distribution detection based on PyTorch
Kirchheim, K., Filax, M., and Ortmeier, F. PyTorch-OOD : A library for out-of-distribution detection based on PyTorch . In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) Workshops, pp.\ 4351--4360, June 2022
2022
-
[16]
Out-of-distribution detection with logical reasoning
Kirchheim, K., Gonschorek, T., and Ortmeier, F. Out-of-distribution detection with logical reasoning. In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pp.\ 2122--2131, 2024
2024
-
[17]
Simple and scalable predictive uncertainty estimation using deep ensembles
Lakshminarayanan, B., Pritzel, A., and Blundell, C. Simple and scalable predictive uncertainty estimation using deep ensembles. In Advances in Neural Information Processing Systems, pp.\ 6402--6413, 2017
2017
-
[18]
Deep learning
LeCun, Y., Bengio, Y., and Hinton, G. Deep learning. Nature, 521 0 (7553): 0 436--444, 2015
2015
-
[19]
A simple unified framework for detecting out-of-distribution samples and adversarial attacks
Lee, K., Lee, K., Lee, H., and Shin, J. A simple unified framework for detecting out-of-distribution samples and adversarial attacks. Advances in Neural Information Processing Systems, 31, 2018
2018
-
[20]
R., and Hand, E
Lingenfelter, B., Davis, S. R., and Hand, E. M. A quantitative analysis of labeling issues in the CelebA dataset. In International Symposium on Visual Computing, pp.\ 129--141. Springer, 2022
2022
-
[21]
Energy-based out-of-distribution detection
Liu, W., Wang, X., Owens, J., and Li, Y. Energy-based out-of-distribution detection. Advances in Neural Information Processing Systems, 33, 2020
2020
-
[22]
Deep learning face attributes in the wild
Liu, Z., Luo, P., Wang, X., and Tang, X. Deep learning face attributes in the wild. In Proceedings of the IEEE International Conference on Computer Vision, pp.\ 3730--3738, 2015
2015
-
[23]
A convnet for the 2020s
Liu, Z., Mao, H., Wu, C.-Y., Feichtenhofer, C., Darrell, T., and Xie, S. A convnet for the 2020s. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp.\ 11976--11986, 2022
2022
-
[24]
and Hutter, F
Loshchilov, I. and Hutter, F. SGDR : Stochastic gradient descent with warm restarts. International Conference on Learning Representations, 2017
2017
-
[25]
Recent advances in ood detection: Problems and approaches
Lu, S., Wang, Y., Sheng, L., Zheng, A., He, L., and Liang, J. Recent advances in ood detection: Problems and approaches. arXiv preprint arXiv:2409.11884, 2024
2024 arXiv
-
[26]
Deep neural networks are easily fooled: High confidence predictions for unrecognizable images
Nguyen, A., Yosinski, J., and Clune, J. Deep neural networks are easily fooled: High confidence predictions for unrecognizable images. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp.\ 427--436, 2015
2015
-
[27]
and Domingos, P
Richardson, M. and Domingos, P. Markov logic networks. Machine Learning, 62 0 (1): 0 107--136, 2006
2006
-
[28]
U-Ne t: Convolutional networks for biomedical image segmentation
Ronneberger, O., Fischer, P., and Brox, T. U-Ne t: Convolutional networks for biomedical image segmentation. In Medical image computing and computer-assisted intervention: 18th international conference, Munich, Germany, October 5-9, 2015, proceedings, part III 18, pp.\ 234--24...
2015
-
[29]
Imagenet large scale visual recognition challenge
Russakovsky, O., Deng, J., Su, H., Krause, J., Satheesh, S., Ma, S., Huang, Z., Karpathy, A., Khosla, A., Bernstein, M., et al. Imagenet large scale visual recognition challenge. International Journal of Computer Vision, 115 0 (3): 0 211--252, 2015
2015
-
[30]
Deep learning in neural networks: An overview
Schmidhuber, J. Deep learning in neural networks: An overview. Neural Networks, 61: 0 85--117, 2015
2015
-
[31]
Stallkamp, J., Schlipsing, M., Salmen, J., and Igel, C. Man vs. computer: Benchmarking machine learning algorithms for traffic sign recognition. Neural Networks, 32: 0 323--332, 2012
2012
-
[32]
and Dinneen, M
Summers, C. and Dinneen, M. J. Nondeterminism and instability in neural network optimization. In International Conference on Machine Learning, pp.\ 9913--9922. PMLR, 2021
2021
-
[33]
and Li, Y
Sun, Y. and Li, Y. Dice: Leveraging sparsification for out-of-distribution detection. In European Conference on Computer Vision, pp.\ 691--708. Springer, 2022
2022
-
[34]
React: Out-of-distribution detection with rectified activations
Sun, Y., Guo, C., and Li, Y. React: Out-of-distribution detection with rectified activations. Advances in Neural Information Processing Systems, 34: 0 144--157, 2021
2021
-
[35]
The INaturalist species classification and detection dataset
Van Horn , G., Mac Aodha , O., Song, Y., Cui, Y., Sun, C., Shepard, A., Adam, H., Perona, P., and Belongie, S. The INaturalist species classification and detection dataset. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, June 2018
2018
-
[36]
Vim: Out-of-distribution with virtual-logit matching
Wang, H., Li, Z., Feng, L., and Zhang, W. Vim: Out-of-distribution with virtual-logit matching. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp.\ 4921--4930, 2022
2022
-
[37]
Generalized out-of-distribution detection: A survey
Yang, J., Zhou, K., Li, Y., and Liu, Z. Generalized out-of-distribution detection: A survey. International Journal of Computer Vision, 132 0 (12), 2024
2024
-
[38]
LSUN : Construction of a large-scale image dataset using deep learning with humans in the loop
Yu, F., Seff, A., Zhang, Y., Song, S., Funkhouser, T., and Xiao, J. LSUN : Construction of a large-scale image dataset using deep learning with humans in the loop. arXiv preprint arXiv:1506.03365, 2015
2015 arXiv
-
[39]
and Komodakis, N
Zagoruyko, S. and Komodakis, N. Wide residual networks. In British Machine Vision Conference 2016. British Machine Vision Association, 2016
2016
-
[40]
Out-of-distribution detection based on in-distribution data patterns memorization with modern hopfield energy
Zhang, J., Fu, Q., Chen, X., Du, L., Li, Z., Wang, G., Han, S., Zhang, D., et al. Out-of-distribution detection based on in-distribution data patterns memorization with modern hopfield energy. In The Eleventh International Conference on Learning Representations, 2022
2022
-
[41]
Places: A 10 million image database for scene recognition
Zhou, B., Lapedriza, A., Khosla, A., Oliva, A., and Torralba, A. Places: A 10 million image database for scene recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2017
2017
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.