Automated Proving of Shannon-Type Entropy Inequalities via Fine-Tuned Language Models and Guided Tree Search

• URL: http://arxiv.org/abs/2606.05729v1
• Date: Thu, 04 Jun 2026 05:43:12 GMT
• Title: Automated Proving of Shannon-Type Entropy Inequalities via Fine-Tuned Language Models and Guided Tree Search
• Abstract summary: Proving Shannon-type entropy inequalities is a fundamental task in information theory.<n>We investigate whether small-scale large language models, fine-tuned on atomic proof steps, can automate this process.<n>We show that GPT-5.5 solves 1.7% samples under zero-shot prompting while Psitip solves 33.3% samples.
• Score: 50.16356451328644
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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\%).

Related papers

• Measuring in-context algorithmic reasoning in language models against an exact Bayes-optimal standard [0.010742675209112621]
  F-ICL is an in-context-learning benchmark for correct inductive inference.<n>We exhaustively enumerate all 1.5 billion programs of length $Lle13$ and compute the Bayes-optimal posterior in closed form.<n>Models answer up to 92% of queries correctly, yet 45 of 46 models yield distributions farther from the optimum than a keystroke reference.
  arXiv  Detail & Related papers  (2026-08-03T01:21:44Z)
• Constrained Decoding for Diffusion Language Models via Efficient Inference over Finite Automata [57.27430779838529]
  We present an exact and tractable algorithm for sampling from the constrained mean-field posterior under any constraint expressible as a finite automaton.<n>The approach guarantees constraint satisfaction by construction, supports both greedy and sampling-based decoding, and is compatible with parallel and block-wise decoding.<n> Empirical evaluations on Dream-7B and LLaDA-8 show substantial accuracy gains across various tasks.
  arXiv  Detail & Related papers  (2026-07-08T05:48:57Z)
• Reasoning Quality Emerges Early: Data Curation for Reasoning Models [58.56882815783977]
  We show that diverse and challenging reasoning examples can be identified using only the initial reasoning tokens.<n>Our method outperforms existing baselines by up to 1.7% while being 91% more token efficient.
  arXiv  Detail & Related papers  (2026-06-25T09:32:58Z)
• Models Can Model, But Can't Bind: Structured Grounding in Text-to-Optimization [54.749573452394664]
  We find that accuracy collapses as instance data grows, even when the formulation itself is simple.<n>We address this via a simple inference-time approach, BIND, which externalizes numeric data to structured files so the model binds data rather than from prompt prompt.<n>We validate our hypothesis by finetuning a model exclusively on binding and show that it outperforms end-to-end SFT and RL across three structurally distinct optimization categories.
  arXiv  Detail & Related papers  (2026-05-20T21:25:41Z)
• Distributional Energy-Based Models for Uncertainty-Aware Structured LLM Reasoning [40.342912574072024]
  Large Language Models produce structured outputs such as travel plans or code solutions.<n>Individual reasoning steps may appear correct while the output as a whole violates budgets, fails test cases, or contradicts earlier deductions.<n>We propose a learned quality scorer with deterministic analytical constraint penalties for verifying structured LLM outputs.
  arXiv  Detail & Related papers  (2026-05-15T17:08:27Z)
• Cognitive-Uncertainty Guided Knowledge Distillation for Accurate Classification of Student Misconceptions [11.509375725817195]
  We propose a two-stage knowledge distillation framework that mines high-value samples from existing data.<n>With augmented training on only 10.30% of filtered samples, we achieve MAP@3 of 0.9585 (+17.8%) on the MAP-Charting dataset.<n>Using only a 4B parameter model, we attain 84.38% accuracy on cross-topic tests of middle school algebra misconception benchmarks.
  arXiv  Detail & Related papers  (2026-05-14T12:17:38Z)
• LaTER: Efficient Test-Time Reasoning via Latent Exploration and Explicit Verification [35.08680804423239]
  Chain-of-thought (CoT) reasoning improves large language models (LLMs) on difficult tasks, but it also makes inference expensive.<n>We propose Latent-Then-Explicit Reasoning (LaTER), a two-stage paradigm that first performs bounded exploration in a continuous latent space.<n>LaTER projects final-layer hidden states back to the input embedding space, preserves the latent KV cache, and uses entropy and model-native stop-token probes to decide when to switch.
  arXiv  Detail & Related papers  (2026-05-08T06:23:58Z)
• On the Role of Reasoning Patterns in the Generalization Discrepancy of Long Chain-of-Thought Supervised Fine-Tuning [63.41902113656453]
  Supervised Fine-Tuning (SFT) on long Chain-of-Thought (CoT) trajectories has become a pivotal phase in building large reasoning models.<n>We conduct a comparative study using two sources of verified CoT trajectories generated by two competing models.<n>We find that SFT on textttDeepSeek-R1-0528 data achieves remarkably lower training loss, yet exhibits significantly worse generalization performance.
  arXiv  Detail & Related papers  (2026-04-02T07:00:54Z)
• When Shallow Wins: Silent Failures and the Depth-Accuracy Paradox in Latent Reasoning [16.505918019260964]
  We demonstrate that state-of-the-art models (Qwen2.5-Math-7B) achieve 61% accuracy through a mixture of reliable and unreliable predictions.<n>We show that 18.4% of correct predictions employ stable, faithful reasoning while 81.6% emerge through computationally inconsistent pathways.
  arXiv  Detail & Related papers  (2026-03-03T19:43:36Z)
• BeyondBench: Benchmark-Free Evaluation of Reasoning in Language Models [13.380359214677176]
  We introduce BeyondBench, an evaluation framework that avoids contamination from internet-scale training data.<n>Our framework covers 44 algorithmic tasks with a total of 117 variations, grouped into three difficulty levels.<n>We evaluate 101 language models, including 85 open-source and 16 closed-source models, spanning sizes from 0.5B to 141B parameters.
  arXiv  Detail & Related papers  (2025-09-29T02:49:01Z)
• Exploring the Limit of Outcome Reward for Learning Mathematical Reasoning [65.2421542320293]
  Reasoning abilities are crucial components of general intelligence.<n>Recent advances by proprietary companies, such as o-series models of OpenAI, have made remarkable progress on reasoning tasks.<n>This paper proposes a new RL framework, termed OREAL, to pursue the performance limit that can be achieved through textbfOutcome textbfREwtextbfArd-based reinforcement textbfLearning for mathematical reasoning tasks.
  arXiv  Detail & Related papers  (2025-02-10T18:57:29Z)
• The Surprising Effectiveness of Test-Time Training for Few-Shot Learning [59.309477460893916]
  Language models (LMs) have shown impressive performance on tasks within their training distribution, but often struggle with structurally novel tasks.<n>We investigate the effectiveness of test-time training (TTT) as a mechanism for improving LMs' reasoning and few-shot learning capabilities.<n>Our findings highlight the limitations of in-context learning for novel tasks and demonstrate the potential of test-time training to enhance language model adaptability.
  arXiv  Detail & Related papers  (2024-11-11T18:59:45Z)
• Faithful Chain-of-Thought Reasoning [51.21714389639417]
  Chain-of-Thought (CoT) prompting boosts Language Models' (LM) performance on a gamut of reasoning tasks. We propose Faithful CoT, a reasoning framework involving two stages: Translation and Problem Solving. This guarantees that the reasoning chain provides a faithful explanation of the final answer.
  arXiv  Detail & Related papers  (2023-01-31T03:04:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.