acceptodds
Under review as a conference paper at ICLR 2027

EXECUTION IS EVIDENCE: CERTIFIED SEMANTIC PROGRAM IDENTIFICATION

Abstract

A program can be identified by what it does even when its source syntax is unrecoverable. We study semantic program identification from partial executions with independently checkable correctness. First, a routing-and-witness condition gives an exact family with d + r adaptive versus d + 2d r fixed queries, and a separate nonlinear repeated-operator language admits exact worst-case optima 6 < 9, certified by a complete decision tree and an independently checked adversary DAG over all 10,974 behaviors. Second, for a fixed accumulator language we prove a width cutoff: two programs of length at most L agree at all bit widths iff they agree at width 2L + 1. This turns large-width uniqueness into a cutoff-width symbolic refutation without enumerating the input domain or the behavioral quotient. On eight adapted 32-bit Hacker’s Delight specifications, all 120 paired runs return independently checked programs. With the same cutoff reduction, adaptive witness queries use 3.125 replies and 0.304 seconds on average versus 4.375 replies and 0.335 seconds for structured fixed probes; holding the word and transcript fixed isolates a 4.47× reduction in terminal certification time. Under the same per-call conflict budget, the cutoff also raises horizon-six certification coverage from 1/8 at native width to 8/8. Together, the results connect adaptive observation design with proof-carrying semantic identification under explicit, executable contracts.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
Semantic program identification from execution admits a certified 6-vs-9 adaptive-query separation, while a \(2L+1\) width cutoff lets small independently checked refutations certify large-width programs and substantially reduce verification cost.

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_LF2gOpenReview ↗
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?

Reviewer_tC2WOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper lets you run a hidden program on inputs you choose, and you want to recover a program that behaves identically.

Critical strengths

Provably optimal query counts are convincing, which are kind of refreshing after only empirical papers.

Critical weaknesses

The abstract is extremely confusing to me, and the presentation overall is really difficult to understand.

What is d + r? What is 6 < 9? What is the "independently checked adversary DAG over all 10,974 behaviors"?

Those are answered more in the paper, but they should not be in the abstract.

By far the biggest weakness is the presentation. I could not understand what this abstract was saying and what problem they were trying to solve. It was really difficult to even identify the problem they were trying to solve, let alone the contribution.

Questions for authors

None

Reviewer_HJ7JOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies how to identify an unknown program by observing its execution results. The authors focus on two questions: how to reduce the number of executions needed to identify a program, and how to prove that the identified behavior is correct. The paper has three main contributions. First, it shows that adaptive querying can require fewer executions than fixed querying, with an example where the optimal numbers are 6 and 9. Second, it uses SAT solving and proof checking to verify the identified program behavior. Third, it introduces a width-cutoff theorem that allows verification using fewer bits for a specific set of operations. The authors evaluate their approach on eight bit-manipulation tasks and show improvements in both query count and verification time.

Critical strengths
  1. Clear theoretical results. The paper provides mathematical proofs for its main claims, including the advantage of adaptive querying over fixed querying.

  2. Improved verification efficiency. The width-cutoff theorem is an interesting result that reduces the cost of program verification under certain conditions. The experiments also show clear performance improvements.

  3. Detailed experiments. The authors compare different querying methods and report both successful and unsuccessful results, helping readers understand the approach's strengths and limitations.

Critical weaknesses
  1. Limited novelty. The idea of choosing the next input based on previous results is already widely used in program analysis and program synthesis. Although the authors provide mathematical proofs, it is unclear how much new insight these results offer compared to existing work.

  2. Limited applicability. The approach relies on a small set of supported operations. In particular, the width-cutoff theorem does not directly apply to common operations such as shifts and multiplication. This makes it difficult to apply the method to more complex programs.

  3. Scalability issues. Even with a simple instruction set, the method fails to certify any of the eight tasks when the maximum program length reaches 8 under the tested budget. This raises concerns about how well the method would work on larger programs.

  4. Limited evaluation. The main experiments use only eight similar bit-manipulation tasks. Also, the adaptive querying results and the width-cutoff theorem are tested on different programming languages. More diverse experiments would help show whether these ideas work well together in more general settings.

Questions for authors
  1. What new insight do your adaptive-querying proofs give beyond the input-selection strategies already common in program analysis and synthesis?

  2. Can the width-cutoff theorem be extended to common operations like shifts and multiplication, and if not, how would the method handle programs that use them?

  3. Why does certification fail on all eight tasks once programs reach length 8, and do you have results showing adaptive querying and the width-cutoff theorem working together on more diverse programs?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.