CIRCE Divines LLM Task Complexity from Constraint Structure

# CIRCE Divines LLM Task Complexity from Constraint Structure
Source: [https://arxiv.org/html/2610.41089](https://arxiv.org/html/2610.41089)
###### 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,111Code will be released at[https://github\.com/hchenhao/CIRCE](https://github.com/hchenhao/CIRCE)\.which extracts a problem’s structure by using a cheap LLM to construct aConstraint Intermediate Representationthat 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\.

## 1Introduction

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\([Chen et al\., 2023](https://arxiv.org/html/2610.41089#bib.bib3);[Ong et al\., 2025](https://arxiv.org/html/2610.41089#bib.bib4)\), allocation of test\-time compute\([Snell et al\., 2024](https://arxiv.org/html/2610.41089#bib.bib5)\), and abstention on likely failures\([Kamath et al\., 2020](https://arxiv.org/html/2610.41089#bib.bib6)\)\.

Existing approaches use text embeddings of the problem\([Pacchiardi et al\., 2025](https://arxiv.org/html/2610.41089#bib.bib36)\), LLM\-generated ratings of required abilities such as logical reasoning and domain knowledge\([Zhou et al\., 2026](https://arxiv.org/html/2610.41089#bib.bib37)\), or the target model’s internal activations\([Zhu et al\., 2025](https://arxiv.org/html/2610.41089#bib.bib38)\)\. 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\([Mitchell et al\., 1992](https://arxiv.org/html/2610.41089#bib.bib7)\), and SATzilla uses structural features to predict runtimes and select the solver expected to be fastest\([Xu et al\., 2008](https://arxiv.org/html/2610.41089#bib.bib21)\)\. Constraint structure also guides LLM task decomposition\([Zhou et al\., 2025](https://arxiv.org/html/2610.41089#bib.bib22)\)\.

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](https://arxiv.org/html/2610.41089#S5.T3)\)\. Our key observation is that an LLM need onlydescribethe variables, constraints, and query in an intermediate representation, which a deterministic compiler converts into a graph\.

We introduceConstraint Intermediate Representation 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\.

## 2Related Work

### 2\.1Complexity Estimation for LLMs

Recent work predicts instance\-level LLM performance using textual assessors[Pacchiardi et al\. \(2025\)](https://arxiv.org/html/2610.41089#bib.bib36);[Schellaert et al\. \(2025\)](https://arxiv.org/html/2610.41089#bib.bib28), semantic task\-demand annotations[Zhou et al\. \(2026\)](https://arxiv.org/html/2610.41089#bib.bib37), or the target model’s hidden representations[Zhu et al\. \(2025\)](https://arxiv.org/html/2610.41089#bib.bib38)\. Complementary work estimates difficulty from problem content or answer plausibility[Truong et al\. \(2025\)](https://arxiv.org/html/2610.41089#bib.bib12);[Mozafari et al\. \(2026\)](https://arxiv.org/html/2610.41089#bib.bib13), or uses difficulty estimates to adapt reasoning strategies[Xu et al\. \(2024\)](https://arxiv.org/html/2610.41089#bib.bib8)\. A related line of work estimates response correctness using elicited confidence, inter\-model response agreement, or historical correctness patterns[Tian et al\. \(2023\)](https://arxiv.org/html/2610.41089#bib.bib10);[Xia et al\. \(2025\)](https://arxiv.org/html/2610.41089#bib.bib9);[Xiao et al\. \(2026\)](https://arxiv.org/html/2610.41089#bib.bib11)\. 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\.

### 2\.2Structured Representations for LLM Reasoning

Prior work has explored symbolic representations for LLM reasoning[Pan et al\. \(2023\)](https://arxiv.org/html/2610.41089#bib.bib14);[Olausson et al\. \(2023\)](https://arxiv.org/html/2610.41089#bib.bib20), relationships between problem structure and reasoning complexity[Kang et al\. \(2024\)](https://arxiv.org/html/2610.41089#bib.bib17), and limitations in LLM reasoning over complex data structures[He et al\. \(2026\)](https://arxiv.org/html/2610.41089#bib.bib16)\. Related work examines formal specification inference and reliable theorem proving[Le\-Cong et al\. \(2025\)](https://arxiv.org/html/2610.41089#bib.bib19);[Quan et al\. \(2025\)](https://arxiv.org/html/2610.41089#bib.bib18)\. Other studies examine compositional problem complexity[Xie et al\. \(2026\)](https://arxiv.org/html/2610.41089#bib.bib23)and constraint\-based problem decomposition[Zhou et al\. \(2025\)](https://arxiv.org/html/2610.41089#bib.bib22)\. Research on multi\-constraint instruction following further shows that constraint composition and dependencies affect model performance[Wen et al\. \(2024\)](https://arxiv.org/html/2610.41089#bib.bib15);[Liu et al\. \(2026\)](https://arxiv.org/html/2610.41089#bib.bib24)\. 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\.

### 2\.3Learning from Graph Representations

Studies show that LLMs struggle with structured graph reasoning problems, motivating explicit representations of relationships and dependencies[Dai et al\. \(2025\)](https://arxiv.org/html/2610.41089#bib.bib26);[Agrawal et al\. \(2024\)](https://arxiv.org/html/2610.41089#bib.bib27)\. Structural properties have also been used to predict solver performance through handcrafted features[Xu et al\. \(2008\)](https://arxiv.org/html/2610.41089#bib.bib21)and graph\-based learning[Chang et al\. \(2022\)](https://arxiv.org/html/2610.41089#bib.bib30);[Fu et al\. \(2025\)](https://arxiv.org/html/2610.41089#bib.bib29)\. Graph neural networks, in contrast, learn representations through neighborhood aggregation[Kipf and Welling \(2017\)](https://arxiv.org/html/2610.41089#bib.bib25);[Xu et al\. \(2019\)](https://arxiv.org/html/2610.41089#bib.bib32), including for language reasoning over knowledge graphs[Yasunaga et al\. \(2021\)](https://arxiv.org/html/2610.41089#bib.bib31)\. Self\-supervised methods such as GraphMAE[Hou et al\. \(2022\)](https://arxiv.org/html/2610.41089#bib.bib33)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\.

## 3Method

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: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\.Figure[1](https://arxiv.org/html/2610.41089#S3.F1)illustrates the workflow of CIRCE\. We first extract a CIR and compile it into a constraint graph \(Section[3\.2](https://arxiv.org/html/2610.41089#S3.SS2)\)\. We then represent the graph using handcrafted features in CIRCE\-Stats \(Section[3\.3](https://arxiv.org/html/2610.41089#S3.SS3)\) or a GNN with or without self\-supervised pretraining in CIRCE\-GNN \(Section[3\.4](https://arxiv.org/html/2610.41089#S3.SS4)\)\. Finally, a gradient\-boosted predictor maps the structural representation to a correctness probability for the target model \(Section[3\.5](https://arxiv.org/html/2610.41089#S3.SS5)\)\.

### 3\.1Problem Formulation

Given a problemxx, a language modelmm, and an inference protocolπ\\pi, we measure how complexxxis formmby the probability that a response is correct,

pm,π​\(x\)=Pr⁡\(a response to​x​is correct∣m,π\),p\_\{m,\\pi\}\(x\)=\\Pr\(\\text\{a response to \}x\\text\{ is correct\}\\mid m,\\pi\),\(1\)where lower means thatxxis more complex formm\. To obtain enough labels for training and evaluation, we observeR=10R=10responses per problem for each model, using a fixed inference protocol\. Withcr∈\{0,1\}c\_\{r\}\\in\\\{0,1\\\}indicating whether a response is correct, the empirical correctness rate is

y=∑r=1Rcr/R\.y=\\sum\_\{r=1\}^\{R\}c\_\{r\}/R\.\(2\)

### 3\.2From 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 graphG=\(V,E\)G=\(V,E\)\.

There are two types of graph nodes\.Factor nodesrepresent constraints and the query, whilevariable nodesrepresent declared variables, propositions, entities, and shared domain values\. Edges connect factor nodes to their corresponding variable nodes\. For example,50​B=W50B\{=\}Wcreates a factor connected to bag countBBand weightWW;C=18​BC\{=\}18Bcreates another connected to costCCandBB\. The query factor connects to the requested costCC\.

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[B](https://arxiv.org/html/2610.41089#A2)provides the checks, repairs, and validation details\.

### 3\.3CIRCE\-Stats: Handcrafted Features

Structural features have been used to predict the difficulty of constraint\-solving problems, as exemplified by SATzilla[Xu et al\. \(2008\)](https://arxiv.org/html/2610.41089#bib.bib21)\. 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[C](https://arxiv.org/html/2610.41089#A3)lists the features and their definitions\.

### 3\.4CIRCE\-GNN: GNN\-based Features

Experiments in Section[5\.1](https://arxiv.org/html/2610.41089#S5.SS1)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 vectorhv\(0\)h\_\{v\}^\{\(0\)\}and use six GIN\-style layers[Xu et al\. \(2019\)](https://arxiv.org/html/2610.41089#bib.bib32)\. Each node vectorhv\(ℓ\)h\_\{v\}^\{\(\\ell\)\}and edge embeddingeu​v\(ℓ\)e\_\{uv\}^\{\(\\ell\)\}has 64 dimensions\. At layerℓ∈\{1,…,6\}\\ell\\in\\\{1,\\ldots,6\\\},eu​v\(ℓ\)e\_\{uv\}^\{\(\\ell\)\}is a trainable embedding, andmv\(ℓ\)m\_\{v\}^\{\(\\ell\)\}sums incoming neighbor messages\.𝒩⁡\(v\)\\mathcal\{N\}\(v\)denotes the nodes connected tovv,ϵℓ\\epsilon\_\{\\ell\}is a learned scalar,MLPℓ\\operatorname\{MLP\}\_\{\\ell\}a feedforward network, andLN\\operatorname\{LN\}layer normalization\. The update is

mv\(ℓ\)\\displaystyle m\_\{v\}^\{\(\\ell\)\}=∑u∈𝒩⁡\(v\)ReLU⁡\(hu\(ℓ−1\)\+eu​v\(ℓ\)\),\\displaystyle=\\sum\_\{u\\in\\mathcal\{N\}\(v\)\}\\operatorname\{ReLU\}\\\!\\left\(h\_\{u\}^\{\(\\ell\-1\)\}\+e\_\{uv\}^\{\(\\ell\)\}\\right\),\(3\)hv\(ℓ\)\\displaystyle h\_\{v\}^\{\(\\ell\)\}=LN⁡\(hv\(ℓ−1\)CLOSE\\displaystyle=\\operatorname\{LN\}\\Big\(h\_\{v\}^\{\(\\ell\-1\)\}OPEN\+MLPℓ⁡\(\(1\+ϵℓ\)​hv\(ℓ−1\)\+mv\(ℓ\)\)\)\.\\displaystyle\\quad\+\\operatorname\{MLP\}\_\{\\ell\}\\\!\\left\(\(1\+\\epsilon\_\{\\ell\}\)h\_\{v\}^\{\(\\ell\-1\)\}\+m\_\{v\}^\{\(\\ell\)\}\\right\)\\Big\)\.\(4\)
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\. \(2023\)](https://arxiv.org/html/2610.41089#bib.bib34)\. 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\. \(2022\)](https://arxiv.org/html/2610.41089#bib.bib33)\. The decoders predict six attributes: node kind, node subtype, factor type, operator counts, edge role and edge polarity\. Let𝒜\\mathcal\{A\}denote these six attributes andℒa\\mathcal\{L\}\_\{a\}the average reconstruction loss for attributeaa\. Node decoders receivehv\(6\)h\_\{v\}^\{\(6\)\}, and edge decoders receive\[hu\(6\);hv\(6\)\]\[h\_\{u\}^\{\(6\)\};h\_\{v\}^\{\(6\)\}\]\. The pretraining objective is

ℒpretrain=16​∑a∈𝒜ℒa\.\\mathcal\{L\}\_\{\\mathrm\{pretrain\}\}=\\frac\{1\}\{6\}\\sum\_\{a\\in\\mathcal\{A\}\}\\mathcal\{L\}\_\{a\}\.\(5\)
We freeze the GNN in both encoder variants after 100 pretraining epochs for CIRCE\-GNN\-P, and right after initialization for CIRCE\-GNN\-R\. Letqv=1q\_\{v\}=1for a query node and00otherwise\. We concatenate the coordinate\-wise sum, mean, query sum and standard deviation of the final node vectors into the graph representation

z\(G\)=\[\\displaystyle z\(G\)=\\bigl\[∑vhv\(6\);meanv⁡hv\(6\);\\displaystyle\\sum\_\{v\}h\_\{v\}^\{\(6\)\};\\operatorname\{mean\}\_\{v\}h\_\{v\}^\{\(6\)\};\(6\)OPEN∑vqv​hv\(6\);stdv⁡hv\(6\)\]\.\\displaystyle\\sum\_\{v\}q\_\{v\}h\_\{v\}^\{\(6\)\};\\operatorname\{std\}\_\{v\}h\_\{v\}^\{\(6\)\}\\bigr\]\.

### 3\.5Complexity Estimation

Both CIRCE\-Stats and CIRCE\-GNN give a structural representationu⁡\(x\)u\(x\)without using correctness labels\. We then fit a predictorp^m,π​\(x\)=fm,π​\(u⁡\(x\)\)\\hat\{p\}\_\{m,\\pi\}\(x\)=f\_\{m,\\pi\}\(u\(x\)\)to predict the correctness probability\. We use histogram gradient\-boosted trees

fGB​\(u\)=σ⁡\(b\+η​∑t=1Tgt​\(u~\)\),f\_\{\\mathrm\{GB\}\}\(u\)=\\sigma\\\!\\left\(b\+\\eta\\sum\_\{t=1\}^\{T\}g\_\{t\}\(\\widetilde\{u\}\)\\right\),\(7\)wheregtg\_\{t\}is a fitted regression tree, andu~\\widetilde\{u\}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\.

## 4Experiments

### 4\.1Evaluation 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

NLL=−1n∑i\[yilogp^i\+\(1−yi\)log\(1−p^i\)\]\.\\operatorname\{NLL\}=\-\\frac\{1\}\{n\}\\sum\_\{i\}\[y\_\{i\}\\log\\hat\{p\}\_\{i\}\+\(1\-y\_\{i\}\)\\log\(1\-\\hat\{p\}\_\{i\}\)\]\.\(8\)Hereyi=ki/10y\_\{i\}=k\_\{i\}/10is the observed success rate over ten attempts, andp^i\\hat\{p\}\_\{i\}is the predicted correctness probability, clipped to\[10−6,1−10−6\]\[10^\{\-6\},1\-10^\{\-6\}\]\. We also report AUROC[Bradley \(1997\)](https://arxiv.org/html/2610.41089#bib.bib35)\.

We compare our methods against the following baselines:

- •C0: training\-fold mean predictor
- •Self probability: calibrated model self\-reported probability
- •ADeLe[Zhou et al\. \(2026\)](https://arxiv.org/html/2610.41089#bib.bib37): a random forest predictor using 18 task\-demand dimensions annotated by GPT\-6 Sol, and an unguessability dimension
- •PredictaBoard[Pacchiardi et al\. \(2025\)](https://arxiv.org/html/2610.41089#bib.bib36): an assessor that predicts correctness from OpenAI text embeddings
- •Already Knows[Zhu et al\. \(2025\)](https://arxiv.org/html/2610.41089#bib.bib38): a hidden\-state predictor trained with temporal\-difference learning

### 4\.2Models and Benchmarks

Our methods and baselines are evaluated on Qwen3\.5\-9B\([Qwen Team, 2026a](https://arxiv.org/html/2610.41089#bib.bib45)\), Qwen3\.8\-27B\([Qwen Team, 2026b](https://arxiv.org/html/2610.41089#bib.bib46)\), Inkling\([Thinking Machines Lab, 2026](https://arxiv.org/html/2610.41089#bib.bib47)\)and GPT\-6 Luna\([OpenAI, 2026](https://arxiv.org/html/2610.41089#bib.bib48)\), 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](https://arxiv.org/html/2610.41089#S4.T1)\)\. 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[B](https://arxiv.org/html/2610.41089#A2)\)\. We set the thinking effort of the models based on the difficulty of each benchmark to prevent saturated accuracy on easier benchmarks \(Appendix[A](https://arxiv.org/html/2610.41089#A1)\)\. 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\.
### 4\.3Main Results

Table 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\.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](https://arxiv.org/html/2610.41089#S4.T2)\)\. 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 baselines, 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 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[D](https://arxiv.org/html/2610.41089#A4)\.

## 5Further Analysis

### 5\.1Effect of Feature Count

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\.We examine how prediction changes as more handcrafted 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](https://arxiv.org/html/2610.41089#S5.F2)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\.

### 5\.2Qualitative 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](https://arxiv.org/html/2610.41089#S5.F3)\)\. 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\.

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\.

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\.
#### 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 relationsW=850W=850,50​B=W50B=WandC=18​BC=18B, whereWWis the total weight,BBthe number of bags andCCthe 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\.

### 5\.3Reliability 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\.

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\.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\.As shown in Table[3](https://arxiv.org/html/2610.41089#S5.T3), 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%, while the correctness of the CIR method is 92\.5%\. Furthermore, as shown in Table[3](https://arxiv.org/html/2610.41089#S5.T3)and Table[4](https://arxiv.org/html/2610.41089#S5.T4), 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\.

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[B](https://arxiv.org/html/2610.41089#A2)\.

### 5\.4Comparison 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:Effect of the downstream predictor\. Each cell reports NLL↓\\downarrow/ AUROC↑\\uparrow, averaged equally across seven benchmarks and four target models\.Table[5](https://arxiv.org/html/2610.41089#S5.T5)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\.

## 6Conclusion

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\.

## 7Limitations

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\. \(2021\)](https://arxiv.org/html/2610.41089#bib.bib1)at Indiana University through allocation TRA120004 from the Advanced Cyberinfrastructure Coordination Ecosystem: Services & Support \(ACCESS\) program[Boerner et al\. \(2023\)](https://arxiv.org/html/2610.41089#bib.bib2), 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\.

## References

- Agrawalet al\.\(2024\)P\. Agrawal, S\. Vasania, and C\. TanCan llms perform structured graph reasoning?\.External Links:2402\.01805,[Link](https://arxiv.org/abs/2402.01805)Cited by:[§2\.3](https://arxiv.org/html/2610.41089#S2.SS3.p1.1)\.
- Boerneret al\.\(2023\)T\. J\. Boerner, S\. Deems, T\. R\. Furlani, S\. L\. Knuth, and J\. TownsACCESS: advancing innovation: NSF’s advanced cyberinfrastructure coordination ecosystem: services & support\.InProceedings of the Practice and Experience in Advanced Research Computing \(PEARC ’23\),New York, NY, USA,pp\. 1–4\.External Links:[Document](https://dx.doi.org/10.1145/3569951.3597559),[Link](https://doi.org/10.1145/3569951.3597559)Cited by:[Acknowledgments](https://arxiv.org/html/2610.41089#Sx1.p1.1)\.
- Bradley \(1997\)A\. P\. BradleyThe use of the area under the roc curve in the evaluation of machine learning algorithms\.Pattern Recognition30\(7\),pp\. 1145–1159\.External Links:ISSN 0031\-3203,[Document](https://dx.doi.org/https%3A//doi.org/10.1016/S0031-3203%2896%2900142-2),[Link](https://www.sciencedirect.com/science/article/pii/S0031320396001422)Cited by:[§4\.1](https://arxiv.org/html/2610.41089#S4.SS1.p1.2)\.
- Changet al\.\(2022\)W\. Chang, H\. Zhang, and J\. LuoPredicting propositional satisfiability based on graph attention networks\.International Journal of Computational Intelligence Systems15\(1\),pp\. 84\.External Links:[Document](https://dx.doi.org/10.1007/s44196-022-00139-9)Cited by:[§2\.3](https://arxiv.org/html/2610.41089#S2.SS3.p1.1)\.
- Chenet al\.\(2025\)J\. Chen, Q\. He, S\. Yuan, A\. Chen, Z\. Cai, W\. Dai, H\. Yu, Q\. Yu, X\. Li, J\. Chen, H\. Zhou, and M\. WangEnigmata: scaling logical reasoning in large language models with synthetic verifiable puzzles\.External Links:2505\.19914,[Link](https://arxiv.org/abs/2505.19914)Cited by:[Table 1](https://arxiv.org/html/2610.41089#S4.T1.2.5.1.1.1),[Table 1](https://arxiv.org/html/2610.41089#S4.T1.2.6.1.1.1)\.
- Chenet al\.\(2023\)L\. Chen, M\. Zaharia, and J\. ZouFrugalGPT: how to use large language models while reducing cost and improving performance\.External Links:2305\.05176,[Link](https://arxiv.org/abs/2305.05176)Cited by:[§1](https://arxiv.org/html/2610.41089#S1.p2.1)\.
- Chen and Guestrin \(2016\)T\. Chen and C\. GuestrinXGBoost: a scalable tree boosting system\.InProceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,pp\. 785–794\.External Links:[Document](https://dx.doi.org/10.1145/2939672.2939785)Cited by:[Appendix D](https://arxiv.org/html/2610.41089#A4.SS0.SSS0.Px3.p1.1)\.
- Cobbeet al\.\(2021\)K\. Cobbe, V\. Kosaraju, M\. Bavarian, M\. Chen, H\. Jun, L\. Kaiser, M\. Plappert, J\. Tworek, J\. Hilton, R\. Nakano, C\. Hesse, and J\. SchulmanTraining verifiers to solve math word problems\.External Links:2110\.14168,[Link](https://arxiv.org/abs/2110.14168)Cited by:[Table 1](https://arxiv.org/html/2610.41089#S4.T1.2.7.1.1.1)\.
- Daiet al\.\(2025\)X\. Dai, Q\. Wen, Y\. Shen, H\. Wen, D\. Li, J\. Tang, and C\. ShanRevisiting the graph reasoning ability of large language models: case studies in translation, connectivity and shortest path\.External Links:2408\.09529,[Link](https://arxiv.org/abs/2408.09529)Cited by:[§2\.3](https://arxiv.org/html/2610.41089#S2.SS3.p1.1)\.
- Fuet al\.\(2025\)Y\. Fu, A\. Tompkins, Y\. Song, and M\. PagnuccoStructure based sat dataset for analysing gnn generalisation\.InProceedings of The 28th International Conference on Artificial Intelligence and Statistics,Y\. Li, S\. Mandt, S\. Agrawal, and E\. Khan \(Eds\.\),Proceedings of Machine Learning Research, Vol\.258,pp\. 4834–4842\.External Links:[Link](https://proceedings.mlr.press/v258/fu25b.html)Cited by:[§2\.3](https://arxiv.org/html/2610.41089#S2.SS3.p1.1)\.
- Hagberget al\.\(2008\)A\. A\. Hagberg, D\. A\. Schult, and P\. J\. SwartExploring network structure, dynamics, and function using networkx\.InProceedings of the 7th Python in Science Conference,pp\. 11–15\.External Links:[Link](https://proceedings.scipy.org/articles/TCWV9851)Cited by:[Appendix C](https://arxiv.org/html/2610.41089#A3.SS0.SSS0.Px1.p1.1)\.
- Hanet al\.\(2024\)S\. Han, H\. Schoelkopf, Y\. Zhao, Z\. Qi, M\. Riddell, W\. Zhou, J\. Coady, D\. Peng, Y\. Qiao, L\. Benson, L\. Sun, A\. Wardle\-Solano, H\. Szabó, E\. Zubova, M\. Burtell, J\. Fan, Y\. Liu, B\. Wong, M\. Sailor, A\. Ni, L\. Nan, J\. Kasai, T\. Yu, R\. Zhang, A\. Fabbri, W\. M\. Kryscinski, S\. Yavuz, Y\. Liu, X\. V\. Lin, S\. Joty, Y\. Zhou, C\. Xiong, R\. Ying, A\. Cohan, and D\. RadevFOLIO: natural language reasoning with first\-order logic\.InProceedings of the 2024 Conference on Empirical Methods in Natural Language Processing,Y\. Al\-Onaizan, M\. Bansal, and Y\. Chen \(Eds\.\),Miami, Florida, USA,pp\. 22017–22031\.External Links:[Link](https://aclanthology.org/2024.emnlp-main.1229/),[Document](https://dx.doi.org/10.18653/v1/2024.emnlp-main.1229)Cited by:[Table 1](https://arxiv.org/html/2610.41089#S4.T1.2.3.1.1.1)\.
- Hancocket al\.\(2021\)D\. Y\. Hancock, J\. Fischer, J\. M\. Lowe, W\. Snapp\-Childs, M\. Pierce, S\. Marru, J\. E\. Coulter, M\. Vaughn, B\. Beck, N\. Merchant, E\. Skidmore, and G\. JacobsJetstream2: accelerating cloud computing via jetstream\.InProceedings of the Practice and Experience in Advanced Research Computing \(PEARC ’21\),New York, NY, USA,pp\. 1–8\.External Links:[Document](https://dx.doi.org/10.1145/3437359.3465565),[Link](https://doi.org/10.1145/3437359.3465565)Cited by:[Acknowledgments](https://arxiv.org/html/2610.41089#Sx1.p1.1)\.
- Heet al\.\(2026\)Y\. He, Y\. Li, C\. White, and E\. VitercikCan LLMs reason structurally? Benchmarking via the lens of data structures\.InProceedings of the 43rd International Conference on Machine Learning,T\. Zhang, M\. Dudik, M\. Jaggi, A\. Agarwal, S\. Li, D\. Schuurmans, J\. Zhu, F\. Berkenkamp, H\. Dong, and A\. Bietti \(Eds\.\),Proceedings of Machine Learning Research, Vol\.306,pp\. 41602–41650\.External Links:[Link](https://proceedings.mlr.press/v306/he26x.html)Cited by:[§2\.2](https://arxiv.org/html/2610.41089#S2.SS2.p1.1)\.
- Houet al\.\(2023\)Z\. Hou, Y\. He, Y\. Cen, X\. Liu, Y\. Dong, E\. Kharlamov, and J\. TangGraphMAE2: a decoding\-enhanced masked self\-supervised graph learner\.External Links:2304\.04779,[Link](https://arxiv.org/abs/2304.04779)Cited by:[§3\.4](https://arxiv.org/html/2610.41089#S3.SS4.p2.1)\.
- Houet al\.\(2022\)Z\. Hou, X\. Liu, Y\. Cen, Y\. Dong, H\. Yang, C\. Wang, and J\. TangGraphMAE: self\-supervised masked graph autoencoders\.External Links:2205\.10803,[Link](https://arxiv.org/abs/2205.10803)Cited by:[§2\.3](https://arxiv.org/html/2610.41089#S2.SS3.p1.1),[§3\.4](https://arxiv.org/html/2610.41089#S3.SS4.p2.1)\.
- Jianget al\.\(2026\)X\. Jiang, J\. Chen, C\. Zhang, J\. Gao, C\. Hu, C\. Zhang, Y\. Wu, and Y\. ZhangReasoning in a combinatorial and constrained world: benchmarking LLMs on natural\-language combinatorial optimization\.InFindings of the Association for Computational Linguistics: ACL 2026,M\. Liakata, V\. P\. Moreira, J\. Zhang, and D\. Jurgens \(Eds\.\),San Diego, California, United States,pp\. 30592–30648\.External Links:[Link](https://aclanthology.org/2026.findings-acl.1529/),[Document](https://dx.doi.org/10.18653/v1/2026.findings-acl.1529),ISBN 979\-8\-89176\-395\-1Cited by:[Table 1](https://arxiv.org/html/2610.41089#S4.T1.2.4.1.1.1)\.
- Kamathet al\.\(2020\)A\. Kamath, R\. Jia, and P\. LiangSelective question answering under domain shift\.InProceedings of the 58th Annual Meeting of the Association for Computational Linguistics,D\. Jurafsky, J\. Chai, N\. Schluter, and J\. Tetreault \(Eds\.\),Online,pp\. 5684–5696\.External Links:[Link](https://aclanthology.org/2020.acl-main.503/),[Document](https://dx.doi.org/10.18653/v1/2020.acl-main.503)Cited by:[§1](https://arxiv.org/html/2610.41089#S1.p2.1)\.
- Kanget al\.\(2024\)L\. Kang, Z\. Zhao, D\. Hsu, and W\. S\. LeeOn the empirical complexity of reasoning and planning in LLMs\.InFindings of the Association for Computational Linguistics: EMNLP 2024,Y\. Al\-Onaizan, M\. Bansal, and Y\. Chen \(Eds\.\),Miami, Florida, USA,pp\. 2897–2936\.External Links:[Link](https://aclanthology.org/2024.findings-emnlp.164/),[Document](https://dx.doi.org/10.18653/v1/2024.findings-emnlp.164)Cited by:[§2\.2](https://arxiv.org/html/2610.41089#S2.SS2.p1.1)\.
- Kipf and Welling \(2017\)T\. N\. Kipf and M\. WellingSemi\-supervised classification with graph convolutional networks\.External Links:1609\.02907,[Link](https://arxiv.org/abs/1609.02907)Cited by:[§2\.3](https://arxiv.org/html/2610.41089#S2.SS3.p1.1)\.
- Le\-Conget al\.\(2025\)T\. Le\-Cong, B\. Le, and T\. MurrayCan llms reason about program semantics? a comprehensive evaluation of llms on formal specification inference\.External Links:2503\.04779,[Link](https://arxiv.org/abs/2503.04779)Cited by:[§2\.2](https://arxiv.org/html/2610.41089#S2.SS2.p1.1)\.
- Liuet al\.\(2026\)J\. Liu, C\. Qian, Z\. Wang, B\. Li, J\. Liu, Q\. Zong, H\. Wang, J\. Kim, Y\. Wang, B\. He, X\. Chen, Y\. R\. Fung, and H\. JiAdaPlanBench: evaluating adaptive planning in large language model agents under world and user constraints\.External Links:2606\.05622,[Link](https://arxiv.org/abs/2606.05622)Cited by:[§2\.2](https://arxiv.org/html/2610.41089#S2.SS2.p1.1)\.
- Mitchellet al\.\(1992\)D\. G\. Mitchell, B\. Selman, and H\. J\. LevesqueHard and easy distributions of SAT problems\.InProceedings of the Tenth National Conference on Artificial Intelligence,pp\. 459–465\.Cited by:[§1](https://arxiv.org/html/2610.41089#S1.p4.1)\.
- Mozafariet al\.\(2026\)J\. Mozafari, B\. Piryani, and A\. JatowtQuestion difficulty estimation for large language models via answer plausibility scoring\.InProceedings of the 64th Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\),M\. Liakata, V\. P\. Moreira, J\. Zhang, and D\. Jurgens \(Eds\.\),San Diego, California, United States,pp\. 11124–11151\.External Links:[Link](https://aclanthology.org/2026.acl-long.510/),[Document](https://dx.doi.org/10.18653/v1/2026.acl-long.510),ISBN 979\-8\-89176\-390\-6Cited by:[§2\.1](https://arxiv.org/html/2610.41089#S2.SS1.p1.1)\.
- Olaussonet al\.\(2023\)T\. Olausson, A\. Gu, B\. Lipkin, C\. Zhang, A\. Solar\-Lezama, J\. Tenenbaum, and R\. LevyLINC: a neurosymbolic approach for logical reasoning by combining language models with first\-order logic provers\.InProceedings of the 2023 Conference on Empirical Methods in Natural Language Processing,H\. Bouamor, J\. Pino, and K\. Bali \(Eds\.\),Singapore,pp\. 5153–5176\.External Links:[Link](https://aclanthology.org/2023.emnlp-main.313/),[Document](https://dx.doi.org/10.18653/v1/2023.emnlp-main.313)Cited by:[§2\.2](https://arxiv.org/html/2610.41089#S2.SS2.p1.1)\.
- Onget al\.\(2025\)I\. Ong, A\. Almahairi, V\. Wu, W\. Chiang, T\. Wu, J\. E\. Gonzalez, M\. W\. Kadous, and I\. StoicaRouteLLM: learning to route llms with preference data\.External Links:2406\.18665,[Link](https://arxiv.org/abs/2406.18665)Cited by:[§1](https://arxiv.org/html/2610.41089#S1.p2.1)\.
- OpenAI \(2026\)OpenAIGPT\-6 Luna model documentation\.Note:Accessed October 4, 2026External Links:[Link](https://developers.openai.com/api/docs/models/gpt-6-luna)Cited by:[§4\.2](https://arxiv.org/html/2610.41089#S4.SS2.p1.1)\.
- Pacchiardiet al\.\(2025\)L\. Pacchiardi, K\. Voudouris, B\. Slater, F\. Martínez\-Plumed, J\. Hernandez\-Orallo, L\. Zhou, and W\. SchellaertPredictaBoard: benchmarking LLM score predictability\.InFindings of the Association for Computational Linguistics: ACL 2025,W\. Che, J\. Nabende, E\. Shutova, and M\. T\. Pilehvar \(Eds\.\),Vienna, Austria,pp\. 15245–15266\.External Links:[Link](https://aclanthology.org/2025.findings-acl.790/),[Document](https://dx.doi.org/10.18653/v1/2025.findings-acl.790),ISBN 979\-8\-89176\-256\-5Cited by:[§1](https://arxiv.org/html/2610.41089#S1.p3.1),[§2\.1](https://arxiv.org/html/2610.41089#S2.SS1.p1.1),[4th item](https://arxiv.org/html/2610.41089#S4.I1.i4.p1.1)\.
- Panet al\.\(2023\)L\. Pan, A\. Albalak, X\. Wang, and W\. Y\. WangLogic\-LM: empowering large language models with symbolic solvers for faithful logical reasoning\.InFindings of the Association for Computational Linguistics: EMNLP 2023,H\. Bouamor, J\. Pino, and K\. Bali \(Eds\.\),Singapore,pp\. 3806–3824\.External Links:[Document](https://dx.doi.org/10.18653/v1/2023.findings-emnlp.248),[Link](https://aclanthology.org/2023.findings-emnlp.248/)Cited by:[§2\.2](https://arxiv.org/html/2610.41089#S2.SS2.p1.1)\.
- Paszkeet al\.\(2019\)A\. Paszke, S\. Gross, F\. Massa, A\. Lerer, J\. Bradbury, G\. Chanan,et al\.PyTorch: an imperative style, high\-performance deep learning library\.InAdvances in Neural Information Processing Systems,Vol\.32\.External Links:[Link](https://arxiv.org/abs/1912.01703)Cited by:[Appendix E](https://arxiv.org/html/2610.41089#A5.p3.1)\.
- Pedregosaet al\.\(2011\)F\. Pedregosa, G\. Varoquaux, A\. Gramfort, V\. Michel, B\. Thirion, O\. Grisel, M\. Blondel,et al\.Scikit\-learn: machine learning in python\.Journal of Machine Learning Research12,pp\. 2825–2830\.External Links:[Link](https://jmlr.org/papers/v12/pedregosa11a.html)Cited by:[§C\.2](https://arxiv.org/html/2610.41089#A3.SS2.p1.1)\.
- Quanet al\.\(2025\)X\. Quan, M\. Valentino, L\. A\. Dennis, and A\. FreitasFaithful and robust llm\-driven theorem proving for nli explanations\.External Links:2505\.24264,[Link](https://arxiv.org/abs/2505.24264)Cited by:[§2\.2](https://arxiv.org/html/2610.41089#S2.SS2.p1.1)\.
- Qwen Team \(2026a\)Qwen TeamQwen3\.5\-9B model card\.Note:Hugging FaceAccessed October 4, 2026External Links:[Link](https://huggingface.co/Qwen/Qwen3.5-9B)Cited by:[§4\.2](https://arxiv.org/html/2610.41089#S4.SS2.p1.1)\.
- Qwen Team \(2026b\)Qwen TeamQwen3\.8\-27B model card\.Note:Hugging FaceAccessed October 4, 2026External Links:[Link](https://huggingface.co/Qwen/Qwen3.8-27B)Cited by:[§4\.2](https://arxiv.org/html/2610.41089#S4.SS2.p1.1)\.
- Schellaertet al\.\(2025\)W\. Schellaert, F\. Martínez\-Plumed, and J\. Hernández\-OralloAnalysing the predictability of language model performance\.ACM Trans\. Intell\. Syst\. Technol\.16\(2\)\.External Links:ISSN 2157\-6904,[Link](https://doi.org/10.1145/3706118),[Document](https://dx.doi.org/10.1145/3706118)Cited by:[§2\.1](https://arxiv.org/html/2610.41089#S2.SS1.p1.1)\.
- Snellet al\.\(2024\)C\. Snell, J\. Lee, K\. Xu, and A\. KumarScaling llm test\-time compute optimally can be more effective than scaling model parameters\.External Links:2408\.03314,[Link](https://arxiv.org/abs/2408.03314)Cited by:[§1](https://arxiv.org/html/2610.41089#S1.p2.1)\.
- Srivastavaet al\.\(2023\)A\. Srivastava, A\. Rastogi, A\. Rao, A\. A\. M\. Shoeb, A\. Abid, A\. Fisch, A\. Brown, A\. Santoro, A\. Gupta,et al\.Beyond the imitation game: quantifying and extrapolating the capabilities of language models\.Transactions on Machine Learning Research\.External Links:[Link](https://arxiv.org/abs/2206.04615)Cited by:[Appendix A](https://arxiv.org/html/2610.41089#A1.SS0.SSS0.Px1.p1.1)\.
- Suzgunet al\.\(2023\)M\. Suzgun, N\. Scales, N\. Schärli, S\. Gehrmann, Y\. Tay, H\. W\. Chung, A\. Chowdhery, Q\. Le, E\. Chi, D\. Zhou, and J\. WeiChallenging BIG\-bench tasks and whether chain\-of\-thought can solve them\.InFindings of the Association for Computational Linguistics: ACL 2023,A\. Rogers, J\. Boyd\-Graber, and N\. Okazaki \(Eds\.\),Toronto, Canada,pp\. 13003–13051\.External Links:[Link](https://aclanthology.org/2023.findings-acl.824/),[Document](https://dx.doi.org/10.18653/v1/2023.findings-acl.824)Cited by:[Table 1](https://arxiv.org/html/2610.41089#S4.T1.2.8.1.1.1)\.
- Thinking Machines Lab \(2026\)Thinking Machines LabInkling model card\.Note:Accessed October 4, 2026External Links:[Link](https://thinkingmachines.ai/model-card/inkling/)Cited by:[§4\.2](https://arxiv.org/html/2610.41089#S4.SS2.p1.1)\.
- Tianet al\.\(2023\)K\. Tian, E\. Mitchell, A\. Zhou, A\. Sharma, R\. Rafailov, H\. Yao, C\. Finn, and C\. ManningJust ask for calibration: strategies for eliciting calibrated confidence scores from language models fine\-tuned with human feedback\.InProceedings of the 2023 Conference on Empirical Methods in Natural Language Processing,H\. Bouamor, J\. Pino, and K\. Bali \(Eds\.\),Singapore,pp\. 5433–5442\.External Links:[Link](https://aclanthology.org/2023.emnlp-main.330/),[Document](https://dx.doi.org/10.18653/v1/2023.emnlp-main.330)Cited by:[§2\.1](https://arxiv.org/html/2610.41089#S2.SS1.p1.1)\.
- Truonget al\.\(2025\)S\. T\. Truong, Y\. Tu, P\. Liang, B\. Li, and S\. KoyejoReliable and efficient amortized model\-based evaluation\.InProceedings of the 42nd International Conference on Machine Learning,A\. Singh, M\. Fazel, D\. Hsu, S\. Lacoste\-Julien, F\. Berkenkamp, T\. Maharaj, K\. Wagstaff, and J\. Zhu \(Eds\.\),Proceedings of Machine Learning Research, Vol\.267,pp\. 60238–60265\.External Links:[Link](https://proceedings.mlr.press/v267/truong25c.html)Cited by:[§2\.1](https://arxiv.org/html/2610.41089#S2.SS1.p1.1)\.
- Weiet al\.\(2025\)A\. Wei, Y\. Wu, Y\. Wan, T\. Suresh, H\. Tan, Z\. Zhou, S\. Koyejo, K\. Wang, and A\. AikenSATBench: benchmarking LLMs’ logical reasoning via automated puzzle generation from SAT formulas\.InProceedings of the 2025 Conference on Empirical Methods in Natural Language Processing,C\. Christodoulopoulos, T\. Chakraborty, C\. Rose, and V\. Peng \(Eds\.\),Suzhou, China,pp\. 33832–33849\.External Links:[Link](https://aclanthology.org/2025.emnlp-main.1716/),[Document](https://dx.doi.org/10.18653/v1/2025.emnlp-main.1716),ISBN 979\-8\-89176\-332\-6Cited by:[Table 1](https://arxiv.org/html/2610.41089#S4.T1.2.2.1.1.1)\.
- Wenet al\.\(2024\)B\. Wen, P\. Ke, X\. Gu, L\. Wu, H\. Huang, J\. Zhou, W\. Li, B\. Hu, W\. Gao, J\. Xu, Y\. Liu, J\. Tang, H\. Wang, and M\. HuangBenchmarking complex instruction\-following with multiple constraints composition\.InAdvances in Neural Information Processing Systems,External Links:[Document](https://dx.doi.org/10.52202/079017-4371),[Link](https://mlanthology.org/neurips/2024/wen2024neurips-benchmarking/)Cited by:[§2\.2](https://arxiv.org/html/2610.41089#S2.SS2.p1.1)\.
- Xiaet al\.\(2025\)Y\. Xia, P\. H\. Luz De Araujo, K\. Zaporojets, and B\. RothInfluences on LLM calibration: a study of response agreement, loss functions, and prompt styles\.InProceedings of the 63rd Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\),W\. Che, J\. Nabende, E\. Shutova, and M\. T\. Pilehvar \(Eds\.\),Vienna, Austria,pp\. 3740–3761\.External Links:[Link](https://aclanthology.org/2025.acl-long.188/),[Document](https://dx.doi.org/10.18653/v1/2025.acl-long.188),ISBN 979\-8\-89176\-251\-0Cited by:[§2\.1](https://arxiv.org/html/2610.41089#S2.SS1.p1.1)\.
- Xiaoet al\.\(2026\)H\. Xiao, V\. Patil, H\. Lee, E\. Stengel\-Eskin, and M\. BansalGeneralized correctness models: learning calibrated and cross\-model correctness predictors from historical patterns\.InProceedings of the 43rd International Conference on Machine Learning,T\. Zhang, M\. Dudik, M\. Jaggi, A\. Agarwal, S\. Li, D\. Schuurmans, J\. Zhu, F\. Berkenkamp, H\. Dong, and A\. Bietti \(Eds\.\),Proceedings of Machine Learning Research, Vol\.306,pp\. 138884–138908\.External Links:[Link](https://proceedings.mlr.press/v306/xiao26l.html)Cited by:[§2\.1](https://arxiv.org/html/2610.41089#S2.SS1.p1.1)\.
- Xieet al\.\(2026\)C\. Xie, X\. Gu, Y\. Shi, and B\. ShenRethinking code complexity through the lens of large language models\.External Links:2602\.07882,[Link](https://arxiv.org/abs/2602.07882)Cited by:[§2\.2](https://arxiv.org/html/2610.41089#S2.SS2.p1.1)\.
- Xuet al\.\(2019\)K\. Xu, W\. Hu, J\. Leskovec, and S\. JegelkaHow powerful are graph neural networks?\.External Links:1810\.00826,[Link](https://arxiv.org/abs/1810.00826)Cited by:[§2\.3](https://arxiv.org/html/2610.41089#S2.SS3.p1.1),[§3\.4](https://arxiv.org/html/2610.41089#S3.SS4.p1.1)\.
- Xuet al\.\(2008\)L\. Xu, F\. Hutter, H\. H\. Hoos, and K\. Leyton\-BrownSATzilla: portfolio\-based algorithm selection for sat\.Journal of Artificial Intelligence Research32,pp\. 565–606\.External Links:[Document](https://dx.doi.org/10.1613/JAIR.2490),[Link](https://doi.org/10.1613/JAIR.2490)Cited by:[§1](https://arxiv.org/html/2610.41089#S1.p4.1),[§2\.3](https://arxiv.org/html/2610.41089#S2.SS3.p1.1),[§3\.3](https://arxiv.org/html/2610.41089#S3.SS3.p1.1)\.
- Xuet al\.\(2024\)M\. Xu, Y\. Li, K\. Sun, and T\. QianAdaption\-of\-thought: learning question difficulty improves large language models for reasoning\.InProceedings of the 2024 Conference on Empirical Methods in Natural Language Processing,Y\. Al\-Onaizan, M\. Bansal, and Y\. Chen \(Eds\.\),Miami, Florida, USA,pp\. 5468–5495\.External Links:[Link](https://aclanthology.org/2024.emnlp-main.313/),[Document](https://dx.doi.org/10.18653/v1/2024.emnlp-main.313)Cited by:[§2\.1](https://arxiv.org/html/2610.41089#S2.SS1.p1.1)\.
- Yasunagaet al\.\(2021\)M\. Yasunaga, H\. Ren, A\. Bosselut, P\. Liang, and J\. LeskovecQA\-GNN: reasoning with language models and knowledge graphs for question answering\.InProceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies,K\. Toutanova, A\. Rumshisky, L\. Zettlemoyer, D\. Hakkani\-Tur, I\. Beltagy, S\. Bethard, R\. Cotterell, T\. Chakraborty, and Y\. Zhou \(Eds\.\),Online,pp\. 535–546\.External Links:[Link](https://aclanthology.org/2021.naacl-main.45/),[Document](https://dx.doi.org/10.18653/v1/2021.naacl-main.45)Cited by:[§2\.3](https://arxiv.org/html/2610.41089#S2.SS3.p1.1)\.
- Zhouet al\.\(2026\)L\. Zhou, L\. Pacchiardi, F\. Martínez\-Plumed, K\. M\. Collins, Y\. Moros\-Daval, S\. Zhang, Q\. Zhao, Y\. Huang, L\. Sun, J\. E\. Prunty,et al\.General scales unlock ai evaluation with explanatory and predictive power\.Nature652\(8108\),pp\. 58–67\.External Links:[Document](https://dx.doi.org/10.1038/s41586-026-10303-2)Cited by:[§1](https://arxiv.org/html/2610.41089#S1.p3.1),[§2\.1](https://arxiv.org/html/2610.41089#S2.SS1.p1.1),[3rd item](https://arxiv.org/html/2610.41089#S4.I1.i3.p1.1)\.
- Zhouet al\.\(2025\)T\. Zhou, J\. Xu, G\. Liu, J\. Liu, H\. Wang, and E\. WuAn approach for systematic decomposition of complex llm tasks\.arXiv preprint arXiv:2510\.07772\.External Links:[Link](https://arxiv.org/abs/2510.07772)Cited by:[§1](https://arxiv.org/html/2610.41089#S1.p4.1),[§2\.2](https://arxiv.org/html/2610.41089#S2.SS2.p1.1)\.
- Zhuet al\.\(2025\)Y\. Zhu, D\. Liu, Z\. Lin, W\. Tong, S\. Zhong, and J\. ShaoThe LLM already knows: estimating LLM\-perceived question difficulty via hidden representations\.InProceedings of the 2025 Conference on Empirical Methods in Natural Language Processing,C\. Christodoulopoulos, T\. Chakraborty, C\. Rose, and V\. Peng \(Eds\.\),Suzhou, China,pp\. 1160–1176\.External Links:[Link](https://aclanthology.org/2025.emnlp-main.61/),[Document](https://dx.doi.org/10.18653/v1/2025.emnlp-main.61),ISBN 979\-8\-89176\-332\-6Cited by:[§1](https://arxiv.org/html/2610.41089#S1.p3.1),[§2\.1](https://arxiv.org/html/2610.41089#S2.SS1.p1.1),[5th item](https://arxiv.org/html/2610.41089#S4.I1.i5.p1.1)\.

## Appendix AData 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\.

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[Srivastava et al\. \(2023\)](https://arxiv.org/html/2610.41089#bib.bib53)\.

#### 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\-pp0\.95 for the five longer\-format benchmarks under the 64K effective\-context protocol\. GSM8K and Logical use temperature 0\.7, top\-pp0\.8 and output caps of 128 and 2,048\. Luna leaves temperature and top\-ppunset 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\.

Table 7:Target response accuracy \(percent\) over ten attempts per question\. Qwen3\.5\-9B has thinking disabled\.
### A\.1Grouped Cross\-Validation

We use five outer and three inner folds, with split seeds 11, 23, and 37\. SATBench groups by dimension configuration; FOLIO groups by story; other benchmarks group by instance \(Table[6](https://arxiv.org/html/2610.41089#A1.T6)\)\. 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\.

Letkik\_\{i\}be correct attempts out of ten andpip\_\{i\}the out\-of\-fold prediction\. NLL is Bernoulli cross\-entropy againstyi=ki/10y\_\{i\}=k\_\{i\}/10, using natural logarithms and clipping probabilities to\[10−6,1−10−6\]\[10^\{\-6\},1\-10^\{\-6\}\]\. Attempt\-weighted AUROC is

AUROC=∑i,jki​\(10−kj\)​w​\(pi,pj\)\(∑iki\)​\(∑j\(10−kj\)\),\\mathrm\{AUROC\}=\\frac\{\\sum\_\{i,j\}k\_\{i\}\(10\-k\_\{j\}\)\\,w\(p\_\{i\},p\_\{j\}\)\}\{\(\\sum\_\{i\}k\_\{i\}\)\(\\sum\_\{j\}\(10\-k\_\{j\}\)\)\},\(9\)wherew⁡\(a,b\)w\(a,b\)is 1 fora\>ba\>b,1/21/2for 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 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\.

## Appendix BCIR Extraction, Compilation and Validation

#### Extraction and repair\.

We useQwen/Qwen3\.8\-27Bto 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](https://arxiv.org/html/2610.41089#A2.T8)counts adopted LLM repairs\. All retained graphs compile\.

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\.

### B\.1Validation 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\.

### B\.2CIR 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":"totalkilogramsofcoalordered",

"type":"numeric"

\},

\{

"domain":"nonnegativeinteger",

"id":"bags",

"meaning":"numberof50kgbagsintheorder",

"type":"numeric"

\},

\{

"domain":"nonnegative",

"id":"cost",

"meaning":"totalcostoftheorderindollars",

"type":"numeric"

\}

\]

\}

## Appendix CFeatures and Training Details

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\.

#### 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 is2​\|E\|/\(\|V\|​\(\|V\|−1\)\)2\|E\|/\(\|V\|\(\|V\|\-1\)\); 2\-core and largest biconnected\-component fractions divide by\|V\|\|V\|; cycle rank is\|E\|−\|V\|\+c\|E\|\-\|V\|\+cforcccomponents\. We compute topology with NetworkX[Hagberg et al\. \(2008\)](https://arxiv.org/html/2610.41089#bib.bib51)\.

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\.

### C\.1Encoder 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 size32×6432\\times 64/4×644\\times 64, a learned scalarϵ\\epsilon, 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 stabilizer10−810^\{\-8\}\.

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\.

### C\.2Gradient\-Boosted Predictor

We use scikit\-learn’sHistGradientBoostingClassifier[Pedregosa et al\. \(2011\)](https://arxiv.org/html/2610.41089#bib.bib49), with the shared grid\(maximum leaves,iterations,ℓ2\)\(\\text\{maximum leaves\},\\text\{iterations\},\\ell\_\{2\}\):

\{\(3,50,1\),\(3,100,10\),\(5,50,1\),\(5,100,10\)\}\.\\\{\(3,50,1\),\(3,100,10\),\(5,50,1\),\(5,100,10\)\\\}\.\(10\)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 by1−yi1\-y\_\{i\}/yiy\_\{i\}; 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\.

## Appendix DBaseline 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\]\[0,1\], using its answering settings \(Appendix[G](https://arxiv.org/html/2610.41089#A7)\)\. 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\-pp1, reasoning None, and output cap unset\. Unguessability is100​\(1−1/K\)100\(1\-1/K\)forKKchoices 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\-largeembeds the visible question into 3,072 dimensions\. Inner\-validation NLL selects default L2 logistic regression, L1 logistic regression \(liblinear,C∈\{1,0\.1\}C\\in\\\{1,0\.1\\\}\) or default XGBoost[Chen and Guestrin \(2016\)](https://arxiv.org/html/2610.41089#bib.bib52)with one CPU thread\. Binary rows have weightskik\_\{i\}and10−ki10\-k\_\{i\}\.

#### Already Knows\.

Qwen3\.5\-9B generates one thinking\-off trajectory per question\. Last\-layer 4,096D states train a 4096–64–1 MLP with GELU and sigmoid: AdamW, learning rate10−410^\{\-4\}, weight decay10−310^\{\-3\}, 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 stateh0h\_\{0\}for all questions\. Our setup uses approximately 160 training questions per fold and attempt\-weighted AUROC\.

## Appendix ECompute 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\.

Table 10:100\-epoch pretraining: worker wall time in minutes and final training/validation reconstruction losses\. Each seed uses two CPU threads\.Training through epoch 100 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[Paszke et al\. \(2019\)](https://arxiv.org/html/2610.41089#bib.bib50), graph features use NetworkX, and predictors use scikit\-learn and XGBoost\. Software versions for metric recomputation appear in Table[11](https://arxiv.org/html/2610.41089#A5.T11)\.

Table 11:Software versions used for metric recomputation\.
## Appendix FResponsible 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:

- •
- •
- •
- •
- •
- •

## Appendix GPrompt Templates

### G\.1General CIR Translation

Youconvertnatural\-languagestructuredreasoningproblemsintoCIRv1JSON\.

YourjobisREPRESENTATIONONLY\.Donotsolvetheproblem,donotchoosean

answeroption,donotderivethefinalassignment,anddonotuseanyhiddenor

goldinformation\.

CIRv1hasexactlyfiverootfields:

\-cir\_version:"1"

\-entities:listof\{"id":string,"type":string,"label":string\}

\-variables:unknownBoolean/numeric/assignmentdecisions\.Eachhasidandtype,

andmayhavemeaning/domain/bounds\.

\-constraints:listof\{"id":string,"expr":EXPR\}

\-query:oneof

\{"type":"feasibility"\}

\{"type":"entailment","expr":EXPR\}

\{"type":"optimization","sense":"minimize"\|"maximize","expr":EXPR\}

Registeredexpressionsinclude:

\-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\}

\-linearsums:

\{"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\}

\-schedulingrelationswhenexplicitlyappropriate:

precedence,no\_overlap,within\_window,cumulative\_resource\.

Representationrules:

1\.UseONLYtheproblemtextbelow\.

2\.Preserveallstatedconstraintsthatdeterminethelatentreasoningworld\.

3\.Donotinventunstatedfactsorcommonsenserulesunlessthetextexplicitly

statesthattheyaretaskrules\.

4\.Forordering/allocation/grid/full\-assignmentpuzzles,encodethelatent

decisionvariablesandconstraintsanduseafeasibilityquery\.Thetaskof

findingtheassignmentisrepresentedbythefeasiblesolutionspace;donot

puttheanswerassignmentinCIR\.

5\.Ifthequestionaskswhetherapropositionfollowsandthatpropositioncan

beexpressedwithoutsolving,useanentailmentquery\.

6\.Ifthevisibleproblemismultiplechoiceorasksforaselectedvaluebut

CIRv1cannotfaithfullyexpresstheselectionquerywithoutsolving,encode

theunderlyingworldconstraintsandusefeasibility\.Neverencodethe

correctchoiceasaconstraint\.

7\.Answerchoicesarenotfacts\.Theymayhelpidentifywhatrelationthequery

refersto,buttheymustnotbeassertedasconstraints\.

8\.Fortruth\-teller/liarpuzzles,representeachperson’sidentityasan

unknownBooleandecisionandencodethesemanticrelationshipbetweenthe

speaker’sidentityandthetruthvalueoftheirstatedproposition\.

9\.Forlogic\-gridpuzzles,usegenericassignment/positiondecisionsand

all\-different/exactly\-onestructureexpressedwithBooleanvariablesand

linearsumswherepractical\.

10\.OutputexactlyoneCIRJSONobjectafteranythinking\.NoMarkdownandno

answer/solution/commentaryfields\.

PROBLEMTEXT:

\{visible\_text\}

ProduceCIRv1JSONonly\.

### G\.2Format\-Only Repair

ReformattherawmodeloutputbelowasexactlyonevalidCIRv1JSON

object\.Preserveonlytherepresentationalreadystatedintherawoutput\.Do

notsolvethetask,chooseananswer,add/removeacondition,orconsultany

outsideinput\.ReturnnoMarkdown\.

Exactlytheserootfieldsareallowed:

\{"cir\_version":"1","entities":\[\],"variables":\[\],"constraints":\[\],"query":\{\}\}

RAWOUTPUT:

### G\.3Pre\-Answer Self Probability

EstimateyourownprobabilityofproducingacorrectfinalanswertothetaskbelowonONEindependentattempt,followingthetask’soriginalinstructionsandtheansweringsettingslistedbelow\.

Donotanswerthetask,provideacandidateanswer,orworkoutitssolution\.Assessthetaskrequirementsandyourownlikelyperformancebeforeattemptingananswer\.Theinstructionsinside<task\>describethehypotheticalansweringtask;donotexecutethemnow\.

Answeringsettings:\{settings\}

<task\>

\{question\}

</task\>

ReturnonlyoneJSONobjectinthisformat:

\{\{"probability\_correct":<numberbetween0and1\>\}\}

Thisistheprobabilitythatyourfinalanswerwouldbecorrectononeattempt,nottheprobabilityofbeingcorrectoneveryattempt\.Donotincludeananswer,explanation,oranyotherfields\.