> ## Content Index > Fetch the complete content index at: https://debugly.dev/llms.txt > Use this file to discover other available public pages before exploring further. # The Model-Written Regex That Took Nine Minutes on One Input - URL: https://debugly.dev/ai-regex-catastrophic-backtracking/ - Published: 2026-10-09T14:10:00.000Z - Updated: 2026-10-17T05:56:21.000Z - Description: The generated pattern passed every test in the suite, then a single long string made it run for nine minutes. The pattern was not wrong. - Author: Rohit Bhadani - Tags: Bug Hunt, AI, Performance The endpoint hung, and the CPU pinned, and the profile said the time was in a regular expression, and the regular expression was one the model had written, and the expression was correct, it matched everything it should and rejected everything it should not, and the tests passed, and the tests were the reason nobody had looked at it, because a passing test suite is a strong signal, and the signal was true, and the truth was incomplete, because the suite tested what the pattern matched and never tested how long the matching took. This is the anatomy of catastrophic backtracking, and of the specific property that makes it invisible in review: the pattern's correctness and the pattern's cost are separate properties, and the review checks the first, and the second only appears on inputs nobody generated. This was Python's re module on a user-supplied string, and the mechanics are the same in JavaScript and Java, because all three use backtracking engines by default. ## Why the pattern was ambiguous I would like to say the hung endpoint was the problem, because that would be a shorter post, but it started at the exponential. The ambiguity is not a mistake in the pattern, it is a property of the pattern, and the property is invisible when the pattern is read, because reading a pattern shows what it matches, and the ambiguity is about how many ways it can try to match, and the trying is the engine's behaviour, and the engine's behaviour is not written in the pattern, so the review cannot see it, and the tests cannot see it either, because the tests use short inputs, and the exponential is small when the input is short. The pattern was correct on every input in the suite. The suite had no input long enough to make the cost visible, which is the gap, and the gap is where the incident lived. ## Why the model wrote it The model generated the pattern that matched the specification, because the specification was about matching, and the pattern matched, and the specification said nothing about cost, and the model optimised for the stated requirement, and the stated requirement was satisfied, and the unstated requirement, the cost, was not in the prompt, so it was not in the output, and the absence is the lesson: the model produces what the specification asks for, and the specification asked for matching, so the matching is what arrived, and the cost is the thing nobody asked for, and the thing nobody asked for is the thing that broke. This is the happy path shape from [why AI-written code is shaped like the happy path](https://debugly.dev/ai-code-is-happy-path-shaped/), which is why the two fixes look alike. ## The diagnosis The diagnosis was the input, and the input was found by the timing, and the timing was found by the profile, and the profile was run because the endpoint hung, which is the slow path to the answer, because the pattern's cost could have been measured before the hang, and the measurement is the test that was missing, and the missing test is the fix. The specific input was a long string with no match, which is the worst case, because the engine must exhaust every split before it can conclude that nothing matched, and the exhaustion is the exponential, and the conclusion is the nine minutes, and the nine minutes is the answer to a question that should have taken microseconds, and the microseconds are what the test should have asserted. ## What I changed **Bounded the repetitions.** The unbounded quantifiers became bounded, which caps the number of splits, and the cap converts the exponential into a polynomial, and the polynomial is fast enough that the worst case is no longer an incident, and the bound is the fix, and the bound is one character per quantifier. **Removed the nested repetition.** The inner repetition was folded into the outer, which removes the ambiguity, and the ambiguity's removal is the root fix, because the engine no longer has multiple splits to explore, and the exploration is what made the cost exponential, and the exploration is gone, and the cost is linear, and the linear is the behaviour the pattern always should have had. **Added a timeout.** The matching runs with a time limit, and the limit is the guard that converts the hang into an error, and the error is handled, and the handling is the fallback, and the fallback is the user seeing a failure rather than a hang, and the failure is the correct outcome for an input the pattern cannot handle in time, and the timeout is the control that bounds the damage even if another ambiguous pattern arrives. **Added a length check.** The input is rejected above a length, which is the cheapest guard, and the length is the input's cost proxy, and the proxy is imperfect but sufficient, because the exponential is a function of length, and the length check caps the input to the exponential, and the cap is the bound. **Added a cost test.** The suite now includes the long non-matching input, and the test asserts the match completes within a time budget, and the budget is the assertion, and the assertion is the regression guard, and the guard is the thing that would have caught the pattern before the hang, and the catch is the prevention. ## What I now do A backtracking regex engine explores every way a pattern can match, and a pattern with nested repetitions has exponentially many ways, so the cost grows with the input length and the worst case is a long non-matching string. Bound the repetitions, remove the nesting, add a timeout and a length check, and test the cost rather than only the correctness. The pattern was correct and the suite was green and the endpoint hung for nine minutes, and the nine minutes was the engine reading the same string exponentially many ways, looking for a match that was not there, and the looking is the cost, and the cost is the property nobody tested. Name that one property in review and this class of bug gets hard to ship. --- Published on [debugly.dev](https://debugly.dev/) by [Rohit Bhadani](https://debugly.dev/about/) | Founder of [Krova Cloud](https://krova.cloud/?ref=debugly.dev)