acceptodds
Under review as a conference paper at ICLR 2027

The Geometry of Robust Symbolic Computation in Neural Networks

Abstract

When can a neural network reliably carry out multi-step symbolic computation? Correct predictions on canonical symbolic inputs are not sufficient, because intermediate neural representations may fall outside regions in which subsequent modules preserve the intended symbolic semantics. We study this problem for fixed encoders and deterministic decoders, characterizing correct execution by containment of reachable neural states in the intended decoder cells. We establish three main results. A multi-step inner-reachability certificate treats the endpoint as a function of the disturbance sequence and can detect full-dimensional reachable sets even when every individual disturbance is rank deficient. For bounded encodings with the norm, we obtain an exact closed-ball capacity bound and a matching finite-ReLU construction for arbitrary finite deterministic transition families, without a network-size constraint. Finally, polyhedral module certificates reduce compositional verification to linear optimization over activation regions. An explicit separation shows that identical canonical tables and identical global Lipschitz constants can coexist with different robustness properties. Outer-radius bounds and quantization-aware recurrences provide complementary sufficient conditions. Experiments with learned arithmetic modules distinguish canonical accuracy from representation robustness and terminal accuracy from pathwise correctness. Additional tests find correct sampled executions despite inconclusive regional inclusion checks, and full numerical rank in multistep endpoint Jacobians under low-rank disturbances, but no positive inner-radius estimate centered at the target encoding.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
Neural-symbolic computation, robustness, reachability analysis, compositional verification

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_MbSUOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies when neural modules preserve symbolic semantics through composition. It formulates correctness as containment of reachable neural states within the intended decoder cells and distinguishes canonical accuracy, terminal accuracy, and correctness throughout an execution.

The experiments examine modular arithmetic, representation perturbations, quantization, learned four-dimensional modules, and capacity attainment with fixed gates and learned translations.

Critical strengths

-- This paper connects a precise capacity bound to a constructive neural realization. -- The experiments demonstrate that high terminal accuracy can coexist with intermediate symbolic errors.

Critical weaknesses

-- Comparisons exist, but the local Lipschitz baseline uses interval masks and absolute-weight sensitivity propagation, which discard cancellations. Its failure does not establish an advantage over stronger local estimators.

-- No tested high-dimensional endpoint setting produces a positive target-centered inner-radius estimate, preventing application of the capacity theorem there. Successful learned regional certificates concern four-dimensional modules, with no complete three-operator family certified.

Questions for authors

see above

Reviewer_6cmcOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

This paper studies the conditions under which neural networks can be used to represent symbolic operations. It formulates the correctness problem as a variant of reachability analysis, and seeks to determine the conditions under which the network’s evolution matches the execution of the symbolic operation. The authors obtain a bound on the number of symbolic states that can be represented in a norm box under a given disturbance model. They then synthesize a network that attains this bound, demonstrating that the ideas from this work can be used for synthesis. Finally, they explore certificates for property satisfaction and evaluate their ideas on modular arithmetic networks.

Critical strengths
  • Addresses a real problem. Neural-symbolic systems are typically evaluated on canonical inputs, which say little about whether intermediate representations remain valid. Studying correctness beyond canonical accuracy is a worthwhile direction.

  • Reachability formulation. Framing correctness a reachability problem is a great way to frame the problem, and it connects neural-symbolic analysis to well-established verification tools.

  • Sythesis. Demonstrating that the ideas can be used to construct an efficient model for the problem is a useful contribution in and of itself.

Critical weaknesses
  • Poor exposition. The prose is laborious and relies on jargon that obscures the core results. The paper launches into dense formalism without first setting context, and the running example introduced in Section 2 is never used again in the main text.

  • Notation is not specified. Much of the notation is introduced in a compressed paragraph with full definitions deferred to the appendix. Key terms such as “inner-reachability radius” appear in the abstract without definition.

  • Weak motivation and no clear problem statement. The paper never clearly states the problem it solves or why it matters to practitioners. The results may be interesting, but they lack meaning without the necessary context.

  • Unclear contribution. Several of the main results are elementary. Theorem 1 essentially restates the definition of correctness, Theorem 4 counts disjoint ℓ∞ balls in a cube, and the construction in Proposition 1 amounts to a lookup table of local translations with unrestricted network size. The polytope certificate in Theorem 5 is standard activation-region verification, as the authors acknowledge.

  • Incomplete related work. There is no related-work section, and prior work is listed in a single paragraph without positioning the contributions against it. Closely related work on the computational power of analog neural networks and modern neural network verification tools is missing.

  • Weak experimental evaluation. The only certified learned modules are small 4–64–4 networks. The 128-dimensional modules are never certified by any method. Baselines are limited to global norm and interval bounds.

  • The paper is not self-contained. Most definitions, all proofs, and much of the experimental interpretation are deferred to the appendix, making the main text hard to parse on its own.

