# Stateful CARS: Exact Cross-History Reuse for Policy-Constrained LLM Agents

arXiv: https://arxiv.org/abs/2608.08282 · HTML: https://mlsanity.com/paper/2608.08282/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in General LLM agent frameworks and benchmarks, one of 16 directions in LLM agents and tool use.
- Builds on 14 of its 27 references that are in the map.
- First posted on arXiv 8 Aug 2026.

## Placed in

- LLM agents and tool use / [General LLM agent frameworks and benchmarks](https://mlsanity.com/agents/general-llm-agent-frameworks-and-benchmarks/)

## Builds on (most cited first, 14 of 14)

- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Toolformer: Language Models Can Teach Themselves to Use Tools](https://mlsanity.com/paper/2302.04761/) (2023)
- [Self-Refine: Iterative Refinement with Self-Feedback](https://mlsanity.com/paper/2303.17651/) (2023)
- [SWE-bench: Can Language Models Resolve Real-World GitHub Issues?](https://mlsanity.com/paper/2310.06770/) (2023)
- [WebArena: A Realistic Web Environment for Building Autonomous Agents](https://mlsanity.com/paper/2307.13854/) (2023)
- [ToolLLM: Facilitating Large Language Models to Master 16000+ Real-world APIs](https://mlsanity.com/paper/2307.16789/) (2023)
- [τ-bench: A Benchmark for Tool-Agent-User Interaction in Real-World Domains](https://mlsanity.com/paper/2406.12045/) (2024)
- [Gorilla: Large Language Model Connected with Massive APIs](https://mlsanity.com/paper/2305.15334/) (2023)
- [PICARD: Parsing Incrementally for Constrained Auto-Regressive Decoding from Language Models](https://mlsanity.com/paper/2109.05093/) (2021)
- [Probabilistic Inference in Language Models via Twisted Sequential Monte Carlo](https://mlsanity.com/paper/2404.17546/) (2024)
- [SynCode: LLM Generation with Grammar Augmentation](https://mlsanity.com/paper/2403.01632/) (2024)
- [Enforcing Temporal Constraints for LLM Agents](https://mlsanity.com/paper/2512.23738/) (2025)
- [ToolGate: Contract-Grounded and Verified Tool Execution for LLMs](https://mlsanity.com/paper/2601.04688/) (2026)
- [Future Validity is the Missing Statistic: From Impossibility to Phi-Estimation for Grammar-Faithful Speculative Decoding](https://mlsanity.com/paper/2605.07698/) (2026)

## Abstract (arXiv)

Tool-using language-model agents face constraints whose meaning changes with observations and prior actions. We study exact sampling from the model distribution conditioned on a hard stateful validator while reusing invalidity certificates across histories. Stateful CARS freezes a bank of sound state--continuation schemas within each attempt and removes every trajectory containing a certified continuation at a matching abstract state. An exact residual Doob transform samples from the resulting proposal. We give a checkable future-validity bisimulation condition, prove schema soundness, adaptive exactness, i.i.d. outputs, almost-sure termination, monotone acceptance, and compression invariance, and characterize computation by the number of reachable full-history product states. This number can be exponential for a history-dependent language model; the evaluated method therefore makes no generic finite-trie scalability claim. On enumerable workflows, its analytic law matches the valid conditional to 10-16 at validity probability 6×10-8, whereas state-aware local decoding can be 0.97 away. A matched comparison is negative: observation-keyed official CARS is cheaper in sampler steps (root/Stateful ratio 0.942 [0.934,0.951]), and the Qwen comparison is null (0.99 [0.90,1.08]). Cross-history transfer helps only in an internal matched-key ablation (1.27×). Thus the evidence supports exact schema-induced conditioning, not a systems advantage over CARS.