pac-bayes-87f1ff67·3 events·first seen Aliases: PAC-Bayes
A new arXiv preprint introduces requential coding, a compression scheme where a teacher model selects training samples from the student model's own distribution, so the code records only teacher-student disagreements rather than the full data sequence. The resulting code lengths are independent of both parameter count and data entropy, yielding codes orders of magnitude shorter than prequential coding baselines. Plugged into a PAC-Bayes framework, the method produces state-of-the-art generalization guarantees for billion-parameter LLMs that tighten with scale in the compute-optimal regime, and reveals that larger models and ensembles become increasingly compressible relative to dataset size.
A new arXiv preprint models user-LLM interaction as a bilevel cheap-talk game and derives PAC-Bayes bounds showing two irreducible limitations: an 'expressivity floor' where language's finite channel capacity makes distinct tasks indistinguishable, and an 'objective-misalignment floor' where alignment constraints prevent reaching user-ideal outputs. The authors prove that prompt-conditioned LLMs cannot be universal problem solvers, as correct behavior on certain task families is provably unattainable even with infinite data, optimal training, or model scaling. The work suggests multimodal inputs and external memory as potential mitigations by increasing task-relevant information bandwidth.
ReuseRL formalizes agentic reinforcement learning through the Minimum Description Length (MDL) principle, extracting a shared skill dictionary from successful trajectories and augmenting the RL objective with a segmentation cost that penalizes idiosyncratic, non-reusable behaviors. The authors prove a PAC-Bayes generalization bound for this compression penalty. Evaluated on ALFWorld, TextWorld-Cooking, and Countdown-Stepwise, ReuseRL outperforms vanilla GRPO and round-length baselines on both in-distribution and out-of-distribution tasks.