Structural Automata for Neural Semantic Parsing

Xiao Zhang

cs.CLOct 9, 2026

Structural Automata for Neural Semantic Parsing

Authors: Xiao Zhang

Organizations: University of Groningen

Abstract

Neural semantic parsers generate meaning representations token by token, yet well-formedness depends on references, scope, and graph relations that unfold during generation. Constrained decoding prevents locally invalid tokens but does not guarantee that a valid prefix can be completed within a fixed output-length limit. We investigate structural automata at three stages of DRS parsing (decoding, post hoc processing, and training) and additionally evaluate decoding on AMR. For decoding, we introduce accepting-path decoding (APD), which maintains a verified completion within the remaining length limit and follows the model's preferred token whenever that token can also be completed. APD guarantees an accepted output without retracting tokens. Under tight length limits, it improves Smatch++ over local masking by 5.1 and 2.4 points on DRS and by 6.4 and 3.2 points on AMR, comparable to rollback under the same limit, which retracts tokens. For post hoc processing, invalid outputs concentrate on the same inputs: eight unconstrained samples yield no valid output for 10.2% of inputs with limited training data, compared with 0.4% with full data, where filtering comes within 0.2 Smatch++ points of APD. For training, penalizing automaton-rejected tokens improves development Smatch++ by 3.6-11.0 points after 10% of training, but this advantage diminishes as cross-entropy alone reduces the probability assigned to rejected tokens from 14% to below 2% within the first sixth of training with limited data.

Figures & tables

Figure 1: A shared structural automaton across three stages of DRS parsing. During training, it identifies rejected next tokens; during decoding, it keeps a verified completion within the remaining output budget; after generation, it validates, filters, or completes candidates. Each stage is characterized by one quantity: the rejected-token mass $m_{t}$ , the verified completion length $|w|$ (an upper bound on the distance to acceptance), and the per-input failure tail.

Figure 2: Fragment of the SBN structural automaton. Forward references create pending targets that must be resolved before acceptance.

\bot

is the absorbing rejection state and

\Sigma

the token alphabet.

$H$	W	WF	W+Roll.	APD
68	86.27 (93.5)	91.26 (99.9)	91.27 (100)	91.33 (100)
78	89.28 (96.8)	91.61 (99.8)	91.69 (100)	91.72 (100)

Table 1: Same-budget test macro Smatch++ (graph validity %). Each arm has all 1,132 inputs. W and W+Rollback share one W trajectory decoded at

H=320

; WF and APD also require accepting EOS.

Tom shook everybody’s hands. budget $H=58$
Gold	male.n.02 Name "Tom" NEGATION <1 person.n.01 NEGATION <1 shake.v.09 Agent -2 Time +1 Patient +2 time.n.08 TPR now hand.n.01 PartOf -3
$W$	… shake.v.01 Agent -2 Patient -1 Time +1 time.n.08 TPR now CONTINUATION <0 person.n.01 hand.n.0 cut off
Reserve $r{=}16$	… shake.v.01 Agent -2 Patient -1 Time +1 time.n.08 TAB ? placeholder inserted
APD	… shake.v.01 Agent -2 Patient -1 Time +1 time.n.08 TPR now CONTINUATION <1 person.n.01 EQU -3 valid within budget

Table 2: Example under the tight budget

H=58

. The local mask is truncated, the fixed reserve closes early with a placeholder, and APD retains more model-generated content while remaining within budget.

Method	600 graphs	1,256	9,057
U	61.23 (23.9)	73.19 (13.4)	88.86 (4.4)
W	75.24	81.29	91.88
APD	76.46	81.68	91.97
Close	74.53	80.73	91.54
Sample	69.63	80.59	91.81
Beam	73.05	81.43	91.39

Table 3: Test Smatch++ at

H=320

(

N=1{,}132

), with the invalidity of U (%) in parentheses. Sample/Beam leave 10.2/8.4%, 2.5/3.2%, and 0.4/1.6% of inputs invalid; development results are in Appendix E .

Figure 3: Unresolved test inputs (

N=1{,}132

). Upper: failure among

k

candidates, averaged over size-

k

subsets of eight stored samples. Lower: observed eight-sample tails (circles, Wilson 95% intervals) versus

p^{8}

(open diamonds), where

p

is the mean sample failure probability. Colors denote parsers trained on 600, 1,256, and 9,057 gold graphs.

First rejected token	600	1,256	9,057
lexical or syntactic	116	51	9
forward reference unresolved	46	21	13
graph cycle	45	25	2
reference out of range	39	28	8
accessibility (Referee)	11	2	3
proposition box missing	10	7	0

Table 4: First structural failures of unconstrained development outputs. Only the lexical or syntactic row is visible to a context-free grammar.

