Is compiling guides supposed to take a long time?

[joerunde]

cc @cpfiffer, following up on the discussion from #180

My colleague @frankdvd has done some analysis of the time it takes to build a RegexGuide based on the complexity of the input json schema, which I'll paste below. We also saw similar results using the Vocabulary, Index, Guide method shown on the readme.

It looks like we're doing something wrong, since it's taking quite a long time to compile these guides for relatively simple json schemas. When we try the same thing with lm-format-enforcer, we don't see a meaningful increase in time taken to compile a token enforcer for the same schemas.

On the related issue where we had a user passing in an invalid schema, you had mentioned I was able to get this to compile in 80-90ms using our internal API. I had assumed you were talking about outlines-core, but maybe not? If there is a super secret sauce that y'all aren't open sourcing, I'd be happy to email you about it, but I did want to have this discussion in the open if we're just using outlines-core wrong.

Here's the anaylsis:

I did some experiments to measure the performance of the outlines, and try to find the root case of the hang/slowness. At first I thought it was some special keyword or syntax that was causing the hang, so I wasted some time trying to troubleshoot what was causing the problem. I eventually realized that the root cause of the problem was so simple that the number of fileds in an object would exponentially affect the computation time.

Test 1: # of fields in 1 objects vs time

Example schema when n = 3:

{
  "type": "object",
  "properties": {
    "w1": {
      "type": "string"
    },
    "w2": {
      "type": "string"
    },
    "w3": {
      "type": "string"
    }
  }
}

We can see that the time grows exponentially as n increases.

Test 2: # of json object in depth nested vs time

Example schema when n = 3:

{
  "type": "object",
  "properties": {
    "d1": {
      "type": "object",
      "description": "simple obj",
      "properties": {
        "d2": {
          "type": "object",
          "description": "simple obj",
          "properties": {
            "d3": {
              "type": "object",
              "description": "simple obj",
              "properties": {}
            }
          }
        }
      }
    }
  }
}

We can see that the time grows linearly as n increases, so the depth is not the root cause.

Test 3: total number of fields in a 2 depth json with nested object contains 6 fields vs time

Example schema when n = 12:

{
  "type": "object",
  "properties": {
    "w1": {
      "type": "object",
      "properties": {
        "w1": {
          "type": "string"
        },
        "w2": {
          "type": "string"
        },
        "w3": {
          "type": "string"
        },
        "w4": {
          "type": "string"
        },
        "w5": {
          "type": "string"
        },
        "w6": {
          "type": "string"
        }
      }
    },
    "w2": {
      "type": "object",
      "properties": {
        "w1": {
          "type": "string"
        },
        "w2": {
          "type": "string"
        },
        "w3": {
          "type": "string"
        },
        "w4": {
          "type": "string"
        },
        "w5": {
          "type": "string"
        },
        "w6": {
          "type": "string"
        }
      }
    }
  }
}

Test 4: total number of fields in a 2 depth json with nested object contains 3 fields vs time

Example schema when n = 9:

{
  "type": "object",
  "properties": {
    "w1": {
      "type": "object",
      "properties": {
        "w1": {
          "type": "string"
        },
        "w2": {
          "type": "string"
        },
        "w3": {
          "type": "string"
        }
      }
    },
    "w2": {
      "type": "object",
      "properties": {
        "w1": {
          "type": "string"
        },
        "w2": {
          "type": "string"
        },
        "w3": {
          "type": "string"
        }
      }
    },
    "w3": {
      "type": "object",
      "properties": {
        "w1": {
          "type": "string"
        },
        "w2": {
          "type": "string"
        },
        "w3": {
          "type": "string"
        }
      }
    }
  }
}

conclusion

if we want to control the size of the input to avoid timeout or hang, the regex generation needs to less than 30s(I guess):
According to test1/3/4, the maximum number of fields in each object must be less than 9. And the total number of fields in the whole json needs to be less than 20.

I'm not sure how many tools/api's would still be available if the above restrictions were applied to our api.......

Python code to reproduce this:

import outlines

from outlines_core.fsm.json_schema import build_regex_from_schema
from outlines.fsm.guide import  RegexGuide
import json
from transformers import AutoTokenizer
import time
import copy
import matplotlib.pyplot as plt
import numpy as np

tk = AutoTokenizer.from_pretrained("meta-llama/Meta-Llama-3-8B")
outlines_tokenizer = outlines.models.TransformerTokenizer(
    tk
)

simple_field = {
    "type": "string"
}

simple_obj = {
    "type": "object",
    "description": "simple obj",
    "properties": {}
}

root_schema = {
    "type": "object",
    "properties": {}
}

def generateTime(n, generateJsonObj):
    t = []
    for i in range(n+1):
        schema_str = json.dumps(generateJsonObj(i))
        #print(schema_str)
        start_time = time.time()
        regex = build_regex_from_schema(schema_str)
        guide = RegexGuide.from_regex(regex, outlines_tokenizer)
        end_time = time.time()
        elapsed_time = end_time - start_time
        t.append(elapsed_time)
        print(f"Elapsed time for build regex: {elapsed_time:.4f} seconds")
    # we use 0 to warmup, now remove it
    del t[0]
    return t

def plot(n, t, factor, name):
    # Data for plotting
    x = np.arange(1, n+1) * factor
    fig, ax = plt.subplots()
    ax.plot(x, t)
    ax.set(xlabel='n', ylabel='regex build time',
        title= name)
    ax.grid()
    fig.savefig(name + ".png")

def n_widths(base):
    def f(n):
        schema = copy.deepcopy(root_schema)
        for i in range(1, n+1):
            schema["properties"][ "w" + str(i) ] = base
        return schema
    return f

def n_depths(base):
    def f(n):
        schema = copy.deepcopy(root_schema)
        root = schema
        for i in range(1, n+1):
            root["properties"][ "d" + str(i) ] = copy.deepcopy(base)
            root = root["properties"][ "d" + str(i) ]
        return schema
    return f

# test width
max_width = 10
t = generateTime(max_width, n_widths(simple_field))
plot(max_width, t, 1, "num_fields_in_width_vs_time")
print("num_fields_in_width_vs_time json example:")
print(json.dumps(n_widths(simple_field)(3)))

# test depth
max_depth = 50
t = generateTime(max_depth, n_depths(simple_obj))
plot(max_depth, t, 1, "num_fields_in_depth_vs_time")
print("num_fields_in_depth_vs_time json example:")
print(json.dumps(n_depths(simple_obj)(3)))

# test n by 6 json
max_width = 5
base_json = n_widths(simple_field)(6)
t = generateTime(max_width, n_widths(base_json))
plot(max_width, t, 6, "total_num_fields_with_6_fields_base_vs_time")
print("total_num_fields_with_6_fields_base_vs_time json example:")
print(json.dumps(n_widths(base_json)(3)))

# test n by 3 json
max_width = 8
base_json = n_widths(simple_field)(3)
t = generateTime(max_width, n_widths(base_json))
plot(max_width, t, 3, "total_num_fields_with_3_fields_base_vs_time")
print("total_num_fields_with_3_fields_base_vs_time json example:")
print(json.dumps(n_widths(base_json)(3)))

[rlouf]

Thank you so much for putting the time to do these benchmarks, this is really helpful. It looks like these times are in second; if that's the case I am really surprised as they are at odds with what we observe in our benchmarks in outlines-core. We need to understand if that's a problem with the integration in Outlines, or if we're missing something in our benchmarks in outlines-core.