acceptodds
Under review as a conference paper at ICLR 2027

Counterexample-Guided Discovery of Executable Semantic State Abstractions

Abstract

A semantic representation in a neural network may predict outputs without containing enough information to determine how it evolves through subsequent computation, and therefore need not define an independently executable high-level model. We study how to select the necessary state from given semantic variables and candidate auxiliary variables, and how to synthesize a high-level program that reproduces the transitions and specified outputs of a fixed computational system. Selecting an auxiliary variable also requires determining its successor, so additional features can destroy closure. We give a verifiable sufficient condition under which a dependency graph yields the unique least admissible state. Without this condition, minimum auxiliary-state selection is NP-complete for explicit finite tables even with an involutive transition and a constant response, and remains NP-hard on a rational box with quadratic supplied functions. State-pair and single-state counterexamples separate state insufficiency from program inexpressibility; for a fixed template affine in its unknown coefficients, exact synthesis needs at most verification calls. Cost-ordered search is optimal within the prescribed finite program class. With a positive verification margin, numerical synthesis terminates and yields finite-execution error bounds under certified domain invariance. Experiments on polynomial instances and ten trained networks demonstrate exact discovery, infeasibility certification, and a separation between greatest and minimum selections. Tests on finite-table systems isolate the auxiliary-update requirements behind minimum-state selection, while alternative feature libraries on the same frozen networks separate state sufficiency from program expressibility and exhibit multiple minimal selectors without a least one.

Primary area:
interpretability and explainable AI
Keywords:
Mechanistic Interpretability, State Abstraction, Program Synthesis, Formal Verification

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_gWrJOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper discusses how to find high-level state representations that can evolve independently, given semantic variables and candidate features. The key issue is that an auxiliary variable may help predict the output without being able to update itself from the retained state. Based on this, the authors distinguish between insufficient state information and insufficient program expressiveness, present results on state selection, program synthesis, and related complexity, and validate them on polynomial systems and small trained networks.

Critical strengths
  1. What is most interesting is the update requirement on the auxiliary variables themselves. It sets this problem apart from conventional feature selection, and it also explains why adding variables can break closure. Around this point, Theorems 6–8 provide structural conditions and a complexity analysis, which constitute the paper's main contribution.

  2. The paper is fairly clear about the scope of its conclusions. For example, the authors do not treat solver timeouts as infeasibility, and they explicitly distinguish the number of verification calls from the actual runtime cost.

  3. Some experiments speak directly to the core issue. In Experiment 4, once the auxiliary update constraint is removed, the selected states are no longer closed; Experiment 5 shows that feature representations carrying the same information can differ in expressive power under a given programming language. These comparisons help clarify the theoretical results.

Critical weaknesses
  1. It remains unclear how much practical discovery power these theoretical results actually provide. The network in Experiment 3 has only six dimensions, the connection mask is fixed in advance, and both the semantic variables and the candidate features are coordinate projections. Under this setting, determining which states need to be retained can essentially be done by inspecting the variable dependencies in the polynomial. The experiment validates the method, but it does not show what structure it helps uncover that is not already easy to see directly.
  2. The trained-network experiments use direct coefficient matching rather than the single-state counterexample-guided synthesis discussed in the paper. As a result, the experimental support for CEGIS comes mainly from the five small instances in Experiment 1. For these polynomial problems, which can be expanded directly, it is currently unclear what concrete benefit the counterexample-guided procedure offers over coefficient matching.
  3. The numerical part lacks empirical validation. Experiment 2 computes the size of the reference grid, but it does not run numerical synthesis, nor does it demonstrate certified errors for multi-step execution. This does not affect the theoretical termination results, but it remains to be seen whether the guarantees proposed in Sections 6–7 can yield useful error bounds on actual examples.
Questions for authors
  1. On the existing trained networks, how do the time and verification costs of running CEGIS compare with those of direct coefficient matching?
  2. Is there a small instance for which numerical synthesis and multi-step certification were run end to end? Are the resulting error bounds tight enough to support judgments about the outputs?
  3. Regarding Theorems 6–8, could the authors specify more concretely where the new technical difficulties lie relative to existing results on state aggregation and functional dependencies?
  4. There are two definitions that leave me somewhat confused, and I hope the authors can clarify them. First, Appendix K.4 defines the semantic variables and candidate features for Experiment 3, but it does not explicitly specify the response function r(x): is r(x) = x_0 being used here, or is only the state transition being tested without including a separate readout task? Second, what part of the original decoder state does rho in Equation (25) of Appendix L specifically correspond to? Is u_res the full residual vector or some component of it? Since the subsequent argument relies on two states that have the same u_res but different rho, it would be advisable to explicitly specify their correspondence to the original states.
Reviewer_rwGAOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

Summary: The paper proposes a counterexample-guided approach for synthesising executable programs that represents projections of a neural network.

Critical strengths

Strengths:

  • The paper tackles an interesting problem of transforming a neural network into an abstract, executable program, which can be more interpretable.
  • The paper contains mathematical formalizations for the core claims.
Critical weaknesses

Weaknesses:

  • Scalability of the approach is unclear.
  • The paper does not addess if the produced programs are more interpretable.
  • Limited experiments (10 neural networks) with no baseline comparisons.
  • The main content of the paper is notation heavy and some statements (e.g. Thm. 8 mixes claims, properties of the reduction, and remarks; Prop. 7 contains algorithmic details) are quite verbose.
