Self-Aware Markov Models for Discrete Reasoning

• URL: http://arxiv.org/abs/2603.16661v2
• Date: Wed, 25 Mar 2026 14:59:45 GMT
• Title: Self-Aware Markov Models for Discrete Reasoning
• Abstract summary: We introduce a method based on learning a Markov transition kernel that is trained on its own outputs.<n>This design enables tokens to be remasked, allowing the model to correct its previous mistakes.<n>On the Sudoku-Extreme dataset we clearly outperform other flow based methods with a validity of 95%.
• Score: 8.161697757509701
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Standard masked discrete diffusion models face limitations in reasoning tasks due to their inability to correct their own mistakes on the masking path. Since they rely on a fixed number of denoising steps, they are unable to adjust their computation to the complexity of a given problem. To address these limitations, we introduce a method based on learning a Markov transition kernel that is trained on its own outputs. This design enables tokens to be remasked, allowing the model to correct its previous mistakes. Furthermore, we do not need a fixed time schedule but use a trained stopping criterion. This allows for adaptation of the number of function evaluations to the difficulty of the reasoning problem. Our adaptation adds two lightweight prediction heads, enabling reuse and fine-tuning of existing pretrained models. On the Sudoku-Extreme dataset we clearly outperform other flow based methods with a validity of 95%. For the Countdown-4 we only need in average of 10 steps to solve almost 96% of them correctly, while many problems can be solved already in 2 steps.

Related papers

• Let It Go or Learn to Self-Correct: Continuous Diffusion for Constrained Discrete Tasks [16.76819088768813]
  Denoising Diffusion Probabilistic Models generate samples by repeatedly denoising while keeping each update close to the current noisy state.<n>We show that standard diffusion sampling may preserve early mistakes, even when the model's clean predictions are informative.<n>We introduce self-correction training, which exposes the model to its own predictions, improving robustness to errors that arise during inference.
  arXiv  Detail & Related papers  (2026-09-08T16:45:52Z)
• Flow Reasoning Models: Scaling Reasoning Through Iterative Self-Refinement [13.205772367296353]
  We introduce Reasoning Flow Models, a training and test-time-scaling framework for structured reasoning with flow models.<n>A correct answer is a stable fixed point of the denoising dynamics, returning to itself when re-noised and re-solved.<n>We train flow models with a self-conditioning channel and close it at inference, letting them refine their own past predictions.
  arXiv  Detail & Related papers  (2026-06-28T02:10:36Z)
• How reliable are LLMs when it comes to playing dice? [0.0]
  We investigate the reasoning capabilities of large language models through a controlled benchmarking study on discrete probability problems.<n>Models achieve an average accuracy of 0.96 on standard problems but only 0.59 on counterintuitive ones.<n> Embedding misleading suggestions in the prompt reduces performance by up to 34%, with no model proving immune.
  arXiv  Detail & Related papers  (2026-06-05T17:59:42Z)
• Fast Unlearning at Scale via Margin Self-Correction [52.46927918952516]
  Language-model unlearning updates a trained model to behave as if it had not seen selected training examples.<n>MASC achieves a competitive forget-retain trade-off at a fraction of the computational cost of existing baselines.
  arXiv  Detail & Related papers  (2026-06-01T21:49:54Z)
• e1: Learning Adaptive Control of Reasoning Effort [88.51897900019485]
  Increasing the thinking budget of AI models can significantly improve accuracy, but not all questions warrant the same amount of reasoning.<n>Users may prefer to allocate different amounts of reasoning effort depending on how they value output quality versus latency and cost.<n>We propose Adaptive Effort Control, a self-adaptive reinforcement learning method that trains models to use a user-specified fraction of tokens.
  arXiv  Detail & Related papers  (2025-10-30T23:12:21Z)
• ConciseRL: Conciseness-Guided Reinforcement Learning for Efficient Reasoning Models [14.403953640255823]
  We introduce a novel score used as a reward signal within a reinforcement learning framework to guide models toward generating correct and concise reasoning traces.<n>This score is evaluated by a large language model acting as a judge, enabling dynamic, context-aware feedback beyond simple token length.<n>Our method achieves state-of-the-art efficiency-accuracy trade-offs on the MATH dataset, reducing token usage by up to 31x on simple problems while improving accuracy by 7%, and on the hardest problems, it outperforms full reasoning by +7.5% accuracy with up to 3.6x fewer tokens.
  arXiv  Detail & Related papers  (2025-05-22T19:56:35Z)
• Climbing the Ladder of Reasoning: What LLMs Can-and Still Can't-Solve after SFT? [59.418994222096885]
  We conduct a detailed analysis of model performance on the AIME24 dataset.<n>We categorize questions into four tiers (Easy, Medium, Hard, and Extremely Hard)<n>We find that progression from Easy to Medium tier requires adopting an R1 reasoning style with minimal SFT-1K instances.<n>Exh-level questions present a fundamentally different challenge; they require unconventional problem-solving skills.
  arXiv  Detail & Related papers  (2025-04-16T03:39:38Z)
• Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Sampling [90.86991492288487]
  evaluating constraint on every token can be prohibitively expensive.<n> LCD can distort the global distribution over strings, sampling tokens based only on local information.<n>We show that our approach is superior to state-of-the-art baselines.
  arXiv  Detail & Related papers  (2025-04-07T18:30:18Z)
• Subtle Errors in Reasoning: Preference Learning via Error-injected Self-editing [59.405145971637204]
  We propose a novel preference learning framework called eRror-Injected Self-Editing (RISE)<n>RISE injects predefined subtle errors into pivotal tokens in reasoning or steps to construct hard pairs for error mitigation.<n>Experiments validate the effectiveness of RISE, with preference learning on Qwen2-7B-Instruct yielding notable improvements of 3.0% on GSM8K and 7.9% on MATH with only 4.5K training samples.
  arXiv  Detail & Related papers  (2024-10-09T07:43:38Z)
• GRACE: Discriminator-Guided Chain-of-Thought Reasoning [75.35436025709049]
  We propose Guiding chain-of-thought ReAsoning with a CorrectnEss Discriminator (GRACE) to steer the decoding process towards producing correct reasoning steps. GRACE employs a discriminator trained with a contrastive loss over correct and incorrect steps, which is used during decoding to score next-step candidates.
  arXiv  Detail & Related papers  (2023-05-24T09:16:51Z)
• Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning [70.65666982566655]
  Permutation flow shop scheduling (PFSS) is widely used in manufacturing systems. We propose to train the model via expert-driven imitation learning, which accelerates convergence more stably and accurately. Our model's network parameters are reduced to only 37% of theirs, and the solution gap of our model towards the expert solutions decreases from 6.8% to 1.3% on average.
  arXiv  Detail & Related papers  (2022-10-31T09:46: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.