acceptodds
Under review as a conference paper at ICLR 2027

GRACER: Graph Regulation and Adaptive Compression for Efficient LLM Reasoning

Abstract

Chain-of-thought reasoning improves large language models by making intermediate reasoning steps explicit. Recent methods organize intermediate reasoning into structured forms such as trees, graphs, and forests. However, these methods often produce verbose or inconsistent structures. To address this issue, we introduce GRACER, Graph-Regularized Adaptive Compression for Efficient Reasoning. GRACER first regularizes noisy dependency structures through role-constrained repair. A critic then estimates structural credit and downstream uncertainty over the dependency graph. These estimates guide greedy compression of redundant nodes under the information-bottleneck principle. Across six benchmarks and two backbone models, GRACER produces more compact reasoning graphs and improves accuracy. GRACER consistently outperforms AoT, the strongest baseline in our comparison. Average performance rises from 82.42% to 86.05% on DeepSeek-V3 and from 79.13% to 81.33% on GPT-4o-mini. Compared with AoT, GRACER reduces average token usage per instance from 26.48K to 23.21K and average LLM calls by 21.5%. Role-constrained repair also reduces structural error rates from 32% to 12%, supporting the effectiveness of graph regularization.

Primary area:
foundation or frontier models, including LLMs
Keywords:
large language models, chain-of-thought reasoning, structured reasoning, reasoning graphs

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_rzK1OpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces GRACER, Graph-Regularized Adaptive Compression for Efficient Reasoning, which first regularizes noisy dependency structures through role-constrained repair and then estimates structural credit and downstream uncertainty over the dependency graph. These estimates guide greedy compression of redundant nodes under the information-bottleneck principle. Across six benchmarks and two backbone models, GRACER produces more compact reasoning graphs and improves accuracy.

Critical strengths

The problem is relevant. Repairing and compressing the intermediate graph is a reasonable way to improve both efficiency and answer quality.

The evaluator does not require LLM calls.

GRACER outperforms AoT on all six benchmarks under both backbones.

Critical weaknesses

Structural credit is not answer-facing, and the worked example is internally inconsistent. In the worked example, the last row of A is zero. Therefore, the target node’s credit must satisfy I_8=(1-d)S_8. In Appendix C, d=0.85 and S_8=0.0574, indicating I_8=0.15 \times 0.0574=0.00861. However, the reported fixed-point vector gives I_8=0.0589.

The benchmark definitions and answer-processing rules are not clearly clarified. Please provide detailed experimental settings with dataset versions, splits, instance IDs, transformations, prompts, extraction rules, and metric aggregation. Label restricted subsets clearly in the main results.

The selection of hyperparameters is based on the evaluation sets. According to Appendix A.9 and B.2, the d and \lambda sweeps use “the same capped evaluation scope as the main efficiency analysis,” i.e., the evaluation instances themselves. The selected values reproduce the main result exactly (d = 0.85 produces 86.05, matching Table 1).

No comparison against the number of target-reaching paths, out-degree of descendants, or direct entropy of normalized w_p. Missing related work and baselines on efficient reasoning, such as prompting-based concise reasoning etc.

Questions for authors

Can you provide a reproducible computation of the case study, including the priors, the chain aggregation, and the action selection? How was credit computed at d = 1?

How does GRACER perform with repair, critic, and compression all removed? What does the ‘direct reasoning’ stage do?

Are hyperparameter-selection instances unrelated to the reported evaluation instances?

2 comments

Dear Reviewer rzK1,

We sincerely thank you for the constructive feedback, which has helped improve our paper. Below, we clarify the credit computation and evaluation protocol, address hyperparameter selection, and add structural controls and efficient-reasoning baselines.

W1 & Q1: Credit computation and reproducible case study

Structural credit is target-facing, not gold-answer-facing: it assesses node support for reaching the target without reference answers, correctness labels, or additional LLM calls.

Why I8=0.0589I_8=0.0589? Using (α,β,γ)=(0.5,0.3,0.2)(\alpha,\beta,\gamma)=(0.5,0.3,0.2), we normalize converged raw credit:

Ii=I~iconv∑jI~jconv.I_i=\frac{\widetilde I_i^{\mathrm{conv}}}{\sum_j\widetilde I_j^{\mathrm{conv}}}.

Thus, 0.05890.0589 is v8v_8's normalized rather than raw credit. Appendix C.1 summarizes the reproducible computation, including the prior, raw iterations, entropy, chain aggregation, and action selection.

