mlsanityData to 7 Oct 2026

Weave of Formal Thought

arXiv 2606.25987 ↗First posted 24 Jun 2026cs.CL cs.AI cs.LGcited by 0

On the map: LLM reasoning → Test-time compute and efficient thinking

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.

Key facts. No citing papers in the map yet (data through 7 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.

Builds on

25 of 42 references.

Closest ancestors · 1

Same direction, newest first

  1. 2023Think before you speak: Training Language Models With Pause Tokens3 Oct

Other references · 24

  1. 2021LoRA: Low-Rank Adaptation of Large Language Modelscited by 14,084
  2. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Modelscited by 12,302
  3. 2022FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awarenesscited by 3,611
  4. 2016Categorical Reparameterization with Gumbel-Softmaxcited by 2,708
  5. 2023FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioningcited by 2,551
  6. 2019HuggingFace's Transformers: State-of-the-art Natural Language Processingcited by 2,201
  7. 2013Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computationcited by 2,031
  8. 2016The Concrete Distribution: A Continuous Relaxation of Discrete Random Variablescited by 1,135
  9. 2016Training Deep Nets with Sublinear Memory Costcited by 825
  10. 2024Training Large Language Models to Reason in a Continuous Latent Spacecited by 763
  11. 2015Importance Weighted Autoencoderscited by 454
  12. 2021PICARD: Parsing Incrementally for Constrained Auto-Regressive Decoding from Language Modelscited by 402
12 more
  1. 2015Gradient Estimation Using Stochastic Computation Graphscited by 120
  2. 2016Recurrent Neural Network Grammarscited by 109
  3. 2024Guiding LLMs The Right Way: Fast, Non-Invasive Constrained Generationcited by 99
  4. 2016Variational inference for Monte Carlo objectivescited by 83
  5. 2018Tighter Variational Bounds are Not Necessarily Bettercited by 76
  6. 2024XGrammar: Flexible and Efficient Structured Generation Engine for Large Language Modelscited by 73
  7. 2014Reweighted Wake-Sleepcited by 66
  8. 2024SynCode: LLM Generation with Grammar Augmentationcited by 66
  9. 2019Unsupervised Recurrent Neural Network Grammarscited by 47
  10. 2023Training Chain-of-Thought via Latent-Variable Inferencecited by 46
  11. 2020DisARM: An Antithetic Gradient Estimator for Binary Latent Variablescited by 27
  12. 2020Optimal Variance Control of the Score Function Gradient Estimator for Importance Weighted Boundscited by 7

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026Thinking Before Constraining: A Unified Decoding Framework for Large Language Models
  2. 2026EPIC: Efficient and Parallel Inference under CFG Constraints for Diffusion Language Models
  3. 2026Think Through a Bottleneck: Hourglass Reasoning for Rigorous Induction
  4. 2025Enhancing Large Language Model Efficiencyvia Symbolic Compression: A Formal Approach Towards Interpretability
  5. 2023Emergent Representations of Program Semantics in Language Models Trained on Programs
  6. 2025Chain of Execution Supervision Promotes General Reasoning in Large Language Models
  7. 2024Assessing Code Generation with Intermediate Languages
  8. 2025R-Stitch: Dynamic Trajectory Stitching for Efficient Reasoning