Papers
arxiv:2611.24975

When Is Program Structure Required? Certificate-Grounded Calibration of Program-Induction Difficulty

Published on Nov 17
Authors:

Abstract

Certifying matched string-replacement tasks with one- and two-rule solutions shows that the examples provided strongly affect both the solution required and the programs generated by language models.

A program-induction benchmark is informative when its examples require the structure it aims to test. Yet a two-rule generator can produce demonstrations that a single rule also explains. We introduce certificate-grounded calibration, which constructs matched tasks with minimum solution lengths of one and two in a bounded string-replacement language. Complete one-rule enumeration and an executable two-rule witness certify the change before model inference. We evaluate 120 reference families with three to six shared examples, using 1,440 new model trajectories and 480 saved trajectories. Across Qwen3-8B and Olmo-3-7B-Think, displayed-task completion is 23.53-45.83 percentage points lower on certified separation tasks, while success on a wholly unshown witness pair is 8.40-13.45 points higher. These witness gains accompany lower agreement on uniformly sampled strings and 1.93-5.78% agreement on inputs that activate both reference rules. Recertification also reveals that a single unchanged example can exclude a shortcut and determine whether two rules are required. Together, these results show how the evidence supplied by examples shapes both the required solution and the programs models produce. The construction provides an executable testbed for comparing program search, final-answer delivery, and behavior on new inputs under verified task requirements.

Community

Sign up or log in to comment

Models citing this paper 0

No model linking this paper

Cite arxiv.org/abs/2611.24975 in a model README.md to link it from this page.

Datasets citing this paper 0

No dataset linking this paper

Cite arxiv.org/abs/2611.24975 in a dataset README.md to link it from this page.

Spaces citing this paper 1

Collections including this paper 0

No Collection including this paper

Add this paper to a collection to link it from this page.