# Certifiable Boolean Reasoning Is Universal arXiv: https://arxiv.org/abs/2602.05120 · HTML: https://mlsanity.com/paper/2602.05120/ ## Key facts - Cited by 2 papers in the map (data through 14 Oct 2026). - Placed in Reasoning benchmarks and evaluation, one of 17 directions in LLM reasoning. - Builds on 37 of its 66 references that are in the map. - First posted on arXiv 4 Feb 2026. ## Placed in - LLM reasoning / [Reasoning benchmarks and evaluation](https://mlsanity.com/lr/reasoning-benchmarks-and-evaluation/) ## Builds on (most cited first, 30 of 37) - [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022) - [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021) - [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022) - [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022) - [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021) - [Reflexion: Language Agents with Verbal Reinforcement Learning](https://mlsanity.com/paper/2303.11366/) (2023) - [Toolformer: Language Models Can Teach Themselves to Use Tools](https://mlsanity.com/paper/2302.04761/) (2023) - [Self-Refine: Iterative Refinement with Self-Feedback](https://mlsanity.com/paper/2303.17651/) (2023) - [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023) - [Voyager: An Open-Ended Embodied Agent with Large Language Models](https://mlsanity.com/paper/2305.16291/) (2023) - [Understanding intermediate layers using linear classifier probes](https://mlsanity.com/paper/1610.01644/) (2016) - [HuggingGPT: Solving AI Tasks with ChatGPT and its Friends in Hugging Face](https://mlsanity.com/paper/2303.17580/) (2023) - [Knowledge Neurons in Pretrained Transformers](https://mlsanity.com/paper/2104.08696/) (2021) - [Error bounds for approximations with deep ReLU networks](https://mlsanity.com/paper/1610.01145/) (2016) - [The Reversal Curse: LLMs trained on "A is B" fail to learn "B is A"](https://mlsanity.com/paper/2309.12288/) (2023) - [Neural Probabilistic Logic Programming in DeepProbLog](https://mlsanity.com/paper/1907.08194/) (2019) - [Formalizing and Benchmarking Prompt Injection Attacks and Defenses](https://mlsanity.com/paper/2310.12815/) (2023) - [The Illusion of Thinking: Understanding the Strengths and Limitations of Reasoning Models via the Lens of Problem Complexity](https://mlsanity.com/paper/2506.06941/) (2025) - [Measuring Compositional Generalization: A Comprehensive Method on Realistic Data](https://mlsanity.com/paper/1912.09713/) (2019) - [PoisonedRAG: Knowledge Corruption Attacks to Retrieval-Augmented Generation of Large Language Models](https://mlsanity.com/paper/2402.07867/) (2024) - [Reasoning or Reciting? Exploring the Capabilities and Limitations of Language Models Through Counterfactual Tasks](https://mlsanity.com/paper/2307.02477/) (2023) - [Universal Approximation with Deep Narrow Networks](https://mlsanity.com/paper/1905.08539/) (2019) - [Logic Tensor Networks](https://mlsanity.com/paper/2012.13635/) (2020) - [The Parallelism Tradeoff: Limitations of Log-Precision Transformers](https://mlsanity.com/paper/2207.00729/) (2022) - [Optimal approximation of continuous functions by very deep ReLU networks](https://mlsanity.com/paper/1802.03620/) (2018) - [Deep Network Approximation for Smooth Functions](https://mlsanity.com/paper/2001.03040/) (2020) - [Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionality](https://mlsanity.com/paper/1810.08033/) (2018) - [Saturated Transformers are Constant-Depth Threshold Circuits](https://mlsanity.com/paper/2106.16213/) (2021) - [On the Turing Completeness of Modern Neural Network Architectures](https://mlsanity.com/paper/1901.03429/) (2019) - [Optimal Approximation Rates for Deep ReLU Neural Networks on Sobolev and Besov Spaces](https://mlsanity.com/paper/2211.14400/) (2022) ## Built on by (most cited first, 2 of 2) - [Every Feedforward Neural Network Definable in an o-Minimal Structure Has Finite Sample Complexity](https://mlsanity.com/paper/2605.07097/) (2026) - [Algorithmic Foundations of Deep Learning: Complexity-Theoretic Rates and a Characterization of Universal Approximation](https://mlsanity.com/paper/2606.26705/) (2026) ## Abstract (arXiv) The proliferation of agentic systems has thrust the reasoning capabilities of AI into the forefront of contemporary machine learning. While it is known that there exist neural networks which can reason through any Boolean task f:0,1B→0,1, in the sense that they emulate Boolean circuits with fan-in 2 and fan-out 1 gates, trained models have been repeatedly demonstrated to fall short of these theoretical ideals. This raises the question: textitCan one exhibit a deep learning model which certifiably always reasons and can universally reason through any Boolean task? Moreover, such a model should ideally require few parameters to solve simple Boolean tasks. We answer this question affirmatively by exhibiting a deep learning architecture which parameterizes distributions over Boolean circuits with the guarantee that, for every parameter configuration, a sample is almost surely a valid Boolean circuit (and hence admits an intrinsic circuit-level certificate). We then prove a universality theorem: for any Boolean f:0,1B→0,1, there exists a parameter configuration under which the sampled circuit computes f with arbitrarily high probability. When f is an O(log B)-junta, the required number of parameters scales linearly with the input dimension B. Empirically, on a controlled truth-table completion benchmark aligned with our setting, the proposed architecture trains reliably and achieves high exact-match accuracy while preserving the predicted structure: every internal unit is Boolean-valued on 0,1B. Matched MLP baselines reach comparable accuracy, but only about 10% of hidden units admit a Boolean representation; i.e. are two-valued over the Boolean cube.