Pith. sign in

REVIEW 3 major objections 4 minor 71 references

Statistical Guarantees for Reasoning Probes on Looped Boolean Circuits

T0 review · 3 major / 4 minor · reviewed 2026-08-03 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Reasoning probes on looped Boolean circuits can achieve optimal worst-case generalization error O(1/√N) from N node queries, independently of circuit size when the snowflake parameter is tuned to 1/h.

desk verdict The 1D snowflake embedding at the core of the proof cannot exist at the claimed parameters; a packing argument contradicts it, so the main theorem is unsupported. read the letter →

arxiv 2602.03970 v3 pith:LJEJZAEM submitted 2026-02-03 stat.ML cs.LGcs.NEmath.MGmath.STstat.TH

Anastasis Kratsios , Giulia Livieri , A. Martina Neuman This is my paper
classification stat.MLcs.LGcs.NEmath.MGmath.STstat.TH
keywords reasoningprobesloopedBooleancircuitsgraphconvolutionalnetworkstransductivegeneralizationhittingprobabilitymetricsnowflakeembeddingfractionalWassersteindistanceoptimaltransport
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Looped reasoning — a circuit whose output is fed back into its input over multiple rounds — can be modeled as computation on a strongly connected directed graph. This paper asks how many randomly sampled internal nodes a reasoning probe needs in order to infer, in a generalization sense, which Boolean gates the circuit executes, when each observed node only gives a noisy, uncertain gate distribution. The main claim is that a graph-convolutional-network probe achieves the optimal worst-case generalization rate O(√log(2/δ)/√N) with high probability, and that this rate is independent of the total circuit size. The mechanism is geometric: a snowflaked version of the graph metric defined by hitting probabilities embeds into the real line with bounded distortion, reducing the problem to one-dimensional Wasserstein concentration. A sympathetic reader would care because it suggests that statistical efficiency in reasoning models can be governed by the geometry of the computation graph, not by exhaustive sampling or coverage of the circuit.

What carries the argument

The carrying mechanism is the hitting-probability metric d_G(v,w) = −log E_G(v,w) on the strongly connected quotient graph of the looped circuit — a metric that encodes global connectivity through the long-run probabilities of one node being hit before another in the circuit's random walk — together with a one-dimensional α-snowflake bi-Lipschitz embedding (Proposition A.1). That embedding maps (Γ, d_{G_sc}^α) into the real line with distortion bounded by constants depending only on the diameter, so the generalization gap over the hypothesis class is dominated by the α-Hölder Wasserstein distance between the sampling measure and its empirical version; classic one-dimensional concentration th

What would settle it

Numerically compute the normalized hitting-probability entries E_{G_sc}(v,w) in (6) for the deepest pairs of nodes in a perfect binary tree with h=10, using the Markov-chain definition in (5). The proof predicts the graph diameter is O(νh + log h), realized by the pair (v_{νh−1}, v_{νh}); if simulation shows a pair whose hitting-probability distance grows faster than linearly in h (e.g., Ω(ν^h)), the prefactor in (25) would acquire a graph-dependent growing term and the claimed graph-size independence would fail.

Watch

Extended reading notes

Core claim

The paper establishes that for a looped Boolean circuit whose computation graph is a perfect ν-ary tree, a GCN-parameterized reasoning probe querying N nodes drawn i.i.d. from the computation nodes has worst-case transductive generalization gap bounded by C·(1/√N + √log(2/δ)/√N) with probability at least 1−δ, where the constant C = (C_J (max{ m^{1/2} ((3+ν)/2)^{p(L−1)} ∏ β_l, ν^h, K_h })^{5/2})^α. Choosing α≍1/h keeps this constant uniformly bounded as the tree height h grows, so the O(1/√N) rate holds independently of the exponentially large number of nodes k=Θ(ν^h). The proof obtains this by embedding the snowflaked hitting-probability metric of the circuit's strongly connected quotient gr

Load-bearing premise

The result hinges on the bounded-complexity condition (18): between any two computation nodes, the probe's uncertain gate distribution changes by at most K_h, with K_h allowed to grow only exponentially in tree height h, because graph-size independence requires tuning α≍1/h to keep K_h^{5α/2} bounded.

Editorial extensions

