💬 NLP

Grounded Normative Rule Generation with Structured Search

This paper introduces GNRS-Search, a framework that employs Markov Chain Monte Carlo sampling on an And-Or Graph to synthesize grounded normative rules, significantly improving operational feasibility and verifiability in regulated environments by decoupling executable logic from surface-level prose generation.

Original authors: Fanqi Kong, Huaxiao Yin, Ruijie Zhang, Xiaoyuan Zhang, Yizhe Huang, Jian Gao, Shuo Chen, Song-Chun Zhu

Published 2026-08-25

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Fanqi Kong, Huaxiao Yin, Ruijie Zhang, Xiaoyuan Zhang, Yizhe Huang, Jian Gao, Shuo Chen, Song-Chun Zhu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a world where the rules that govern our daily lives—from workplace safety protocols to community bylaws—are written not just to sound good, but to actually work. For decades, computer scientists have been teaching machines to write text that flows smoothly, mimicking the rhythm and vocabulary of human language. But there is a critical gap in this ability: a machine can write a sentence that sounds perfectly logical and professional while describing a process that is impossible to carry out. It might invent a type of record that doesn't exist, or demand a witness who cannot be found. In the real world, a rule that cannot be checked against actual data is not a rule at all; it is merely a suggestion that fails the moment someone tries to enforce it. This problem is particularly acute for artificial intelligence, which often generates plausible-sounding policies that collapse under the weight of reality because they rely on information the system simply does not have.

A team of researchers has tackled this specific vulnerability by treating the creation of rules not as a writing exercise, but as a search for a working blueprint. They introduced a new framework called GNRS-Search, which fundamentally changes how an AI approaches the task of drafting a policy. Instead of asking the computer to write the final paragraph immediately, the system first builds a skeletal structure. This structure is a five-part framework that defines the scope of the rule, the event that triggers it, the specific behavior required, the evidence needed to prove compliance, and the procedure for handling violations. The researchers then use a mathematical method, similar to how a hiker might explore a mountain range by taking small steps and checking the terrain, to test thousands of variations of this skeleton. The computer swaps out different pieces of the structure, constantly checking if the new combination can be supported by the actual data logs available in the environment. Only after the system finds a structure that is fully grounded in real, available records does it translate that solid framework into natural, readable language.

The results of this approach were tested against two distinct sets of challenges. The first was a controlled environment with 116 specific goals across eight different scenarios, ranging from restaurant shift coordination to managing public spaces. In these tests, the new method raised the average quality of the rules from 68.8 percent to 81.0 percent. More importantly, it ensured that the rules were executable, meaning they could actually be verified against real data. The researchers also tested the system on 53 tasks derived from real-world policies, such as corporate handbooks and open-source governance guidelines, where the original text was hidden from the computer to prevent simple copying. Here, the system again outperformed standard methods, achieving a perfect feasibility rate while maintaining high readability. The study showed that the improvement did not come from the AI simply using better words or sounding more professional; it came from the system correctly identifying which parts of a rule could be supported by evidence and which could not.

Crucially, the research also revealed where the system was most likely to fail. By deliberately swapping out specific parts of the rule structure, the researchers found that errors in the core meaning of the rule—such as who the rule applies to, when it starts, or what behavior is required—caused the most significant drop in performance. In contrast, the system was surprisingly resilient when the details about how to gather evidence or the specific steps for enforcement were slightly altered, as long as the core logic remained sound. This suggests that the most important part of writing a functional rule is getting the fundamental logic right before worrying about the phrasing. The study concludes that by separating the structural logic from the final text, it is possible to create AI agents that can draft policies which are not only easy to read but are also strictly verifiable and ready for real-world enforcement. This shift from generating text to searching for valid structures offers a new path for deploying artificial intelligence in regulated environments where trust and accuracy are non-negotiable.

Technical Summary: Grounded Normative Rule Generation with Structured Search

1. Problem Definition: Grounded Normative Rule Synthesis (GNRS)

The paper addresses a critical vulnerability in current language generation systems: the inability to produce normative rules (e.g., institutional charters, workplace policies) that are both human-readable and operationally verifiable. While standard benchmarks reward surface fluency or schema compliance, they often fail to test whether a generated rule can be enforced against actual environment records.

The authors formalize this as Grounded Normative Rule Synthesis (GNRS). Given a normative goal, an institutional schema, and a record layer containing environment traces and logs, the task is to generate a natural-language rule that is strictly backed by available data. The core challenge is not merely factual hallucination but the coordination of five interdependent components:

Scope: Who/what the rule applies to.
Trigger: When the rule activates.
Norm: The required or forbidden conduct.
Evidence: The data channels used to verify compliance.
Procedure: The steps for enforcement or appeal.

A failure in one component (e.g., selecting "staff testimony" as evidence when the environment only logs "check-in records") renders the entire rule unenforceable, even if the prose is fluent.