Figure 4: Rejected-token mass at gold prefixes among top-32 tokens (600 training graphs). Left: full training (log scale); right: first 25% (linear). CE/UL show five seeds (thin), means (thick), and min–max bands; masked likelihood uses one seed.

Appendix figures & tables17 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 5: Withholding new completions after initialization (

H=68

, test

N=1{,}132

): (a) graph validity, (b) Smatch++, and (c) APD-minus-WF gain, split into common-valid change and rescue, with paired 95% intervals on the total (Appendix A ).

$H$	Wh.	Method	$L$	$R$	$s_{L}$	$s_{R}$	EOS	Fail
68	0	W	1,058	1,058	86.27	86.27	1,033	0
68	0	W+Rollback	1,132	1,131	91.27	91.20	1,132	0
68	0	WF	1,131	1,129	91.26	91.12	1,131	1
68	0	APD	1,132	1,130	91.33	91.19	1,132	0
78	0	W	1,096	1,096	89.28	89.28	1,082	0
78	0	W+Rollback	1,132	1,131	91.69	91.62	1,132	0

Appendix

Table 5: All matched test conditions,

N=1{,}132

per row. Wh. is the fraction of new completions withheld after initialization.

L

and

R

count valid outputs under the two validity policies, and

s_{L}

and

s_{R}

are the corresponding Smatch++ scores. EOS counts outputs ending in an accepting EOS; Fail counts decoder stops. W and W+Rollback share one W trajectory decoded at

H=320

$H$	Wh.	Baseline	Exact	$\Delta_{L}$ [95% CI]	$\Delta_{R}$ [95% CI]
68	0	W	1,033	5.053 [3.938, 6.233]	4.912 [3.790, 6.106]
68	0	WF	1,131	0.066 [0.000, 0.199]	0.066 [0.000, 0.199]
68	0	W+Rollback	1,058	0.057 [0.016, 0.104]	$-$ 0.016 [ $-$ 0.189, 0.092]
78	0	W	1,082	2.445 [1.672, 3.293]	2.320 [1.568, 3.140]
78	0	WF	1,130	0.117 [0.000, 0.296]	0.117 [0.000, 0.296]
78	0	W+Rollback	1,101	0.039 [0.015, 0.067]	$-$ 0.018 [ $-$ 0.150, 0.060]

Appendix

Table 6: Paired Smatch++ differences, APD minus baseline, in points, over all 1,132 inputs with paired bootstrap intervals. Exact counts byte-identical outputs.

\Delta_{L}

and

\Delta_{R}

use validity policies

L

and

R

$H$	Baseline	Policy	Counts	Common	Rescue	Lost
68	W	$L$	1058/74/0/0	$-$ 0.065	5.119	0.000
68	W	$R$	1057/73/1/1	$-$ 0.062	5.050	$-$ 0.077
68	WF	$L$	1131/1/0/0	0.000	0.066	0.000
68	WF	$R$	1129/1/0/2	0.000	0.066	0.000
68	W+Rollback	$L$	1132/0/0/0	0.057	0.000	0.000
68	W+Rollback	$R$	1130/0/1/1	0.057	0.000	$-$ 0.073

Appendix

Table 7: Decomposition of the APD-minus-baseline difference in Smatch++ points, each term divided by all 1,132 inputs. Counts list common-valid/rescued/lost/neither inputs; the three contributions sum to the total difference.

$H$	Wh.	Method	Requests	Withheld	Unknown	Construct	Carry	Replan	Proposal s	Gen. s
68	0	WF	99,607	0	50,298	100,739	–	–	119.7	3,633.2
68	0	APD	109,586	0	73,648	110,718	14,504	35,938	95.6	3,609.7
78	0	WF	88,264	0	38,220	89,396	–	–	166.8	3,704.5
78	0	APD	73,771	0	37,265	74,903	14,673	36,506	139.8	3,666.4
68	.25	WF	8,504,965	2,126,385	8,453,636	6,379,712	–	–	11,523.6	19,784.1
68	.25	APD	539,670	134,743	497,821	406,059	15,687	41,849	505.4	4,928.9

Appendix

Table 8: Proposer operations of WF and APD, as totals over the test set, including 1,132 initial constructor calls per row. Carry and Replan count APD’s token decisions along its owned completion and with a newly certified completion. Times are in seconds, summed over inputs.

$H$	Wh.	Returned	Median	p95	Max	Changed/decisions	Slack ch./unch.
68	0	37,070	4	11	26	316/50,442	0/41
78	0	37,638	4	11	27	195/51,179	2/51
68	.25	42,981	4	11	36	14,254/57,536	35/39
68	.50	45,461	5	14	41	27,510/62,432	34/36
68	.75	40,681	5	16	47	37,145/61,738	34/37