Credit at d=1d=1. The prior vanishes, and propagation on a finite DAG yields zero raw mass. Our safeguard therefore sets Ii=1/NI_i=1/N (N=∣V∣N=|V|) to avoid zero path weights and denominators; we will document it explicitly.

 

W2: Benchmark protocol

Appendix A.9 now specifies versions, splits, indexed ranges, transformations, extraction, and aggregation. Following AoT, all methods use matched snapshots, wrappers, instances, and scoring. The main-table caption labels these subsets as restricted and matched; we will release the manifest, complete prompts, and evaluation code.

 

W3 & Q3: Hyperparameters and evaluation overlap

Reply to Q3. No—the sweeps reuse the main evaluation instances. The anchor (d,λlen)=(0.85,0.20)(d,\lambda_{\mathrm{len}})=(0.85,0.20) was fixed beforehand; neither instances nor preprocessing were selected from outcomes.

Rationale and sensitivity. We use conventional PageRank d=0.85d=0.85[1] and empirical λlen=0.20\lambda_{\mathrm{len}}=0.20, since information-bottleneck theory gives no universal coefficient.[2] One-at-a-time sweeps fix the other parameter, so d=0.85d=0.85 reproduces the main configuration. They show sensitivity, not held-out selection or global optimality.

[1] L. Page et al., "The PageRank Citation Ranking: Bringing Order to the Web," Stanford Technical Report 1999-66, 1999. [2] N. Tishby et al., "The Information Bottleneck Method," Allerton, 1999.

 

W4: Structural controls and efficient-reasoning baselines

Structural controls. Under DeepSeek-V3, we replace only HiH_i with normalized path count, aggregate descendant out-degree, or direct entropy of normalized path weights.

EstimatorMATHGSM8KBBHMMLU-CFHotpotQALongBenchAvg.
GRACER97.6097.7088.8082.6081.6068.0086.05
Path Count96.9096.4087.9079.6080.3066.5084.60
Descendant Out-degree96.8096.0087.2078.4079.2067.0084.10
Path-weight Entropy97.5097.3088.6082.1081.3065.0085.30

Path Count ignores route weights and composition; Descendant Out-degree captures branching but not complete target-reaching routes; and Path-weight Entropy uses complete paths and credit but remains length-sensitive. GRACER instead fits a distribution under credit-weighted structural-feature constraints, representing route diversity, relative credit, and path composition.

Efficient-reasoning baselines. Given the rebuttal timeline, we evaluate two representative prompting-based concise-reasoning baselines, CCoT and TALE-EP, under the same protocol, retaining AoT as the closest structured baseline.[3][4]

MethodCallsMATHGSM8KBBHMMLU-CFHotpotQALongBenchAvg.
CCoT1.0087.5094.7083.6075.6055.8057.7575.83
TALE-EP2.0091.2093.8082.6073.4070.1059.5078.43
AoT11.1195.9095.0086.0076.2076.4065.0082.42
GRACER8.7297.6097.7088.8082.6081.6068.0086.05

CCoT controls global length and TALE-EP assigns query-level budgets; neither uses graph dependencies to allocate local fidelity.

[3] S. Nayab et al., "Concise Thoughts: Impact of Output Length on LLM Reasoning and Cost," Information Sciences, 2026. [4] T. Han et al., "Token-Budget-Aware LLM Reasoning," Findings of ACL, 2025.

 

Q2: Removing all modules and direct reasoning

Removing all three components. This leaves AoT's decomposition-contraction pipeline without graph optimization and therefore corresponds to the reported AoT row.

Direct reasoning. Before graph decomposition, this inherited AoT branch applies standard CoT to the original question; its output joins the decomposition and contraction outputs in final selection. It is not a GRACER graph component.

Best regards,
The Authors

Dear Reviewer rzK1,

We sincerely appreciate your recognition of the value of our work! GRACER evaluates structural credit and downstream uncertainty without additional LLM calls, while its repair and compression modules directly address structural errors and redundancy in generated reasoning graphs. Therefore, it provides a practical post-processing approach for graph-structured reasoning that improves performance while reducing token usage; the underlying idea may also extend to tree-structured reasoning! We have also aimed to make the method, overview, and overall pipeline transparent and easy to follow, thereby addressing an underexplored gap in the post-processing of structured reasoning.

