mlsanityData to 14 Oct 2026

Statistical Guarantees for Reasoning Probes on Looped Boolean Circuits

arXiv 2602.03970 ↗First posted 3 Feb 2026stat.ML cs.LG cs.NEcited by 0

Not on the map. Why?

Abstract (arXiv)

We study the statistical behavior of reasoning probes in a stylized model of iterative computation inspired by neural algorithmic reasoning. The underlying computation is given by a looped Boolean circuit whose graph is a perfect nu-ary tree (nu≥ 2), with outputs recursively fed back as inputs across computation rounds. A probe observes a sampled subset of internal nodes and seeks to infer the latent operation at each node, represented as a probability distribution over a finite set of admissible Boolean gates. This partial observability induces a transductive generalization problem on a structured computation graph. We show that when the probe is parameterized by a graph convolutional network and queries N nodes, the worst-case generalization error decays at the optimal rate O(√log(2/δ)/√N) with probability at least 1-δ. Our analysis combines metric embedding techniques with tools from optimal transport. A key insight is that this rate is achievable independently of the size of the computation graph, enabled by a low-distortion one-dimensional snowflake embedding of the induced graph metric. These results highlight a geometric mechanism underlying statistical efficiency in probing structured, iterative computations.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 42 of its 88 references that are in the map. First posted on arXiv 3 Feb 2026.

Builds on

42 of 88 references.

References · 42

  1. 2020Language Models are Few-Shot Learnerscited by 32,419
  2. 2023GPT-4 Technical Reportcited by 18,396
  3. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Modelscited by 12,459
  4. 2020Retrieval-Augmented Generation for Knowledge-Intensive NLP Taskscited by 9,297
  5. 2022Self-Consistency Improves Chain of Thought Reasoning in Language Modelscited by 5,708
  6. 2022Large Language Models are Zero-Shot Reasonerscited by 4,374
  7. 2023Reflexion: Language Agents with Verbal Reinforcement Learningcited by 4,276
  8. 2023Self-Refine: Iterative Refinement with Self-Feedbackcited by 3,442
  9. 2023Voyager: An Open-Ended Embodied Agent with Large Language Modelscited by 2,191
  10. 2023Self-RAG: Learning to Retrieve, Generate, and Critique through Self-Reflectioncited by 1,839
  11. 2017Towards A Rigorous Science of Interpretable Machine Learningcited by 1,416
  12. 2018Datasheets for Datasetscited by 1,386
30 more
  1. 2016Understanding intermediate layers using linear classifier probescited by 1,353
  2. 2018Model Cards for Model Reportingcited by 1,080
  3. 2016The Mythos of Model Interpretabilitycited by 721
  4. 2017Network Dissection: Quantifying Interpretability of Deep Visual Representationscited by 708
  5. 2021Knowledge Neurons in Pretrained Transformerscited by 601
  6. 2018What you can cram into a single vector: Probing sentence embeddings for linguistic propertiescited by 457
  7. 2020Closing the AI Accountability Gap: Defining an End-to-End Framework for Internal Algorithmic Auditingcited by 384
  8. 2025Reasoning with Latent Thoughts: On the Power of Looped Transformerscited by 240
  9. 2018Learning a SAT Solver from Single-Bit Supervisioncited by 200
  10. 2022The Parallelism Tradeoff: Limitations of Log-Precision Transformerscited by 193
  11. 2021Is Homophily a Necessity for Graph Neural Networks?cited by 182
  12. 2021Saturated Transformers are Constant-Depth Threshold Circuitscited by 139
  13. 2019On the Turing Completeness of Modern Neural Network Architecturescited by 129
  14. 2019Neural Execution of Graph Algorithmscited by 121
  15. 2022The CLRS Algorithmic Reasoning Benchmarkcited by 106
  16. 2021Neural Algorithmic Reasoningcited by 94
  17. 2022A Generalist Neural Algorithmic Learnercited by 59
  18. 2024MAgICoRe: Multi-Agent, Iterative, Coarse-to-Fine Refinement for Reasoningcited by 41
  19. 2023Neural Algorithmic Reasoning with Causal Regularisationcited by 31
  20. 2024Transformers in Uniform TC0cited by 25
  21. 2016Inference for Empirical Wasserstein Distances on Finite Spacescited by 21
  22. 2023Neural Algorithmic Reasoning for Combinatorial Optimisationcited by 19
  23. 2022Instance-Dependent Generalization Bounds via Optimal Transportcited by 13
  24. 2019The Neural State Pushdown Automatacited by 9
  25. 2025Thinking Isn't an Illusion: Overcoming the Limitations of Reasoning Models via Tool Augmentationscited by 9
  26. 2020The Information-Geometric Perspective of Compositional Data Analysiscited by 5
  27. 2020A metric on directed graphs and Markov chains based on hitting probabilitiescited by 3
  28. 2025Learning from one graph: transductive learning guarantees via the geometry of small random worldscited by 3
  29. 2013Polynomial-time Solvable #CSP Problems via Algebraic Models and Pfaffian Circuitscited by 2
  30. 2025Do we really need the Rademacher complexities?cited by 2

Built on by

Not cited yet.