Algorithmic Solvability

This is a research pipeline, not a demo. It exists to answer one narrow methodological question honestly: when a model gets high accuracy on a task, did it learn the underlying algorithm, or did it learn a pattern that happens to correlate with the algorithm's output on the data it saw? The repo answers that by running its 32-task registry (17 sequence-transformation tasks, 15 tabular-classification tasks, each with a known ground-truth reference algorithm) through 9 model families, scoring each task against a 9-criterion evidence rubric, and assigning one of five verdicts: STRONG, MODERATE, WEAK, NEGATIVE, or INCONCLUSIVE.

The headline result is a split verdict the project reports without softening. Of the 14 classification tasks scored in the executed suite, results are frequently and legibly solvable from examples: 3 STRONG, 9 MODERATE, mean best accuracy 93.6% in distribution. Of the 16 sequence tasks scored, results mostly are not: 0 STRONG, 1 MODERATE, 11 outright NEGATIVE, mean best accuracy 38.1% in distribution, even with an LSTM trained for 200 epochs across 5 seeds. That asymmetry, not a single leaderboard number, is the actual finding. The engineering discipline behind it is real: 20 completed implementation tasks each with a written log, 462 passing tests, a documented deviation log explaining every place the implementation diverged from the design spec, and one traceable instance where the project caught its own baseline gaming a class-imbalance loophole and fixed the data sampler rather than loosening the acceptance criterion.

"My model got 98% accuracy" conflates two very different things: the model memorized surface statistics that happen to correlate with the right answer on this data distribution, or the model recovered something closer to the actual generating rule and will keep working when the distribution shifts. Standard ML evaluation, a single held-out test set drawn from the same distribution as training, cannot tell these apart. The premise of this repo is to build tasks where the answer is a deterministic Python function, generate labeled data from it, and construct out-of-distribution test conditions (longer inputs, wider value ranges, injected noise, irrelevant features) where a model that learned the real rule keeps working and a model that learned a shortcut breaks.

Two parallel task tracks cover different input modalities. The sequence track (S0-S3 tiers) covers variable-length token sequences: reversing, sorting, rotating, computing parity, running cumulative XOR, checking balanced parentheses. The classification track (C0-C3 tiers) covers fixed-width mixed numeric and categorical tabular inputs: a numeric threshold rule, an AND-of-two-features rule, a nested if/else rule, polynomial feature interactions. Both tracks scale by tier, from a random-label or majority-class control up through rules combining three or more primitives.

Every task has a deterministic reference algorithm and a verifier, so every generated label is checked against ground truth at generation time, and noise is injected into inputs only, after labeling, so a noisy example still has a correct label to evaluate against. Nine model families, from a majority-class baseline through logistic regression, decision trees, random forests, k-NN, gradient-boosted trees, an MLP, an LSTM, and a raw-sequence baseline, are trained on each task under four split strategies (IID, length extrapolation, value extrapolation, noise) and scored against a 9-criterion evidence rubric: 5 minimum criteria that gate a MODERATE verdict, plus 4 stronger criteria where clearing at least two upgrades MODERATE to STRONG.

The pipeline is a straight-line sequence of typed stages (task registry, data generator, splits, model harness, evaluation, multi-seed runner, reporting), plus two side branches that consume the baseline results: a diagnostic suite that adds deeper robustness evidence, and a bonus suite that tries to literally extract the learned rule. Diagnostics feeds sample-efficiency, distractor, noise, and feature-importance evidence back into verdict calibration. Bonus only runs against tasks that already scored MODERATE or better, checking whether the model actually recovered the rule rather than just scoring well on it.

The clearest evidence of engineering rigor is a caught and fixed measurement artifact. Task C2.1_and_rule (positive iff x1 > 50 AND cat1 == "A") is a genuinely easy rule, but under the original uniform sampler it was true only about 1 in 6 times, which let a plain majority-class baseline hit 86% accuracy on label imbalance alone, close enough to the roughly 99.8% best-model accuracy that the pipeline's own baseline-separation criterion failed and the task was mislabeled WEAK even though the rule itself was trivially learnable. The fix was not to loosen the threshold, it was to change the sampling distribution to draw positives and negatives roughly 50/50, verified with a 1,000-seed distribution check and two new regression tests. That repairs a measurement artifact instead of quietly relaxing the definition of success.

