WorksComputer Science
CIRCE Divines LLM Task Complexity from Constraint Structure
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.
Introduction
Large language models (LLMs) are increasingly asked to solve complex problems in which constraints create dependencies among decisions. These problems include constraint satisfaction (e.g., arranging wedding seating while keeping some guests together and others apart), resource management and scheduling (e.g., assigning staff to shifts while respecting availability and coverage requirements), logical entailment (e.g., determining whether an expense qualifies for reimbursement under a company’s policy), and database editing under integrity constraints (e.g., deleting a customer record without leaving orders linked to a nonexistent customer). Although task success may be assessed from an LLM’s result, it remains difficult to predict in advance whether a particular problem is too complex for the model to solve reliably.
Complexity estimation predicts the probability that a given LLM will answer a problem correctly under a fixed inference protocol (prompting and generation settings). Estimates made before generation can support model routing ([6, 26]), allocation of test-time compute ([36]), and abstention on likely failures ([18]).
Existing approaches use text embeddings of the problem ([28]), LLM-generated ratings of required abilities such as logical reasoning and domain knowledge ([51]), or the target model’s internal activations ([53]). The latter requires internal model access unavailable in proprietary model APIs. These approaches also do not explicitly represent the problem’s variables and interacting constraints.
Constraint structure helps predict computational difficulty: random 3-SAT formulas are hardest near a critical clause-to-variable ratio ([23]), and SATzilla uses structural features to predict runtimes and select the solver expected to be fastest ([48]). Constraint structure also guides LLM task decomposition ([52]).
We therefore ask: (1) does constraint structure predict LLM response correctness, and (2) can it be recovered reliably from problem text?
One challenge is that natural-language problems often do not specify variables and constraints explicitly, and LLM-generated constraint graphs are unreliable: only 136 of 200 Hamiltonian path graphs are correct in our evaluation (68.0%; Table 3). Our key observation is that an LLM need only describe the variables, constraints, and query in an intermediate representation, which a deterministic compiler converts into a graph.
We introduce Constraint Intermediate Representation tation for Complexity Estimation (CIRCE), a workflow built on this separation of semantic extraction and graph construction. On the Hamiltonian path, this approach raises correctness to 92.5%. We develop 41 handcrafted graph features (CIRCE-Stats) and find that richer feature sets generally improve prediction. To capture interactions beyond aggregate statistics, we also use a graph neural network (CIRCE-GNN). We compare frozen encoders with random initialization or self-supervised pretraining on separate unlabeled problems. A lightweight, model-specific predictor maps either representation to the probability of a correct response.
We evaluate CIRCE against four prediction baselines and a constant predictor on seven reasoning benchmarks and four LLMs. Five-fold cross-validation over 200 problems per benchmark fits each predictor on approximately 160 training problems, with ten responses per problem supplying correctness labels. Relative to the strongest baseline overall for each metric, the pretrained variant reduces average negative log-likelihood of response correctness by 9.5% (0.465 to 0.421) and increases AUROC by 3.9 percentage points (0.691 to 0.730). Even a frozen, randomly initialized GNN encoder outperforms every baseline on average and nearly matches the pretrained variant. These results show that constraint structure recovered from text is a useful signal for predicting LLM failures before generation. Text-to-SQL and program synthesis are promising targets for future evaluation.
Related Work
Complexity Estimation for LLMs
Recent work predicts instance-level LLM performance using textual assessors ([28, 35]), semantic task-demand annotations ([51]), or the target model’s hidden representations ([53]). Complementary work estimates difficulty from problem content or answer plausibility ([41, 24]), or uses difficulty estimates to adapt reasoning strategies ([49]). A related line of work estimates response correctness using elicited confidence, inter-model response agreement, or historical correctness patterns ([40, 44, 45]). Although these approaches provide useful textual, semantic, representational, and behavioral signals, they do not explicitly model reasoning problems as constraint structures with interacting variables and constraints.
Structured Representations for LLM Reasoning
Prior work has explored symbolic representations for LLM reasoning ([29, 25]), relationships between problem structure and reasoning complexity ([19]), and limitations in LLM reasoning over complex data structures ((He et al., 2026)). Related work examines formal specification inference and reliable theorem proving ([21, 32]). Other studies examine compositional problem complexity ([46]) and constraint-based problem decomposition ([52]). Research on multi-constraint instruction following further shows that constraint composition and dependencies affect model performance ([43, 22]). While these studies show that problem structure and constraints matter for LLM reasoning, whether structural features extracted from a common constraint representation can predict correctness on individual problem instances remains underexplored.
Learning from Graph Representations
Studies show that LLMs struggle with structured graph reasoning problems, motivating explicit representations of relationships and dependencies ([9, 1]). Structural properties have also been used to predict solver performance through handcrafted features ([48]) and graph-based learning ([4] (Fu et al. 2025)). Graph neural networks, in contrast, learn representations through neighborhood aggregation ([20, 47]), including for language reasoning over knowledge graphs ([50]). Self-supervised methods such as GraphMAE ([16]) further enable graph representation learning without problem-specific labels. However, rather than using these representations to solve problems or support reasoning directly, we leverage the constraint structure to estimate the empirical difficulty of individual problems for a target LLM.
Method
The way constraints connect variables can affect the reasoning required to answer a problem. We use these relationships as a signal for complexity estimation. Extracting them directly from the problem using an LLM is challenging. CIRCE addresses this by asking the LLM to describe the variables and constraints in an intermediate representation (CIR), from which a rule-based compiler constructs the graph.
Figure 1 illustrates the workflow of CIRCE. We first extract a CIR and compile it into a constraint graph (§ 3.2). We then represent the graph using handcrafted features in CIRCE-Stats (§ 3.3) or a GNN with or without self-supervised pretraining in CIRCE-GNN (§ 3.4). Finally, a gradient-boosted predictor maps the structural representation to a correctness probability for the target model (§ 3.5).
Figure 1. CIRCE workflow. (a) An LLM extracts a CIR from the question, and a rule-based graph builder constructs its constraint graph. Examples from SATBench and GSM8K are abbreviated. (b) CIRCE-Stats uses handcrafted features. CIRCE-GNN produces a feature vector with GNN. Optional pretraining of the GNN masks and reconstructs node and edge attributes. (c) A gradient-boosted predictor maps the representation to an estimated score.
Problem Formulation
Given a problem , a language model , and an inference protocol , we measure how complex is for by the probability that a response is correct,
where lower means that is more complex for . To obtain enough labels for training and evaluation, we observe responses per problem for each model, using a fixed inference protocol. With indicating whether a response is correct, the empirical correctness rate is
From Problem to Constraint Graph
A CIR describes variables, constraints, types, domains, and the requested query. We prompt an LLM to translate the problem into this representation without solving it or asserting an answer. A rule-based graph builder checks the CIR format, reports parsing errors for correction, and compiles accepted outputs into a typed constraint graph .
There are two types of graph nodes. Factor nodes represent constraints and the query, while variable nodes represent declared variables, propositions, entities, and shared domain values. Edges connect factor nodes to their corresponding variable nodes. For example, creates a factor connected to bag count and weight ; creates another connected to cost and . The query factor connects to the requested cost .
The same graph builder is shared across benchmarks. Both syntax checking and semantic validation help assess whether the CIR preserves the problem’s variables, constraints, and query. Automated checks can trigger repair. Appendix § 9 provides the checks, repairs, and validation details.
CIRCE-Stats: Handcrafted Features
Structural features have been used to predict the difficulty of constraint-solving problems, as exemplified by SATzilla (Xu et al., [48]). As a first step of examining whether such features can be used to predict the correctness of LLMs on constraint problems, we introduce CIRCE-Stats, where we handcrafted 41 features to capture the structural information of the constraint graph: size (5), factor occurrences (4), degree (8), topology (5), query (3), and CIR operators (16). Appendix § 10 lists the features and their definitions.
CIRCE-GNN: GNN-based Features
Experiments in § 5.1 show that writing more handcrafted features continued to improve the model’s predictive accuracy. Yet, manual feature engineering may omit complex but predictive interactions between the constraints and the variables. We therefore use a GNN to encode the graph structure. We project each node’s attributes to an initial vector and use six GIN-style layers (Xu et al., [47]). Each node vector and edge embedding has 64 dimensions. At layer , is a trainable embedding, and sums incoming neighbor messages. denotes the nodes connected to , is a learned scalar, a feed-forward network, and LN layer normalization. The update is
A randomly initialized GNN is already a powerful tool in encoding graph features through its message-passing mechanism, while self-supervised pretraining may further enhance its accuracy (Hou et al., [15]). Thus, CIRCE-GNN-P uses encoder pretraining, and CIRCE-GNN-R skips pretraining and uses the randomly initialized parameters. CIRCE-GNN-P trains the GNN in a self-supervised manner by masking a portion of the node attributes and the edge attributes (Hou et al., [16]). The decoders predict six attributes: node subtype, factor type, operator counts, edge role and edge polarity. Let denote these six attributes and the average reconstruction loss for attribute . Node decoders receive , and edge decoders receive . The pretraining objective is
We freeze the GNN in both encoder variants after 100 pretraining epochs for CIRCE-GNN-P, and right after initialization for CIRCE-GNN-R. Let for a query node and 0 otherwise. We concatenate the coordinate-wise sum, mean, query sum and standard deviation of the final node vectors into the graph representation
Complexity Estimation
Both CIRCE-Stats and CIRCE-GNN give a structural representation without using correctness labels. We then fit a predictor to predict the correctness probability.
We use histogram gradient-boosted trees
where is a fitted regression tree, and is the representation after training-fold preprocessing. The predictor is fitted by Bernoulli log-loss against ten-attempt correctness rates and is used for both CIRCE-Stats and CIRCE-GNN.
Experiments
Evaluation Metrics and Baselines
We use grouped five-fold cross-validation for each benchmark/model pair. All methods are evaluated with three different random splits. In addition, both CIRCE-GNN variants average four encoder seeds, with matched random initializations. The primary metric is Bernoulli negative log-likelihood, defined as
Here is the observed success rate over ten attempts, and is the predicted correctness probability, clipped to . We also report AUROC [3].
We compare our methods against the following baselines:
C0: training-fold mean predictor
Self probability: calibrated model self-reported probability
ADeLe ([51]): a random forest predictor using 18 task-demand dimensions annotated by GPT-6 Sol, and an unguessability dimension
PredictaBoard ([28]): an assessor that predicts correctness from OpenAI text embeddings
Already Knows ([53]): a hidden-state predictor trained with temporal-difference learning
Models and Benchmarks
Our methods and baselines are evaluated on Qwen3.5-9B ([33]), Qwen3.8-27B ([34]), Inkling ([39]) and GPT-6 Luna ([27]), representing the latest generation of open-weight and proprietary LLMs at the time of our study.
A diverse set of reasoning benchmarks with explicit or implicit constraints is used (Table 1). For each benchmark, a subset of the problems is used for evaluation, and a larger, non-overlapping subset is used for pretraining our GNN. Qwen3.8-27B is used to generate the CIR for all the benchmarks (Appendix § 9). We set the thinking effort of the models based on the difficulty of each benchmark to prevent saturated accuracy on easier benchmarks (Appendix § 8). Among the models we evaluate, Qwen3.5-9B is the only model that we can deploy locally given the limitations of model weight access and GPU memory. It is therefore used as the only model to evaluate the Already Knows predictor. To match the behavior of the models used in the original paper, we set the thinking mode to off for Qwen3.5-9B.
Table 1. Question counts and thinking effort settings for models other than Qwen3.5-9B, whose thinking mode is always set to Off. Pretrain questions are used only for pretraining the GNN encoder of CIRCE-GNN-P. Evaluation questions are used for fitting and evaluating the predictors in all methods.
Main Results
Our methods, CIRCE-Stats and both variants of CIRCE-GNN, have lower NLL and higher AUROC on average across the seven benchmarks than every baseline (Table 2). To summarize overall performance, we additionally compute macro averages, giving equal weight to all 28 benchmark/model pairs.
CIRCE-Stats is a strong method in its own right, achieving a macro NLL of 0.4311 and AUROC of 0.7029. Compared with the respective best base-
lines, it reduces NLL by 7.26% relative to PredictaBoard (0.4648) and improves AUROC by 1.19 percentage points over ADeLe (0.6910). Without encoder pretraining, CIRCE-GNN-R achieves a macro NLL of 0.4227 and AUROC of 0.7266, also outperforming every external baseline on average. Pretraining further reduces NLL by 0.51% and improves AUROC by 0.38 percentage points relative to the random encoder. The results demonstrate the effectiveness of utilizing the structural information of the reasoning tasks through the extracted CIRs to improve the prediction of correctness. The results also support the use of GNN-encoded graph representations over the handcrafted features.
Compared with CIRCE-GNN-R, the pretrained variant brings the largest improvement on FOLIO, where AUROC is improved by 2.6 percentage points. The changes on the other six benchmarks are smaller. This modest improvement suggests that the graph representation and GNN architecture already provide useful features without pretraining. The advantage of CIRCE-GNN-P over CIRCE-Stats also varies across benchmarks. The largest gains occur on the Logical benchmark, where CIRCE-GNN-P reduces NLL from 0.5835 to 0.5227 (−10.4%) and increases AUROC from 0.6698 to 0.7649 (+9.5 percentage points), averaged over four models.
Among the three external baselines, ADeLe achieves the highest macro AUROC, whereas PredictaBoard achieves the lowest macro NLL across the four models. However, neither consistently outperforms Self probability on all models. We also
| Method | SATBench NLL↓ / AUC↑ | FOLIO NLL↓ / AUC↑ | NLCO NLL↓ / AUC↑ | Hamiltonian NLL↓ / AUC↑ | Zebra NLL↓ / AUC↑ | GSM8K NLL↓ / AUC↑ | Logical NLL↓ / AUC↑ | Avg NLL↓ / AUC↑ |
| Qwen3.5-9B | ||||||||
| C0 | .5040/.4290 | .6692/.4855 | .5838/.4506 | .6481/.4732 | .2746/.4499 | .6224/.4748 | .6904/.4791 | .5703/.4631 |
| Self probability | .4999/.5228 | .6760/.4662 | .5683/.6240 | .6497/.4551 | .2693/.4896 | .6036/.6146 | .7034/.4347 | .5672/.5153 |
| ADeLe | .5592/.7034 | .7044/.6295 | .4895/.7641 | .5944/.6918 | .2657/.6238 | .5947/.7087 | .6158/.7243 | .5462/.6922 |
| PredictaBoard | .4517/.7093 | .6693/.4855 | .5198/.7021 | .5952/.6931 | .2701/.5956 | .6322/.5128 | .6868/.5585 | .5464/.6081 |
| Already Knows | .5823/.5167 | .6796/.4975 | .6381/.5059 | .6262/.7040 | .4417/.5192 | .6276/.5458 | .6922/.4879 | .6125/.5396 |
| CIRCE-Stats | .4141/.7727 | .6577/.6144 | .4609/.8016 | .5735/.7245 | .2476/.6914 | .5580/.7169 | .6299/.6799 | .5060/.7145 |
| CIRCE-GNN-R | .4265/.7539 | .6482/.6332 | .4569/.8064 | .5657/.7384 | .2518/.7013 | .5644/.7111 | .5670/.7745 | .4972/.7313 |
| CIRCE-GNN-P | .4289/.7521 | .6520/.6278 | .4544/.8085 | .5630/.7415 | .2530/.6962 | .5566/.7199 | .5634/.7779 | .4959/.7320 |
| Qwen3.8-27B | ||||||||
| C0 | .1621/.3446 | .6360/.4766 | .3581/.3927 | .3823/.4637 | .1995/.4291 | .6879/.4794 | .5828/.4756 | .4298/.4374 |
| Self probability | .1671/.4923 | .6228/.6054 | .2442/.8802 | .3085/.8098 | .1934/.6412 | .6941/.5023 | .5606/.5738 | .3987/.6436 |
| ADeLe | .2151/.6193 | .8534/.6056 | .2700/.8508 | .3080/.8037 | .2000/.6670 | .7568/.7171 | .4618/.7786 | .4379/.7203 |
| PredictaBoard | .1661/.4677 | .6557/.4873 | .2761/.8344 | .3239/.8096 | .1940/.6384 | .6680/.6004 | .5739/.5625 | .4082/.6286 |
| Already Knows | – | – | – | – | – | – | – | – |
| CIRCE-Stats | .1619/.5685 | .6320/.6088 | .2389/.8822 | .2956/.8355 | .1810/.7422 | .6125/.7174 | .5052/.7387 | .3753/.7276 |
| CIRCE-GNN-R | .1605/.5974 | .6359/.6064 | .2521/.8682 | .2918/.8405 | .1847/.7195 | .5971/.7371 | .4295/.8268 | .3645/.7423 |
| CIRCE-GNN-P | .1606/.6018 | .6221/.6295 | .2495/.8725 | .2909/.8402 | .1826/.7339 | .6022/.7330 | .4297/.8241 | .3625/.7479 |
| Inkling | ||||||||
| C0 | .0864/.3069 | .6548/.4751 | .2411/.4144 | .2020/.4518 | .6934/.4815 | .6226/.4813 | .5609/.4839 | .4373/.4421 |
| Self probability | .0880/.4178 | .6539/.5558 | .2124/.8111 | .1946/.6102 | .6982/.4953 | .5709/.6952 | .5463/.6965 | .4235/.6117 |
| ADeLe | .1588/.4653 | .6995/.6341 | .2185/.7654 | .1783/.7848 | .7023/.6048 | .6807/.6625 | .4967/.7661 | .4478/.6690 |
| PredictaBoard | .0874/.3421 | .6604/.4750 | .2100/.7563 | .1796/.8181 | .6879/.5689 | .6227/.4813 | .5625/.4712 | .4301/.5590 |
| Already Knows | – | – | – | – | – | – | – | – |
| CIRCE-Stats | .0891/.3894 | .6551/.5961 | .1909/.8248 | .1575/.8455 | .6452/.6626 | .5437/.7419 | .5338/.6550 | .4022/.6736 |
| CIRCE-GNN-R | .0862/.5562 | .6455/.6196 | .1931/.8403 | .1589/.8467 | .6531/.6583 | .5358/.7520 | .4677/.7710 | .3915/.7206 |
| CIRCE-GNN-P | .0856/.5869 | .6308/.6439 | .1948/.8309 | .1591/.8471 | .6543/.6579 | .5492/.7334 | .4713/.7653 | .3922/.7236 |
| GPT-6 Luna | ||||||||
| C0 | .2744/.4203 | .6369/.4822 | .3388/.4138 | .1701/.4417 | .6622/.4808 | .6320/.4836 | .6838/.4733 | .4855/.4565 |
| Self probability | .2758/.4985 | .6256/.5774 | .2969/.7180 | .1562/.7198 | .6592/.5598 | .6309/.5895 | .6849/.4817 | .4756/.5921 |
| ADeLe | .2802/.6175 | .8300/.5765 | .3039/.7410 | .1566/.7495 | .5618/.7604 | .6785/.7234 | .7146/.6085 | .5036/.6824 |
| PredictaBoard | .2651/.6460 | .6703/.5005 | .3132/.7009 | .1614/.7230 | .5945/.7366 | .6458/.5420 | .6717/.5820 | .4746/.6330 |
| Already Knows | – | – | – | – | – | – | – | – |
| CIRCE-Stats | .2588/.6396 | .6140/.6418 | .3008/.7249 | .1550/.7393 | .5394/.7782 | .5528/.7411 | .6652/.6054 | .4409/.6958 |
| CIRCE-GNN-R | .2545/.6801 | .6380/.6044 | .3006/.7366 | .1543/.7523 | .5359/.7831 | .5499/.7418 | .6307/.6863 | .4377/.7121 |
| CIRCE-GNN-P | .2588/.6642 | .6022/.6672 | .3025/.7287 | .1557/.7368 | .5346/.7846 | .5422/.7505 | .6263/.6924 | .4318/.7178 |
caption: tbl:2: The NLL and AUROC (denoted as AUC) of all methods on four models across seven benchmarks. Each cell reports NLL/AUC. Avg is the mean across seven benchmarks. Lower NLL and higher AUC are better. The best scores within each model are marked in red and bold.
:::
observe an unstable performance of the Already Knows predictor, with its average NLL (0.6125) higher than that of C0 (0.5703) on the only model we tested, Qwen3.5-9B. We suspect that the Already Knows predictor is sensitive to the number of correctness labels: we provided only approximately 160 labels for training in each fold, compared with thousands of labels used in the original paper. The full implementation details are in Appendix § 11.
Further Analysis
Effect of Feature Count
We examine how prediction changes as more hand-crafted features are included. We use greedy forward selection, starting from an empty feature set. At each step, we evaluate every remaining feature together with the selected features and add the one yielding the lowest inner-validation NLL.
Figure 2 shows that richer feature sets generally improve prediction. Improvements continue near the full 41-feature set on several benchmarks, including FOLIO, GSM8K, and Logical. Averaged across benchmarks and models, increasing the feature count from 30 to 41 reduces NLL from 0.4325 to 0.4311 and increases AUROC from 0.7007 to 0.7029. These results suggest that capturing additional structural properties can improve complexity estimation.
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.
Qualitative Analysis
Graph representations versus statistics. The Logical benchmark shows the largest average advantage of CIRCE-GNN over CIRCE-Stats. To examine what the graph representation adds, consider two problems about the same seven golfers, L1 and L2 (Figure 3). Their six ordering clues are identical: Amy finishes last, Ana third-to-last, Eve third, and Eli above Dan above Ada above Mel. L1 asks who finishes last, and L2 asks who finishes second-to-last. Forty of their 41 Stats features match exactly, including their graph sizes and operator counts.
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.
The relevant difference is how the query connects to the stated constraints. In L1, the query’s position node is shared with the clue fixing Amy’s position. In L2, the requested position has no such fixed-position clue. Identifying its occupant requires combining the ordering chain with the occupied positions. Message passing can distinguish these query neighborhoods, whereas the present aggregate statistics largely omit their arrangement. For Qwen3.5-9B, CIRCE-GNN-P predicts 0.804 and 0.282, consistent with the observed success rates of 10/10 and 0/10. CIRCE-Stats predicts 0.366 and 0.503, reversing their ordering. This pair illustrates a structural distinction the GNN can represent.
Explicit constraints versus external assessors. A GSM8K problem asks the cost of 850 kilograms of coal, delivered in 50-kilogram bags costing 18 dollars each. The CIR exposes the relations , and , where is the total weight, the number of bags and the requested cost. Its graph is a short, acyclic dependency chain: each quantity depends on one preceding quantity, without branching alternatives or additional interacting conditions. These properties provide a concrete description of the required reasoning independent of the story’s wording. CIRCE-Stats summarizes such graph properties, while CIRCE-GNN learns from the connected sequence of constraint types.
In comparison, ADeLe represents the problem through broad reasoning-demand scores, PredictaBoard uses a text embedding, and Already Knows uses the target model’s initial hidden state. These inputs do not explicitly supply the extracted dependency chain: relations must be summarized by the demand scores or recovered implicitly from the learned representations. For Qwen3.5-9B, both CIRCE variants give this question higher probabilities than the external assessors: 0.667 for Stats and 0.737 for pretrained GNN, versus 0.253–0.419 for the three external baselines, where the target model answers all ten attempts correctly. This example illustrates a case where the explicit constraint structure is a more informative representation than the external assessors’ features.
Reliability of CIR
We measure two metrics to assess the reliability of the CIRs: parsability and correctness. Parsability measures whether the CIR has a valid syntax, and correctness measures whether the CIR correctly represents the constraint structure of the problem. For SATBench, Logical, and Hamiltonian, a rule-based checker can verify the constraint structure, so we check both parsability and correctness on all 200 problems. For FOLIO, NLCO, Zebra, and GSM8K, rule-based checker only covers part of the constraint structure, so we check parsability on all 200 problems and manually review the correctness of 20 randomly sampled source–CIR pairs per benchmark. On the three benchmarks with a full checker, we also check the parsability and correctness of direct graph generation, where the LLM is prompted to generate the graph directly from the natural-language question.
As shown in Table 3, the CIR method has higher parsability and correctness than the direct graph generation method on the three benchmarks with an available correctness checker, especially on the Hamiltonian benchmark, where the correctness of the direct graph generation method is only 68.0%,
| Method | Parsable | Correct |
| SATBench | ||
| CIR | 198/200 = 99.0% | 194/200 = 97.0% |
| Direct graph | 197/200 = 98.5% | 192/200 = 96.0% |
| Logical | ||
| CIR | 200/200 = 100.0% | 194/200 = 97.0% |
| Direct graph | 200/200 = 100.0% | 185/200 = 92.5% |
| Hamiltonian | ||
| CIR | 200/200 = 100.0% | 185/200 = 92.5% |
| Direct graph | 196/200 = 98.0% | 136/200 = 68.0% |
Table 3. Parsability and correctness of the CIR and direct graph generation methods on three benchmarks, with 200 questions per benchmark. The numbers are before LLM repairs.
while the correctness of the CIR method is 92.5%. Furthermore, as shown in Table 3 and Table 4, the CIR method achieves at least 90% correctness on all seven benchmarks, supporting that the LLM-generated CIR reliably represents the constraint structure of the problem.
| Benchmark | Parsable | Correct |
| FOLIO | 200/200 = 100.0% | 18/20 = 90.0% |
| NLCO | 200/200 = 100.0% | 20/20 = 100.0% |
| Zebra | 200/200 = 100.0% | 20/20 = 100.0% |
| GSM8K | 200/200 = 100.0% | 20/20 = 100.0% |
Table 4. Parsability and correctness of the CIR on four benchmarks. Parsability is checked on 200 questions per benchmark before LLM repairs, while correctness is human-reviewed on a random sample of 20 questions per benchmark after repairs.
Rule-based checkers can trigger CIR repair or regeneration, while human review only assesses correctness and does not trigger repairs. Details about processing the CIRs are described in Appendix § 9.
Comparison of Predictors
We examine whether the advantage of graph embeddings depends on the downstream predictor. Keeping the input representations and outer evaluation folds fixed, we compare gradient-boosted trees (GB), logistic regression (LR), and a multilayer perceptron (MLP).
Table 5 shows that both GNN variants achieve lower average NLL and higher average AUROC than CIRCE-Stats with all three predictors. The advantage of graph embeddings therefore persists across linear, tree-based, and neural predictors. The pretrained variant also has slightly higher AUROC and lower NLL than the random one across the three predictors. Compared with LR and MLP, GB achieves the highest average AUROC for each representation, whereas LR and MLP yield slightly lower NLL for the GNN variants.
| Predictor | CIRCE-Stats | CIRCE-GNN-R | CIRCE-GNN-P |
| GB | .4311 / .7029 | .4227 / .7266 | .4206 / .7303 |
| LR | .4339 / .7024 | .4209 / .7172 | .4198 / .7200 |
| MLP | .4341 / .6947 | .4206 / .7158 | .4194 / .7211 |
Table 5. Effect of the downstream predictor. Each cell reports NLL ↓ / AUROC ↑, averaged equally across seven benchmarks and four target models.
Conclusion
CIRCE demonstrates that constraint structure recovered from problem text is a useful signal for predicting LLM task complexity before generation. Strong results from handcrafted statistics and randomly initialized GNNs show that this signal can be used without encoder pretraining. Graph encodings improve over statistics on average, with pretraining providing further small gains. These findings support separating task representation from model-specific prediction: a shared constraint graph can serve different target models through lightweight predictors trained on black-box labels. Extending this representation to richer constraints and queries is a promising direction for future work.
Limitations
While CIRCE applies to a wide range of reasoning benchmarks, its scope is limited to the problems whose constraints are part of the input. It does not cover the problems where inferring constraints is part of the reasoning process. CIRCE also estimates only the part of problem complexity that constraint structure reflects, while other methods that depend on the model’s states could potentially reveal the failure cases such as a misread question. Combining our method with their features remains future work.
We showed the reliability of the CIRs, but they are generated by a single LLM, and their correctness cannot be fully verified: rule-based checkers cover three benchmarks, and the other four were spot-checked on 20 questions each. We also used a fixed set of problems for pretraining the GNN encoder and evaluating the predictors. Evaluating how the number of problems affects the encoder and predictor performance would further establish the scalability of our method. Exploring predictor transfer across benchmarks and models could provide further evidence of the generalizability of our method.
Acknowledgments
This work used Jetstream2 (Hancock et al., [13]) at Indiana University through allocation TRA120004 from the Advanced Cyberinfrastructure Coordination Ecosystem: Services & Support (ACCESS) program (Boerner et al., [2]), which is supported by National Science Foundation grants #2138259, #2138286, #2138307, #2137603, and #2138296.
This research also received DAPLab corporate support in the form of funding and/or compute from Amazon, IntellectAI, Infosys, Tidalwave, Veris, Shopify, Microsoft, Thinking Machines, Dandy, Perplexity, and Daytona. The views and conclusions presented here are those of the authors and should not be interpreted as representing the official positions of the funding organizations.
Data and Evaluation Protocol
The evaluation contains 200 problems per benchmark, four target models, and ten responses per problem (56,000 responses). The 5,200 question-disjoint Pretraining (SSL) instances comprise 4,684 training and 516 validation graphs.
| Benchmark | SSL train | SSL val. | Groups | Fold train |
| SATBench | 810 | 90 | 27 | 154–165 |
| FOLIO | 810 | 90 | 152 | 158–161 |
| NLCO | 364 | 36 | 200 | 160 |
| Hamiltonian | 810 | 90 | 200 | 160 |
| Zebra | 810 | 90 | 200 | 160 |
| GSM8K | 810 | 90 | 200 | 160 |
| Logical | 270 | 30 | 200 | 160 |
Table 6. SSL split sizes, downstream groups and outer-training-fold sizes. Each benchmark has 200 evaluation questions.
Subsets. We use FOLIO v2; NLCO’s KP, QKP, MIS, and MVC tasks; Enigmata’s Hamiltonian Path and Zebra Logic; and BBH’s five- and seven-object Logical Deduction subsets [37].
Grouped Cross-Validation
We use five outer and three inner folds, with split seeds 11, 23, and 37. SATBench groups by dimension saturation configuration; FOLIO groups by story; other benchmarks group by instance (Table 6). All attempts for a question stay together. Methods share frozen folds within each benchmark/model pair. Preprocessing and hyperparameter selection use training folds only.
Metrics. Let be correct attempts out of ten and the out-of-fold prediction. NLL is Bernoulli cross-entropy against , using natural logarithms and clipping probabilities to . Attempt-weighted AUROC is
where is 1 for , for ties and 0 otherwise. This corresponds to ten binary outcomes per question sharing one probability.
Metrics are computed on all 200 out-of-fold predictions, then averaged over three split seeds and
Target sampling. Qwen3.5-9B has thinking disabled throughout. For Qwen3.8-27B and Inkling, SATBench/FOLIO/NLCO use default reasoning, Hamiltonian/Zebra use Low, and GSM8K/Logical use Off. Luna uses Medium, Low, and None for these respective groups.
Qwen and Inkling use temperature 0.7 and top- 0.95 for the five longer-format benchmarks under the 64K effective-context protocol. GSM8K and Logical use temperature 0.7, top-p 0.8 and output caps of 128 and 2,048. Luna leaves temperature and top-p unset in Medium/Low mode; None mode uses 0.7/1.0. Its output cap is unset. Responses are scored using final labels, choices, numerical answers or instance-specific feasibility/objective checks.
| Benchmark | 9B | 27B | Inkling | Luna |
| SATBench | 80.00 | 96.30 | 98.35 | 92.25 |
| FOLIO | 60.95 | 66.80 | 63.85 | 66.65 |
| NLCO | 73.15 | 88.65 | 93.55 | 89.50 |
| Hamiltonian | 65.00 | 87.25 | 94.90 | 95.95 |
| Zebra | 92.20 | 95.00 | 49.10 | 37.55 |
| GSM8K | 31.35 | 44.70 | 68.60 | 67.35 |
| Logical | 54.00 | 73.10 | 75.15 | 57.10 |
| Avg | 65.24 | 78.83 | 77.64 | 72.34 |
Table 7. Target response accuracy (percent) over ten attempts per question. Qwen3.5-9B has thinking disabled.
four encoder seeds for GNNs. Overall averages weight the 28 benchmark/model pairs equally; Already Knows covers seven Qwen3.5-9B pairs. C0 predicts the training-fold mean.
Feature selection. Stats forward selection adds the remaining feature yielding the lowest inner-validation NLL, jointly selecting tree settings within each outer training fold.
CIR Extraction, Compilation and Validation
Extraction and repair. We use Qwen/Qwen3.8-27B to extract entities, variables, constraints, and a query. Prompts and input formats vary by benchmark. Parsing, reference checks, and task-specific source checks identify repair candidates. Repair inputs contain the question, candidate CIR, and diagnostic. The general format-repair prompt permits one LLM retry.
The main results use 1,400 evaluation graphs and 5,200 SSL graphs after recorded processing, fixed before predictor cross-validation. Table 8 counts adopted LLM repairs. All retained graphs compile.
| Benchmark | Questions | Format repairs | Content repairs |
| Evaluation data | |||
| SATBench | 200 | 1 | 0 |
| FOLIO | 200 | 0 | 0 |
| NLCO | 200 | 0 | 0 |
| Hamiltonian | 200 | 0 | 15 |
| Zebra | 200 | 0 | 1 |
| GSM8K | 200 | 0 | 0 |
| Logical | 200 | 1 | 6 |
| Pretraining (SSL) data | |||
| SATBench | 900 | 1 | 7 |
| FOLIO | 900 | 0 | 11 |
| NLCO | 400 | 0 | 4 |
| Hamiltonian | 900 | 0 | 101 |
| Zebra | 900 | 0 | 11 |
| GSM8K | 900 | 0 | 1 |
| Logical | 300 | 6 | 11 |
Table 8. Numbers of questions with recorded format repair, content repair based on the visible question. Format and content counts can overlap.
Compilation. Factors represent constraints and the query. Non-factor nodes represent variables, propositions, entities, and shared domain values. Each occurrence creates a connection carrying role and Boolean polarity, with messages in both directions.
Validation Protocol
The reliability tables assess the correctness outputs on the three benchmarks before subsequent LLM repairs, while human-review of FOLIO, NLCO, Zebra, and GSM8K already include those repairs.
Rule checks. SATBench compares Boolean clauses, identities, and polarity with visible conditions. Logical checks variables, ordering clues, and query candidates. Hamiltonian checks vertex coverage, distinctness, and allowable transitions. These checks derive references from the visible problem description, without gold answers or target outcomes. The other four benchmarks have partial rule checks.
Human review. Independent human reviewers check 20 source–CIR pairs per remaining benchmark. A question passes if variables, domains, constraints, and query are preserved without unstated conditions or an answer. Review measures reliability and does not trigger repairs.
CIR Example
The coal question in the qualitative analysis (gsm8k_direct:formal:1184) produces the following CIR.
{
"cir_version": "1",
"constraints": [
{
"expr": {
"left": {
"id": "total_kg",
"op": "var"
},
"op": "eq",
"right": {
"op": "const",
"value": 850
}
},
"id": "total_kg_fact"
},
{
"expr": {
"left": {
"op": "linear_sum",
"terms": [
{
"coef": 50,
"var": "bags"
}
]
},
"op": "eq",
"right": {
"id": "total_kg",
"op": "var"
}
},
"id": "bag_weight_relation"
},
{
"expr": {
"left": {
"op": "linear_sum",
"terms": [
{
"coef": 18,
"var": "bags"
}
]
},
"op": "eq",
"right": {
"id": "cost",
"op": "var"
}
},
"id": "cost_relation"
}
],
"entities": [],
"query": {
"expr": {
"id": "cost",
"op": "var"
},
"sense": "minimize",
"type": "optimization"
},
"variables": [
{
"domain": "nonnegative",
"id": "total_kg",
"meaning": "total kilograms of coal ordered",
"type": "numeric"
},
{
"domain": "nonnegative integer",
"id": "bags",
"meaning": "number of 50 kg bags in the order",
"type": "numeric"
},
{
"domain": "nonnegative",
"id": "cost",
"meaning": "total cost of the order in dollars",
"type": "numeric"
}
]
}
Features and Training Details
Feature definitions. Size includes auxiliary factors; constraint nodes are non-query factors. Factor counts repeated occurrences, whereas Degree counts distinct neighbors. Summaries use mean, maximum, 90th percentile, and population SD/mean (zero when the mean is zero). Density is ; 2-core and largest biconnected-component fractions divide by .
| Family | Features | Count |
| Size | Counts of all nodes, variable nodes, factor nodes, non-query factor nodes, and edges | 5 |
| Factor | Occurrences of variables, propositions, or entities in each factor* | 4 |
| Degree | Degrees of variable nodes* (4) and factor nodes* (4) | 8 |
| Topology | Connected components; density; 2-core fraction; largest biconnected-component fraction; cycle rank | 5 |
| Query | Query degree; fraction of reachable constraints; mean distance to reachable constraints | 3 |
| CIR operators | Occurrence counts of ¬, ∧, ∨, ⇒, ∀, ∃, =, ≠, <, ≤, >, ≥, linear sum, predicate, variable, and constant | 16 |
| Total | 41 |
Table 9. CIRCE-Stats features, grouped by family. Variable nodes denote all non-factor nodes.
*We compute mean, maximum, 90th percentile and coefficient of variation for these quantities.
cycle rank is for components. We compute topology with NetworkX [11].
Query features use the first query factor’s degree, reachable non-query factor fraction, and mean distance, with missing values when undefined. Operator features recursively count occurrences, including query expressions.
Encoder and Pretraining
Kind, subtype and factor-type embeddings have dimensions 8, 8 and 4, with 5, 64 and 4 categories. Node subtypes record variable or entity types and predicate argument counts. The 20 embedding coordinates and 16 log-transformed operator counts are projected from 36 to 64 dimensions with ReLU and layer normalization.
Each of the six layers has role/polarity embeddings of size , a learned scalar , a 64–128–64 MLP, ReLU, dropout 0.1, and residual layer normalization. Readout concatenates sum, mean, query sum, and population SD into 256 dimensions, using variance stabilizer .
Node/edge masking probabilities are 0.4/0.2. Learned vectors replace masked attributes; reverse edges share a mask and connectivity is retained. One mask is forced when a nonempty set receives none. Six equally weighted losses reconstruct kind, subtype, factor type, operator counts, edge role, and polarity. Subtype applies to non-factors, factor type/operators to factors, and edge losses to one orientation per masked pair. Empty losses are zero. Linear decoders use 64D node states or 128D endpoint concatenations.
We use AdamW, learning rate 0.001, weight decay 0.001, batch size 32, gradient-norm clipping 5, and fixed 100 epochs. Each epoch samples 4,684 graphs with equal source weight; validation balances 516 entries with mask seed 777001. Encoder seeds are 20260919, 20260922, 20260923, and 20260924. Evaluation freezes the encoder and disables dropout and masking.
Gradient-Boosted Predictor
We use scikit-learn’s HistGradientBoostingClassifier (Pedregosa et al. [31]), with the shared grid (maximum leaves, iterations, ):
Fixed settings are learning rate 0.05, maximum depth 3, minimum leaf size 40, early stopping disabled, and seed 713. Each question supplies binary rows 0/1 weighted by ; leaf size counts these rows.
Training-fold preprocessing performs median imputation (zero for all-missing columns), appends missingness indicators, drops constant columns, and standardizes. Inner-validation NLL selects the candidate, with grid order breaking ties; final fitting uses the outer training fold. This procedure is shared by Stats and both GNN variants.
Baseline Implementations
Baselines share CIRCE’s evaluation labels and outer folds. We retain their published predictor families, with the settings below.
C0 and self probability. C0 predicts the training-fold mean. Self probability asks the target once for a pre-answer JSON probability in [0, 1], using its answering settings (Appendix G). Training-only calibration fits a regularized logistic intercept and slope on standardized log-odds, with regularization 0.001. Missing estimates use C0: eight for Qwen3.8-27B (SATBench 1, NLCO 6, Hamiltonian 1), zero for other targets.
ADeLe. The 18 original demand rubrics are scored by GPT-6 Sol with temperature 0, top- 1, reasoning None, and output cap unset. Unguessability is for choices and 100 for open-ended tasks. A random forest uses 100 trees, entropy criterion, and minimum split size 50, with remaining defaults. Training expands each question into ten grouped binary attempt rows.
PredictaBoard. text-embedding-3-large embeds the visible question into 3,072 dimensions. Inner-validation NLL selects default L2 logistic regression, L1 logistic regression (liblinear, ) or default XGBoost (Chen and Guestrin [7]) with one CPU thread. Binary rows have weights and .
Already Knows. Qwen3.5-9B generates one thinking-off trajectory per question. Last-layer 4,096D states train a 4,096–64–1 MLP with GELU and sigmoid: AdamW, learning rate , weight decay , 40 epochs and discount 1. The next-state target is detached. Terminal reward is the trajectory’s response correctness. Squared TD errors are summed across the whole response, followed by one optimizer step. Chunks of 1,024 states bound memory; caches are FP16 and computations FP32.
TD training uses 199 complete NLCO trajectories and 200 per other benchmark. Evaluation uses the pre-generation state for all questions. Our setup uses approximately 160 training questions per fold and attempt-weighted AUROC.
Compute and Software
CIRCE pretraining and predictors run on local CPU virtual machines with 8 cores. Each pretraining worker uses two CPU threads, while tree-fitting workers use one. The reconstruction module has 127,995 parameters, comprising 117,118 encoder, 10,429 decoder, and 448 mask parameters. Qwen targets have 9B/27B parameters. Inkling has 975B total and 41B active. Hosted GPT-6 model sizes are undisclosed. Training through epoch 100
| Encoder seed | Minutes | Train loss | Val. loss |
| 20260919 | 22.39 | 0.01149 | 0.01090 |
| 20260922 | 22.27 | 0.01145 | 0.01003 |
| 20260923 | 23.18 | 0.01082 | 0.01059 |
| 20260924 | 22.50 | 0.01035 | 0.02221 |
Table 10. 100-epoch pretraining: worker wall time in minutes and final training/validation reconstruction losses. Each seed uses two CPU threads.
across four encoder seeds totals 1.51 worker wall-hours. The 336 pretrained predictor evaluations total 0.56 worker wall-hours. Across 479 recorded exploratory SSL runs, the summed worker wall time is 379.67 hours. The encoder uses PyTorch [30], graph features use NetworkX, and predictors use scikit-learn and XGBoost. Software versions for metric recomputation appear in Table 11.
| Package | Version |
| torch | 2.13.0+cu130 |
| numpy | 2.4.3 |
| scipy | 1.17.1 |
| sklearn | 1.8.0 |
| networkx | 3.6.1 |
| xgboost | 3.4.1 |
| transformers | 5.12.1 |
| safetensors | 0.8.0 |
| python | 3.13.12 |
Table 11. Software versions used for metric recomputation.
Responsible Research
Use and data. CIRCE estimates correctness under a specified model and inference protocol. Incorrect confidence can encourage over-reliance; new languages and applications require validation. We use released English reasoning benchmarks. A contact-pattern screen of 1,400 evaluation prompts found no email addresses, HTTP(S) URLs, or international phone-number matches. Names defining problem entities are retained in text and omitted from graph features.
Asset terms. Upstream licenses and sources are:
SATBench (Apache-2.0): https://huggingface.co/datasets/LLM4Code/SATBench.
FOLIO v2 (MIT dataset card): https://huggingface.co/datasets/yale-nlp/FOLIO; legacy repository: CC-BY-SA-4.0.
NLCO (MIT): https://huggingface.co/datasets/summer142857jiang/NLCO.
Enigmata (Apache-2.0): https://github.com/BytedTsinghua-SIA/Enigmata.
GSM8K (MIT): https://github.com/openai/grade-school-math.
BBH (MIT): https://github.com/suzgunmirac/BIG-Bench-Hard; BIG-Bench (Apache-2.0): https://github.com/google/BIG-bench. Task-specific notices apply.
Prompt Templates
General CIR Translation
You convert natural-language structured reasoning problems into CIR v1 JSON.
Your job is REPRESENTATION ONLY. Do not solve the problem, do not choose an answer option, do not derive the final assignment, and do not use any hidden or gold information.
CIR v1 has exactly five root fields:
cir_version: "1"entities: list of {"id": string, "type": string, "label": string}variables: unknown Boolean/numeric/assignment decisions. Each has id and type, and may have meaning/domain/bounds.constraints: list of {"id": string, "expr": EXPR}query: one of {"type":"feasibility"} {"type":"entailment","expr":EXPR} {"type":"optimization","sense":"minimize"|"maximize","expr":EXPR}
Registered expressions include:
variable/entity/constant:
{"op":"var","id":"..."}{"op":"entity","id":"..."}{"op":"const","value":...}
Boolean:
{"op":"not","arg":EXPR}{"op":"and","args":[...]}{"op":"or","args":[...]}{"op":"xor","args":[...]}{"op":"implies","left":EXPR,"right":EXPR}{"op":"iff","left":EXPR,"right":EXPR}
comparisons:
{"op":"eq"|"ne"|"le"|"lt"|"ge"|"gt","left":EXPR,"right":EXPR}
linear sums:
{"op":"linear_sum","terms":[{"coef":1,"var":"x"}, ...]}
predicates:
{"op":"predicate","name":"Relation","args":["entity_or_bound_var", ...]}
quantifiers:
{"op":"forall"|"exists","vars":[{"id":"x","type":"entity"}],"body":EXPR}
scheduling relations when explicitly appropriate: precedence, no_overlap, within_window, cumulative_resource.
Representation rules:
Use ONLY the problem text below.
Preserve all stated constraints that determine the latent reasoning world.
Do not invent unstated facts or commonsense rules unless the text explicitly states that they are task rules.
For ordering/allocation/grid/full-assignment puzzles, encode the latent decision variables and constraints and use a feasibility query. The task of finding the assignment is represented by the feasible solution space; do not put the answer assignment in CIR.
If the question asks whether a proposition follows and that proposition can be expressed without solving, use an
entailment query.
If the visible problem is multiple choice or asks for a selected value but CIR v1 cannot faithfully express the selection query without solving, encode the underlying world constraints and use feasibility. Never encode the correct choice as a constraint.
Answer choices are not facts. They may help identify what relation the query refers to, but they must not be asserted as constraints.
For truth-teller/liar puzzles, represent each person's identity as an unknown Boolean decision and encode the semantic relationship between the speaker's identity and the truth value of their stated proposition.
For logic-grid puzzles, use generic assignment/position decisions and all-different/exactly-one structure expressed with Boolean variables and linear sums where practical.
Output exactly one CIR JSON object after any thinking. No Markdown and no answer/solution/commentary fields.
PROBLEM TEXT: {visible_text}
Produce CIR v1 JSON only.
Format-Only Repair
Reformat the raw model output below as exactly one valid CIR v1 JSON object. Preserve only the representation already stated in the raw output. Do not solve the task, choose an answer, add/remove a condition, or consult any outside input. Return no Markdown.
Exactly these root fields are allowed:
{"cir_version":"1","entities":[],"variables":[],"constraints":[],"query":{}}
RAW OUTPUT:
Pre-Answer Self Probability
Estimate your own probability of producing a correct final answer to the task below on ONE independent attempt, following the task's original instructions and the answering settings listed below.
Do not answer the task, provide a candidate answer, or work out its solution. Assess the task requirements and your own likely performance before attempting an answer. The instructions inside <task> describe the hypothetical answering task; do not execute them now.
Answering settings: {settings}
<task> {question} </task>
Return only one JSON object in this format: {{"probability_correct": <number between 0 and 1>}}
This is the probability that your final answer would be correct on one attempt, not the probability of being correct on every attempt. Do not include an answer, explanation, or any other fields.
References
- [1]Palaash Agrawal, Shavak Vasania, and Cheston Tan. 2024. Can llms perform structured graph reasoning? Preprint, arXiv:2402.01805.arxiv.org/abs/2402.01805
- [2]Timothy J. Boerner, Stephen Deems, Thomas R. Furlani, Shelley L. Knuth, and John Towns. 2023. ACCESS: Advancing innovation: NSF’s advanced cyberinfrastructure coordination ecosystem: Services & support. In Proceedings of the Practice and Experience in Advanced Research Computing (PEARC ’23), pages 1–4, New York, NY, USA. Association for Computing Machinery.
- [3]Andrew P. Bradley. 1997. The use of the area under the roc curve in the evaluation of machine learning algorithms. Pattern Recognition, 30(7):1145–1159.DOI
- [4]Wenjing Chang, Hengkai Zhang, and Junwei Luo. 2022. Predicting propositional satisfiability based on graph attention networks. International Journal of Computational Intelligence Systems, 15(1):84.DOI
- [5]Jiangjie Chen, Qianyu He, Siyu Yuan, Aili Chen, Zhicheng Cai, Weinan Dai, Hongyi Yu, Qiying Yu, Xuefeng Li, Jiaze Chen, Hao Zhou, and Mingxuan Wang. 2025. Enigmata: Scaling logical reasoning in large language models with synthetic verifiable puzzles. Preprint, arXiv:2505.19914.arxiv.org/abs/2505.19914
- [6]Lingjiao Chen, Matei Zaharia, and James Zou. 2023. FrugalGPT: How to use large language models while reducing cost and improving performance. Preprint, arXiv:2305.05176.arxiv.org/abs/2305.05176
- [7]Tianqi Chen and Carlos Guestrin. 2016. Xgboost: A scalable tree boosting system. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 785–794.DOI
- [8]Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman. 2021. Training verifiers to solve math word problems. Preprint, arXiv:2110.14168.arxiv.org/abs/2110.14168
- [9]Xinnan Dai, Qihao Wen, Yifei Shen, Hongzhi Wen, Dongsheng Li, Jiliang Tang, and Caihua Shan. 2025. Revisiting the graph reasoning ability of large language models: Case studies in translation, connectivity and shortest path. Preprint, arXiv:2408.09529.arxiv.org/abs/2408.09529
- [11]Aric A. Hagberg, Daniel A. Schult, and Pieter J. Swart. 2008. Exploring network structure, dynamics, and function using networkx. In Proceedings of the 7th Python in Science Conference, pages 11–15.
- [12]Simeng Han, Hailey Schoelkopf, Yilun Zhao, Zhenting Qi, Martin Riddell, Wenfei Zhou, James Coady, David Peng, Yujie Qiao, Luke Benson, Lucy Sun, Alexander Wardle-Solano, Hannah Szabó, Ekaterina Zubova, Matthew Burtell, Jonathan Fan, Yixin Liu, Brian Wong, Malcolm Sailor, and 16 others. 2024. FOLIO: Natural language reasoning with first-order logic. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, pages 22017–22031, Miami, Florida, USA. Association for Computational Linguistics.arxiv.org/abs/2209.00840
- [13]David Y. Hancock, Jeremy Fischer, John Michael Lowe, Winona Snapp-Childs, Marlon Pierce, Suresh Marru, J. Eric Coulter, Matthew Vaughn, Brian Beck, Nirav Merchant, Edwin Skidmore, and Gwen Jacobs. 2021. Jetstream2: Accelerating cloud computing via jetstream. In Proceedings of the Practice and Experience in Advanced Research Computing (PEARC ’21), pages 1–8, New York, NY, USA. Association for Computing Machinery.DOI
- [15]Zhenyu Hou, Yufei He, Yukuo Cen, Xiao Liu, Yuxiao Dong, Evgeny Kharlamov, and Jie Tang. 2023. Graphmae2: A decoding-enhanced masked self-supervised graph learner. Preprint, arXiv:2304.04779.arxiv.org/abs/2304.04779
- [16]Zhenyu Hou, Xiao Liu, Yukuo Cen, Yuxiao Dong, Hongxia Yang, Chunjie Wang, and Jie Tang. 2022. Graphmae: Self-supervised masked graph autoencoders. Preprint, arXiv:2205.10803.arxiv.org/abs/2205.10803
- [17]Xia Jiang, Jing Chen, Cong Zhang, Jie Gao, Chengpeng Hu, Chenhao Zhang, Yaoxin Wu, and Yingqian Zhang. 2026. Reasoning in a combinatorial and constrained world: Benchmarking LLMs on natural-language combinatorial optimization. In Findings of the Association for Computational Linguistics: ACL 2026, pages 30592–30648, San Diego, California, United States. Association for Computational Linguistics.
- [18]Amita Kamath, Robin Jia, and Percy Liang. 2020. Selective question answering under domain shift. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 5684–5696, Online. Association for Computational Linguistics.arxiv.org/abs/2006.09462
- [19]Liwei Kang, Zirui Zhao, David Hsu, and Wee Sun Lee. 2024. On the empirical complexity of reasoning and planning in LLMs. In Findings of the Association for Computational Linguistics: EMNLP 2024, pages 2897–2936, Miami, Florida, USA. Association for Computational Linguistics.
- [20]Thomas N. Kipf and Max Welling. 2017. Semi-supervised classification with graph convolutional networks. Preprint, arXiv:1609.02907.arxiv.org/abs/1609.02907
- [21]Thanh Le-Cong, Bach Le, and Toby Murray. 2025. Can llms reason about program semantics? a comprehensive evaluation of llms on formal specification inference. Preprint, arXiv:2503.04779.
- [22]Jiayu Liu, Cheng Qian, Zhenhailong Wang, Bingxuan Li, Jiateng Liu, Qing Zong, Heng Wang, Jeonghwan Kim, Yumeng Wang, Bingxiang He, Xiusi Chen, Yi R. Fung, and Heng Ji. 2026. Adaplanbench: Evaluating adaptive planning in large language model agents under world and user constraints. Preprint, arXiv:2606.05622.arxiv.org/abs/2606.05622
- [23]David G. Mitchell, Bart Selman, and Hector J. Levesque. 1992. Hard and easy distributions of SAT problems. In Proceedings of the Tenth National Conference on Artificial Intelligence, pages 459–465. AAAI Press.
- [24]Jamshid Mozafari, Bhawna Piryani, and Adam Jatowt. 2026. Question difficulty estimation for large language models via answer plausibility scoring. In Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 11124–11151, San Diego, California, United States. Association for Computational Linguistics.
- [25]Theo Olausson, Alex Gu, Ben Lipkin, Cedegao Zhang, Armando Solar-Lezama, Joshua Tenenbaum, and Roger Levy. 2023. LINC: A neurosymbolic approach for logical reasoning by combining language models with first-order logic provers. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pages 5153–5176, Singapore. Association for Computational Linguistics.
- [26]Isaac Ong, Amjad Almahairi, Vincent Wu, Wei-Lin Chiang, Tianhao Wu, Joseph E. Gonzalez, M. Waleed Kadous, and Ion Stoica. 2025. Routellm: Learning to route llms with preference data. Preprint, arXiv:2406.18665.arxiv.org/abs/2406.18665
- [27]OpenAI. 2026. GPT-6 Luna model documentation. Accessed October 4, 2026.
- [28]Lorenzo Pacchiardi, Konstantinos Voudouris, Ben Slater, Fernando Martínez-Plumed, Jose Hernandez-Orallo, Lexin Zhou, and Wout Schellaert. 2025. PredictabBoard: Benchmarking LLM score predictability. In Findings of the Association for Computational Linguistics: ACL 2025, pages 15245–15266, Vienna, Austria. Association for Computational Linguistics.
- [29]Liangming Pan, Alon Albalak, Xinyi Wang, and William Yang Wang. 2023. Logic-LM: Empowering language model reasoning with symbolic solvers for faithful logical reasoning. In Findings of the Association for Computational Linguistics: EMNLP 2023, pages 3806–3824, Singapore. Association for Computational Linguistics.arxiv.org/abs/2305.12295
- [30]Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, et al. 2019. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems, volume 32.arxiv.org/abs/1912.01703
- [31]Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, et al. 2011. Scikit-learn: Machine learning in python. Journal of Machine Learning Research, 12:2825–2830.arxiv.org/abs/1201.0490
- [32]Xin Quan, Marco Valentino, Louise A. Dennis, and André Freitas. 2025. Faithful and robust llm-driven theorem proving for nli explanations. Preprint, arXiv:2505.24264.arxiv.org/abs/2505.24264
- [33]Qwen Team. 2026a. Qwen3.5-9B model card. Hugging Face. Accessed October 4, 2026.
- [34]Qwen Team. 2026b. Qwen3.8-27B model card. Hugging Face. Accessed October 4, 2026.
- [35]Wout Schellaert, Fernando Martínez-Plumed, and José Hernández-Orallo. 2025. Analysing the predictability of language model performance. ACM Trans. Intell. Syst. Technol., 16(2).DOI
- [36]Charlie Snell, Jaehoon Lee, Kelvin Xu, and Aviral Kumar. 2024. Scaling llm test-time compute optimally can be more effective than scaling model parameters. Preprint, arXiv:2408.03314.arxiv.org/abs/2408.03314
- [37]Aarohi Srivastava, Abhinav Rastogi, Abhishek Rao, Abu Awal Md Shoeb, Abubakar Abid, Adam Fisch, Adam Brown, Adam Santoro, Aditya Gupta, et al. 2023. Beyond the imitation game: Quantifying and extrapolating the capabilities of language models. Transactions on Machine Learning Research.
- [38]Mirac Suzgun, Nathan Scales, Nathanael Schärli, Sebastian Gehrmann, Yi Tay, Hyung Won Chung, Aakanksha Chowdhery, Quoc Le, Ed Chi, Denny Zhou, and Jason Wei. 2023. Challenging BIG-bench tasks and whether chain-of-thought can solve them. In Findings of the Association for Computational Linguistics: ACL 2023, pages 13003–13051, Toronto, Canada. Association for Computational Linguistics.arxiv.org/abs/2210.09261
- [39]Thinking Machines Lab. 2026. Inkling model card. Accessed October 4, 2026.
- [40]Katherine Tian, Eric Mitchell, Allan Zhou, Archit Sharma, Rafael Rafailov, Huaxiu Yao, Chelsea Finn, and Christopher Manning. 2023. Just ask for calibration: Strategies for eliciting calibrated confidence scores from language models fine-tuned with human feedback. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pages 5433–5442, Singapore. Association for Computational Linguistics.
- [41]Sang T. Truong, Yuheng Tu, Percy Liang, Bo Li, and Sanmi Koyejо. 2025. Reliable and efficient amortized model-based evaluation. In Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pages 60238–60265. PMLR.
- [42]Anjiang Wei, Yuheng Wu, Yingjia Wan, Tarun Suresh, Huanmi Tan, Zhanke Zhou, Sanmi Koyejo, Ke Wang, and Alex Aiken. 2025. SATBench: Benchmarking LLMs’ logical reasoning via automated puzzle generation from SAT formulas. In Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing, pages 33832–33849, Suzhou, China. Association for Computational Linguistics.
- [43]Bosi Wen, Pei Ke, Xiaotao Gu, Lindong Wu, Hao Huang, Jinfeng Zhou, Wenchang Li, Binhin Hu, Wendy Gao, Jiaxin Xu, Yiming Liu, Jie Tang, Hongning Wang, and Minlie Huang. 2024. Benchmarking complex instruction-following with multiple constraints composition. In Advances in Neural Information Processing Systems.arxiv.org/abs/2407.03978
- [44]Yuxi Xia, Pedro Henrique Luz De Araujo, Klim Zaporjets, and Benjamin Roth. 2025. Influences on LLM calibration: A study of response agreement, loss functions, and prompt styles. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 3740–3761, Vienna, Austria. Association for Computational Linguistics.
- [45]Hanqi Xiao, Vaidehi Patil, Hyunji Lee, Elias Stengel-Eskin, and Mohit Bansal. 2026. Generalized correctness models: Learning calibrated and cross-model correctness predictors from historical patterns. In Proceedings of the 43rd International Conference on Machine Learning, volume 306 of Proceedings of Machine Learning Research, pages 138884–138908. PMLR.arxiv.org/abs/2509.24988
- [46]Chen Xie, Xiaodong Gu, Yuling Shi, and Beijun Shen. 2026. Rethinking code complexity through the lens of large language models. Preprint, arXiv:2602.07882.arxiv.org/abs/2602.07882
- [47]Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2019. How powerful are graph neural networks? Preprint, arXiv:1810.00826.arxiv.org/abs/1810.00826
- [48]Lin Xu, Frank Hutter, Holger H. Hoos, and Kevin Leyton-Brown. 2008. Satzilla: Portfolio-based algorithm selection for sat. Journal of Artificial Intelligence Research, 32:565–606.DOI
- [49]Mayi Xu, Yongqi Li, Ke Sun, and Tieyun Qian. 2024. Adaptation-of-thought: Learning question difficulty improves large language models for reasoning. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, pages 5468–5495, Miami, Florida, USA. Association for Computational Linguistics.DOI
- [50]Michihiro Yasunaga, Hongyu Ren, Antoine Bosselut, Percy Liang, and Jure Leskovec. 2021. QA-GNN: Reasoning with language models and knowledge graphs for question answering. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 535–546, Online. Association for Computational Linguistics.
- [51]Lexin Zhou, Lorenzo Pacchiardi, Fernando Martínez-Plumed, Katherine M Collins, Yael Moros-Daval, Seraphina Zhang, Qinlin Zhao, Yitian Huang, Luning Sun, Jonathan E Prunty, et al. 2026. General scales unlock ai evaluation with explanatory and predictive power. Nature, 652(8108):58–67.
- [52]Tianle Zhou, Jiakai Xu, Guanלהong Liu, Jiaxiang Liu, Haonan Wang, and Eugene Wu. 2025. An approach for systematic decomposition of complex llm tasks. arXiv preprint arXiv:2510.07772.arxiv.org/abs/2510.07772
- [53]Yubo Zhu, Dongrui Liu, Zecheng Lin, Wei Tong, Sheng Zhong, and Jing Shao. 2025. The LLM already knows: Estimating LLM-perceived question difficulty via hidden representations. In Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing, pages 160–1176, Suzhou, China. Association for Computational Linguistics.arxiv.org/abs/2509.12886


