{"ID":3084866,"CreatedAt":"2026-06-05T06:46:15.197025399Z","UpdatedAt":"2026-06-07T05:32:54.120957816Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.05729","arxiv_id":"2606.05729","title":"Automated Proving of Shannon-Type Entropy Inequalities via Fine-Tuned Language Models and Guided Tree Search","abstract":"Proving Shannon-type entropy inequalities is a fundamental task in information theory that often requires constructing non-trivial linear combinations of known constraints, which is a combinatorial search problem that scales poorly with the number of random variables. We investigate whether small-scale large language models (0.6B--1.7B parameters), fine-tuned on atomic proof steps and combined with guided beam search, can automate this process. On a held-out test set of 60 inequalities spanning n=10 to 15 variables, our 0.6B fine-tuned model achieves an 85\\% proof success rate with tree search. GPT-5.5 solves 1.7\\% samples under zero-shot prompting while Psitip solves 33.3\\% samples. A systematic ablation study across training context length (4096 vs.\\ 8192 tokens) and data distribution (n=9-skewed vs not skewed) reveals that a 4096-token not skewed training distribution yields the best performance, with extended context and skewed data providing no marginal benefit. We further identify two dominant failure modes -- format failures and step quality degradation -- and verify that the beam-scoring heuristic is essential via a controlled ablation (random scoring reduces success from 83\\% to 23\\%).","short_abstract":"Proving Shannon-type entropy inequalities is a fundamental task in information theory that often requires constructing non-trivial linear combinations of known constraints, which is a combinatorial search problem that scales poorly with the number of random variables. We investigate whether small-scale large language m...","url_abs":"https://arxiv.org/abs/2606.05729","url_pdf":"https://arxiv.org/pdf/2606.05729v1","authors":"[\"Shing Yin Wong\",\"Shaocheng Liu\",\"Linqi Song\",\"Amin Gohari\",\"Cheuk Ting Li\"]","published":"2026-06-04T05:43:12Z","proceeding":"cs.IT","tasks":"[\"cs.IT\",\"cs.LG\"]","methods":"[\"Language Model\"]","has_code":false}