CIRCE Divines LLM Task Complexity from Constraint Structure

Chenhao Hong, Jiakai Xu, Kaushiki Singh, Yusen Zhang, Eugene WuarXiv 2026 · arXiv

TL;DR

CIRCE is a new framework that predicts whether a Large Language Model (LLM) will solve a reasoning problem correctly by analyzing its underlying "constraint structure." By converting natural language problems into constraint graphs, CIRCE provides a more accurate difficulty estimate than text-only embeddings, helping developers better route tasks or allocate compute resources before a model even starts generating an answer.

What Problem Does This Paper Address?

As LLMs are increasingly deployed for complex tasks like scheduling, logical reasoning, and math, knowing when a model is likely to fail becomes critical. If we can predict a failure in advance, we can route the task to a more capable model, allocate more "thinking time" (test-time compute), or suggest using external tools.

Existing difficulty estimators usually rely on raw text embeddings, LLM-generated difficulty ratings, or internal model activations. However, raw text often obscures the actual logical complexity, and internal activations are inaccessible for proprietary APIs. The authors argue that the true difficulty of a reasoning task lies in its constraint structure—how many variables are involved and how they interact. For example, a scheduling problem with 10 conflicting constraints is fundamentally harder than one with two, regardless of how the problem is phrased.

Methods

The authors introduce CIRCE (Constraint Intermediate Representation for Complexity Estimation), a workflow that moves from natural language to a structured complexity score in four steps:

  1. CIR Extraction: A "cheap" LLM (like Qwen3.8-27B) extracts the variables and constraints from the problem text into a JSON-like Constraint Intermediate Representation (CIR).
  2. Graph Compilation: A deterministic, rule-based compiler converts the CIR into a constraint graph. In this graph, "factor nodes" represent constraints and "variable nodes" represent the entities involved.
  3. Structural Encoding: The graph is converted into a feature vector using two possible methods:
  4. CIRCE-Stats: 41 handcrafted features (e.g., graph density, node degrees, number of logical operators).
  5. CIRCE-GNN: A Graph Neural Network (GNN) that learns to represent the graph structure. The authors tested both randomly initialized GNNs and those pretrained using self-supervised learning.
  6. Complexity Prediction: A gradient-boosted tree model takes these structural features and predicts the probability that a target LLM will answer the question correctly.
The CIRCE workflow: from natural language to constraint graph to complexity prediction.

Datasets

The researchers evaluated CIRCE across seven diverse reasoning benchmarks involving four different LLMs (Qwen3.5-9B, Qwen3.8-27B, Inkling, and GPT-6 Luna). The benchmarks included:

  • SATBench: Logical puzzles generated from SAT formulas.
  • FOLIO: First-order logic reasoning.
  • NLCO: Combinatorial optimization tasks (e.g., Maximum Value Cover).
  • Enigmata: Hamiltonian Path and Zebra Logic puzzles.
  • GSM8K: Grade-school math word problems.
  • BBH: Logical deduction tasks.

The study used 5,200 questions for GNN pretraining and 1,400 questions for fitting and evaluating the complexity predictors.

Summary of question counts and thinking effort settings for the benchmarks used.

Key Insights and Ideas

  • Structure is a Stronger Signal than Text: Structural features are much more indicative of LLM performance than text embeddings. Even a randomly initialized GNN outperformed every text-based baseline, suggesting that the raw topology of the constraints carries the most important information.
  • Separation of Concerns: By using an LLM only for semantic extraction (text to CIR) and a deterministic compiler for graph building, the system achieves high reliability. The CIR method achieved over 90% correctness in representing the original problem structure across all benchmarks.
  • Local vs. Global Features: While aggregate statistics (like the number of variables) are helpful, GNNs excel because they capture how the specific "query" connects to the constraints. For instance, in logic puzzles, a GNN can distinguish between a question that asks for a directly stated fact versus one that requires traversing a long chain of inferences.
Figure 3: Selected Amy-candidate connections in L1 and L2. Orange and blue squares denote fixed-position and query factors. Circles marked 5–7 are position nodes. Gray squares connect adjacent domain positions. The query shares the fixed clue’s position node only in L1. Other candidates and constraints are omitted.

Key Results

CIRCE significantly outperformed state-of-the-art baselines (like ADeLe and PredictaBoard) across all metrics:

  • Accuracy: The pretrained CIRCE-GNN reduced the average negative log-likelihood (NLL) of response correctness by 9.5% (from 0.465 to 0.421) compared to the strongest baseline.
  • Discrimination: It increased the AUROC (a measure of how well the model distinguishes between success and failure) from 0.691 to 0.730.
  • Feature Scaling: The authors found that adding more handcrafted features consistently improved performance, but the GNN still provided the best results by capturing complex interactions that manual features missed.
Figure 2: CIRCE-Stats with features added one at a time using training-only forward selection. NLL (left axis) and AUROC (right axis) are averaged over four models and three splits.

Limitations and Future Work

  • Scope of Constraints: CIRCE currently only works for problems where the constraints are explicitly stated in the input. It does not yet handle tasks where the model must infer constraints through its own reasoning process.
  • Failure Modes: Structural analysis only captures complexity inherent in the problem logic. It cannot predict failures caused by the model misreading a word or hallucinating a fact that isn't related to the constraint structure.
  • Future Directions: The authors suggest extending this representation to handle even richer constraints and exploring "predictor transfer"—seeing if a complexity model trained on one LLM can accurately predict the failures of a completely different model.

Summary updated

Abstract

Estimating whether a problem is too complex for a large language model (LLM) before the model attempts it can guide model routing, how to allocate test-time compute, and suggest the need for new tools to aid the agent. While existing estimators rely on the problem text, LLM-annotated task difficulty labels, or signals obtained after a model attempts to solve the problem, such as its hidden states, none explicitly leverage the constraint structure inherent in the problem: the variables to assign and how the constraints over them interact. We introduce CIRCE, which extracts a problem's structure by using a cheap LLM to construct a Constraint Intermediate Representation that deterministically compiles into the constraint graph. Across seven reasoning benchmarks (including SAT, logic, and math) and four LLMs, even a randomly initialized GNN encoder improves predictions of LLM response correctness, reducing negative log-likelihood from 0.465 to 0.423 and increasing AUROC from 0.691 to 0.727 relative to the strongest baseline for each metric.
BibTeX
@misc{hong2026circe,
  author = {Chenhao Hong and Jiakai Xu and Kaushiki Singh and Yusen Zhang and Eugene Wu},
  title = {{CIRCE Divines LLM Task Complexity from Constraint Structure}},
  year = {2026},
  eprint = {2610.41089},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.41089},
}
Figure