When Hierarchical Architectures Help — and When They Should Not
This benchmark tests a specific claim:
Hierarchical architectures are not universally better than flat models. They should outperform flat models specifically on tasks where the target computation admits a sufficient, verifiable, compositional summary.
The benchmark includes both positive cases (where compositional summaries exist) and negative controls (where local summaries are insufficient).
| Model | tree_parity | Status |
|---|---|---|
| Oracle-HTN | 1.000 | Perfect — given block boundaries |
| Flat Transformer | 0.515 | Chance — can't solve compositional XOR |
| Learned-HTN | 0.515 | Chance — routing never converges |
| Two-Stage Learned | 0.515 | Chance — even pre-trained agent fails |
Oracle-HTN achieves perfect accuracy on positive tasks while matching flat
models on negative controls — exactly the separation the thesis predicts.
Full results across all 6 tasks in reports/BENCHMARK_REPORT.md.
Learned-HTN (Gumbel-softmax routing) degenerates to a flat transformer.
The two-stage experiment (pre-train LocalAgent to 1.000 on isolated blocks,
freeze, train router) confirms: even with a perfect agent, gradient-based
routing cannot discover discrete segment boundaries.
See docs/two_stage_training_thesis.md.
Classical ML baselines reveal the fundamental structure:
| Feature representation | DT accuracy (n=1k) | DT accuracy (n=50k) |
|---|---|---|
| 4 block parities (the decomposition) | 1.000 | 1.000 |
| 12 relevant bits (no decomposition) | 0.497 | 1.000 |
| 32 data bits (with noise) | 0.501 | 1.000 |
| Logistic Regression (4 parities) | 0.506 | 0.515 |
Decision trees with pre-computed block parities solve tree_parity with 1k
examples. Without decomposition, they need 50k (50×). Logistic regression
fails at ALL feature levels — XOR is unlearnable by smooth optimization.
See scripts/run_rf_experiment.py.
Our results match established complexity theory on parity learning:
| Setting | Sample complexity | Our result |
|---|---|---|
| SGD, no decomposition | n^Ω(k) (SQ lower bound) | Flat transformer ≈ 0.50 |
| SGD + CoT supervision | Polynomial (Kim & Suzuki 2025) | Oracle-HTN = 1.000 |
| Decision tree, with decomposition | O(2^k_local) | DT(4 parities) = 1.000 |
| Decision tree, without | O(2^k_total) | DT(12 bits) needs 50k |
| Linear model, any features | Impossible (XOR ∉ linear) | LogReg ≈ 0.50 always |
Full theoretical analysis with citations:
docs/parity_learning_complexity.md.
HAN's architecture — weak local models composed via coordination — belongs
to a lineage including Mixture of Experts (Jacobs et al. 1991), Hierarchical
MoE (Jordan & Jacobs 1994), Stacking (Wolpert 1992), and Boosting (Schapire
1990). The critical finding: no established method learns spatial
decomposition end-to-end from task loss at small scale. Methods that
succeed either don't decompose the input (boosting), have decomposition
given externally (Oracle-HTN, co-training), or use massive scale with
heuristics (Switch Transformer). The routing problem was already visible
in the HME literature 30 years ago. Full survey in
docs/parity_learning_complexity.md
(Section 8).
| # | Family | Type | Summary Type |
|---|---|---|---|
| 1 | Tree-of-Parities with Distractors | Positive | Block parity bit |
| 2 | Segmented Addition / Carry Propagation | Positive | Partial sum + carry |
| 3 | Tree Formula / Circuit Value | Positive | Subtree value |
| 4 | Sparse Certificate Retrieval | Positive | Certificate validity |
| 5 | Cross-Block Random Matching | Negative | None (global pairing) |
| 6 | Global Pseudohash Control | Negative | None (global mixing) |
pip install -r requirements.txt
# Run full benchmark (6 tasks × 4 models × 3 seeds, ~2h on CPU)
python scripts/run_full_benchmark.py
# Run two-stage experiment (pre-train + freeze + route)
python scripts/run_two_stage_experiment.py
# Run classical ML baselines (DT/RF/LogReg on all tasks)
python scripts/run_rf_experiment.py
# Generate analysis plots from results
python scripts/generate_analysis.py
# Run tests
pytest tests/- Flat Transformer: Encoder-only, [CLS] pooling. The null hypothesis.
- Flat + Intermediate: Same architecture + auxiliary intermediate heads.
- Oracle-HTN: LocalAgent per segment + GlobalAggregator, given ground-truth boundaries. The upper bound for hierarchy.
- Learned-HTN: Same architecture but must discover segments via Gumbel-softmax routing. The critical test (currently fails).
| Document | Contents |
|---|---|
reports/BENCHMARK_REPORT.md |
Full scientific report with statistical tests and plots |
docs/model_internals_deep_dive.md |
Verbatim samples, architectures, training milestones, weight evolution, classical ML baselines |
docs/two_stage_training_thesis.md |
Two-stage training insight + experimental results |
docs/parity_learning_complexity.md |
Theoretical complexity of parity learning (SQ bounds, leap complexity, CoT, DT/RF) |
docs/meta_han_demo_story.md |
How report writing itself demonstrated the HAN thesis |
CLAUDE.md |
Developer context for AI-assisted sessions |
src/
generators/ # 6 task families
models/ # 4 model architectures
training/ # Training loop, datasets, tokenizer
metrics/ # Accuracy and routing metrics
plots/ # Visualization utilities
scripts/
run_full_benchmark.py # Main: 6 tasks × 4 models × 3 seeds
run_two_stage_experiment.py # Two-stage Learned-HTN experiment
run_rf_experiment.py # Classical ML baselines (DT/RF/LogReg)
generate_analysis.py # Plots + significance tests
docs/ # Research docs, theses, theory
reports/ # Benchmark results (JSON) + plots + reports
configs/ # YAML configs
tests/ # pytest suite
- Splits: IID, length extrapolation, noise extrapolation, structure extrapolation
- Seeds: 42, 1042, 2042 (95% CI via t-distribution, df=2)
- Hardware: CPU-only (intentional — removes GPU non-determinism)
- Training: AdamW (lr=1e-3), cosine annealing, early stopping (patience 10)
MIT