Structural Automata for Neural Semantic Parsing

1 Introduction

• Structural dependencies include references, variable binding, scope, and graph relations, so a grammar-accepted sequence can still violate graph-level constraints.A prefix may be locally valid yet impossible to complete within the remaining output budget.Source: §1 · p. 1
• The paper applies one structural automaton to DRS decoding, post-generation validation and repair, and training-time identification of invalid next tokens.These stages are assessed through distance to acceptance, per-input failure tail, and rejected-token mass, respectively.Source: §1 · pp. 1–2
• APD maintains a verified completion within the remaining budget, follows the model’s preferred token when it remains completable, and guarantees acceptance without retracting emitted tokens.The contribution list describes the DRS automaton as operating directly on subword tokens and supporting transitions, acceptance checks, and verified completion.Source: §1 · p. 2
• 5.05 and 2.44 Smatch++ points on DRS, and 6.44 and 3.20 on AMR: APD improves over local masking under two tight budgets, with same-budget rollback comparable but retracting up to 27 tokens.When new completions are withheld, per-step viability fails on 29–70% of DRS inputs, while APD completes every input using its verified completion.Source: §1 · p. 2

2 Related Work

• Grammar constraints keep prefixes extendable to some valid output, while distance-guided decoding adds a budget and witness continuation for context-free grammars; APD targets non-context-free SBN dependencies.APD separates completion proposal from exact verification and retains a verified, budget-feasible fallback.Source: §2 · p. 2
• Post hoc selection filters well-formed candidates, while IterGen and DTV backtrack after failed checks and retract emitted tokens; this paper compares filtering with constructive completion.Filtering cost grows with an input’s rate of invalid samples.Source: §2 · p. 2
• Unlikelihood and margin losses discourage undesirable continuations, while grammar masks and symbolic losses add structural constraints to learning objectives; the paper asks what they add beyond likelihood training.Its analysis relates training effects to probability mass assigned to rejected tokens.Source: §2 · p. 3
• Neural DRS parsers commonly generate linearized representations and check well-formedness after generation, while DRS validity also depends on references, scope, accessibility, and graph structure.Constrained decoding has shown particular benefits for semantic parsing with little training data.Source: §2 · p. 3

3.1 Distance to acceptance

• A state is b-viable when its minimum completion length fits the remaining budget; local masking prevents rejected transitions but does not ensure this condition.The proposer constructs a suffix and verifies it by replaying it through the automaton, certifying viability without computing the exact distance.Source: §3.1 · p. 3

3.2 An SBN structural automaton

• The SBN automaton tracks structural dependencies such as unresolved forward references, box structure, typed graph relations, and accessibility until the output is accepted.A forward reference creates a pending target; introducing a later concept resolves it, while EOS is rejected before resolution.Source: §3.2 · p. 3

3.3 Decoding

• Accepting-path decoding keeps a verified completion within the remaining budget, follows a higher-ranked token when that token has a certified completion, and otherwise advances along its owned completion.This preserves an accepted output within budget without retracting emitted tokens, given an initial certificate; unlike fresh-viability decoding, it retains a fallback if new certificates cannot be found.Source: §3.3 · p. 4

3.4 Post hoc processing

• Post hoc sampling and beam filtering return an invalid output when every candidate is invalid, whereas Close repairs from the first rejected token using a certified completion.W+Rollback similarly closes a generated prefix with a certified suffix, retracting tokens when needed.Source: §3.4 · p. 5
• Filtering difficulty depends on how invalid outputs concentrate across inputs: repeated independent sampling can leave high-failure inputs unresolved, so mean invalidity understates the failure tail.Under the beta-distributed failure model, concentration turns exponential decay of independent failures into polynomial decay.Source: §3.4 · p. 5

3.5 Training

• Unlikelihood training adds a penalty for probability mass on rejected candidates to cross-entropy, while masked training removes those candidates from the softmax and leaves inference needing a mask.The unlikelihood gradient diminishes as rejected-token mass falls; cross-entropy also lowers probability on non-gold tokens, including rejected ones.Source: §3.5 · p. 5

• Experiments vary the amount of gold supervision and the output budget.Source: §4 · p. 5
• The data are gold English PMB 5.1 SBN graphs, with 9,057 training, 1,132 development, and 1,132 test examples; smaller training subsets contain 600 and 1,256 graphs.The automaton accepts every gold development and test graph.Source: §4 · p. 5
• Models fine-tune Qwen3.5-0.8B-Base with rank-16 LoRA, select checkpoints by development loss, and use greedy decoding except for width-4 Beam and eight-output Sample.Decoding and post hoc experiments use one adapter per supervision level; the training comparison uses separate CE and UL adapters.Source: §4 · p. 6
• Budgets count native tokens including EOS: the default H = 320 is about 1.3 times the longest gold output, while the budget study tests H = 58, 68, 78, 100, and 256.H = 68 and H = 78 correspond to the 90th and 95th percentiles of gold test length.Source: §4 · p. 6
• Validity is automaton acceptance, while semantic quality is example-macro Smatch++ with exact alignment and invalid outputs or decoder failures scored as zero.The evaluation also reports a Referee-check sensitivity score, constructed-placeholder counts, and paired bootstrap 95% intervals.Source: §4 · p. 6

