△ Mechanism confirmed, baseline not beaten 2026

Coloring-Probed Curvature Traces

Implementation & benchmark of arXiv:2607.05157 — Variance reduction with probing and Multilevel Monte Carlo in Lattice QCD

Usefulness7/10

Difficulty5/10

Novelty7/10

Optimization Speedup Stability Optimizer Regularization Training dynamics Probability Graph theory Linear algebra Numerical analysis

Source paper: Variance reduction with probing and Multilevel Monte Carlo in Lattice QCD arXiv:2607.05157 ⓘ · analyzed Aug 30, 2026

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

Idea description

Replace independent Hutchinson vectors used to estimate traces of neural-network curvature operators with graph-coloring probing vectors. Coordinates that are far apart in an interaction graph share a color, so one probe simultaneously covers many coordinates while reducing variance from localized off-diagonal matrix entries. Apply this to Hessian-trace regularization, Fisher-trace diagnostics, or layerwise curvature estimates used by adaptive optimizers.

Formulas

$$\mathbb{E}[\eta_j]=0,\qquad \mathbb{E}[\bar{\eta}_j\eta_k]=\delta_{jk},\qquad \operatorname{tr}(A)=\mathbb{E}[\eta^*A\eta].$$

$$\widehat{\operatorname{tr}}(A)=\frac{1}{M}\sum_{m=1}^{M}\eta_m^*A\eta_m.$$

$$\widehat{\operatorname{tr}}_{\mathrm{probe}}(A)=\frac{1}{M}\sum_{m=1}^{M}\sum_{r=1}^{C}z_{m,r}^*Az_{m,r},\qquad (z_{m,r})_i=\begin{cases}\epsilon_{m,i},&c(i)=r,\\0,&c(i)\neq r,\end{cases}\quad \epsilon_{m,i}\in\{-1,+1\}.$$

$$\operatorname{Var}(\eta^*A\eta)=\sum_{i\neq j}|A_{ij}|^2\,\mathbb{E}[|\bar\eta_i\eta_j|^2]\quad\text{for independent Rademacher probes}.$$

Mathematical statement

The stochastic trace identity uses a zero-mean probe vector $\eta\in\mathbb{C}^n$ satisfying $\mathbb{E}[\eta_j]=0$ and $\mathbb{E}[\bar\eta_j\eta_k]=\delta_{jk}$, where $\delta_{jk}$ is the Kronecker delta. For a matrix $A$, Hutchinson estimation is $\operatorname{tr}(A)\approx M^{-1}\sum_{m=1}^M\eta_m^*A\eta_m$. Construct a graph $G=(V,E)$ whose vertices are tensor coordinates or parameter blocks and whose edges connect coordinates with potentially large $|A_{ij}|$; a distance-$d$ coloring assigns a color $c(i)$ so that vertices at graph distance at most $d$ have different colors. For each color $r$, construct a probing vector $z_r$ whose entries on color $r$ are independent Rademacher signs and whose other entries are zero. Resampling signs preserves unbiasedness, while color separation suppresses contributions from localized off-diagonal entries.

Implementation notes

(1) Integration point: add this to a Hessian-trace regularizer or curvature-aware optimizer for a small Transformer or MLP. Let $A=H$, the minibatch-loss Hessian, and compute $Hz$ with Pearlmutter's Hessian-vector product; never materialize $H$. Build an interaction graph over parameter blocks. Connect blocks that occur in the same layer, share an attention head, or have a large pilot cross-block Hessian interaction. For a simple MVP, use a chain or grid graph over coordinates within each layer. (2) Pseudocode: construct $G$; form its distance-$d$ power graph; greedily color it to obtain $c(i)\in\{1,\ldots,C\}$. For each minibatch and repetition $m$, set $s=0$; for every color $r$, sample Rademacher signs on coordinates with $c(i)=r$, form $z_{m,r}$, compute $u=\operatorname{HVP}(loss,z_{m,r})$, and add $z_{m,r}^{\top}u$ to $s$. Return $s/M$ as the trace estimate. (3) Compute the trace identity, coloring, and quadratic forms exactly; estimate the graph from architecture connectivity or a pilot covariance of gradient blocks. Track empirical variance online. (4) First experiment: train a two-layer MLP and tiny ViT on MNIST or CIFAR-10, comparing dense Hutchinson probes with distance-1 and distance-2 probing at equal HVP count and equal wall-clock time. Measure trace variance, HVPs to target loss, and final accuracy. Success is at least 2x lower variance or equivalent accuracy with fewer HVPs.

