Membership Testing for Semantic Regular Expressions

Yifei Huang, Massih-Reza Amini, Alexis Le Glaunec, Konstantinos Mamouras, Mukund Raghothaman

TL;DR

This paper introduces a novel algorithm for efficiently testing membership in "semantic regular expressions" (SemREs), which extend traditional regular expressions with the ability to query external knowledge sources like LLMs or databases. They present a practical, two-pass algorithm that significantly outperforms existing methods, while also establishing theoretical limits on how efficiently this problem can be solved, particularly concerning the cost of oracle queries.

What Problem Does This Paper Address?

Traditional regular expressions are powerful for matching syntactic patterns in text but struggle with semantic concepts (e.g., identifying "celebrities" or "pharmaceutical spam"). Semantic Regular Expressions (SemREs) bridge this gap by allowing primitives that query external "oracles" (like LLMs, databases, or APIs) to resolve these semantic queries. While synthesizing SemREs was previously explored, the crucial problem of membership testing – determining if a given string matches a SemRE – remained challenging, especially given the potential cost and latency of oracle interactions. This paper tackles this membership testing problem, aiming for efficient algorithms that minimize oracle calls.

Methods

The authors propose a two-pass, NFA-based algorithm for SemRE membership testing.

  1. Query Graph Construction: The first pass converts the SemRE into a Semantic NFA (SNFA). Instead of directly executing oracle queries, it constructs a "query graph." This graph encodes the syntactic structure of the SemRE and the relationships between potential oracle queries, representing them as a directed acyclic graph (DAG). This phase is designed to be efficient, avoiding immediate oracle calls.
  2. Dynamic Programming Evaluation: The second pass uses dynamic programming to evaluate the query graph. This involves computing "alive" vertices (those reachable from the start) and backreferences (information about open queries), ultimately determining if a feasible path exists from the start to the end of the graph, which signifies a match.

A key innovation is the "inter-character gadget," which efficiently summarizes the effects of e-transitions and query contexts between processing characters of the input string. The algorithm's complexity is analyzed, showing it runs in $O(|r|^2|w|^2 + |r||w|^3)$ time with $O(|r||w|^2)$ oracle queries, with improvements for non-nested queries.

Datasets

The authors evaluated their algorithm using two datasets:

  • Spam Emails: Filtered lines from spam emails.
  • Java Code: Filtered lines from Java code repositories.

These datasets were pruned to remove lines longer than 1000 characters and non-ASCII characters. The paper also provides the SemREs and corresponding text files used for benchmarking, making them available for future research.

Key Insights and Ideas

  • SemREs as a Practical Extension: SemREs offer a powerful way to combine syntactic pattern matching with semantic understanding, leveraging external knowledge sources.
  • The Oracle Cost is Key: Unlike classical regex matching, minimizing oracle calls is paramount due to their potential cost and latency. The proposed algorithm explicitly aims to reduce these calls.
  • Query Graphs Encode Complexity: The query graph is a novel data structure that elegantly captures the boolean logic and dependencies of oracle queries within the SemRE.
  • Nested Queries Introduce Hardness: The presence of nested queries in SemREs makes the membership testing problem as hard as finding triangles in graphs, suggesting that sub-cubic algorithms might be challenging to achieve in practice.
  • Practical Speedups: The proposed algorithm offers significant practical speedups over simpler dynamic programming baselines, especially for complex SemREs.

Key Results

  • Theoretical Performance: The algorithm achieves a time complexity of $O(|r|^2|w|^2 + |r||w|^3)$ with $O(|r||w|^2)$ oracle queries. For SemREs without nested queries, this improves to $O(|r|^2|w|^2)$.
  • Experimental Speedup: The prototype implementation ("grep^") demonstrated a 101x higher throughput compared to a dynamic programming baseline on average.
  • Reduced Oracle Calls: The algorithm made 51% fewer oracle calls than the baseline.
  • Lower Bounds: A lower bound of $\Omega(|w|^2)$ oracle queries is established for SemRE membership testing, highlighting the inherent complexity.
  • Hardness Reduction: The problem is shown to be as hard as triangle finding in graphs, implying that practical, asymptotically faster algorithms might be difficult to devise, especially for SemREs with nested queries.

Limitations and Future Work

  • Nested Queries: The theoretical analysis and hardness results are particularly impacted by nested queries. While the authors provide an example (Paris Hilton SemRE), they expect most practical SemREs to not involve deep nesting.
  • Oracle Assumptions: The analysis assumes a unit-time oracle response. The practical performance is heavily influenced by the actual oracle's latency.
  • Future Work: The authors suggest exploring extensions to handle more complex SemRE operations like negation, intersection, and bounded repetition, which are significantly harder. They also point to derivative-based algorithms as a potential avenue for simplifying SemRE matching. Further work on optimizing query graph construction and evaluation for practical scenarios is also implied.

Summary updated

Abstract

This paper is about semantic regular expressions (SemREs). This is a concept that was recently proposed by Smore (Chen et al. 2023) in which classical regular expressions are extended with a primitive to query external oracles such as databases and large language models (LLMs). SemREs can be used to identify lines of text containing references to semantic concepts such as cities, celebrities, political entities, etc. The focus in their paper was on automatically synthesizing semantic regular expressions from positive and negative examples. In this paper, we study the membership testing problem . First, we present a two-pass NFA-based algorithm to determine whether a string w matches a SemRE r in O (| r | 2 | w | 2 + | r | | w | 3 ) time, assuming the oracle responds to each query in unit time. In common situations, where oracle queries are not nested, we show that this procedure runs in O (| r | 2 | w | 2 ) time. Experiments with a prototype implementation of this algorithm validate our theoretical analysis, and show that the procedure massively outperforms a dynamic programming-based baseline, and incurs a ≈ 2 × overhead over the time needed for interaction with the oracle. Second, we establish connections between SemRE membership testing and the triangle finding problem from graph theory, which suggest that developing algorithms which are simultaneously practical and asymptotically faster might be challenging. Furthermore, algorithms for classical regular expressions primarily aim to optimize their time and memory consumption. In contrast, an important consideration in our setting is to minimize the cost of invoking the oracle. We demonstrate an Ω(| w | 2 ) lower bound on the number of oracle queries necessary to make this determination.
BibTeX
@inproceedings{huang2025membership,
  author = {Yifei Huang and Massih-Reza Amini and Alexis Le Glaunec and Konstantinos Mamouras and Mukund Raghothaman},
  title = {{Membership Testing for Semantic Regular Expressions}},
  booktitle = {Proceedings of the ACM on Programming Languages},
  year = {2025},
  doi = {10.1145/3729300},
}
Figure