# Neuro-Symbolic Verification on Instruction Following of LLMs

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 88 references that are in the map.
- First posted on arXiv 25 Jan 2026.

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

- [Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena](https://mlsanity.com/paper/2306.05685/) (2023)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [SWE-bench: Can Language Models Resolve Real-World GitHub Issues?](https://mlsanity.com/paper/2310.06770/) (2023)
- [G-Eval: NLG Evaluation using GPT-4 with Better Human Alignment](https://mlsanity.com/paper/2303.16634/) (2023)
- [AutoGen: Enabling Next-Gen LLM Applications via Multi-Agent Conversation](https://mlsanity.com/paper/2308.08155/) (2023)
- [DSPy: Compiling Declarative Language Model Calls into Self-Improving Pipelines](https://mlsanity.com/paper/2310.03714/) (2023)
- [OpenAssistant Conversations -- Democratizing Large Language Model Alignment](https://mlsanity.com/paper/2304.07327/) (2023)
- [WildChat: 1M ChatGPT Interaction Logs in the Wild](https://mlsanity.com/paper/2405.01470/) (2024)
- [Why Do Multi-Agent LLM Systems Fail?](https://mlsanity.com/paper/2503.13657/) (2025)
- [GEPA: Reflective Prompt Evolution Can Outperform Reinforcement Learning](https://mlsanity.com/paper/2507.19457/) (2025)
- [LMSYS-Chat-1M: A Large-Scale Real-World LLM Conversation Dataset](https://mlsanity.com/paper/2309.11998/) (2023)
- [LLMs Get Lost In Multi-Turn Conversation](https://mlsanity.com/paper/2505.06120/) (2025)
- [Logic-LM: Empowering Large Language Models with Symbolic Solvers for Faithful Logical Reasoning](https://mlsanity.com/paper/2305.12295/) (2023)
- [Evaluating Large Language Models at Evaluating Instruction Following](https://mlsanity.com/paper/2310.07641/) (2023)
- [SWE-smith: Scaling Data for Software Engineering Agents](https://mlsanity.com/paper/2504.21798/) (2025)
- [MultiChallenge: A Realistic Multi-Turn Conversation Evaluation Benchmark Challenging to Frontier LLMs](https://mlsanity.com/paper/2501.17399/) (2025)
- [LINC: A Neurosymbolic Approach for Logical Reasoning by Combining Language Models with First-Order Logic Provers](https://mlsanity.com/paper/2310.15164/) (2023)
- [Benchmarking Complex Instruction-Following with Multiple Constraints Composition](https://mlsanity.com/paper/2407.03978/) (2024)
- [COLLIE: Systematic Construction of Constrained Text Generation Tasks](https://mlsanity.com/paper/2307.08689/) (2023)
- [Can Large Language Models Understand Real-World Complex Instructions?](https://mlsanity.com/paper/2309.09150/) (2023)
- [Evaluating the Instruction-Following Robustness of Large Language Models to Prompt Injection](https://mlsanity.com/paper/2308.10819/) (2023)
- [AGENTIF: Benchmarking Instruction Following of Large Language Models in Agentic Scenarios](https://mlsanity.com/paper/2505.16944/) (2025)
- [Following Length Constraints in Instructions](https://mlsanity.com/paper/2406.17744/) (2024)
- [Formal-LLM: Integrating Formal Language and Natural Language for Controllable LLM-based Agents](https://mlsanity.com/paper/2402.00798/) (2024)
- [LIFBench: Evaluating the Instruction Following Performance and Stability of Large Language Models in Long-Context Scenarios](https://mlsanity.com/paper/2411.07037/) (2024)
- [ReIFE: Re-evaluating Instruction-Following Evaluation](https://mlsanity.com/paper/2410.07069/) (2024)
- [M-IFEval: Multilingual Instruction-Following Evaluation](https://mlsanity.com/paper/2502.04688/) (2025)
- [Formally Specifying the High-Level Behavior of LLM-Based Agents](https://mlsanity.com/paper/2310.08535/) (2023)
- [PDL: A Declarative Prompt Programming Language](https://mlsanity.com/paper/2410.19135/) (2024)
- [When Models Can't Follow: Testing Instruction Adherence Across 256 LLMs](https://mlsanity.com/paper/2510.18892/) (2025)

## Built on by (most cited first, 4 of 4)

- [PatchWorld: Gradient-Free Optimization of Executable World Models for Agent Environments](https://mlsanity.com/paper/2605.30880/) (2026)
- [Who Holds the Pen? Let Specifications, Not Agents, Sign Off](https://mlsanity.com/paper/2609.29921/) (2026)
- [Agentic Cognitive Depth: Operational Criteria for Evaluating LLM Agents](https://mlsanity.com/paper/2610.04168/) (2026)
- [AgentSpy: Making AI Agent Behavior Observable](https://mlsanity.com/paper/2610.06001/) (2026)

## Abstract (arXiv)

A fundamental problem of applying Large Language Models (LLMs) to important applications is that LLMs do not always follow instructions, and violations are often hard to observe or check. In LLM-based agentic workflows, such violations can propagate and amplify along reasoning chains, causing task failures and system incidents. This paper presents NSVIF, a neuro-symbolic framework for verifying whether an LLM's output follows the instructions used to prompt the LLM. NSVIF is a universal, general-purpose verifier; it makes no assumption about the instruction or the LLM. NSVIF formulates instruction-following verification as a constraint-satisfaction problem by modeling user instructions as constraints. NSVIF models both logical and semantic constraints; constraint solving is done by a unified solver that orchestrates logical reasoning and semantic analysis. To evaluate NSVIF, we develop VIFBENCH, a new benchmark for instruction-following verifiers with fine-grained data labels. Experiments show that NSVIF significantly outperforms LLM-based approaches and provides interpretable feedback. We also show that feedback from NSVIF helps improve LLMs' instruction-following capability without post-training.