How Structural Automata Improve Neural Semantic Parsing Quality

The Structural Constraint Challenge in Neural Semantic Parsing

Neural semantic parsers generate meaning representations token by token, but whether an output is "well-formed" often depends on referential relationships, scope, and graph structure — constraints that unfold progressively during generation rather than being decidable at the level of a single token.

Traditional constrained decoding can mask locally invalid tokens at each step, but it has a fundamental flaw: even if the current prefix is valid, there is no guarantee that it can be completed into a fully valid structure within a fixed output length limit. In other words, the model may paint itself into a corner step by step, ultimately producing an incomplete structure that cannot be finished.

This research proposes using structural automata to systematically address this problem, validating the approach across three stages of DRS (Discourse Representation Structure) parsing — decoding, post hoc processing, and training — while also evaluating decoding performance on AMR (Abstract Meaning Representation) tasks.

DRS (Discourse Representation Structure) is a formal meaning representation rooted in Discourse Representation Theory, designed to capture sentence- and discourse-level semantics — including quantifier scope, coreference, and tense information — producing a nested logical graph structure. AMR (Abstract Meaning Representation) is another widely used graph-based semantic formalism that encodes "who did what to whom" as a rooted directed acyclic graph, with nodes representing concepts and edges representing semantic role relations. Both share a common characteristic: valid outputs must satisfy globally consistent graph structure constraints — for example, variables must be declared before being referenced, and dangling nodes are not permitted — constraints that are difficult to enforce with purely local rules during token-by-token generation, which is precisely the core problem this paper addresses.

Smatch++ (an enhanced version of Smatch) is the primary metric for evaluating graph-based semantic parsing results. It measures parsing quality by computing the optimal-alignment F1 score between predicted and reference graphs over nodes and edges — higher scores indicate closer agreement with the gold annotation.

Accepting-Path Decoding: Guaranteeing Completable Outputs

The central contribution of this research is the introduction of Accepting-Path Decoding (APD) at the decoding stage. Its design principle is straightforward: always maintain a verified completable path within the remaining length budget, while preferring the model's own token choices whenever they are also completable.

The key guarantee this mechanism provides is that APD ensures the final output is accepted by the automaton without needing to retract any already-generated tokens. This stands in sharp contrast to rollback-based methods, which must undo previously generated tokens when they reach a dead end.

Looking at the experimental results, under strict length constraints, APD outperforms local masking on the Smatch++ metric by:

• 5.1 and 2.4 points on DRS tasks
• 6.4 and 3.2 points on AMR tasks

More notably, APD achieves performance comparable to rollback methods under the same length constraints, while avoiding the additional overhead and complexity that rollback entails. This means a cleaner generation guarantee is obtained without sacrificing quality.

Structural automata here refer to a class of finite-state machines or their extensions (such as pushdown automata) whose state transition rules encode the valid structural constraints of the target meaning representation. During decoding, the automaton runs in parallel with the language model: each time a token is generated, the automaton simultaneously transitions states to track the structural state of the current prefix in real time. The key innovation of APD is that it does not merely query "is the current token valid?" — it also performs a lookahead query: "from the current state, does there exist at least one path leading to an accepting state within the remaining steps?" Only tokens satisfying this lookahead condition are retained in the candidate set. This forward-looking check is precisely what distinguishes it from traditional local masking, which can only eliminate currently invalid tokens but cannot prevent the model from walking into a structural dead end.

Post Hoc Processing: Invalid Outputs Are Highly Concentrated

The research also examines a strategy of unconstrained sampling followed by post hoc filtering, yielding a valuable observation: invalid outputs are highly concentrated on the same inputs.

Specifically, when sampling eight candidates from the model without constraints:

• With limited training data, 10.2% of inputs fail to produce any valid output;
• With full training data, this proportion drops sharply to just 0.4%.

When data is plentiful, a simple filtering strategy already comes very close to APD — the Smatch++ gap is within 0.2 points. This suggests that when the model is well-trained, the marginal benefit of complex structural constraint decoding diminishes; it is in low-resource settings that structural guarantee mechanisms like APD deliver their full value.

Training Stage: Diminishing Returns from Structural Penalties

The third finding comes from the training stage. The research experiments with penalizing tokens rejected by the automaton during training. Results show that after 10% of training, development set Smatch++ can improve by 3.6 to 11.0 points — a significant gain.

However, this advantage gradually disappears as training progresses. The reason is that cross-entropy loss inherently suppresses the probability of rejected tokens — under limited data conditions, the probability assigned to these tokens drops from 14% to below 2% within the first sixth of training.

This finding is quite instructive: the training signal from structural constraints largely overlaps with the learning objective of standard cross-entropy. As the model learns correct structure, it naturally learns to avoid invalid tokens. Explicitly introducing structural penalties during training therefore acts more like an "accelerator" — providing gains early on — but does not confer capabilities that cross-entropy cannot eventually reach on its own.

Overall Implications Across Three Stages

Taking the findings from all three stages together, a coherent conclusion emerges: the value of structural automata is highly dependent on resource availability and constraint conditions.

• At the decoding stage with tight length constraints, APD provides deterministic completion guarantees with the most pronounced benefits;
• In post hoc processing, the concentration of invalid outputs means filtering is sufficiently effective when data is abundant;
• At the training stage, the benefits of structural penalties are gradually absorbed by cross-entropy.

For practitioners building semantic parsing systems, this means strategies should be selected based on data scale and deployment constraints: prioritize APD in low-resource settings with strict length limits; when data is plentiful, lightweight post hoc filtering may be sufficient. This approach — treating "structural correctness" as a configurable module rather than a one-size-fits-all constraint — offers practical engineering guidance for neural structured generation.