At the same time, we fully understand the concerns you raised. Some details—such as the worked example and benchmark protocol—were insufficiently explained or omitted from the appendix, and we sincerely apologize for the resulting confusion and concern. We have done our best to provide the requested details, although we cannot guarantee that every detail has been fully covered. So, don't be mean to tell us whether any issues remain unresolved after considering our rebuttal! Although the initial assessment was discouraging and we felt that some aspects of the work may not have been fully reflected, we fully respect your judgment and greatly value your feedback!

In the end, if our rebuttal resolves or alleviates your concerns, we would sincerely appreciate your reconsideration of the rating and the opportunity for our work to receive further consideration.

Best regards,
The Authors

Reviewer_G6fgOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper introduces GRACER, a method for improving the accuracy and efficiency of structured LLM reasoning. It represents intermediate reasoning as a dependency graph and repairs inconsistencies in node roles and dependencies before contraction. Reverse credit propagation and an entropy estimate over downstream paths guide which intermediate chains to retain, summarize, or remove. The compression rule uses a practical surrogate inspired by the information bottleneck principle. Experiments cover six reasoning benchmarks and two LLM backbones, including comparisons with structured reasoning methods, component ablations, and resource measurements.

Critical strengths
  1. The improvement over AoT remains when the two methods receive the same call allocation and use similar numbers of tokens. This supports the practical value of graph-guided revision beyond increasing the number of model calls. The consistent gains across the evaluated benchmarks and both backbones make the approach promising for improving reasoning efficiency.

  2. I appreciate the interventions examining which reasoning content is important to preserve. Removing high-credit nodes is more damaging than removing low-credit or randomly selected nodes, while compressing high-entropy chains is more damaging under length-matched conditions. These results help explain why the proposed signals may be useful for selecting where to compress a reasoning graph.

Critical weaknesses

The preservation of answer-critical information through repair and compression could be established more directly. The interventions support the usefulness of the structural scores, but do not directly measure whether the actual rewrites retain the premises and intermediate results needed downstream. AoT [1] includes an assessment of answer equivalence across state transitions, which offers a useful reference for evaluating GRACER's added operations. As acknowledged in Appendix D, structural consistency and final-answer accuracy do not fully capture semantic drift. This leaves some uncertainty about the fidelity side of the proposed compression–fidelity trade-off, an important aspect of the contribution despite the encouraging overall gains.

[1] Atom of Thoughts for Markov LLM Test-Time Scaling. NeurIPS, 2025.

Questions for authors

Could the authors discuss how the granularity and dependency structure of the initial decomposition affect GRACER's compression decisions? Since both credit and entropy depend on this graph, any observations about sensitivity to decomposition choices would help clarify when the structural scores reliably identify reasoning content that should be preserved.

2 comments

Dear Reviewer G6fg,

We sincerely thank you for recognizing the value of GRACER and for highlighting two important limitations! The first concerns semantic fidelity across graph transitions. The second concerns sensitivity to the initial decomposition. We address the former through a direct audit and clarify when our structural scores are reliable for the latter.

W1: Semantic fidelity of repair and compression

Mechanism. Repair is local and error-directed. It is instructed to preserve the original premises and intermediate results together with external dependencies. Compression replaces an eligible INTERMEDIATE chain with one summary node while preserving its core operation, downstream-required result, and interfaces. Although these constraints do not guarantee fidelity, they explicitly encourage it.

Direct audit. Following AoT,[1] an independent LLM judge receives the question, graph states before and after each operation, and their context; method names, gold answers, and final correctness are hidden. Faithfulness requires preservation of problem semantics and answer-critical information without unsupported or contradictory reasoning. For brevity, the core prompt excerpt is:

prompt = f"""
You are an independent auditor of reasoning-graph {transition_type}. ...
ORIGINAL QUESTION: {question}
OPTIONAL CONTEXT: {context}
GRAPH BEFORE MODIFICATION: {before_graph}
GRAPH AFTER MODIFICATION: {after_graph}
Evaluate:
1. Problem-semantic preservation: ...
2. Answer-critical information coverage: ...
3. Factual/logical consistency: ...
Label rules: ...
Return exactly one JSON object:
{{"label": "faithful | partially_faithful | unfaithful"}}
"""

The reported rate is the fraction of transitions assigned the discrete faithful label; no continuous confidence scores are averaged.

Repair fidelity.

MetricMATHGSM8KBBHMMLU-CFHotpotQALongBenchOverall
Audited transitions3301804404502201041,724
Faithful (%)99.09100.0099.3298.0099.5599.0499.01

Compression fidelity.

