The Fastest Regex Is the One You Don’t Run

When we give an AI agent a regular expression filter, it tends to use it for search. Not only for patterns that need regex, but also for ordinary keyword and phrase queries.

That choice makes sense from the agent's point of view. A literal phrase is already a valid regex. Case insensitivity, word boundaries, optional spelling, and alternatives are small changes to the same expression. The agent can use one tool for all of these requests:

invoice
(?i)nobel prize
colou?r
error (reading|writing) file

This is a good interface for an agent. However, it can be a very expensive operator inside a query execution plan even when using an automaton-based regex engine without exponential backtracking (see ReDoS).

Regular expressions are fast when they run against one string. They are much slower when they run against every string in a large collection. An occasional scan may be acceptable for a person typing a query but not for agents that issue many concurrent queries while exploring, verifying, and refining an answer.

That was the problem we had in TopK. Our regex engine was already efficient, but every regex filter still had to read the target field and evaluate the pattern for every document. A better regex kernel would improve it by a constant factor, but it couldn't address the fundamental problem. The useful observation was that agent-generated regexes often contain many literals. Even a pattern with optional sections or alternatives usually says that some characters must occur which can be exploited to speed up the queries using an index.

So we changed the question. Instead of asking how to evaluate a regex faster, we asked how many documents needed the full regex at all.

The result is a two-stage approach. A sparse n-gram index finds a set of candidate documents, then the full regex checks only the candidates instead of the full corpus. The index is allowed to return false positives, but it must never lose a real match.

regex → boolean expression over n-grams → candidate documents → exact regex

Just index trigrams?

The usual way to accelerate substring search is a trigram index. Split each document into every overlapping sequence of three characters and store a posting list for each trigram.

For example, alan turing produces:

["ala", "lan", "an ", "n t", " tu", "tur", "uri", "rin", "ing"]

A document that contains alan turing must contain all nine trigrams. Intersecting their posting lists gives a candidate set that can be checked with the full regex.

