Skip to content

From Reasoning Strings to Partial Orders: Verifier-Certified Rule Transport through Quotient Policy Optimization

Aug 2026 · 0 citations · 36 references
Computer Science

TL;DR

This work introduces Verifier-Certified Rule Transport (VCRT), which replays adjacent operation pairs with native verifiers to preserve genuine prerequisites and constrains post-swap consistency, source retention, and policy drift.

Abstract

Many computations admit several valid execution orders because independent subgoals or disjoint state updates can commute. Reinforcement learning with verifiable rewards usually treats each successful trace as a separate token sequence, so serialization choices can be mistaken for logical dependencies. We introduce Verifier-Certified Rule Transport (VCRT), which replays adjacent operation pairs with native verifiers. Pairs whose two orders are accepted and reach the same canonical state provide commutation certificates; rejected or state-changing reversals provide anti-diamonds. VCRT uses anti-diamonds to preserve genuine prerequisites and assigns policy credit to the total probability mass of each certified orbit. It also constrains post-swap consistency, source retention, and policy drift. We evaluate leave-one-environment-out transfer across ProofWriter, CLRS, and Lean through a shared anonymized relation-graph interface. All training and checkpoint decisions are frozen before held-out evaluation, which uses one greedy trajectory per item without search or verifier feedback. VCRT obtains a 77.60% macro pass rate versus 64.53% for the strongest matched baseline, a paired gain of 13.06 points (95% bootstrap CI [12.58, 13.54]). Lean accounts for most of this gain at 33.49 points, while ProofWriter and CLRS improve by 2.85 points on average. Mechanism tests consistently favor anti-diamond supervision, whereas No-Orbit is statistically indistinguishable from full VCRT. The evidence does not establish a general benefit from exact orbit aggregation.

View source

Similar papers

Auditability Is Not One Property: Rule Overlap, Behavioural Agreement, and Composition in Reinforcement Learning

This work contributes an evidence-bounded audit and composition protocol, not a claim of universal interpretability or autonomous skill generation, and defines auditability as six separately testable predicates: trace integrity, lossless coding, rule coverage, behavioral agreement, composition quality, and value-model...

Hung-Ming Liu · 0 citations
#artificial intelligence Review Sep 2026

Proof-Gated Signing: Solver-Checked Transaction Guards that Hold Under State Drift for Onchain AI Agents

AI agents that control wallets read attacker-reachable content, so they can be steered into proposing harmful transactions. The usual last line of defense is a pre-signing check: a static allowlist, an LLM reviewer, or a transaction simulation. All three share a gap: the check describes the chain state at check time, b...

Bravish Ghosh · 0 citations
Sep 2026

Audit-First Recombination for Test-Time LLM Optimization Under Deterministic Verifiers.

Deterministic verifiers make test-time optimization of large language model (LLM) outputs practical, but modern search pipelines still waste budget on candidates that are structurally ineligible for semantic evaluation. Ineligibility includes parse failures, schema violations, and dependency breaks. These dead-on-arriv...

Rui Li, Shuang Cao · 0 citations
#machine learning Preprint Sep 2026

RAISE: Reinforcing Access Control Policy Synthesis in LLMs via Symbolic Evaluation

RAISE is introduced, which trains policy synthesizers from formal verification in two stages, verified supervised fine-tuning (SFT) followed by a reinforcement learning (RL) stage that learns from verifier signal, and it is found that SFT succeeds largely by letting models express authorization logic they already have.

Ying-Ming Zhou, Adarsh Vatsa, William Eiers · 0 citations
#artificial intelligence Preprint Sep 2026

ContractRL: Shielded Group-Relative Policy Optimization for Auditable Tool-Call Repair

Structured tool calls often fail after only a small number of fields violate a schema or an execution contract. Regenerating the complete object enlarges the action surface and makes repeated repair difficult to audit. We introduce ContractRL, a contract-constrained sequential repair protocol that models verifier-guide...

Miao-Bo Hu, Shu-Hao Hu, Xiao-Bo Guo et al. · 0 citations

Related blog posts

Microsoft Research Blog Nov 16, 2026

TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient

AI coding agents are increasingly help developers fix bugs and build features largely on their own, but every interaction with their models consumes tokens. In each session, an agent sends instructions, tool descriptions, and session history to its model. Most efforts to reduce this cost focus on individual tasks. Yet developers return to the same […] The post TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient appeared first on Microsoft Research.

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.