ReSyn: 일반화된 재귀적 Regular Expression 합성 프레임워크

실세계 regex는 깊은 중첩과 다수의 Union 연산으로 구성되어 전통적 프로그래밍-에-예제(PBE) 접근법의 일반화가 어렵다. ReSyn은 Regex Canonicalization으로 데이터 품질을 높이고, Set2Regex(10M 파라미터)와 학습 가능한 Router/Partitioner/Segmenter를 통해 재귀적으로 문제를 분해해 복잡한 패턴을 합성한다. RegExLib와 같은 벤치마크에서 SOTA 수준의 성능을 보여주고, 대형 언어모델(GPT-5) 대비 파라미터 효율성에서도 우수한 성능 차이를 보인다.

단락 1: 기존의 Seq2Seq 뉴럴 합성기는 입력 예제를 순차적으로 처리해 정규식을 생성하는 경향이 있으며, 이는 트리 구조의 깊은 중첩과 Union의 위치에 대한 장기 의존성을 포착하기 어렵다. 또한 입력 예제의 순차적 정렬은 permutation invariance를 방해한다. 단락 2: ReSyn은 데이터 차원의 정규화를 통해 예제 집합의 구조를 명확히 파악하고, Hierarchical Set Encoder를 통해 순서를 불필요하게 학습하지 않게 한다. 재귀적 분해 모듈(Router/Partitioner/Segmenter)은 학습된 정책으로 문제를 작은 부분으로 나누어 각 부분에 적합한 합성기를 적용한 뒤, Leaf에서 합성된 하위 Regex를 Bottom-Up으로 결합한다. 단락 3: 이 재귀적 인덕션 바이어스는 깊은 중첩과 다중 연산이 포함된 실제 Regex에서 비재귀적 방법보다 우수한 일반화 능력을 보이며, 3개 벤치마크에서 일관된 성능 향상을 달성한다.

• 전체 접근 방식: 데이터 정규화 → 바탕 합성기(Set2Regex) → 재귀적 분해(ReSyn)으로 구성된다. [입력] Positive 예제 집합 P, Negative 예제 N → [처리] Regex Canonicalizer로 정규화 → Set2Regex를 기반으로 부분 Regex를 생성하거나, Router에 의해 분해 전략을 선택한다. [합성] leaf 노드에서 부분 Regex를 합성하고, 내부 노드에서 Concatenation(SEG) 또는 Union(PART)으로 합성 결과를 결합한다. [출력] 최종 정규식 R. [계산 흐름] 입력 값 -> 연산(정규화, 인코딩, 디코딩) -> 산출물. 패턴: 입력값(문자열 집합) → 학습된 Router에 의한 분해 결정 → Segmenter/Partitioner에 의한 하위 문제 생성 → Set2Regex로 하위 Regex 합성 → 하위 Regex의 Bottom-Up 조합 → 최종 Regex.

• StructuredRegex, Snort, RegExLib의 벤치마크에서 ReSyn이 Baseline 대비 성능 향상을 보인다. StructuredRegex에서 Set2Regex+ReSyn은 Succ 97.60%, Acc 85.93%, MCC 95.23. Snort에서는 Set2Regex+ReSyn이 Succ 68.26%, Acc 41.61%, MCC 58.97. RegExLib에서도 Set2Regex+ReSyn이 강한 성능을 보이고, 대형 일반 추론 모델과의 비율에서도 경쟁력을 보여준다. GPT-5와의 비교에서 StructuredRegex와 Snort에서 ReSyn이 더 나은 합성 성공률을 보이고 RegExLib에서 Semantic Accuracy 측면에서 큰 차이를 보이는 경우도 존재한다. Ablation 연구에서 재귀 모듈(Router/Segmenter/Partitioner)의 기여를 분리해 분석했고, 비 재귀적 방법 대비 ReSyn의 재귀적 분해가 구조적 정확도와 MCC를 향상시킴을 확인했다. Set2Regex의 파라미터 수는 10M으로 Prax의 300M 대비 30배 이상 작은 규모인데도, 벤치마크에서 비슷하거나 더 좋은 성능을 달성한다. 모듈 간 의존성 없이도 base Synthesizer 중 Set2Regex가 우수한 성능을 보이며, 중첩된 정규식 구조에서 재귀 분해의 효과가 크다.

• Regex Canonicalizer: 다양한 regex 표현들을 표준 형식으로 정규화하고, 상호 교환 가능한 부분(regex)들을 추출한다. 후보 하위 Regex를 자동으로 구성해 학습 데이터로 사용한다. - Set2Regex: Hierarchical Set Encoder를 사용해 문자열 단위 임베딩을 구성하고, 이를 통해 글로벌 컨텍스트 벡터 c와 지역 임베딩 h'i를 생성한다. 디코더는 먼저 c에 주의하고, 그다음 h'i에 주의를 기울여 Regex를 생성한다. - ReSyn 프레임워크: Router는 Positive 예제 집합 P의 구조를 바탕으로 Segmentation(Concatenation) 또는 Partitioning(Union) 전략을 선택한다. Segmenter는 문자열의 경계에서 분할점을 예측하고, Partitioner는 유사한 패턴을 가진 문자열을 클러스터링한다. leaf 노드에서 Set2Regex를 이용해 부분 Regex를 합성하고, 내부 노드에서 점진적으로 결합한다. - NP-hardness: 정규식의 간결성 비용 및 문자열 정합성 비용의 최적 분해 문제는 NP-hard이며, 이는 학습 기반 접근의 필요성을 이론적으로 정당화한다. - 학습 및 구현: 전체 파라미터 수는 29.6M(Set2Regex 10M, Router 4.6M, Partitioner 7.5M, Segmenter 7.5M)이며, 선택적 beam search(k=500)로 디코딩한다. Appendix에 수식, 알고리즘, 및 구현 세부사항 포함.