Distributional Program Analysis: Treating Large Language Models as Program Samplers

Abstract

A specification under-determines a program: prompted with one, a large language model (LLM) induces a distribution over candidate programs that respond to it in different ways. Pipelines that generate one program and analyze it discard the key artifact of that distribution: variation across samples. We propose distributional program analysis (DPA): analyze many LLM samples for the same task and aggregate analyzer outputs as cross-sample evidence about candidate program properties. The central statistic is an invariant's survival rate, the fraction of samples in which the analyzer infers it. Under stated sampling and analyzer assumptions, high-survival invariants mark properties on which independently sampled programs agree; fragile ones may indicate decoding noise, underspecification, or analyzer blind spots. Agreement is not correctness, and we are explicit about when the two come apart. We define survival, release a prototype, and report a HumanEval+ pilot in which high-survival invariants match reference-solution invariants in roughly four of five cases; filtering by survival also improves pass@1 at the same 20-sample budget. Variation is an analysis signal, not noise to hide.