Appendix

Table 9: APD certificates and decisions. Returned counts all verified completions, including initial ones; lengths are in native tokens. Changed counts decisions that differ from the model’s top token; the last column gives the median remaining budget for changed and unchanged decisions.

	$H=348$		$H=411$
Method	F1	V%	F1	V%
P (local mask)	69.76	90.4	73.34	95.1
$r{=}2$	70.82	91.9	73.89	96.0
$r{=}4$	74.57	97.6	75.67	98.7
$r{=}8$	76.15	100	76.52	100
$r{=}16$	76.06	100	76.49	100

Appendix

Table 10: AMR test Smatch++ (validity %),

N=1{,}898

. Close after may exceed the budget.

Rate	WF	APD	$\Delta$ [95% CI]	Fail
.25	20.35	23.14	2.79 [2.10, 3.47]	19
.50	4.60	6.82	2.22 [1.76, 2.70]	17
.75	0.66	1.65	0.99 [0.71, 1.29]	41

Appendix

Table 11: AMR test Smatch++ with new completions withheld after initialization (

H=348

). Fail: WF stops.

Figure 6: Test validity and Smatch++ under output budget

H

(

N=1{,}132

), from the original, independently decoded budget study (Appendix C ). The reserve stops W 16 tokens early.

$H$	Baseline	$\Delta_{\mathrm{valid}}$	$\Delta_{\mathrm{rescue}}$
68	$W$	$-0.071$ $[-0.117,-0.030]$	$+5.009$ $[3.894,6.175]$
	$r=16$	$+1.307$ $[1.129,1.492]$	$+0.163$ $[0.000,0.380]$
78	$W$	$-0.025$ $[-0.052,-0.001]$	$+2.331$ $[1.584,3.147]$
	$r=16$	$+0.555$ $[0.448,0.668]$	$+0.164$ $[0.000,0.378]$

Appendix

Table 12: APD-minus-baseline contributions to macro Smatch++ in points, with paired 95% intervals below. Each contribution is divided by the full

N=1{,}132

, and the two terms sum to the total gain.

	$H=58$			$H=68$			$H=78$			$H=100$
Arm	F1	V%	PH	F1	V%	PH	F1	V%	PH	F1	V%	PH
$W$	80.44	86.9	2	86.44	93.6	2	89.47	97.0	2	91.37	99.1	2
$r{=}2$	80.84	87.8	20	86.22	93.5	11	89.30	96.7	4	91.43	99.2	3
$r{=}4$	84.47	92.4	76	87.80	95.5	37	90.08	97.7	18	91.61	99.5	3
$r{=}8$	85.91	95.0	149	89.10	97.5	74	90.51	98.5	42	91.62	99.5	7
$r{=}16$	86.58	98.9	322	89.91	99.7	162	91.05	99.7	81	91.82	99.8	20

Appendix

Table 13: Original test budget study. Each horizon has separate columns for macro Smatch++ (F1), validity (V%), and the number of outputs containing constructed placeholders (PH). Close after may exceed the budget.

Figure 7: Test Smatch++ change from CE to UL training (

N=1{,}132

), without constraints (circles) and under the local mask (squares). Diamonds mark five-seed means at 600 graphs; the larger settings have one run each. Adapters are selected by development loss.

Figure 8: Development learning curves for CE and UL training. Bands show the range over five seeds at 600 graphs.

Method	600 graphs	1,256	9,057
U	63.09 (23.6)	76.10 (11.8)	90.64 (3.1)
W	77.86	83.68	92.56
APD	78.81	84.08	92.84
Close	77.32	83.28	92.54
Sample	72.22	82.87	92.62
Beam	74.81	83.08	92.54

Appendix

Table 14: Development macro Smatch++ at

H=320

(

N=1{,}132

). Parentheses give U invalidity (%).

Graphs	Unresolved	Tail % [95% CI]	$\rho$ [95% CI]
600	115	10.16 [8.53,12.06]	.273 [.250,.296]
1,256	28	2.47 [1.72,3.55]	.261 [.236,.285]
9,057	5	0.44 [0.19,1.03]	.278 [.238,.316]

Appendix

Table 15: Test eight-sample tail and within-input correlation. Tail intervals are Wilson; correlation intervals use an input bootstrap.

State component	Condition tracked
lexical phase	concept and role syntax; constant and operator syntax
concept register	backward targets already exist
pending targets	forward targets are stored and must be resolved at EOS
box register	references are range-checked; required proposition boxes must exist at EOS
typed graph	cycles are rejected on insertion; connectedness is required at EOS
accessibility	Referee-style box-subordination closure remains loop-free

