CIRCE predicts LLM task complexity from constraint structure

[arXiv] A preprint by Hong, Xu, Singh, Zhang and Wu introduces CIRCE, a method that uses a cheap LLM to extract a Constraint Intermediate Representation from a problem and deterministically compiles it into a constraint graph, aiming to estimate task complexity before a model attempts it. According to the authors, existing estimators rely on problem text, LLM-annotated difficulty labels or post-attempt signals such as hidden states, and none explicitly uses the constraint structure inherent in the problem. Across seven reasoning benchmarks, including SAT, logic and math, and four LLMs, the authors report that even a randomly initialized GNN encoder improves predictions of LLM response correctness, reducing negative log-likelihood from 0.465 to 0.423 and raising AUROC from 0.691 to 0.727 relative to the strongest baseline for each metric. The work is a preprint and has not been peer-reviewed.