Abstract
Translating natural language into Graph Query Language (GQL) is a significant challenge for small, on-device Large Language Models (LLMs), which often fail to maintain syntactic validity and schema compliance. This paper introduces a framework for schema-constrained grammar-guided generation. By embedding database schema constraints directly into the decoding grammar, the proposed method ensures that generated queries are valid "off-the-bat." This approach eliminates the need for extensive prompt engineering or specialized fine-tuning, offering a scalable solution for privacy-preserving personal assistants.
Introduction
The task of Natural Language to Graph Query Language (NL2GQL) translation is essential for modern personal assistants that query local knowledge graphs. However, deploying this capability on-device presents two primary hurdles. First, resource constraints necessitate the use of small models (typically ≤7B parameters), which are prone to syntax errors. Second, queries must strictly adhere to a user's unique database schema. Traditional methods, such as including the schema in the prompt, lead to "context bloat," increasing latency and memory usage. Fine-tuning models for every possible schema is equally impractical.
Methodology
The authors propose a Schema-Constrained Grammar-Guided Generation approach. This technique restricts the LLM's output during decoding using a formal grammar, such as a Context-Free Grammar (CFG), augmented with schema-specific information.
Grammar Extension and Expansion
The process begins with a standard GQL grammar containing placeholders for schema components like nodes, properties, and relationships (e.g., ${node}`, `${prop}). These placeholders are automatically expanded based on the target database schema. For instance, a rule for ${rel}_properties is specialized to the actual properties available for a specific relationship type, such as points_scored for a plays_for relationship.
Constrained Decoding
During inference, frameworks like llama.cpp (using GBNF) or outlines use this schema-augmented grammar to mask invalid tokens. The LLM is forced to select only those tokens that result in a syntactically and structurally valid GQL query.
AST Post-processing
Because the output is guaranteed to be syntactically valid, it can be reliably parsed into an Abstract Syntax Tree (AST). This AST facilitates "data grounding," where literal values in the query (e.g., names) can be cross-referenced with actual graph data to correct typos or resolve synonyms before execution.
Key Insights
The proposed framework offers several advantages for on-device AI:
- Prompt Efficiency: Moving schema definitions from the prompt to the grammar reduces the input token count, speeding up inference.
- Zero-Shot Adaptation: Generic models can support custom schemas without retraining; only a new grammar file is required.
- Type Enforcement: The grammar can enforce data types (e.g., ensuring a numeric property is followed by an integer), preventing common hallucination errors.
- Robustness: By guaranteeing a valid AST, developers can implement sophisticated post-processing pipelines to handle semantic nuances.
Limitations and Future Work
As a methodology and position paper, this work identifies several areas for further development. While CFGs are effective for syntax, they struggle with context-dependent constraints, such as variable scoping. Future research will explore backtracking strategies to allow the decoder to recover from dead-end paths and the development of automated tools for grammar generation.
Conclusion
Schema-constrained grammar-guided generation provides a robust path forward for NL2GQL on small models. By shifting the burden of schema compliance from the model's weights or context window to the decoding process, it enables efficient, accurate, and private graph querying on-device.
Summary updated