A few gaps are named honestly in the repo's own docs rather than discovered by outside review. requirements.txt lists xgboost and lightgbm, and the harness docstring claims to wrap them, but neither is imported anywhere. The gradient-boosted-trees family is sklearn's GradientBoostingClassifier. A Transformer sequence architecture is cataloged across the design docs and listed as an explicitly PENDING action item, but never implemented, a real gap given the sequence track's headline result is that nothing currently in the harness solves most sequence tasks. One of five declared split strategies (DISTRACTOR) has no generator function at the split layer, an explicitly logged deviation, with distractor robustness instead tested at the task level inside the diagnostic suite.

A few smaller choices show the same discipline: noise never touches labels, only inputs, enforced as a design rule rather than a convention, schemas are immutable frozen dataclasses rather than the heavier Pydantic already in the dependency list, a defensible minimal choice, and np.random.default_rng(seed) is used everywhere rather than the legacy RandomState API, for reproducibility across roughly 8,200 lines of pipeline code.

Verified against a fresh clone at commit 42aa8ac. pytest --collect-only reports 462 tests across 15 test modules, and the full suite passes 462 tests, 0 failed, in 113 seconds. python main.py smoke runs end to end and writes its artifacts to disk. src/ totals 8,223 lines across 15 modules (largest: diagnostic_experiments.py at 1,328 lines), and tests/ totals 5,991 lines.

The 32-task registry breaks down as 17 sequence tasks and 15 classification tasks, confirmed by directly importing the registry rather than trusting the README. Of the 16 sequence tasks scored in the executed baseline suite: 0 STRONG, 1 MODERATE, 2 WEAK, 11 NEGATIVE, 2 INCONCLUSIVE, mean best IID accuracy 38.1%, mean best OOD accuracy 25.9%. Best individual result: S1.4_count_symbol (MODERATE, 99.1% IID / 90.8% OOD, LSTM). Worst: S1.1_reverse and S3.4_rle_encode (both NEGATIVE, under 2% IID). Of the 14 classification tasks scored: 3 STRONG, 9 MODERATE, 1 INCONCLUSIVE, 1 NEGATIVE, 0 WEAK, mean best IID accuracy 93.6%, mean best OOD accuracy 97.0%. Decision trees and random forests win most classification tasks. No classical sklearn model wins a single sequence task, only the LSTM and MLP do.

Diagnostics and bonus experiments add further evidence: D1 sample efficiency positive on 6/8 task-model pairs, D2 distractor robustness on 4/5 tasks, D3 noise robustness on 4/4 classification tasks, and D4 feature-alignment precision at 9/9. B1 decision-tree rule extraction passed functional-equivalence checks on 9/12 classification tasks, and B2 DSL program search recovered an equivalent program on 7/9 sequence tasks. Sequence experiments are the compute cost center (EXP-S1 about 45 minutes, EXP-S2 about 21 minutes), against under a minute for most classification runs.

Only the S0-S3 and C0-C3 tiers are implemented. Harder compositional tiers were deferred at the design stage and never built, so the benchmark's conclusions apply to single-primitive-through-three-primitive tasks, not beyond. The sequence-track LSTM protocol was substantially upgraded partway through the project specifically because an earlier baseline run was judged too weak to trust, which is the right call, but it means the sequence track's NEGATIVE-heavy verdict distribution reflects a properly tuned protocol, not an under-trained model. No deployed service, API, or web UI exists. This is a local, CLI-driven pipeline that writes artifacts to disk. It is also a solo, three-day build (52 commits over three days, one author): the task-by-task discipline is real and verifiable, but it is the discipline of one person working fast with a documented process, not independent code review from a team.

The transferable idea is building acceptance criteria before running the experiments and refusing to relax them when a result comes back inconvenient. The C2.1_and_rule episode is the clean example: the honest response to a task failing the baseline-separation bar was to find out why, a sampling artifact, and fix that, not quietly lower the bar. The second lesson is in what the results actually say: tabular rule-classification tasks are, on this evidence, comfortably learnable from examples by ordinary tree-based models, while sequence-transformation tasks mostly are not, even with a properly tuned LSTM. That is a real, reportable negative result for the sequence track, not a failure of the project, and it is published with the same rigor as the positive one.