Questions for authors

Questions:

  1. How does the interpretability of the synthesized programs compare to other neural network explanation approaches?
  2. How much time does a verifier call cost in experiments 1, 3, and 5?
  3. The minimal selectors are nonunique (see experiment 5). How does the interpretability compare among these programs?
  4. The verification only applies to the rationalized neural network. Could the gap to the actual neural network be bounded?
Reviewer_jGMjOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper asks a sharper version of a standard interpretability question. Usually, researchers train a probe on a network's internal activations. If the probe predicts a concept well, they say the network "represents" that concept. The paper argues this is too weak. A variable can predict the current output and still be too thin to drive the next step of computation. What matters is whether a set of variables can keep the computation running on its own.

The authors turn this into a precise problem. They assume a semantic mapping is already given, so the paper does not guess what variables mean. They fix a small library of candidate helper variables and a restricted program syntax. The task is to select which variables to keep, then write explicit update and readout formulas. The resulting high-level program must run using only its own state. It may not call the original network's transitions, its remaining decoder, or a learned surrogate. The program must reproduce the original transitions and outputs, and must be reproducible with a bounded error.

The main contribution is separating two failure types. One is insufficient state: the information is genuinely not retained. The other is inexpressible programs: the information is there, but the allowed formula class is too weak. The paper defines admissible selectors with unrestricted maps to measure state sufficiency alone, then checks formula availability separately. Failures come with certificates, not just poor fit scores.

Further contributions include a structural condition under which state selection reduces to dependency propagation, with a unique least state; NP-completeness and NP-hardness results showing the general selection problem is computationally hard; a counterexample-guided algorithm needing at most N+1 verification calls; and an exact synthesis bound of p+1 calls for templates affine in unknown coefficients. A numerical variant adds certified domain invariance and finite-horizon output error bounds.

Validation covers five experiments on exact finite instances and small trained polynomial networks: accepted programs, rejected instances with witness certificates, agreement with independently computed combinatorial optima, and comparisons across alternative feature libraries. No real language model is involved.

Critical strengths

The central strength is that the paper separates two failures that prior work reports as one. When a symbolic pattern cannot be recovered, it may be because the needed information is not retained, or because the chosen formula class is too weak. These say very different things about the model. The paper defines admissible selectors using unrestricted maps, so state sufficiency is judged on its own. It then checks whether a formula exists inside a restricted syntax. Because the two are judged separately, a negative result carries a clear attribution. This matters to me because it makes negative findings usable. Much interpretability evidence is only "the fit was poor," which supports no conclusion. Here a rejection comes with a verifiable certificate: an observed state pair, or a small contradictory equation system. A reader can check it. That raises the evidentiary standard for a literature that often relies on probe accuracy.

A second strength is that the formal results are tied to runnable procedures and then tested. Verification bounds are stated as call counts: at most N+1 for finding the largest admissible selection, and p+1 for exact synthesis when templates are affine in coefficients. The paper reports these counts against measured values. It also proves when selection is easy and when it is hard, locating the difficulty in a single requirement: keeping a helper variable forces you to update it too. Experiments isolate this factor directly, by replacing transitions with identity and by removing successor closure. Results agree with independently computed optima. The theory is therefore accountable rather than decorative.

Critical weaknesses

The major weakness is that the framework is never exercised on a real model. All evidence comes from small hand-built instances and six-dimensional polynomial networks. Transformer decoder execution appears only as a claim that it "can be represented" in this form. The paper itself concedes what would be needed first: a supported semantic mapping, certified extraction ranges, and expression verification for operations like softmax. Its own certificate machinery also depends on Lipschitz bounds and box inclusions that it states are not certified for pretrained decoders. This is not a missing experiment; it questions the framing. The guarantees hold inside deliberately restricted domains where exact checking is possible. The interpretability problems that motivate the work live outside those domains, where the guarantees likely cannot be delivered.

The second weakness is that all three inputs are supplied by hand: the semantic mapping, the candidate library, and the program syntax. The method cannot say which variables deserve attention, and a function absent from the library surfaces as inexpressibility rather than missing information. The promised separation between "not retained" and "not expressible" therefore depends on the quality of an unvalidated human choice. Relatedly, minimality is relative to a fixed syntax and a declared cost, so a smaller state is not shown to be a more understandable or more plausible explanation. The paper also observes that minimal selectors are often non-comparable and that a least one may not exist, which weakens the claim that this search recovers a network's actual state.

Questions for authors

The structural condition for dependency propagation is only sufficient, not necessary. This is acknowledged, but the paper gives no sense of how often the condition holds in practice.

The cost function is syntax-relative throughout, and the paper states explicitly that minimality is never over all equivalent real-valued programs. A brief concrete example where two equivalent programs rank differently under different syntaxes would make the limitation harder to overlook.

Unrolling a finite-horizon decoder into an acyclic graph makes the graph grow with the horizon. This interacts with the N+1 and p+1 bounds, and the total cost is not discussed.

Requiring a strict interior margin ε̄ may render the constraints infeasible even when a non-strict invariant would hold. A note on how often this bites, or an alternative formulation, would help.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.