5arXiv cs.AI (Artificial Intelligence)·
Graph Sparse Sampling (GSS) breaks exponential horizon dependence in continuous MDP planning
Researchers introduce Graph Sparse Sampling (GSS), an online planning algorithm for continuous Markov Decision Processes that shares sampled futures across candidate decisions rather than branching separately per action, eliminating the tree structure of methods like MCTS. The approach exposes large GPU-friendly batches and uses heuristics to focus computation, with finite-sample performance guarantees showing polynomial (rather than exponential) dependence on planning horizon under suitable conditions. Empirical results on continuous-control tasks show GSS substantially outperforms tree-based planners at long horizons. The work formalizes when shared-future graph planning can avoid the curse of the horizon that afflicts sparse sampling trees.
Related guides (1)
Related events (8)
GRASP: Gradient-based Planning for World Models at Longer Horizons
Researchers from Berkeley, Meta, and collaborators introduce GRASP, a gradient-based planner designed to make long-horizon planning with learned world models more robust. The method addresses three core failure modes: ill-conditioned computation graphs from backpropagation through time, non-greedy loss landscapes with many local minima, and brittle gradients through high-dimensional vision models. GRASP lifts trajectory optimization into virtual states for parallel optimization across time, injects stochasticity into state iterates for exploration, and reshapes gradients to avoid problematic state-input gradient paths. The work is positioned in the context of scaling world models toward general-purpose simulators usable for control and planning.
GaP: Graph-as-Policy multi-agent harness for reliable robot automation via self-learning computation graphs
Researchers introduce Graph-as-Policy (GaP), a multi-agent coding harness that generates directed computation graphs combining perception, planning, and control nodes for robotic 'Variational Automation' tasks — those with high variation in object geometry and pose. GaP uses an internal simulation environment to rehearse and iteratively refine graph structures in parallel, improving success rates without relying solely on model-free policies. Evaluation across 8 new benchmarks (4 simulated, 4 real-world) shows significant outperformance over baselines. The work bridges agentic coding systems with interpretable robot programming and Task and Motion Planning.
Unified framework for generalization and sketching across variable-size inputs via random sampling maps
A new arXiv preprint introduces a theoretical framework for understanding how ML models trained on small inputs generalize to larger, unseen input sizes — covering sequences, graphs, point clouds, and tensors. The approach uses random sampling maps (generalizing sampling with replacement, random binning, and species sampling) to compare inputs of different sizes and derive explicit generalization and sketching rates. The framework applies to transformers, graph neural networks, and moment polynomials, among other architectures. This is a foundational theoretical contribution addressing out-of-distribution generalization across input dimensionality.
GADD: Gibbs-Accelerated Discrete Diffusion Achieves Polylog Sampling Complexity
This paper introduces Gibbs-Accelerated Discrete Diffusion (GADD), a corrector method for uniform-rate discrete diffusion models that constructs Gibbs posterior likelihoods directly from the concrete score function without additional training. GADD achieves O(polylog(ε⁻¹)) sampling complexity, the first such rate for diffusion-based samplers in this setting. Experiments on synthetic data, zero-shot text sampling, and zero-shot conditional music generation show consistent improvements in sample quality and wall-clock efficiency over Euler and CTMC baselines. The work also introduces a novel induction-based theoretical framework for analyzing predictor-corrector methods in discrete diffusion.
MDM-VGB: Theoretically grounded test-time scaling for masked diffusion models via reward-guided remasking
Researchers introduce MDM-VGB, a discrete diffusion sampler for Masked Diffusion Models that augments token unmasking with reward-guided remasking inspired by the Jerrum-Sinclair backtracking Markov chain. The method extends backtracking from a fixed prefix tree to a masked-state graph, enabling tokens to be unmasked and remasked at arbitrary positions to favor higher-reward partial configurations. The authors prove quadratic complexity and robustness to process-verifier noise, contrasting with exponential complexity of best-of-N heuristics, and validate on constraint-satisfaction benchmarks including Sudoku and QM9.
MG-ADSGD achieves optimal communication complexity for decentralized stochastic strongly convex optimization
Researchers propose Multi-Gossip Accelerated DSGD (MG-ADSGD), a decentralized stochastic optimization algorithm that simultaneously achieves accelerated dependence on both the condition number (√κ) and the network spectral gap (1/√(1-β)), a combination no prior stochastic method had attained. The algorithm couples gossip depth with mini-batch size so that additional communication rounds improve both consensus accuracy and gradient variance reduction. The resulting communication complexity is claimed to be the best currently known for decentralized stochastic strongly convex optimization up to logarithmic factors.
Adaptive Data Scheduling (ADS) improves LLM reinforcement learning post-training by 5.2% over GRPO
Researchers propose Adaptive Data Scheduling (ADS), a dual-level framework that replaces uniform sampling in RL post-training with adaptive distribution over semantic clusters and policy-boundary sample selection. Evaluated across three LLMs and seven reasoning benchmarks, ADS improves average accuracy by 5.2% over GRPO and generalizes across RL objectives. The method addresses a structural limitation in standard RL post-training pipelines by accounting for semantic data structure and evolving policy capability during training.
GraphBU: Graph-native block unit generator for MILP instances improves solver training data
GraphBU is a new method for generating synthetic Mixed-Integer Linear Programming (MILP) instances using graph-native block units that explicitly encode how local subproblems couple to the rest of an instance. The approach achieves ~0.934 average graph-statistical similarity to source families, ~96.7% feasibility preservation, and ~8% improvement in downstream Predict-and-Search training performance. The work addresses a practical bottleneck in ML-for-combinatorial-optimization research: the scarcity of realistic MILP instances from private or proprietary pipelines.