Paper #54
Syntactic Variety, Behavioural Collapse: A Pre-registered Decision-Trace Audit of LLM-Generated Combinatorial Heuristics
Presenting author: Majed Bouchahma
Session: O02
Abstract
LLM-driven heuristic design frameworks, including FunSearch, EoH, ReEvo, and their successors, often treat independently sampled code outputs as a diverse candidate pool, with diversity assessed at the codehash or token-edit level. Whether this syntactic variation translates into behavioural diversity has not been tested directly. We report a pre-registered audit of 900 heuristic implementations generated by three 7Bclass open-weight code-specialised models on two NP-hard problems, 0/1 knapsack and one-dimensional bin packing, under a five-level prompt ablation from canonical labelling to full adversarial domain anonymisation. The Output Trajectory Signature (OTS), a decision-trace equivalence framework applied to a fixed nine-instance battery, reveals severe behavioural compression: 278 syntactically distinct knapsack implementations reduce to eight OTS classes (IDR = 34.75; 95% CI [21.88, 44.00]), and 126 bin-packing implementations reduce to thirteen (IDR = 9.69; 95% CI [6.08, 9.75]). Canonical labelling produces a directional shift in textbook-baseline matching for bin packing (PAI = 0.171), although its bootstrap interval spans zero; the canonical-adversarial distributional test remains underpowered. Behavioural convergence persists under full adversarial anonymisation, suggesting a structural prior that survives surface-level domain re-skinning. Code-hash diversity substantially overstates the effective behavioural coverage of LLM-generated heuristic pools; behavioural equivalence auditing should therefore precede claims of heuristic diversity, novelty, or prompt-induced exploration.