FEINBERG, Circuit Judge:
James L. Tenzer appeals from a judgment of conviction entered in February 1999 in the United States District Court for the Southern District of New York (Charles L. Brieant, J.) on an information charging him with four misdemeanor counts of failure to file timely tax returns for the years 1987-1990 in violation of 26 U.S.C. § 7203. The case comes before this court for the second time. In the first appeal, the government sought reversal of the district court’s order dismissing the information because Tenzer’s offer in compromise, submitted pursuant to the voluntary disclosure policy of the Internal Revenue Service (IRS), had been improperly turned down. We reversed, holding that Tenzer’s offer did not meet the requirements of that policy. United States v. Tenzer, 127 F.3d 222 (2d Cir.l997)(“2’e?mr /”). On remand, Tenzer again sought dismissal, based on allegedly new evidence produced by the government, but the district court held that the “mandate rule” precluded it. 4 F.Supp.2d 306, 310 (S.D.N.Y.1998). Following a conditional guilty plea, Judge Brieant sentenced Ten-zer to a year and a day incarceration, but declined to depart downward. Tenzer now appeals from his conviction and sentence. Tenzer argues that (1) the new evidence produced by the government on remand merits the reconsideration of our decision in Tenzer /; and (2) Judge Brieant did not fully understand his authority to downwardly depart. For the reasons set forth below, we affirm the conviction and remand for reconsideration of the sentence.
I. Background
A complete account of the events leading up to Tenzer’s prosecution was set forth in Tenzer I, and the two district court opinions issued in this case, 950 F.Supp. 554 (S.D.N.Y.1996) and 4 F.Supp.2d 306 (S.D.N.Y.1998), familiarity with which is assumed. We summarize below the facts and proceedings germane to the present appeal.
A. The Civil Proceedings
Tenzer is an experienced tax attorney and one of the principals of Margolin, Win-er and Evens (MW & E), a large accounting firm in Long Island, New York. It is uncontested that during the four years covered by the information, Tenzer earned substantial income but did not pay any tax. In October 1991, the IRS notified Tenzer that his account had been referred to the enforcement section and that he could still avoid enforcement action if he filed all his delinquent returns and paid all outstanding taxes within 10 days, or if he immediately contacted the IRS. Tenzer’s attorney, Myron Weinberg, contacted the IRS and requested an extension of time for filing the returns, which the IRS granted. In February 1992, Tenzer filed complete and accurate returns for three of the years involved (1987-1989), but did not enclose any payments.
In October 1992, Tenzer began negotiating a payment plan with IRS revenue officer Elizabeth Kishlansky. At that time, Weinberg advised Kishlansky that Tenzer wanted to enter into an installment agreement with the IRS. Kishlansky notified Weinberg that the IRS would not consider any installment plan unless Tenzer immediately filed his delinquent 1990 and 1991 returns. Tenzer filed those returns in November 1992.
[37]*37In January 1993, Kishlansky again met with Tenzer’s lawyers, including Ernest Honecker, formerly a high-ranking attorney for the IRS, to discuss Tenzer’s payment plan. At that meeting, Tenzer’s lawyers sought assurances from Kishlansky that Tenzer’s case was being handled as a civil matter. Tenzer’s attorneys also informed Kishlansky that rather than enter into an installment plan with the IRS, whereby all delinquent payments would be made, Tenzer intended to make an “offer in compromise,” that is, a partial payment in settlement of his tax liabilities. Kish-lansky responded that such an offer would only be considered if Tenzer became current on his taxes due for 1992, and if the offer reasonably reflected his assets and potential earnings. Tenzer’s lawyers then proposed $250,000 in compromise of his tax liability. Kishlansky indicated that she thought this amount would be unsatisfactory and that a more reasonable offer would be around $600,000. Nevertheless, when Tenzer submitted his $250,000 offer in a letter dated February 5, 1993, along with a $5000 payment, Kishlansky did not reject it but forwarded it to the IRS service center in Maine for review.
In early April 1993, the IRS returned Tenzer’s offer in compromise letter, as well as the $5000 payment, as “unprocessa-ble.” The letter returning the offer explained that “for offers based on inability to pay, you must generally offer an amount equal to or in excess of the amount shown as ‘equity in assets’ on your financial statement(s).” The letter also invited Tenzer to amend his offer. On April 14, 1993, Honecker wrote a letter to the IRS disclosing his intention to resubmit the same offer in compromise, and explaining that $250,000 was a reasonable amount in light of the “forced sale” value of Tenzer’s non-liquid assets. Later that month, Kishlan-sky notified Honecker that Tenzer’s file was being transferred to the IRS office in Brooklyn, which covered the region where most of Tenzer’s assets were located. Kishlansky also advised Honecker not to resubmit the offer until he was contacted by that office. At this point, all communication between Tenzer and the IRS regarding civil collection of his taxes ceased.
B. The Criminal Proceedings
In late June 1993, a “freeze” was placed on Tenzer’s file halting any further collection efforts. The freeze was ordered by the IRS criminal investigation division, as a result of a separate investigation into criminal tax evasion by JRD, a corporate client of Tenzer’s accounting firm.1 It was not until several weeks later that Tenzer’s attorneys learned of the freeze and that Tenzer was now a subject of an IRS criminal investigation. The collection freeze on Tenzer’s file was not lifted until February 25, 1999, shortly after Tenzer was sentenced by the district court.2
In November 1994, consultation between agents of the IRS and the tax division of the Department of Justice led to a recommendation that Tenzer be prosecuted for his failure to timely file his tax returns. The recommendation reflected the IRS’s conclusion that Tenzer did not meet the criteria of the voluntary disclosure policy. That policy provides that where a delinquent taxpayer comes forward and either pays or makes a bona fide arrangement to pay the applicable taxes, the IRS will not recommend prosecution. As a result of this policy, non-filers are seldom prosecuted. Nevertheless, in November 1995, the Justice Department charged Tenzer in the [38]*38four-count information that led to this appeal.
Subsequently, Tenzer moved to dismiss the information. Tenzer argued that he had satisfied the requirements of the voluntary disclosure policy, and that by initiating criminal proceedings against him, the IRS failed to follow its own policy, thereby violating his due process rights. Following a four-day evidentiary hearing, the district court agreed and dismissed the information. The court reasoned that although Tenzer’s initial offer in compromise was “laughable,” he had intended in good faith to reach an acceptable compromise agreement with the IRS and thus complied with the voluntary disclosure program. 950 F.Supp. at 562. The district court further concluded that the policy, which was widely publicized, afforded Tenzer due process rights, and that those rights were violated when the government decided, without affording Tenzer any advance notice, to freeze the civil collection effort and to prosecute him. Id. at 563. The district court also noted that Tenzer’s prosecution was “unique in the regular day to day administration of the [voluntary disclosure] Policy.” Id.
C. Tenzer I
In September 1997, we reversed the dismissal of the information, holding that prosecution was not barred because Ten-zer did not comply with the voluntary disclosure policy. 127 F.3d at 226. Because we held that Tenzer did not comply with the policy, we found it unnecessary to decide whether the policy afforded Tenzer any due process rights and whether those rights were violated by the IRS. Id. at 222 n. 1. The panel held that an “arrangement to pay” under the voluntary disclosure policy “may be a great variety of things, e.g., an installation payment agreement, a promise to pay on a specific date, or an offer of a lump-sum payment in compromise.” Id. at 227. We also concluded that “under the express language of the policy, the ‘bona fide arrangement’ must have been ‘made’ for the policy to apply.” Id. Because Tenzer’s offer had not been accepted by the IRS at the time he became the subject of a criminal investigation, his prosecution was not barred. Although we remarked that the government must negotiate in good faith toward the goal of achieving a settlement with the taxpayer, we found that in this case the government had provided Tenzer with sufficient opportunity to make an acceptable offer, and that he had not made such an offer. We concluded that “having thoroughly failed to bring himself within the letter of the voluntary disclosure policy, Tenzer cannot now claim the benefits of any protection it affords.” Id. at 228.3 Thus, we reversed the district court’s dismissal of the information and remanded to the district court.
D. Proceedings on Remand.
In the district court on remand, the government produced a new piece of evidence that prompted Tenzer to renew his motion to dismiss the information. The new evidence, a one-page computer-printout from the IRS processing center in Maine, shows that defendant’s offer in compromise was “pending,” as opposed to “rejected.” The printout included a notation by one IRS official to another demonstrating, Tenzer argues, that the IRS expected resubmission of his offer.4 On this basis, Tenzer argued to the district court that the IRS’s return of Tenzer’s first offer as “unprocessable” is different from a return of the offer as “rejected.” Since this distinction was not made clear on the previous appeal, Tenzer’s argument went, [39]*39this court’s decision in Tenzer I was based on the erroneous assumption that Tenzer’s offer was “firmly (and predictably) rejected.” 127 F.3d at 227. Additionally, Ten-zer urged the district court to rule that the IRS denied him due process by failing to continue the settlement negotiations with him — an issue, as already noted, that the panel in Tenzer I did not decide.
In a written opinion, Judge Brieant refused to grant Tenzer’s renewed motion to dismiss the information. The opinion stated that “[i]t seems to this Court that the IRS’ unilateral decision to terminate negotiations with Mr. Tenzer without warning was unfair and was in violation of Mr. Tenzer’s right to due process.” 4 F.Supp.2d at 309. But citing the “mandate rule,” Judge Brieant held that “[wjhile this argument is attractive, this Court concludes that our Court of Appeals has already ruled on this issue, even if in an indirect way. The commission of a district judge does not extend to correcting the decisions of the Court of Appeals, or to placing a gloss on such decisions which would alter the practical outcome.” Id.
Thereafter, Tenzer entered a conditional guilty plea to all four counts of the information pursuant to Fed.R.Crim.P. 11(a)(2), reserving his right to appeal the district court’s denial of his motion to dismiss and to appeal his sentence. The plea agreement set forth Tenzer’s net offense level at 13 and his criminal history category as I.
At sentencing, Tenzer moved for a downward departure on various grounds that he claimed took this case out of the heartland of the sentencing guidelines. The most contentious of these concerned Tenzer’s claim that his prosecution was unfair and in violation of his due process rights. Consistent with his two prior published opinions in this case, Judge Brieant stated at the sentencing proceeding, “I believe that the entire prosecution here is essentially unfair and in violation of public policies adopted by the Internal Revenue Service.... ” In ultimately refusing to depart on this ground, however, Judge Brieant explained, “I do not believe that these issues alone or taken together provide a reasonable basis for the Court to depart downwardly in Mr. Tenzer’s case.... [Wjhile courts have considerable power in connection with the fashioning of a sentence, a court must honor the mandates and decisions of the Court of Appeals, even when they’re totally wrong.” Judge Brieant also considered and rejected other grounds for departure. Tenzer was sentenced to concurrent terms of 12 months on counts one and two, and to concurrent terms of one day on counts three and four, making the total sentence a year and a day, at the bottom of the applicable guidelines range of 12 to 18 months. This appeal followed.
II. Discussion
A. Reconsideration of Tenzer I
We turn first to Tenzer’s claim that new evidence supports reconsideration of our decision in Tenzer I under an exception to the law of the case doctrine. That doctrine has two principal prongs. Under one, a court of appeals must usually adhere “to its own decision at an earlier stage of the litigation.” Doe v. New York City Dep’t of Soc. Servs., 709 F.2d 782, 789 (2d Cir.1983) (quoting United States v. Cirami, 563 F.2d 26, 33 n. 6 (2d Cir.1977)). We have stated that “we will not depart from this sound policy absent ‘cogent’ or ‘compelling’ reasons. The major grounds justifying reconsideration are an intervening change of controlling law, the availability of new evidence, or the need to correct a clear error or prevent manifest injustice.” Doe, 709 F.2d at 789 (internal citations and quotations omitted); see also United States v. Fernandez, 506 F.2d 1200, 1203 (2d Cir.1974). Nonetheless, “this branch of the doctrine, while it informs the court’s discretion, does not limit the tribunal’s power.” United States v. Uccio, 940 F.2d 753, 758 (2d Cir.1991) (citation and quotations omitted).
[40]*40The other prong of the “law of the case” doctrine, commonly referred to as the “mandate rule,” describes the duty of the district court on remand. “When an appellate court has once decided an issue, the trial court, at a later stage of the litigation, is under a duty to follow the appellate court’s ruling on that issue.... ” Cirami, 563 F.2d at 32. We believe that, in refusing to dismiss the information, Judge Brieant correctly adhered to our prior decision, even though he evidently felt that the new evidence supported his disagreement with that decision.
However, the law of the case doctrine does not bind us with the same rigidity as it binds the district court. Thus, we are free to reconsider our holding in Tenzer I, if, as Tenzer claims, the new evidence sheds substantial doubt on that decision. As described above, the new evidence consists of a computer printout listing Tenzer’s offer in compromise as “pending,” rather than as “rejected.” Tenzer argues that this evidence contravenes our finding in Tenzer I that “[Tenzer’s offer of $250,000] was firmly (and predictably) rejected,” 127 F.3d at 227, and that this finding led us to conclude that Tenzer’s negotiations with the IRS had ended and that no “arrangement to pay” would be reached. Tenzer further argues that this error was fueled by the government’s representation at oral argument in the prior appeal that the IRS rejected Tenzer’s offer “out of hand.” By contrast, Tenzer argues, the computer printout demonstrates that the IRS did not consider its negotiations with Tenzer to have ended and that Tenzer’s offer was not “rejected.”
The government responds that there is nothing new in the evidence relied on by Tenzer. First, it is not surprising that Tenzer’s case-file was designated as “pending,” since the collection efforts on it had been frozen pending resolution of the criminal proceedings, as required by IRS regulations. Further, whether Tenzer’s offer was “rejected,” or “returned as unprocessable,” was not material to our prior holding that an arrangement to pay had not been made, and therefore Tenzer could not enjoy the protection of the voluntary disclosure policy.
This court has previously reconsidered its decisions when presented with compelling new evidence. See Cirami, 563 F.2d at 33-35 (new “extraordinary” evidence of attorney negligence supported reconsideration); Fernandez, 506 F.2d at 1204 (reconsidered holding because new evidence conclusively contradicted government’s previous representation); but see United States v. Adegbite, 877 F.2d 174, 179 (2d Cir.1989) (declining to reconsider a previous Miranda holding based on new evidence concerning officer motivation in questioning suspect).
After carefully considering Tenzer’s arguments and the district court’s second opinion, we conclude that the new evidence does not warrant reconsideration of this court’s previous decision in this case. The holding in Tenzer I was premised on Ten-zer’s failure, from the time he was notified of his tax delinquency to the time he submitted his first offer, to arrive at an arrangement to pay that was satisfactory to the IRS. The Tenzer I panel had before it the letter from the IRS returning Tenzer’s first offer in compromise and the payment attached thereto. The court stated “[t]he IRS subsequently returned the check and rejected the offer as being ‘unprocessable’ because it was below the minimum amount.” 127 F.3d at 224. Although the court did not distinguish between “return as unprocessable,” and “rejection,” it clearly understood, as Tenzer had at the time he received the letter, that Tenzer could attempt to restart the negotiations by submitting another offer. In other words, the court was aware that the return of Ten-zer’s first offer did not necessarily mark the end of the negotiations between Ten-zer and the IRS. The point was not how we chose to characterize the IRS’s response to Tenzer’s initial offer, but rather our conclusion that it was not a bona fide [41]*41offer, that Honeeker’s proposed resubmission was unlikely to change the situation, and that, at this point, the IRS was entitled to refer the matter to the DOJ for prosecution. The court stated that “it is clear that Tenzer was given ample opportunity, including a reasonable length of time, to comply with the voluntary disclosure policy, yet repeatedly failed to do so.”5 Id. at 227.
While Tenzer, and Judge Brieant, evidently disagree with the panel’s conclusion in Tenzer I, the new evidence does not undermine it. The new evidence does not refer to the time period relevant to our prior decision, namely the period leading up to and including the return of Tenzer’s first offer in compromise. Thus, it does not change the fact that no arrangement to pay had been made. Rather, it simply raises the speculative prospect that had the negotiations continued, they might (or might not) have resulted in an agreement between Tenzer and the IRS at some point down the line. Such speculation is not an appropriate basis for reconsideration.
Since we do not disturb our holding in Tenzer I that Tenzer did not comply with the voluntary disclosure policy, we again find it unnecessary to decide whether the policy afforded Tenzer any due process rights and whether those rights were violated by the IRS.
B. Sentencing
We now turn to Tenzer’s claim that the district court misunderstood its authority to downwardly depart in sentencing. This aspect of the appeal involves two important doctrines: the mandate rule and the “substantial deference” due a district court judge in determining whether a departure from the sentencing guidelines is warranted. See Koon v. United States, 518 U.S. 81, 98, 116 S.Ct. 2035, 2046, 135 L.Ed.2d 392 (1996). We believe that, on the record before us, the latter policy controls the outcome of this part of the appeal. Our dissenting brother believes that the former does. We remand for reconsideration of the sentence because we conclude that the district judge also believed, in error, that the mandate rule precluded the exercise of his discretion with regard to a downward departure on certain grounds.
In the district court, Tenzer argued that downward departure was warranted in his case principally because of: (1) his voluntary disclosure to the IRS; (2) the prejudice caused by unfair actions taken by the prosecution and its agents; and (3) extraordinary rehabilitation and acceptance of responsibility. At sentencing, Judge Brieant opened his remarks on departure by noting, somewhat hyperbolically, that “courts in this Circuit have finally gained unlimited power to depart downwardly.” Nevertheless, when he turned to consider Tenzer’s first two claims, the judge concluded that he could not depart because of our mandate in Tenzer I. Specifically, the judge stated that although he believed Tenzer “was entitled to the benefits of [the voluntary disclosure] policy,” that could not “provide a reasonable basis for” a departure because “a court must honor the mandates and decisions of the Court of Appeals.” In this connection, Judge Brieant also found that to the extent that Tenzer has “been treated unfairly by the government ... this has ... already been a matter of appellate review,” and so is not a proper basis for departure. The judge concluded his ruling on this point by stating: “simply because I believe that generalized fairness requires that the Court take some step in connection with a downward departure,” doing so would amount to “a nullification by departure.” Also in connection with Tenzer’s claim that his prosecution was unfair, the judge correctly [42]*42noted that his disagreement with the use of prosecutorial discretion in this case was not an appropriate basis for departure. The judge then considered and rejected Tenzer’s third claim in support of a downward departure.6
It is well settled that a district court’s refusal to grant a downward departure is generally not appealable. United States v. Labeille-Soto, 163 F.3d 93, 100 (2d Cir.1998). We have carved out an exception to this rule for “cases in which the sentencing judge mistakenly believes that he or she lacks authority to grant a given departure.” United States v. Clark, 128 F.3d 122, 124 (2d Cir.1997). Although we normally presume that the district court understands the scope of its authority, we have held that “this presumption can be overcome where the record provides a reviewing court with clear evidence of a substantial risk that the judge misapprehended the scope of his departure authority.” Id. (internal citation and quotation marks omitted); see also United States v. Montez-Gaviria, 163 F.3d 697, 706 (2d Cir.1998). Tenzer argues, and we agree, that the passages from Judge Brieant’s colloquy reproduced above constitute the “clear evidence of a substantial risk” that the judge may not have fully understood his authority to depart in this case.7
Judge Brieant’s concern with “nullification by departure” led him to interpret the mandate rule too broadly. A corollary to the mandate rule we discussed above, see supra at 39-40, is that “upon remand the trial court may consider matters not expressly or implicitly part of the decision of the court of appeals.” Cirami, 563 F.2d at 33. Because the appeal in Tenzer I came from an order dismissing the information, the panel there had no occasion to decide any issues concerning sentencing, including any possible bases for departure. See United States v. Salemi, 46 F.3d 207, 209 (2d Cir.l995)(district court may impose a sentencing enhancement on remand based on factors not considered in the previous appeal); Uccio, 940 F.2d at 757-58 (same).
The panel in Tenzer I, 127 F.3d at 227, concluded that Tenzer did not qualify for the voluntary disclosure policy because “an arrangement” to pay had not been “made” at the time negotiations with the IRS ceased and the government decided to prosecute. That conclusion cannot be challenged by the district court. However, the court may consider certain aspects of Tenzer’s case that, although irrelevant for purposes of conviction, may well be relevant for purposes of sentencing. For instance, the court in Tenzer I noted that the voluntary disclosure policy is not satisfied by “mere offers to make payments.” Id. It also noted that, for purposes of the policy, “it is irrelevant that a taxpayer intends to eventually reach an agreement,” and that, therefore, “Tenzer’s alleged good intentions” were not an appropriate basis for dismissal. Id. These factors, however, may be considered by the district judge in his evaluation of the sentence if he believes them to be “mitigating circumstances of a kind, or a degree, not adequately taken into consideration by ... the [sentencing] guidelines.” U.S.S.G. § 5K2.0 (quoting 18 U.S.C. § 3553(b) (1994)).' Indeed, it is quite conceivable that — as occurred here— after a taxpayer makes a complete disclosure of his tax liabilities, and offers to settle with the IRS, negotiations with the [43]*43IRS nevertheless break down, and the IRS appropriately decides to proceed with a criminal prosecution. That does not mean that the district judge cannot then take into account at sentencing the taxpayer’s intentions and the conduct of the parties during the negotiations.
We have held previously that “absent express prohibition, a sentencing court ‘is free to consider, in an unusual case, whether or not the factors that make it unusual ... are present in sufficient kind or degree to warrant a departure.’ ” United States v. Core, 125 F.3d 74, 77 (2d Cir.1997) (citing United States v. Rivera, 994 F.2d 942, 949 (1st Cir.1993) (Breyer, C.J.)), cert. denied sub nom. Reyes v. United States, 522 U.S. 1067, 118 S.Ct. 735, 139 L.Ed.2d 672 (1998); see, e.g., United States v. Brennick, 134 F.3d 10, 14 (1st Cir.1998) (noting that taxpayer’s intent to pay and temporary delay in payment might support a departure); see also U.S.S.G. § 5K2.0 (quoting 18 U.S.C. § 3553(b) (1994)).
Judge Brieant’s sentencing colloquy and his two opinions clearly indicate that he thought certain elements present in Ten-zer’s case were unusual. In his first opinion, in which he dismissed the information because he concluded that Tenzer’s rights under the voluntary disclosure policy had been violated, Judge Brieant stated that “it is fair to say that Tenzer’s case is unique in the regular day to day administration of the policy.” 950 F.Supp. at 563. In his second opinion, issued after the remand in Tenzer I, the judge noted that he felt “Tenzer was [not] provided with reasonable notification regarding the status of the negotiations,” and that “the IRS’ unilateral decision to terminate negotiations with Mr. Tenzer was unfair....”8 4 F.Supp.2d at 309. In his sentencing colloquy, the judge again noted that this issue continues to be “of some concern to the Court.” It is entirely consistent with the precedent in this Circuit granting district court judges discretion in sentencing to allow this district court judge to depart downwardly if he finds that this case is sufficiently unusual or that it falls out of the heartland.9 See, e.g., Core, 125 F.3d at 77.
The dissent argues that by allowing the district court to consider certain aspects of this case for purposes of sentencing, we are, in effect, attempting “to revise,” or 'allowing the district court and Tenzer “to revise, the factual predicate for Tenzer’s offenses.” Dissent at 45, 47. This is not so. The “factual predicate” referred to is that Tenzer “failed to make the necessary and timely arrangements required for compliance with the voluntary disclosure policy.” Dissent at 47. We do not suggest that the district court can make different factual findings on that issue. But it is not inconsistent with Tenzer I for Tenzer to admit, as he fully does, that he violated the law [44]*44by failing to file his federal income tax for six years and still argue that his attempted entry into the IRS’s voluntary disclosure program, albeit unsuccessful in the end, can be taken into account for sentencing. Further, the district court should not be precluded from considering whether the IRS’s decision to terminate negotiations, despite its previous signals to Tenzer, see supra n. 8, was unfair in light of its usual administration of the voluntary disclosure policy. As the district court pointed out, such a finding is distinct from Tenzer I’s holding that Tenzer was given a reasonable length of time to comply with the policy.
In sum, we do not now decide whether any of these factors, taken individually or together, constitute an appropriate basis for departure; we simply hold that their consideration has not been ruled out by our mandate in Tenzer I. The district court is in the best position to evaluate, in the first instance, whether a downward departure is appropriate. See Koon, 518 U.S. at 98, 116 S.Ct. at 2047 (discussing the district court’s “institutional advantage” in determining whether a factor is sufficiently exceptional to warrant a departure). If the district court, upon reconsideration, concludes that the present record does not support a downward departure, it is free to leave the sentence undisturbed.
III. Conclusion
For the reasons set forth above we affirm the judgment of conviction and remand the district court’s sentencing decision for reconsideration- consistent with this opinion.