Semi-structured LLM Reasoners Can Be Rigorously Audited

Jixuan Leng, Cassandra A. Cohen, Zhixian Zhang, Chenyan Xiong, William W. CohenSubmission to ICLR 2026 · Rejected

TL;DR

Large Language Models (LLMs) often generate superficially plausible reasoning traces that obscure flaws or unfaithful shortcuts. To address this, the authors introduce Semi-Structured Reasoning Models (SSRMs), which output non-executable, Pythonic traces specifying step names, inputs, and outputs. This structure allows traces to be rigorously inspected using automated programmatic unit tests and statistical "typicality" audits—reliably flagging errors without sacrificing downstream task accuracy.

What Problem Does This Paper Address?

While Chain-of-Thought (CoT) prompting and reinforcement learning (RL) have significantly advanced LLM reasoning, models frequently produce unfaithful reasoning: explanations that sound convincing but do not reflect the actual decision process, or "right-for-the-wrong-reasons" solutions. In high-stakes domains like clinical decision-making, such failures are unacceptable. When using outcome-based RL rewards, models can even be actively reinforced for skipping critical protocol steps or making calculation shortcuts if they happen to stumble on the correct final answer.

Evaluating free-form natural language reasoning is notoriously difficult, whereas enforcing fully executable code is often too rigid. The authors ask: Can we train an LLM to structure its reasoning so we can automatically verify whether it faithfully followed a prescribed problem-solving protocol?

Methods

  1. Semi-Structured Reasoning (SSRMs): Instead of free-form text or executable code, models are trained to output a "partial program" (Python function stubs with docstrings) followed by a "program trace" consisting of symbolic function calls showing explicit arguments and returned values (e.g., Calling get_data(...), get_data returned ...).
  2. Two-Stage Training:
  3. Supervised Fine-Tuning (SFT): Bootstrapped using Program Trace Prompting (PTP) demonstrations from Claude Sonnet 3.5/3.7 across mathematical and reasoning benchmarks.
  4. Reinforcement Learning with Verifiable Rewards (RLVR): Trained using Group Relative Policy Optimization (GRPO) with rewards conditioned both on final answer correctness and structural regex conformance (e.g., proper tags and consistent function definitions).
  5. Auditing Frameworks:
  6. Hand-Crafted Structured Audits: Trace logs are converted into a Pandas DataFrame. Audits run like Python unit tests (e.g., asserting that every extracted rule is passed to an evaluation function and accumulated in the total score).
  7. LLM-Generated Audits: Claude Sonnet 4.0 generates unit tests given a few sample traces, drastically reducing human authoring cost.
  8. Learned Typicality Audits: Probabilistic models (n-grams and Hidden Markov Models) model the sequence of reasoning step names. Traces in the lowest probability quantiles are flagged as anomalous/atypical, functioning as an abstaining classifier.

Datasets

  • Training:
  • SFT: 4,211 examples spanning BBH, GSM8K, MATH500, and MedCalcV2.
  • RLVR: English subset of DAPO-Math-17K combined with held-out clinical calculation tasks.
  • MedCalcBenchV2 (New Benchmark): A deduplicated, error-corrected revision of MedCalcBench separating tasks into two categories: MedCalcV2 Formulas (arithmetic/formula evaluation) and MedCalcV2 Rules (multi-step clinical rubric execution, e.g., PSI score).
  • Out-of-Domain Generalization Benchmarks: GPQA-Diamond, AIME24, CommonsenseQA, TruthfulQA, MedQA, MMLU-Pro (Biology and Health subsets), and PubMedQA.

Key Insights and Ideas

  • Traces don't need to execute to be testable: By framing reasoning steps as structured input/output logs, standard software testing practices (unit assertions, DataFrame queries) can verify whether an LLM skipped steps, reused variables improperly, or hallucinated outputs.
  • Failures differ fundamentally across task types: In formula-based problems, arithmetic errors were common but weakly correlated with final outcome failure (often due to soft-matching tolerances). In rule-based clinical tasks, structural reasoning failures (skipping a rule or failing to sum outputs) strongly predicted an incorrect final answer (a 22–26% drop in accuracy).
  • Atypical reasoning signals errors: The sequence of step names acts like a formal reasoning grammar. HMM typicality models revealed that atypical reasoning sequences had significantly higher error rates, allowing automated triage of questionable outputs without needing access to ground-truth answers.
  • Audit-guided inference: Typicality audits can guide test-time compute: by only resampling traces falling into the lowest typicality tertile, models match or exceed vanilla self-consistency while using ~45% fewer samples.

Key Results

  • No Accuracy Penalty: On Qwen2.5-7B, the SSRM achieved a 61.7% overall average across 12 benchmarks, outperforming the identically trained unstructured CoT baseline (60.8%) and standard Qwen2.5-7B-Instruct (58.0%).
  • Clinical Calculation Gains: On MedCalcV2 Rules, Qwen SSRM reached 43.2% accuracy compared to 38.4% for unstructured RL and 32.1% for Qwen2.5-7B-Instruct.
  • Audit Discriminative Power: Failing a structured audit on MedCalcV2 Rules correlated with severe performance drops (e.g., passing accuracy ~47% vs. failing accuracy ~21–26%, $p < 0.05$).
  • LLM-Generated Audits: Claude-generated audits matched hand-crafted tests, producing statistically significant error flags across nearly half of tested Big-Bench Hard (BBH) tasks ($p < 0.05$).

Limitations and Future Work

  • Step Execution Errors: Symbolic audits verify structural adherence (e.g., whether all rules were called and aggregated), but cannot easily verify whether the model correctly interpreted text within a single step.
  • Token Overhead: SSRMs consume substantially more tokens than standard CoT on clinical tasks (e.g., 2,260 vs. 425 tokens on MedCalcV2 Rules) due to verbose string arguments and redundant variable references.
  • Model Scale: Primary experiments were conducted on 7B–8B scale models (Qwen2.5-7B and Llama3.1-8B); evaluating scaling behavior on frontier models remains to be explored.

Summary updated

Abstract

Although Large Language Models (LLMs) have become capable reasoners, the problem of faithfulness persists: their reasoning can contain errors and omissions that are difficult to detect and that may obscure biases in model outputs. To address this issue, we introduce Semi-Structured Reasoning Models (SSRMs), which are trained to produce semi-structured representations of reasoning. SSRMs generate reasoning traces in a *non-executable* Pythonic syntax that names each reasoning step and marks its inputs and outputs. This structure allows SSRM traces to be automatically *audited* to identify reasoning flaws. We evaluate three types of audits: hand-crafted *structured reasoning audits*, written in a domain-specific language (DSL) implemented in Python; LLM-generated *structured reasoning audits*; and learned *typicality audits*, which apply probabilistic models over reasoning traces. We show that all of these methods can be used to effectively flag probable reasoning errors. Importantly, the auditability of SSRMs does not appear to compromise overall accuracy: in evaluation on twelve benchmarks and two model families, SSRMs demonstrate strong performance and generalizability relative to other models of comparable size.
BibTeX
@misc{leng2025semi,
  author = {Jixuan Leng and Cassandra A. Cohen and Zhixian Zhang and Chenyan Xiong and William W. Cohen},
  title = {{Semi-structured LLM Reasoners Can Be Rigorously Audited}},
  year = {2025},
  eprint = {2505.24217},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2505.24217},
}

Loading related content...

Figure