5.1 Decoding

• At H = 68 and 78, APD beats W by +5.05 and +2.44 Smatch++ points on DRS; on AMR, it beats the local mask by +6.44 and +3.20 at H = 348 and 411.The DRS comparison is from the same-budget test study; the AMR gains come from rescued graphs.Source: Table 1 · p. 6, §5.1 · p. 6
• When new completions are withheld, APD completes all 1,132 inputs and exceeds WF by 21.79, 25.04, and 27.62 Smatch++ points at withholding rates .25, .50, and .75.Same-budget rollback reaches nearly the same scores, but retracts 567 and 300 emitted tokens across 99 and 50 outputs.Source: §5.1 · p. 6

5.2 Post hoc processing

• At H = 320, APD beats Close by +1.93 points with 600 graphs and Sample by +0.16 with 9,057 graphs; the latter confidence interval includes zero.APD returns a valid graph for every input; the strongest post hoc method changes from Close to Beam and then Sample as supervision grows.Source: §5.2 · p. 6, Table 3 · p. 7
• Eight samples leave 10.2%, 2.5%, and 0.4% of inputs unresolved—13, 168, and more than 105 times independent-failure expectations—as failures cluster by input.With 600 graphs, 18.9% of the longest quartile has no valid sample, against 6.2% of the shortest; all five unresolved inputs at 9,057 graphs were already unresolved at 600.Source: Figure 3 · p. 7, §5.2 · p. 7

5.3 Training

• After 10% of training, UL leads CE in development Smatch++ by 3.6, 11.0, and 3.9 points across the three supervision levels; CE lowers rejected-token mass from about 14% to below 2% within the first sixth.With 600 and 1,256 graphs, UL reaches the final CE checkpoint's validity and Smatch++ within 35–50% of the steps; final test effects vary across seeds.Source: §5.3 · pp. 7–8

6 Discussion

• When the output budget can bind, APD completes every graph within budget; rollback reaches similar quality only when emitted tokens may be revised.With full training data, filtering comes within 0.2 points of APD; with 600 graphs, eight samples leave 10.2% of inputs without a valid output.Source: §6 · p. 8
• Training feedback helps early while rejected-token mass is high, complementing decoding by shaping the model at gold prefixes while decoding governs its own prefixes.Source: §6 · p. 8
• APD keeps emitted tokens for streaming or interactive parsing, but bounded decoding matters most for representations with long-range requirements; AMR closures took at most eight tokens, while SBN closures took up to 40.APD ran about as fast as WF in the reported test, and both were about 30–40% slower per graph than unconstrained greedy decoding.Source: §6 · p. 8

7 Conclusion

• At the three DRS stages, the relevant quantities are distance to acceptance, inputs rarely parsed validly, and rejected-token mass.Source: §7 · p. 8
• Given an initial certificate, APD reaches an accepted output within budget without retracting tokens, and completes budget-truncated graphs on DRS and AMR while matching same-budget rollback.Source: §7 · p. 8
• Extending APD to sampling and checking bounded viability lazily along unconstrained prefixes are identified as next steps; constraint placement depends on the structural failure that remains.Source: §7 · p. 8

Limitations

• The three-stage analysis covers English DRS in SBN with one Qwen3.5-0.8B model finetuned with LoRA; AMR is evaluated only for decoding.Other meaning representations, languages, and larger or prompted models remain to be tested.Source: Limitations · p. 9
• All constrained decoders are greedy; lazy masking also applies to sampling with shared noise, but not to beam search.Supervision levels use random subsets of gold data rather than naturally low-resource corpora; 600-graph results vary across seeds, while larger training settings have one run each.Source: Limitations · p. 9
• Automaton acceptance is broader than the upstream CLF checker, and structural validity does not guarantee semantic correctness.The automaton accepts some punctuation-initial lemmas and x-type senses that the checker rejects; incremental rejection is not a complete coaccessibility test.Source: Limitations · p. 9

A Matched Decoding Study

• Against W, APD’s gain comes from rescued outputs; against WF, it comes from the one or two inputs where WF stops.Withheld proposals add gains from rescued inputs and from inputs both decoders complete; rollback scores are close to APD’s, and its small policy-L margins disappear under policy R.Source: A Matched Decoding Study · p. 11
• Across 18 conditions, the independent check rejects 628 automaton-accepted outputs: 534 for lexical format, 93 for other reasons, and one conversion failure.Policy R scores these rejections as zero.Source: A Matched Decoding Study · p. 11

B AMR Decoding Study