If this is right

  • With α set to ≍1/h, the majorant in (25) remains bounded as h grows, so the optimal O(1/√N) generalization rate holds uniformly in circuit depth and cardinality.
  • The bound is time-uniform and holds for every input x and every computation round t, without assuming the probe samples all nodes or achieves coverage.
  • The prefactor depends on the probe's noise level K_h and on the GCN's sizes β_l only through the α-th power, so these constants are strongly damped when α is small.
  • If full node coverage is desired, N = Θ(k log(k/(1−δ))) uniform queries suffice by the coupon-collector bound; the generalization guarantee itself does not require that many samples.
  • The GCN probe is Lipschitz on the hitting-probability metric with explicit constant proportional to (m−1)^{1/2}((3+ν)/2)^{p(L−1)}Π β_l, so predicted gate distributions cannot vary abruptly between nearby computation nodes.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial extension: the only metric properties used are a diameter O(ν^h) and a one-dimensional snowflake embedding with bounded distortion; if those hold for other looped computation graphs (not necessarily perfect trees), the same optimal-rate conclusion is likely to transfer.
  • Editorial extension: tuning α≍1/h means the snowflaked loss becomes progressively flatter in deep circuits, so the guarantee should be read as covering coarse gate-level discrimination; subtler distinctions in very deep circuits may require a different, non-snowflaked analysis.
  • Editorial extension: a practical two-stage protocol suggests itself — use roughly k log(k/(1−δ)) i.i.d. queries if coverage is desired, then rely on the generalization bound for the inference task; testing this on simulated ν-ary circuits for h=5..15 would directly check the predicted prefactor behavior.
  • Editorial extension: because the theorem allows repeated sampling of the same nodes and never exploits memory across rounds, an immediate open direction is whether relaxing the 'read once per time step' assumption — allowing the probe to adapt its queries to earlier outputs — improves the constant or changes the rate.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper studies transductive generalization of GCN-parameterized reasoning probes on looped Boolean circuits whose computational graph is a perfect ν-ary tree. The probe observes N sampled internal nodes and predicts distributions over a finite set of Boolean gates. The main result, Theorem 3.1 / Eq. (25), states a worst-case generalization gap bound of order O(1/√N) with probability 1−δ, with a prefactor that the paper claims can be made independent of graph size by choosing the snowflake exponent α ≍ 1/h. The proof combines a one-dimensional snowflake embedding (Proposition A.1), a Wasserstein concentration lemma (Lemma A.1), and Lipschitz estimates for GCNs on digraphs (Proposition B.1). The graph-size-independence claim is the central advertised contribution.

Significance. If the result were valid, it would be a substantial contribution: optimal O(1/√N) generalization rates for reasoning probes that are independent of the exponentially large computation graph, with a clean geometric mechanism via snowflake embeddings. The paper also provides explicit Lipschitz bounds for GCNs on directed graphs, which could be of independent interest. However, the central technical lemma, Lemma A.1, is false as stated, and Proposition A.1, the genuinely new embedding result, is impossible for the parameter regime used in the paper. Because these lemmas are load-bearing for Eq. (25), the main theorem is unsupported. The paper does disclose that parts of the Wasserstein machinery are adapted from the authors' prior work [30], which is acceptable self-reliance rather than circular reasoning, but the new embedding step cannot be repaired without changing the substance of the paper.

major comments (3)
  1. [Appendix A, Lemma A.1 / Eq. (31)] The lemma is false. Take X = {1,...,k} with d(x,y) = 1 for x ≠ y, and let λ be the uniform distribution. Then d(x,y)^α = 1 for all x≠y, so every [0,1]-valued function is in H(α,X,1). Consequently W_α(λ,λ_N) equals the total variation distance between λ and its empirical measure λ_N. For fixed N and k → ∞, E[TV(λ,λ_N)] tends to 1, not O(diam(X)^{3α/2}/√N) = O(1/√N). This directly invalidates Eq. (31). Since the proof of Theorem 3.1 uses exactly this bound in the Wasserstein step, Eqs. (50)-(52), the main inequality (25) is not established.
  2. [Appendix A, Proposition A.1 / Eq. (32)] Proposition A.1 claims a bi-Lipschitz embedding φ:(X,d^α)→(R,|·|) with lower bound c D^{-α/2} d(x,y)^α and diameter at most C D^α. In R, any set with minimum separation L and diameter M has at most M/L+1 points. Here the lower bound gives L ≍ D^{-α/2} (since d(x,y)≥1) and the diameter bound gives M ≍ D^α, hence k ≤ O(D^{3α/2}). In the application to X = Γ, k = |Γ| ≍ ν^h and D ≍ ν^h by Proposition B.1(i) and Eq. (56). The advertised graph-size independence requires α ≍ 1/h, which gives D^{3α/2} = ν^{3/2} = O(1), contradicting k ≍ ν^h for large h. Thus the embedding cannot exist; the composition argument around Eqs. (34)-(42), specifically the step invoking [35, Thm 6.6] with m_θ = 1, must be invalid.
  3. [Section 4, selection of α ≍ 1/h] Even aside from the embedding failure, the claimed graph-size independence is obtained only by making the loss depend on h. For α = 1/h and any bounded nonnegative Lipschitz loss J, J(y,z)^α approaches a threshold loss as h grows (0 when J(y,z)=0, 1 when J(y,z)>0). Thus Eq. (25) bounds a different and increasingly degenerate objective for each graph size. If α is instead held fixed, the prefactor (max{ν^h, K_h})^{5α/2} in (25) grows with h and the graph-size independence claim fails. The paper should state explicitly what fixed learning problem enjoys graph-size-independent rates, or reinterpret what is being claimed.
