Skip to content
Book Open access

FLoRE: A Formal Language Benchmark for Robustness and Effectiveness Evaluation of LLM Reasoning

Nov 2026 · Proceedings of the 35th ACM International Conference on Information and Knowledge Management · 0 citations · 37 references

Abstract

Large language models (LLMs), especially recent reasoning-oriented models trained with reinforcement learning, achieve near-saturating accuracy on many reasoning benchmarks. However, it remains unclear whether these models truly reason over semantic structure or rely on superficial symbol patterns and familiar language forms. This issue is increasingly critical in the agent era, where reasoning systems must remain reliable under changing representations. We introduce FLoRE, a controllable evaluation benchmark for diagnosing LLM reasoning robustness and effectiveness using formal languages. By isolating reasoning from world knowledge, formal languages enable direct evaluation of structural reasoning with machine-verifiable ground truth. We defines two tasks: Formal Language Recognition and Grammar Induction and construct 25.5k data instances. Evaluating diverse reasoning and non-reasoning LLMs, we identify two universal failure modes. First, models exhibit severe symbol-binding fragility: changing symbolic representations while preserving semantics causes large drops on positive instances but increases accuracy on negative instances, revealing a strong default rejection bias under unfamiliar symbols. Second, many reasoning-oriented local LLMs show negation non-termination during grammar induction, failing to terminate reasoning on negative instances and instead exhausting large portions of the context window. Our results show that current LLM reasoning remains strongly dependent on surface symbol priors and lacks robust semantic invariance and termination stability. FLoRE provides a unified framework for systematically evaluating these properties in controllable formal-language settings. Code and data files are available at https://github.com/HoganZinger/FLoRE

Read PDF

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.