Markov Chains

Follow this topic Ask about this topic

Latest papers

29 papers3 papers in the last four weeks, level with the four weeks before. 0.0% of all new papers.

PreSTO: Predictive Subtree Prefetching for Fast LLM Power Sampling
Oct 9, 2026Nan Jiang, Panagiotis Theodoropoulos, Wei DengLLM Inference Acceleration Markov Chain Monte Carlo
University of Texas at El Paso · Georgia Institute of Technology · Morgan Stanley
Average-Reward Reinforcement Learning for Multichain MDPs: A Hierarchical Decomposition Approach
Oct 7, 2026Huizhen Yu, Isaiah HeidtMarkov Decision Processes Average-Reward RL
Department of Computing Science University of Alberta, Canada
Discrete Wasserstein Flows for One-Step Generative Modeling
Oct 1, 2026Alessandro Micheli, Andrea Zerio, Samir BhattWasserstein Gradient Flows Markov Chains
Imperial College London London, United Kingdom · Department of Computer Science, Aalborg University, Copenhagen, Denmark; Centre for Frontier AI Research (CFAR), Institute of Advanced Intelligence and Computing (IAIC), A*STAR, Singapore · University of Copenhagen Copenhagen, Denmark
When Metropolis and Hastings Meet Bradley and Terry: Exact MCMC From Preference Voting
Sep 1, 2026Ariel Smogorghevski, Nir Rosenfeld, Yaniv RomanoMarkov Chain Monte Carlo Markov Models
Department of Data and Decision Sciences, Technion – Israel Institute of Technology · Department of Computer Science, Technion – Israel Institute of Technology · Department of Electrical and Computer Engineering, Technion – Israel Institute of Technology
Propensity Straight-Through Gradients for Discrete Stochastic Systems
Aug 26, 2026Jose M. G. Vilar, Leonor SaizStraight-Through Estimator Markov Chains
Biofisika Institute (CSIC, UPV/EHU), University of the Basque Country, P.O. Box 644, 48080 Bilbao, Spain · IKERBASQUE, Basque Foundation for Science, 48011 Bilbao, Spain · Department of Biomedical Engineering, University of California, 451 East Health Sciences Drive, Davis, CA 95616, USA
Data-driven Effective Modeling of Stochastic Chemical Reaction Networks
Aug 26, 2026Yuan Chen, Weize Mao, Dongbin XiuMarkov Chains Surrogate Modeling
Department of Mathematics, The Ohio State University, Columbus, OH 43210, USA.
Tensor Probabilistic Model Checking of Finite-Horizon Markov Chains (Extended Version)
Aug 1, 2026Jianlin Li, Nick Guo, Peter Ye +1Reachability Analysis Markov Models
David R. Cheriton School of Computer Science University of Waterloo, Canada
Mean-to-Score Discrete Diffusion: Posterior-Mean Denoisers for Score Entropy
Jul 23, 2026Jingyuan Li, Xiaoyi Jiang, Yixuan Jiang +4Constrained Generative Modeling Markov Models
Tsinghua University · Beijing Institute of Mathematical Sciences and Applications · Wuhan University +1
Concurrent Image Understanding and Generation: Self-Correcting Coupled Markov Jump Processes
Jul 14, 2026Minh-Quan Le, Armand Comas, Alexandros Lattas +7Masked Diffusion Models Markov Models
Google · Stony Brook University · Google DeepMind
A Markov Chain Approach to Preference Alignment
Jun 21, 2026Takuya Koriyama, Tengyuan LiangPairwise Preference Learning Pairwise Comparison
The University of Chicago
Mask, Sample, Revise: A Revisable CTMC Inference Stack for Guided Discrete Flow Matching Text-to-Speech
Jun 12, 2026Alef Iury Siqueira Ferreira, Lucas Rafael Stefanel Gris, Luiz Fernando de Araújo Vidal +4Flow Matching TTS Synthesis
Federal University of Goi´as, Goiˆania, Brazil · Federal University of Mato Grosso, Cuiab´a, Brazil · Elsa Speak, S˜ao Paulo, Brazil
A Continuous-Time Markov Chain Framework for Insertion Language Models
Jun 8, 2026Dhruvesh Patel, Benjamin Rozonoyer, Soumitra Das +3Markov Models Markov Chains
UMass Amherst · IBM Research · University of Toronto & Vijil
On the Error-Correcting Effects of Stochasticity in Discrete Diffusion
May 26, 2026William Yuan, Sungwon Jeong, Amirali AghazadehMarkov Models Diffusion Sampling
Georgia Institute of Technology
AI4BayesCode: From Natural Language Descriptions to Validated Modular Stateful Bayesian Samplers
May 18, 2026Jungang Zou, Alex Ziyu Jiang, Qixuan ChenMarkov Chain Monte Carlo Bayesian Inference
Department of Biostatistics, Columbia University
Discrete MeanFlow: One-Step Generation via Conditional Transition Kernels
May 12, 2026Fairoz Nower Khan, Nabuat Zaman Nahim, Md Sajid Ahmed +2Markov Models MeanFlow
Department of Computer Science, University of Kentucky, Lexington, Kentucky 40506, USA
Mixing Times of Glauber Dynamics on Masked Language Models
May 11, 2026Suvadip Sana, Sami Wolf, Neer Mehta +4Dynamical Systems Markov Chain Monte Carlo
Department of Statistics and Data Science Cornell University · Cornell University · Department Cornell of University Mathematics
From graphemic dependence to lexical structure: a Markovian perspective on Dante's Commedia
Apr 24, 2026Angelo Maria SabatiniComputational Literary Studies Markov Chains
The BioRobotics Institute Scuola Superiore Sant’Anna Pisa, Italy
Self-Correction as Feedback Control: Error Dynamics, Stability Thresholds, and Prompt Interventions in LLMs
Apr 24, 2026Aofan Liu, Jingxiang MengLLM Self-Correction Language Model-Based Control
1Peking University. · University of Chicago.
Neural Continuous-Time Markov Chain: Discrete Diffusion via Decoupled Jump Timing and Direction
Apr 17, 2026Jingyuan Li, Xiaoyi Jiang, Fukang Wen +5Markov Models Diffusion Language Models
2Beijing Institute of Mathematical Sciences and Applications · 3Wuhan University · 4MathonAI +1
An Empirical Markov Chain Car-Following (MC-CF) Model
Mar 29, 2026Sungyong Chung, Yanlin Zhang, Nachuan Li +2Intelligent Transportation Systems Markov Chains
Department of Civil and Environmental Engineering, University of Illinois Urbana-Champaign · Northwestern University Transportation Center, Northwestern University
Markovian Generation Chains in Large Language Models
Mar 11, 2026Mingmeng Geng, Amr Mohamed, Guokan Shang +2LLM Inference Diverse Text Generation
ENS-PSL & CNRS-Lattice · MBZUAI & Ecole Polytechnique · MBZUAI
Autocorrelation effects in a stochastic-process model for solving two-armed bandit problems
Mar 5, 2026Tomoki Yamagami, Mikio Hasegawa, Takatomo Mihana +2Multi-Armed Bandits Markov Chains
Department of Information and Computer Sciences, Saitama University, 255 Shimo-Okubo, Sakura-ku, Saitama City, Saitama 338–8570, Japan. · Department of Electrical Engineering, Tokyo University of Science, 6–3–1, Niijuku, Katsushika-ku, Tokyo 125–8585, Japan. · Department of Information Physics and Computing, The University of Tokyo, 7–3–1 Hongo, Bunkyo-ku, Tokyo 113–8656, Japan.
Sketch2Colab: Sketch-Conditioned Multi-Human Animation via Controllable Flow Distillation
Mar 2, 2026Divyanshu Daiya, Aniket BeraMarkov Chains Style-Conditioned Motion Generation
IDEAS Lab, Department of Computer Science, Purdue University
When does Chain-of-Thought Help: A Markovian Perspective
Feb 27, 2026Zihan Wang, Yijun Dong, Qi LeiMarkov Chains CoT Reasoning
New York University
Exact Discrete Stochastic Simulation with Deep-Learning-Scale Gradient Optimization
Feb 23, 2026Jose M. G. Vilar, Leonor SaizStraight-Through Estimator Markov Chains
Biofisika Institute (CSIC, UPV/EHU), University of the Basque Country (UPV/EHU), P.O. Box 644, 48080 Bilbao, Spain · IKERBASQUE, Basque Foundation for Science, 48011 Bilbao, Spain · Department of Biomedical Engineering, University of California, 451 E. Health Sciences Drive, Davis, CA 95616, USA
A Markovian View of Iterative-Feedback Loops in Image Generative Models: Neural Resonance and Model Collapse
Feb 22, 2026Vibhas Kumar Vats, David J. Crandall, Samuel GoreeMarkov Chains Model Collapse
Luddy School of Informatics, Computing, and Engineering, Indiana University, Bloomington, IN, USA · Department of Computer Science, Stonehill College, Easton, MA, USA
FedAvg-Based CTMC Hazard Model for Federated Bridge Deterioration Assessment
Feb 22, 2026Takato YasunoMarkov Chains Structural Health Monitoring
1Yachiyo Engineering Co., Ltd., Tokyo, Japan
Conditionally Site-Independent Neural Evolution of Antibody Sequences
Feb 21, 2026Stephen Zhewen Lu, Aakarsh Vermani, Kohei Sanno +4Markov Chains Molecular Generation
University of California, Berkeley · Mila - Québec AI Institute · Université de Montréal +4
Flow Matching for Offline Reinforcement Learning with Discrete Actions
Feb 5, 2026Fairoz Nower Khan, Nabuat Zaman Nahim, Ruiquan Huang +2Markov Chains Reinforcement Learning
Department of Computer Science, University of Kentucky · Department of Computing and Information Sciences, Rochester Institute of Technology

