osaariki

llguidance is used in vLLM, SGLang, internally at OpenAI and elsewhere. At the same time, I also see a non-trivial JSON error rate from Gemini models in large scale synthetic generations, so perhaps Google hasn't seen the "llight" yet and are using something less principled.

>This doesn't compose though, right? For example, if you have `sam|samwise`, then you can do that transformation, but if you have `\b(?:sam|samwise)\b` then you can't.

You'd get subsumption when you have something like '(?:sam)?wise|wise' and in fact this kind of subsumption due to a "nullable prefix" is the main one currently detected (because we encountered patterns that motivated it). And you're right that all these rewrites should compose regardless of context so that they can be eagerly applied in the AST constructors.

>> but a larger class of patterns get to stay in the DFA world with derivatives. >Can you say more about this?

Yeah, the easiest example I can point at is from that tool paper [1], where a subsumption-based rewrite for counted repetitions can turn an exponential blow-up into a linear one. Off the top of my head I think a pattern like '.*a[ab]{0,1000}' would have a 2^1000 blow-up when determinized into a DFA but stays linear in size with derivatives. However, that loop subsumption rule isn't valid as-is under PCRE semantics, so it still needs some work to be ported to the .NET engine.

Before we get that PLDI paper out the best resource is probably just the code under [2]. It's fairly well commented, but of course that's no substitute for a good write-up.

An initial implementation might be doable in 5 hours for someone competent and familiar with RLLib's APIs, but could take much longer to really polish.

Something that came out of the Koka project that everyone should know about is mimalloc [2]: if your built-in malloc is not doing it for you, this is the alternative allocator you should try first. Mimalloc is tiny and it has consistently great performance in concurrent environments.

My view is that this is already fast enough to support use cases that really need the unique capabilities of FHE. Since this work we've been focused on making FHE more usable with compilers and tooling [3]. Currently most FHE is being programmed like that Intel 8087 was: with the equivalent of assembly by directly calling functions in FHE libraries to perform arithmetic and crypto operations. Imagine having to do register allocation by hand for all of your code. The EVA compiler [4] is meant to be like a "C compiler for FHE", hiding low-level crypto concerns and providing common optimizations.

Instead the article just seems to say that color design for animation is a bit different.

Something an automata based engine can do (and IIRC re2 does) is that instead of constructing the full DFA, you can construct the much smaller non-deterministic finite automaton (NFA) and perform the product construction on-the-fly while caching states you've seen. However, this only helps if your input doesn't actually visit all those states. A malicious input could target your NFA engine to cause states being constantly kicked out of the cache. The slowdown here is linear though, so you're still better off than with a backtracking engine.

A project I'm working on is the Symbolic Regex Engine (SRM) [1], which uses a symbolic variant of regex derivatives. This technique allows an often-minimal DFA to be constructed lazily. This is similar to NFA based engines, but results in much fewer states thus helping with the cache issue. SRM can also handle some classes of counters natively in how the automaton gets constructed, which can turn a blow-up that would be exponential in a DFA based engine into a linear one.