This approach works, and it has an important property: it cannot create false negatives (i.e. documents that don't match the index but match the full regex). However, trigrams are a compromise.

Short grams are common. A trigram such as the, ing, or tur may occur in a large fraction of a corpus, so its posting list is expensive to read and does little filtering. Trigrams also forget adjacency beyond three characters. A document may contain every trigram from a query in unrelated places and still become a candidate.

Using longer fixed n-grams improves selectivity, but creates another problem. An index over one width cannot help with required fragments shorter than that width which might force us to a full scan (remember, no false negatives). Indexing every width repeats much of the same text and makes the number of tokens per document grow with the maximum width which explodes the index size.

Sparse-grams offer a solution. Guarantee that all minimum length n-grams are present, and probabilistically create longer n-grams to improve index selectivity.

Content-defined n-grams

Sparse-gram tokenization starts by assigning a deterministic weight to every bigram in the input string. We currently use CRC32 to compute bigram weights, though any deterministic function with a sufficiently even output can play the same role.

Consider an n-gram spanning n - 1 bigrams. We select it when its two boundary bigrams have greater weights than every bigram in its interior. Put another way, the two largest weights in the span must sit at its edges. The rule depends only on the contents of the span, not on its position in the surrounding document which makes tokenization context-free.

That locality gives sparse grams their most important property. If a string q occurs inside a document d, every gram selected from q is also selected from the same interval in d. Adding text before or after the match cannot change a decision made entirely inside it.

TopK uses two views of the tokenizer:

• At index time, all(d) stores every eligible sparse gram selected from document d.
• At query time, covering(q) keeps a smaller set of eligible grams used to constrain the query.

The property we need is:

covering(q) ⊆ all(q) ⊆ all(d), when q is a substring of d

This is the correctness contract behind the index. A matching document contains every required query gram. Hash collisions or an imprecise regex plan can add candidates, but the exact regex removes them later.

Try the parser below. build_all shows the grams stored at index time. build_covering shows the smaller set needed for a query. Open the boundary weights to see why each interval was selected.

Why the index stays sparse

Assume the bigram weights are independent and have no ties. An n-character span contains n - 1 bigrams. Every ordering of their weights is equally likely. The span is selected only when the two largest weights land on its boundaries, in either order. Its selection probability is:

P(select an n-gram) = 2 / ((n - 1)(n - 2))

Long intervals become progressively rarer. Their selection probability falls in proportion to 1 / n². If the minimum length is three, every trigram is selected, since 2 / ((3 - 1)(3 - 2)) = 1. Longer grams are then added less frequently.

For a long string of L characters, the expected number of selected grams with lengths from a through N is approximately:

E[grams] ≈ 2L × (1 / (a - 2) - 1 / (N - 1))

The sum telescopes. With a minimum of three, the expectation approaches 2L even as the maximum grows. A dense index over every width grows on the order of LN. This is the useful asymmetry: sparse grams can admit longer terms without indexing every longer interval.

N-Gram information and selectivity

Length is a useful proxy for selectivity, but it's not the whole picture. The quantity that matters for a particular gram g is its information, where P(g) is the probability that the gram begins at a given position:

I(g) = -log₂ P(g)

A rare gram carries more information than a common one. Two grams of the same length can therefore have very different posting lists. A familiar phrase may remain common even when it is long, while a name or unusual spelling can become selective after only a few characters.

If a gram has information I(g) and a document offers roughly L positions where it could begin, a simple occurrence model gives:

P(document contains g) = 1 - (1 - 2^(-I(g)))^L

When the gram is rare, this is approximately L × 2^(-I(g)). The posting list starts to leave the saturated region when I(g) reaches about log₂(L) bits. In a corpus of M similar documents, its expected document frequency reaches one near:

I(g) ≈ log₂(M L)

Natural language does not spread probability evenly across all strings. It produces a small head of common grams and a long tail of names, numbers, phrases, and accidental combinations. Longer grams still help because they can accumulate more information. Extending a gram x by a character c adds the conditional information of that continuation:

I(xc) = I(x) - log₂ P(c | x)

A predictable continuation adds little. A surprising one adds a lot. Maximum n-gram length therefore controls how much evidence one index term can carry, without assuming that every extra character is equally valuable.

The chart below lets you vary a gram's information directly to see how it affects its selectivity. The orange curve estimates its posting-list fraction. The teal line marks one document in the selected corpus. The two vertical guides show where posting lists begin to narrow and where the expected document frequency reaches one.

Raising the maximum n-gram length from N to N + 1 adds only about 2L / (N(N - 1)) index terms under the sparse selection model. It also admits grams that may carry more information so the query planner can then prefer the terms with the lowest measured document frequency, regardless of their length.

Turning a regex into a boolean expression

Literal strings are the easy case. Real regexes contain optional sections, alternations, character classes, repetitions, and wildcards.

We parse the regex into the same high-level representation used by the exact matcher. For each node, the planner tracks what it can prove about every possible match:

• exact strings, when the set is small enough;
• required prefixes and suffixes;
• whether the expression can match an empty string;
• a boolean expression over grams that every match must satisfy.

The boolean operators follow the regex structure. Concatenation usually combines constraints with AND. Alternation combines them with OR. A wildcard contributes no constraint, but known text on either side can still be useful. A subexpression that can match the empty string cannot be required, so its constraint is weakened or dropped.

The planner feeds required literal runs through covering() and uses the resulting grams as leaves in the boolean expression. Those terms are guaranteed to exist in the index for every matching document.

Consider:

colou?r of the (sky|sea)

A conservative index query could look like this:

" the"
AND "r of t"
AND ("e se" OR "e sk")

The plan does not encode the full regex. It does not need to. It states only facts that must be true for a match. A document that fails this expression cannot match the regex and can be safely skipped. A document that passes is only a candidate for full regex verification.

This one-way guarantee lets the planner control its own cost. It can drop a weak gram, cap a large alternation, or give up on an unhelpful subexpression. Each choice admits more candidates, but none can remove a true match. Patterns such as .*, or patterns made mostly from broad character classes, safely fall back to a scan.

At execution time, TopK resolves the gram posting lists, evaluates the AND and OR tree, and gets sorted list of candidate document IDs. It then uses the candidate IDs to prune blocks that contain no candidates (saves I/O) and evaluates the full regex only on matching rows inside the remaining blocks. The regex engine is still the source of truth, it just nees to do far less work.

What's the performance?

Literal-heavy patterns benefit most because they yield long, selective grams. Optional text and small alternations can still produce useful constraints. Patterns dominated by wildcards, broad classes, or short fragments produce weak plans and may fall back to scanning.

We measured the query path end-to-end on one of our clusters. The index path uses sparse grams to generate candidates, then verifies them with the exact regex. The scan path evaluates the regex through an unindexed full scan.

For this workload at concurrency sixteen, the sparse index provides 55.3 times the throughput, 61 times lower average latency, and 51.2 times lower p99 latency. From concurrency one to sixteen, indexed throughput grows by almost thirteen times. Full scans saturate much earlier because concurrent queries compete to read and test the same body of text.

This is especially relevant for agentic workloads. One agent may issue several parallel searches while refining an answer, and multiple agents may search at once. Candidate pruning significantly improves query efficiency to handle concurrent queries at scale.

Conclusion

The key idea was not a new regex engine. It was splitting the problem into two parts: fast candidate generation and exact verification. Similar two-stage approaches are already used in our query engine for dense and multi-vector search and probabilistic block filtering with bloom filters.

The agent still gets the search language it naturally prefers. TopK turns whatever literal information the pattern contains into a selective plan, then runs the regex only where certainty is needed.

References

• Regular Expression Matching with a Trigram Index, or, How Google Code Search Worked, Russ Cox
• The technology behind GitHub’s new code search, GitHub Engineering
• Fast regex search: indexing text for agent tools, Cursor