Search-Based Regular Expression Inference on a GPU

on YouTube ↗20m

" summary

Enumerative RE inference runs as a cost-ordered search over languages encoded as contiguous matrix of bitvectors built from the infix-closure of the example set, with C++ CPU and CUDA GPU implementations and a read-only language cache plus a hashed global uniqueness check. Precomputation turns concatenation into linear scans, enabling massive parallelism; on a 5,000-instance benchmark the GPU implementation is over 1000x faster on the hardest cases, but larger alphabets blow up cache size.

AI-written summary · about

" chapters (16)

1. 0:00Introduction
2. 1:03Synthesis without GPUs
3. 2:29Regular expression inference as a simple synthesis task
4. 3:56Regex inference challenges
5. 5:00Search space representation
6. 6:45Characteristic sequences
7. 8:53GPU-friendly bit vectors
8. 10:00Star semi rings API
9. 10:43Main algorithm and cache
10. 11:46Concatenation example
11. 13:56Uniqueness check
12. 14:16Benchmarks
13. 14:59Future work
14. 15:42Mathematical questions
15. 16:03Comparison with large language models
16. 16:27Q&A