Affirmed by published opinion. Judge Niemeyer wrote the opinion for the court, in which Judge Williams joined as to Parts I, II, IV, and V, and Judge Shedd joined as to Parts I, III, and V. Judge Williams wrote an opinion concurring in part and concurring in the judgment. Judge Shedd wrote a concurring opinion.
OPINION
NIEMEYER, Circuit Judge:Erskine Hartwell pleaded guilty, pursuant to a plea agreement dated April 27, 2000, to a one-count criminal information charging him with murder-for-hire resulting in death, in violation of 18 U.S.C. § 1958(a), a crime punishable by life imprisonment or death. Under the plea agreement, the government agreed not to seek the death penalty and to consider, “in its sole discretion,” filing a motion at a later time for a reduction in the sentence below the statutory minimum, and Hart-well agreed to cooperate fully, completely, and truthfully with the government in investigating criminal activity. If Hartwell did not ful-fill his obligations, the agreement provided that the government could “seek release from any or all of its obligations” under the agreement.
The district court sentenced Hartwell to life imprisonment, and a judgment on his conviction and sentence was entered August 18, 2000.
As Hartwell’s efforts to assist the government were still ongoing a year later, the government filed a motion under Federal Rule of Criminal Procedure 35(b) for a reduction of sentence on August 14, 2001, to toll the one-year time limit imposed by that rule. A year-and-a-half later, the government filed a memorandum at the direction of the district court, recommending that Hartwell’s sentence be reduced from life imprisonment to 38 years’ imprisonment despite the government’s concerns over Hartwell’s cooperation. Several months later, however, because of Hart-well’s ongoing and past lies and his lack of full disclosure, the government filed a motion to withdraw its motion for a reduction of sentence. Hartwell filed a motion for an evidentiary hearing to determine whether the government’s motion constituted a breach of the plea agreement.
By order dated January 14, 2004, the district court granted the government’s motion to withdraw its Rule 35(b) motion for reduction of sentence and denied Hart-well’s motion for an evidentiary hearing.
On appeal from that order, Hartwell contends that the district court never had subject-matter jurisdiction in this case because the government proceeded on an information instead of an indictment for a crime punishable by death. He also contends that the plea agreement, both in its original form and as modified by the parties during the course of his cooperation, did not authorize the government to withdraw its motion for a reduction of sentence. Finally, he contends that the district court abused its discretion in denying him an evidentiary hearing on whether the government breached the plea agreement.
For the reasons that follow, we conclude that we have jurisdiction- to hear Hart-well’s appeal and affirm the district court’s January 14, 2004 order.
*710I
For his participation in a conspiracy to kill a government witness in Westmore-land County, Virginia, which resulted in the death of Jaime Pereira, who was not the intended target, Hartwell pleaded guilty to a criminal information charging him with aiding and abetting murder for hire, in violation of 18 U.S.C. § 1958(a). That statute provides that when death results, the defendant is to be punished by either life imprisonment or death. To avoid the death penalty and to receive the possibility of an additional sentence reduction, Hartwell negotiated a plea agreement with the government, in which he agreed to provide “full, complete and truthful cooperation” with the government’s investigation of criminal activity. More particularly, Hartwell agreed:
— to waive indictment and plead guilty to a one-count criminal information;
— that the court had jurisdiction and authority to impose any sentence within the statutory maximum;
— that he could not withdraw his guilty plea based upon the sentence imposed;
— to waive his right to appeal “any sentence within the maximum provided in the statute(s) of conviction (or the manner in which that sentence was determined) on the grounds set forth in Title 18, United States Code section 3742 or on any ground whatever”;
— to cooperate fully, completely, and truthfully with the government and provide it all information that he knew regarding any criminal activity;-to testify truthfully and completely at any grand juries, trials, or other proceedings;
— to be reasonably available for debriefing and pre-trial conferences as the government might require;
— that if he failed “to fulfill completely all the obligations under this plea agreement, the United States may seek release from any or all its obligations under this plea agreement.”
The government agreed:
— not to seek the death penalty;
— not to prosecute the defendant further in the Eastern District of Virginia for the “specific conduct described in the information or statement of facts”;
— to recommend to the court that the sentence in this case run concurrently with any sentence that Hartwell received for crimes charged in the District of Maryland;
— that it reserved “its option to seek any departure from the applicable sentencing guidelines, pursuant to Section 5K of the Sentencing Guidelines and Policy Statements, or Rule 35(b) of the Federal Rules of Criminal Procedure, if in its sole discretion, the United States determines that such departure is appropriate.”
Hartwell was sentenced to life imprisonment and ordered to pay $5,320 in restitution to the family of Jaime Pereira, and judgment was entered on August 18, 2000. Hartwell did not appeal the judgment.
Hartwell provided information and testimony in other criminal investigations and trials. The government, however, became concerned about the completeness and truthfulness of his cooperation following his testimony during the trial of James McGill, Jr., in the District of Maryland. Hartwell told two FBI agents that he had committed perjury at the urging of an Assistant United States Attorney. He then told the Assistant United States Attorney that he had lied to the FBI agents because he was angry at some of the law enforcement officers involved in the case and that he had not in fact perjured himself. The government also learned that Hartwell withheld information from DEA *711agents about homicides in which he was involved.
As a result of these concerns, the government sent a letter to Hartwell’s counsel in January 2001, stating, “[W]e have concluded that Mr. Hartwell has violated his responsibilities under his plea agreement[ ].” The government stated, however, that because Hartwell accepted responsibility and because of the complexities of his cooperating in three different jurisdictions, it would “continue to allow Mr. Hart-well to cooperate in his efforts to merit a sentence reduction motion.” If Hartwell agreed to and satisfied specified conditions, the government would “continue to consider him for a sentence reduction at the appropriate time” (emphasis added). These conditions included successfully completing a polygraph examination; paying his restitution obligation in full by May 31, 2001; stipulating to his false statements in the McGill prosecution; and cooperating fully and truthfully with the government. Both Hartwell and his counsel signed the letter on March 14, 2001, agreeing to the conditions.
On August 14, 2001, while Hartwell’s assistance was ongoing, the government filed a motion for a reduction of Hartwell’s sentence under Federal Rule of Criminal Procedure 35(b). The motion stated that since the defendant was “in the midst of cooperating,” it was filed only to toll the one-year time limitation imposed by Rule 35(b). The government asked the court to delay ruling on the motion until the defendant had fulfilled his responsibilities. Hartwell consented to the delay and agreed that “if the defendant fails to fulfill his responsibilities to the Government, the Government may withdraw this motion without objection by the defendant.”
Approximately a year-and-a-half later, the district court, sua sponte, ordered the government to file its memorandum in support of its Rule 35(b) motion, which the government did on March 10, 2003. In addition to detailing the nature and value of Hartwell’s cooperation, the government also outlined problems with his cooperation, including the McGill incident. The government also stated that Hartwell had not paid restitution to Pereira’s family. In a footnote to the motion, the government stated:
The Government considers defendant’s anticipated truthful testimony against [B.N.] as the principal basis for the filing of this motion. If, for any reason, defendant fails to provide truthful testimony during the [B.N.] prosecution, the Government will take the position that defendant has engaged in a material breach of his plea agreement and his commitment to provide substantial assistance to the Government.
The government concluded its motion by recommending that Hartwell’s sentence be reduced from life imprisonment to 38 years’ imprisonment.
A few months later, in June 2003, Hart-well filed a motion for an evidentiary hearing, alleging that the government had breached the plea agreement. He attached an affidavit stating, “On or about Feb[r]uary 25, 2000 AUSA David Nova[k] from Virginia entered an agreement and promised [defendant] and previous counsel William Purpura Esq, that after receiving a life sentence he was going to reduce [defendant’s] sentence to 18 years on a 35(b) motion.”
The government thereupon filed a motion to withdraw its Rule 35(b) motion. The government stated that Hartwell’s affidavit was false and that no one had ever promised Hartwell a specific sentence or that he would receive a Rule 35(b) reduction at all. Because of this “latest act of untruthfulness,” the government no longer believed that Hartwell deserved a sentence reduction.
*712Hartwell promptly filed a statement and motion to strike his own affidavit, admitting that AUSA Novak did not make the promises that Hartwell stated in his affidavit.
The court heard argument on the government’s motion to withdraw its Rule 35(b) motion, and on January 14, 2004, it granted the government’s motion and denied Hartwell’s motion for an evidentiary hearing. United States v. Hartwell, 302 F.Supp.2d 609 (E.D.Va.2004).
Hartwell filed this appeal, contending (1) that the district court lacked subject-matter jurisdiction to convict and sentence him because he was charged by an information and not an indictment; (2) that the district court erred in permitting the government to withdraw its Rule 35(b) motion; and (3) that the district court abused its discretion in denying him an evidentiary hearing on whether the government breached the plea agreement.
II
At the outset, we address the government’s contention that Hartwell may not appeal the district court’s order granting its motion to withdraw its Rule 35(b) motion, citing United States v. Pridgen, 64 F.3d 147 (4th Cir.1995), and that therefore we must dismiss Hartwell’s appeal. In Pridgen, we held that appeals from rulings on Rule 35(b) motions are governed by 18 U.S.C. § 3742, not 28 U.S.C. § 1291, and that the district court’s exercise of discretion in denying the government’s motion for a sentence reduction does not fulfill the condition for a defendant’s appeal under that section, so long as the district court did not misconstrue its authority. See Pridgen, 64 F.3d at 149; 18 U.S.C. § 3742(a)(1) (authorizing appeal if sentence was imposed in violation of law). We did, however, find that the defendant could appeal the district court’s refusal to conduct an evidentiary hearing because such an appeal was essentially a claim that the sentence was imposed in violation of law. See Pridgen, 64 F.3d at 150. In response to Hartwell’s invocation of 28 U.S.C. § 1291 (authorizing appeals from “all final decisions of the district courts”), the government argues that Hartwell failed to file his appeal within ten days of the judgment in this case, which was entered on August 18, 2000.
Generally, it is 28 U.S.C. § 1291 that gives the Courts of Appeals jurisdiction of appeals from “all final decisions of the district courts.” A judgment in a criminal case becomes final after conviction and imposition of sentence. United States v. Bundy, 392 F.3d 641, 644 n. 1 (4th Cir.2004) (citing Flanagan v. United States, 465 U.S. 259, 263, 104 S.Ct. 1051, 79 L.Ed.2d 288 (1984)). Other orders in criminal cases are final and therefore ap-pealable when there is nothing further to be done. See Catlin v. United States, 324 U.S. 229, 233, 65 S.Ct. 631, 89 L.Ed. 911 (1945). Any appeal of a criminal judgment or other final criminal order must be filed within ten days after “the entry of either the judgment or the order being appealed.” See Fed. RApp. P. 4(b)(1)(A)(i). But parties to a criminal case may appeal otherwise final sentences, even after the time for appealing has elapsed, in the limited circumstances provided by 18 U.S.C. § 3742. See also Pridgen, 64 F.3d at 148-49. Section 3742 provides in relevant part that “[a] defendant may file a notice of appeal in the district court for review of an otherwise final sentence if the sentence was imposed in violation of law.” 18 U.S.C. § 3742(a)(1) (emphasis added).
Virtually every circuit to have considered the question has ruled that a criminal defendant may not invoke 28 U.S.C. § 1291 to circumvent the conditions imposed by 18 U.S.C. § 3742 for appealing otherwise final sentences. See United *713States v. Doe, 374 F.3d 851, 853 (9th Cir.2004); United States v. Moran, 325 F.3d 790, 792 (6th Cir.2003); United States v. McDowell, 117 F.3d 974, 977 (7th Cir.1997); United States v. McMillan, 106 F.3d 322, 324 n. 4 (10th Cir.1997); United States v. Doe, 93 F.3d 67, 68 (2d Cir.1996); United States v. Arishi, 54 F.3d 596, 598-99 (9th Cir.1995); but see United States v. McAndrews, 12 F.3d 273 (1st Cir.1993). In Pridgen, we explicitly rejected the McAndrews holding. Pridgen, 64 F.3d at 149.
Thus, if Hartwell is appealing an otherwise final sentence, his appeal must be authorized by § 3742(a) or not at all, and to rely on that section, he must be alleging that his otherwise final sentence was imposed in violation of law. He may make that claim in appealing a ruling on a Rule 35(b) motion.
Hartwell contends that, because the government was not legally entitled to withdraw its Rule 35(b) motion, the district court failed to consider a sentence reduction as required and therefore that the sentence was illegal, thus satisfying the condition of § 3742(a) that his sentence be imposed in violation of law. But he also contends that when the government failed to seek a sentence reduction under Rule 35(b), it breached the plea agreement. Accordingly, he also requests in essence that the district court specifically enforce the plea agreement as written. Finally, Hart-well contends that the district court did not have subject-matter jurisdiction to consider the entire case, including a Rule 35(b) motion or its withdrawal' — -a contention that we describe and address in Part III, below.
In the unique circumstances of this case, we conclude that we have authority to hear this appeal under either 18 U.S.C. § 3742(a) or 28 U.S.C. § 1291(a). To the extent that Hartwell contends that the district court erred in construing the plea agreement so as to permit the government to withdraw its earlier 35(b) motion, thus precluding a sentence reduction, he is challenging the legal foundation of his sentence. See United States v. Khoury, 62 F.3d 1138 (9th Cir.1995) (reviewing the government’s withdrawal of a § 5K1.1 motion for substantial assistance); Bischel v. United States, 32 F.3d 259 (7th Cir.1994) (reviewing government’s withdrawal of a Rule 35(b) motion); cf. United States v. Barnette, 427 F.3d 259 (4th Cir.2005) (reviewing extent of district court’s departure under a U.S.S.G. § 5K1.1 motion where defendant claimed court impermissibly considered possibility of future departure under Rule 35(b)); United States v. Wilson, 390 F.3d 1003 (7th Cir.2004) (reviewing government’s failure to file a Rule 35(b) motion); United States v. Buchanan, 213 F.3d 302 (6th Cir.2000) (same). And a challenge to the legal foundation of an otherwise final sentence may be appealed under 18 U.S.C. § 3742(a).
In addition, to the extent that Hartwell claims that the government breached the plea agreement, he is not challenging his sentence directly, but the district court’s refusal to require the government to comply with the agreement. Such an argument is essentially a request for a specific performance of the plea agreement. Thus, when the district court granted the government’s motion to withdraw its rule 35(b) motion, it entered a final order rejecting Hartwell’s specific performance claim, which is appealable under 28 U.S.C. § 1291. See United States v. Alexander, 869 F.2d 91 (2d Cir.1989); United States v. Worley, No. 04-30491, 145 Fed.Appx. 593 (9th Cir.2005); cf. Wilson, 390 F.3d 1003 (reviewing, without citation for court’s jurisdiction, defendant’s contention that government failed to “carry[ ] out its part of the [plea] bargain”).
Finally, because Hartwell contends that the district court did not have subject-*714matter jurisdiction to consider a Rule 35(b) motion or its withdrawal, we conclude that we have authority to hear this appeal to determine the district court’s jurisdiction. Cf United States v. Carey, 120 F.3d 509 (4th Cir.1997) (affirming the district court’s holding that a late-filed Rule 35(b) motion was beyond its jurisdiction).
At bottom, for any one of the grounds stated, we conclude that the government’s request that we dismiss this appeal must be denied.
Ill
Hartwell contends that the district court never had subject-matter jurisdiction in this case to accept his guilty plea or to sentence him because he was charged by an information, not an indictment, with an offense that potentially carried the death penalty. He argues that the right to be prosecuted on an indictment for a crime punishable by death may not be waived, citing Smith v. United States, 360 U.S. 1, 10, 79 S.Ct. 991, 3 L.Ed.2d 1041 (1959) (ruling that the information to which the defendant pleaded guilty “did not confer power on the convicting court to hear the case”), and Federal Rule of Criminal Procedure 7 (requiring an indictment to prosecute an offense punishable by death or by imprisonment for more than one year and authorizing waiver of an indictment only for offenses punishable by imprisonment for more than one year — not for offenses punishable by death). This necessarily includes a claim that the district court did not have jurisdiction to consider the Rule 35(b) motion. If the district court lacked subject-matter jurisdiction, it never had the power to consider any part of the case, including motions to correct or reduce the sentence.
The government contends that Hart-well’s conviction and sentence became final in August 2000 and that, at this late date, Hartwell may not challenge the jurisdiction of his conviction or sentence by appeal because the time for appeal has long passed and such time limits are “jurisdictional.” United States v. Robinson, 361 U.S. 220, 229, 80 S.Ct. 282, 4 L.Ed.2d 259 (1960); see also Browder v. Dir., Dep’t of Corrections, 434 U.S. 257, 264, 98 S.Ct. 556, 54 L.Ed.2d 521 (1978) (noting that the purpose of the jurisdictional time limit for appeal is “to set a definite point of time when litigation shall be at an end”) (quoting Motton Steamboat Co. v. Murphy, 319 U.S. 412, 415, 63 S.Ct. 1126, 87 L.Ed. 1483 (1943)). The government argues alternatively that even though a challenge to subject-matter jurisdiction can be made at any time, Smith did not establish a rule of subject-matter jurisdiction. The government maintains further that even if it did, the “meaning of jurisdiction has changed in the intervening 46 years since the Supreme Court decided Smith.” See United States v. Cotton, 535 U.S. 625, 630, 122 S.Ct. 1781, 152 L.Ed.2d 860 (2002) (noting that an earlier Court decision’s elastic concept of jurisdiction is not what the term “jurisdiction” means today — “the courts’ statutory or constitutional power to adjudicate a case” — and holding that “defects in an indictment do not deprive a court of its power to adjudicate a case” (emphasis added)).
Initially, we note our agreement with the government’s position that judicial policy strongly favors that convictions and sentences become final.1 Any challenges *715to a criminal judgment after the appellate process is complete therefore may generally be brought only pursuant to a specific authorization for collateral review, such as 28 U.S.C. § 2255. But when a party suggests the absence of subject-matter jurisdiction, even at this late stage of a case, the party questions not only the original conviction, but the power to sentence and the power to correct or reduce the sentence under Rule 35(b), and therefore we must address it. See generally Cotton, 535 U.S. at 630, 122 S.Ct. 1781; Steel Co. v. Citizens for Better Env’t, 523 U.S. 83, 89, 118 S.Ct. 1003, 140 L.Ed.2d 210 (1998). This is because subject-matter jurisdiction can “never be forfeited or waived”; “it involves a court’s power to hear a case.” Cotton, 535 U.S. at 630, 122 S.Ct. 1781. And any action by a court without subject-matter jurisdiction is “ultra vires” and therefore void. Ruhrgas AG v. Marathon Oil Co., 526 U.S. 574, 583, 119 S.Ct. 1563, 143 L.Ed.2d 760 (1999) (quoting Steel Co., 523 U.S. at 101-02, 118 S.Ct. 1003).
To support his position that the district court did not have subject-matter jurisdiction to consider the Rule 35(b) motions, Hartwell points only to the decision in Smith v. United States, 360 U.S. 1, 79 S.Ct. 991, 3 L.Ed.2d 1041, and to Rule 7. In Smith, the defendant, Smith, was charged with kidnapping, which at the time carried the possibility of the death penalty if the victim was harmed. The information to which Smith pleaded guilty did not state whether the victim had been harmed, and the government did not explicitly disavow the intention to seek the death penalty. In what the Supreme Court described as “precipitous and telescoped proceedings,” 360 U.S. at 4, 79 S.Ct. 991, Smith was interrogated at length without counsel, after which the government agents had an ex parte conversation with the judge regarding the case. A “stilted and formal colloquy” ensued, during which Smith waived counsel, waived the indictment, waived venue, and pleaded guilty to an information. Id. at 3, 79 S.Ct. 991. Immediately after conviction and only three days after arrest, Smith was sentenced to 30 years’ imprisonment.
Obviously troubled by the “summary treatment” of the defendant, id. at 9, 79 S.Ct. 991, the Court held that Federal Rule of Criminal Procedure 7 did not permit Smith to waive indictment. The critical basis of this holding was that the information against Smith and his guilty plea did not eliminate the capital element of the crime:
[Wjhen the offense as charged is sufficiently broad to justify a capital verdict, *716the trial must proceed on that basis, even though the evidence later establishes that such a verdict cannot be sustained because the victim was released unharmed. It is neither procedurally correct nor practical to await the conclusion of the evidence to determine whether the accused is being prosecuted for a capital offense.
Id. at 8, 79 S.Ct. 991. The Court concluded, without further explanation: “Under our view of Rule 7(a), the United States Attorney did not have authority to file an information in this case and the waivers made by petitioner were not binding and did not confer power on the convicting court to hear the case.” Id. at 10, 79 S.Ct. 991 (emphasis added).
Hartwell argues that this language in Smith requires the conclusion that the failure to obtain an indictment to prosecute a capital case strips the district court of subject-matter jurisdiction. We disagree. A careful reading of Smith and consideration of how that decision has been understood subsequently by the Supreme Court reveal that the Court in Smith was speaking of some authorization other than subject-matter jurisdiction.
Subject-matter jurisdiction (in the sense of judicial power) over federal criminal prosecutions is conferred on district courts by 18 U.S.C. § 3231. As the Seventh Circuit has noted,
Subject-matter jurisdiction in every federal criminal prosecution comes from 18 U.S.C. § 3231, and there can be no doubt that Article III permits Congress to assign federal criminal prosecutions to federal courts. That’s the beginning and the end of the “jurisdictional” inquiry.
Hugi v. United States, 164 F.3d 378, 380 (7th Cir.1999); see also United States v. Titterington, 374 F.3d 453, 459 (6th Cir.2004); United States v. White Horse, 316 F.3d 769, 772 (8th Cir.2003); United States v. Jacquez-Beltran, 326 F.3d 661, 662 (5th Cir.2003); Alikhani v. United States, 200 F.3d 732, 734-35 (11th Cir.2000).
While the language in Smith on which Hartwell relies — that the defendant’s waivers “did not confer power on the convicting court to hear the case” (emphasis added)— might suggest that the Smith Court was addressing subject-matter jurisdiction and thus denying district courts subject-matter jurisdiction over federal capital criminal cases in which an indictment was not used, the Supreme Court’s recent discussion in Cotton would seem to preclude that conclusion. In Cotton, the Court overruled Ex Parte Bain, 121 U.S. 1, 7 S.Ct. 781, 30 L.Ed. 849 (1887), which held that defects in an indictment deprive the district court of jurisdiction. As the Cotton Court stated:
Bain, however, is a product of an era in which this Court’s authority to review criminal convictions was greatly circumscribed. At the time it was decided, a defendant could not obtain direct review of his criminal conviction in the Supreme Court. The Court’s authority to issue a writ of habeas corpus was limited to cases in which the convicting court had no jurisdiction to render the judgment which it gave. In 1887, therefore, this Court could examine constitutional errors in a criminal trial only on a writ of habeas corpus, and only then if it deemed the error jurisdictional. The Court’s desire to correct obvious constitutional violations led to a somewhat expansive notion of jurisdiction, which was more of a fiction than anything else. Bain’s elastic concept of jurisdiction is not what the term “jurisdiction” means today, i.e., the courts’ statutory or constitutional power to adjudicate the case. This latter concept of subject-matter jurisdiction, because it involves a court’s power to hear a case, can never be *717forfeited or waived. Consequently, defects in subject-matter jurisdiction require correction regardless of whether the error was raised in district court. In contrast, the grand jury right can be waived.
Post-Bain cases confirm that defects in an indictment do not deprive a court of its power to adjudicate a case.
Cotton, 535 U.S. at 629-30, 122 S.Ct. 1781 (emphases added) (internal quotation marks and citations omitted). The Supreme Court, citing Smith in support of the proposition that the grand jury right, because waivable, does not involve subject-matter jurisdiction, stated plainly that “a district court ‘has jurisdiction of all crimes cognizable under the authority of the United States,’ ” id. at 631, 122 S.Ct. 1781 (quoting Lamar v. United States, 240 U.S. 60, 65, 36 S.Ct. 255, 60 L.Ed. 526 (1916) (Holmes, J.)).
The Supreme Court again elaborated on the confusion engendered by an imprecise use of the term “subject-matter jurisdiction” in Kontrick v. Ryan, 540 U.S. 443, 124 S.Ct. 906, 157 L.Ed.2d 867 (2004). There, the Court noted that only Congress may alter a district court’s subject-matter jurisdiction and that court-prescribed rules of practice and procedure neither create nor withdraw jurisdiction. 540 U.S. at 452, 124 S.Ct. 906. Such rules “merely prescribe the method by which the jurisdiction granted the courts by Congress is to be exercised.” Id. at 454, 124 S.Ct. 906 (emphasis added). The Court then exhorted, “Clarity would be facilitated if courts and litigants used the label ‘jurisdictional’ not for claim-processing rules, but only for prescriptions delineating the classes of cases ... and the persons ... falling within the court’s adjudicatory authority.” Id. at 455, 124 S.Ct. 906. Subject-matter jurisdiction cannot be altered on the basis of the parties’ litigation conduct. “[A] claim-processing rule, on the other hand, even if unalterable on a party’s application, can nonetheless be forfeited if the party asserting the rule waits too long to raise the point.” Id. at 456,124 S.Ct. 906 (emphasis added).
Rule 7 is just such a claim-processing rule. It describes the process by which a defendant must be charged in order to comply with the Fifth Amendment requirement that “[n]o person shall be held to answer for a capital, or otherwise infamous crime, unless on a presentment or indictment of a Grand Jury,” and the process by which a defendant may waive the protections of that Amendment. Although Rule 7 does not permit a defendant charged with a capital crime to waive indictment, it does not follow that noncompliance is a defect of subject-matter jurisdiction. The district court’s jurisdiction is conferred by 18 U.S.C. § 3231 and may not be affected by the litigation conduct of the parties. Thus, if permitting Hartwell to be charged by information were error, it was not an error that denied the district court the power to adjudicate the federal criminal prosecution.
We conclude that the district court had subject-matter jurisdiction to consider the government’s Rule 35(b) motion and to consider the government’s motion to withdraw that motion.
IV
We now consider the district court’s application of the plea agreement entered into by the parties. Hartwell contends that the district court erred in granting the government’s motion to withdraw its Rule 35(b) motion because, under the plea agreement, the government did not retain the discretion “to withdraw a previously filed sentence-reduction motion.... [A]bsent a provision in the plea agreement governing such a withdrawal, the govern*718ment was precluded from withdrawing its motion.” He reasons:
[Paragraph ten of the agreement specifically states that once the government “determines that such a departure is appropriate,” the departure motion will be filed. Once that determination was made, the government had an obligation to proceed with the motion, absent language in the agreement to the contrary. It did, in fact, file the motion. Because there was no language in the contract to the contrary, the government should not have been allowed to withdraw its motion.
Hartwell argues alternatively that if the government did retain discretion to withdraw its Rule 35(b) motion, the memorandum that the government filed on March 10, 2003, in support of its Rule 35(b) motion modified the government’s discretion and limited its right to withdraw the Rule 35(b) motion to the circumstances in which Hartwell failed to provide truthful testimony in the B.N. trial referred to in footnote 1 of the memorandum. Hartwell also argues that the government acted in bad faith in withdrawing its Rule 35(b) motion because the “government’s rationale for withdrawal rested on a relatively insignificant happening.”
The government contends that the plea agreement gave it “sole discretion” to decide whether to file a Rule 35(b) motion, and that its motion to withdraw the 35(b) motion was simply part of that discretion. It also argues that the May 10, 2003 memorandum that it filed did not constitute a new agreement, but was a continuation of the original plea agreement by the enumeration of specific instances of cooperation required of Hartwell.2
We conclude that the language giving the government “sole discretion” to file a Rule 35(b) motion also includes the discretion to file a motion to withdraw it. This was explicitly understood by the parties when the government initially filed the motion in August 2001. Because Hartwell was then in the midst of cooperating, the parties asked the court to delay ruling on the motion, and the government reserved its right to withdraw the motion. Indeed, Hartwell’s attorney agreed that “if the defendant fails to fulfill his responsibilities to the Government, the Government may withdraw this motion without objection by the defendant.”
This understanding was consistent with the specific purpose of the agreement in this case. Because the motion had to be filed within one year of the sentencing and Hartwell had not yet finished cooperating, the parties agreed that the motion was a “placeholder,” intended to preserve the government’s ability to seek a sentence reduction for Hartwell after he completed his cooperation and after the government was able to evaluate his assistance and provide full information to the district court.
We conclude additionally that the government did not relinquish its discretion in *719whole or in part when it imposed new conditions on Hartwell in view of deficiencies in his cooperation. The supplemental agreement in the March 14, 2001 letter signed by the parties did not modify this aspect of the agreement. That letter agreement was entered into after problems with Hartwell’s cooperation had come to light. It was executed to reinforce the original understanding that Hartwell must still cooperate fully and truthfully, but with additional conditions, and that the government would still “consider him for a sentence reduction motion at the appropriate time” (emphasis added).
Likewise, in the government’s March 10, 2003 memorandum in support of its Rule 35(b) motion, on which Hartwell relies, there is no language to suggest a relinquishment of the government’s discretion. The footnote relied on by Hartwell simply recites that the “principal” reason for the government’s willingness to keep open its consideration of a motion for sentence reduction was Hartwell’s “anticipated truthful testimony against [B.N.].” Moreover, the footnote does not state that it is the only reason or basis for the motion; the use of the word “principal” implies the existence of other reasons or bases. The footnote also states that if Hartwell fails to provide truthful testimony, the government “will take the position that [he] has engaged in a material breach of his plea agreement and his commitment to provide substantial assistance to the Government.” This language, however, does not limit the government’s options. It simply identifies one particular event that would qualify as a breach, not exclusive of other such events.
Finally, we are not persuaded by Hart-well’s argument that the incident prompting the government to withdraw its motion for reduction of sentence was an “insignificant happening” that evidences a lack of good faith on the part of the government. The government took Hartwell’s June 6, 2003 affidavit (relating a promise made to him of an 18-year sentence) as an unacceptable reoccurrence of his earlier conceded perjury. The government also recognized that this second serious incident of perjury substantially undercut the government’s ability to use Hartwell as a witness in the future. Hartwell had already claimed to have committed perjury in the McGill case in the District of Maryland and then recanted that claim. Thus, when he filed the false affidavit in 2003, stating that the government had promised him an 18-year sentence, and recanted, he added to and thus made especially significant his history of making false statements. The government has an obligation to ensure that cooperating witnesses testify truthfully, and it reasonably concluded that it could no longer trust Hartwell to be truthful. Moreover, with two admittedly false statements and recantations, Hartwell created about himself excellent fodder for cross-examination and impeachment in any future prosecution in which he might be used by the government. A defense attorney could argue that these two examples indicate that Hartwell is willing to say anything, even lie under oath to the court, in order to get a lower sentence. If Hart-well’s “insignificant happening” did not destroy his credibility altogether, it certainly weakened it to the point that the government acted well within its discretion in deciding that Hartwell no longer was satisfactorily fulfilling his plea-agreement obligations.
In short, we conclude that in this case the government reserved to itself the sole discretion to file a motion under Rule 35(b) for a sentence reduction; that this discretion included the right to withdraw that motion for Hartwell’s failure to cooperate; and that the government never relinquished this discretion. Moreover, there is no evidence that the government acted *720in bad faith or for improper motives. The government simply concluded that Hart-well had told one lie too many.
V
For these same reasons, we conclude that the district court did not abuse its discretion in denying Hartwell an eviden-tiary hearing on his claim that the government breached the plea agreement.
* * *
For the reasons given, the district court’s January 14, 2004 order is
AFFIRMED.
. In her concurring opinion, Judge Williams concludes that Hartwell’s time for challenging the district court’s subject-matter jurisdiction "has come and gone” and we must now treat his challenge to the government’s motion to withdraw its Rule 35(b) motion as if Hartwell’s conviction and sentence were validly entered. See post at 724.
This conclusion seems inconsistent with the Supreme Court’s jurisprudence establishing that a court’s "power to hear a case ... can *715never be forfeited or waived.” Cotton, 535 U.S. at 630, 122 S.Ct. 1781. The Court has expressly held that this principle extends even beyond the entry of judgment: "The objection that a federal court lacks subject-matter jurisdiction ... may be raised by a party, or by a court on its own initiative, at any stage in the litigation, even after trial and the entry of judgment.” Arbaugh v.Y & H Corp., - U.S. -, -, 126 S.Ct. 1235, 1240, 163 L.Ed.2d 1097 (2006); see also Caterpillar, Inc. v. Lewis, 519 U.S. 61, 76-77, 117 S.Ct. 467, 136 L.Ed.2d 437 (1996). These principles are grounded in the fact that subject-matter jurisdiction is a question of judicial power, and for a court to act " 'when it has no jurisdiction to do so ... is ... for a court to act ultra vires.' " Ruhrgas AG v. Marathon Oil Co., 526 U.S. 574, 583, 119 S.Ct. 1563, 143 L.Ed.2d 760 (1999) (second omission in original) (quoting Steel Co., 523 U.S. at 101-02, 118 S.Ct. 1003).
Thus, it appears that Judge Williams is arguing that even if a conviction and sentence were entered ultra vires and were therefore void, we should nonetheless let stand a ruling on a Rule 35(b) motion to decrease or leave the sentence as entered. But a void sentence may not legitimately be increased, decreased, or maintained under Rule 35(b) if the original sentence was ultra vires and therefore void ab initio, because the lack of subject-matter jurisdiction cannot be forfeited or waived.
. The government also contends that Hartwell waived any right to seek review of its Rule 35(b) decision because he waived appeal of all sentencing issues (“on any ground whatever”) in his plea agreement. See United States v. Emerson, 349 F.3d 986, 988 (7th Cir.2003) (holding that waiver of appeal of sentencing issues included “appeals regarding reductions in sentence for cooperating with the government”); see also United States v. Benitez-Zapata, 131 F.3d 1444 (11th Cir.1997) (holding that the defendant waived his right to appeal the government's decision not to move for a downward departure). Hartwell argues that because the government breached the plea agreement, it may not rely on its waiver provision. See United States v. Bowe, 257 F.3d 336, 342 (4th Cir.2001). We need not address the waiver argument because we find that the government, in seeking to withdraw its Rule 35(b) motion, did not breach the plea agreement.