• APD and WF produce identical outputs on all 1,898 AMR test graphs; same-budget rollback retracts 677 and 348 tokens across 184 and 95 outputs at the two budgets.Close-after can exceed the budget by up to 7 and 8 tokens.Source: B AMR Decoding Study · p. 11
• With new completions withheld, APD completes every AMR input and leads WF at every withholding rate, although both decoders’ scores fall sharply.AMR outputs average about 200 tokens; APD closes each graph along its owned completion after replacements are withheld.Source: B AMR Decoding Study · p. 11

C Budget Study Details

• Against r = 16, most of APD’s gain comes from the 1,129 inputs valid under both methods, where APD keeps model content that the reserve replaces.Against W, the gain instead comes from rescued outputs.Source: C Budget Study Details · p. 12
• On graphs W completes, APD and W have nearly identical output lengths: 42.93 and 42.96 tokens at H = 68, and 44.14 and 44.17 at H = 78.On rescued inputs, W exhausts the budget, while APD averages 66.75 and 76.88 tokens and ends with an accepting EOS.Source: C Budget Study Details · p. 12

D Training End-point Details

• For 600 graphs, the unconstrained change spanned −2.39 to +5.92 points; three seeds were significantly positive and one significantly negative, while the local-mask change was −0.59.At 1,256 and 9,057 graphs, unconstrained changes were −0.15 and −0.27, while APD changes were +0.37 and −0.16; intervals included zero.Source: D Training End-point Details · p. 13
• For the 600-graph seed with the largest unconstrained gain, APD yields +1.28 development Smatch++ points and +0.83 test points.The development interval is 95% CI [0.71, 1.84].Source: D Training End-point Details · p. 13
• On test, the five 600-graph seeds change by +0.74 Smatch++ points on average without constraints and −0.58 under W.At 1,256 and 9,057 graphs, unconstrained test changes are +0.87 and +0.33, while the corresponding development changes are negative.Source: D Training End-point Details · p. 14
• Masked likelihood scores 3.23 without the mask at inference and 76.80 with it, versus 77.86 for standard training under W.Source: D Training End-point Details · p. 14

E Development Results and Failure Analysis

• Only 3–24% of outputs with a rejected token need constrained regeneration; the rest need only a validity check.For 429 of 436 development outputs with a rejection, the constrained and unconstrained decoders share the entire prefix before the first rejected token.Source: E Development Results and Failure… · p. 14
• After eight samples, unresolved development inputs are 8.8%, 2.6%, and 0.6%, while observed test failure rates are 10.16%, 2.47%, and 0.44% across supervision levels.The test tail is reported with Wilson intervals.Source: E Development Results and Failure… · p. 14, Table 15 · p. 15
• At full supervision, 64% of first test failures are invisible to a context-free grammar, and first failures occur at median output positions of 71%, 80%, and 89%.Failure types include forward-reference errors, out-of-range references, missing proposition boxes, cycles, and accessibility violations.Source: E Development Results and Failure… · p. 14
• Non-context-free failures account for 57%, 62%, and 74% of development first failures; Close inserts placeholders in 133, 61, and 20 outputs versus APD’s 12, 8, and 1.Source: E Development Results and Failure… · p. 15

F.1 Transitions and acceptance

• The SBN automaton checks concept surface forms locally, tracks references and box relations as edges are added, and requires resolved targets, required boxes, and graph connectivity at EOS.Source: §F.1 · pp. 15–16
• The independent type-and-structure Referee check accepts all 2,264 gold development and test graphs, while its official operator-signature check rejects 159 gold graphs.The signature check is reported separately because its inventory lacks some operators.Source: §F.1 · p. 16, Table 17 · p. 16

F.2 Completion proposer

• The proposer constructs a suffix from requirements recorded in the current state, then verifies replay and budget fit before APD stores it as a certificate.Construction can return unknown; APD replays any returned suffix again before storing it.Source: §F.2 · pp. 16–17

F.3 Initialization, repair, and training labels

• From the empty state, the proposer’s entity.n.00-plus-EOS suffix is APD’s initial certificate when it fits H; Close repairs invalid outputs by replacing content after a certified prefix.Training labels replay gold prefixes through the same transitions and disable structural loss after a rejected gold prefix.Source: §F.3 · p. 17

F.4 Training and runtime

• Withheld completions are tested at rates 0.25, 0.50, and 0.75 using a deterministic hash; initialization, cache hits, and owned completions are exempt.Source: §F.4 · p. 17
• Checking the top 32 candidates adds 0.26 s per step with 600 graphs and 0.92 s with 9,057; W and APD run 30–40% longer per graph than greedy decoding.Source: §F.4 · p. 17

G Proofs

• Given an initial certificate, APD reaches an accepting state within budget while retaining every committed token, even if the proposer returns an unknown proposal.Source: G Proofs · p. 17
• Lazy masking matches deterministic masked decoding through the first rejected greedy token; if greedy output is entirely accepted, both outputs coincide.Source: G Proofs · p. 17