# Weave of Formal Thought

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 25 of its 42 references that are in the map.
- First posted on arXiv 24 Jun 2026.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

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

- [LoRA: Low-Rank Adaptation of Large Language Models](https://mlsanity.com/paper/2106.09685/) (2021)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [Categorical Reparameterization with Gumbel-Softmax](https://mlsanity.com/paper/1611.01144/) (2016)
- [FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning](https://mlsanity.com/paper/2307.08691/) (2023)
- [HuggingFace's Transformers: State-of-the-art Natural Language Processing](https://mlsanity.com/paper/1910.03771/) (2019)
- [Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation](https://mlsanity.com/paper/1308.3432/) (2013)
- [The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables](https://mlsanity.com/paper/1611.00712/) (2016)
- [Training Deep Nets with Sublinear Memory Cost](https://mlsanity.com/paper/1604.06174/) (2016)
- [Training Large Language Models to Reason in a Continuous Latent Space](https://mlsanity.com/paper/2412.06769/) (2024)
- [Importance Weighted Autoencoders](https://mlsanity.com/paper/1509.00519/) (2015)
- [PICARD: Parsing Incrementally for Constrained Auto-Regressive Decoding from Language Models](https://mlsanity.com/paper/2109.05093/) (2021)
- [Think before you speak: Training Language Models With Pause Tokens](https://mlsanity.com/paper/2310.02226/) (2023)
- [Gradient Estimation Using Stochastic Computation Graphs](https://mlsanity.com/paper/1506.05254/) (2015)
- [Recurrent Neural Network Grammars](https://mlsanity.com/paper/1602.07776/) (2016)
- [Guiding LLMs The Right Way: Fast, Non-Invasive Constrained Generation](https://mlsanity.com/paper/2403.06988/) (2024)
- [Variational inference for Monte Carlo objectives](https://mlsanity.com/paper/1602.06725/) (2016)
- [Tighter Variational Bounds are Not Necessarily Better](https://mlsanity.com/paper/1802.04537/) (2018)
- [XGrammar: Flexible and Efficient Structured Generation Engine for Large Language Models](https://mlsanity.com/paper/2411.15100/) (2024)
- [SynCode: LLM Generation with Grammar Augmentation](https://mlsanity.com/paper/2403.01632/) (2024)
- [Reweighted Wake-Sleep](https://mlsanity.com/paper/1406.2751/) (2014)
- [Unsupervised Recurrent Neural Network Grammars](https://mlsanity.com/paper/1904.03746/) (2019)
- [Training Chain-of-Thought via Latent-Variable Inference](https://mlsanity.com/paper/2312.02179/) (2023)
- [DisARM: An Antithetic Gradient Estimator for Binary Latent Variables](https://mlsanity.com/paper/2006.10680/) (2020)
- [Optimal Variance Control of the Score Function Gradient Estimator for Importance Weighted Bounds](https://mlsanity.com/paper/2008.01998/) (2020)

## Abstract (arXiv)

Large language models attain remarkable surface fluency on code, yet they do not formally guarantee the syntactic validity of their output, nor do they typically leverage the hierarchical structure that defines the target language. While existing constrained-decoding frameworks offer a solution to the former, they predominantly operate under rigid assumptions that preclude critical lexical mechanisms relied upon by modern parsers (e.g., Pythonic indentation). In this work, we present a formal engine and constrained decoder that is sound and complete with respect to the full Tree-sitter specification by augmenting generalized LR (GLR) parsing with a novel speculative-lexing construction that maintains concurrent lexer-state hypotheses synchronized with the GLR graph-structured stack. We also introduce Weave of Formal Thought (WoFT), a latent-variable fine-tuning method that trains the language model to interleave non-terminal grammar symbols directly into the generation process. Utilizing the reweighted wake-sleep (RWS) algorithm to optimize the importance-weighted evidence lower bound (IW-ELBO) of the surface text, the model learns to selectively retain formal derivations as an adaptive structural scratchpad. Across ten widely used programming languages spanning multiple paradigms, fine-tuning StarCoder2-3B with WoFT consistently outperforms text-only SFT baselines, achieving up to a 14.9% relative reduction in surface-token cross-entropy, and demonstrating that discretionary latent syntax recovers critical structural information that flat autoregressive training discards. Our code and implementation are publicly available at https://github.com/alexbouayad/formal.