Oct 9, 2026J/K move · Enter open · S save

PreSTO: Predictive Subtree Prefetching for Fast LLM Power Sampling

Nan Jiang, Panagiotis Theodoropoulos, Wei Deng

University of Texas at El Paso · Georgia Institute of Technology · Morgan Stanley

LLM Inference Acceleration Markov Chain Monte Carlo Markov Chains

Open paper AskPDF arXiv

Power sampling improves large language model (LLM) reasoning at test time by sampling from a sharpened version of the base model's distribution. Its sampler, PowerMH, is slow because its Metropolis--Hastings (MH) updates are sequential: each accept/reject decision sets the state from which the next proposal is generated. Prior work reduces this cost by changing the sampler or the model (e.g., sequential Monte Carlo, approximate lookahead, distillation). We propose Predictive SubTree Prefetching (PreSTO), which accelerates PowerMH by prefetching future proposals and provably leaves its MH transition kernel unchanged. PreSTO views future MH outcomes as a tree of accept/reject decisions: in each model call, it generates the proposals of a prefetched subtree of this tree in one batch, then follows the realized path with the original MH acceptance rule. We also observe that MH reaches only a sparse, nearly unary part of each prefetched subtree, we further design a predictive traversal rule that chooses the subtree to maximize the predicted number of completed transitions. Across seven datasets and five base LLMs, PreSTO achieves median speedups of

1.71\times

1.91\times

, and

2.33\times

on PowerMH and its follow-ups EntropyCut and MultiTryMH, respectively; on the first two, it makes a median of

3.9\times

fewer model calls, each only

2.1\times

longer. On LCB V6 with Qwen3.5-9B, the predictive traversal rule is a further

1.25\times

1.37\times

faster than the default breadth-first traversal.