# Van der Corput progressive expert scheduler

- ID: 1715
- Canonical URL: https://synthcore.org/idea/1715/van-der-corput-progressive-expert-scheduler
- API JSON: https://synthcore.org/api/idea/1715.json
- API Markdown: https://synthcore.org/api/idea/1715.md
- Verification status: mech_ok_no_baseline
- Source: [arXiv:2608.02559](https://arxiv.org/abs/2608.02559)
- Category: architecture
- Solves: stability, sample-efficiency, accuracy
- ML areas: moe-routing, transformer, training-dynamics
- Math tags: combinatorics, number-theory, approximation-theory
- Ratings: usefulness 7/10; difficulty 5/10; novelty 7/10

## Idea description

Replace random or greedy one-expert-at-a-time activation with a deterministic binary van der Corput sequence. At each training or inference step, the schedule chooses an expert whose cumulative usage remains close to its proportional target, while recursively balancing nested expert groups rather than only balancing individual experts.

## Mathematical statement

For D equally entitled leaves, let x_t in {0,...,D-1} be the expert selected at step t and let A_S(n)=sum_{t=1}^n 1{x_t in S} be the number of selections from a leaf set S in the first n steps. The ideal proportional count is n|S|/D, and the prefix discrepancy is E_S(n)=A_S(n)-n|S|/D. The paper's constructive schedule is the binary van der Corput ordering: write m=sum_{j>=0} b_j 2^j with bits b_j in {0,1}, define v_2(m)=sum_{j>=0} b_j 2^{-j-1}, and choose x_m=floor(D v_2(m)) for D a power of two. For the comb hierarchy, the resulting worst nested-prefix error is bounded by log(D)/(3 log 2)+1. A midpoint embedding gives general interval discrepancy at most the grid-aligned discrepancy plus 1/2. The transferable property is deterministic proportional coverage at every prefix, rather than merely good average frequencies.

## Key formulas

- $$v_2(m)=\sum_{j\ge 0} b_j2^{-j-1},\qquad m=\sum_{j\ge 0}b_j2^j,\quad b_j\in\{0,1\}.$$
- $$x_m=\left\lfloor D\,v_2(m)\right\rfloor,\qquad A_S(n)=\sum_{t=1}^{n}\mathbf 1\{x_t\in S\},\qquad E_S(n)=A_S(n)-\frac{n|S|}{D}.$$
- $$\max_{S\in\mathcal C}\max_{n\ge 1}|E_S(n)|\le \frac{\log D}{3\log 2}+1,$$
- $$\Delta_{\mathrm{interval}}\le \Delta_{\mathrm{grid}}+\frac12.$$

## Implementation notes

Integrate the scheduler into a top-1 MoE router or another progressive activation mechanism where one of D equally sized experts is selected per token or microbatch. For global assignment index m, compute the binary radical inverse v2(m), set the scheduled expert c=floor(D*v2(m)) for D a power of two, and either force c for a small calibration fraction or use c as the first candidate before selecting among the learned router logits. A hybrid implementation is: compute router logits l; reserve a fraction rho of assignments for the schedule; on scheduled assignments choose expert c; otherwise choose argmax(l), subject to capacity. Maintain A_S(n) for every node S in a fixed binary tree over experts and calculate E_S(n)=A_S(n)-n|S|/D after each batch. The exact mathematical inputs are v2, the one-hot schedule, and the logarithmic discrepancy budget B(D)=log(D)/(3 log 2)+1. Router logits, rho, tree layout, and capacity factor are empirical choices. First test a 4- or 8-expert Switch-Transformer-style MLP on CIFAR-100 or a small language-model corpus against random routing and standard capacity-factor routing at identical FLOPs. Record maximum nested-group discrepancy, expert-load variance, dropped-token rate, and validation loss. Success means fewer overflowed tokens and lower worst-prefix imbalance without worse perplexity or classification accuracy.

## Verification

- Status: mech_ok_no_baseline
- Mechanism evidence: yes
- Mechanism confirmed: yes
- Practical verdict: inconclusive
- Verdict: Built a readable binary van der Corput scheduler and numerical verification experiment in files vdc_moe_experiment.py and results.json. Across D=2..64, endpoint error at n=D was exactly 0, maximum nested discrepancy was 0.5..0.984 (always below the stated B(D)=1.33..3.0), and VDC leaf prefix error stayed below 1. In the synthetic capacity test with D=8 and 128 assignments, VDC had zero drops and zero load variance at capacity factor 1.0, versus 9.3% drops for random routing and 61.0% for greedy routing; this demonstrates the scheduling mechanism, not end-to-end model accuracy.

### Mechanism check

- Verdict: Built a readable binary van der Corput scheduler and numerical verification experiment in files vdc_moe_experiment.py and results.json. Across D=2..64, endpoint error at n=D was exactly 0, maximum nested discrepancy was 0.5..0.984 (always below the stated B(D)=1.33..3.0), and VDC leaf prefix error stayed below 1. In the synthetic capacity test with D=8 and 128 assignments, VDC had zero drops and zero load variance at capacity factor 1.0, versus 9.3% drops for random routing and 61.0% for greedy routing; this demonstrates the scheduling mechanism, not end-to-end model accuracy.
- Confidence: 9/10
- Limitations: The experiment is a scheduler/capacity simulation rather than a trained Switch-Transformer or CIFAR/language-model benchmark. It does not test router-logit integration, learned expert specialization, FLOPs, validation loss, classification accuracy, perplexity, GPU behavior, or the midpoint interval-discrepancy claim; the random baseline uses a reduced trial count for runtime.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 0.08055
- Paired wins: 6/8
- Benchmark verdict: no significant win

## Artifacts

- [bench_report.json](https://synthcore.org/code/634/bench_report.json)
- [registered_bench.py](https://synthcore.org/code/634/registered_bench.py)
- [report.md](https://synthcore.org/code/634/report.md)
- [report_bench_2026-08-31T202413.md](https://synthcore.org/code/634/report_bench_2026-08-31T202413.md)
- [results.json](https://synthcore.org/code/634/results.json)
- [vdc_bench.py](https://synthcore.org/code/634/vdc_bench.py)
- [vdc_moe_experiment.py](https://synthcore.org/code/634/vdc_moe_experiment.py)
- [Download all files as ZIP](https://synthcore.org/download/634)

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.