minor comments (4)
  1. [Notation, Section 3] The symbol h is used both for the tree height and for a hypothesis h ∈ H in Eq. (21) and throughout the proof of Theorem 3.1. This creates confusion in phrases such as 'as h grows' versus 'for h ∈ H'.
  2. [Section 4 / Proposition 4.1] Proposition 4.1 and the sharpened bound (28) are not used in the proof of the main theorem. They are presented as contextual discussion, but the paper should state more explicitly that they are not needed for Theorem 3.1, or move them to the appendix.
  3. [Eq. (28)] The displayed lower bound contains a possible missing parenthesis: '1-(k-1)^n(min w_i)^n -(k-1)(1-min w_i)^n' is missing a closing parenthesis after the first term. Please correct the typo.
  4. [Abstract and Section 1.3] The phrase 'optimal rate O(1/√N)' is used without a formal minimax statement. The rate is optimal for one-dimensional Wasserstein concentration, but the paper does not prove optimality for the specific probe/graph problem. A precise caveat would be helpful.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the claimed O(1/√N) graph-size-independent rate is not built into the definitions; it follows from external embedding theorems plus a disclosed, independently checkable concentration lemma.

full rationale

Theorem 3.1's derivation has two independent pillars. The embedding step (Prop. A.1) is proved in the paper from Neiman's Assouad-type theorem [53] and Har-Peled–Mendel [35]; it is not imported from the authors' prior work. The Wasserstein concentration step (Lemma A.1) is adapted from the authors' own [30, Prop. 4.1] and uses Prop. A.2, cited to [30, Lemma B.2] as a variant of [36, Lemma 16]. These self-references are load-bearing, but they concern a parameter-free concentration estimate on R whose stated assumptions (X compact, N≥4) do not include the target graph-size independence; by rule 4, that is independent support, not circularity. The graph-size independence enters only through the explicit 'a priori' choice α≍1/h in a bound valid for every α, and through the explicit assumption (18) that K_h grows at most exponentially in h; neither is a fitted parameter renamed as a prediction. The paper's new one-dimensional snowflake embedding (Prop. A.1) is the genuinely novel element and is derived from external theorems, though its mathematical correctness is a separate soundness question (e.g. the packing-bound objection in the reviewer context), not a circularity issue. No equation is shown to be equivalent to its own input by construction.

Assumptions & free parameters 2 free parameters · 8 assumptions · 0 invented entities

The central theorem rests on the probe-variation bound (18), a Lipschitz loss (20), the GCN model of Def 2.1, external Assouad-type embedding theorems, and the Wasserstein concentration result from the authors' earlier paper [30]. The 1D snowflake embedding is derived in the paper, so no new invented entities are needed.

free parameters (2)
  • α (snowflake exponent) = α ≍ 1/h (chosen by hand)
    The main theorem's constant contains (max{...})^{5α/2}; choosing α proportional to 1/h makes the prefactor independent of h, but the loss J^α becomes nearly constant for large h.
  • η (certainty level) = unset, in (0,1)
    Parameter of the probe noise model Q_η; it affects the Aitchison distances between probe outputs and hence the bound via K_h.
assumptions (8)
  • standard math The hitting probability metric d_G (Eq 7) is a metric on strongly connected digraphs, per [18].
    Used throughout to define the metric geometry of G_sc and the induced subgraph Γ.
  • domain assumption Bounded-complexity condition (Eq 18): ‖Q_η(v)−Q_η(w)‖_A ≤ K_h for all v,w∈Γ, with K_h at most exponential in h.
    Load-bearing premise for the graph-size independence: it controls C_Qη and diam(D).
  • domain assumption The loss J is Lipschitz in the Aitchison metric (Eq 20).
    Needed to relate the empirical/population risks to the Wasserstein distance.
  • domain assumption GCN model (Def 2.1) with 1-Lipschitz activation and bounded weight operator norms.
    Defines the hypothesis class H and enables the Lipschitz estimate in Prop B.1(iii).
  • standard math External embedding theorems: Neiman's Assouad embedding [53, Thm 3] and Har-Peled-Mendel's snowflake embedding [35, Thm 6.6].
    Used in the proof of Proposition A.1 to construct the one-dimensional snowflake embedding.
  • standard math Wasserstein concentration on R (Prop A.2) established in [30, Lemma B.2].
    The concentration bound for W1 on the real line is taken from the authors' prior work.
  • standard math Aitchison geometry: Δ_m^∘ with d_A is isometric to R^{m−1} via the ilr transform.
    Used to identify probe outputs with Euclidean space and to compute Lipschitz constants.
  • standard math Strong connectivity of G_sc and existence/uniqueness of the Perron vector for the irreducible transition matrix P_Gsc.
    Underlies the hitting-probability metric and the diameter computation.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Statistical Guarantees for Reasoning Probes on Looped Boolean Circuits." pith.science (2026). https://pith.science/paper/LJEJZAEM

