- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper frames program identification from executions as recovering a program's behavior rather than its source string, since syntactic aliases are indistinguishable by execution. It shows that adaptive querying can strictly beat fixed query designs, on a constructed family and on a small finite language. For a restricted bitvector language, it also proves a width-cutoff theorem that allows uniqueness to be certified at a small width. Experiments on a few bit-manipulation tasks show reduced proof cost.
Critical strengths
Taking the behavior class as the target is well motivated, and the indistinguishability argument makes clear why string-level recovery is the wrong goal. The separation between routing and simultaneous coverage gives a simple, intuitive account of when adaptivity helps.
Critical weaknesses
The adaptive separations are not very general. They are shown on a purpose-built family and one small finite language, so it is unclear what insight carries beyond these specific constructions.
The evaluation does not scale. The empirical study uses a few closely related tasks and short programs, and it breaks down at moderately longer horizons.
Questions for authors
Can the adaptive advantage be characterized more generally, beyond the specific constructions?
What limits scaling to longer programs, and how would the method perform on a broader set of tasks?