MetricMATHGSM8KBBHMMLU-CFHotpotQALongBenchOverall
Audited transitions1,0001,0001,0001,0001,0004005,400
Faithful (%)99.2099.5098.9098.0099.1099.2598.96

 

Q1: Sensitivity to decomposition granularity and dependencies

Decomposition granularity. An overly coarse decomposition may merge several operations, skip intermediate details, and hide critical subquestions or safe compression boundaries. An overly fine decomposition may introduce redundant nodes, extra paths, and noisy dependencies, thereby changing Credit, Entropy, and the available compression candidates.

Dependency structure. Edges determine reverse-credit propagation, downstream path sets, and chain eligibility. Missing or spurious edges can therefore change both structural scores and the selected action.

Reliable conditions. Bounded repair cannot guarantee correction of every severely incomplete or semantically corrupted decomposition. However, it receives the original question, optional context, current graph, and defect report. This context supports structural correction and the recovery of some omitted or inconsistent reasoning.

Overall, GRACER shows particular promise for difficult real-world and long-context reasoning problems. It first repairs the initial decomposition into a more coherent graph. It then evaluates fine-grained reasoning units, preserves essential details, and selectively compresses low-risk regions. The resulting graph is more compact and better supports downstream LLM reasoning!

[1] F. Teng et al., "Atom of Thoughts for Markov LLM Test-Time Scaling," NeurIPS, 2025.

Best regards,
The Authors

Thank you for the author's response. I will maintain my initial positive evaluation.

Reviewer_3j9YOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The authors proposed a method GRACER, which manages intermediate reasoning graphs within an AoT-style decomposition–contraction pipeline. It combines role-constrained repair, reverse dependency-credit propagation, maximum-entropy modeling of downstream paths, and selective compression using an information-bottleneck-inspired surrogate. Then, the authors conducted experiments across 6 benchmarks and 2 backbones to validate the effectiveness of this method.

Critical strengths

(1) The experiments are reasonable and convincing. In detail, the authors reported consistent metrics across 6 benchmarks and 2 backbones. The results support a benefit from graph-derived guidance beyond the revision-call budget.

(2) The ablations studies examine the effectiveness of each module of repair, credit, and entropy. They provide useful mechanism-oriented evidence beyond final task scores.

(3) The proposed solution is described clearly, and each design is reasonable. The sequence of repair, backward credit propagation, risk-sensitive local compression and structural revalidation is reasonably aligned with the dependency-management problem.

Critical weaknesses

(1) The correspondence between the stated method and the executed implementation is unclear. Appendix C reports d=0.85, S_8=0.0574, a zero final row of M^T, and I_8*=0.0589, whereas Equation (2) implies I_8=0.00861. Chain normalization and the complete action-threshold mapping are also insufficiently specified. These details determine which reasoning content is compressed. Exact pseudocode/configuration and a corrected example would help resolve the concern. The manuscript inconsistency is confirmed; its effect on the experiments remains unverified.

(2) The evaluation scope and statistical reporting limit assessment of experimental completeness. Appendices A.8–A.9 and B.2 do not clearly identify disjoint tuning and final-reporting instances. Figure 4 shows accuracy around 96%–97.6%, but its relationship to the stated six-benchmark sensitivity analysis and the reported default average of 86.05 is not explained. Table 11 also omits the retained matched-pair count and uncertainty estimates; matching chain length does not establish independence from other graph properties, as Appendix F.5 acknowledges. These issues limit assessment of independent evaluation and the stability and specificity of the entropy-based attribution. Exact split/sample definitions, clarification of the plotted scope and paired uncertainty estimates from existing outputs would help resolve the concern. The reporting limitations are confirmed; evaluation leakage and experimental invalidity have not been established.

Questions for authors

(1) How were scores normalized and combined, and what rules triggered rewriting? Please explain the discrepancy between Appendix C and Eq. (2), and how d=1 was handled in Table 5.

(2) Were separate examples used for tuning and evaluation? Please clarify the data and averaging used in Figure 4, the MATH filtering, the LongBench subset, and the BBH answer mapping.

(3) How many matched graphs/chains were included in Table 11? Did the High-H and Low-H groups have similar credit scores? Could you add confidence intervals for the paired comparisons?

1 comment

Dear Reviewer 3j9Y,

We sincerely thank you for recognizing GRACER's value and carefully examining its implementation and evaluation! We have updated the manuscript to address the worked example, evaluation scope, and entropy intervention.

W1 & Q1: Credit normalization, aggregation, and action mapping

Credit discrepancy. We apologize that the example mixed raw and policy-normalized credit. After convergence:

