Grammar Pruning: Enabling Low-Latency Zero-Shot Task-Oriented Language Models for Edge AI

Octavian Alexandru Trifan, Jason Lee Weber, Marc Titus Trifan, Alexandru Nicolau, Alexander VeidenbaumEMNLP 2025

TL;DR

This paper introduces "Grammar Pruning," a novel framework that significantly reduces latency and improves accuracy for task-oriented semantic parsing on edge devices. By dynamically constraining language model outputs based on a user-defined API schema, it achieves state-of-the-art performance with small models, making advanced NLP feasible on resource-constrained hardware.

What Problem Does This Paper Address?

The proliferation of edge devices (smartphones, wearables, IoT) has created a demand for sophisticated Natural Language Processing (NLP) capabilities directly on these devices. A key NLP task for edge AI is Task-Oriented Semantic Parsing (TOSP), which allows users to control device functions using natural language (e.g., "Set a timer for 5 minutes"). While large language models (LLMs) excel at TOSP, their high latency and substantial computational requirements make them unsuitable for edge deployment. Existing methods often struggle to balance accuracy, latency, and resource constraints, leading to either inaccurate outputs, slow responses, or the need for cloud offloading, which is not always feasible or desirable. This paper aims to bridge this gap by enabling accurate and low-latency TOSP on edge devices using small language models (SLMs).

Methods

The core innovation is Grammar Pruning, a lightweight, schema-driven framework. It operates in two main stages:

  1. Item Extraction (NER) and Intent Validation: The system first extracts relevant entities (like "New York" or "747") from the user's input. This extraction is guided by a well-defined API schema that lists all possible intents (e.g., atis_fare) and their associated slots (e.g., departure_city). The extracted items are then used to identify a set of "valid intents/slots" that are plausible for the given input. This step prioritizes recall to avoid prematurely discarding potentially useful information.
  2. Grammar Pruning and Constrained Generation: The initial, unpruned grammar (representing the full schema) is dynamically pruned based on the valid intents and slots identified in the previous step. As the language model generates output and fills slots, the grammar is further refined by removing used items. This iterative pruning process drastically reduces the model's output search space, ensuring that it only generates schema-compliant API calls and significantly minimizing hallucinations. The generation is then performed using this dynamically constrained grammar.

Datasets

The authors evaluated their approach on three primary datasets, all adapted to output Python API call structures:

  • FoodOrdering: An adaptation of a previously released dataset, focusing on food-related orders.
  • APIMIXSNIPS & APIMIXATIS: Evaluation-only subsets derived from existing benchmarks, focusing on intent/slot extraction.

These datasets were used for both zero-shot evaluation and, in some cases, for instruction fine-tuning to test cross-schema knowledge transfer.

Key Insights and Ideas

  • Schema as a Constraint, Not Just a Guide: The paper demonstrates that a well-defined API schema can be actively used to prune the generation space, rather than just guiding it. This active pruning is key to achieving both accuracy and low latency.
  • Recall-First Extraction for Robustness: Prioritizing recall during the initial entity extraction is crucial. While this might introduce some ambiguity, the subsequent grammar pruning and the language model's generation process are designed to handle these ambiguities, preventing the loss of essential information.
  • Small Models Can Compete: The results show that small, efficient models enhanced with Grammar Pruning can achieve accuracy comparable to or even exceeding larger, more powerful models (like GPT-4.1-mini) on TOSP tasks, especially when latency and resource constraints are critical.
  • Dynamic Pruning is Key: The iterative nature of pruning the grammar as the model generates output is what allows for efficient, hallucination-free generation, unlike static constrained decoding.

Key Results

  • Accuracy: Grammar Pruning achieved over 90% execution accuracy on adapted benchmarks, rivaling state-of-the-art cloud-based solutions. For instance, on the FoodOrdering dataset, accuracy improved from 73.3% to 96.2% on the BURGER subset and from 54.8% to 91.1% on the COFFEE subset.
  • Latency: The framework delivered at least a 2x lower end-to-end latency compared to existing methods. On a Raspberry Pi, Grammar Pruning achieved sub-second latencies, outperforming other techniques by over twice the speed.
  • Model Agnosticism: The approach demonstrated robustness across various small language model architectures and sizes (0.5B to 1.5B parameters) and remained effective even with 4-bit quantization.
  • Comparison to Baselines: Grammar Pruning significantly outperformed baselines like Cross-TOP, DSCP, and Qwen3 (CoT) in terms of both accuracy and latency, especially on the APIMIXATIS and APIMIXSNIPS datasets.

Limitations and Future Work

  • NER Module Vulnerability: The current rule-based NER module is sensitive to novel lexical variants and domain drift (e.g., slang). Future work could explore hybrid or self-refining extraction methods.
  • Static Schema Assumption: The framework assumes a complete and static schema. Applications requiring user-defined extensions would necessitate schema recreation. Future work could explore dynamic schema evolution or methods to gracefully handle out-of-schema inputs.
  • Hardware Dependency: While efficient on consumer GPUs, performance on highly constrained edge hardware (like Raspberry Pi) still benefits from device-specific optimizations.
  • Broader Applicability: The authors suggest extending Grammar Pruning to tasks beyond TOSP, such as structured web data extraction or code generation, and investigating adaptive extraction and schematic evolution.

Summary updated

BibTeX
@inproceedings{trifan2025grammar,
  author = {Octavian Alexandru Trifan and Jason Lee Weber and Marc Titus Trifan and Alexandru Nicolau and Alexander Veidenbaum},
  title = {{Grammar Pruning: Enabling Low-Latency Zero-Shot Task-Oriented Language Models for Edge AI}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2025},
}
Figure