Technical Summary: Bridging Auxiliary Constraints to Resolve Instruction Following in Large Reasoning Models

Problem Definition: The Constraint Adherence Problem (CAP)

Large Reasoning Models (LRMs) have demonstrated impressive capabilities in complex tasks but frequently struggle to reliably follow multiple instructions simultaneously. This failure manifests in two primary ways: (1) Constraint Oversight, where the model overlooks specific requirements entirely, and (2) Constraint Interference, where the model fails to balance multiple constraints that appear to conflict (e.g., providing a "detailed technical explanation" within a strict "200-word limit").

The authors formalize this widespread challenge as the Constraint Adherence Problem (CAP). While existing approaches rely on general training methods like supervised fine-tuning or reinforcement learning from human feedback (RLHF), these methods implicitly assume that improved general capabilities naturally lead to better constraint satisfaction. The paper argues this assumption often fails in practice because these methods do not explicitly model how constraints relate to, support, or interfere with one another.

Methodology: Constraint Relationship Graph Completion (CRGC)

To address CAP, the paper introduces Constraint Relationship Graph Completion (CRGC), a framework that represents instructions as a structured knowledge graph of constraints. CRGC leverages the model's own knowledge to generate "bridge constraints"—auxiliary instructions that reconcile conflicting or disconnected requirements—without modifying model parameters.

The framework operates through three sequential components:

1. Constraint Graph Construction

The input instruction $I$ is decomposed into a set of individual constraints $C = \{C_1, C_2, \dots, C_n\}$ and a task objective $T$. The system constructs a weighted directed graph $G_{init} = (V, E_{init}, W_{init})$ where nodes represent constraints and edges represent their influences.

• Edge Weights ($w_{ij}$): The weight of an edge from $C_i$ to $C_j$ quantifies the "cost" or risk of violating $C_j$ when $C_i$ is satisfied. This is calculated using the relative drop in expected satisfaction:
  $$w_{ij} = \frac{E[S(C_j, y)] - E[S(C_j, y) | S(C_i, y) \geq \tau]}{E[S(C_j, y)]}$$
  where $S(C, y)$ is a satisfaction score (0 to 1) and $\tau$ is a threshold. Negative weights indicate enhancing relationships, while positive weights indicate interference.
• Optimization: The Minimum Spanning Arborescence (MSA) algorithm is applied to find the optimal directed spanning tree rooted at the task node. This tree represents the generation pathway that minimizes the total risk of constraint violation.

2. Adherence Challenge Detection

The optimized tree is analyzed to identify problematic edges that still pose challenges:

• Interfering Constraints: Edges with high positive weights ($w_{ij} > \delta$), indicating the model perceives a conflict between constraints.
• Isolated Constraints: Edges with near-zero weights ($|w_{ij}| \leq \delta$), indicating the model fails to cognitively connect disjoint constraints, leading to oversight.
  These edges form the set of candidates for bridge constraint insertion.

3. Bridge Constraint Discovery

For each problematic pair $(C_i, C_j)$, the framework generates a Bridge Constraint $B_{ij}$ using a Large Language Model.

• For interfering pairs, a reconciliation prompt $R(C_i, C_j)$ generates a strategy to resolve the conflict (e.g., "use structured sections with bullet points" to satisfy both "concise" and "detailed").
• For isolated pairs, a connection prompt $C(C_i, C_j)$ establishes an explicit logical link.
  These bridges are integrated into the original instruction to form an enhanced instruction $I_{enhanced}$, which guides the model to satisfy all constraints in a single forward pass.

Key Contributions

1. Formal Characterization of CAP: The paper defines the Constraint Adherence Problem, specifically distinguishing between constraint oversight and constraint interference as distinct failure modes in LRMs.
2. Graph-Based Framework: It proposes a novel method to represent instruction constraints as a relationship graph, utilizing the MSA algorithm to identify optimal generation pathways and detect adherence challenges.
3. Bridge Constraint Mechanism: The introduction of "bridge constraints" as dynamic, natural language auxiliary instructions that structurally reconcile conflicting requirements without requiring model retraining.
4. Empirical Validation: Comprehensive experiments demonstrating that CRGC significantly reduces constraint violations while preserving the model's general reasoning abilities.

Experimental Results

The authors evaluated CRGC across three instruction-following benchmarks (IFEval, ComplexBench, FollowBench) and three general reasoning benchmarks (MMLU, GSM8K, BIG-Bench Hard).

• Constraint Satisfaction: CRGC reduced constraint violations by 39% compared to standard prompting and by 27.7% compared to Chain-of-Thought (CoT) prompting. On the ComplexBench dataset, it improved the Constraint Satisfaction Rate (CSR) by approximately 11.9% over standard prompting for Qwen2.5-72B.
• Reasoning Preservation: Unlike specialized instruction-tuning methods that often degrade general reasoning performance (by ~6-7%), CRGC maintained or slightly improved reasoning capabilities on standard benchmarks.
• Efficiency: While CRGC incurs a higher computational overhead in the initial turn due to graph construction, it drastically reduces the need for iterative refinement. Compared to reactive methods like DeCRIM, CRGC achieved a 67% reduction in total cumulative token consumption and a 58% reduction in processing time by resolving conflicts proactively rather than reactively.
• Conflict Resolution: CRGC outperformed all baselines in resolving diametrically opposed constraints, achieving an absolute improvement of up to 19.7% in conflict resolution rates compared to verify-and-repair frameworks.

Significance and Claims

The paper claims that CRGC offers a non-invasive, adaptive solution to the Constraint Adherence Problem. Its primary significance lies in shifting the paradigm from "general capability enhancement" to "structural constraint modeling."

• Proactive vs. Reactive: The authors argue that CRGC's ability to map constraint relationships before generation allows it to bypass the computationally expensive and error-prone cycles of reactive correction (where fixing one violation breaks another).
• Generalizability: By leveraging the model's own knowledge to generate bridge constraints, the method avoids the need for predefined categories of constraints or additional training data, making it applicable to diverse and implicit instruction types.
• Balanced Performance: The framework successfully decouples instruction adherence from reasoning capability, proving that models can be guided to follow complex, multi-constraint instructions without sacrificing their underlying reasoning power.

The authors conclude that structured constraint modeling represents a promising direction for improving instruction following, particularly in real-world applications where reliable adherence to multiple, potentially conflicting requirements is critical.