Questions for authors
  1. Can you state the problem formally in one place and explain why it matters to practitioners building neural-symbolic systems?

  2. Can you list the contributions explicitly and clarify which results are new versus restatements of standard facts?

  3. Can you define the notation in the main text before it is used, and give intuition for central objects such as Tube^π and the inner-reachability radius? Can you also use the running example in the main text?

  4. How does this work relate to classical results on the computational power of analog neural networks and to modern verification tools such as α,β-CROWN or Marabou?

  5. Why are the 128-dimensional modules never certified, and would stronger verifiers succeed where global norm and interval bounds fail? Can the certificates be demonstrated on larger or more realistic symbolic tasks?

1 comment

Thank you for the response. While your revisions address some of my concerns, they do not address my primary reservations about the work. The presentation still needs work, and the overall relevance of the work is not clear. For these reasons, I maintain my score.

Reviewer_48vHOpenReview ↗
Rating
2
Confidence
3
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies when neural modules preserve symbolic semantics under composition and perturbations. It characterizes correctness through reachable-set containment and develops outer-radius, inner-reachability, and polyhedral certificates. Its main result combines an exact closed-ball (\ell_\infty) capacity bound with a matching finite-ReLU realization of arbitrary finite deterministic transition families. Experiments on modular arithmetic examine representation robustness, regional verification, and capacity attainment in a model with fixed gates and learned translations.

Critical strengths
  1. A precise capacity result with a matching dynamic construction. Theorem 4 and Proposition 1 connect a sharp geometric packing bound to an actual neural implementation. The construction uses a shared encoder and decoder for arbitrary finite deterministic transition families and handles all admissible full-ball disturbance sequences through a prescribed horizon. This establishes more than static representability and gives a coherent characterization under the stated assumptions.

  2. Careful separation of empirical correctness and formal guarantees. The paper consistently distinguishes canonical accuracy from compositional robustness, outer bounds from reachable inner sets, and certificate failure from execution failure. The regional verification results also include fully trained four-dimensional networks with complete single-operator certificates, providing a concrete application beyond manually constructed networks.

Critical weaknesses

1. Tight representation capacity leaves the cost of robust computation unresolved.
Proposition 1 attains the packing bound through a separate gate for each symbolic state and transition-specific translations, without restricting network size. Its implementation can therefore grow exponentially with representation dimension, while regional certification also explicitly covers states or input tuples. The construction may simply transfer complexity from the encoding to the network and certificates. It establishes optimal geometric packing, but provides no corresponding efficiency result for compactly described symbolic systems. This substantially limits what capacity optimality tells us about scalable neural computation.

2. The successful capacity demonstration builds in the properties that make the analysis work.
Applying the framework requires informative inner-reachability bounds and suitable regions for compositional verification. Obtaining these certificates is itself a central difficulty. Yet the capacity experiment fixes the codebook, gates, and local dynamics, leaving only 64 translations with a closed-form optimum (Appendix A.33.8). Although some fully trained four-dimensional operators are certified, the 128-dimensional models obtain neither closure nor positive target-centered inner-radius estimates. Thus, the strongest capacity demonstration validates consequences of prescribed geometry, while the difficult step of obtaining useful geometric certificates for less structured learned systems remains unresolved.

Questions for authors

Scalability.
What mechanisms keep the guarantees informative and computationally tractable as the state space, dimension, and network size grow? Verification can involve NkN^k input tuples and exponentially many ReLU regions. The capacity experiment fixes the geometry, while the 128-dimensional models obtain neither closure certificates nor positive inner-radius estimates. Please specify the required structural assumptions, supported model classes, and scaling costs, distinguishing mechanisms established here from those requiring new techniques.

Comments on the paper

1 comment

Thank you for the response. The circuit-based construction strengthens the theoretical contribution, but my main concern remains practical applicability. Beyond the small-scale demonstrations, it remains unclear how useful geometric certificates can be obtained efficiently for learned systems. The response therefore does not sufficiently bridge the gap between the theoretical guarantees and practical use. I maintain my rating of 2 (Weak rejection).

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.