Verification

Mechanism confirmed, baseline not beaten

Stage 1 · Toy mechanism gate: Passed ✓

Stage 2 · Mechanism transferred to benchmark: Confirmed ✓

Stage 2 · Practical benchmark result: Inconclusive

Methodology: 8 paired seeds, permutation test (p<0.05) against a learning-rate-tuned baseline. How verification works

Stage 1 — Mechanism check agent confidence 9/10

Built and numerically verified colored Rademacher probing on banded curvature matrices with chain distance coloring. The estimator was unbiased, variance followed the predicted 1/M law (log-log slopes -1.002 for dense and -0.969 for colored), and variance became exactly zero when coloring distance covered the matrix bandwidth. At equal HVP budget, distance-1 and distance-2 coloring reduced theoretical variance to 0.573x and 0.432x of Hutchinson, while distance-3 eliminated variance for the bandwidth-3 matrix.

Agent confidence: 9/10

Baseline: Equal-budget Hutchinson variance: 1.786 theoretical, with 1.677-1.984 observed across runs; finite-sample unbiasedness mean error was 0.0955.
Idea: Colored probing mean error was 5.7e-14; equal-budget theoretical variance ratios were 1.000 (d=0), 0.573 (d=1), 0.432 (d=2), and 0.000 (d=3), with observed variances 1.845, 1.068, 0.794, and approximately 0.

Limitations: This was a controlled toy verification using explicitly materialized symmetric banded matrices, not a neural-network Hessian-vector-product implementation. The interaction graph was a known chain rather than estimated from architecture or pilot curvature, and wall-clock speed, training loss, accuracy, Fisher traces, and real optimizer integration were not tested.

How to run: python3 experiment.py

Stage 2 — Benchmark vs. tuned baseline (arXiv:2607.05157) Sep 2, 2026

No significant difference vs. the tuned baseline (+2.8%, p=0.5039, wins 4 / 8 paired seeds).

Benchmark: Tabular regression (Friedman)
Model: mlp_tiny
Paired seeds: 8
Baseline mean: 8.1616
Idea mean: 8.3924
Effect (Δ): 0.2308 (+2.8%; negative = idea better)
Wins: 4 / 8 paired seeds
p-value: 0.5039 (permutation test, 20 000 shuffles)
Smallest detectable effect: ±9.5%
Mechanism: Confirmed ✓
Practical effect: Inconclusive
Baseline tuning: swept over 9 configs

Limitations:

Only the structurally matched registered tabular track was tested. The best idea setting selected no curvature intervention (lam=0), so the benchmark does not establish an end-to-end benefit from using colored traces for regularization; no vision, sequence, dynamics, or wall-clock/HVP-throughput comparison was run.

How to run: python3 run_stage2.py

Verdict computed by deterministic test code from paired-seed statistics — not by the language model.

Stage 2 — Benchmark Aug 30, 2026 latest Failed ✗

Agent confidence: 10/10

The registered Stage-2 tabular benchmark completed with the required baseline sweep, shared hyperparameter union, eight paired seeds, and bench.make_report output. Colored HVP probing reduced trained-model probe variance to 0.108x of dense Hutchinson, confirming the variance mechanism, but the best idea configuration used lam=0.0, had higher test MSE (8.3924 versus 8.1616), and was not significant (p=0.50385); therefore there is no demonstrated training-task win.

Baseline: Registered tabular/Friedman track, mlp_tiny, tuned cfg lr=0.03 lam=0.0: mean test MSE 8.1615795493 across 8 seeds.
Idea: Registered tabular/Friedman track, mlp_tiny, best colored cfg lr=0.03 lam=0.0: mean test MSE 8.3924094439 across 8 seeds; paired delta +0.2308298945; p=0.50385; trained-model probe variance ratio 0.107965.

Benchmark result