CPU Bound Issue in Parser with Complex Grammar (Possible Error with handling of Zero-Width/empty Strings)

[bytemouse]

The bug For complex grammar, the generation becomes CPU bound and doesn't terminate. My guess is that the problem lies with empty or zero-width strings not being properly handled by the parser. By line profiling I see that all of the time is spent in these lines: https://github.com/guidance-ai/guidance/blob/c9e71fbc3a434eab5209c31735d72fd7e60876f2/guidance/_parser.py#L191-L195

To Reproduce I use this model and this code: https://huggingface.co/cognitivecomputations/dolphin-2.9-llama3-8b https://gist.github.com/bytemouse/6b8eaa647840c3793d5a4f23516b2a5f

System info OS: Fedora 40 Guidance Version: 0.1.15

[Harsha-Nori]

Thank you so so much for reporting this, and for sharing your grammar to help us reproduce! Would you mind checking if the issue existed on Guidance v.0.1.14? We introduced some richer support for zero-width strings in this recent release and it'd be helpful to know if it may be the culprit.

[bytemouse]

I tried the other 0.1.14 and the same error error persists with the same prompt and others. it always seems to 'crash' on the last closed curly brace as in this example in 0.1.14 and 15 across various prompts:

package cd4code.lighting;

class CarLighting {

  class Light {
    boolean on;
  }

  class HeadLight extends Light {
    double brightness;
  }

  class TailLight extends Light {
    double blinkRate;
  }

Even in cases where there is no empty token in the top logits, stalling at the probably last tokhen happens. Sometimes it stalls in _compute_children, but I am unsure if these similar problems relate to the same error. Thank you for your fast response.

Method	Calls	Time (ms)	Own time (ms)
_compute_children	13,070,618	139,349	126,432
_inner_loop	1,701	105,906	55,044
<built-in method builtins.len>	563,931,597	37,746	37,698
__eq__	128,219,828	25,312	15,477
<built-in method builtins.isinstance>	155,682,311	13,623	12,804
_pre_process_regex	543,995	16,668	9,877
replace_grammar_node	20,817	11,413	6,110

[hudson-ai]

@bytemouse you did indeed uncover a bug here, but here's a simple workaround for you for the moment. "Works on my machine", so your mileage may vary, but why don't you give this a try:

@guidance(stateless=True)
def NAME(lm):
    return lm + zero_or_more(WS()) + gen(regex='[a-zA-Z_\$][a-zA-Z_0-9\$]*')

The library we are using to parse regular expressions doesn't correctly escape special characters inside of character classes, so you have to do that manually for now (note that my only change above from your code was escaping the dollar signs).

[bytemouse]

This did resolve the issue. Thank you for your help!