Catastrophic regex backtracking in boxed display-math extraction: unclosed `$$`/`\[` followed by many `\boxed{}` makes parse() take minutes while holding the GIL

Start in src/math_verify/parser.py, around make_latex_env_pattern (L258-L282), and inspect the lazy_latex_regex boxed-context patterns for display math. Reproduce with the supplied unclosed $$ or \[ input and compare pattern timings. Done when these inputs no longer cause superlinear parsing delays or lose the boxed answer at the timeout, while the issue’s unaffected input shapes still parse correctly.

Summary

parse() takes superlinear time, roughly cubic in the input length, when a prediction contains a display-math opener ($$ or \[) that is never closed and is followed by many \boxed{...}. The time goes to one regex: the boxed-context pattern built in lazy_latex_regex. It runs in C and holds the GIL, so while it runs every other thread in the process is frozen too.

Model output of exactly this shape is common in practice: degenerate generations that repeat \boxed{answer} until the token limit. One real HMMT response (54,944 characters, 2,745 \boxed{5940} after a closed $$...$$ block) took ~42 minutes in a single parse() call with the timeout disabled.

Environment

• math-verify 0.9.0, latex2sympy2_extended 1.11.0, Python 3.12.14, Linux
• The relevant code is unchanged on current main (ba3d3aa, src/math_verify/parser.py, make_latex_env_pattern around L258-L282)

Reproduction

Default parse() called from the main thread, so the default 5 s timeout is active:

import time
from math_verify import parse

for n in (80, 160, 320, 640):
    text = "$$\n" + "\\boxed{5940}\n" * n
    t = time.perf_counter()
    result = parse(text)
    print(f"n={n:4d} chars={len(text):5d} time={time.perf_counter() - t:5.2f}s result={result}")

Output:

n=  80 chars= 1043 time= 0.09s result=[5940, '5940']
n= 160 chars= 2083 time= 0.34s result=[5940, '5940']
n= 320 chars= 4163 time= 2.69s result=[5940, '5940']
n= 640 chars= 8323 time= 5.00s result=[]          # "Timeout during parsing", correct answer lost

With parsing_timeout=None, the same input at n=640 takes 20.7 s and does return [5940, '5940'], and the 2,745-group real sample took ~42 min. A heartbeat thread running alongside the call stalls for exactly the duration of the call, so the GIL is held throughout.

Which regex

Timing each pattern from lazy_latex_regex(LatexExtractionConfig()) on the n=320 input:

import time
from math_verify import LatexExtractionConfig
from math_verify.parser import lazy_latex_regex

text = "$$\n" + "\\boxed{5940}\n" * 320
for i, (pattern, priority) in enumerate(lazy_latex_regex(LatexExtractionConfig())):
    t = time.perf_counter()
    hits = sum(1 for _ in pattern.finditer(text))
    print(i, priority, hits, f"{time.perf_counter() - t:.2f}s")

0   0 0 0.00s
1  50 0 0.00s
2 100 0 0.00s
3 200 0 0.00s
4 300 2 0.00s
5  50 0 2.60s   <- latex_re_boxed (context="boxed")
6  50 1 0.00s

Pattern 5 alone, on different input shapes (n=320):

Input	Time
\boxed{5940}\n × 320	0.00 s
unclosed $$ + boxes	2.61 s
closed $$...$$, then boxes (the closing $$ acts as an opener)	2.65 s
unclosed \[ + boxes	2.89 s
unclosed $ or \( + boxes	0.00 s
boxes followed by a closing $$	0.00 s

The inline environments are not affected because their content patterns exclude \n. The display environments allow newlines and are affected.

Analysis

With context="boxed", the display-dollar content becomes:

display_dollar_content = r"(?:[^$]|\$(?!\$))"
rf"{display_dollar_content}*?\\boxed{{{display_dollar_content}+?}}{display_dollar_content}*?"
# wrapped as: (?<!\\)\$\$(?P<...>...)(?<!\\)\$\$

When no closing $$ exists, the engine retries every split: every \boxed{ for the first lazy group × every later } for the +? group (which may run past } and across further \boxed{) × a scan to the end for the trailing lazy group. That is O(k²·n) for k boxes in n characters, i.e. roughly cubic when k grows with n, consistent with the ~8× growth when n doubles from 160 to 320 above. display_content_bracket (\[ ... \]) has the same structure.

Possible directions, untested:

• Keep the boxed body from crossing a closing brace, e.g. [^{}] with limited nesting.
• Cap the content length.
• Use atomic groups or possessive quantifiers (Python ≥ 3.11).
• Check for a closing delimiter before attempting the boxed-context match.

Related

Different root causes, listed to avoid duplication:

• #65 / #63: hangs in SymPy evaluation of huge exponents.
• #22 / #42 / #50 / #55: the signal-based timeout is unavailable outside the main thread, which is why this regex is fully unbounded when parse() runs in worker threads.

Downstream, EvalScope now bounds each scoring call in a forked process (modelscope/evalscope#1897), but a fix in the pattern itself would help all users.