program-structure-certificates / GITHUB_README.md
system's picture
system HF Staff
Mirror GitHub f31f2ceadd54
fd74a4d verified
|
Raw History Blame Contribute Delete
3.43 kB
# When Is Program Structure Required? Certificate-Grounded Calibration of Program-Induction Difficulty
Wenzhang Du 路 Independent Researcher, China 路 arXiv preprint, November 2026
[Paper 路 arXiv:2611.24975](https://arxiv.org/abs/2611.24975) 路 [Technical report](https://dqswordman.github.io/technical-reports/program-structure-certificates/) 路 [涓枃浼磋](https://dqswordman.github.io/zh/technical-reports/program-structure-certificates/) 路 [Interactive Space](https://huggingface.co/spaces/DQSWORDMAN/program-structure-certificates)
A generator can use two string-replacement rules even when the displayed examples admit a one-rule solution. This artifact follows a matched pair of specifications through complete one-rule enumeration, executable two-rule witnesses, and the programs returned by language models.
[Reproduction guide](docs/reproduction.md) 路 [Result map](docs/result-map.csv) 路 [Data provenance](DATA_PROVENANCE.md) 路 [Frozen artifact v1.0.0](https://github.com/dqswordman/program-structure-certificates/tree/v1.0.0)
## Follow one archived task pair
From the repository root with Python 3.11 or newer:
python -B verify_manifest.py
python -B replay_fixture.py
The fixture checks the six-example pair in Figure 1. The control admits the single replacement from exa to azy. The separation example excludes that rule, and the shared two-rule reference satisfies both specifications. The command reports certified minima of **one** and **two**, then executes four saved Qwen and Olmo programs on the displayed, witness, uniform, and rule-active inputs. It uses the included archive and the Python standard library.
[![Three-panel example showing how changing one input-output example excludes the one-rule control solution.](docs/figures/construction.png)](docs/figures/construction.pdf)
## Results at a glance
Across both models and the three-to-six base-example settings, the certified separation tasks reduce displayed-task completion by **23.53 to 45.83 percentage points** and increase exact success on the wholly unshown witness pair by **8.40 to 13.45 points**. Agreement on strings activating both reference rules ranges from **1.93% to 5.78%** in the separation conditions. The archived tables distinguish these evaluation targets. [Primary panel](results/PRIMARY_PANEL_READABLE.csv) 路 [Broader-input panel](results/BROADER_PANEL_READABLE.csv)
## Replay the panel
Create an environment with NumPy, then run the full CPU check from the frozen tag:
python -m pip install -r requirements.txt
python -B reproduce.py --out replay
This reads **1,920 saved outputs**, checks **960 certificates** and **7,680 additional reference labels**, and regenerates the three comparison CSVs. The result map marks which historical analyses are available as aggregate tables and protocols. [Full instructions](docs/reproduction.md) 路 [Verification report](docs/reproduction_report.json)
## Citation
Cite Wenzhang Du, *When Is Program Structure Required? Certificate-Grounded Calibration of Program-Induction Difficulty*, arXiv:2611.24975 (2026). The [public release](PUBLICATION.md) lists the software and data licenses, the frozen revision and the [single offline download](https://github.com/dqswordman/program-structure-certificates/releases/download/v1.0.0/program-structure-certificates-v1.0.0.zip). [CITATION.cff](CITATION.cff) 路 [Version record](docs/release-manifest.json)