Normative rules like institutional charters and workplace policies must be both human-readable and operationally verifiable against actual environment records. However, current language generation and structured-output benchmarks primarily reward surface fluency or schema compliance, leaving operational grounding weakly tested. This creates a critical vulnerability where standard language models generate plausible-sounding policies that fail during enforcement because they rely on unavailable data logs or misaligned scopes. To address this challenge, we formalize the problem as Grounded Normative Rule Synthesis (GNRS) and introduce GNRS-Search, a framework that utilizes Markov Chain Monte Carlo (MCMC) sampling to optimize a discrete, five-slot And-Or Graph (AOG). By explicitly decoupling intermediate operational structure from final prose generation, this method isolates executable feasibility from writing style and allows rule failures to be localized prior to surface realization. We evaluate our approach on GNRS-Bench, a benchmark spanning 116 controlled goals across eight scene families, and RealCharter-Bench, which evaluates transfer to 53 real-derived policy tasks with hidden source clauses. GNRS-Search raises average rubric quality from 68.8% to 81.0% and ranks first under a disclosed executable composite metric, while systematic slot interventions confirm that performance gains stem from robust operational logic rather than rhetorical tuning. Ultimately, by transforming automated rule drafting into an inspectable search problem, this work provides a foundational paradigm for deploying verifiable and compliance-ready personal agents within regulated environments.
Figures & tables
Figure 1: Normative rules must be both readable and operationally grounded. Direct prompting often satisfies the surface-language requirement but introduces unsupported evidence channels or vague enforcement procedures. GNRS-Search addresses this by searching over a five-slot operational structure, covering scope, trigger, norm body, evidence, and procedure, before rendering the selected structure into natural language grounded in concrete operational records.
Figure 2: System architecture of the GNRS-Search pipeline. Slotted candidate primitives derived from heterogeneous sources are assembled into a joint five-slot AOG structural space, optimized via an MCMC structural sampler against an internal record-grounded score, and rendered into verifiable normative prose.
Method
Spec
Exec
Flu
Read
Faith
Avg
v2 Avg
hard-ok
Overall
Direct Prompting
60.4
61.7
83.1
79.8
59.2
68.8
64.9
0.0
55.1
Structured Outputs
72.7
53.8
54.1
47.7
68.4
59.3
68.8
4.2
48.3
Best-of- N
72.0
52.7
54.5
47.4
68.7
59.1
69.0
6.1
48.5
Self-Refine
72.7
55.4
50.2
46.4
68.3
58.6
68.6
3.8
47.6
In-Context Grounding
70.2
51.9
59.8
49.9
67.8
59.9
69.7
0.0
48.0
Norm Synthesis
73.8
55.3
63.9
54.5
68.4
63.2
71.3
2.7
51.1
Table 1: Main test results on 88 goals × 3 seeds. Rubric columns are GPT-5.1 judgments on a 1–5 scale, reported as percentages. Avg denotes Rubric Avg (v1), the equal-weight mean of the five rubric dimensions; v2 Avg is a stricter diagnostic rubric that penalizes generic evidence vocabulary. hard-ok is a binary AOG feasibility diagnostic. Overall is the disclosed executable composite 0.80× Avg +0.20× hard-ok .
Ablation
Avg
Δ
hard-ok
GNRS-Search full
81.0
0.00
51.1
Uniform weights
80.4
-0.53
60.6
Random candidates
79.9
-1.03
36.0
No hard penalty
80.1
-0.86
53.8
100 search steps
80.2
-0.77
47.0
AND-only evidence
80.6
-0.35
52.7
Table 2: Ablations on GNRS-Search. Δ is the Avg difference. All rows run on the same 88 goals and three seeds; CP-SAT uses the LLM-augmented candidate inventory with an OR-Tools backend.
Figure 3: Analytical view of the headline results. Left: Rubric Avg (v1) and hard-ok form a quality-feasibility plane; dashed contours show the disclosed Overall composite, and points are labeled with abbreviated method names. Both full GNRS-Search and its No-LLM-candidates ablation are Pareto-optimal operating points: full GNRS-Search attains the highest reader-facing quality, while No LLM candidates attains higher hard-ok . GNRS-Search achieves the highest score under the disclosed Overall composite, not the highest hard-ok . Right: red bars show GNRS-Search’s executable- Overall margin over the best non-GNRS-Search method, while blue dots show GNRS-Search minus Direct Prompting on pure Rubric Avg (v1).
Figure 4: Slot sensitivity. Each cell is the Avg change after replacing one slot’s candidate pool with distractors from other goals.
Method
Avg
hard-ok
Overall
ssearch
Direct
65.6
0.0
52.4
0.546
Structured
58.0
0.0
46.4
0.805
Best-of- N
58.1
0.0
46.5
0.814
Self-Refine
58.2
0.0
46.6
0.806
Grounding
52.7
0.0
42.1
0.803
Norm Synth.
57.8
0.0
46.2
0.790
Table 3: OOD results on the held-out open-space navigation family (12 goals × 3 seeds). Overall uses the same disclosed 0.80/0.20 weighting as Table 1 . Method names are abbreviated in the table body for width.
Generator
Direct
Refine
No LLM
GNRS-Search
Δ
GPT-4o-mini
55.1
47.6
69.2
75.0
+5.7
GPT-5.1
67.3
66.2
69.1
82.0
+12.9
Gemini Flash Lite
61.6
51.7
69.0
73.7
+4.7
Qwen3-235B
63.1
54.9
69.2
74.1
+4.9
Table 4: Cross-model executable Overall with a fixed GPT-5.1 scorer. Δ is GNRS-Search minus the best non-GNRS-Search row for that generator.
Method
n
Faith
hard-ok
Overall
Direct
53
4.64
62.26
82.26
Self-Refine
53
4.77
77.36
86.09
No LLM
53
4.50
47.17
76.07
No search
53
2.68
0.00
50.56
GNRS-Search
53
5.00
100.00
94.69
Table 5: RealCharter-Bench results. Faith is the 1–5 task-faithfulness score; hard-ok and Overall are percentages. All methods receive the same normalized task card, while the source clause text is hidden.
Figure 5: External transfer from the synthetic benchmark to real-derived charter tasks for three anchor methods. Open markers show the main synthetic benchmark; filled markers show the 53 real-derived tasks.
Appendix figures & tables18 assets
Supplementary material from the paper’s appendix.
Appendix
Scene family
Scene tags
Att.
Prop.
Task.
Mix.
Total
service_coordination
restaurant
4
4
4
4
16
public_order_and_patrol
public_square, territory_border
4
4
4
4
16
commerce_and_exchange
shop, public_square
4
3
4
3
14
residence_and_rest
territory_border, public_square
3
4
3
4
14
labor_and_production
farm
4
3
4
3
14
education_and_play
public_square
3
3
3
3
12
Appendix
Table 6: Per-family goal counts crossed with the four goal categories. The open_space_navigation family is held out for OOD evaluation; the remaining 104 goals are split into 16 development and 88 in-distribution test goals.
Category
Example goal_id
Intent stem
Required / forbidden actions
attendance
GNRS-001 service_coordination
coordinate shared service shifts with auditable arrival and closure
req. CheckIn , CheckOut ; forbid. none
property
GNRS-059 residence_and_rest
protect rest and personal boundaries while allowing justified access
req. Speak ; forbid. Interact
task_execution
GNRS-002 service_coordination
coordinate shared service shifts with auditable arrival and closure
req. CheckOut , Deliver ; forbid. none
mixed
GNRS-099 crisis_response
make emergency response fast, auditable, and fair under resource pressure
req. Speak ; forbid. Trade
Appendix
Table 7: One illustrative goal per category. Required and forbidden actions are drawn from the canonical action set of Table 8 ; full roles, objects, observables, and evidence channels are part of the released benchmark specification.
Table 8: Operational primitives exposed to generators. The vocabulary is fixed across all methods and seeds; the search space A(x) of Section 5 is built from these primitives plus the goal-level templates.
Table 9: Provenance of the 53 RealCharter-Bench tasks. Each task is exposed to generators as a normalized policy card containing source family, domain, context, roles, trigger conditions, normative summary, required and forbidden actions, evidence channels, procedure requirements, and expected slots. The original clause text is withheld from generators.
Question
Contrast
Metric
Primary
Comparator
Gap
Main benchmark
GNRS-Search vs. No LLM candidates
Overall
74.99
69.25
+5.74
Main benchmark
GNRS-Search vs. No LLM candidates
Avg
80.95
67.24
+13.71
Main benchmark
GNRS-Search vs. No LLM candidates
hard-ok
51.14
77.27
-26.14
Main benchmark
GNRS-Search vs. Direct Prompting
readability
79.47
79.77
-0.30
Ablation study
GNRS-Search vs. random candidates
Avg
80.95
79.92
+1.03
Ablation study
GNRS-Search vs. uniform weights
hard-ok
51.14
60.61
-9.47
Appendix
Table 10: Selected contrasts for interpreting the result suite. Values are drawn from the reported results and are included to expose the trade-offs behind the headline claims rather than to introduce a new ranking.
Context
α
Winner
GNRS-Search rank
GNRS-Search score
Margin
Main benchmark
0.0
GNRS-Search
1
80.95
+12.12
Main benchmark
0.1
GNRS-Search
1
77.97
+9.73
Main benchmark
0.2
GNRS-Search
1
74.99
+5.74
Main benchmark
0.3
GNRS-Search
1
72.01
+1.76
Main benchmark
0.4
No LLM candidates
2
69.03
-2.23
Held-out OOD
0.0
GNRS-Search
1
79.78
+14.22
Appendix
Table 11: Sensitivity of the executable composite \textscOverallα=(1−α)Avg+α\textschard−ok . Margins are GNRS-Search minus the best non-GNRS-Search method under the same context and weight.
Experiment
Metric
Best non-GNRS-Search
n
GNRS-Search
Margin
95% CI
Main benchmark
Overall
No LLM candidates
88
74.99
+5.74
[3.93, 7.53]
Main benchmark
Avg
No LLM candidates
88
80.95
+13.71
[12.65, 14.85]
Main benchmark
hard-ok
No LLM candidates
88
51.14
-26.14
[-34.47, -18.56]
Main benchmark
Faith
No LLM candidates
88
3.96
+0.56
[0.42, 0.70]
Held-out OOD
Overall
No LLM candidates
12
82.71
+14.00
[11.42, 16.49]
Held-out OOD
Avg
No LLM candidates
12
79.78
+18.89
[16.11, 21.67]
Appendix
Table 12: Paired bootstrap confidence intervals for GNRS-Search against the best non-GNRS-Search method in each experiment. For the main and held-out evaluations, seeds are averaged within goal before resampling.
Method
n
Spec
Exec
Flu
Read
Faith
hard-ok
Overall
Direct Prompting
53
4.60
3.87
4.44
4.27
4.64
62.26
82.26
Self-Refine
53
4.77
4.06
4.28
4.20
4.77
77.36
86.09
No LLM candidates
53
4.52
3.58
4.22
4.00
4.50
47.17
76.07
No search
53
2.39
1.73
4.50
4.50
2.68
0.00
50.56
GNRS-Search
53
5.00
4.34
4.50
4.50
5.00
100.00
94.69
Appendix
Table 13: Full RealCharter-Bench metric breakdown. Direct Prompting and Self-Refine are LLM workflow baselines over the same normalized task cards; No search uses the GNRS-Search inventory and renderer without candidate scoring or search.
Audit quantity
Template/goal
Schema
Record
LLM
Candidates generated per test goal
14.0
9.3
10.2
16.7
LLM candidates dropped per run
–
–
–
1.3
Selected payloads/run, GNRS-Search
9.3
3.0
8.3
3.5
Selected payloads/run, No LLM candidates
8.4
2.9
12.0
–
Appendix
Table 14: Candidate-source audit for main-test search. Deterministic candidate counts are reconstructed from the frozen test goals and context/record inventory; LLM kept/dropped counts and selected-payload sources are computed from completed main-run artifacts.
Slot
Cand.
Distr.
Sig.
Cov.
Scope
7.00
812
52
100.0
Trigger
4.23
464
71
100.0
NormBody
6.52
754
103
100.0
EvidencePolicy
6.22
697
46
100.0
Procedure
9.15
1015
16
100.0
Appendix
Table 15: Candidate-pool audit for the slot-sensitivity experiment. Replacement coverage is the percentage of slot-intervention runs in which the degraded slot was actually replaced.
Method
n
Faith
Ground
Proc.
Read
Mean
Direct Prompting
20
3.93
2.22
2.98
4.62
3.44
Self-Refine
20
3.72
3.43
2.82
2.52
3.12
No search
20
3.87
3.48
3.47
3.22
3.51
No LLM candidates
20
3.87
2.32
3.22
3.55
3.24
GNRS-Search
20
4.53
3.42
4.12
4.72
4.20
Appendix
Table 16: Human calibration details for the main benchmark sample. Three annotators scored 100 method-blinded outputs from 20 goals. Faith is intent faithfulness, Ground is grounding, Proc. is procedural closure, and Mean averages the four 1–5 dimensions.
Agreement quantity
Value
Scope
Human–GPT Spearman ρ
0.77
row-level mean
Human–GPT Kendall τ
0.62
row-level mean
Human–GPT Pearson r
0.91
method means
Pairwise human Spearman
0.65
annotator means
Ordinal within-one agreement
85.6
all 1–5 labels
Appendix
Table 17: Agreement statistics for the human calibration study. Ordinal within-one agreement is the average pairwise percentage of labels within one point across the four 1–5 dimensions.
Method
n
GPT Avg
Gemini Avg
Gemini Overall
Direct Prompting
20
68.80
71.40
57.12
Self-Refine
20
58.20
78.60
63.88
No search
20
64.80
85.60
75.48
No LLM candidates
20
67.80
84.80
82.84
GNRS-Search
20
80.40
96.40
86.12
Appendix
Table 18: Second-model evaluator sanity check on the 100-row human-calibration pack. GPT Avg is the primary GPT-5.1 v1 rubric mean. Gemini Avg is scored by a Gemini-family judge with the same five rubric dimensions.
Failure mode
Typical symptom
Evidence in results
Implication
Surface-only fluency
The clause reads well but cites generic systems, manager discretion, or unsupported testimony.
Direct Prompting has strong fluency/readability but zero main-table hard-ok and lower faithfulness.
Language quality must be separated from operational validity.
Syntactic structure without grounding
The output follows a schema or workflow but fails to bind the fields to available records.
Structured Outputs, Best-of- N , and Self-Refine remain weak on executability and hard-ok .
A parseable intermediate form is not enough unless candidates are record-grounded.
Conservative under-generation
The system stays close to safe record payloads but loses specificity, executability, or naturalness.
No LLM candidates has the highest main-table hard-ok but much lower Avg and Overall than GNRS-Search.
Feasibility coverage should remain visible rather than replace the rubric score.
Semantic-core corruption
The rule changes who is covered, when it activates, or what conduct is regulated.
Slot degradation hurts most for NormBody , Scope , and Trigger .
Search should prioritize the semantic core before optimizing evidence wording or procedure.
Renderer-only transfer
A real-derived task card is formatted into prose without selecting the right operational structure.
The RealCharter no-search ablation collapses on faithfulness and feasibility.
External transfer depends on structured search, not just on templates over policy fields.
Appendix
Table 19: Diagnostic failure modes implied by the result suite. The table collects evidence across the reported experiments rather than introducing an additional scoring procedure.
Figure 6: AOG schematic and MCMC search trace for the service-shift case study. Left: an AND node requires a complete five-slot rule, while each OR node selects one candidate from a slot-local pool containing selected, rejected, and unused alternatives. Right: a shortened proposal trajectory shows accepted edits raising the internal structural score and rejected edits falling off the path, with proposal details moved to the legend to keep the curve readable. Vertical position is qualitative and illustrates the search dynamics rather than adding a new reported metric.
Stage
Intermediate structure
Role in the search
Goal and records
Goal: coordinate shared service shifts with auditable arrival and closure. Relevant vocabulary includes restaurant roles, CheckIn , CheckOut , movement_log , checkin_log , and checkout_log .
The goal supplies the normative intent; the record layer restricts which actors, actions, and evidence channels can be used without inventing unavailable logs.
Each slot receives multiple candidates from templates, schema terms, record traces, and validated LLM proposals. The AOG search space is the cross-product of these local choices.
Initial AOG state
A safe but weak state covers generic members and requires CheckIn / CheckOut , with broad evidence wording and little procedural closure.
This state is feasible but underspecified. It resembles the No LLM candidates behavior: close to the inventory, but poor as an organizational rule.
Accepted MCMC edits
The sampler replaces generic scope with waiter , cook , and duty_manager ; coordinates the trigger with a 15-minute arrival window; and swaps vague evidence for movement_log , checkin_log , and checkout_log .
These edits increase intent alignment and procedural closure while preserving record grounding. Unsupported variants such as a generic attendance-system timestamp receive lower structural scores because they are not in the record vocabulary.
Selected AOG and rendering
The selected structure binds scope, trigger, norm body, evidence, and procedure before the natural-language renderer writes the final clause.
The final prose is therefore a realization of an inspectable structure. If the rule later fails hard-ok , the failure can be localized to selected payloads rather than treated as an opaque text-generation error.
Appendix
Table 20: Worked AOG construction and MCMC search trace for a representative service-shift goal. The example illustrates the intermediate commitments behind the outputs in Table 21 .
Claim
Representative excerpt
Diagnostic issue
Score signal
Direct Prompting is fluent but unsupported
“documented in the designated attendance system”; evidence from “timestamps recorded in the attendance system”
The prose is coherent, but the support audit marks the attendance-system timestamp and shift-commencement payloads as unavailable in the record layer.
Avg =3.6 , hard-ok = no
No LLM candidates is feasible but rigid
“Covered members must perform CheckIn and CheckOut ” and “record the actor role, scene, object, action, evidence channel, and observed value”
The clause passes the feasibility gate by staying close to known actions and logs, but reads like a fixed template and gives little substantive policy guidance beyond slot enumeration.
Avg =3.2 , hard-ok = yes
GNRS-Search is richer but hard-ok can be fragile
“ CheckIn within trigger_window_minutes=15 ” using movement_log , checkin_log , and checkout_log
The clause is more specific and faithful, but its real-data grounding ratio is 0.475: six payloads, including shift , checkin_record , and checkout_record , lack direct resource support under the binary gate.
Avg =4.6 , hard-ok = no
Appendix
Table 21: Qualitative examples for the main method comparison on a shared service-shift goal. The examples illustrate why the paper reports both rubric quality and hard-ok rather than collapsing them into a hidden score.
Degraded slot
Correct slot content
After degradation
Concrete error
Scope
The service-shift rule covers waiter , cook , and duty_manager in the restaurant , with shift , checkin_record , and checkout_record .
The degraded rule adds organization_member and patrol_member , and swaps in learning_material , play_area , and shared_resource .
The rule becomes about the wrong actors and objects, so the shift-attendance goal is no longer the governing context. Avg drops from 3.2 to 2.0.
Trigger
The same service-shift rule activates in the restaurant when the CheckIn → CheckOut sequence is checked.
The degraded rule activates in public_square around Speak and forbidden Interact .
The activation condition moves from shift arrival/closure to unrelated public interaction, so the rule fires at the wrong time. Avg drops from 3.2 to 2.0.
NormBody
An emergency-response rule requires Patrol and forbids Trade under resource pressure.
The degraded norm requires speaking to an owner before Harvest and forbids false excuses before leaving a shift without checkout.
The core duty is replaced by unrelated harvest and shift-excuse obligations, so the rule no longer implements emergency response. Avg drops from 3.4 to 1.8.
Appendix
Table 22: Qualitative examples from the slot-sensitivity intervention. Each row uses a paired direct-render baseline and a single-slot-degraded output.
Tool-using LLM agents violate the policies they are deployed to enforce, often silently. Prior defenses hand-write rules, query an LLM verifier per action, or compile policies through heavyweight formal machinery. Naive compilation fails: extracted rules block the tool satisfying their own precondition, or read arguments their tool lacks. NOMOS, a four-pass compiler, turns a natural-language policy into a deterministic tool-call gate; static verification with tool-schema-level checks alone (no prover, solver, or LLM) repairs or rejects 37% (airline) and 13% (retail) of candidates, without which most shipped rules are inoperable. Replaying compiled rules over undefended transcripts flags bindings that refuse legitimate work (a development binding refused 95.9% of task-passing calls); no evaluation binding is flagged. On τ2-bench the gate cuts violations of reference-encoded clauses among state-changing calls from 66.3% to 2.6% (airline) and 30.8% to 6.9% (retail), raising airline task success significantly for 2≤k≤4; a 26B on-premise compilation is not significantly worse than hand-written or frontier-compiled rules. Unlike AgentDojo's shipped defenses, it reaches a zero attack success rate (ASR) on banking, where nine attack families collapse onto three structural rules. On the other three suites its ASR is at most 3.6%, from goals with no tool call to govern and one write admitted by a binding weaker than its clause; a second agent model, Llama-3.3-70B, reproduces the effect on both benchmarks. Decisions take microseconds without an LLM call, at a domain-dependent benign-utility cost; compilation runs on-premise on open-weight gemma-4-26B.
In many practical applications of generative AI systems, from tax rules to airline baggage allowance, responses to natural language queries must respect written policies or rules. We present a hybrid symbolic approach that expresses policies in formal logic and at inference time exploits the representation power of language models for fact extraction to ground predicates, and an answer set solver for reasoning such that responses are interpretable, auditable, and as we show, accurate and robust under input perturbations. Specifically, we show this separation of extraction and reasoning steps outperforms policy-as-prompt and policy-as-code methods in most cases with ~10x reduction in token usage. The results point to the value of structured reasoning and symbolic solvers in conjunction with generative models to make robust decisions involving objective criteria.
Customer-service LLM agents must follow organizational policy when acting on a user's behalf. Compliance failures arise from either forbidden actions, such as granting an ineligible change, or omitted procedural requirements, such as identification or confirmation. Runtime safeguards can intervene on risky actions, but action-local checks do not guide an agent through a multi-step procedure. Workflow-following systems support prescribed process execution, but primarily target workflow completion rather than safeguarding agent behavior. PolicyGuide instead compiles each domain policy into a workflow graph and invokes a proactive verifier at user-turn boundaries. From persisted graph state, the verifier reconciles open requests and returns step-specific remediation along a policy-compliant path. Across the τ2-bench airline, retail, and telecom domains with a GPT-5.4 agent and verifier, PolicyGuide raises mean Pass4 from 0.42 to 0.62, with the largest gain on telecom (0.19 to 0.61), the most workflow-structured domain. The same workflows transfer to Claude Sonnet 4.6 and Gemini 2.5 Pro agents. Complementary evaluations find the lowest observed attack-success rate under adversarial users and the strongest procedural compliance in an author-designed workflow-level validation.