Appendix

Table 16: State maintained by the SBN structural automaton. Lexical syntax is local; other conditions depend on the evolving representation.

Graphs	$N$	Automaton	Type/struct	Signature
Gold	2,264	2,264	2,264	2,105
$U$	1,132	1,082	1,092	1,018
$W$	1,132	1,130	1,130	1,052
WF	1,132	1,132	1,131	1,053
APD	1,132	1,132	1,131	1,053

Appendix

Table 17: Independent check on gold development and test graphs and on the full-data test outputs at

H=320

. Counts are accepted graphs; Type/struct and Signature are the two Referee checks.

Explore similar work

Aug 28, 2026cs.AI

Stay Within Your Bounds: Distance-Guided Decoding for Guaranteed Context-Free Grammar Compliance

Grammar-constrained decoding helps large language models produce syntactically valid structured outputs, such as code, JSON, and SQL. For context-free grammars, many practical decoders enforce local prefix feasibility: each token must keep the current prefix extendable to some valid completion. Yet, under tokenizer-grammar mismatch and finite token budgets, feasible prefixes may still fail to reach acceptance. We propose a lookahead-guided decoding framework for context-free grammars based on pushdown automata. Offline, we compute bounded pushdown summaries with reachability labels and upper-bound distances to acceptance. Online, these estimates guide horizon-aware pruning and beam search. The resulting decoder is syntactically sound: every output is accepted by the target grammar. Experiments on JSON, SQL, and Linear Temporal Logic (LTL) show both consistent syntactic validity and improved completion quality over existing baselines.

Vincenzo Collura, Karim Tit, Eleonora Giunchiglia +2

University of Luxembourg, Luxembourg · Imperial College London, United Kingdom

Constrained Decoding Grammar-Constrained Decoding

Ask PDF

Apr 28, 2026cs.CL

Structural Generalization on SLOG without Hand-Written Rules

Structural generalization in semantic parsing requires systems to apply learned compositional rules to novel structural combinations. Existing approaches either rely on hand-written algebraic rules (AM-Parser) or fail to generalize structurally (Transformer-based models). We present an alternative requiring no hand-written compositional rules, based on a neural cellular automaton (NCA) with a discrete bottleneck: all compositional rules are learned from data through local iteration. On the SLOG benchmark, the system achieves an overall accuracy of

67.3 \pm 0.2\%

across 10 seeds (AM-Parser:

70.8 \pm 4.3\%

), with 11 of 17 structural generalization categories at

100\%

type-exact match, including three where AM-Parser scores

0

74\%

. Analysis reveals that all 5,539 failure instances reduce to exactly two mechanisms: novel combinations of wh-extraction context with reduced verb types, and modifiers appearing on the subject side of verbs. When we decompose results by CCG structural features, each sub-pattern either succeeds on all instances or fails on all. Intermediate scores (e.g.,

41.4\%

) are mixtures of structurally distinct CCG patterns, not partial generalization. These results suggest that CCG directed types provide higher resolution than SLOG's phenomenon-level categories for characterizing structural generalization, and that the success/failure boundary is determined by the coverage of directed operations in the training data.

Zichao Wei

Saarland University

Neural Cellular Automata Semantic Parsing Compositional Generalization

Ask PDF

Aug 12, 2026cs.AI

Trie Automata for Constrained Decoding over Large Finite Sets

Large language models increasingly need to generate structured outputs that conform to predefined schemas, with one common constraint being selection from a finite set of valid strings. Current constrained decoding systems handle this through general-purpose grammar compilation, which becomes prohibitively slow as the number of valid values grows into the thousands, a cardinality wall. We introduce the trie automaton, a specialized mechanism that exploits finite-set structure (shared prefixes, bounded depth, known cardinality) via Aho-Corasick multi-pattern matching to precompute per-node token masks. The trie achieves 7X faster per-step valid-token computation (0.65 us vs. 5.8 us) compared to XGrammar, one of the primary backends in vLLM and SGLang, and 2--6.5X faster compilation at K >= 300. Because precomputed masks enable a stateless serving path that bypasses the guided decoding pipeline, this advantage compounds in batch serving: end-to-end vLLM throughput reaches 219 req/s vs. XGrammar's 7.5 req/s at batch size 256 (29X). The 29X combines the algorithmic speedup with integration-path savings that only precomputed masks can unlock. Across seven tokenizer families (32K--262K vocabulary), the trie maintains sub-100ms compilation up to K = 10,000 and flat per-step cost regardless of set size, while guaranteeing 100% output validity.

Xingzi Xu, Karim Bouyarmane

Amazon

Constrained Decoding LLM Inference Acceleration

Ask PDF