Hex-Grid Lattice MC Refinement: Design Principles

Problem

You already have a greedy hex-grid packer (pack.js / hexLayout.ts / future Rust port) that produces reasonable file-tree layouts. You want to push closer to optimal via Monte Carlo / Simulated Annealing. Four non-obvious design decisions determine whether the refinement actually helps or wastes compute; this skill documents them with benchmark numbers from a full multi-hour experiment session so you don't rediscover them the hard way.

Context / Trigger Conditions

• Hex-grid hierarchical layout for code visualisation (file → folder → pkg → root), hundreds to millions of nodes
• Greedy pack already exists and is "good enough" structurally
• Considering MC/SA refinement to reduce Σ link length further
• Or planning a from-scratch MC cold-start because "why not"
• Or seeing surprising symptoms (Swiss-cheese holes, folders refusing to nucleate, MC never improving on the last 20 minutes)
• Or choosing move set: random adjacency swap vs force-directed vs chain drag vs folder drift

Lesson 1 — Hole-guard > smart proposals

Claim: For dense-pack hex lattice MC, preventing isolated-hole formation gives more improvement than adding force-directed proposal generation. Geometric invariants beat smart directions.

Benchmark (1497 grafema nodes, warm-start from greedy, 15s wall budget):

Move set	Σ-link reduction over greedy
Random swaps + Metropolis (naive)	5.0%
+ hole-guard (reject hops that create interior holes)	6.9% (+1.9 p.p.)
+ force-directed top-3 flanking proposal	7.6% (+0.7 p.p.)
+ hierarchical force (intra before snap, external after)	7.5% (noise)
+ BFS bent chain drag	7.5% (noise)

Why hole-guard matters so much: Single-atom hop moves create vacancies when an atom jumps from a boundary cell into empty space. In Metropolis, hop-OUT is typically ΔE > 0 (stretches links, rarely accepted) while hop-BACK is ΔE < 0 (shortens links, almost always accepted). This breaks detailed balance — holes form at the boundary and migrate inward, turning the blob Swiss-cheese over thousands of iterations even though the energy metric keeps improving.

Fix: before allowing an atom to hop into an empty neighbour, verify the atom's old cell has ≥2 empty neighbours so it remains connected to the outer empty region after the hop. One-line check, 40% relative improvement:

const oldEmptyNeighbours = countEmptyHexNeighbours(a.coord);
if (oldEmptyNeighbours < 2) return null; // would create isolated hole

Non-obvious corollary: after adding hole-guard, force-directed proposals give only +0.7 p.p. more. If you're on a refinement budget, spend it on invariants, not smart proposals.

Lesson 2 — MC cold-start is infeasible vs structured construction

Claim: Lattice MC with local moves (swap, hop, drift, chain) cannot close the gap with a structured greedy pack for cold-start initialisation, even with hours of compute.

Benchmark (1497 grafema nodes, cold-start from alphabetic ring):

Budget	Σ-link reduction	vs greedy's 13026
Greedy (3.6s)	n/a	1.00×
MC 60s	31.4%	14.0× worse
MC 180s	38.3%	12.6× worse
MC 300s	42.9%	11.7× worse
MC 900s (15 min)	54.9%	9.2× worse

Log-linear scaling: ~20 p.p. of reduction per log-unit of wall-clock. Extrapolating to match greedy's 13026 requires +40 p.p. more = 2 more log units = 100× the 900s budget = 25 hours per run. Infeasible.

Why: glassy regime — the move set is too local. Acceptance rate stays at 16-22% even after 15 min (never drops below 1.5% which would indicate equilibrium). Convergence detector never fires. "Run until frozen" SA doctrine doesn't apply.

Practical rule: Always seed MC with a structured algorithm. For hex hierarchical layouts, use the greedy pack (pack.js / future Rust port). Reserve MC as a refinement layer for the final ~7% polish on warm starts, not as a primary algorithm.