@misc{pith2026260203970,
  author       = {Pith},
  title        = {Pith review of: Statistical Guarantees for Reasoning Probes on Looped Boolean Circuits},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LJEJZAEM}},
  note         = {Machine review of arXiv:2602.03970}
}
abstract

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\ge 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 $\mathcal{O}(\sqrt{\log(2/\delta)}/\sqrt{N})$ with probability at least $1-\delta$. 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.

Figures

Figures reproduced from arXiv: 2602.03970 by the authors.

Figure 1
Figure 1. A looped reasoning model (a) and its induced time-quotient, strongly connected digraph (b). In the [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Illustration of a one￾dimensional embedding of a finite met￾ric space; the objective is to keep metric distortion small. More recently, [30] removes the dependence on metric cardinality by adopting a fractional 1/2-Wasserstein distance. In their approach, both the true and empirical risks are measured with respect to the 1/2- snowflaked loss function, and—by combining the results of [36] with Kan￾torovich duality—th… view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

71 extracted references · 9 linked inside Pith

  1. [30]

    Learning from one graph: transductive learning guarantees via the geometry of small random worlds.arXiv preprint arXiv:2509.06894, 2025

    Nils Detering, Luca Galimberti, Anastasis Kratsios, Giulia Livieri, and A Martina Neuman. Learning from one graph: transductive learning guarantees via the geometry of small random worlds.arXiv preprint arXiv:2509.06894, 2025

    arXiv 2025

  2. [1]

    Gpt-4 technical report.arXiv preprint arXiv:2303.08774, 2023

    Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. Gpt-4 technical report.arXiv preprint arXiv:2303.08774, 2023

    arXiv 2023

  3. [2]

    The statistical analysis of compositional data.Journal of the Royal Statistical Society: Series B (Methodological), 44(2):139–160, 1982

    John Aitchison. The statistical analysis of compositional data.Journal of the Royal Statistical Society: Series B (Methodological), 44(2):139–160, 1982

    1982

  4. [3]

    Understanding intermediate layers using linear classifier probes.arXiv preprint arXiv:1610.01644, 2016

    Guillaume Alain and Yoshua Bengio. Understanding intermediate layers using linear classifier probes.arXiv preprint arXiv:1610.01644, 2016

    arXiv 2016

  5. [4]

    Self-RAG: Learning to retrieve, generate, and critique through self-reflection

    Akari Asai, Zeqiu Wu, Yizhong Wang, Avirup Sil, and Hannaneh Hajishirzi. Self-RAG: Learning to retrieve, generate, and critique through self-reflection. InThe Twelfth International Conference on Learning Represen- tations, 2024

    2024

  6. [5]

    Plongements Lipschitziens dansR n.Bulletin de la Soci´ et´ e Math´ ematique de France, 111:429– 448, 1983

    Patrice Assouad. Plongements Lipschitziens dansR n.Bulletin de la Soci´ et´ e Math´ ematique de France, 111:429– 448, 1983

    1983

  7. [6]

    Do we really need the Rademacher complexities?arXiv preprint arXiv:2502.15118, 2025

    Daniel Bartl and Shahar Mendelson. Do we really need the Rademacher complexities?arXiv preprint arXiv:2502.15118, 2025

    arXiv 2025

  8. [7]

    Uniform mean estimation via generic chaining.arXiv preprint arXiv:2502.15116, 2025

    Daniel Bartl and Shahar Mendelson. Uniform mean estimation via generic chaining.arXiv preprint arXiv:2502.15116, 2025

    arXiv 2025

Show all 71 references
  1. [8]

    Local rademacher complexities.The Annals of Statistics, 33(4):1497–1537, 2005

    Peter L Bartlett, Olivier Bousquet, and Shahar Mendelson. Local rademacher complexities.The Annals of Statistics, 33(4):1497–1537, 2005

    2005

  2. [9]

    Rademacher and gaussian complexities: Risk bounds and structural results.Journal of machine learning research, 3(Nov):463–482, 2002

    Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results.Journal of machine learning research, 3(Nov):463–482, 2002

    2002

  3. [10]

    Network dissection: Quantifying interpretability of deep visual representations

    David Bau, Bolei Zhou, Aditya Khosla, Aude Oliva, and Antonio Torralba. Network dissection: Quantifying interpretability of deep visual representations. InProceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 3319–3327, 2017

    2017

  4. [11]

    Minimalstellen von funktionen und extremalpunkte.Archiv der Mathematik, 9(4):389–393, 1958

    Heinz Bauer. Minimalstellen von funktionen und extremalpunkte.Archiv der Mathematik, 9(4):389–393, 1958

    1958

  5. [12]

    Square-root lasso: pivotal recovery of sparse signals via conic programming.Biometrika, 98(4):791–806, 2011

    Alexandre Belloni, Victor Chernozhukov, and Lie Wang. Square-root lasso: pivotal recovery of sparse signals via conic programming.Biometrika, 98(4):791–806, 2011

    2011

  6. [13]

    Managing extreme AI risks amid rapid progress.Science, 384(6698):842–845, 2024

    Yoshua Bengio, Geoffrey Hinton, Andrew Yao, Dawn Song, Pieter Abbeel, Trevor Darrell, Yuval Noah Harari, Ya-Qin Zhang, Lan Xue, Shai Shalev-Shwartz, et al. Managing extreme AI risks amid rapid progress.Science, 384(6698):842–845, 2024

    2024

  7. [14]

    Neural algorithmic reasoning with causal regularisation

    Beatrice Bevilacqua, Kyriacos Nikiforou, Borja Ibarz, Ioana Bica, Michela Paganini, Charles Blundell, Jovana Mitrovic, and Petar Veliˇ ckovi´ c. Neural algorithmic reasoning with causal regularisation. InInternational Conference on Machine Learning, pages 2272–2288. PMLR, 2023

    2023

  8. [15]

    Learnability and the Vapnik- Chervonenkis dimension.Journal of the ACM (JACM), 36(4):929–965, 1989

    Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K Warmuth. Learnability and the Vapnik- Chervonenkis dimension.Journal of the ACM (JACM), 36(4):929–965, 1989

    1989

  9. [16]

    Oxford University Press, 2014

    Nick Bostrom.Superintelligence: Paths, Dangers, Strategies. Oxford University Press, 2014

    2014

  10. [17]

    A universal uniform approximation theorem for neural networks

    Olivier Bournez, Johanne Cohen, and Adrian Wurm. A universal uniform approximation theorem for neural networks. InProceedings of the International Symposium on Mathematical Foundations of Computer Science (MFCS), Palaiseau, France, 2025

    2025

  11. [18]

    A metric on directed graphs and markov chains based on hitting probabilities.SIAM Journal on Mathematics of Data Science, 3(2):467–493, 2021

    Zachary M Boyd, Nicolas Fraiman, Jeremy Marzuola, Peter J Mucha, Braxton Osting, and Jonathan Weare. A metric on directed graphs and markov chains based on hitting probabilities.SIAM Journal on Mathematics of Data Science, 3(2):467–493, 2021

    2021

  12. [19]

    Pek¨ oz, and Sheldon M

    Mark Brown, Erol A. Pek¨ oz, and Sheldon M. Ross. Coupon collecting.Probability in the Engineering and Informational Sciences, 22(2):221–229, 2008. 18

    2008

  13. [20]

    Language models are few-shot learners

    Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Nee- lakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. In Advances in Neural Information Processing Systems (NeurIPS), 2020

    2020

  14. [21]

    Magicore: Multi-agent, iterative, coarse-to-fine refinement for reasoning

    Justin Chih-Yao Chen, Archiki Prasad, Swarnadeep Saha, Elias Stengel-Eskin, and Mohit Bansal. Magicore: Multi-agent, iterative, coarse-to-fine refinement for reasoning. InProceedings of EMNLP, 2025

    2025

  15. [22]

    Transformers in uniform TC 0.arxiv, 2024

    David Chiang. Transformers in uniform TC 0.arxiv, 2024

    2024

  16. [23]

    Laplacians and the cheeger inequality for directed graphs.Annals of Combinatorics, 9(1):1–19, 2005

    Fan Chung. Laplacians and the cheeger inequality for directed graphs.Annals of Combinatorics, 9(1):1–19, 2005

    2005

  17. [24]

    Turing completeness of bounded-precision recurrent neural networks

    Stephen Chung and Hava Siegelmann. Turing completeness of bounded-precision recurrent neural networks. Advances in neural information processing systems, 34:28431–28441, 2021

    2021

  18. [25]

    What you can cram into a single vector: Probing sentence embeddings for linguistic properties.CoRR, abs/1805.01070, 2018

    Alexis Conneau, Germ´ an Kruszewski, Guillaume Lample, Lo ¨ ıc Barrault, and Marco Baroni. What you can cram into a single vector: Probing sentence embeddings for linguistic properties.CoRR, abs/1805.01070, 2018

    2018 arXiv

  19. [26]

    A dexire for extracting propositional rules from neural networks via binarization.Electronics, 11(24), 2022

    Victor Contreras, Niccolo Marini, Lora Fanda, Gaetano Manzo, Yazan Mualla, Jean-Paul Calbimonte, Michael Schumacher, and Davide Calvaresi. A dexire for extracting propositional rules from neural networks via binarization.Electronics, 11(24), 2022

    2022

  20. [27]

    Extracting tree-structured representations of trained networks

    Mark Craven and Jude Shavlik. Extracting tree-structured representations of trained networks. In D. Touretzky, M.C. Mozer, and M. Hasselmo, editors,Advances in Neural Information Processing Systems, volume 8. MIT Press, 1995

    1995

  21. [28]

    Knowledge neurons in pretrained transformers

    Damai Dai, Li Dong, Yaru Hao, Zhifang Sui, Baobao Chang, and Furu Wei. Knowledge neurons in pretrained transformers. InProceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 8493–8502, Dublin, Ireland, 2022. Assoc...

    2022

  22. [29]

    Gemini: A family of highly capable multimodal models.arXiv preprint arXiv:2312.11805, 2023

    Google DeepMind. Gemini: A family of highly capable multimodal models.arXiv preprint arXiv:2312.11805, 2023

    2023 arXiv

  23. [31]

    The information-geometric perspective of compositional data analysis

    Ionas Erb and Nihat Ay. The information-geometric perspective of compositional data analysis. InAdvances in Compositional Data Analysis: Festschrift in Honour of Vera Pawlowsky-Glahn, pages 21–43. Springer, 2021

    2021

  24. [32]

    Birthday paradox, coupon collectors, caching algorithms and self-organizing search.Discrete Applied Mathematics, 39(3):207–229, 1992

    Philippe Flajolet, Daniele Gardy, and Lo¨ ys Thimonier. Birthday paradox, coupon collectors, caching algorithms and self-organizing search.Discrete Applied Mathematics, 39(3):207–229, 1992

    1992

  25. [33]

    Neural algorithmic reasoning for combinatorial optimisation

    Dobrik Georgiev Georgiev, Danilo Numeroso, Davide Bacciu, and Pietro Li` o. Neural algorithmic reasoning for combinatorial optimisation. InLearning on Graphs Conference, pages 28–1. PMLR, 2024

    2024

  26. [34]

    Compositional data analysis.Annual Review of Statistics and its Application, 8(1):271–299, 2021

    Michael Greenacre. Compositional data analysis.Annual Review of Statistics and its Application, 8(1):271–299, 2021

    2021

  27. [35]

    Fast construction of nets in low-dimensional metrics and their applications

    Sariel Har-Peled and Manor Mendel. Fast construction of nets in low-dimensional metrics and their applications. SIAM Journal on Computing, 35(5):1148–1184, 2006

    2006

  28. [36]

    Instance-dependent generalization bounds via optimal transport.Journal of Machine Learning Research, 24(349):1–51, 2023

    Songyan Hou, Parnian Kassraie, Anastasis Kratsios, Andreas Krause, and Jonas Rothfuss. Instance-dependent generalization bounds via optimal transport.Journal of Machine Learning Research, 24(349):1–51, 2023

    2023

  29. [37]

    Polynomial bounds for vc dimension of sigmoidal and general pfaffian neural networks.Journal of Computer and System Sciences, 54(1):169–176, 1997

    Marek Karpinski and Angus Macintyre. Polynomial bounds for vc dimension of sigmoidal and general pfaffian neural networks.Journal of Computer and System Sciences, 54(1):169–176, 1997

    1997

  30. [38]

    Large language models are zero-shot reasoners.arXiv preprint arXiv:2205.11916, 2022

    Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners.arXiv preprint arXiv:2205.11916, 2022

    2022 arXiv

  31. [39]

    Tighter generalization bounds on digital computers via discrete optimal transport.arXiv preprint arXiv:2402.05576, 2024

    Anastasis Kratsios, A Martina Neuman, and Gudmund Pammer. Tighter generalization bounds on digital computers via discrete optimal transport.arXiv preprint arXiv:2402.05576, 2024. 19

    2024 arXiv

  32. [40]

    Retrieval-augmented generation for knowledge- intensive nlp tasks.Advances in neural information processing systems, 33:9459–9474, 2020

    Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich K¨ uttler, Mike Lewis, Wen-tau Yih, Tim Rockt¨ aschel, et al. Retrieval-augmented generation for knowledge- intensive nlp tasks.Advances in neural information processing sys...

    2020

  33. [41]

    Certifiable reasoning is universal: A differentiable reasoning AI.arXiv preprint, 2026

    Wenhao Li, Anastasis Kratsios, Hrad Ghoukasian, and Dennis Zvigelsky. Certifiable reasoning is universal: A differentiable reasoning AI.arXiv preprint, 2026. Preprint

    2026

  34. [42]

    Learning arithmetic circuits

    Daniel Lowd and Pedro Domingos. Learning arithmetic circuits. InProceedings of the Twenty-Fourth Confer- ence on Uncertainty in Artificial Intelligence, pages 383–392, 2008

    2008

  35. [43]

    Is homophily a necessity for graph neural networks? In International Conference on Learning Representations, 2022

    Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. Is homophily a necessity for graph neural networks? In International Conference on Learning Representations, 2022

    2022

  36. [44]

    Cambridge University Press, 2021

    Yao Ma and Jiliang Tang.Deep learning on graphs. Cambridge University Press, 2021

    2021

  37. [45]

    Wolfgang Maass, Georg Schnitger, and Eduardo D. Sontag. On the computational power of sigmoid versus boolean threshold circuits. InProceedings of the 32nd Annual Symposium on Foundations of Computer Science (FOCS), pages 767–776, 1991

    1991

  38. [46]

    Self-refine: Iterative refinement with self-feedback.Advances in Neural Information Processing Systems, 36:46534–46594, 2023

    Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, et al. Self-refine: Iterative refinement with self-feedback.Advances in Neural Information Processing Systems, 36:46534–46594, 2023

    2023

  39. [47]

    A neural state pushdown automata.IEEE Transactions on Artificial Intelligence, 1(3):193–205, 2021

    Ankur Arjun Mali, Alexander G Ororbia II, and C Lee Giles. A neural state pushdown automata.IEEE Transactions on Artificial Intelligence, 1(3):193–205, 2021

    2021

  40. [48]

    John Wiley & Sons, 2009

    Kanti V Mardia and Peter E Jupp.Directional statistics. John Wiley & Sons, 2009

    2009

  41. [49]

    Polynomial-time solvable# csp problems via algebraic models and pfaffian circuits.Journal of Symbolic Computation, 74:152–180, 2016

    Susan Margulies and Jason Morton. Polynomial-time solvable# csp problems via algebraic models and pfaffian circuits.Journal of Symbolic Computation, 74:152–180, 2016

    2016

  42. [50]

    The parallelism tradeoff: Limitations of log-precision transformers

    William Merrill and Ashish Sabharwal. The parallelism tradeoff: Limitations of log-precision transformers. Transactions of the Association for Computational Linguistics, 2023

    2023

  43. [51]

    William Merrill, Ashish Sabharwal, and Noah A. Smith. Saturated transformers are constant-depth threshold circuits.Transactions of the Association for Computational Linguistics, 2022

    2022

  44. [52]

    Assouad’s theorem with dimension independent of the snowflaking.Revista Matematica Iberoamericana, 28(4):1123–1142, 2012

    Assaf Naor and Ofer Neiman. Assouad’s theorem with dimension independent of the snowflaking.Revista Matematica Iberoamericana, 28(4):1123–1142, 2012

    2012

  45. [53]

    Low dimensional embeddings of doubling metrics.Theory Comput

    Ofer Neiman. Low dimensional embeddings of doubling metrics.Theory Comput. Syst., 58(1):133–152, 2016

    2016

  46. [54]

    Zoom in: An introduction to circuits.Distill, 5(3):e00024.001, 2020

    Chris Olah, Nick Cammarata, Ludwig Schubert, Gabriel Goh, Michael Petrov, and Shan Carter. Zoom in: An introduction to circuits.Distill, 5(3):e00024.001, 2020

    2020

  47. [55]

    The building blocks of interpretability.Distill, 3(3):e10, 2018

    Chris Olah, Arvind Satyanarayan, Ian Johnson, Shan Carter, Ludwig Schubert, Katherine Ye, and Alexander Mordvintsev. The building blocks of interpretability.Distill, 3(3):e10, 2018

    2018

  48. [56]

    Multiplicative schr¨ odinger problem and the dirichlet transport

    Soumik Pal and Ting-Kam Leonard Wong. Multiplicative schr¨ odinger problem and the dirichlet transport. Probability Theory and Related Fields, 178(1):613–654, 2020

    2020

  49. [57]

    Compositional data and their analysis: an introduction

    Vera Pawlowsky-Glahn and Juan Jos´ e Egozcue. Compositional data and their analysis: an introduction. Geological Society, London, Special Publications, 264(1):1–10, 2006

    2006

  50. [58]

    On the turing completeness of modern neural network architectures

    Jorge P´ erez, Javier Marinkovi´ c, and Pablo Barcel´ o. On the turing completeness of modern neural network architectures. InInternational Conference on Learning Representations, 2019

    2019

  51. [59]

    On a classical problem of probability theory.Magyar Tudom´ anyos Akad´ emia Matematikai Kutat´ o Int´ ezet´ enek K¨ ozlem´ enyei, 6:215–220, 1958

    Alfr´ ed R´ enyi. On a classical problem of probability theory.Magyar Tudom´ anyos Akad´ emia Matematikai Kutat´ o Int´ ezet´ enek K¨ ozlem´ enyei, 6:215–220, 1958

    1958

  52. [60]

    Nikunj Saunshi, Nishanth Dikkala, Zhiyuan Li, Sanjiv Kumar, and Sashank J. Reddi. Reasoning with latent thoughts: On the power of looped transformers. InThe Thirteenth International Conference on Learning Representations, 2025. 20

    2025

  53. [61]

    Narasimhan

    Noah Shinn, Beck Labash, Ashwin Gopinath, and Karthik R. Narasimhan. Reflexion: Language agents with verbal reinforcement learning. InAdvances in Neural Information Processing Systems (NeurIPS), 2023

    2023

  54. [62]

    Springer Science & Business Media, 2012

    Hava T Siegelmann.Neural networks and analog computation: beyond the Turing limit. Springer Science & Business Media, 2012

    2012

  55. [63]

    Depth efficient neural networks for division and related problems.IEEE Transactions on Information Theory, 39(3):946–956, 1993

    Kai-Yeung Siu, Jehoshua Bruck, Thomas Kailath, and Thomas Hofmeister. Depth efficient neural networks for division and related problems.IEEE Transactions on Information Theory, 39(3):946–956, 1993

    1993

  56. [64]

    Inference for empirical wasserstein distances on finite spaces.Journal of the Royal Statistical Society Series B: Statistical Methodology, 80(1):219–238, 2018

    Max Sommerfeld and Axel Munk. Inference for empirical wasserstein distances on finite spaces.Journal of the Royal Statistical Society Series B: Statistical Methodology, 80(1):219–238, 2018

    2018

  57. [65]

    Thinking isn’t an illusion: Overcoming the limitations of reasoning models via tool augmentations.arXiv preprint arXiv:2507.17699, 2025

    Zhao Song, Song Yue, and Jiahao Zhang. Thinking isn’t an illusion: Overcoming the limitations of reasoning models via tool augmentations.arXiv preprint arXiv:2507.17699, 2025

    2025 arXiv

  58. [66]

    Sharp oracle inequalities for square root regularization.Journal of Machine Learning Research, 18(67):1–29, 2017

    Benjamin Stucky and Sara Van De Geer. Sharp oracle inequalities for square root regularization.Journal of Machine Learning Research, 18(67):1–29, 2017

    2017

  59. [67]

    Springer, 2009

    C´ edric Villani et al.Optimal transport: old and new, volume 338. Springer, 2009

    2009

  60. [68]

    Voyager: An open-ended embodied agent with large language models

    Guanzhi Wang, Yu Wang, Xinyi Liu, Shibin Liu, Yizhou Chen, Yiming Zhang, Jian Zhao, and Tong Zhang. Voyager: An open-ended embodied agent with large language models. InInternational Conference on Learning Representations (ICLR), 2024

    2024

  61. [69]

    Le, Ed H

    Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc V. Le, Ed H. Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. InInternational Conference on Learning Representations (ICLR), 2023

    2023

  62. [70]

    Le, Denny Zhou, et al

    Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed Chi, Quoc V. Le, Denny Zhou, et al. Chain-of-thought prompting elicits reasoning in large language models. InAdvances in Neural Information Processing Systems (NeurIPS), 2022

    2022

  63. [71]

    Star: Self-taught reasoner

    Eric Zelikman, Yuhuai Wu, and Noah D Goodman. Star: Self-taught reasoner. InProceedings of the NIPS, volume 22, 2022. 21

    2022

Pith tools

Reviewed August 3, 2026 · model on record in the stance chip above.