研究神经网络如何通过部分观测推断循环布尔电路的运算逻辑，给出理论保证。
Statistical Guarantees for Reasoning Probes on Looped Boolean Circuits
- 用图卷积网络探测循环布尔电路中部分节点的逻辑门。
- 观测节点数为N时，错误率以√(log(2/δ)/N)速率下降。
- 适用于分析结构化迭代计算中的探针效率，如神经算法推理。
我们研究了一种受神经算法推理启发的迭代计算简化模型中推理探针的统计行为。该模型基于环形布尔电路，其图结构为完全ν-叉树（ν≥2），输出在各计算轮次间递归反馈作为输入。探针仅观测内部节点的采样子集，试图推断每个节点的潜在运算，以有限可接受布尔门集合上的概率分布表示。这种局部可观测性导致在结构化计算图上的归纳泛化问题。当探针由图卷积网络参数化且查询N个节点时，最坏情况下的泛化误差以最优速率𝒪(√(log(2/δ)/√N))衰减，置信度至少为1−δ。我们的分析结合度量嵌入与最优传输工具。关键洞见是：该速率可独立于计算图规模实现，得益于诱导图度量的一维雪崩嵌入具有低失真。这些结果揭示了探针在结构化、迭代计算中实现统计高效性的几何机制。
原文摘要 · Abstract (English)
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 $ν$-ary tree ($ν\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/δ)}/\sqrt{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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。