Ii=I~iconv∑jI~jconv,I8=0.0171430.291157=0.058878≈0.0589.I_i=\frac{\widetilde{I}_i^{\mathrm{conv}}}{\sum_j\widetilde{I}_j^{\mathrm{conv}}},\qquad I_8=\frac{0.017143}{0.291157}=0.058878\approx0.0589.

Here, I~8conv=(1−0.85)S8=0.017143\widetilde{I}_8^{\mathrm{conv}}=(1-0.85)S_8=0.017143, and the raw vector totals 0.2911570.291157. Equation (2) defines the raw recurrence, while policy scoring uses its normalized vector. Thus, the inconsistency was presentational, not experimental. Appendix C.1 reports the full trace.

Aggregation and actions. Rescaled Credit, Entropy, and length form node objectives averaged over each eligible INTERMEDIATE chain. Appendix A.8 specifies the action mapping and rewrite gate. Here, [v5,v6,v7][v_5,v_6,v_7] passes the gate and becomes one summary node; drop removes only standalone representations while retaining required content.

Credit at d=1d=1. The prior vanishes and propagation on a finite DAG yields zero raw mass. Our safeguard sets Ii=1/∣V∣I_i=1/|V| to avoid zero path weights and denominators (Appendix B.2).

 

W2 & Q2: Evaluation scope, Figure 4, and benchmark rules

Evaluation scope and aggregation. The dd sweep uses the main matched scope: the first 1,000 examples from five benchmarks and all 400 LongBench-MH examples. Its score is the unweighted six-benchmark mean. The anchor (0.85,0.20)(0.85,0.20) was fixed before the one-at-a-time sweeps; no instances or preprocessing were outcome-selected. These are sensitivity analyses, not held-out selection or evidence of global optimality. Appendix A.8 separately documents fixed action penalties.

Figure 4 reports MATH accuracy of 96.0--97.6 under the λ\lambda sweep, not the six-benchmark average of 86.0586.05. The revised caption and Appendix B.2 now state this scope.

Benchmark rules. Appendix A.9 and Table 5 specify snapshots, indexed intervals, transformations, extraction, and aggregation. MATH retains 2,957 integer/decimal-answer examples and evaluates [0,1000)[0,1000). LongBench-MH contains 200 MuSiQue and 200 2WikiMultiHopQA examples. BBH extracts one option letter and uses case-insensitive exact match after removing optional parentheses. All methods share instances and scoring.

 

Q3: Entropy intervention and uncertainty

Table 13 in the revision (Table 11 originally) reports the entropy intervention over 5,400 instances. It includes 1,157 matched graphs and 1,241 one-to-one High-HH/Low-HH chain pairs (2,482 chains), selected within the same graph and matched by length. High Entropy may coincide with high Credit, but neither signal alone determines compression: GRACER combines Credit, Entropy, and length. The signals are not necessarily monotonic because Credit measures target-facing support, whereas Entropy measures its downstream dispersion.

Paired confidence intervals. For this rebuttal, we newly extracted the matched pairs from the graph-level outputs and computed 95% confidence intervals. Each matched graph contributes one outcome after comparing High-HH and Low-HH removal; multiple chain pairs within a graph are aggregated first. We assign dg=+1d_g=+1 when Low-HH removal succeeds but High-HH removal fails, dg=−1d_g=-1 for the reverse, and dg=0d_g=0 when the outcomes agree. This gives 70 positive and 46 negative graph-level differences. For each benchmark, we report the normal-approximation 95% CI:

\bar d=\frac{1}{N_g}\sum_g d_g,\qquad \mathrm{CI}_{95\\%}=\bar d\pm1.96\frac{s_d}{\sqrt {N_g}}.

Drop: Low-HH −- High-HHMATHGSM8KBBHMMLU-CFHotpotQALongBench-MHOverall
Matched graphs220170230210235921,157
Accuracy difference0.91%1.76%3.04%1.43%2.55%3.26%2.16%
95% CI[-2.88%, 4.70%][-3.00%, 6.53%][-1.21%, 7.30%][-2.64%, 5.50%][-1.70%, 6.80%][-3.81%, 10.33%][0.19%, 4.13%]

Overall, Coarse decomposition may hide critical subquestions, while overly fine decomposition may add redundant nodes and noisy paths. GRACER repairs the structure, then uses Credit and Entropy to preserve important details and compress low-risk regions, benefiting difficult and long-context problems.

Best regards,
The Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.