Lesson 3 — Hierarchical nucleation-aware force trades raw energy for

folder cohesion

Claim: Gating force-direction on folder nucleation state (pre-snap intra-folder, post-snap external) improves folder cohesion by ~36% at the cost of ~13% raw Σ-link energy. This is the right tradeoff for code-map visualisation.

Design:

for each atom a:
  find the deepest ancestor folder F that is NOT yet in `connected` set
  AND whose size ≤ connCheckMaxSize
  if F exists:
    # pre-snap: crystallise F
    force(a) = Σ (sibling.pos - a.pos) × weight   over same-F links
    # fallback if no intra-F links: pull to F's centroid
  else:
    # post-snap of all ancestors: place the now-coherent unit
    force(a) = Σ (other.pos - a.pos) × weight  over external-to-leaf links

Benchmark (1497 nodes, cold-start 60s):

Force type	Σlinks	conn folders	adj invariants
Plain force (always external)	162873	273/518	186
Hierarchical (intra→external)	182678	379/518	159

Plain gives best raw energy. Hierarchical gives +38% more connected folders — the ones where a leaf actually condensed into a coherent blob. For a visualisation where folders should read as regions on a map, structure beats raw length.

Required fix — size-cap trap: folders above connCheckMaxSize never enter the connected set (BFS check too expensive). Without explicit skip in the ancestor walk, atoms below them are trapped forever in "pre-snap, pull toward huge-folder centroid" mode, producing weak scattered forces. Fix:

for (const fp of ancestors) {
  if (connected.has(fp)) continue;
  const size = folderAtoms.get(fp)?.size ?? 0;
  if (size > connCheckMaxSize) continue; // virtually nucleated
  activeFolder = fp;
  break;
}

This one-liner was missed in the first implementation and caused conn counts to plateau at 372/518. After the fix: 379/518 at 60s, 391/518 at 180s.

Lesson 4 — Bent chain drag via BFS vacancy routing

Claim: Row-shift chain drag (all atoms in a column shift by one hex) frequently breaks folder connectedness. Replacing it with BFS vacancy routing (the chain bends around obstacles) preserves invariants more often.

Design:

tryChainDrag(atom a, direction d):
  target = a.coord + d
  if target empty: use a plain hop instead
  if a.coord has <2 empty neighbours: abort (hole-guard)

  BFS from `target` through OCCUPIED cells, looking for the nearest empty
  cell. Each step uses any of 6 hex neighbours (chain bends freely).
  Max depth CHAIN_BFS_MAX_DEPTH=6.

  When empty cell found, reconstruct path: [target, c1, c2, ..., empty]
  Each cell path[i] moves to path[i+1]:
    - occupant of path[0] → path[1]
    - occupant of path[1] → path[2]
    - ...
    - occupant of path[k-1] → empty
    Finally `a` moves from a.coord to path[0] (now freed).

  Per-atom step direction can differ (that's the bending).
  ΔE: sum over affected atoms' external links; inter-chain links use
  new positions (both endpoints moved).

Why bending helps: a rigid row-shift only succeeds if the entire row can translate without breaking a registered connected(F) invariant. For a typical mid-nucleation cold-start, at least one atom on the row is usually a cut vertex of some folder — rigid shift fails. A bent chain can route around that atom, pushing only atoms whose folder is safe to re-arrange.

Not implemented (future): proactive constraint-aware BFS that weights candidates by "is this atom a cut vertex of an active invariant folder". Current implementation is reactive — it applies the chain, then rejects on invariant-check failure. Proactive would cost O(folder BFS) per step and wasn't worth it for our benchmarks, but may matter for much larger projects.

Consolidated verdict

For a refinement layer on top of greedy on ~1500-node projects:

• Minimum viable MC = plain random swaps + Metropolis + hole-guard gets 6.9% over greedy in 15s. ~100 lines of code.
• Maximum effort MC (force-directed + hierarchical + bent chain + nucleation invariants) gets 7.5% in 15s. ~600 lines of code.
• Net value of the fancy machinery: +0.6 p.p. (noise-level).
• Only reason to keep the complexity: folder cohesion guarantees (hierarchical nucleation) and map-like visual structure. If raw Σ-links is the only metric, delete it and use plain SA.

For million-node targets: MC is not the answer at all. Port the greedy pack to Rust (see REG-1102). MC refinement gives ≤7% that you can spend a week of engineering on; greedy port gives 100× throughput for 1-2 weeks of engineering. Cold-start MC gives an extrapolated 25h wall-clock for a result that greedy produces in seconds.

Example

// The minimum-viable refinement loop that captures 90% of the value:
async function refine(map, wallMs = 15000) {
  const rng = Math.random;
  const atoms = [...map.nodes.values()];
  const linksByAtom = indexLinksByAtom(map.links);
  const occupancy = buildOccupancy(map);

  // Temperature auto-calibrate from 300 random adjacency-swap ΔE samples
  const avgDelta = sampleSwapDeltas(300, atoms, linksByAtom, rng);
  const T0 = Math.max(1, avgDelta * 2);
  const T1 = Math.max(0.05, avgDelta * 0.01);

  const tStart = performance.now();
  let energy = computeTotalEnergy(map.links);

  while (performance.now() - tStart < wallMs) {
    const t = (performance.now() - tStart) / wallMs;
    const T = T0 * (T1 / T0) ** t;

    // Propose: 80% adjacency swap, 15% long-distance swap, 5% hole-safe hop
    const roll = rng();
    const move = roll < 0.80 ? adjSwap(atoms, rng, occupancy, map)
               : roll < 0.95 ? randomSwap(atoms, rng)
               : holeSafeHop(atoms, rng, occupancy);          // ← guards against Lesson 1
    if (!move) continue;

    const dE = computeDeltaE(move, linksByAtom);
    if (dE > 0 && rng() >= Math.exp(-dE / T)) continue;

    applyMove(move, occupancy);
    energy += dE;
  }
}

For the project-specific holeSafeHop implementation, look in sandbox/hex-sandbox/src/pack-mc.js (commit 6dcefd09) — it's a 20-line helper with the ≥2-empty-neighbours guard.

Notes

• All benchmarks used a 1497-node grafema codebase with 4351 real polyglot import edges (scan-links.mjs). Synthetic data with folder-biased random links gives artificially optimistic numbers.
• The connected.has(fp) check relies on a size-cap (connCheckMaxSize=200) — any folder above that never enters the invariant set; code walking ancestors must skip them explicitly (Lesson 3 size-cap trap).
• 0 reheats across every cold-start benchmark confirms the glassy regime: acceptance stays above the 1.5% reheat threshold even at 15 min. Don't budget based on "time to convergence" — budget on wall-clock.
• Chain drag is expensive per-call (BFS + multi-atom apply/undo). Cap its proposal frequency to 5% or less of the move mix, otherwise iteration throughput drops below the point where simpler moves give better ΔE/second.
• For incremental (warm-start with small changes) use case, MC is ideal: seeded from last layout, low-temperature polish. This is the ONE use case where MC beats everything including fresh greedy.

References

• Session artifact: sandbox/hex-sandbox/src/pack-mc.js at commit 6dcefd09
• Related skills:
  • .claude/skills/hex-grid-sa-o1-connectivity/ — O(1) connectivity check for SA migrate moves (orthogonal speedup)
  • .claude/skills/hex-grid-sequential-bfs-layout/ — the greedy algorithm this MC refines (pack.js)
• Linear: REG-1102 (Rust port of greedy for million-node target), REG-1100 (layout/view split), REG-1101 (npm package)
• Physics literature: Wolff 1989 (cluster moves), Binder & Heermann "Monte Carlo Simulation in Statistical Physics" (glassy regime)