Pooled CRISPR screens with single-cell RNA-seq readout (Perturb-seq) have emerged as a key technique in functional genomics, but are limited in scale by cost and combinatorial complexity. Here, we reimagine Perturb-seq's design through the lens of algorithms applied to random, low-dimensional observations. We present compressed Perturb-seq, which measures multiple random perturbations per cell or multiple cells per droplet and computationally decompresses these measurements by leveraging the sparse structure of regulatory circuits. Applied to 598 genes in the immune response to bacterial lipopolysaccharide, compressed Perturb-seq achieves the same accuracy as conventional Perturb-seq at 4 to 20-fold reduced cost, with greater power to learn genetic interactions. We identify known and novel regulators of immune responses and uncover evolutionarily constrained genes with downstream targets enriched for immune disease heritability, including many missed by existing GWAS or trans-eQTL studies. Our framework enables new scales of interrogation for a foundational method in functional genomics.