2. Methodology: GNRS-Search

To solve GNRS, the authors propose GNRS-Search, a framework that decouples the generation of the final prose from the synthesis of the underlying operational structure. Instead of end-to-end text generation, the system treats rule creation as a discrete optimization problem over a structured representation.

Core Architecture

Latent Structure (AOG): The rule is modeled as a five-slot And-Or Graph (AOG). This graph represents intermediate operational commitments across the five slots (Scope, Trigger, Norm, Evidence, Procedure). The AOG is not the final output but a modeling assumption that allows the system to reason about grounding before rendering text.
Candidate Construction: For each slot, the system builds a candidate repository ( $C_k$ $C_{k}$ ) from four sources:
1. Symbolic rule templates.
2. Context-schema primitives.
3. Trace-derived event records (from the operational log).
4. LLM-augmented proposals (filtered against the schema and logs to prevent hallucination).
  The total search space is the Cartesian product of these sets.
MCMC Optimization: The system employs Markov Chain Monte Carlo (MCMC) sampling to navigate the combinatorial space of structural configurations. It iteratively edits the discrete AOG using four operations:
1. Slot replacement.
2. Parameter editing.
3. Evidence swapping.
4. Joint trigger-evidence adjustments.
Scoring Function: An internal scoring function ( $s_{search}$ ) guides the search, evaluating record grounding and penalizing hard feasibility violations (e.g., referencing unavailable logs). This score is distinct from the final evaluation metric to prevent overfitting.
Realization: Once an optimal structural layout ( $a^*$ ) is found, a realization function ( $R$ ) renders it into natural language. A "programmatic alignment guard" ensures the polishing phase does not discard essential structural entities or evidence logs.

3. Evaluation Benchmarks

The paper introduces two benchmarks to evaluate grounded rule synthesis:

GNRS-Bench: A controlled simulation environment with 116 goals across 8 scene families (e.g., restaurant attendance, public order). It features a typed operational record layer where rules must be grounded in specific, available logs (e.g., checkin_record, movement_log). It includes an Out-of-Distribution (OOD) split for robustness testing.
RealCharter-Bench: A transfer benchmark containing 53 tasks derived from authentic public policies (e.g., Python PSF, GitLab Handbook). The original human-authored text is hidden; models receive normalized policy cards and must synthesize rules grounded in the provided context, testing generalization to real-world scenarios.

4. Key Results

Experiments were conducted across multiple model backbones (GPT-4o-mini, GPT-5.1, Gemini, Qwen3) and compared against baselines including direct prompting, structured outputs, best-of-N reranking, and self-refinement.

Performance Gains: GNRS-Search raised the average rubric quality (a composite of specificity, executability, fluency, readability, and faithfulness) from 68.8% (Direct Prompting) to 81.0%.
Executability: The method achieved a 73.3% score on the "Executability" dimension, significantly outperforming baselines which often generated fluent but unenforceable rules.
Composite Metric: Under a disclosed executable composite metric ( $0.80 \times \text{Quality} + 0.20 \times \text{HARD-OK}$ ), GNRS-Search ranked first across all tested generators and OOD scenes.
Robustness: The method maintained its advantage in OOD settings (scoring 82.7% on the composite metric) and on RealCharter-Bench (94.69% composite score).
Ablation Insights:
- Removing the structured search or randomizing candidates caused significant performance drops.
- A mathematical CP-SAT solver baseline performed substantially worse, indicating that the gains stem from the specific MCMC search strategy and candidate inventory, not just discrete optimization.
- Slot Sensitivity: Sensitivity analysis revealed that errors in the Norm Body, Scope, and Trigger slots caused the largest performance drops, whereas the system was more resilient to variations in Evidence and Procedure slots.

5. Significance and Claims

The paper claims to provide a foundational paradigm for deploying verifiable and compliance-ready personal agents in regulated environments. Its primary contributions are:

Formalization: Defining GNRS as a structured Natural Language Generation (NLG) task where validity depends on operational grounding, not just fluency.
Methodological Shift: Moving rule generation from a surface-level text task to an inspectable search problem over discrete operational structures. This allows failures to be localized to specific structural components (e.g., evidence channels) before prose generation.
Empirical Validation: Demonstrating that enforcing structural grounding via MCMC search yields rules that are both readable and operationally executable, outperforming standard prompting and iterative refinement techniques.
Transparency: The framework explicitly separates the internal search score from the final evaluation, ensuring that performance gains are driven by genuine structural grounding rather than metric optimization.

The authors conclude that while fluent open-ended prompting is unreliable for compliance, and syntactic constraints alone are insufficient, grounding-aware structural search is necessary to satisfy joint executability requirements in regulated environments. The work establishes a framework where rule failures can be diagnosed and corrected at the structural level, bridging the gap between natural language generation and operational verification.