Computer Science > Programming Languages
Title:When Is Program Structure Required? Certificate-Grounded Calibration of Program-Induction Difficulty
Abstract: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.
| Comments: | 26 pages, 1 figure, 24 tables, including appendices. Code and reproduction artifacts at this https URL |
|---|---|
| Subjects: | Programming Languages (cs.PL) ; Machine Learning (cs.LG) |
| Cite as: | arXiv:2611.24975 [cs.PL] |
| (or arXiv:2611.24975v1 [cs.PL] for this version) | |
| https://doi.org/10.48550/arXiv.2611.24975 arXiv-issued DOI via DataCite (pending registration) |
Submission history
Access Paper:
- HTML (experimental)
Additional Features
- Audio Summary
Current browse context:
References & Citations
- Google Scholar
- Semantic Scholar
BibTeX formatted citation
Bookmark
Bibliographic and Citation Tools
Code, Data and Media Associated with this Article
Demos
Recommenders and Search Tools
arXivLabs: experimental projects with community collaborators
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.