Proj. CRR: Adaptive Restarts for Stochastic Synthesis

Abstract

• 背景：
  • 假设：
    1. 搜索经常会经历一系列plateus平台期
    2. 合成时间的分布经常是heavy-tailed(越在后期，进展越慢）
• 方法
  • 提出了一种能加快合成速度的算法
• 效果
  • 能加快一个数量级
  • 实验：
    • 从生产代码中提取了新benchmark

1. Intro

Program synthesis：给定一组(输入、输出)对，合成一个程序，为每个输入产生指定的输出
随机合成：对程序进行随机搜索，在每步中，设当前搜索状态从程序p出发，得到下一个状态p'，p'比p的损失函数更小，更靠近目标输出。
本文：专注于随机合成的特征行为、出现这些行为的原因、如何利用这些观察结果来设计更高效的综合算法

随机过程可以是做一个马尔可夫过程，其转换概率可以被视为取决于测试用例、随机变化的分布(distribution of random changes)、