- 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
-
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.
-
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.
-
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
- 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.
- 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.
- 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
- On the existing trained networks, how do the time and verification costs of running CEGIS compare with those of direct coefficient matching?
- 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?
- 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?
- 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.